Research And Implementation Of Scheduling Algorithms In High-speed Router Switches

Core routers must provide more switch bandwidth and more precise QoS control to keep up with the development of Internet. Under the limitation of memory access speed, input-buffered crossbar can provide more bandwidth than the traditional share-memory switch. So more and more input-buffered crossbar switches are used in core routers and the crossbar scheduling algorithm(SA) has become a research hotpot.The research of SA includes high performance and fair algorithm, multicast-supported algorithm and QoS-supported algorithms. In recent years, many previous works have been done, but almost all the SAs presented are too complex to be implemented. That is why few of them are really used now.To solve this problem, this paper presents a new way, called stride scheduling, to design SA. Different to other ways, stride scheduling guarantee fair in much longer time scale instead of .in every schedule, so it can be easily implemented. On the light of stride scheduling, this paper present a new SA called ISP. Comparing SA used in cisco routers. ISP is not only high performance but also readily to be implemented. We can also achieve many other new SAs by extending ISP. These new SAs include a multicast algorithm-E1SP. a priority algorithm-OSP. which supports DiffServ, and a bandwidth reservation algorithm-R1SP. which supports IntServ. We also introduce how to implement these three SAs in hardware.Routers deal with packets with variable length, while crossbar switches deal with fixed length cells. So at the input port of a switch, packets must be segmented to many cells first, and at the output of a switch, cells should be reassembled to packets again. Only a whole packet is reassembled, does it can be sent to output lines. This paper presents a model, called Pipe, to simplify the process of reassemble and analyses the SA in the output port. Under some conditions, the maximum buffer needed and the maximum packet delay taken by reassembling can be achieved. This result can be used to design a crossbar switch.This paper also- introduces our works on implementation a router switch, called KDS50. using ISP and Pipe model. The whole design can be implemented in FPGA/EPLD. Using Cadence Verilog tools, we emulation the design and give the bandwidth utility and delay property of KDS50 under variable packet length. KDS50 has been used in our core router design.