| 摘要 |
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. |
