LAS Scheduling for Packet Switched Networks
Eurécom staff: Ernst Biersack, Guillaume Urvoy-Keller,
Former PhD Student: Idris Rai
External Collaboration: Mary Vernon, Univ. of Madison at Wisconsin
LAS Scheduling for Packet Switched Networks: Theory
LAS scheduling is a size-based scheduling discipline that favors short
jobs. We study the least attained service (LAS) scheduling policy in
packet switched networks. LAS has
been known for decades as job scheduling policy but has never been
considered for packet switched networks. When analyzed under the M/M/1
queue LAS penalizes the largest jobs a lot. However, recent Internet
traffic measurements have revealed that the Internet traffic exhibits
a high variability property; many flows are short Web transfers and
about 1% of the largest flows carry more than 50% of all bytes.
LAS Scheduling Applied in Packet Switched Networks: Theory
We evaluate LAS scheduling analytically using job size distributions
with varying degrees of variability. We compare the performance of
LAS to a wide range of other scheduling policies to study its
performance improvements for job sizes. The numerical results show
that the performance of LAS highly depends on the variability of a job
size distribution. In particular, we see that LAS significantly
reduces the mean response time of short jobs for any job size
distribution, and it negligibly penalizes a tiny fraction of the
largest jobs for job sizes with a high variability property. Moreover,
we proved that the penalty experienced by the largest jobs is
moderate. The comparison of LAS to SRPT showed that LAS performs very
close to SRPT and its comparison with FIFO shows that LAS yields a
lower mean response time for job size distributions with high
LAS Scheduling and its Impact on TCP Flows: Implementation
The Internet today carries different types of traffic that have
different service requirements. A large fraction of the traffic is
either Web traffic requiring low response time or peer-to-peer traffic
requiring high throughput. Meeting both performance requirements in a
network where routers use droptail or RED for buffer management and
FIFO as service policy is an elusive goal. It is therefore worthwhile
to investigate alternative scheduling and buffer management policies
for bottleneck links.
LAS minimizes number of active flows, thus helping connection
tracking to scale
Under LAS short interactive jobs don't see any congestion at all and
users can browse the web as if
the network utilization was close to zero, even under heavy overload
When there is no overload, long flows are not heavily penalized and yet short ones take great advantage of
Interactivity is boosted in presence of congestion, whereas in case of no queuing LAS behaves exactly
the same as FIFO
We have an implementation of different variants of LAS under Linux.
We propose to use the least attained service
(LAS) policy to improve the response time of Web traffic. Under LAS,
the next packet to be served is the one belonging to the flow that has
received the least amount of service. When the buffer is full, the
packet dropped belongs to the flow that has received the most
service. We show that under LAS, as compared to FIFO with droptail,
the transmission time and loss rate for short TCP flows are
significantly reduced, with only a negligible increase in transmission
time for the largest flows. The improvement seen by short TCP flows
under LAS is mainly due to the way LAS interacts with the TCP protocol
in the slow start phase, which results in shorter round-trip times and
zero loss rates for short flows.
Some nice properties of LAS are:
I. A. Rai, G. Urvoy-Keller, M. Vernon, and E. W. Biersack.
Performance models for LAS-based scheduling
disciplines in a packet switched network.
In ACM SIGMETRICS-Performance, pages--, June 2004.
I. A. Rai, G. Urvoy-Keller, and E. W. Biersack.
Analysis of LAS Scheduling for Job Size Distributions
with High Variance.
In Proc. ACM SIGMETRICS, pages 218--228, June 2003.
I. Rai, E. W. Biersack, and G. Urvoy-Keller.
Size-based Scheduling to improve the Performance of
Short TCP Flows.
IEEE Network Magazine, 2005.
I. A. Rai, Urvoy-Keller, and E. W. Biersack.
LAS Scheduling Approach to Avoid Bandwidth Hogging in
Heterogeneous TCP Networks.
In 7th IEEE International Conference on High Speed
Networks and Multimedia Communications HSNMC'04, 2004, pages~--, July