Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches
Date
2008
Authors
Shen, Xiaojun
Lou, Jianyu
Liang, Weifa
Luo, Junzhou
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
Many applications need to solve the deadline guaranteed packet scheduling problem. However, it is a very difficult problem if three or more deadlines are present in a set of packets to be scheduled. The traditional approach to dealing with this problem is to use EDF (Earliest Deadline First) or similar methods. Recently, a non-EDF based algorithm was proposed that constantly produces a higher throughput than EDF-based algorithms by repeatedly finding an optimal scheduling for two classes. However, this new method requires the two classes be non-overloaded, which greatly restricts its applications. Since the overloaded situation is not avoidable from one iteration to the next in dealing with multiple classes, it is compelling to answer the open question: Can we find an optimal schedule for two overloaded classes efficiently? This paper first proves that this problem is NP-complete. Then, this paper proposes an optimal preprocessing algorithm that guarantees to drop a minimum number of packets from the two classes such that the remaining set is non-overloaded. This result directly improves on the new method.
Description
Keywords
Keywords: Computer networks; Nuclear propulsion; Packet networks; Response time (computer systems); Routers; Scheduling; Switches; Switching networks; Wireless networks; Applications.; Deadline guarantee; Earliest deadline firsts; Input-queued switch; Multiple clas Deadline guarantee; Input-queued switch; NP-hard; Packet scheduling; Quality of service
Citation
Collections
Source
Theoretical Computer Science
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description