More Web Proxy on the site http://driver.im/

article

On tracking the behavior of an output-queued switch using an input-queued switch

Authors:

Ted H. Szymanski,

Douglas G. DownAuthors Info & Claims

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

Pages 1978 - 1988

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

Published: 01 December 2009 Publication History

Abstract

We address the problem of fair scheduling of packets in Internet routers with input-queued (IQ) switches and unity speedup. Scheduling in IQ switches is formulated as tracking the behavior of an output-queued (OQ) switch that provides optimal performance. We present the notion of "lag" as a performance metric that measures the difference between a packet's departure time in an IQ switch over that provided by an OQ switch. We prove that per-packet mean lag is bounded for a maximum weight-matching scheduling policy that uses lag values for its weights and derive a bound on the mean lag value using a Lyapunov function technique. Furthermore, we propose a simple heuristic tracking scheduling policy and evaluate its performance by simulation.

References

[1]

A. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: The single-node case," IEEE/ACM Trans. Netw., vol. 1, no. 3, pp. 344-357, Jun. 1993.

Digital Library

[2]

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

[3]

S. T. Chuang, A. Goel, N. McKeown, and B. Prabhakar, "Matching output queueing with a combined input/output-queued switch," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1030-1039, Jun. 1999.

Digital Library

[4]

P. Krishna, N. Patel, A. Charny, and R. Simcoe, "On the speedup required for work-conserving crossbar switches," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1057-1066, Jun. 1999.

Digital Library

[5]

B. Magill, C. Rohrs, and R. Stevenson, "Output-queued switch emulation by fabrics with limited memory," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 606-5, May 2003.

Digital Library

[6]

P. Giaccone, E. Leonardi, B. Prabhakar, and D. Shah, "Delay bounds for combined input-output switches with lowspeedup," Perf. Eval., vol. 55, no. 1-2, pp. 113-128, Jan. 2004.

Digital Library

[7]

C. Minkenberg, "Work-conservingness of CIOQ packet switches with limited output buffers," IEEE Commun. Lett., vol. 6, pp. 452-454, Oct. 2002.

[8]

Cisco 12000 Series-Internet Routers. 2004 {Online}. Available: http:// www.cisco.com

[9]

C. Partridge, P. P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohalmi, T. Ma, J. Mcallen, T. Mendez, W. C. Milliken, R. Pettyjohn, J. Rokosz, J. Seeger, M. Sollins, S. Storch, B. Tober, G. D. Troxel, D. Waitzman, and S. Winterble, "A 50-Gb/s IP router," IEEE/ACM Trans. Netw., vol. 6, no. 3, pp. 237-248, Jun. 1998.

Digital Library

[10]

Lucent Technologies, Inc., Holmdel, NJ, 2004 {Online}. Available: http://www.lucent.com

[11]

Avici Systems, Inc., Billercia, MA, 2004 {Online}. Available: http:// www.avici.com

[12]

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

Digital Library

[13]

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, Aug. 1999.

[14]

V. Tabatabaee, L. Georgiadis, and L. Tassiulas, "QoS provisioning and tracking fluid policies in input queueing switches," IEEE/ACM Trans. Netw., vol. 9, no. 5, pp. 605-7, Oct. 2001.

Digital Library

[15]

M. Rosenblum, M. X. Goemans, and V. Tarokh, "Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches," in Proc. IEEE INFOCOM, Mar. 2004, pp. 1126-1134.

[16]

T. H. Szymanski, "Design principles for practical self-routing nonblocking connection networks with n log(n) bit-complexity," IEEE Trans. Comput., vol. 46, no. 10, pp. 1057-1069, Oct. 1997.

Digital Library

[17]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1993.

Digital Library

[18]

I. Keslassy and N. McKeown, "Analysis of scheduling algorithms that provide 100% throughput in input-queued switches," presented at the 39th Annu. Allerton Conf. Commun., Control, Comput., Oct. 2001.

[19]

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

[20]

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 Proc. IEEE INFOCOM, Alaska, Apr. 2001, pp. 1095-1103.

[21]

E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan, "Bounds on delays and queue lengths in input-queued cell switches," JACM, vol. 50, pp. 520-550, Jul. 2003.

Digital Library

[22]

A. Mekkittikul and N. McKeown, "A practical scheduling algorithm to achieve 100% throughput in input-queued switches," in Prco. IEEE INFOCOM, 1998, pp. 792-799.

[23]

A. Mekkittikul, "Scheduling non-uniform traffic in high speed packet switches and routers," Ph.D. dissertation, Stanford University, Stanford, CA, Nov. 1998.

Digital Library

[24]

M. Andrews and L. Zhang, "Achieving stability in networks of inputqueued switches," IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 848-857, Oct. 2003.

Digital Library

[25]

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

Digital Library

[26]

P. R. Kumar and S. P. Meyn, "Stability of queueing networks and scheduling policies," IEEE Trans. Autom. Control, vol. 40, no. 2, pp. 251-260, Feb. 1995.

Cited By

Cai YWang XGong WTowsley D(2014)A Study on the Performance of a Three-Stage Load-Balancing SwitchIEEE/ACM Transactions on Networking10.1109/TNET.2013.224490622:1(52-65)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2244906
Szymanski TZomaya ACesana M(2008)Throughput and QoS optimization in nonuniform multichannel wireless mesh networksProceedings of the 4th ACM symposium on QoS and security for wireless and mobile networks10.1145/1454586.1454589(9-19)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1145/1454586.1454589

Recommendations

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 ...
The impact of bursty traffic on FPCF packet switch performance

This paper analyses and compares the performance of forward planning conflict-free (FPCF), virtual output queuing-partitioned (VOQ-P) and virtual output queuing-shared (VOQ-S) packet switches. The influence of packet burst size, offered switch load and ...
FPCF Input-Queued Packet Switch for Variable-Size Packets
ICN '01: Proceedings of the First International Conference on Networking-Part 2

The existing forward planning conflict-free (FPCF) packet switches are designed for fixed-size packets and synchronous operation mode. In this paper an asynchronous FPCF packet switch for variable-size packets is proposed. The key problem of efficient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 6

December 2009

331 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2009

Revised: 02 July 2008

Received: 09 May 2007

Published in TON Volume 17, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
151
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cai YWang XGong WTowsley D(2014)A Study on the Performance of a Three-Stage Load-Balancing SwitchIEEE/ACM Transactions on Networking10.1109/TNET.2013.224490622:1(52-65)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2244906
Szymanski TZomaya ACesana M(2008)Throughput and QoS optimization in nonuniform multichannel wireless mesh networksProceedings of the 4th ACM symposium on QoS and security for wireless and mobile networks10.1145/1454586.1454589(9-19)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1145/1454586.1454589

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