article

Buffered cross-bar switches, revisited: design steps, proofs and simulations towards optimal rate and minimum buffer memory

Author:

George F. GeorgakopoulosAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 16, Issue 6

Pages 1340 - 1351

https://doi.org/10.1109/TNET.2007.911441

Published: 01 December 2008 Publication History

Abstract

Regarding the packet-switching problem, we prove that the weighed max-min fair service rates comprise the unique Nash equilibrium point of a strategic game, specifically a throughput auction based on a "least-demanding first-served" principle. We prove that a buffered crossbar switch can converge to this equilibrium with no pre-computation or internal acceleration, with either randomized or deterministic schedulers, (the latter with a minimum buffering of a single-packet per crosspoint). Finally, we present various simulation results that corroborate and extend our analysis.

References

[1]

D. P. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1992.

Digital Library

[2]

N. Chrysos, "Weighted max-min fairness in a buffered crossbar switch with distributed WFQ schedulers: A first report," M.Sc. Thesis, Inst. Comp. Sci., FORTH, Univ. Crete, Crete, Greece, 2002, FORTH-ICS/TR-309.

[3]

N. Chrysos and M. Katevenis, "Weighted fairness in buffered crossbar scheduling," in Proc. IEEE Workshop High Perf. Switch. Routing, Torino, Italy, Jun. 2003, pp. 17-22.

[4]

T. Javidi, R. Magill, and T. Hrabik, "A high-throughput scheduling algorithm for a buffered crossbar switch fabric," in Proc. IEEE Int. Conf. Commun., 2001, vol. 5, pp. 1586-1591.

[5]

C. Lund, S. Phillips, and N. Reingold, "Fair prioritized scheduling in an input-buffered switch," in Proc. IFIP-IEEE Conf. Broadband Commun., 1996, pp. 358-369.

[6]

R. O. LaMaire and D. N. Serpanos, "Two-dimensional Round-Robin schedulers for Packet Switches with multiple input queues," IEEE/ACM Trans. Networking, vol. 2, no. 5, pp. 471-482, Apr. 1994.

Digital Library

[7]

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

Digital Library

[8]

A. Charny, P. Krishna, N. Patel, and R. Simcoe, "Algorithms for providing bandwidth and delay guarantees in input-buffered crossbars with speedup," in Proc. IEEE 6th Int. Workshop Quality Service, Napa, CA, 1998, pp. 235-244.

[9]

H. Ahmadi and W. Denzel, "A survey of modern high-performance switching techniques," IEEE J. Sel. Areas Commun., vol. 7, no. 7, pp. 1091-1103, Jul. 1989.

Digital Library

[10]

E. L. Hahne, "Round-Robin scheduling for max-min fairness in data networks," IEEE J. Sel. Areas Commun., vol. 9, no. 7, pp. 1024-1039, 1991.

Digital Library

[11]

L. Zhang, "Virtual clock: A new traffic control algorithm for packet switching networks," ACM Trans. Computer Syst., vol. 9, no. 2, pp. 101-124, 1990.

Digital Library

[12]

C. H. Papadimitriou, "Algorithms, games and the internet," in Proc. 33rd ACM Symp. Theory of Computing, Hersonissos, Crete, Greece, 2001, pp. 749-753.

Digital Library

[13]

G. F. Georgakopoulos, "Nash-equilibria as a fundamental issue concerning network-switches design," presented at the IEEE Int. Conf. Commun., Paris, France, 2004.

[14]

K. G. I. Harteros, "Fast Parallel Comparison Circuits for Scheduling" M.Sc. Thesis, Univ. Crete, Crete, Greece, 2002 {Online}. Available: http://archvlsi.ics.forth.gr/muqpro/cmpTree.html, TR FORTH-ICS/TR-304

[15]

D. C. Stephens and H. Zhang, "Implementing distributed packet fair queueing in a scalable switch architecture," in Proc. INFOCOM'98, San Francisco, CA, 1998, pp. 282-290.

[16]

H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. IEEE, vol. 83, no. 10, pp. 1374-1396, Oct. 1995.

[17]

A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," J. Internetw.: Res. Exp., vol. 1, no. 1, pp. 3-26, 1990.

[18]

R. Myerson, Game Theory: Analysis of Conflict. Cambridge, MA: Harvard Univ. Press, 1997.

[19]

P. Marbach, "Priority service and max-min fairness," presented at the INFOCOM'02, New York, 2002.

[20]

H. Gintis, Game Theory Evolving. Princeton, NJ: Princeton Univ. Press, 2000.

Cited By

Chrysos NKatevenis M(2011)Distributed WFQ scheduling converging to weighted max-min fairnessComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.01155:3(792-806)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1016/j.comnet.2010.10.011

Index Terms

Buffered cross-bar switches, revisited: design steps, proofs and simulations towards optimal rate and minimum buffer memory

Recommendations

Localized asynchronous packet scheduling for buffered crossbar switches
ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

Buffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input ...
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 ...
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

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 \times N$$N N CIOQ ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 16, Issue 6

December 2008

248 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2008

Revised: 02 June 2006

Received: 14 December 2005

Published in TON Volume 16, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
165
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chrysos NKatevenis M(2011)Distributed WFQ scheduling converging to weighted max-min fairnessComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.01155:3(792-806)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1016/j.comnet.2010.10.011

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents