Input-queued switches with logarithmic delay: necessary conditions and a reconfigurable scheduling algorithm
Pages 121 - 122
Abstract
Typically, a scheduling algorithm for an n x n packet switch with a crossbar as the data fabric divides time into slots, each of duration tp sufficient to transmit a packet. If a scheduling round requires tr > tp time, then the switch can transmit multiple packets, up to s = ⌊tr/tp⌋, between each mapped input-output pair under the current mapping. If s = 1, there exists a frame-based scheduling algorithm with Θ(log n) delay. For uniform random traffic, we establish that the delay is Ω(n) for any s > 1, hence, s = 1 is the only case where a Θ(log n) delay is achievable.
Given the importance of achieving a low s, it is imperative to develop extremely fast scheduling algorithms (that reduce tr) on a mesh-based structure (corresponding to the crossbar topology of the switch). We present results for a fast scheduling algorithm that runs on a mesh-of-trees topology that can be overlaid on the crossbar switching fabric.
References
[1]
H. J. Chao and B. Liu. High Performance Switches and Routers. Wiley-IEEE Press, USA, 2007.
[2]
C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan, D. Moll, R. Rockell, T. Seely, and S. C. Diot. Packet-level traffic measurements from the sprint ip backbone. Network, IEEE, 17(6):6--16, December 2003.
[3]
S. Iyer and N. McKeown. Maximum size matchings and input queued switches. In 40th Annual Allerton Conf. on Communication, Control, and Computing, 2002.
[4]
P. Kelsen. Optimal parallel algorithm for maximal matching. Information Processing Letters, 52(4):223--228, 1994.
[5]
E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan. Bounds on average delays and queue size averages and variances in input-queued cell-based switches. In IEEE INFOCOM, 2001.
[6]
X. Li and I. Elhanany. Stability of frame-based maximal weight matching algorithms with reconfiguration delays. In Workshop on High Performance Switching and Routing, May 2005.
[7]
N. McKeown. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 7(2):188--201, 1999.
[8]
S. Mneimneh, V. Sharma, and K. Y. Siu. Switching using parallel input-output queued switches with no speedup. IEEE/ACM Transactions on Networking, 10(5):653--665, 2002.
[9]
M. J. Neely, E. Modiano, and Y. S. Cheng. Logarithmic delay for n x n packet switches under the crossbar constraint. IEEE/ACM Transactions on Networking, 15(3):3--9, June 2007.
Index Terms
- Input-queued switches with logarithmic delay: necessary conditions and a reconfigurable scheduling algorithm
Recommendations
Frame-Based Packet-Mode Scheduling for Input-Queued Switches
Most packet scheduling algorithms for input-queued switches operate on fixed-sized packets known as cells. In reality, communication traffic in many systems such as Internet runs on variable-sized packets. Motivated by potential savings of segmentation ...
An efficient packet scheduling algorithm with deadline guarantees for input-queued switches
Input-queued (IQ) switches overcome the scalability problem suffered by output-queued switches. In order to provide differential quality of services (QoS), we need to efficiently schedule a set of incoming packets so that every packet can be transferred ...
A logarithmic scheduling algorithm for high speed input-queued switches
Throughput of input queued switches using FIFOs is limited due to the Head of Line blocking (HoL) problem. Using VOQs at inputs and a proper scheduling algorithm, near 100% throughput can be achieved. Scaling in terms of number of ports and line rates ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2008
191 pages
ISBN:9781605583464
DOI:10.1145/1477942
- General Chair:
- Mark Franklin,
- Program Chairs:
- D. K. Panda,
- Dimitri Stiliadis
Copyright © 2008 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 06 November 2008
Check for updates
Author Tags
Qualifiers
- Poster
Funding Sources
Conference
ANCS '08: Symposium on Architecture for Networking and Communications Systems
November 6 - 7, 2008
California, San Jose
Acceptance Rates
ANCS '08 Paper Acceptance Rate 17 of 67 submissions, 25%;
Overall Acceptance Rate 88 of 314 submissions, 28%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 134Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in