The Iterative Scheduling Algorithms For Input-queued Switches

The ever-increasing demand for Internet bandwidth is further fueled by the ongoing shift to cloud computing. In a cloud computing architecture, services and data reside in shared data centers, and are accessed by users over the Internet. Huge amount of traffic will be transported between users and data centers, and between servers within a data center. To meet the need for high-speed and low-latency switching, it’s highly desirable to have a unified switch fabric for all types of traffic. There are generally two approaches in constructing a switch fabric, input-queued and output-queued. In each time slot, the input-queued switch only allows one packet to be sent/received by each input/output and no speedup is required. Thus input-queued switch is more suitable for high-speed implementation and also the most widely adopted switch fab-ric. The scheduling algorithm for input-queued switch is the key to realize low-delay and high-throughput performance. With the increase of switch scale, distributed schedulers are adopted and distributed scheduling algorithms are one of the very hot and promising topics today. In this paper, we mainly study the monolithic and distributed iterative scheduling algorithms for input-queued switch.Firstly, we study the monolithic iterative scheduling algorithms for input-queued switch. The iterative scheduling algorithms can achieve Maximal Size Matching (MSM) and are the most widely adopted. Iterative scheduling algorithms usually consist of three phases, request, grant and accept. Although some iterative algorithms can achieve good performance, there’s still space for them to be modified and improved. In this paper, we firstly make some modifications on the existing algorithm RR/LQF (Round Robin with Longest Queue First). On one hand, we amend the request phase to cut down the packet delay and improve the performance. On the other hand, we raise a pipelined mechanism of updating packet counters to reduce the time complexity from O(NlogN) to O(logN), which is more suitable for high-speed scalability.Secondly, we put forward a max-min fair monolithic iterative scheduling algorithm GR-R/LRR (Global Round Robin with Local Round Robin). GRR/LRR adopts the global round robin (RR) schedule as the highest priority to increase the match size. When the global RR fails, GRR/LRR utilizes a local port RR pointer to schedule. GRR/LRR is simple to implement with complexity O(1). When GRR/LRR executes for a single iteration, it can obtain the best per-formance among all the algorithms with the same overhead and complexity. When GRR/LRR executes for N iteration, it can tighten the speedup bound to 2-1/N. What’s more, GRR/LRR satisfies max-min fairness criterion in despite of traffic patterns.At last, we study the distributed iterative scheduling algorithm for input-queued switch. Due to the limited I/O pins in a centralized monolithic scheduler, the multi-chips implementation is essential for input-queued switch with the unilateral port number N≥ 64. At this case, distributed schedulers are placed at each input/output port. Thus the propagation delay between different chips lead to large round trip time (RRT) between the input and output port, which is usually multiple time slots. In most of the existing distributed scheduling algorithms, the average queuing delay of packet is always larger than RTT. To break this bound, we raise a Request Prediction (RP) mechanism. When applied to the distributed scheduling algorithms, RP can cut down the packet queuing delay below RTT. RP is simple to implement with complexity O(1). What’s more, RP can be adjusted to fit for a specific scheduling algorithm.