Article

Pipelined two step iterative matching algorithms for CIOQ crossbar switches

Authors:

Deng Pan,

Yuanyuan YangAuthors Info & Claims

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

Pages 41 - 50

https://doi.org/10.1145/1095890.1095897

Published: 26 October 2005 Publication History

Get Access

Abstract

Traditional iterative matching algorithms for VOQ switches need three steps, i.e., request, grant and accept. By incorporating arbitration into the request step, two step iterative matching can be achieved. This enables simpler implementation and shorter scheduling time, while maintaining almost identical performance. As an example of the two step iterative matching algorithms, in this paper we present Two Step Parallel Iterative Matching (PIM2), and theoretically prove that its average convergence iterations are less than ln N + e/(e-1) for an N x N switch. Furthermore, two step iterative matching algorithms can be efficiently pipelined on CIOQ switches so that two matchings can be obtained in each time slot. We propose a scheme called Second of Line (SOL) matching to provide two independent virtual switches, with which the pipelining can be achieved without additional scheduling time and arbitration hardware. More importantly, the pipelined algorithms are theoretically guaranteed to achieve 100% throughput for any admissible traffic. Extensive simulations are conducted to show that our analytical result on the average convergence iterations ln N + e/(e-1) is more accurate than the classical result log₂ N + 4/3, and to test the performance of different pipelined algorithms on CIOQ switches.

References

[1]

N. McKeown, "The iSLIP scheduling algorithm for input-queued switches," IEEE/ACM Trans. Networking, vol. 7, no. 2, pp. 188--201, 1999.

Digital Library

Google Scholar

[2]

N. McKeown, A. Mekkittikul, V. Anantharam and J. Walrand, "Achieving 100% throughput in an input queued switch," IEEE Trans. Commun., vol. 47, no. 8, pp. 1260--1267, 1999.

Crossref

Google Scholar

[3]

T. Anderson, S. Owicki. J. Saxe and C. Thacker, "High-speed switch scheduling for local-area networks," ACM Trans. Comput. Syst., vol. 11, no. 4, pp. 319--352, Nov. 1993.

Digital Library

Google Scholar

[4]

M. J. Karol, M. J. Hluchyj and S. P. Morgan, "Input versus output queueing on a space-division packet switch," IEEE Trans. Commun., vol. 35, pp. 1347--1356, 1987.

Crossref

Google Scholar

[5]

Nick McKeown, "A fast switched backplane for a gigabit switched router," Business Communications Review, vol. 27, no. 12, 1997.

Google Scholar

[6]

J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," IEEE INFOCOM '00, vol. 2, pp. 556--564, Tel Aviv, Israel, Mar. 2000.

Google Scholar

[7]

N. McKeown, M. Izzard, A. Mekkittikul, B. Ellesick and M. Horowitz, "The tiny tera: a packet switch core," it IEEE Micro, vol. 17, no. 1, pp. 26--33, Feb. 1997.

Digital Library

Google Scholar

[8]

C. Partridge et al., "A 50-Gb/s IP router," it IEEE/ACM Trans. Networking, vol. 6, no. 3, pp. 237--248, 1998.

Digital Library

Google Scholar

[9]

N. McKeown, "Scheduling algorithms for input queued cell switches," PhD Thesis, University of California at Berkeley, May 1995.

Digital Library

Google Scholar

[10]

J. Hopcroft, R. Karp, "An N5/2 algorithm for maximum matching in bipartite graphs," SIAM Journal of Computing, vol. 2, no. 4, pp. 225--231, Dec. 1973.

Crossref

Google Scholar

[11]

R. Tarjan, "Data structures and network algorithms," CBMS-NSF Regional Conference Series in Applied Mathematics, Dec. 1983.

Digital Library

Google Scholar

[12]

R. Panigrahy, A. Prakash, A. Nemat, and A. Aziz, "Weighted Random Matching: a simple scheduling algorithm for achieving 100% throughput," Proc. of the IEEE Workshop on High Performance Switching and Routing, pp. 111--115, Phoenix, AZ, 2004.

Google Scholar

[13]

D. Pan and Y. Yang, "FIFO based multicast scheduling algorithm for VOQ packet switches," to appear in it IEEE Trans. Computers, vol. 54, no. 10, October 2005.

Digital Library

Google Scholar

[14]

Y. Li, S. S. Panwar and H.J. Chao, "Exhaustive service matching algorithms for input queued switches," Proc. of IEEE Workshop on High Performance Switching and Routing, pp. 253--258, 2004.

Google Scholar

Cited By

View all

Pan DYang Y(2019)Bandwidth guaranteed multicast scheduling for virtual output queued packet switchesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2009.08.01069:12(939-949)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2009.08.010
Qian PQiao LChen QHuang X(2018)A Queue Manager Support Independent Management of Multicast Queues for CIOQ Switches2018 IEEE 2nd International Conference on Circuits, System and Simulation (ICCSS)10.1109/CIRSYSSIM.2018.8525981(80-84)Online publication date: Jul-2018
https://doi.org/10.1109/CIRSYSSIM.2018.8525981
Kachris CNikiforos GPapaefstathiou VKavadias SKatevenis M(2018)NP-SARCJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2012.11.00159:1(39-47)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.sysarc.2012.11.001
Show More Cited By

Index Terms

Pipelined two step iterative matching algorithms for CIOQ crossbar switches
1. Networks
  1. Network types
    1. Packet-switching networks

Recommendations

Set-valued mixed quasi-variational inequalities and implicit resolvent equations

In this paper, we introduce and study a new class of variational inequalities, which is called the set-valued mixed quasi-variational inequality. The resolvent operator technique is used to establish the equivalence among generalized set-valued mixed ...
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

We consider the problem of online packet scheduling in Combined Input and Output Queued (CIOQ) and buffered crossbar switches. In the widely used CIOQ switches, packet buffers (queues) are placed at both input and output ports. An N x N CIOQ switch has ...
Hardware Efficient Two Step Iterative Matching Algorithms for VOQ Switches
ICPADS '06: Proceedings of the 12th International Conference on Parallel and Distributed Systems - Volume 1

Virtual output queued (VOQ) crossbar switches have been demonstrating advantages as high speed interconnects. They eliminate the Head of Line (HOL) blocking, which limits the maximum throughput of single input queued switches, and do not require ...

Comments

Information & Contributors

Information

Published In

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

October 2005

230 pages

ISBN:1595930825

DOI:10.1145/1095890

General Chair:
Alan Berenbaum
SMSC
,
Program Chairs:
Kai Li
Princeton University, Princeton, NJ
,
Jonathan Turner
Washington University in St. Louis

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS05

Sponsor:

ANCS05: Symposium on Architecture for Networking and Communications Systems 2005

October 26 - 28, 2005

NJ, Princeton, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
280
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pan DYang Y(2019)Bandwidth guaranteed multicast scheduling for virtual output queued packet switchesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2009.08.01069:12(939-949)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2009.08.010
Qian PQiao LChen QHuang X(2018)A Queue Manager Support Independent Management of Multicast Queues for CIOQ Switches2018 IEEE 2nd International Conference on Circuits, System and Simulation (ICCSS)10.1109/CIRSYSSIM.2018.8525981(80-84)Online publication date: Jul-2018
https://doi.org/10.1109/CIRSYSSIM.2018.8525981
Kachris CNikiforos GPapaefstathiou VKavadias SKatevenis M(2018)NP-SARCJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2012.11.00159:1(39-47)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.sysarc.2012.11.001
Yang LChen QQiao LLv PChen Q(2017)A Deficit-Round-Robin-Based Variable-Length Packets Scheduling Scheme for Satellite Onboard SwitchesCommunications, Signal Processing, and Systems10.1007/978-981-10-3229-5_5(39-47)Online publication date: 27-Oct-2017
https://doi.org/10.1007/978-981-10-3229-5_5
Luo HHui JFayoumi A(2013)A low power and delay multi-protocol switch with IO and network virtualization2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2013.6602287(35-42)Online publication date: Jul-2013
https://doi.org/10.1109/HPSR.2013.6602287
Wang QGopalakrishnan S(2010)Adapting a Main-Stream Internet Switch Architecture for Multihop Real-Time Industrial NetworksIEEE Transactions on Industrial Informatics10.1109/TII.2010.20515576:3(393-404)Online publication date: Aug-2010
https://doi.org/10.1109/TII.2010.2051557
Kachris CNikiforos GPapaefstathiou VYang XKavadias SKatevenis M(2010)Low-latency explicit communication and synchronization in scalable multi-core clusters2010 IEEE International Conference On Cluster Computing Workshops and Posters (CLUSTER WORKSHOPS)10.1109/CLUSTERWKSP.2010.5613092(1-4)Online publication date: Sep-2010
https://doi.org/10.1109/CLUSTERWKSP.2010.5613092
Karimi MSun ZPan DChen Z(2009)Packet-mode asynchronous scheduling algorithm for partially buffered crossbar switchesProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812234(5144-5149)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811982.1812234
Pan DYang Y(2009)Localized Independent Packet Scheduling for Buffered Crossbar SwitchesIEEE Transactions on Computers10.1109/TC.2008.14058:2(260-274)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TC.2008.140
Karimi MSun ZPan DChen Z(2009)Packet-Mode Asynchronous Scheduling Algorithm for Partially Buffered Crossbar SwitchesGLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference10.1109/GLOCOM.2009.5425406(1-6)Online publication date: Nov-2009
https://doi.org/10.1109/GLOCOM.2009.5425406
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Set-valued mixed quasi-variational inequalities and implicit resolvent equations

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Hardware Efficient Two Step Iterative Matching Algorithms for VOQ Switches

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations