An efficient scheduling policy for edge routers to speedup the Internet access

Recent Internet traffic measurements reveal that Internet traffic exhibits high coefficient of variability (CoV). That is, the Internet traffic consists of many small jobs and very few large jobs, and less than 1% of the largest jobs constitute more than half of the load. Consequently, we propose to use policies that take advantage of this attribute to favor small jobs over large jobs. If such a policy is implemented in an edge router, this would mean that short jobs such as HTTP sessions will see their latency reduced. The shortest remaining processing time first (SRPT) scheduling policy has been known to be an optimal policy in minimizing the mean response time. Recent work [2] has shown that for job size distributions with high coefficient of variability (CoV), SRPT favors small jobs without unfairly penalizing large jobs. An implementation of SRPT requires that the sizes of all jobs be known, which can not be assumed in most networking environments. In this paper, we analyze the Foreground- Background-Infinity (_ __ ) scheduling policy, which is a priority policy that is known to favor small jobs the most among the scheduling policies that do not require the knowledge of job sizes. However, when evaluated under the M/M/1 queueing model, _ __ has been shown to highly penalize many large jobs in favor of small jobs. In this paper, we analyze the M/G/1/_ _ queue the objective being to investigate the fairness of _ __ by comparing its slowdown to the slowdown offered by PS, to quantify the response time improvement that _ _ offers when used instead of FIFO, and to compare _ __ to an optimal policy SRPT, for service distributions _ with varying CoVs. Finally, we consider _ __ under overload where we analyze its stability and derive its expression for the conditional mean response time.

Document Bibtex

Permalink: http://www.eurecom.fr/publication/1131