Study On The Multicast Switching In High-speed Switching Architectures

With the accelerated pace of high-speed and broadband Internet, and the rise ofvarious new applications, it is required that the core equipments in network nodes-therouting and switching equipments can adapt to the rapid expansion of information andthe diversification of network applications. Multicast technology can effectively solvethe problem that information transmitted from one source to multiple destinations, so asto realize the high-speed multicast service transmission, effective use of networkresources, save network bandwidth and reduce the network load. As Crossbar switchnetwork is the mainstream switching fabric in current core routers, a large amount ofscheduling algorithms supporting unicast services based on the Crossbar switchingfabric have been proposed with good performance and simple implementation. Withmulticast services supporting, there are some problems with existing multicastscheduling algorithms such as high speed-up, high complexity and hard implementation,which lead to some scalability issues, and therefore cannot provide effective multicastswitching in high-speed environments. As a result, the key issues of realizablehigh-speed switching fabrics and multicast scheduling algorithms are investigated inthis thesis. The major contributions of this thesis are as follows.1. We research on the multicast HoL (Head of Line) blocking alleviation schemefor input-queued Crossbar switching fabrics, and present three scalable multicastscheduling algorithms (MDRR、 MMWR and MMFR). Most existing multicastscheduling algorithms allocate one FIFO (first-in-first-out) queue for multicast traffic ateach input, and the performance achievable by switches is limited because of thewell-known multicast HoL blocking. Other algorithms maintain a small number ofFIFO queues for multicast traffic at each input to reduce the HoL blocking problem,however, multiple iterations, as well as a large amount of control message exchange arerequired to achieve high switching performance, which makes it difficult to implementin a high-speed environment. As a result, we propose three scalable non-iterativetwo-phase (request-grant) multicast scheduling schemes. The proposed schedulingsemploy new multicast HoL blocking alleviation schemes by fully using the one-to-manyproperty of multicast cells，as well as the diversity of fan-out sets with HoL cells, whichreduces the complexity of schedulings efficiently with very little loss of switchingperformance, and offers a reasonable choice for high-speed input-queuedswitches/routers. 2. Based on the study of multicast scheduling algorithm, we present a scalableintegrated scheduling algorithm that supporting unicast and multicast trafficsimultaneously for Crossbar switching fabrics. Most integrated three-phase(request-grant-accept) scheduling algorithms presented are, in fact, a combination ofearlier unicast and multicast algorithms unified in one integrated scheduler, and multipleiterations are needed to improve the switching performance. As link speed growsdramatically, high-speed switches have less and less time to perform scheduling, thusiterative scheduling schemes are difficult to implement. We propose a non-iterativetwo-phase (request-grant) integrated scheduling in this thesis to address the scalabilityproblems, in which the unicast scheduling and multicast scheduling are performedsequentially to increase the matching size by avoiding the grant-blocking in each timeslot, and the complexity of the scheduling can also be reduced efficiently by employingthe two-phase (request-grant) scheduling scheme.3. Motivated by the load-balanced Birkhoff-von Neumann switches, we propose amulticast load-balancing two-stage switching architecture to support the mixed trafficswitching. The unicast scheduling and multicast scheduling are performed in parallelwith pipeline method at different stages. The first stage of the switching fabric performsswitching for unicast traffic and load-balancing for multicast traffic, while the secondstage performs switching for multicast traffic, as well as uses an integrated schedulingto solve the output contentions for unicast and multicast traffic. The proposed two-stageswitching fabric is more tolerant to unbalanced mixed traffic model, and reduces thescheduling complexity dramatically, which is more suitable for high-speed applications.4. The study on the3-stage Clos network has been increasingly valued by theresearchers as its good scalability. However, little research has been done on supportingmulticast traffic efficiently in the3-stage Clos network. The existing implementationscheme with3-stage Clos networks supporting multicast traffic is that multicast cells aredivided into several unicast cells at each input according to the fan-out sets, and thenadopts unicast scheduling to schedule the copied cells. This implementation schememaintains the limitations of existing unicast schedulings at high-speed, at the same time,since the copied cells experience a separate queuing and scheduling process, it alsocauses the cells belonging to the same multicast cell to get out of sync at the outputs. Inaddition, as same queues are associated with both unicast and multicast traffic, one ofthe bursty traffic could influence the switching performance of the other normal traffic,and also reduces the memory utilization rate at each input. In order to solve theseproblems, we propose a distributed multicast orthogonal scheduling algorithm, as well as a distributed unicast and multicast integrated orthogonal scheduling algorithm in thisthesis. By taking each Crossbar module as the elemental scheduling unit, the proposedalgorithms adopt the rotated orthogonal routing at each timeslot to solve the outputcontentions arisen at each switching module of the second stage, in which iterations andcontrol message exchanged between stages are not required, and have lower timecomplexity and control message complexity, which improve the scalability inhigh-speed switching environments.