"Using Load-Balancing To Build High-Performance Routers," Ph.D. Oral Examination, Stanford, February 2004.
The committee members were Professors David Miller (chair), Mark Horowitz, Balaji Prabhakar and Nick McKeown.
A related paper is:
I. Keslassy, S.-T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard and N. McKeown, "Scaling Internet Routers Using Optics," ACM SIGCOMM '03, Karlsruhe, Germany, August 2003.
Interested readers can also check my Ph.D. dissertation, the Optics in Routers project and my publications.
I was asked this question so often that I needed to provide an answer! Using Powerpoint in Windows XP:
- First, click on Slide Show -> Custom Animation to open the custom animation sidebar.
- Then, pick your packet.
- Finally, choose Add Effect -> Motion Paths -> Draw Custom Path -> Curve, and pick the successive points of the curve that this packet will follow. Click on the button Escape to end the curve. You can then change the animation speed on the right, and the curve points by right-clicking on them.
The capacity of Internet routers grows more slowly than the growth in traffic. Therefore, unless something changes, routers will become the bottleneck in the backbone of the Internet. Meanwhile, network operators will continue to place more and more routers in each central office. But such ad-hoc aggregations of routers do not allow operators to fully utilize their expensive long-haul links. The router clusters are also increasingly difficult to manage, and waste significant capacity interconnecting the routers. Therefore, operators would like to replace these routers with a single large router per central office. However current router architectures are already limited by the complexity of their centralized scheduler. Hence a new architecture is required to build such a large router.
In my talk, I will advocate the use of the load-balanced switch architecture to scale routers. A load-balanced switch spreads packets inside the router before forwarding them to their destination, thus removing the need for any centralized scheduling. However, pathological traffic patterns can reorder packets and drastically reduce throughput in a load-balanced switch. I will introduce a scheme that prevents packet reordering and provides a utilization guarantee for any adversarial traffic pattern. I will also show how to incorporate passive optical devices into the load-balanced switch. Finally, I will demonstrate how this architecture can scale and be fault-tolerant to linecard failures. In conclusion, I will argue why this load-balanced switch architecture is ideal for scaling high-capacity routers.
Title: "Using Load-Balancing To Build High-Performance Routers"
When: Friday, February 20, 1:00pm - 2:00pm (refreshments served at 12:45pm)
Location: Packard 101 (how to get there: , , )