A measurement-based admission control algorithm for integrated services packet networks

ABSTRACT

Many designs for integrated service networks offer a bounded delay packet delivery service to support real-time applications. To provide bounded delay service, networks must use admission control to regulate their load. Previous work on admission control mainly focused on algorithms that compute the worst case theoretical queueing delay to guarantee an absolute delay bound for all packets. In this paper we describe a measurement-based admission control algorithm for predictive service, which allows occasional delay violations. We have tested our algorithm through simulations on a wide variety of network topologies and driven with various source models, including some that exhibit long-range dependence, both in themselves and in their aggregation. Our simulation results suggest that, at least for the scenarios studied here, the measurement-based approach combined with the relaxed service commitment of predictive service enables us to achieve a high level of network utilization while still reliably meeting the delay bound.

REFERENCES

• AM95: A. Adas , A. Mukherjee, On resource management and QoS guarantees for long range dependent traffic, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 2)-Volume, p.779, April 02-06, 1995
• AS94: S. Abe and T. Soumiya. "A Traffic Control Method for Service Quality Assurance in an ATM Network". IEEE Journal of Selected Areas in Communication, 12(2):322-331,Feb. 1994.
• Ber94: J Beran. Statistics Jbr Long-Memory Processes. New York: Chapman & Hail, 1994.
• BJ76: George Edward Pelham Box , Gwilym Jenkins, Time Series Analysis, Forecasting and Control, Holden-Day, Incorporated, 1990
• Bol94: V.A. Bolotin. "Modeling Call Holding Time Distributions for CCS Network Design and Performance Analysis". iEEE Journal o/'Selected Areas in Communication, 12(3):433-438, Apr. 1994.
• Bre95: Lee Michel Breslau , Deborah Estrin, Adaptive source routing of real-time traffic in integrated services networks, 1995
• BSTW95: J. Beran, R. Sherman, M.S. Taqqu, and W Willinger. "Variable-Bit-Rate Video Traffic and Long-Range Dependence''. ACM/iEEE Transactions on Networking, to appear in 1995.
• CI90: D. Cox and V. Isham. Point Processes. New York: Chapman & Hall, 1990.
• CLG95: S. Chong, S-Q. Li, and J. Ghosh. "Predictive Dynamic Bandwidth Allocation for Efficient Transport of Real-Time VBR Video over ATM". IEEE Journal of Selected Areas in Commumcation, 13(1): 12-23, Jan. 1995.
• Cru91: R.L. Cruz. "A Calculus for Network Delay, Part I: Network Elements in Isolation". IEEE Transactions on Information Theory, 37(1):l14-131,Jan. i991.
• CSZ92: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• DJ91: P.B. Danzig and S. Jamin. tcplib: A Library ofTCP Internetwork Traffic Characteristics. Technical Report 91-495, USC, CS Dept., I991. URL http://netweb.usc.edu/jamin/tcplib.
• DKPS95: M. Degermark, T. Krhler, S. Pink, and Schelrn. "Advance ReservaUons for Predicted Service". Submitted for publication, 1995.
• DKS89: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• DMRW94: D.E. Duffy, A.A. Mclntosh, M. Rosenstein, and W. Willinger. "Statistical Analysis of CCSN/SS7 Traffic Data from Working CCS Subnetworks". IEEE Journal of Selected Areas in Communication, 12(3):544-551, Apr. 1994.
• Flo94: S. Floyd. Personal communication. Phone conversation, 1994.
• FV90: D. Ferrari and D.C. Verma. "A Scheme for Real-Time Channel Establishment in Wide-Area Networks". 1EEE Journal of Selected Areas in Communtcation, 8(3):368-379,1990.
• GHN91: R. Gurrin, Ahmadi H., and M. Naghshineh. "Equivalent Capacity and Its Application to Bandwidth Allocation in High- Speed Networks". IEEE Journal of Selected Areas in Communication, 9(7):968-981, Sept. 1991.
• GW94: Mark W. Garrett , Walter Willinger, Analysis, modeling and generation of self-similar VBR video traffic, Proceedings of the conference on Communications architectures, protocols and applications, p.269-280, August 31-September 02, 1994, London, United Kingdom
• Hir91: A. Hiramatsu. "Integration of^TM Call Admission Control and Link Capacity Control by Distributed Neural Network". IEEE Journal of Selected Areas in Communication, 9(7): 1131-1138, Sept. 1991.
• HLP93: J.M. Hyman, A.A. Lazar, and G. Pacifici. "A Separation Principle Between Scheduling and Admission Control for Broadband Switching". IEEE Journal of Selected Areas in Communication, 1 l(4):605-616, May 1993.
• Hos84: J.R.M. Hosking. "Modeling Persistence in Hydrological Time Series Using Fractional Differencing. Water Resources Research, 20(12):1898-1908, Dec. 1984.
• HR89: J. Haslett and A.E. Raftery. "Space-time Modelling with Longmemory Dependence: Assessing Ireland's Wind Power Resource". Applied Statisttcs, 38(1 ): 1-50, 1989.
• Hui88: J.Y. Hui. "Resource Allocation for Broadband Networks". IEEE Journal of Selected Areas in Communication, 6(9):1598-1608, Dec. 1988.
• Jai91: R. Jain. The Art of Computer Systems PetCbrmance Analysis. New York: John Wiley & Sons, Inc., 1991.
• Jam95: Sugih Jamin, A measurement-based admission control algorithm for integrated services packet networks, 1996
• JSZC92: Sugih Jamin , Scott Shenker , Lixia Zhang , David D. Clark, An Admission Control Algorithm for Predictive Real-Time Service (Extended Abstract), Proceedings of the Third International Workshop on Network and Operating System Support for Digital Audio and Video, p.349-356, November 12-13, 1992
• Kel91: F. P. Kelly, Effective bandwidths at multi-class queues, Queueing Systems: Theory and Applications, v.9 n.1-2, p.5-16, Oct. 1991 [doi>10.1007/BF01158789]
• KM94: S.M. Klivansky and A. Mukherjee. "On Long-Range Dependence in NSFNET Traffic". preprint, 1994.
• LTWW94: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• Mol27: E.C Molina. "Application of the Theory of Probability to Telephone Trunking Problems". The Bell System Technical Journal, 6:461--494, 1927.
• NK92: Ramesh Nagarajan , James F. Kurose, On defining, computing and guaranteeing quality-of-service in high-speed networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2016-2025, May 1992, Florence, Italy
• OON88: H. Ohnishi, T. Okada, and K. Noguchi. "Flow Control Schemes and Delay/Loss Tradeoff in ^TM Networks". IEEE Journal of Selected Areas in Communication, 6(9): 1609-1616, Dec. 1988.
• Par92: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• PF94: Vern Paxson , Sally Floyd, Wide-area traffic: the failure of Poisson modeling, Proceedings of the conference on Communications architectures, protocols and applications, p.257-268, August 31-September 02, 1994, London, United Kingdom
• SCZ95: S. Shenker, D.D. Clark, and L. Zhang. A Scheduling Service Model and a Scheduling Archttecture {or an Integrated Services Packet Network. Submitted for publication, 1995.
• SS91: H. Saito and K. Shiomoto. "Dynamic Call Admission Control in ATM Networks". IEEE Journal o/Selected Areas in Communication, 9(7):982-989, Sept. 1991.
• VPV88: W. Verbiest, L. Pinnoo, and B. Voeten. "The Impact of the ATM Concept on Video Coding". iEEE Journal o! Selected Areas in Communication, 6(9):1623-1632, Dec. 1988.
• Wil95: W. Willinger. Private communication. E-mail, 1995.
• Z+93: L. Zhang et al. Resource ReSerVation Protocol (RSVP) Internet- Draft. URL ftp://ds.internic.net/internet-drafts/draft-ietf-rsvpspec-04.txt, Oct. 1993.
• ZF94: H. Zhang and D. Ferrari. "Improving Utilization for Deterministic Serwce in Multimedia Communication". IEEE Internanonal Conference on Multime&a Computmg and Systems, 1994
• ZK94: Hui Zhang , Edward W. Knightly, Providing end-to-end statistical performance guarantees with bounding interval dependent stochastic models, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.211-220, May 16-20, 1994, Nashville, Tennessee, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Measurement, Performance