Request-grant scheduling for congestion elimination in multistage networks

Abstract

This thesis considers bu ered multistage interconnection networks (fabrics), and investigates methods to reduce their bu er size requirements. Our contribution is a novel ow and congestion control scheme that achieves performance close to that of per-ow queueing while requiring much less bu er space than what per-ow queues would need. The new scheme utilizes a request-grant preapproval phase, as many contemporary bu erless networks do, but its operation is much simpler and its performance is remarkably better. Traditionally, the role of requests in bu erless networks is to reserve an available time slot on each link along a packet's route, where these time slots are contiguous in time along the path, so as to guarantee non-conicting packet transmission. These requirements impose a very heavy toll on the scheduling unit of such bu erless fabrics. By contrast, our requests do not reserve links for a speci c time duration, but instead only reserve space in the bu ers at their entry points; e ectively, the scheduling decisions that concern di erent links are decoupled among themselves, leading to a much simpler admission process. The proposed scheduling subsystem comprises independent single-resource schedulers, operating in a pipeline; they operate asynchronously to each other. In this thesis we show that the reservation of bu ers in front of critical network links {links that are unable to carry the potential aggregate demand{ eliminates congestion, in the sense that tra#c ows seamlessly through the network: it neither gets dropped, nor is excessively blocked waiting for downstream bu ers to become available. First, we apply request-grant scheduling to a single-stage switch, with small, shared output queues, which serves as a model for the more challenging multistage case. We demonstrate that, in principle, a very small number of fabric bu ers su#ces to reach high performance levels: with 12-cell bu er space per output, performance is better than in bu ered crossbars, which consume N cells of bu er space per output, where N is the number of ports. In this single-stage setting, we study the impact of input contention on scheduler performance, and the related synchronization phenomena. During this work, we have introduced a novel scheduling scheme for bu ered crossbar switches that makes bu er size independent of the round-trip-time between the linecards and the switch. We then proceed to the multistage case. Our main motivation and our primary benchmark is an example next-generation fabric challenge: a 1024#1024, 3-stage, non-blocking Clos/Benes fabric, running with no internal speedup, made of 96 single-chip 32#32 bu ered crosssbar switching elements (3 stages of 32 switch chips each). To eliminate congestion in the fabric, we carefully apply our request-grant scheduling protocol. We demonstrate that it is feasible to implement all schedulers centrally, in a single chip. Besides congestion elimination, our scheduler can guarantee 100 percent in-order delivery, using very small reorder bu ers, which can easily t in on-chip memory. Simulation results indicate very good delay performance, and throughput that exceeds 95% under unbalanced tra#c. Most prominent is the result that, under hotspot tra#c, with almost all output ports being congested, the non-congested outputs experience negligible delay degradation. The proposed system can directly operate on variable-size packets, eliminating the padding overhead and the associated internal speed-up. We also discuss a possible distributed version of the scheduling subsystem. Our scheme is appropriate to deal with heavy congestion; in systems that need to provide very low latency under (uncongested) light tra#c, one would apply this scheme when the load exceeds a given threshold. Lastly, we consider some blocking network topologies, like the banyan. In a banyan network, besides output ports, internal links can cause congestion as well. We show a fully distributed scheduler for this network, that eliminates congestion from both internal and output-port links.