High-Performance Routers

Nian-Feng Tzeng
Center for Advanced Computer Studies
University of Louisiana at Lafayette

Existing or earlier proposed routers often lacks scalability because they utilize a shared backplane bus or crossbar to interconnect line cards (LC's) and forwarding engines (FE's). Their packet classification mechanisms could easily become performance bottlenecks, as the router's speed increases or the routing/filter table sizes grow. This project investigates router architecture with good scalability and capable of forwarding hundreds of millions of packets per second, in order to keep up with future transmission technologies. It aims to help advance the state-of-the-art of router design and to enable large networking configurations.

Current routers rely on enhanced software search algorithms or specific hardware support to meet the IP address lookup rate (of up to 5 million lookups per second per lookup unit), but a future high-speed network calls for routers with aggregate lookup rates of some two orders of magnitude higher than a lookup unit presently can offer. Hardware-assisted mechanisms for fast packet forwarding appear promising. In particular, the use of caches to hold lookup results can fulfill subsequent lookup requests for identical destinations immediately without resorting to FE's for lookups, reducing the mean lookup latency tremendously. Unlike other software- or hardware-based forwarding improvement approaches, our hardware-assisted mechanisms can be effectively applicable to both IPv6 and IPv4, ideally suitable for scalable high-performance routers.

This work has been carried out in the Computer Architecture and Networks Laboratory (CAN) Lab, which houses a wide range of computers and communication gear. Please visit Computer Architecture and Networks Laboratory for more details.

Publications

• N-F. Tzeng, Multistage-Based Switching Fabrics for Scalable Routers, to appear in IEEE Transactions on Parallel and Distributed Systems, April 2004.

• N-F. Tzeng, SPAL: Speedy Packet Lookups under Distributed Router Architecture, submitted for possible presentation.

• N-F. Tzeng, Hardware-Assisted Design for Fast Packet Forwarding in Parallel Routers, Proc. 2003 Int'l Conference on Parallel Processing, Oct. 2003, pp. 11-18. Abstract, PDF (387K).

• N-F. Tzeng and M. Mandviwalla, Performance Evaluation of Router Switching Fabrics, Proc. 9th IEEE Int'l Conference on Parallel and Distributed Systems, December 2002, pp. 542-547. Abstract, PDF (282K).

• N-F. Tzeng and R. Batchu, Design and Evaluation of Scalable Switching Fabrics for High-Performance Routers, Proc. 31st Int'l Conference on Parallel Processing, August 2002, pp. 167-174. Abstract, PDF (521K).

• N-F. Tzeng and M. Mandviwalla, Cost-Effective Switching Fabrics with Distributed Control for Scalable Routers, Proc. 22nd IEEE Int'l Conference on Distributed Computing Systems, July 2002, pp. 65-73. Abstract, PDF (513K).

• K. Vibhatavanij, N-F. Tzeng, and A. Kongmunvattana, Simultaneous Multithreading-Based Routers, Proc. 29th Int'l Conference on Parallel Processing (ICPP '00), Aug. 2000, pp. 362-369. Abstract, PDF (738K).

• N.-F. Tzeng, K. Ponnuru, and K. Vibhatavanij, A Cost-Effective Design for ATM Switching Fabrics, Proc. 1999 IEEE Int'l Conference on Communications (ICC '99), June 1999, pp. S37.4.1-5. Abstract, Compressed PDF (81K).

Funding

• National Science Foundation under Grants EIA-9871315 and CCR-0105529.
• U.S. Army Research Office via Grant/Cooperative Agreement No. DAAG55-98-1-0240.
• Board of Regents, State of Louisiana under Contracts No. DOD/LEQSF(1997-01)-06, No. LEQSF(1998-99)-ENH-TR-101, and No. LEQSF(2000-01)-ENH-TR90.