DocumentCode :
1756771
Title :
A Nearly Optimal Packet Scheduling Algorithm for Input Queued Switches with Deadline Guarantees
Author :
Baoxian Zhang ; Xili Wan ; Junzhou Luo ; Xiaojun Shen
Author_Institution :
Res. Center of Ubiquitous Sensor Networks, Univ. of Chinese Acad. of Sci., Beijing, China
Volume :
64
Issue :
6
fYear :
2015
fDate :
June 1 2015
Firstpage :
1548
Lastpage :
1563
Abstract :
Deadline guaranteed packet scheduling for switches is a fundamental issue for providing guaranteed QoS in digital networks. It is a historically difficult NP-hard problem if three or more deadlines are involved. All existing algorithms have too low throughput to be used in practice. A key reason is they use packet deadlines as default priorities to decide which packets to drop whenever conflicts occur. Although such a priority structure can ease the scheduling by focusing on one deadline at a time, it hurts the throughput greatly. Since deadlines do not necessarily represent the actual importance of packets, we can greatly improve the throughput if deadline induced priority is not enforced. This paper first presents an algorithm that guarantees the maximum throughput for the case where only two different deadlines are allowed. Then, an algorithm called iterative scheduling with no priority (ISNOP) is proposed forthe general case where k > 2 different deadlines may occur. Not only does this algorithm have dramatically better average performance than all existing algorithms, but also guarantees approximation ratio of 2. ISNOP would provide a good practical solution for the historically difficult packet scheduling problem.
Keywords :
computational complexity; digital communication; iterative methods; packet switching; quality of service; queueing theory; telecommunication scheduling; ISNOP; NP-hard problem; QoS; approximation ratio; digital network; iterative scheduling with no priority; optimal packet scheduling algorithm; quality of service; switch queuing scheme; Global Positioning System; Optimal scheduling; Ports (Computers); Quality of service; Scheduling; Scheduling algorithms; Throughput; Input-queued switch; deadline guarantee; minimum cost maximum flow; packet scheduling; quality of service; real time scheduling;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.2014.2329695
Filename :
6853339
Link To Document :
بازگشت