Output Initiated Fair Scheduling Algorithm for Large-Scale Input Buffered Switches

In order to provide quality of service guarantee, a switch may have to maintain a large number of queues in the high-speed network environment. However, when considering the cost of hardware implementation, the number of queues maintained in switch will become a decisive factor. In this paper, we present a novel output initiated parallel matching (OIPM) algorithm for large-scale input buffered switches. In our proposed switch architecture, packets are buffered in a shared memory at each input port and K first-come-first-serve queues are maintained at each output port for K classes of traffic packets. The number of queues maintained at each output port is equal to the number of traffic classes that is comparable less than the VOQ-based switch dramatically. The OIPM algorithm needs only request-grant matching phases, it is comparable less than request-grant-accept phases required in PIM-similar matching algorithms. That means the OIPM algorithm takes less arbitration time and is much feasible in implementation. Moreover, our proposed OIPM algorithm guarantees starvation free, non-interleave of packet, in-order packet delivery, and achieves weighted fairness among traffic classes. Based on the experimental results, the input buffered switch with OIPM algorithm presents well performance for high speed network with a speedup factor of 2. And it is practicable for the implementation of large scale switch and works in high-speed network environment.