Scheduling Multirate Periodic Traffic in a Packet Switch
James Ryan Giles · 1997
This paper explores scheduling multiclass periodic traffic with deadlines in a time slotted system through an N \\Theta N switch. Different traffic streams may have different periods and different rates. Each packet must depart before the next packet in its stream arrives. An algorithm is given to schedule all traffic if each period evenly divides all longer periods, and if the utilization at each link is no larger than one. Furthermore, this algorithm can schedule all traffic with no restrictions on the periods if the link utilization does not exceed 1=4. A simple greedy algorithm is presented to schedule all traffic with no restrictions on the periods if the link utilization does not exceed 1=14. These algorithms can also be applied to more general deterministically constrained traffic when the link utilization is at most 1=4 and 1=14 respectively. 1. Introduction The problem of scheduling multirate traffic with guaranteed quality of service through a non-blocking N \\Theta N crossb...