© 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Networking
Volume 6 Number 5, October 1998

Table of Contents for this issue

Complete paper in PDF format

Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms

Dimitrios Stiliadis and Anujan Varma, Member, IEEE

Page 611.

Abstract:

In this paper, we develop a general model, called Latency-Rate servers ({al{LR}} servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an {al{LR}} server is determined by two parameters--the latency and the allocated rate. Several well-known scheduling algorithms, such as Weighted Fair Queueing, VirtualClock, Self-Clocked Fair Queueing, Weighted Round Robin, and Deficit Round Robin, belong to the class of {al{LR}} servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of {al{LR}} servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of {al{LR}} servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models.

References

  1. R. Agrawal and R. Rajan, "Performance bounds for guaranteed and adaptive services," Tech. Rep. RC 20649, IBM Research Div., 1996.
  2. R. L. Cruz, "A calculus for network delay. I. Network elements in isolation," IEEE Trans. Inform. Theory, vol. 37, pp. 114-131, Jan. 1991.
  3. --, "A calculus for network delay. II. Network analysis," IEEE Trans. Inform. Theory, vol. 37, pp. 132-141, Jan. 1991.
  4. --, "Service burstiness and dynamic burstiness measures: A framework," J. High-Speed Networks, vol. 1, no. 2, pp. 105-127, 1992.
  5. R. L. Cruz and H. N. Liu, "End-to-end queueing delay in ATM networks," J. High Speed Networks, vol. 2, no. 3, pp. 149-164, 1994.
  6. R. L. Cruz, "Quality of service guarantees in virtual circuit switched networks," IEEE J. Select. Areas Commun., vol. 13, pp. 1048-1056, Aug. 1995.
  7. R. L. Cruz and C. M. Okino, "Service guarantees for window flow control," in Proc. 34th Allerton Conf. on Communication Control and Computing, Monticello, IL, Oct. 1996, pp. 10-21.
  8. A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," Internetworking: Research and Experience, vol. 1, no. 1, pp. 3-26, 1990.
  9. N. Duffield, T. V. Lakshman, and D. Stiliadis, "On adaptive bandwidth sharing with rate guarantees," In Proc. IEEE INFOCOM'98, San Francisco, CA, Apr. 1998.
  10. S. J. Golestani, "A framing strategy for congestion management," IEEE J. Select. Areas Commun., vol. 9, pp. 1064-1077, Sept. 1991.
  11. --, "A self-clocked fair queueing scheme for broadband applications," in Proc. IEEE INFOCOM '94, Toronto, ON, Canada, Apr. 1994, pp. 636-646.
  12. --, "Network delay analysis of a class of fair queueing algorithms," IEEE J. Select. Areas Commun., vol. 13, pp. 1057-1070, Aug. 1995.
  13. P. Goyal, S. L. Lam, and H. M. Vin, "Determining end-to-end delay bounds in heterogeneous networks," in Proc. 5th Int. Workshop on Network and Operating System Support for Digital Audio and Video, Durham, NH, Apr. 1995, pp. 287-298.
  14. A. Hung and G. Kesidis, "Bandwidth scheduling for wide-area ATM networks using virtual finishing times," IEEE/ACM Trans. Networking, vol. 4, pp. 49-54, Feb. 1996.
  15. C. R. Kalmanek, H. Kanakia, and S. Keshav, "Rate controlled servers for very high-speed networks," in Proc. IEEE Global Telecommunications Conf., Dec. 1990, pp. 300.3.1-300.3.9.
  16. M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, "Weighted round-robin cell multiplexing in a general-purpose ATM switch chip," IEEE J. Select. Areas Commun., vol. 9, pp. 1265-1279, Oct. 1991.
  17. S. S. Lam and G. G. Xie, "Burst scheduling: Architecture and algorithm for switching packet video," in Proc. INFOCOM'95, Boston, MA, Apr. 1995, pp. 940-950.
  18. 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. Networking, vol. 1, no. 3, pp. 344-357, June 1993.
  19. --, "A generalized processor sharing approach to flow control in integrated services networks: The multiple node case," IEEE/ACM Trans. Networking, vol. 2, no. 2, pp. 137-150, Apr. 1994.
  20. M. Shreedhar and G. Varghese, "Efficient fair queueing using deficit round-robin," IEEE/ACM Trans. Networking, vol. 4, no. 3, pp. 375-385, June 1996.
  21. D. Stiliadis, "Traffic scheduling in packet-switched networks: Analysis, design and implementation," Ph.D. dissertation, Univ. of California, Santa Cruz, 1996. [Online]. Available WWW: www.cse.ucsc.edu/research/hsnlab/publications/
  22. D. Stiliadis and A. Varma, "Latency-rate servers: A general model for analysis of traffic scheduling algorithms," in Proc. IEEE INFOCOM '96, San Francisco, CA, Apr. 1996, pp. 111-119.
  23. --, "Rate-proportional servers: A design methodology for fair queueing algorithms," IEEE/ACM Trans. Networking, vol. 6, no. 2, pp. 164-174, Apr. 1998.
  24. --, "Efficient fair queueing algorithms for packet switched networks," IEEE/ACM Trans. Networking, vol. 6, no. 2, pp. 175-185, Apr. 1998.
  25. --, "A general methodology for designing efficient traffic scheduling and shaping algorithms," in Proc. IEEE INFOCOM'97, Kobe, Japan, Apr. 1997, pp. 326-335.
  26. O. Yaron and M. Sidi, "Performance and stability of communication networks via robust exponential bounds," IEEE/ACM Trans. Networking, vol. 1, no. 3, pp. 372-385, June 1993.
  27. H. Zhang, "Service disciplines for packet-switching integrated services networks," Ph.D. dissertation, Univ. of California, Berkeley, 1992.
  28. L. Zhang, "VirtualClock: A new traffic control algorithm for packet switching networks," ACM Trans. Computer Systems, vol. 9, no. 2, pp. 101-124, May 1991.
  29. Z. Zhang, D. Towsley, and J. Kurose, "Statistical analysis of generalized processor sharing scheduling discipline," in Proc. ACM SIGCOMM '94, Sept. 1994, pp. 68-77.