Transcript General

MATE:
MPLS Adaptive Traffic Engineering
Anwar Elwalid Cheng Jin Steven Low Indra Widjaja
Bell Labs Michigan
altech Fujitsu
2006
Talk Outline

MPLS Traffic Engineering

Overview of MATE

Theoretical Results

Simulation Results
Best of Both Worlds

MPLS + IP form a middle ground that combines
the best of IP and the best of virtual circuit
switching technologies

ATM and Frame Relay cannot easily come to the
middle so IP has!
Label Encapsulation

MPLS – between L2 and L3

MPLS Encapsulation is specified over various
media types. Top labels may use existing format,
lower label(s) use a new “shim” label format.
Label Substitution

Have a friend go to B ahead of you using one of
the two routing techniques (hop-hop, source). At
every road they reserve a lane just for you. At
every intersection they post a big sign that says
for a given lane which way to turn and what new
lane to take.
MPLS Explicit Routing

Multiple Label-Switched Paths (LSPs) between an
ingress-egress pair can be efficiently established
The Need for Traffic Engineering

No automatic load balancing among LSPs
Design Goals

Distributed load-balancing algorithm

Need no extra network support

Minimal packet reordering required

General framework for traffic engineering

Internet Draft: draft-widjaja-mpls-mate-02.txt
Two-State Adaptive Traffic
Engineering
Functional Units in Ingress LSRs

Probe packets are sent to estimate the relative oneway mean packet delay and packet loss rate along
the LSP
Traffic Engineering Problem

For each Ingress-Egress pair s:

Input
Load: as
Set of LSPs: Ps
 Output
Offered
Vector
(an LSP p)
of traffic splits: ls
 lsp = as
Problem Formulation

Define a cost Cp , for an LSP p, as a function
of link utilization lsp

Each ingress-egress pair minimizes the sum
of the cost function of each LSP subject to a
feasible traffic split
Min C(ls) =
s.t.
 Cp (lsp)
lsp = as, lsp > 0
Understanding the Cost Function

Not necessarily a perfect cost function

Help steer network toward desirable
operating point

Allows systematic derivation and refinement
of practical traffic engineering schemes
Solution Approach

Optimality Criterion
Optimal
if paths with positive flow have
minimum (and equal) cost derivatives
 Gradient Projection Algorithm
Shift
traffic from paths with highest
derivatives to paths with lowest
derivatives by a small amount each
iteration
Asynchronous Environment

Feedback delays (probe measurements):
non-negligible
 different delays for LSPs
 time-varying
 Many ingress-egress routers shift traffic

independently
 at different times
 likely with different frequencies

Convergence under Asynchronous
Conditions



The algorithm will converge provided the cost
function satisfies certain requirements
Starting from any initial rate vector l(0), the
limit point of the sequence {l (t)} is optimal,
provided the step size is sufficiently small
Bound on step size estimates the effect of
asynchronism
Packet-level Discrete Event
Simulator

Entities: Packets, Routers, Queues, and
Links

Simulated Functional Units
Measurement and Analysis
 Traffic Engineering
 Assume traffic already filtered into bins
 Both Poisson and Long-range dependent
traffic (DAR)

Experiment Setup
Aggregate Utilization on Shared
Links
Packet Loss on Shared Links
Conclusion

MPLS Adaptive Traffic Engineering
an end-to-end solution without network
support
 distributed load-balancing
 steer networks toward “optimal”
operating point under asynchronous
network conditions
 validated in simulation
