Method to schedule multiple traffic flows through packet-switched routers with near-minimal queue sizes

Abstract

A method to schedule multiple traffic flows through a multiplexer server to provide fairness while minimizing the sizes of the associated queues, is proposed. The multiplexer server minimizes a quantity called the maximum Normalized Service Lag for each traffic flow. In each time-slot, the normalized service lag of every traffic flow may be updated by adding the normalized lag increment value, whether or not there is a packet in the queue associated with the flow. In each time-slot, a multiplexer server selects a traffic flow to service with an available packet and with the maximum normalized service lag. When the traffic rate requested by each traffic flow is stable, the multiplexer server schedule may repeat periodically. Efficient methods to compute periodic schedules are proposed. The methods can be applied to packet-switched Internet routers to achieve reduced queue sizes and delay.

1 . A method of transmitting a plurality of traffic flows to N output ports through a switch during a scheduling interval, comprising:
 receiving each of said plurality of traffic flows, each of said plurality of traffic flows associated with a respective guaranteed data rate;   buffering packets in each of said plurality of traffic flows in one of N input queues, in dependence on the output port for that traffic flow;   in a switching interval, transmitting a packet from a chosen traffic flow from a selected one of said N input queues to the output port for that selected one of said N input queues;   wherein said chosen traffic flow is chosen as having the largest positive normalized service lag among traffic flows having buffered packets in said selected one of said N input queues, determined over a period of time from the beginning of the scheduling interval until the beginning of the switching interval;   wherein the normalized service lag of each traffic flow reflects the difference between the amount of traffic that could be transmitted at said flow's guaranteed data rate during said period and the amount of traffic from said flow transmitted through said switch during said period.