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
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;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2014.2329695