Drexel University Home Pagewww.drexel.edu DREXEL UNIVERSITY LIBRARIES HOMEPAGE >>

iDEA: Drexel E-repository and Archives > Drexel Academic Community > College of Engineering > Department of Electrical and Computer Engineering > Faculty Research and Publications (ECE) > Degree-sequenced matching algorithms for input-queued switches

Please use this identifier to cite or link to this item: http://hdl.handle.net/1860/1652

Title: Degree-sequenced matching algorithms for input-queued switches
Authors: Hosaagrahara, Madhusudan
Sethu, Harish
Keywords: Input-queued switches;Scheduling and matching algorithms
Issue Date: 2007
Publisher: Springer Science + Business Media
Citation: Telecommunication Systems, 34(1-2): pp. 37-49.
Abstract: This paper presents a class of algorithms for scheduling packets in input-queued switches. As opposed to previously known algorithms that focus only on achieving high throughput, these algorithms seek to achieve low average delay without compromising the throughput achieved. Packet scheduling in input-queued switches based on the virtual-output-queued architecture is a bipartite graph matching problem wherein ports are represented by vertices and the traffic flows by the edges. The set of matched edges determine the packets that are to be transferred from the input ports to the output ports. Current matching algorithms implicitly prioritize high-degree vertices, i.e., ports with a large number of flows, causing longer delays at ports with a smaller number of flows. Motivated by this observation, we present three matching algorithms based on explicitly prioritizing low-degree vertices and the edges through them. Using both real gateway traffic traces as well as synthetically generated traffic, we present simulation results showing that this class of algorithms achieves a low average delay as compared to other scheduling algorithms of equivalent complexity while still achieving similar throughput. We also show that these algorithms determine the maximum size matching in almost all cases.
URI: http://dx.doi.org/10.1007/s11235-006-9024-y
Appears in Collections:Faculty Research and Publications (ECE)

Files in This Item:

File Description SizeFormat
2006175083.pdf266.5 kBAdobe PDFView/Open
View Statistics

Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! iDEA Software Copyright © 2002-2010  Duraspace - Feedback