Method and apparatus for scheduling traffic to meet quality of service requirements in a communication network

Abstract

Packets are scheduled for transmission over a communication link in a network, using a Largest Weighted Delay First (LWDF) scheduling policy. A delay measure W, i=1, 2, . . . N, is computed for each of N packets, each associated with a corresponding one of N data flows and located in a head position in a corresponding one of N data flow queues. The computed delay measures are then weighted using a set of positive weights α, α, . . . , α. The packet having the largest weighted delay W/αassociated therewith is then selected for transmission. In an embodiment configured to meet a quality of service (QoS) requirement specified in terms of a deadline Tand an allowed deadline violation probability δ, e.g., a requirement specified by P(W>T)≦δ, the weights αin the set of positive weights α, α, . . . , αmay be given by α=−T/log δ. The invention can also be used to meet other types of QoS requirements, including, e.g., requirements based on packet loss probabilities. For example, the QoS guarantee may be defined for a delay measure in the form of queue length Q, i=1, 2, . . . N, and an allowed queue length violation probability δ. In such an embodiment, the QoS requirement is specified by P(Q>H)≦δ, and the weights αin the set of positive weights α, α, . . . , αmay be given by α=−H/log δ, where Hrepresents an upper bound on the length of the queue.