Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2007

Filename

wucse-2007-16.pdf

Technical Report Number

WUCSE-2007-16

Abstract

Elastic applications are primarily interested in minimal delay achievable for their messages under current network load. In this paper, we investigate how to transmit such messages over a bottleneck link efficiently and fairly. While SRPT (Shortest Remaining Processing Time) is an optimally efficient algorithm that minimizes average delay of messages, large messages might starve under SRPT in heavy load conditions. PS (Processor Sharing) and ViFi (Virtual Finish Time First) are fair but yield higher average delays than under SRPT. We explore the class of fair algorithms further and prove that no online algorithm in this class is optimally efficient. Then, we derive a fair algorithm SFS (Shortest Fair Sojourn) and report extensive experimental evidence that SFS is consistently more efficient than PS and ViFi during either temporal overload or steady-state operation, with the largest benefits when average load is around the bottleneck link capacity. Furthermore, average delay under the fair SFS remains close to the minimum attained under the unfair SRPT.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7765CJ3

Download

Share

COinS