Graduate School and Research Center In communication systems

Performance analysis of LAS-based scheduling disciplines in a packet switched network

Rai, Idris A;Urvoy-Keller, Guillaume;Vernon, Mary K;Biersack, Ernst W

SIGMETRICS 2004, ACM International Conference on Measurement and Modeling of Computer Systems, June 12-16, 2004, New York, USA / Also published in ACM SIGMETRICS Performance Evaluation Review Homepage Volume 32 Issue 1, June 2004

The Least Attained Service (LAS) scheduling policy, when used for scheduling packets over the bottleneck link of an Internet path, can greatly reduce the average flow time for short flows while not significantly increasing the average flow time for the long flows that share the same bottleneck. No modification of the packet headers is required to implement the simple LAS policy. However, previous work has also shown that a drawback of the LAS scheduler is that, when link utilization is greater than 70%, long flows experience large jitter in their packet transfer times as compared to the conventional First-Come-First-Serve (FCFS) link scheduling. This paper proposes and evaluates new differentiated LAS scheduling policies that reduce the jitter for long flows that are identified as "priority" flows.To evaluate the new policies, we develop analytic models to estimate average flow transfer time as a function of flow size, and average packet transmission time as a function of position in the flow, for the single-bottleneck "dumbbell topology" used in many ns simulation studies. Models are developed for FCFS scheduling, LAS scheduling, and each of the new differentiated LAS scheduling policies at the bottleneck link. Over a wide range of configu-rations, the analytic estimates agree very closely with the ns estimates. Thus, the analytic models can be used instead of simulation for comparing the policies with respect to mean flow transfer time (as a function of flow size) and mean packet transfer time. Furthermore, an initial discrepancy between the analytic and simulation estimates revealed errors in the parameter values that are often specified in the widely used ns Web workload generator. We develop an improved Web workload specification, which is used to estimate the packet jitter for long flows (more accurately than with previous simulation workloads).Results for the scheduling policies show that a particular policy, LAS-log, greatly improves the mean flow transfer time for priority long flows while providing performance similar to LAS for the ordinary flows. Simulations show that the LAS-log policy also greatly reduces the jitter in packet delivery times for the priority flows.

Document Doi Bibtex

Type:Conference
Language:English
City:New York
Country:UNITED STATES
Date:
Department:Networking and Security
Eurecom ref:1464
Copyright: © ACM, 2004. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SIGMETRICS 2004, ACM International Conference on Measurement and Modeling of Computer Systems, June 12-16, 2004, New York, USA / Also published in ACM SIGMETRICS Performance Evaluation Review Homepage Volume 32 Issue 1, June 2004 http://dx.doi.org/10.1145/1005686.1005702
Bibtex: @inproceedings{EURECOM+1464, doi = {http://dx.doi.org/10.1145/1005686.1005702}, year = {2004}, title = {{P}erformance analysis of {LAS}-based scheduling disciplines in a packet switched network}, author = {{R}ai, {I}dris {A} and {U}rvoy-{K}eller, {G}uillaume and {V}ernon, {M}ary {K} and {B}iersack, {E}rnst {W}}, booktitle = {{SIGMETRICS} 2004, {ACM} {I}nternational {C}onference on {M}easurement and {M}odeling of {C}omputer {S}ystems, {J}une 12-16, 2004, {N}ew {Y}ork, {USA} / {A}lso published in {ACM} {SIGMETRICS} {P}erformance {E}valuation {R}eview {H}omepage {V}olume 32 {I}ssue 1, {J}une 2004 }, address = {{N}ew {Y}ork, {UNITED} {STATES}}, month = {06}, url = {http://www.eurecom.fr/publication/1464} }
See also: