High-performance variable-length packet scheduling algorithm for IP traffic

A high-performance variable-length packet scheduling algorithm is proposed for efficiently accommodating IP traffic in input. queued crossbar switches. It uses a rotating priority(round-robin) arbitration and a masking operation for variable-length packets. This algorithm achieves 100% throughput with a single iteration for uniform IP traffic and performs better in terms of packet latency and similar cell latency, compared with the well-known iSLIP cell-level scheduling algorithm.

I. Introduction

Over the past few years, it has been very difficult to accommodate explosively growing internet traffic demands by means of electrical router technologies. In order to solve this problem, newly emerging routers are being combined with new optical technologies. Recently, many large-scale, fast routers have used input-queued crossbar switches with internal optical links and virtual output qeueue(VOQ) for preventing head-of-line(HOL) blocking. In order to minimize input/output contentions, it is very important to find a simple, fast, and efficient scheduling algorithm for high-speed input-queued routers using VOQ[1]. Many cell-by-cell scheduling algorithms have been proposed and they include PIM[2], RRM, and iSLIP[3]. However, these cell-by-cell scheduling schemes can increase time complexity[4]. In high-speed routers, it is a heavy load to segment long IP packets into fixed-size cells and reassemble each cell for recovering the original packet at the output interface of the switch fabric. Moreover, if a optical switching technology is introduced, it is even more difficult to segment optical-domain packets.