Frame-based packet scheduling algorithms for input queued switches
Xiaojun Shen, Jianyu Lou · 2006
With good scalability, input-queued switches have become the main switch architecture used in today's high speed networks. However, input-queued switches need efficient packet scheduling to satisfy growing bandwidth demands and high quality of services (QoS). Existing scheduling algorithms mainly focus on throughput guarantees but are weak in providing deterministic delay guarantees. In order to provide differential QoS guarantees, this dissertation studies the deadline guaranteed packet scheduling problem that aims to schedule a maximum number of packets from input ports to their destined output ports before their deadlines. This problem has been proved to be an NP-complete problem, and traditionally EDF (Earliest Deadline First) or similar approaches have been the only ways to deal with it. This dissertation proposes a novel algorithm called Flow-based Iterative Packet Scheduling (FIPS) algorithm which is fundamentally different than the EDF approach. Simulations show that FIPS outperforms EDF with a much higher success rate and a much lower packet dropping ratio. To further improve the scalability, frame-based scheduling is assumed instead of slot-by-slot-based scheduling. Frame-based scheduling groups a constant number of consecutive time slots into a frame. It buffers arriving packets in the current frame and schedules them into the next frame. Frame-based scheduling thus computes a schedule per frame rather than per slot to reduce the frequency of schedule computation. Motivated by the potential savings in the overhead of segmentation and reassembly in handling variable sized packets, this dissertation also studies packet-mode scheduling where all constituent cells of a packet must be consecutively transmitted from an input to their destined output without interleaving. A formula is given on the relation between the frame sizes and the packet sizes that classifies the conditions for the scheduling problem to be polynomial solvable, or otherwise NP-hard. An interesting result is that the NP-hardness is not solely determined by how many different packet sizes are involved. It may be polynomial solvable even if many different sizes occur in the set, while it may be NP-hard with just two packet sizes present.