Network Working Group Jerry Ash Internet Draft AT&T Expiration Date: May 2003 November, 2002 Max Allocation with Reservation BW Constraint Model for MPLS/DiffServ TE Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 obsoleted 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 document is intended to complement the DiffServ-aware MPLS TE (DSTE) requirements document by describing the implications of some of the criteria for selecting a default bandwidth constraint model. Properties of a candidate model called maximum allocation with reservation (MAR) are presented, and its performance analyzed, to provide guidance to the corresponding DSTE protocol extensions document for selection of the default model. Table of Contents 1. Introduction 2. Maximum Allocation with Reservation (MAR) Model 2.1 MAR Bandwidth Allocation Rules 2.2 MAR Bandwidth Allocation Parameters 3. MAR Bandwidth Allocation Performance 4. Summary 5. Security Considerations 6. Acknowledgments 7. References 8. Authors' Addresses 9. Full Copyright Statement 1. Introduction Work is currently ongoing in the Traffic Engineering Working Group to provide the capability for DiffServ-aware MPLS traffic engineering (DSTE) [DSTE-REQ, DSTE-PROTO]. A major item under discussion is the specification of bandwidth constraint models for use with DSTE. The bandwidth constraint model provides the 'rules' to support the allocation of bandwidth to individual class types (CTs). CTs are groupings of service classes in the DSTE model, which are provided separate bandwidth allocations, priorities, and QoS objectives. Several CTs can share a common bandwidth pool on an integrated, multiservice MPLS/DiffServ network. This document is intended to complement the DSTE requirements document [DSTE-REQ] by describing the properties of a candidate model called maximum allocation with reservation (MAR), and analyzing its performance, to provide guidance to the corresponding DSTE protocol extensions document [DSTE-PROTO] for selection of the default model. There is some consensus on the bandwidth constraint model objectives: 1. applies equally when preemption is either enabled or disabled (when preemption is disabled, the model still works 'reasonably' well), 2. Bandwidth efficiency, i.e., good bandwidth sharing among CTs under both normal and overload conditions, 3. bandwidth isolation, i.e., a CT cannot hog the bandwidth of another CT under overload conditions, 4. protection against QoS degradation, at least of the high-priority CTs (e.g. high-priority voice, high-priority data, etc.), and 5. reasonably simple, i.e., does not require additional IGP extensions and minimizes signaling load processing requirements. Two bandwidth constraint models are described in the DSTE requirements document: 1. maximum allocation (MA) - the maximum allowable bandwidth usage of each CT is explicitly specified 2. Russian doll (RD) - the maximum allowable bandwidth usage is done cumulatively by grouping successive CTs according to priority classes The use of any given bandwidth constraint model has significant impacts on the performance of a network, as explained later. Therefore, the criteria used to select a model must enable us to evaluate how a particular model delivers its performance, relative to other models. Lai [LAI1, LAI2] has analyzed the MA and RD models and provided valuable insights into the relative performance of these models under various network conditions. In environments where preemption is not used, the MA model is attractive because a) it is good at achieving isolation, and b) it achieves reasonable bandwidth efficiency with some QoS degradation of lower classes. When preemption is used, the RD model is attractive because it can achieve bandwidth efficiency under normal load. However, the RD model cannot provide service isolation under high load or when preemption is not used. In this draft we introduce another model called the maximum allocation with reservation (MAR) model. It is similar to the MA model in that a maximum bandwidth allocation is given to each CT. However, through the use of bandwidth reservation and protection mechanisms, CTs are allowed to exceed their bandwidth allocations under conditions of no congestion but revert to their allocated bandwidths when overload and congestion occurs. We show that the MAR model simultaneously achieves bandwidth efficiency, bandwidth isolation, and protection against QoS degradation without preemption. In Section 2 we describe the MAR bandwidth constraint model, and its operation. In Section 3, modeling analysis is presented in which MAR bandwidth allocation is shown to provide good network performance relative to full sharing models, under normal and abnormal operating conditions. A large-scale MPLS/DiffServ TE simulation model is used, in which several CTs with different priority classes share the pool of bandwidth on a multiservice, integrated voice/data network. MAR methods have also been analyzed in practice for TDM-based networks [ASH1], and in modeling studies for IP-based networks [ASH2, ASH3, E.360]. 2. Maximum Allocation with Reservation (MAR) Model In the MAR bandwidth constraint model, the bandwidth allocation control for each CT is based on estimated bandwidth needs, bandwidth use, and status of links. The LER makes needed bandwidth allocation changes, and uses [RSVP-TE], for example, to determine if link bandwidth can be allocated to a CT. Bandwidth allocated to individual CTs is protected as needed but otherwise shared. Under normal non-congested network conditions, all CTs/services fully share all available bandwidth. When congestion occurs for a particular CTi, bandwidth reservation acts to prohibit traffic from other CTs from seizing the allocated capacity for CTi. Associated with each CT are the allocated bandwidth (BWalloc) and maximum bandwidth (BWmax) parameters to govern bandwidth allocation and protection. An allowed load state (ALS) parameter controls the bandwidth allocation on individual links in a CT, based on their available bandwidth. These parameters are discussed further in the next Section. In performing MAR bandwidth allocation for a given flow, the LER first determines the egress LSR address, service-identity, and CT. The connection request is allocated an equivalent bandwidth to be routed on a particular CT. The LER then accesses the CT priority, QoS/traffic parameters, and routing table between the LER and egress LSR, and sets up the connection request using the MAR bandwidth allocation rules. The LER selects a first choice path and determines if bandwidth can be allocated on the path based on the MAR bandwidth allocation rules given in the next Section. If the first choice path has insufficient bandwidth, the LER may then try alternate paths, and again applies the MAR bandwidth allocation rules now described. 2.1 MAR Bandwidth Allocation Rules MAR bandwidth allocation is done on a per-CT basis, in which aggregated CT bandwidth is managed to meet the overall bandwidth requirements of CT service needs. Individual flows are allocated bandwidth in the corresponding CT according to CT bandwidth availability. A fundamental principle applied in MAR bandwidth allocation methods is the use of bandwidth reservation techniques. Bandwidth reservation gives preference to the preferred traffic by allowing it to seize any idle bandwidth on a link, while allowing the non-preferred traffic to only seize bandwidth if there is a minimum level of idle bandwidth available called the reserved bandwidth RBW. Burke [BUR] first analyzed bandwidth reservation behavior from the solution of the birth-death equations for the bandwidth reservation model. Burke's model showed the relative lost-traffic level for preferred traffic, which is not subject to bandwidth reservation restrictions, as compared to non-preferred traffic, which is subject to the restrictions. Bandwidth reservation protection is robust to traffic variations and provides significant dynamic protection of particular streams of traffic. It is widely used in large-scale network applications [ASH1, MUM]. Bandwidth reservation is used in two ways in MAR bandwidth allocation, first to control sharing of link bandwidth across different CTs, and second to prevent inefficient (long) routing paths from degrading network performance. On a given link, a small amount of bandwidth RBW is reserved (say 1% of the total link bandwidth), and the reserved bandwidth can be accessed when a given CT has bandwidth-in-use below its allocated bandwidth BWalloc. That is, if the available link bandwidth ABW exceeds RBW, then any CT is free to access the available bandwidth on the link. However, if ABW is less than RBW, then the CT can utilize the available bandwidth only if its current bandwidth usage is below the allocated amount BWalloc. In this way, bandwidth can be fully shared among CTs if available, but is protected by bandwidth reservation if below the reservation level. Bandwidth reservation is also used to prevent inefficient (long) routing paths from degrading network performance, which if uncontrolled can lead to network "instability" and severely reduce throughput in periods of congestion, perhaps by as much as 50 percent of the traffic-carrying capacity of a network. Bandwidth reservation is used to prevent this unstable behavior by having the preferred traffic on a link be the traffic on the primary, shortest path, and the non-preferred traffic, subjected to bandwidth reservation restrictions as described above, be the alternate-routed traffic on longer paths. In this way the alternate-routed traffic is inhibited from selecting longer alternate paths when sufficient idle trunk capacity is not available on all links of an alternate-routed connection, which is the likely condition under network and link congestion. Through the bandwidth reservation mechanism, MAR bandwidth allocation also gives preference to high-priority CTs, in comparison to normal-priority and best-effort priority CTs. Hence, bandwidth allocated to each CT is protected by bandwidth reservation methods, as needed, but otherwise shared. Each LER monitors CT bandwidth use on each CT, and determines if connection requests can be allocated to the CT bandwidth. For example, for a bandwidth request of DBW on a given flow, the LER determines the CT priority (high, normal, or best-effort), CT bandwidth-in-use, and CT bandwidth allocation thresholds, and uses these parameters to determine the allowed load state threshold (ALSi) to which capacity can be allocated. In allocating bandwidth DBW to a CT on given LSP, say A-B-E, each link in the path is checked for available bandwidth in comparison to ALSi. If bandwidth is unavailable on any link in path A-B-E, another LSP could by tried, such as A-C-D-E. Hence determination of the link load state is necessary for MAR bandwidth allocation, and three link load states are distinguished: available (non-reserved) bandwidth (ABW), reserved-bandwidth (RBW), and bandwidth-not-available (BNA). Management of CT capacity uses the link state and the ALS threshold to determine if a bandwidth allocation request can be accepted on a given CT. 2.2 MAR Bandwidth Allocation Parameters The ALS threshold is a simple function of bandwidth-in-progress, CT priority, and bandwidth allocation thresholds, as follows: Table 1 Allowed Load State (ALS) Threshold Allowed High- Normal-Priority CT Best-Effort Load Statei Priority CT --------------------------- Priority CT First Choice Alternate Path Path ------------------------------------------------------------------------ RBW If BWIPi <= If BWIPi <= Not Allowed Note 1 2 X BWmaxi BWalloci ------------------------------------------------------------------------ ABW If 2 X BWmaxi If BWalloci < If BWalloci Note 1 < BWIPi BWIPi BWIPi ------------------------------------------------------------------------ where BWIPi = bandwidth-in-progress on CT-i BWalloci = allocated (minimum guaranteed) bandwidth for CT-i BWmaxi = bandwidth allocation threshold for high-priority CTs Note 1 = allocated bandwidth BWalloc = 0; DiffServ queuing admits BE packets only if there is available bandwidth on a link The link load state definition is as follows: Table 2 Link Load State Thresholds Link Load State Condition ------------------------------------------------------------ Bandwidth-Not-Available BNA ILBWk < DBW Reserved-Bandwidth RBW ILBWk - RBWrk < DBW Available-Bandwidth ABW DBW <= ILBWk - RBWrk ------------------------------------------------------------ where ILBWk = idle link bandwidth on link k DBW = delta bandwidth requirement for a bandwidth allocation request RBWrk = reserved bandwidth for link k = .01 x TLBWk TLBWk = total link bandwidth on link k 3. MAR Bandwidth Allocation Performance Our performance analysis of MAR bandwidth allocation methods is based on a full-scale, 135-node simulation model of a national network together with a multiservice traffic demand model to study various scenarios and tradeoffs [ASH3]. Three levels of traffic priority - high, normal, and best effort -- are given across 5 CTs: normal priority voice, high priority voice, normal priority data, high priority data, and best effort data. The performance analyses for overloads and failures include a) the MAR bandwidth constraint model, as described in Section 2, and b) the full sharing bandwidth constraint model. In the full sharing bandwidth constraint model, no reservation or protection of CT bandwidth is applied, and bandwidth allocation requests are admitted if bandwidth is available. Table 3 gives performance results for a six-times overload on a single network node at Oakbrook IL. The numbers given in the table are the total network percent lost (blocked) or delayed traffic. Note that in the focused overload scenario studied here, the percent lost/delayed traffic on the Oakbrook node is much higher than the network-wide average values given. Table 3 Performance Comparison for MAR & Full Sharing Bandwidth Constraint Models 6X Focused Overload on Oakbrook (Total Network % Lost/Delayed Traffic) Class Type MAR Bandwidth Full Sharing Bandwidth Constraint Model Constraint Model ---------------------------------------------------------------------- NORMAL PRIORITY VOICE 0.16 10.83 HIGH PRIORITY VOICE 0.00 8.47 NORMAL PRIORITY DATA 3.18 12.88 HIGH PRIORITY DATA 0.00 0.46 BEST EFFORT PRIORITY DATA 12.32 9.75 ---------------------------------------------------------------------- Clearly the performance is better with MAR bandwidth allocation, and the results show that performance improves when bandwidth reservation is used. The reason for the poor performance of the full sharing model, without bandwidth reservation, is due to the lack of protection of allocated bandwidth, and the tendency to admit flows on longer paths rather than protect shorter primary paths under network congestion. Without bandwidth reservation, networks can exhibit unstable behavior in which essentially all connections are established on longer alternate paths as opposed to shorter primary paths, which greatly reduces network throughput and increases network congestion [AKI, KRU, NAK]. If we add the bandwidth reservation mechanism, then performance of the network is greatly improved. Table 4 illustrates the performance of the MAR and full sharing bandwidth constraint models for a high-day network load pattern with a 50% general overload. The numbers given in the table are the total network percent lost (blocked) or delayed traffic. Table 4 Performance Comparison for MAR & Full Sharing Bandwidth Constraint Models 50% General Overload (Total Network % Lost/Delayed Traffic) Class Type MAR Bandwidth Full Sharing Bandwidth Constraint Model Constraint Model ---------------------------------------------------------------------- NORMAL PRIORITY VOICE 0.03 2.00 HIGH PRIORITY VOICE 0.00 2.41 NORMAL PRIORITY DATA 0.01 1.90 HIGH PRIORITY DATA 0.00 2.04 BEST EFFORT PRIORITY DATA 11.15 24.95 ---------------------------------------------------------------------- Again, we can see the performance is always better when MAR bandwidth allocation and reservation is used, including the best effort traffic. Lai's results [LAI1, LAI2] show the trade-off between bandwidth sharing and service protection/isolation, using an analytic model of a single link. He shows that the RD model has a higher degree of sharing than the MA model. Furthermore, for a single link, the overall loss probability is the smallest under full sharing and largest under MA, with the RD model being intermediate. Hence, on a single link, Lai shows that the full sharing model yields the highest link efficiency and MA model the lowest, and that full sharing has the poorest service protection capability. The results of the present study show that when considering a network context, in which there are many links and multiple-link routing paths are used, full sharing does not necessarily lead to maximum network-wide bandwidth efficiency. In fact, the results in Table 2 show that the full sharing model not only degrades total network throughput, but also degrades the performance of every CT. Allowing more bandwidth sharing may improve performance up to a point, but can severely degrade performance if care is not taken to protect allocated bandwidth under congestion. Both Lai's study and this study show that increasing the degree of bandwidth sharing among the different CTs leads to a tighter coupling between CTs. Under normal loading conditions, there is adequate capacity for each CT, which minimizes the effect of such coupling. Under overload conditions, when there is a scarcity of capacity, such coupling can cause severe degradation of service, especially for the lower priority CTs. Thus, the objective of maximizing efficient bandwidth usage, as stated in bandwidth constraint model objectives, must be exercised with care. Due consideration needs to be given also to achieving bandwidth isolation under overload, in order to minimize the effect of interactions among the different CTs. The proper tradeoff of bandwidth sharing and bandwidth isolation needs to be achieved in the selection of a default bandwidth constraint model. Bandwidth reservation supports greater efficiency in bandwidth sharing while still providing bandwidth isolation and protection against QoS degradation. 4. Summary The proposed MAR bandwidth constraint model includes the following: a) allocate bandwidth to individual CTs, b) protect allocated bandwidth by bandwidth reservation methods, as needed, but otherwise fully share bandwidth, c) differentiate high-priority, normal-priority, and best-effort priority services, and d) provide admission control to reject connection requests when needed to meet performance objectives. In the modeling results, the MAR bandwidth constraint model compares favorably with methods that permit more bandwidth sharing. In particular, some of the conclusions from the modeling are as follows: 1. MAR bandwidth allocation is effective in improving performance over methods that lack bandwidth protection and allow more bandwidth sharing under congestion, 2. MAR achieves service differentiation for high-priority, normal-priority, and best-effort priority services, 3. bandwidth reservation supports greater efficiency in bandwidth sharing while still providing bandwidth isolation and protection against QoS degradation, and is critical to stable and efficient network performance. 5. Security Considerations No new security considerations are raised by this document, they are the same as in the DSTE requirements document [DSTE-REQ]. 6. Acknowledgements I would like to thank Wai Sum Lai for his support and review of this draft. 7. References [AKI] Akinpelu, J. M., The Overload Performance of Engineered Networks with Nonhierarchical & Hierarchical Routing, BSTJ, Vol. 63, 1984. [ASH1] Ash, G. R., Dynamic Routing in Telecommunications Networks, McGraw-Hill, 1998. [ASH2] Ash, G. R., et. al., Routing Evolution in Multiservice Integrated Voice/Data Networks, Proceeding of ITC-16, Edinburgh, June 1999. [ASH3] Ash, G. R., Traffic Engineering & QoS Methods for IP-, ATM-, & TDM-Based Multiservice Networks, work in progress. [BUR] Burke, P. J., Blocking Probabilities Associated with Directional Reservation, unpublished memorandum, 1961. [E.360] ITU-T Recommendations, QoS Routing & Related Traffic Engineering Methods for Multiservice TDM-, ATM-, & IP-Based Networks. [DIFF-MPLS] Le Faucheur, F., et. al., "MPLS Support of Diff-Serv", RFC 3270, May 2002. [DSTE-REQ] Le Faucheur, F., et. al., "Requirements for support of Diff-Serv-aware MPLS Traffic Engineering," work in progress. [DSTE-PROTO] Le Faucheur, F., et. al., "Protocol extensions for support of Diff-Serv-aware MPLS Traffic Engineering," work in progress. [DIFFSERV] Blake, S., et. al., "An Architecture for Differentiated Services", RFC 2475, December 1998. [KEY] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. [KRU] Krupp, R. S., Stabilization of Alternate Routing Networks, Proceedings of ICC, Philadelphia, 1982. [LAI1] Lai, W., Bandwidth Constraint Models for Diffserv-aware MPLS Traffic Engineering , work in progress. [LAI2] Lai, W., Traffic Engineering for MPLS, Internet Performance and Control of Network Systems III Conference, SPIE Proceedings Vol. 4865, pp. 256-267, Boston, Massachusetts, USA, 29 July-1 August 2002 (http://www.columbia.edu/~ffl5/waisum/bcmodel.pdf). [MUM] Mummert, V. S., Network Management and Its Implementation on the No. 4ESS, International Switching Symposium, Japan, 1976. [NAK] Nakagome, Y., Mori, H., Flexible Routing in the Global Communication Network, Proceedings of ITC-7, Stockholm, 1973. [MPLS-ARCH] Rosen, E., et. al., "Multiprotocol Label Switching Architecture," RFC 3031, January 2001. [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. [RSVP-TE] Awduche, D., et. al., "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001. 8. Authors' Addresses Jerry Ash AT&T Room MT D5-2A01 200 Laurel Avenue Middletown, NJ 07748, USA Phone: +1 732-420-4578 Email: gash@att.com 9. Full Copyright Statement Copyright (C) The Internet Society (1998). 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 languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.