Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches

dc.contributor.authorShen, Xiaojun
dc.contributor.authorLou, Jianyu
dc.contributor.authorLiang, Weifa
dc.contributor.authorLuo, Junzhou
dc.date.accessioned2015-12-10T22:13:39Z
dc.date.issued2008
dc.date.updated2016-02-24T10:17:15Z
dc.description.abstractMany 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.
dc.identifier.issn0304-3975
dc.identifier.urihttp://hdl.handle.net/1885/49837
dc.publisherElsevier
dc.sourceTheoretical Computer Science
dc.subjectKeywords: 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
dc.titleDeadline guaranteed packet scheduling for overloaded traffic in input-queued switches
dc.typeJournal article
local.bibliographicCitation.lastpage485
local.bibliographicCitation.startpage477
local.contributor.affiliationShen, Xiaojun, University of Missouri
local.contributor.affiliationLou, Jianyu, University of Missouri
local.contributor.affiliationLiang, Weifa, College of Engineering and Computer Science, ANU
local.contributor.affiliationLuo, Junzhou, Southeast University
local.contributor.authoremailu9404892@anu.edu.au
local.contributor.authoruidLiang, Weifa, u9404892
local.description.embargo2037-12-31
local.description.notesImported from ARIES
local.identifier.absfor080201 - Analysis of Algorithms and Complexity
local.identifier.ariespublicationU3594520xPUB193
local.identifier.citationvolume409
local.identifier.doi10.1016/j.tcs.2008.09.013
local.identifier.scopusID2-s2.0-55949116062
local.identifier.thomsonID000261785400015
local.identifier.uidSubmittedByU3594520
local.type.statusPublished Version

Downloads

Original bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
01_Shen_Deadline_guaranteed_packet_2008.pdf
Size:
812.54 KB
Format:
Adobe Portable Document Format
Back to topicon-arrow-up-solid
 
APRU
IARU
 
edX
Group of Eight Member

Acknowledgement of Country

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.


Contact ANUCopyrightDisclaimerPrivacyFreedom of Information

+61 2 6125 5111 The Australian National University, Canberra

TEQSA Provider ID: PRV12002 (Australian University) CRICOS Provider Code: 00120C ABN: 52 234 063 906