Internet DRAFT - draft-cchen-te-overbooking
draft-cchen-te-overbooking
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]
