Network Working Group Yufei Wang (Photuris)
Internet Draft Leah Zhang (Photuris)
Expiration Date: December 2001
June 2001
A Scalable and Hybrid IP Network Traffic Engineering Approach
draft-wang-te-hybrid-approach-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. 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/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
Currently a common approach to IP network traffic engineering is
the overlay approach where explicit end to end MPLS LSPs between all
possible edge nodes are established to form a full mesh virtual network
on top of the physical topology. By carefully choosing the routes for
these LSPs, one can completely control how traffic flows across the
network and therefore achieve any given traffic engineering objective.
However scalability is a serious concern with this approach because it
requires N square number of LSPs where N is the number of nodes.
WAng, Y. & Zhang, L. [Page 1]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
A recent research [1] proposes a scalable traffic engineering method
by optimizing the IGP link weights and shows that theoretically the
native shortest path routing (OSPF or IS-IS) under appropriate link
weight setting matches the performance of the overlay approach exactly.
But this theoretical result faces two major practical problems. One is
that it only applies to static traffic engineering as link weights
cannot be changed too often due to IGP slow convergence. The other is
that it may need to split traffic across multiple equal cost shortest
paths if any, in unequal proportions and currently OSPF only supports
equal splitting. We are proposing a new approach called the hybrid
approach which relies on both IGP link weight setting and MPLS LSPs.
The hybrid approach retains the scalability of the link weight method
and at the same time eliminates the two practical problems of it.
The basic idea of this new approach is to rely on IP native routing
(OSPF, IS-IS) for most part of the network and to use MPLS LSPs for
load balancing at some locations only when necessary. The new approach
achieves the exact performance of the overlay approach without
the associated complexity.
Introduction
Traffic engineering is concerned with the problem of how to optimally
map traffic flows onto the network topology so that network resources
are best utilized and network congestions are minimized or completely
eliminated [2]. If the traffic matrix (end to end bandwidth
requirement, each individual requirement is called a demand) and
network bandwidth are given, the traffic engineering problem can be
modeled as a mathematical problem called multi-commodity network
flows [3] which can then be solved easily by some very efficient
algorithms such as the simplex method [4]. The solution of this
mathematical model provides the optimal set of end to end routes,
one for each demand. Therefore how to determine the optimal
routes is not a problem at all. But how to implement these routes in
real world IP networks is the concern. This draft addresses precisely
this concern.
WAng, Y. & Zhang, L. [Page 2]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
One straightforward implementation is to set up an explicit LSP for
each of these routes so that each demand will follow its respective
optimal routing exactly. This is the overlay approach. The concern
with this approach is that it does not scale because it requires
N square number of LSPs where N is the number of nodes. And even
worse, N square may not be enough because sometimes a demand needs to
be split between multiple routes. In other words, it is possible that
the optimal routing provides multiple optimal paths between a pair of
end nodes and the traffic between them needs to be split across these
paths according to the optimal proportions (which are also determined
by the solution of the mathematical model). In such cases multiple LSPs
should be set up between these two nodes for load splitting. It should
be pointed out that although from network topology point of view there
may be many alternative paths connecting two end nodes, not all of them
need to necessarily be chosen as optimal paths for traffic engineering
purpose. Normally the possibilities of traffic splitting between
multiple optimal paths may be far less than those suggested by
topological connectivity.
The overlay approach seems to be the only viable approach even with
its scalability concern until very recently when a research paper [1]
observes that the optimal routes are always the shortest paths with
respect to an appropriate set of positive link weights and proposes
a new approach which relies on the IP native shortest path routing
(OSPF, IS-IS). The new approach controls how traffic moves cross
the network by making the desirable routes the shortest paths through
optimal link weight setting. The paper also observes that the optimal
link weights are actually provided by the optimal solution of the
mathematical model as a by-product. This theoretical result may provide
us some valuable insight into the traffic engineering capabilities of
shortest path routing.
However the proposed IGP link weight setting method does have its
practical limitations. One major issue is that it only applies to
static traffic engineering as link weights cannot be changed too
often to respond to traffic pattern changes in real time due to IGP
slow convergence. Another issue is that it may need to split traffic
WAng, Y. & Zhang, L. [Page 3]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
across multiple equal cost shortest paths if any, in unequal
proportions, while current IGP protocols only support equal
splitting. Regarding the first issue, one may argue that the link
weight method can be used for long-term statistical traffic
engineering where traffic volumes are measured as statistical
averages and that this method is not designed for handling traffic
fluctuations in real time. But the second issue indeed limits
the possibility that this method can be implemented in real networks
today because IGP protocols do not support arbitrary load splitting. It
is possible that we implement the link weight method by only doing equal
load splitting even though the optimal routing requires unequal
distributions. But another research [5] shows that the performance of
equal splitting only traffic engineering can deviate from that of the
optimal solution significantly, at least for some worst cases.
It is interesting to notice that traffic splitting across multiple
optimal paths between two nodes for the overlay approach and traffic
splitting across multiple equal cost shortest paths between the same
node pair for the link weight approach are identical. The multiple
optimal paths in the overlay approach are precisely turned into multiple
equal cost shortest paths by properly setting the link weights in the
link weight approach. So no matter which implementation approach we take,
we all implement the optimal traffic engineering routing and we all
face the unequal traffic splitting problem. In todayÆs technology,
unequal splitting among multiple MPLS LSPs is readily supported [6,7].
When setting up each LSP, one can specify its (virtual) bandwidth,
and traffic can be split across multiple LSPs in proportion to
their bandwidth ratios. This capability of LSPs motivates us to
propose a new approach called the hybrid approach which relies on
both IGP link weights and MPLS LSPs. The hybrid approach retains
the advantages of IGP link weights method while eliminates its
shortcomings.
To avoid ambiguity, throughout this paper, all traffic (demands),
links, and LSPs are assumed unidirectional, even though we do not
explicit mentioning directionality. In the illustrated examples,
the direction is always assumed to go from left to right. We use
the term optimal routing to refer to the optimal solution of
WAng, Y. & Zhang, L. [Page 4]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
the mathematical traffic enginerring model. But the term optimal
routing can also refer to any desirable set of routes designed by
a carrier which may not be necessarily mathematical optimal
but are prefered to be implemented for some practical reasons. This
draft is about a new approach to the implementation of such routing
scheme. Whether the routing is realy optimal or not does not make
any difference to our approach because research [1] shows that even
a non-optimal set of routes can also be reproduced as shortest paths
as long as they are not loopy.
The Hybrid Approach
In this approach we rely on optimal IGP shortest path routing to
route most of traffic and only use LSPs to do the necessary traffic
splitting. We would like to make the following observations. First,
not every demand needs to be split for optimal routing. Second, even
a demand indeed needs to be split, the section of the split routing
(which is called load balance section from now on) does not necessarily
span the entire path from the source node to the destination node.
Third, many different demands may share the same load balance section.
As an example, the third observation of common load balance section is
illustrated in figure 1, where many demands (A to I, A to J, B to I,
C to H, etc.) share the common load balance section that goes
between D and G.
A E I
\ /,,\ /
\ /, ,\ /
\ /, LSP1 ,\ /
C ---- D : : G ----- H
/ \` LSP2 ` / \
/ \` ` / \
/ \` / \
B F J
Figure 1
WAng, Y. & Zhang, L. [Page 5]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
In order to reduce number of LSPs required, we donÆt set up an
LSP for every demand that requires splitting. We aggregate splitting.
That is, different demands which share the same load balance section
are aggregated and LSPs are set up only between the two end points of
the load balance section where traffic flows actually start to diverge
to difference paths and where they converge back to one path,
not between the source node and the destination node of each individual
demand. As illustrated in figure 1, only two LSPs need to be setup
for the common load balance section between D and G, LSP1 and LSP2.
LSP1 goes from D via E to G and LSP2 goes from D via F to G. All demands
which share this load balance section D-G (e.g. demands A to I, A to J,
B to I, C to H, etc.) are aggregated between D and G and are load
balanced uniformly by these two LSPs.
So the basic idea of the hybrid approach is to set up LSPs for all load
balance sections for traffic splitting. These LSPs are viewed as virtual
links (express paths) between the head end and the tail end of a load
balance section. They are advertised into IGP as forwarding adjacencies
(FA) [8] between the head end and the tail end. The LSPs are assigned
weights that are the sum of the weights of the links on their paths.
So the LSPs are also on the shortest path routing and carry the same
total weight as their respective original paths. The routers can be
configured [8] such that the LSPs (FAs) are preferred over the original
links. In addition, these LSPs are assigned bandwidths that represent
the proportions of the optimal traffic splitting and traffic is split
across LSPs according to their bandwidths [6,7]. Therefore traffic will
be split at the load balance section across multiple LSPs in proportion
to the bandwidth ratios of these LSPs which will be then identical to
the optimal traffic split ratios.
The number of LSPs required by this approach normally should be far less
than the overlay approach because of the following reasons. First, the
percentage of demands that need splitting for optimal routing is usually
very small. As discussed previously, even though the topological
WAng, Y. & Zhang, L. [Page 6]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
connectivity may offer many alternative paths between a source node
and a destination node, only one or very few of them may be selected
as optimal paths. Second, the ôsplitting aggregationö further reduces
the LSP needs to per load balance segment from per individual demands.
We use the example in figure 1 to demonstrate how scalable this hybrid
approach is. In figure 1, all the demands that go from node set {A,B,C,D}
to node set {G,H,I,J} need to traverse the load balance section D-G.
There are a total of 16 such demands (A-G, A-H, A-I, A-J,
B-G, B-H, B-I, B-J, etc.). If all of them need to be split between D and G,
the overlay approach will need to set up a total of 32 end to end LSPs,
two for each demand. Even if some of the demands only take one of the
two paths between D-G without load balancing, we still need a minimum
of 16 LSPs. But in the hybrid approach we only need 2 LSPs.
And the performances of the two approaches are identical. Both follow the
optimal routing exactly.
To summarize, the procedure of the hybrid approach is as follows.
1. Solve the mathematical model (just as the link weight setting
method) to find the optimal solution, if the solution is not given.
2. Derive the following information from the optimal solution: a) The
optimal set of link weights, b) All the load balance sections,
and c) The aggregated traffic split proportions for each load
balance sections.
3. Set the links to the optimal link weights
4. Set up traffic split LSPs for each load balance section. Set
the weights of the LSPs as the sum of the link weights of their
respective paths. Set their bandwidths to the optimal aggregated
traffic split proportions. Advertise these LSPs as forwarding
adjacencies into IGP [8] and make LSPs the preferred paths over
the native IGP paths [6] [7].
5. IGP will compute the optimal shortest path routing. Traffic will
follow the IGP shortest path routing and only at the load balance
sections will diverge to appropriate LSPs to achieve the optimal
load balancing.
WAng, Y. & Zhang, L. [Page 7]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
Load Balance Sections and their Scope
Since in the hybrid approach we only establish LSPs for load balance
sections, the concept of load balance section is a key concept and we
would like to offer a thorough description of it. We first give a
precise definition of load balances section and then provide an
investigation of load balance scopes for nested load balance sections.
A load balance section with respect to a given optimal routing consists
of two nodes, one is called the head end and one is called the tail end,
and two or more paths called LB (Load Balance) paths between the head
end and the tail end such that:
¸ All of the LB paths are optimal shortest paths,
¸ LB paths diverge at the head end and converge at the tail end,
and
¸ LB paths never come back together at any point in between.
Again using the example in figure 1, D-G is a load balance section but
C-H is not. Although C-H also has multiple optimal paths, the paths
do not diverge at C nor converge at H. A load balance section is a
property of an optimal routing as a whole, but not a property of the
routing of an individual demand. It is shared by all the demands
whose optimal paths traverse the section.
D
/ \
/ \
C/ \G
/ \ / \
/ \ / \
A-----B/ \ / \H--------I
\ E /
\ /
\ /
\ /
\ /
\ /
F
Figure 2
WAng, Y. & Zhang, L. [Page 8]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
Load balance sections can be nested one inside another. The example
in figure 2 has two load balance sections, B-H and C-G, where C-G is
inside B-H. Obviously any optimal paths between C-G are also on the
optimal paths between B-H. There are three optimal paths between B-H.
Therefore we need to set up three LSPs for B-H, LSP1, LSP2, and LSP3
(not shown). The first two LSPs, LSP1 (B-C-D-G-H) and LSP2 (B-C-E-G-H)
also traverse load balance section C-G. The third LSP, LSP3, takes the
bottom route (B-F-H). The bandwidths for these three LSPs are set
according to the optimal routing specifications on how the aggregated
traffic between B-H should be split. Since for load balance section C-G,
there are only two optimal paths, we need only set up two LSPs, LSP4
(C-D-G) and LSP5 (C-E-G), between C-G (not shown). Similarly the
bandwidths for LSP4 and LSP5 are set according to the optimal routing
specifications on how the aggregated traffic between C-G should be
split. Please note that here the aggregated traffic for C-G does not
include the portion of the aggregated traffic for B-H which flows
through LSP1 and LSP2.
It can been seen that the LSPs for C-G are only responsible for load
balancing "local" traffic, or more specifically, demands between
nodes B-G, C-G, and C-H. The balancing of "through" traffic is taken
care of by two of the LSPs for the outer load balance section B-H, LSP1
and LSP2. The advantage of this separation is that the impact of any
changes to a nested load balance section may only be limited to local
traffic and may not affect its outer load balance sections. The downside
is of course that it may be desirable sometimes that a load balance
section should be able to balance all the traffic flowing through it,
not just local traffic. Unfortunately the current technology does not
support the latter option, even though the optimal routing solution
provides traffic split ratios for either way.
Dynamic Load Balancing
In addition to its scalability, another benefit of this approach is
that it not only can handle static traffic patterns, but also can
address traffic changes dynamically. The key for this capability is
the rapid reconfigurability of LSPs' bandwidth.
WAng, Y. & Zhang, L. [Page 9]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
The original LSP bandwidth is set according to the optimal split
proportions of the optimal routing. The optimal routing is the
solution of the mathematical traffic engineering model which is
formed based on static traffic or statistical average traffic. The
actual traffic flowing across the network may deviate from this
ôassumedö traffic pattern from time to time. Therefore it would be
desirable if the approach can modify its way of directing traffic flows
in response to traffic fluctuations rapidly or in real time.
Fortunately this hybrid approach can handle traffic changes in a quick
and easy way. When load level disparity among the constituent links
of LSPs of a load balance section is detected, the bandwidths of
these LSPs can be adjusted to make the load levels more even.
In RSVP-TE [9], we can use the shared reservation style to setup
a new LSP with the adjusted bandwidth to replace the old LSP with
the old bandwidth gracefully. The time this process takes is usually
very short.
Two clarifications should be made with this dynamic load balance
feature. First, the changes in the aggregated traffic to be split
across a load balance section are not the reason for the modification
of LSP bandwidth ratios because all the LSPs at the load balance
section are designed to share the load of the same traffic. The traffic
volume scale up or scale down should not affect the percentages of
their shares. What triggers the modification is the uneven load
changes of individual links of the load balance sections caused by
traffic in other directions. In the example of figure 1, what may
cause bandwidth adjustments to LSP1 and LSP2 are the possible changes
of traffic between nodes D and E, or E and G, or D and F,
or F and G, or E and F, but not the aggregated traffic between D
and G. Second, this reconfiguration still stays within the optimal
routing pattern. If the traffic changes so drastically that load
balance ratio adjustments can no longer handle, we have to re-compute
a new set of optimal routes based on a new assumed traffic pattern.
But hopefully this global re-optimization does not need to be done
too often for at least two reasons. First, carriers desire route
stability and even though routing needs to be changed to reflect
new traffic, changes should be made gradually in a controlled fashion,
not drastically in every minute. Second, technically the IGP
protocols take time to converge and do not allow real time link
weight changes either.
WAng, Y. & Zhang, L. [Page 10]
Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001
Security Considerations
This document raises no new security concerns for IP network traffic
engineering.
References
[1] Yufei Wang, Zheng Wang, Leah Zhang, "Internet traffic engineering
without full mesh overlaying," Proceedings of INFOCOM'2001, April 2001.
[2] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus,
"Requirements for traffic engineering over MPLS," RFC2702, September 1999.
[3] Yufei Wang and Zheng Wang, "Explicit routing algorithms for internet
traffic engineering," Proceedings of ICCCN'99, September 1999.
[4] R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993.
[5] B. Fortz and M. Thorup, "Internet traffic engineering by optimizing
ospf weights," Proceedings of INFOCOM'2000, March 2000.
[6] Cisco IOS. http://www.cisco.com/univercd/cc/td/doc/product/software/
ios120/120newft/120t/120t7/te120_7t.htm
[7] Juniper JUNOS. http://www.juniper.net/
[8] K. Kompella and Y. Rehkter, "LSP hierarchy with MPLS TE," Internet
Draft, draft-ietf-mpls-lsp-hierarchy-02.txt, February 2001.
[9] D. Awduche, et.al, "RSVP-TE: Extensions to RSVP for LSP tunnels,"
Internet Draft, draft-ietf-mpls-rsvp-lsp-tunnel-08.txt, February 2001.
Author Information
Yufei Wang
20 Corporate Place South
Piscateway, NJ 08854
Phone: +1 732-465-1000, x1258
Email: ywang@photuris.com
Leah Zhang
20 Corporate Place South
Piscateway, NJ 08854
Phone: +1 732-465-1000, x1252
Email: lzhang@photuris.com