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.sub.i, 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 .alpha..sub.1, .alpha..sub.2, . . . , .alpha..sub.N. The packet having the largest weighted delay W.sub.i/.alpha..sub.i 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 T.sub.i and an allowed deadline violation probability .delta..sub.i, e.g., a requirement specified by P(W.sub.i>T.sub.i).ltoreq..delta..sub.i, the weights .alpha..sub.i in the set of positive weights .alpha..sub.1, .alpha..sub.2, . . . , .alpha..sub.N may be given by .alpha..sub.i=-T.sub.i/log .delta..sub.i. 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.sub.i, i=1, 2, . . . N, and an allowed queue length violation probability .delta..sub.i. In such an embodiment, the QoS requirement is specified by P(Q.sub.i>H.sub.i).ltoreq..delta..sub.i, and the weights .alpha..sub.i in the set of positive weights .alpha..sub.1, .alpha..sub.2, . . . , .alpha..sub.N may be given by .alpha..sub.i=-H.sub.i/log .delta..sub.i, where H.sub.i represents an upper bound on the length of the queue.