Providing performance guarantees with crossbar-based routers

The backbone of the Internet is comprised of a network of high performance routers. Every router receives packets and forwards them to the correct outgoing port. Routers are designed to achieve a specific capacity, and network operators expect routers to provide predictable performance. This thesis is about how to design practical routers with predictable performance.; Network operators expect certain performance characteristics; for example, if the arrival rate is less than the router's advertised capacity, they can reasonably assume the router can handle the traffic. Somewhat surprisingly, no commercial router can do this today. And some operators would like to provide customers with service guarantees such as guaranteed bandwidth and delay through their network. To provide these guarantees, each individual router within the network must also provide bandwidth and delay guarantees.; Most high performance routers built today use crossbars and a centralized scheduler. Building crossbar-based routers which provide these performance guarantees is difficult using current technology. Scheduling the crossbar is a bottleneck and limits scalability. It also makes it impractical to provide performance guarantees. As line rates and the number of ports increase, the scheduling problem will only become more difficult.; This thesis describes crossbar scheduling algorithms that provide deterministic throughput, bandwidth, and delay guarantees. Each technique is based on an analytical counting method. The first result---for crossbar switches---is primarily a theoretical observation of what is possible, but is too complex to be practical. To make the result more practical, I describe crossbars with a small amount of internal buffering. A buffered crossbar simplifies the scheduling process and provides a practical way to build routers with performance guarantees.