Switch port scheduling scheme for IP forwarding

Abstract

The internet is overwhelmed with traffic, with user demand for bandwidth well in excess of supply and there is bottleneck in router. In order to improve the performance of router, the efficiency of packet scheduling algorithm in scheduler and buffering policy in each I/O port are important. It has been recently shown that an input-queued switch with an appropriate buffering policy (for example, VOQ; Virtual Output Queueing) and scheduling algorithm (for example, maximum weight matching algorithm) can achieve 100% throughput for independent arrival processes in theory. Since Maximum Weight Matching algorithm is too complex to implement in hardware, previous work proposed i-MWM (iterative Maximal Weight Matching) to implement simply in hardware. Port partitioning concept is employed to reduce the computational burden of the scheduler within a switch. The input and output ports are divided into two groups such that the matching algorithm is implemented within each group in parallel. The matching is performed by exchanging input and output port groups at every time slot to handle all incoming traffics. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching with port partitioning (MMPP) are presented. MMPP has the lowest delay for every packet arrival rate. The buffer size on a port is approximately 20-60 packets depending on the packet arrival rates. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm. And this thesis proposes also Dynamic queue scheduling algorithm to support the utility of both DC (Delay-Critical) and LC (Loss-Critical) packets simultaneously.