|
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
http://hdl.handle.net/1860/1652 |
| Appears in Collections: | Faculty Research and Publications (ECE)
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
