skip to main content
article

On guaranteed smooth scheduling for input-queued switches

Published: 01 December 2005 Publication History

Abstract

Input-queued switches are used extensively in the design of high-speed routers. As switch speeds and sizes increase, the design of the switch scheduler becomes a primary challenge, because the time interval for the matching computations needed for determining switch configurations becomes very small. Possible alternatives in scheduler design include increasing the scheduling interval by using envelopes [19], and using a frame-based scheduler that guarantees fixed rates between input-output pairs. However, both these alternatives have significant jitter drawbacks: the jitter increases with the envelope size in the first alternative, and previously-known methods do not guarantee tight jitter bounds in the second.In this paper, we propose a hybrid approach to switch scheduling. Traffic with tight jitter constraints is first scheduled using a frame-based scheduler that achieves low jitter bounds. Jitter-insensitive traffic is later scheduled using an envelope-based scheduler. The main contribution of this paper is a scheduler design for generating low-jitter schedules. The scheduler uses a rate matrix decomposition designed for low jitter and different from the minimum-bandwidth Birkhoff-Von Neumann (BV) decomposition. In addition to generating low-jitter schedules, this decomposition in the worst case yields fewer switch configuration matrices (O(n)) than the BV decomposition (O(n2)), and so requires far less high-speed switch memory. We develop an efficient algorithm for decomposing the rate matrix and for scheduling the permutation matrices. We prove that our low-jitter algorithm has an O(logn) factor bound on its bandwidth consumption in comparison to the minimum-bandwidth BV decomposition. Experimentally, we find that the bandwidth increase in practice is much lower than the theoretical bound. We also prove several related performance bounds for our scheduler. Finally, we propose a practical algorithm for bandwidth-guaranteed algorithm, and show how our findings could even be extended to systems with large tuning time.

References

[1]
{1} M. A. Marsan, P. Giaccone, E. Leonardi, and F. Neri, "On the stability of local scheduling policies in networks of packet switches with input queues," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 642-655, May 2003.
[2]
{2} E. Altman, Z. Liu, and R. Righter, "Scheduling of an input-queued switch to achieve maximal throughput," Prob. Eng. Inform. Sci., vol. 14, pp. 327-334, 2000.
[3]
{3} T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker, "High speed switch scheduling for local area networks," ACM Trans. Comput. Syst., vol. 11, no. 4, pp. 319-52, Nov. 1993.
[4]
{4} M. Andrews and M. Vojnovic, "Scheduling reserved traffic in input queued switches: New delay bounds via probabilistic techniqueues," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 595-605, May 2003.
[5]
{5} E. Balas and P. R. Landweer, "Traffic assignment in communication satellites," Oper. Res. Lett., vol. 2, pp. 141-147, Nov. 1983.
[6]
{6} A. Bar-Noy, R. Motwani, and J. Naor, "The greedy algorithm is optimal for on-line edge coloring," Inf. Process. Lett., vol. 44, no. 5, pp. 251-253, 1992.
[7]
{7} J. C. R. Bennett and H. Zhang, "WF2Q: Worst-case fair weighted fair queueing," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1996, pp. 120-128.
[8]
{8} G. Bongiovanni, D. Coppersmith, and C. K.Wong, "An optimal time slot assignment for an SS/TDMA system with variable number of transponders," IEEE Trans. Communications, vol. COM-29, no. 5, pp. 721-726, May 1981.
[9]
{9} C. S. Chang, J. W. Chen, and H. Y. Huang, "On service guarantees for input-buffered crossbar switches: a capacity decomposition approach by Birkhoff and von Neumann," in Proc. 7th Int. Workshop on Quality of Service (IWQoS), London, U.K., 1999, pp. 79-86.
[10]
{10} C. S. Chang, J. W. Chen, and H. Y. Huang, "Birkhoff-Von Neumann input-buffered crossbar switches," in Proc. IEEE INFOCOM, Tel Aviv, Israel, 2000, pp. 1614-1623.
[11]
{11} A. Charny et al., An expedited forwarding PHB. Internet Engineering Task Force. {Online}. Available: draft-ietf-diffserv-rfc2598bis-02.txt
[12]
{12} K. L. Chen, "A conflict-free protocol for optical WDMA networks," in Proc. IEEE GLOBECOM, 1991, pp. 1276-1281.
[13]
{13} N. R. Figueira and J. Pasquale, "An upper bound delay for the virtual-clock service discipline," IEEE Trans. Netw., vol. 3, no. 4, pp. 399-408, Aug. 1995.
[14]
{14} A. Ganz and Y. Gao, "Efficient algorithms for SS/TDMA scheduling," IEEE Trans. Commun., vol. 40, no. 8, pp. 1367-1374, Aug. 1992.
[15]
{15} P. Giaccone, B. Prabhakar, and D. Shah, "Toward simple, high-performance schedulers for high-aggregate bandwidth switches," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 1160-1169.
[16]
{16} I. Gopal and C. K. Wong, "Minimizing the number of switchings in an SS/TDMA system," IEEE Trans. Commun., vol. COM-33, no. 6, pp. 497-501, Jun. 1985.
[17]
{17} I. Gragopoulos and F.-N. Pavlidou, "A new evaluation criterion for Clos- and Benes-type rearrangeable switching networks," IEEE Trans. Commun., vol. 45, no. 1, pp. 119-126, Jan. 1997.
[18]
{18} A. Hung, G. Kesidis, and N. McKeown, "ATM input-buffered switches with the guaranteed-rate property," in Proc. 3rd IEEE Symp. Computers and Communications (ISCC), Athens, Greece, 1998, pp. 331-335.
[19]
{19} K. Kar, T. V. Lakshman, D. Stiliadis, and L. Tassiulas, "Reduced complexity input buffered switches," in Proc. Hot Interconnects VIII, Palo Alto, CA, Aug. 2000.
[20]
{20} H. Lee, F. Hwang, and J. Carpinelli, "A new matrix decomposition algorithm for rearrangeable Clos interconnection networks," IEEE Trans. Commun., vol. 44, no. 11, pp. 1572-1578, Nov. 1996.
[21]
{21} N. McKeown, M. Izzard, A. Mekkittikul, B. Ellersick, and M. Horowitz, "Tiny Tera: a packet switch core," in Proc. Hot Interconnects IV, Stanford, CA, Aug. 1996, pp. 161-173.
[22]
{22} C. A. Pomalaza-Raez, "A note on efficient SS/TDMA assignment algorithms," IEEE Trans. Commun., vol. 36, no. 9, pp. 1078-1082, Sep. 1988.
[23]
{23} F. Rendl, "On the complexity of decomposing matrices arising in satellite communication," Oper. Res. Lett., vol. 4, pp. 5-8, May 1985.
[24]
{24} D. Shah and M. Kopikare, "Delay bounds for approximate maximum weight matching algorithms for input queued switches," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 1024-1031.
[25]
{25} V. Sivaraman and G. N. Rouskas, "A reservation protocol for broadcast WDM networks and stability analysis," Comput. Netw., vol. 32, no. 2, pp. 211-227, Feb. 2000.
[26]
{26} IEEE J. Sel. Topics Quantum Electron., Special Issue on Optical MEMS, vol. 8, no. 1, Jan.-Feb. 2002.
[27]
{27} Y. Tamir and H. C. Chi, "Symmetric crossbar arbiters for VLSI communication switches," IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 1, pp. 13-27, Jan. 1993.
[28]
{28} L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input queued switches," in Proc. IEEE INFOCOM, vol. 2, San Francisco, CA, 1998, pp. 533-539.
[29]
{29} B. Towles and W. J. Dally, "Guaranteed scheduling for switches with configuration overhead," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 342-351.
[30]
{30} R. S. Tucker and W. D. Zhong, "Photonic packet switching: An overview," IEICE Trans. Commun., vol. E82-B, no. 2, pp. 254-264, Feb. 1999.
[31]
{31} T. Weller and B. Hajek, "Scheduling nonuniform traffic in a packet-switching system with small propagation delay," IEEE Trans. Netw., vol. 5, no. 6, pp. 813-823, Dec. 1997.
[32]
{32} K. L. Yeung, "Efficient time slot assignment algorithms for TDM hierarchical and nonhierarchical switching systems," IEEE Trans. Commun., vol. 49, no. 2, pp. 351-359, Feb. 2001.
[33]
{33} J. Gripp et al., "Demonstration of a 1.2 Tb/s optical packet switch fabric based on 40 Gb/s burst-mode clock-data-recovery, fast tunable lasers, and a high-performance N × N AWG," in Proc. 27th Eur. Conf. Optical Communication (ECOC), vol. 6, Oct. 2001, pp. 58-59.

Cited By

View all
  • (2022)Analysis of Performance Improvement of Real-time Internet of Things Application Data Processing in the Movie Industry PlatformComputational Intelligence and Neuroscience10.1155/2022/52372522022Online publication date: 1-Jan-2022
  • (2016)An ultra-low-latency guaranteed-rate internet for cloud servicesIEEE/ACM Transactions on Networking10.1109/TNET.2014.235849724:1(123-136)Online publication date: 1-Feb-2016
  • (2016)Supporting consumer services in a deterministic industrial internet core networkIEEE Communications Magazine10.1109/MCOM.2016.749809654:6(110-117)Online publication date: 22-Jun-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 13, Issue 6
December 2005
207 pages

Publisher

IEEE Press

Publication History

Published: 01 December 2005
Published in TON Volume 13, Issue 6

Author Tags

  1. jitter
  2. router
  3. scheduling
  4. switch

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Analysis of Performance Improvement of Real-time Internet of Things Application Data Processing in the Movie Industry PlatformComputational Intelligence and Neuroscience10.1155/2022/52372522022Online publication date: 1-Jan-2022
  • (2016)An ultra-low-latency guaranteed-rate internet for cloud servicesIEEE/ACM Transactions on Networking10.1109/TNET.2014.235849724:1(123-136)Online publication date: 1-Feb-2016
  • (2016)Supporting consumer services in a deterministic industrial internet core networkIEEE Communications Magazine10.1109/MCOM.2016.749809654:6(110-117)Online publication date: 22-Jun-2016
  • (2016)The emerging era of fog computing and networking [The President's Page]IEEE Communications Magazine10.1109/MCOM.2016.749775754:6(4-5)Online publication date: 22-Jun-2016
  • (2014)Impact of Future Trends on Exascale Grid and Cloud ComputingProceedings of the 29th International Conference on Supercomputing - Volume 848810.1007/978-3-319-07518-1_14(215-231)Online publication date: 22-Jun-2014
  • (2013)Low latency energy efficient communications in global-scale cloud computing systemsProceedings of the 2013 workshop on Energy efficient high performance parallel and distributed computing10.1145/2480347.2480349(13-22)Online publication date: 17-Jun-2013
  • (2011)Video multicasting in an autonomic future internet with essentially-perfect throughput and QoS guaranteesProceedings of the 11th international conference and 4th international conference on Smart spaces and next generation wired/wireless networking10.5555/2033707.2033780(608-619)Online publication date: 22-Aug-2011
  • (2011)Future internet video multicasting with essentially perfect resource utilization and QoS guaranteesProceedings of the Nineteenth International Workshop on Quality of Service10.5555/1996039.1996068(1-3)Online publication date: 6-Jun-2011
  • (2010)Provisioning backhaul traffic flows in TDMA/OFDMA infrastructure wireless mesh networks with near-perfect QoSProceedings of the 33rd IEEE conference on Sarnoff10.5555/1843486.1843506(100-106)Online publication date: 12-Apr-2010
  • (2010)Rate quantization and the speedup required to achieve 100% throughput for multicast over crossbar switchesIEEE/ACM Transactions on Networking10.1109/TNET.2009.203858218:4(1207-1219)Online publication date: 1-Aug-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media