Scheduling Unit-Length Packets with Soft Deadlines

Author

Zhang, Zhi ; Li, Fei

Author_Institution

Dept. of Comput. Sci., George Mason Univ., Fairfax, VA, USA

fYear

2010

fDate

15-19 March 2010

Firstpage

1

Lastpage

5

Abstract

We study scheduling unit-length packets with soft deadlines. In our setting, packets arrive over time and a packet may have different values contributed to the objective when it is delivered at different time. In one time step, at most one packet is allowed to be sent. Our goal is to maximize the total value achieved by delivering packets. Based on various application requirements, we propose two models: a general model and a B-bounded model. In this paper, we design optimal offline algorithms and two simple online algorithms, MATCH and GREED, and give their competitive analysis.

Keywords

greedy algorithms; quality of service; scheduling; telecommunication services; B-bounded model; GREED online algorithms; MATCH online algorithms; QoS; general model; optimal offline algorithms; qualify-of-service; unit-length packet scheduling; Algorithm design and analysis; Communications Society; Computer science; Delay; Network servers; Next generation networking; Packet switching; Processor scheduling; Scheduling algorithm; USA Councils;

fLanguage

English

Publisher

ieee

Conference_Titel

INFOCOM IEEE Conference on Computer Communications Workshops , 2010

Conference_Location

San Diego, CA

Print_ISBN

978-1-4244-6739-6

Electronic_ISBN

978-1-4244-6739-6

Type

conf

DOI

10.1109/INFCOMW.2010.5466643

Filename

5466643