LAS Scheduling for Packet Switched Networks

The Team

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 variability property.

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.
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:

  • 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 conditions
  • When there is no overload, long flows are not heavily penalized and yet short ones take great advantage of LAS
  • 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.

    Relevant papers

    [RUKB04]
    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.
    [RUKB03]
    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.
    [RBUK05]
    I. Rai, E. W. Biersack, and G. Urvoy-Keller. Size-based Scheduling to improve the Performance of Short TCP Flows. IEEE Network Magazine, 2005.
    [RUKB04]
    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 2004.

    Publications