A service-curve framework for packet scheduling with switch configuration delays

ABSTRACT

In modern packet switches, technology limitations may introduce switch configuration delays that are nonnegligible compared with the time required to transmit a single packet. In this paper, we propose a methodology for scheduling of packets, in the context of these technology limitations. If the total tolerable delay through a packet switch is at least on the order of the switch configuration delay, we show that a near 100% utilization of the communication links is possible, while providing strict quality of service guarantees. The main idea is to increase the quantum with which data is scheduled and switched to beyond that of a single packet. This also decreases the rate at which scheduling need to be made, and hence decreases the implementation complexity. The quality of service guarantees we consider are in terms of a service curve. Specifically, we present a framework for the provision of service curves while coping with non-negligible switch configuration delays.

REFERENCES

• 1: Rajeev Agrawal , Rene L. Cruz , Clayton Okino , Rajendran Rajan, Performance bonds for flow control protocols, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.310-323, June 1999 [doi>10.1109/90.779197]
• 2: Cheng-Shang Chang, Performance Guarantees in Communication Networks, Springer-Verlag, London, 2000
• 3: [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.
• 4: [4] R. L. Cruz, "A calculus for network delay, part I: Network elements in isolation," IEEE Trans. Inf. Theory, vol. 37, no. 1, pp. 114-131, Jan. 1991.
• 5: [5] R. L. Cruz, "SCED+: Efficient management of quality of service guarantees," in Proc. IEEE INFOCOM, 1998, pp. 625-634.
• 6: [6] R. L. Cruz and S. Al-Harthi, "Packet scheduling with switch configuration delays," in Proc. 39th Annu. Allerton Conf. Commun., Contr., Comput., 2001.
• 7: Aura Ganz , Yao Gao, A time-wavelength assignment algorithm for a WDM star network, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2144-2150, May 1992, Florence, Italy
• 8: [8] S. Gopal and C. K. Wong, "Minimizing the number of switchings in a SS/TDMA system," IEEE Trans. Commun., vol. COM-33, no. 6, pp. 497-501, Jun. 1985.
• 9: [9] 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, Sep. 1991.
• 10: [10] T. Inukai, "An efficient SS/TDMA time slot assignment algorithm," IEEE Trans. Commun., vol. COM-27, no. 10, pp. 1449-1455, Oct. 1979.
• 11: [11] K. Kar, T. V. Lakshman, and S. D. L. Tassiulas, "Reduced complexity input buffered switches," in Proc. Hot Interconnects VIII, 2000.
• 12: Jean-Yves Le Boudec , Patrick Thiran, Network calculus: a theory of deterministic queuing systems for the internet, Springer-Verlag New York, Inc., New York, NY, 2001
• 13: Gerard R. Pieris , Galen H. Sasaki, Scheduling transmissions in WDM broadcast-and-select networks, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.105-110, April 1994 [doi>10.1109/90.298429]
• 14: Hanrijanto Sariowan , Rene L. Cruz , George C. Polyzos, SCED: a generalized scheduling policy for guaranteeing quality-of-service, IEEE/ACM Transactions on Networking (TON), v.7 n.5, p.669-684, Oct. 1999 [doi>10.1109/90.803382]
• 15: [15] D. Stephens and H. Zhang, "Implementing distributed packet fair queueing in a scalable switch architecture," in Proc. IEEE INFOCOM, 1998, pp. 282-290.
• 16: [16] B. Towles and W. J. Dally, "Guaranteed scheduling for switches with configuration overhead," in Proc. IEEE INFOCOM, 2002, pp. 342-351.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
MEMS, ballast packet, convoy, convoy buffer, network calculus, optical packet switching, quality of service (QoS), scheduling