Measurement-based admission control at edge routers

ABSTRACT

It is very important to allocate and manage resources for multimedia traffic flows with real-time performance requirements in order to guarantee quality of service (QoS). In this paper, we develop a scalable architecture and an algorithm for admission control of real-time flows. Since individual management of each traffic flow on each transit router can cause a fundamental scalability problem in both data and control planes, we consider that each flow is classified at the ingress router and data traffic is aggregated according to the class inside the core network as in a DiffServ framework. In our approach, admission decision is made for each flow at the edge (ingress) routers, but it is scalable because per-flow states are not maintained and the admission algorithm is simple. In the proposed admission control scheme, an admissible bandwidth, which is defined as the maximum rate of a flow that can be accommodated additionally while satisfying the delay performance requirements for both existing and new flows, is calculated based on the available bandwidth measured by edge routers. The admissible bandwidth is a threshold for admission control, and thus, it is very important to accurately estimate the admissible bandwidth. The performance of the proposed algorithm is evaluated by taking a set of simulation experiments using bursty traffic flows.

REFERENCES

• 1: R. Braden , D. Clark , S. Shenker, Integrated Services in the Internet Architecture: an Overview, RFC Editor, 1994
• 2: S. Blake , D. Black , M. Carlson , E. Davies , Z. Wang , W. Weiss, An Architecture for Differentiated Service, RFC Editor, 1998
• 3: Abhijit Bose , Mohamed El Gendy , Kang G. Shin, Sapphire: Statistical Characterization and Model-Based Adaptation of Networked Applications, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1512-1525, December 2006 [doi>10.1109/TPDS.2006.177]
• 4: [4] E. Lochin, L. Dairaine, and G. Jourjon, "gTFRC, a TCP friendly QoS-aware rate control for DiffServ assured service," Telecommun. Syst., vol. 33, no. 1-3, pp. 3-21, Dec. 2006.
• 5: Sugih Jamin , Peter B. Danzig , Scott J. Shenker , Lixia Zhang, A measurement-based admission control algorithm for integrated service packet networks, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.56-70, Feb. 1997 [doi>10.1109/90.554722]
• 6: Lee Breslau , Edward W. Knightly , Scott Shenker , Ion Stoica , Hui Zhang, Endpoint admission control: architectural issues and performance, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.57-69, August 28-September 01, 2000, Stockholm, Sweden
• 7: [7] F. P. Kelly, P. B. Key, and S. Zachary, "Distributed admission control," IEEE J. Sel. Areas Commun., vol. 18, no. 12, pp. 2617-2628, Dec. 2000.
• 8: [8] S. Crosby et al., "Statistical properties of a near-optimal measurement-based CAC algorithm," in Proc. IEEE ATM'97, May 1997, pp. 103-112.
• 9: Zbigniew Dziong , Marek Juda , Lorne G. Mason, A framework for bandwidth management in ATM networks—aggregate equivalent bandwidth estimation approach, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.134-147, Feb. 1997 [doi>10.1109/90.554728]
• 10: [10] S. Floyd, "Comments on "Measurement-based admission control for controlled-load services"," Lawrence Berkeley Lab., Tech. Rep., Jul. 1997.
• 11: [11] R. Gibbens and F. Kelly, "Measurement-based connection admission control," in 15th Int. Teletraffic Congr., Jun. 1997.
• 12: [12] R. J. Gibbens, F. P. Kelly, and P. B. Key, "A decision-theoretic approach to call admission control in ATM networks," IEEE J. Sel. Areas Commun., vol. 13, no. 6, pp. 1101-1114, Aug. 1995.
• 13: Matthias Grossglauser , David Tse, A framework for robust measurement-based admission control, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.237-248, Oct. 1997
• 14: [14] M. Grossglauser and D. Tse, "A time-scale decomposition approach to measurement-based admission control," in Proc. IEEE INFOCOM, Mar. 1999, vol. 3, pp. 1539-1547.
• 15: Claudio Casetti , James F. Kurose , Donald F. Towsley, A new algorithm for measurement-based admission control in integrated services packet networks, Proceedings of the TC6 WG6.1/6.4 Fifth International Workshop on Protocols for High-Speed Networks V, p.13-28, October 28-30, 1996
• 16: Sugih Jamin , Scott J. Shenker , Peter B. Danzig, Comparison of Measurement-based Admission Control Algorithms for Controlled-Load Service, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.973, April 09-11, 1997
• 17: [17] L. Breslau and S. Jamin, "Comments on the performance of measurement-based admission control algorithms," in Proc. IEEE INFOCOM, Mar. 2000, vol. 3, pp. 1233-1242.
• 18: [18] R. Guerin, H. Ahmadi, and M. Naghshineh, "Equivalent capacity and its application to bandwidth allocation in high-speed networks," IEEE J. Sel. Areas Commun., vol. 9, no. 7, pp. 968-981, Sep. 1991.
• 19: [19] A. Elwalid, D. Mitra, and R. H. Wentworth, "A new approach for allocating buffers and bandwidth to heterogeneous, regulated traffic in an ATM node," IEEE J. Sel. Areas Commun., vol. 13, no. 6, pp. 1115-1127, Aug. 1995.
• 20: [20] F. P. Kelly, "Note on effective bandwidth," in Stochastic Networks: Theory and Applications, ser. Royal Statistical Society Lecture Notes, F. P. Kelly, S. Zachary, and I. B. Ziedins, Eds. London, U.K.: Oxford Univ. Press, 1996, vol. 4, pp. 141-168.
• 21: Sunggon Kim , Seung Yeob Nam , Dan Keun Sung, Effective bandwidth for a single server queueing system with fractional Brownian input, Performance Evaluation, v.61 n.2-3, p.203-223, July 2005 [doi>10.1016/j.peva.2004.11.007]
• 22: [22] J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger, "Long-range dependence in variable bit rate video traffic," IEEE Trans. Commun., vol. 43, no. 2/3/4, pp. 1566-1579, Feb./Mar./Apr. 1995.
• 23: 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
• 24: [24] S. Kim, J. Y. Lee, and D. K. Sung, "A shifted gamma distribution model for long-range dependent Internet traffic," IEEE Commun. Lett., vol. 7, no. 3, pp. 124-126, Mar. 2003.
• 25: [25] N. G. Duffield and N. O'Connell, "Large deviations and overflow probabilities for the general single-server queue, with applications," Math. Proc. Cambridge Philos. Soc., vol. 118, pp. 363-374, 1995.
• 26: [26] J. R. Gallardo, D. Makrakis, and M. Angulo, "Dynamic resource management considering the real behavior of aggregate traffic," IEEE Trans. Multimedia, vol. 3, no. 2, pp. 177-185, Jun. 2001.
• 27: K. Ramakrishnan , S. Floyd, A Proposal to add Explicit Congestion Notification (ECN) to IP, RFC Editor, 1999
• 28: [28] C. Cetinkaya, V. Kanodia, and E. W. Knightly, "Scalable services via egress admission control," IEEE Trans. Multimedia, vol. 3, no. 1, pp. 69-81, Mar. 2001.
• 29: [29] S. Y. Nam, S. Kim, and D. K. Sung, "Estimation of available bandwidth for an unidentified queueing system," KAIST, Daejeon, Korea, Tech. rep. KAIST-CNR-06-01, 2006.
• 30: [30] S. Y. Nam, S. Kim, J. Kim, and D. K. Sung, "Probing-based estimation of end-to-end available bandwidth," IEEE Commun. Lett., vol. 8, no. 6, pp. 400-402, Jun. 2004.
• 31: [31] S. Y. Nam, "Available bandwidth estimation and measurement-based admission control in IP networks," Ph.D. thesis, Dept. EECS, KAIST, Daejeon, Korea, 2004.
• 32: [32] S. Karlin and H. M. Taylor, A First Course in Stochastic Processes, 2nd ed. New York: Academic, 1975.
• 33: [33] One-Way Transmission Time, ITU-T Recommendation G.114, May 2000.
• 34: [34] A. Shriram and J. Kaur, "Empirical study of the impact of sampling timescales and strategies on measurement of available bandwidth," in Proc. Passive and Active Measurement (PAM) Conf., Mar. 2006.
• 35: [35] B. Melander, M. Bjorkman, and P. Gunningberg, "A new end-to-end probing and analysis method for estimating bandwidth bottlenecks," in Proc. IEEE Globecom, Nov. 2000, pp. 415-421.
• 36: [36] M. Jain and C. Dovrolis, "Pathload: A measurement tool for end-to-end available bandwidth," in Proc. Passive and Active Measurements (PAM) Workshop, Mar. 2002.
• 37: [37] N. Hu and P. Steenkiste, "Evaluation and characterization of available bandwidth probing techniques," IEEE J. Sel. Areas Commun., vol. 21, no. 6, pp. 879-894, Aug. 2003.
• 38: [38] R. H. Riedi, M. S. Crouse, V. J. Ribeiro, and R. G. Baraniuk, "A multifractal wavelet model with application to network traffic," IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 992-1018, Apr. 1999.
• 39: [39] Services and Service Capabilities, 3GPP Technical Specification 22.105.
• 40: [40] Quality of Service (QoS) Concept and Architecture, 3GPP Technical Specification 23.107.
• 41: [41] R. W. Wolff, Stochastic Modeling and the Theory of Queues. Englewood Cliffs, NJ: Prentice-Hall, 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management
      C.2.6 Internetworking
          Subjects: Routers
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Management, Performance, Security

Keywords:
admissible bandwidth, admission control, available bandwidth, measurement, quality of service (QoS)