© 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

Efficient Admission Control of Piecewise Linear Traffic Envelopes at EDF Schedulers

Victor Firoiu, Member, IEEE, Jim Kurose, Fellow, IEEE, and Don Towsley, Fellow, IEEE

Page 558.

Abstract:

In this paper, we present algorithms for flow admission control at an earliest deadline first link scheduler when the flows are characterized by piecewise linear traffic envelopes. We show that the algorithms have very low computational complexity and, thus, practical applicability. The complexity can be further decreased by introducing the notion of discretized admission control. Through discretization, the range of positions for the end points of linear segments of the traffic envelopes is restricted to a finite set. Simulation experiments show that discretized admission control can lend to two orders of magnitude decrease in the amount of computation needed to make admission control decisions over that incurred when using exact (nondiscrete) admission control, with the additional benefit that this amount of computation no longer depends on the number of flows. We examine the relative performance degradation (in terms of the number of flows admitted) incurred by the discretization and find that it is small.

References

  1. ATM User-Network Interface Specification, Version 3.1, ATM Forum, Sept. 1994.
  2. R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, Resource ReSerVation Protocol (RSVP)--Version 1, Functional Specification, IETF Proposed Standard RFC 2205, Sept. 1997.
  3. C.-S. Chang, "Stability, queue length and delay of deterministic and stochastic queuing networks," IEEE Trans. Automat. Contr., vol. 39, May 1994.
  4. R. Cruz, "Quality of service guarantees in virtual circuit switched networks," IEEE J. Select. Areas Commun., vol. 13, Aug. 1995.
  5. --, "A calculus for network delay, Part I: Network elements in isolation," IEEE Trans. Inform. Theory, vol. 37, Jan. 1991.
  6. A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queuing algorithm," Comput. Commun. Rev., vol. 19, no. 4, 1989.
  7. D. Ferrari and D. Verma, "A scheme for real-time channel establishment in wide-area networks," IEEE J. Select. Areas Commun., vol. 8, Apr. 1990.
  8. V. Firoiu, "Network support for applications requiring quality of service in heterogeneous environments," Ph.D. dissertation, Dep. Comput. Sci., Univ. Massachusetts, Amherst, 1998.
  9. V. Firoiu and D. Towsley, "Call admission and resource reservation for multicast sessions," in Proc. IEEE INFOCOM, 1996, pp. 94-101.
  10. L. Georgiadis, R. Guerin, and A. Parekh, "Optimal multiplexing on a single link: Delay and buffer requirements," IEEE Trans. Inform. Theory, vol. 43, pp. 1518-1535, Sept. 1997.
  11. L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan, "Efficient network QoS provisioning based on per node traffic shaping," IEEE/ACM Trans. Networking, vol. 4, pp. 482-501, Aug. 1996.
  12. M. Grossglauser, S. Keshav, and D. Tse, "RCBR: A simple and efficient service for multiple time-scale traffic," in Proc. ACM SIGCOMM, 1995.
  13. D. Kandlur, K. Shin, and D. Ferrari, "Real-time communications in multihop networks," IEEE Trans. Parallel Distrib. Syst., vol. 5, Oct. 1994.
  14. E. Knightly, D. Wrege, J. Liebeherr, and H. Zhang, "Fundamental limits and tradeoffs of providing deterministic guarantees to VBR video traffic," in Proc. ACM SIGMETRICS'95, 1995.
  15. E. Knightly and H. Zhang, "Traffic characterization and switch utilization using a deterministic bounding interval dependent traffic model," in Proc. IEEE INFOCOM, 1995.
  16. E. Knightly and H. Zhang, "D-BIND: An accurate traffic model for providing QoS guarantees to VBR traffic," IEEE/ACM Trans. Networking, vol. 5, Apr. 1997.
  17. J. Liebeherr, D. Wrege, and D. Ferrari, "Exact admission control for networks with bounded delay services," IEEE/ACM Trans. Networking, vol. 4, Dec. 1996.
  18. C. Liu and J. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. Assoc. Comput. Mach., vol. 20, no. 1, Jan. 1973.
  19. O. Rose, "MPEG coded video traces," ftp://ftp-info3.informatik.uni-wuerzburg.de/pub/MPEG/.
  20. --, "Statistical properties of MPEG video traffic and their impact on traffic modeling in ATM systems," University of Würzburg, Würzburg, Germany, Technical Report TR 101, Feb. 1995.
  21. A. K. Parekh, "A generalized processor sharing approach to flow control in integrated services networks," Ph.D. dissertation, Dep. Elect. Eng. Comput. Sci., Massachusetts Inst. Technol., Cambridge, Feb. 1992.
  22. F. Preparata and M. Shamos," Computational Geometry.Berlin, Germany, Springer-Verlag, 1985.
  23. S. Sahu, V. Firoiu, D. Towsley, and J. Kurose, "Traffic models and admission control for variable bit rate continuous media transmission with deterministic service," in Proc. SPIE Symp. Voice, Video and Data Communications, 1998.
  24. S. Shenker, C. Partridge, and R. Guerin, Specification of Guaranteed Quality of Service, IETF Proposed Standard RFC 2212, Sept. 1997.
  25. D. Wrege and J. Liebeherr, "A near-optimal packet scheduler for QoS networks," in Proc. IEEE INFOCOM, 1997.
  26. H. Zhang and D. Ferrari, "Rate-controlled service disciplines," J. High Speed Networks, vol. 3, no. 4, 1994.
  27. Q. Zheng and K. Shin, "On the ability of establishing real-time channels in point-to-point packet-switched networks," IEEE Trans. Commun., vol. 42, 1994.