Research On The Design Of Scheduling Algorithms For Input Queued Scalable Switches

Switch fabric is a core element of high performance switch and router. How toincrease its switching capacity and the predictability of quality of service is a hot andhard topic of network research over the past decade. A typical switch fabric consists ofthree elements: input ports, output ports and switch core. To avoid cells from differentinput ports being sent to the same output port at the same time, it is necessary to placebuffers at output ports or input ports, and two buffering schemes are prevalent: outputqueueing (OQ) and input queueing (IQ). Although the OQ switches provide good qualityof service guarantee (100% throughput, bounded delay, bandwidth fairness etc.), thememory bandwidth requires the sum of all the input ports bandwidth. Therefore thescalability of OQ switches is greatly limited. Compared with the OQ switches, the IQswitches have a memory bandwidth requirement comparable to the line rate, and suchgood scalability makes IQ swith fabrics becoming the prevalent choice of highperformance router. Since the scheduling algorithm is responsible to transfer the cellsfrom the input ports to the output ports across the switch core, it plays the key role inimproving the switch devices utilization and the quality of service guarantee. From theview points of the scalability of switching capacity and the predictability of quality ofservice, this thesis studied the design of scheduling algorithms for some types of scalableswitch fabrics. At present, crossbar is often employed to construct the switch core because of itsnonblocking property, and one centralized scheduler is used to schedule the cells acrossthe crossbar. For this switch fabric, maximum weighted matching (abbr. MWM)algorithms have been proved to achieve 100% throughput and the bounded averagedelay. However such type of algorithms has high time complexity O(N3). This thesisstudied MWM approximations based on local search technique. Combined with theparallel computing feature of local search, we presented a randomized schedulingalgorithm and a deterministic scheduling algorithm. Furthermore, we proved thestability of the presented algorithms. Compared with the existing approximations, ouralgorithms have lower average delay. The buffered crossbar switch fabric is an ideal choice to build the terabit-capacityrouter because of its features of distributed storage and distributed scheduling. Since theround-robin algorithms are easy to be implemented by hardware, such a type ofalgorithm has been widely studied. Although the previously proposed round-robinalgorithms provide nearly 100% throughput under uniform traffic, the througput ofsuch algorithms will drop down under nonuniform traffic patterns. In order to solve thisproblem, we presented a class of dual round-robin algorithms which is different from thesingle round-robin pointer usage. For our algorithms, each input scheduler is associatedwith a primary pointer and a secondary pointer. The input queue pointed to by theprimary pointer has the highest priority to be scheduled;the input scheduler decideswhen to update the primary pointer according to the status of input queue. When theinput queue pointed to by the primary pointer is blocked by the flow control, thesecondary pointer is used to service other queues in a fair way. The extensive simulationsshow that the performance of buffered crossbar switch under nonuniform traffic isgreatly improved by introducing the dual round-robin pointers method.For buffered crossbar switch fabric, the credit based flow control is often used.Under such mechanism, in order to keep work-conserving of input and output port, thecapacity of each crosspoint buffer should be at least equal to the product of the line rateand the fabric-internal round-trip latency. Such large crosspoint buffer requirement willbe a hurdle to implementing multiterabit switches. This thesis studied the quality ofservice of buffered crossbar switches from the point of view of smooth switching. A newtype of switch core which supports the flow level smooth switching is presented. Suchswitch fabric adopts rate based flow control method, which permits arbitraryfabric-internal latency. Under admissible traffic, it provides 100% throughput and nocell loss with only four cells at each crosspoint buffer.