skip to main content
article

Approximating fluid schedules in crossbar packet-switches and Banyan networks

Published: 01 December 2006 Publication History

Abstract

We consider a problem motivated by the desire to provide flexible, rate-based, quality of service guarantees for packets sent over input queued switches and switch networks. Our focus is solving a type of online traffic scheduling problem, whose input at each time step is a set of desired traffic rates through the switch network. These traffic rates in general cannot be exactly achieved since they assume arbitrarily small fractions of packets can be transmitted at each time step. The goal of the traffic scheduling problem is to closely approximate the given sequence of traffic rates by a sequence of transmissions in which only whole packets are sent. We prove worst-case bounds on the additional buffer use, which we call backlog, that results from using such an approximation.We first consider the N × N, input queued, crossbar switch. Our main result is an online packet-scheduling algorithm using no speedup that guarantees backlog at most (N+1)2/4 packets at each input port and each output port. Upper bounds on worst-case backlog have been proved for the case of constant fluid schedules, such as the N2-2N+2 bound of Chang, Chen, and Huang (INFOCOM, 2000). Our main result for the crossbar switch is the first, to our knowledge, to bound backlog in terms of switch size N for arbitrary, time-varying fluid schedules, without using speedup.Our main result for Banyan networks is an exact characterization of the speedup required to maintain bounded backlog, in terms of polytopes derived from the network topology.

References

[1]
{1} C.-S. Chang, W.-J. Chen, and H.-Y. Huang, "Birkhoff-von Neumann input buffered crossbar switches," in Proc. IEEE INFOCOM, 2000, pp. 1614-1623.
[2]
{2} M. Adler, P. Berenbrink, T. Friedetzky, L. A. Goldberg, P. W. Goldberg, and M. Paterson, "A proportionate fair scheduling rule with good worst-case performance," presented at the ACM Symp. Parallel Algorithms and Architectures, San Diego, CA, Jun. 2003.
[3]
{3} J. C. R. Bennett and H. Zhang, "WF2 Q: worst-case fair weighted fair queueing," in Proc. IEEE INFOCOM, 1996, pp. 120-128.
[4]
{4} M. Bonuccelli and M. Clo, "EDD algorithm performance guarantee for periodic hard-real-time scheduling in distributed systems," in Proc. IEEE IPPS/SPDP, Apr. 1999, pp. 668-677.
[5]
{5} A. Charny, "Providing QoS guarantees in input-buffered crossbar switches with speedup," Ph.D. dissertation, Mass. Inst. Technol., Cambridge, MA, Aug. 1998.
[6]
{6} R. Cruz, "A calculus for network delay. I. Network elements in isolation," IEEE Trans. Inf. Theory, vol. 37, no. 1, pp. 114-131, Jan. 1991.
[7]
{7} R. Cruz, "A calculus for network delay. II. Network analysis," IEEE Trans. Inf. Theory, vol. 37, no. 1, pp. 132-141, Jan. 1991.
[8]
{8} N. G. Duffield, T. V. Lakshman, and D. Stiliadis, "On adaptive bandwidth sharing with rate guarantees," in Proc. IEEE INFOCOM, 1998, pp. 1122-1130.
[9]
{9} M. J. Girone, "Tracking switch fluid policies: bounding lookahead," Master's project, Dept. Elect. Eng. Comput. Sci., Mass. Inst. Technol., Feb. 2002.
[10]
{10} A. C. Kam and K.-Y. Siu, "Linear complexity algorithms for QOS support in input-queued switches with no speedup," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1040-56, Jun. 1999.
[11]
{11} C. E. Koksal, "Providing quality of service over high speed electronic and optical switches," Ph.D. dissertation, Mass. Inst. Technol., Cambridge, MA, Sep. 2002.
[12]
{12} A. K. 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.
[13]
{13} A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: the multiple node case," IEEE/ACM Trans. Netw., vol. 2, no. 2, pp. 137-150, Apr. 1994.
[14]
{14} A. Stamoulis and G. B. Giannakis, "Deterministic time-varying packet fair queueing for integrated services networks," in Proc. IEEE Global Telecommunications Conf., 2000, vol. 1, pp. 621-625.
[15]
{15} V. Tabatabaee, L. Georgiadis, and L. Tassiulas, "QoS provisioning and tracking fluid policies in input queueing switches," in Proc. IEEE INFOCOM , 2000, pp. 1624-1633.
[16]
{16} J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, 2000, pp. 556-564.
[17]
{17} E. Leonardi, M. Mellia, F. Neri, and M. Marsan, "On the stability of input-queued switches with speed-up," IEEE/ACM Trans. Netw., vol. 9, no. 1, pp. 104-118, Feb. 2001.
[18]
{18} N. McKeown, V. Anantharam, and J. C. Walrand, "Achieving 100% throughput in an input-queued switch," in Proc. IEEE INFOCOM, 1996, pp. 296-302.
[19]
{19} L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input queued switches," in Proc. IEEE INFOCOM , 1998, pp. 533-539.
[20]
{20} M. Andrews, B. Awerbuch, A. Fernandez, T. Leighton, Z. Liu, and J. Kleinberg, "Universal-stability results and performance bounds for greedy contention-resolution protocols," J. ACM, vol. 48, no. 1, pp. 39-69, 2001.
[21]
{21} M. Andrews and L. Zhang, "The effects of temporary sessions on network performance," in Proc. 11th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), San Francisco, CA, 2000, pp. 448-457.
[22]
{22} A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. P. Williamson, "Adversarial queuing theory," J. ACM, vol. 48, no. 1, pp. 13-38, 2001.
[23]
{23} T. Lee and C. Lam, "Path switching--a quasi-static routing scheme for large-scale ATM packet switches," IEEE J. Sel. Areas Commun., vol. 15, no. 5, pp. 914-924, Jun. 1997.
[24]
{24} L. Tassiulas and L. Georgiadis, "Any work-conserving policy stabilizes the ring with spatial re-use," IEEE/ACM Trans. Netw., vol. 4, no. 2, pp. 205-208, Apr. 1996.
[25]
{25} A. Pattavina, Switching Theory, Architectures and Performance in Broadband ATM Networks. New York: Wiley, 1998.
[26]
{26} S. Keshav, An Engineering Approach to Computer Networking. Boston, MA: Addison-Wesley, 1997.
[27]
{27} M. A. Rosenblum, "Approximating fluid schedules in packet-switched networks," Ph.D. dissertation, Mass. Inst. Technol., Cambridge, MA, Sep. 2004.
[28]
{28} 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, Hong Kong, Mar. 2004, pp. 1126-1134.
[29]
{29} P. Hall, "On representatives of subsets," J. London Math. Soc., no. 10, pp. 26-30, 1935.
[30]
{30} V. Chvatal, Linear Programming. San Francisco, CA: W.H. Freeman, 1983.
[31]
{31} J. Hopcroft and R. Karp, "An n 5/2 algorithm for maximum matchings in bipartite graphs," SIAM J. Computing, no. 2, pp. 225-231, 1973.
[32]
{32} A. Schrijver, "Bipartite edge-colouring in Om) time," SIAM J. Computing, vol. 28, pp. 841-846, 1999.
[33]
{33} H. Gabow, "Using euler partitions to edge color bipartite multigraphs," Int. J. Comput. Inf. Sci., no. 5, pp. 345-355, 1976.
[34]
{34} A. Schrijver, Combinatorial Optimization. New York: Springer, 2003.
[35]
{35} R. Wenger, "Helly-type theorems and geometric transversals," in Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds. Cleveland, OH: CRC Press, 1997.
[36]
{36} M. Grotschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Berlin: Springer-Verlag, 1993.
[37]
{37} J. Matoušsek, Lectures on Discrete Geometry. New York: Springer, 2002.
[38]
{38} T. Motzkin, H. Raiffa, G. Thompson, and R. Thrall, Contributions to Theory of Games, H.W. Kuhn and A. W. Tucker, Eds. Princeton, NJ: Princeton Univ. Press, 1953, vol. 2.
[39]
{39} A. Smiljanić, "Flexible bandwidth allocation in high-capacity packet-switches," IEEE/ACM Trans. Netw., vol. 10, no. 2, pp. 287-293, Apr. 2002.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue 6
December 2006
247 pages

Publisher

IEEE Press

Publication History

Published: 01 December 2006
Published in TON Volume 14, Issue 6

Author Tags

  1. combinatorics
  2. graph theory
  3. network calculus
  4. packet-switching
  5. scheduling

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 251
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

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