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.