Scheduling algorithms for scalable high-performance packet switching architectures

by 1975- Li, Xike

Packet switching fabrics constitute a fundamental building block of all Internet routers. As a core technology, the switching engine is responsible for enabling multiple input (ingress) ports to be dynamically linked to output (egress) ports, thereby allowing packets to effectively traverse the router. Scheduling algorithms, which play a key role in switching fabrics, determine the dynamic con…gurations of the input-output matchings. The ever growing need for additional bandwidth and more sophisticated service provisioning in nextgeneration networks necessitates the introduction of scalable packet scheduling solutions that go beyond legacy schemes. Switch architectures can be coarsely classi…ed into two categories, in accordance with the queuing mechanism they employ. In input-queued (IQ) architectures arriving packets are bu¤ered at the ingress ports, awaiting to traverse the switch. In output-queued (OQ) architectures, arriving packets are immediately transferred to their corresponding egress ports at which they are bu¤ered until their departure time. Scheduling algorithms for these two families of architectures vary signi…cantly, yet they share the goals of maximizing throughput while minimizing the delay experienced by the packets. This dissertation presents novel architectures and algorithms pertaining to both IQ and OQ switch designs. In the context of IQ switches, due to the increase in link rates directly resulting in a decrease of packet duration times, packet-by-packet switching is no longer considered a pragmatic approach for designing scalable systems. To address this challenge, this dissertation advocates the utilization of frame-based algorithms that relax the timing constraints imposed on scheduling algorithms while retaining key performance characteristics. The algorithms are studied via theoretical stability analysis and evaluated by means of statistical simulations. In the context of OQ switching, an e¢ cient memory management algorithm that alleviates some of the principal limitations of OQ designs is presented and studied. In an e¤ort to introduce pragmatic solutions to the challenges associated with highcapacity packet switches, the focus of this work is to guarantee performance and scalability while utilizing o¤-the-shelf components that can be easily combined with custom hardware circuitry. We conclude by showing that the developed architectures and algorithms provide v solid cost-e¢ cient foundations for supporting next-generation Internet switches and routers. vi