Implementing shortest job first order of service in the internet

Implementing shortest job first order of service in the internet

The Internet needs protocols and mechanisms to provide guaranteed quality of service. The existing Internet is surprisingly close to providing good quality for a very wide range of services, probably because the TCP protocols aim to achieve, and come to close to achieving, fair queueing, or processor sharing, whenever several flows compete for limited resources. The DiffServ architecture aims to do better than this by providing different performance standards for different classes of service. The obvious way to apply DiffServ is to allocate classes in accordance with the urgency or priority of the requests. However, another approach is to use DiffServ to
allocate service classes according to the 'size' of the requests - smaller requests receiving generally better service and longer requests worse. A Pareto distribution with small shape parameter has been used in a great deal of research, and in this paper, to model the widely accepted heavy-tailed nature of flow lengths. We assume that the starting times of these flows forms a Poisson process. It was shown in (McNickle and Addie(2005)) by means of a queueing model with this traffic that serving flows in order of job size (in bytes, shorter flows served first) leads to significantly lower mean and standard deviation for response times, for flows of all lengths. This paper also provided evidence that it is unlikely that DiffServ can achieve a significantly better result. This poses the
challenge of how to arrange for flows to be served in the shortest-job-first (SJF) order, or as close as possible to it. We define a simple approach to achieving this which can be implemented locally - in just two routers in the simplest case. Simulations have been used to demonstrate that some of the benefits of the SJF discipline can, indeed, be obtained.
In this paper we propose a protocol for achieving an approximation to the shortest job first order of service at times of congestion. The proposed mechanism is scalable and local in the sense that the actions taken are confined to a small number of routers near the site of the congestion. This concept of a local protocol modification can be viewed as a generalization of Active Queue Management. Whereas AQM's are generally formed by modifying the queueing discipline and ensuing behavior at the congested node, in our proposal, which we shall term local QM (LQM), some nearby nodes also assist in managing the congestion, with the objective of approaching as close as possible to SJF.
SJF is sometimes not achievable to acceptable accuracy for reasons which have nothing to do with the treatment of packets by the nodes near where congestion is occurring. In such situations we cannot expect our mechanism to do the impossible. For example, if the sending host is unable to deliver a flow at the maximum rate of the bottleneck link, it will not be possible to serve this flow ahead of all others, and so SJF will not be achievable.
Two similar LQM strategies have been tested and compared in the context of a local premises network connected to the Internet via a congested link. In one of these strategies, packets are marked at the edge router are dropped or remarked at the gateway to the premises depending on the traffic conditions there. In the other strategy some packets are remarked and others have their ECN bits left in
place. Simulation results have been able to demonstrate that the strategy is able to produce better response times than AQM's of comparable complexity located at the edge router.

Permission granted to deposit.