Internet Draft Internet Traffic Engineering Working Group Cheng C. Chen <draft-cchen-te-overbooking-00.txt> Shanti Hadvani Expires May 17, 2001 NEC America, Inc Category: Informational Rauf Izmailov C&C Princeton Lab, NEC 17 Norvember 2000 The Notion of overbooking and Its Application to IP/MPLS Traffic Engineering <draft-cchen-te-overbooking-00.txt> Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026[1]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsolete by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This contribution aims at examining the notion of overbooking in detail and its application on traffic engineering and capacity planning. For the ease of explanation, MPLS network with DiffServ support is used to demonstrate the concept in the subsequent sections. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [2]. Cheng , Shanti, Rauf [Page 1] NEC contribution on The Notion of overbooking November 17,2000 1. Introduction Many network design and capacity provisioning approaches assume that network engineers have access to accurate traffic demand data. Other approaches assume that users can accurately describe their QoS requirements using traffic descriptors and Service Level Agreements (SLA). Both assumptions have to be questioned. Pricing structure may result in discrepancy between customer-declared traffic descriptors and actual traffic send into the network; predicted traffic demand may be distorted, and so on. To improve the network efficiency, this contribution revisits the notion of "Overbooking Factor" and its applications to off-line and on-line traffic engineering mechanisms. The proposal aims at complementing the existing traffic engineering methodologies such as those documented in [3], [4], etc. The notion of "overbooking" can be traced back to the concept of "concentration ratio" in the voice-based telephone network. In the past decade, the concept of overbooking was utilized in ATM networks as "statistical multiplexing gain" for the bursty (variable-bit rate) traffic. The overbooking concept will become even more relevant in engineering of MPLS-based DiffServ networks. While telecommunications network operators have been using overbooking for a long time, there is hardly a clear definition of it. Usually, overbooking is interpreted and implemented in telecom network equipment differently. This contribution aims at examining the notion of overbooking and its applications to traffic engineering and capacity planning in detail. To simplify the discussion, MPLS network with DiffServ support is used to demonstrate the concept in the subsequent sections. 2. Factors Affecting the Efficiency of Network Capacity Design and Traffic Engineering Processes Efficiency of planning and engineering an MPLS-based DiffServ network for guaranteeing QoS requirements is complicated by the following factors. 2-1. The inaccuracy of predictions of traffic demands. 2-2. The discrepancy between customer-declared traffic descriptor and the actual traffic. This can happen due to a user mistake, malicious behavior; it can also be a result of improperly designed charging policy of service provider. 2-3. The traffic non-coincident phenomena, i.e. the peak hour traffic occurs in different time period due to diverse geographic locations. Cheng , Shanti, Rauf [Page 2] NEC contribution on The Notion of overbooking November 17,2000 All these factors can greatly contribute to the accuracy (over- provisioning or under-provisioning) of bandwidth allocation and admission control, since the actual bandwidth demand within the network becomes an unknown variable. In live networks, the "Overbooking Factor" could be as high as 400~500%. 3. Proposed Definition of Overbooking Factor The following three parameters determine the overbooking factor: a. P(i): The probability that a connection is at active state (off-hook) during the time period "i" of the day b. S(i): Statistical multiplexing gain during the time period "i" of the day. For non-bursty traffic, S(i)= 1. S(j) = N*EQB(j)/EQBN(j); where EQB(j) is the equivalent bandwidth of one LSP based on traffic descriptors and QoS requirements and EQBN(j) is the aggregate equivalent bandwidth of N active LSPs in some service class j assuming all LSPs have identical PHBs. c. A(i): Accuracy factor which summarizes the inaccuracy of market traffic projection, charging method, and user claimed relative to the actual traffic descriptors. A(i) can be defined as follows: A(i) = EQBC(i)/EQB(i), where EQBC(i) is the bandwidth or equivalent bandwidth based on marketing projection or computed based on available (possibly inaccurate) information (such as traffic descriptors claimed by the user). The overbooking factor OBF(i) at time period "i" can be defined as follows: OBF(i) = S(i)* A(i)/S(i) Accuracy factor A(i) is difficult to quantify without using traffic measurement technique to estimate the actual traffic being sent for each LSP within certain DiffServ service class. With properly designed traffic measurements on packet inter-arrival time, the overbooking factor for service class can be determined by the following algorithm. An Algorithm for Determining Overbooking Factor for DiffServ Service Class in an MPLS network Cheng , Shanti, Rauf [Page 3] NEC contribution on The Notion of overbooking November 17,2000 Step 1: Select a traffic model for the service class. (for some bursty traffic one may choose on-off source model). Step 2: For each service class, monitor the average packet interarrival time and average packet size. Step 3: Estimate the traffic parameters associated with the traffic model determined in Step 1. (e.g., for on-off source model there are two parameters: the average of burst and silent duration, the estimation method results in a closed-form solution). Step 4: Calculate the equivalent bandwidth EQB(i) For aggregate traffic based on traffic model and estimated parameters based on measurement data. (One may use Chernoff bound or large deviation theory for calculating equivalent bandwidth, which will result in closed form solution in many situations [5]). Step 5: Calculate the equivalent bandwidth EQBP(i) based on the market projection or user specified traffic descriptor and QoS requirements with same technique described in Step 4. Step 6: Let overbooking factor for time period "i" Be OBF(i) = EQBP(i)/EQB(i). Notice that while overbooking factor is an effective mechanism for improving network utilization efficiency. It is a function of time; it changes according to time of day. However, frequent change of overbooking factor may cause network instability. If operator determines the overbooking factor based on the busy hour, the only time the operator need to change the overbooking factor is before the special event such as mothers day or a significant shift in traffic demand patterns. Cheng , Shanti, Rauf [Page 4] NEC contribution on The Notion of overbooking November 17,2000 4. MPLS Traffic Engineering based on Overbooking Overbooking factor can be used for such MPLS traffic engineering tasks as off-line traffic estimation and network design and on-line traffic control on network level including network monitoring, trunk engineering, dynamic routing and node level including admission control, buffer threshold setting, and packet buffering and processing. We describe the method of using overbooking factor to improve the efficiency and accuracy of traffic engineering process in the following sections. 4.1 Application of Overbooking Factor in Off-line Traffic Estimation and Network Design Let A = [a(I,j)] be the traffic demand matrix and a(I,j) is the traffic demand from node I to node j, based on market projection or calculated from aggregated LSP demand based on user specified traffic descriptors and QoS. Step 1: For each pair of originating, destination (I,j), let the updated a'(I,j) = a(I,j)/OBF(k) for certain time period k. Step 2: Let the updated traffic demand matrix A'(I,j) = [a'(I,j)] Step 3: Use the updated traffic demand matrix A'[a(I,j)] as input to the network design algorithm for sizing working capacity and spare capacity for restoration for each link in the network. 4.2 On-line Traffic Control Using Overbooking Factor One of the important applications of overbooking factor in the MPLS network is supporting link state routing and threshold setting for the flooding for the link state changes. For dynamic routing the path computation will need to recompute whenever link state changes. Thus, for each admitted connection, the available bandwidth for related links has to be adjusted by subtracting the equivalent bandwidth of each admitted connection from available bandwidth. Thus, the equivalent bandwidth for each admitted connection, which is based on the error-prone traffic descriptors provided by user has to be adjusted by the overbooking factor obtained. And the adjusted available bandwidth will reflect the actual link state and hence will improve the route computation and threshold setting for the link state flooding. Cheng , Shanti, Rauf [Page 5] NEC contribution on The Notion of overbooking November 17,2000 4.3 Application of Overbook Factor on LSR Admission Control In the initial phase of MPLS network deployment the bandwidth assigned for each DiffServ service class will be allocated based on user provided traffic descriptors and the admission control process may proceed as follows: Let N be the connections already accepted within service class i. The admission control algorithm for the incoming call connection request will be proceeds as follows: Step 1: Compute the aggregated equivalent bandwidth, EQB(N+1, I), of the N+! connections based on the user provided traffic descriptors. Step 2: Let the adjusted aggregate equivalent bandwidth For the N+1 connection, EQB'(N+1)= EQB(N+1)/OBF(i); where OBF(i) is the overbooking factor for service class i. Step 3: If the available bandwidth for service call I is greater than EQB'(N+1,I, then, the (N+1)th connection request will be honored, otherwise, the request will be rejected. 5. Security Considerations This contribution aims at examining the notion of overbooking and its applications to traffic engineering and capacity planning in detail. This document discusses neither security nor authenticated mechanisms. 6. References [1] Bradner, S., "The Internet Standards Process--Revision 3", BCP 9, RFC 2026, October 1996. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [3] Awduche D., et al "A Framework for Internet Traffic Engineering", July, 2000.< draft-ietf-tewg-framework-02.txt> [4] Lai, W.S. "Capacity Engineering of IP-based Networks with MPLS", July, 2000. <draft-wlai-tewg-cap-eng-01.txt> [5] Chen, C. et al "Re-engineering ATM Network: A Measurement Approach", 3rd IEEE Symposium of Broadband Network Planning and Design, 1998. Cheng , Shanti, Rauf [Page 6] NEC contribution on The Notion of overbooking November 17,2000 7.Acknowledgments The authors would like to thank Mr. Susumu Shirasawa and S. Arao, IP Network Division,NEC NETWORKS, NEC Corporation, Japan, for his review and comments on the content and format of the contribution. 8.Author's Addresses Cheng Chen NEC America, Inc. 1525 W. Walnut Hill Lane, Irving TX 75038 Phone: (972)518-5584 Email: cchen@asl.dl.nec.com Shanti Hadvani NEC America, Inc. 1525 W. Walnut Hill Lane, Irving, TX 75038 Phone: (972)518-3628 Email: shadvani@necam.com Rauf Izmailov C&C Princeton Lab, NEC Phone: (609)9512454 Email: rauf@ccrl.nj.nec.com Full Copyright Statement "Copyright (C) The Internet Society (date). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into [1] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997 Cheng , Shanti, Rauf [Page 7]