Implementation of Scalable Routers with Direct Networks

Abstract: In the Internet, the exponential growth of user traffic has been driving routers to run at higher capacity. Traditional routers consist of line cards and centralized switching fabrics. The centralized switching fabric in such a router, however, is becoming the bottleneck for its limited port numbers and complicated scheduling algorithms. In addition, the fabric is the single point of failure (SPF) in the router. Direct networks, such as 3-D Torus topology, have been successfully applied to the design of scalable routers. They show good scalability and fault tolerance. Unfortunately, its scalability is limited in practice. This paper introduces another type of direct network, called cellular router (CR). With a little modification, this network shows excellent topological properties. Based on this network, two classes of minimal routing algorithms are introduced. The load-balanced minimal routing (LBMR) algorithm makes use of path diversity and shows low latency and high throughput on both uniform random (UR) and Tornado traffic. This paper also discusses some other aspects of the routing algorithms, such as effects of queue length and scheduling algorithms. The CR architecture is a promising choice for the design of scalable routers