An evaluation of scheduling mechanisms for providing best-effort, real-time communication in wide-area networks

The authors distinguish between four types of service that may be provided to real-time traffic by packet-switched networks, ranging from "need-blind" and "need-based best-effort" to "guaranteed throughput" and "bounded delay jitter" services. They evaluate a number of scheduling policies that offer need-based, best-effort service. They introduce hop-laxity (HL) scheduling which is based on the time remaining until the packet must reach its destination as well as the number of hops separating it from the destination. HL scheduling is evaluated through simulation and has been implemented within a BSD-based kernel and tested on the DARTnet network. The results indicate that HL scheduling tends to equalize delays between calls with large and small number of hops as compared to a FIFO discipline, reducing the 99.9% percentile of delay and the fraction of late packets. They compare HL scheduling to the FIFO+ discipline suggested by Clark et al., (see SIGCOMM Symposium on Communications Architectures and Protocols, p.14-26, 1992, and Computer Communication Review, vol.22, no.4) and find that their delay properties are similar. Other disciplines, such as minimum laxity or transit priority, may actually do more harm than good.