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 to schedule N traffic flows through a multiplexer server system, said multiplexer server system comprising a queue for each of said N traffic flows, a multiplexer server, and an outgoing link, wherein each of said N traffic flows has an associated weight equaling the fraction of the outgoing link capacity requested by said flow, said method comprising
 (a) assigning each of said N traffic flows an initial normalized lag value,   (b) processing each of said N traffic flows and assigning each of said N traffic flows a normalized lag increment value, equaling an ideal inter-departure time for average sizes packets associated with that traffic flow divided by the time-slot duration,   (c) in each increment of the time-slot clock, processing said N traffic flows and adding the normalized lag increment value to the normalized lag value associated with each of said N traffic flows,   (d) in each increment of the time-slot clock during which the outgoing link is idle, processing the N traffic flows and selecting one packet associated with one of said N traffic flows for transmission over said outgoing link, said one of said N traffic flows having the largest normalized lag value which exceeds a given threshold value,   (e) removing one packet from the queue associated with said one of said N traffic flows, transmitting the packet over the outgoing transmission line for K time-slots, and decrementing the normalized lag value associated with said one of said N traffic flows by K times the normalized lag increment value.   
     
     
         2 . The method of  claim 1 , where all packets have a fixed maximum size. 
     
     
         3 . The method of  claim 1 , where all packets have a fixed maximum size, and each packet can be transmitted over the outgoing link in a fixed number of time-slots. 
     
     
         4 . The method of  claim 1 , where all packets have a fixed maximum size, and each packet can be transmitted over the outgoing link in one time-slot. 
     
     
         5 . A method to schedule traffic flows through an input port associated with a switching matrix, said input port comprising multiple Virtual Output Queues (VOQs), one server, and one outgoing link associated with a switching matrix, wherein each of said VOQs stores packets associated with a subset of said N traffic flows, and wherein packets within one VOQ request a common output port of the switching matrix, said method comprising steps of
 (a) assigning each of said N VOQs a weight equaling the fraction of the capacity of said outgoing link requested by said VOQ,   (b) wherein said server selects said VOQs for transmission onto the outgoing link such that traffic associated with each of said N VOQ is transmitted over the outgoing link with a bounded normalized service lead/lag.   
     
     
         6 . A method to schedule multiple Guaranteed-Rate (GR) traffic flows through an input port associated with a switching matrix, said input port comprising N Virtual Output Queues (VOQs), one VOQ-server, and one outgoing link associated with a switching matrix, said outgoing link called a port link, each of said VOQs comprising multiple flow-VOQs, one gated flow-server and one outgoing link connected indirectly or directly to the VOQ-server, each of said outgoing links called a VOQ-link, each of said flow-VOQs storing packets associated with one of said GR traffic flows,
 (a) wherein each VOQ is assigned a weight equaling the fraction of the capacity of the outgoing port link requested by the VOQ,   (b) wherein the VOQ-server selects VOQs for service in proportion to the weight of the VOQ,   (c) wherein each gated flow-server associated with each VOQ receives control signals called enable signals from the VOQ-server, and selects one GR traffic flow for transmission onto the outgoing VOQ-link in response to an enable signal, such that each of said GR traffic flows is transmitted over the outgoing port link with a bounded normalized service lead/lag.   
     
     
         7 . The method of  claim 6  where the switching matrix is unbuffered. 
     
     
         8 . The method of  claim 6  where the switching matrix is buffered.