Transcript A Fair and Dynamic Load Balancing Mechanism F. Larroca and J.L.

Dynamic Traffic
Engineering Techniques
for the Internet
Federico Larroca
Supervisor: Jean-Louis Rougier
December 18th 2009
Introduction
 Traffic
Engineering has regained the research
community interest. Why?
• Increasing complexity and dynamicity of traffic
-
(new) Services convergence
External routing modifications
Large-volume network attacks
Flash crowds
Equipment failures
• Blind overprovisioning still a viable solution?
- Ever increasing access rates (e.g. FTTH)
- New architectures with intrinsically scarce resources (e.g. Wireless)
- Greedy and irresponsible waste of resources with non-negligible
environmental impact
page 1
Dynamic Traffic Engineering
Federico Larroca
Introduction
 Network
•
•
•
•
Operators in need of TE techniques:
Robust with respect to changes in traffic demands
Tolerant to node/link failures
Efficient in the use of resources
Automatic so as to ease network management
 Answer:
Dynamic Load-Balancing
• Each Origin-Destination (OD) pair connected by
several pre-established paths
• How to distribute traffic among paths so as to
optimize a certain objective function?
• On-line adaptation: function is “always” optimized
page 2
Dynamic Traffic Engineering
Federico Larroca
Introduction
 Example:
Minimizing the maximum link utilization
Intranet
page 3
Dynamic Traffic Engineering
Federico Larroca
Contributions of the Thesis
 Resulting
performance clearly depends on the objective
function. How to choose it?
• Which performs better out of the previously proposed
ones?
• Are they the only possibilities?
 How may the optimum be attained?
• To avoid oscillations, previously proposed algorithms are
conservatively slow
• Is there a way to adapt convergence speed on-line?
 Alternatives to Dynamic Load-Balancing?
• Which one is better? In which case?
page 4
Dynamic Traffic Engineering
Federico Larroca
Agenda
Introduction
Objective
Function
Attaining
the Optimum
Evaluation
Conclusions
page 5
Dynamic Traffic Engineering
and Future Work
Federico Larroca
(Brief) Notation
 l=1,..,L
: links (cl is its capacity)
 s=1,..,S : OD pairs (or commodities)
 ds : traffic demand (amount from origin to destination)
 Psi : one path of OD pair s (i=1,..,ns)
 dP : amount of traffic sent along Psi
si
• ∑ dPsi = ds
• dPsi ≥ 0
 d : the vector of dP ’s
si
 ρl : load on link l
page 6
Dynamic Traffic Engineering
Federico Larroca
Objective Function I
 Link
Utilization (ul)
ul 
l
cl
A
Link Utilization ul close to 1.0 means a link operating
near its capacity
 To support sudden increases in traffic and link/node
failures: Keep it as low as possible!
min
d
page 7
Dynamic Traffic Engineering
max ul
l 1,.., L
Federico Larroca
Objective Function II
 Path
Available Bandwidth (ABWP)
ABWP  min ABWl   min cl  l 
lP
lP
 Twofold
path performance indicator:
• Rough estimation of TCP rate on path P (current
conditions)
• How much extra traffic supports path P (prudence)
 How should ABWP be distributed among paths?
• Idea: draw on Congestion Control ideas
max
d
page 8
  d U  ABW 
Dynamic Traffic Engineering
s PPs
P
Federico Larroca
P
Objective Function III
Congestion (Cl (l))
• Cl (l) (non-decreasing and continuous) measures the
congestion on link l
 Use what as Cl (l )? The mean queuing delay (Dl (l))
• Simplicity: total path queuing delay DP = ∑ Dl (l)
• Versatility
 Link
- Streaming traffic: bigger queuing delays mean more delay and jitter
- Elastic traffic: bigger queuing delays mean bottlenecked flows
S
min
d
page 9
 d
s 1 PPs
P
L
L
l 1
l 1
DP  Dl l l   f l l 
Dynamic Traffic Engineering
Federico Larroca
Classic Objective Function III
 Anyway,
use what as the mean queue size fl (l )?
• Typical answer: assume a queuing model (e.g. M/M/1)
• Unrealistic and arbitrary choice!
 Idea: why not learn it from
measurements?
 Complications
• Robustness of the estimation
• Estimated fl (l ) still convex
continuous and non-decreasing
 Solution:
• Convex Nonparametric Weighted Least Squares (CNWLS)
page 10
Dynamic Traffic Engineering
Federico Larroca
Agenda
Introduction
Objective
Function
Attaining
the Optimum
Evaluation
Conclusions
page 11
Dynamic Traffic Engineering
and Future Work
Federico Larroca
Converging to the Optimum
 Necessary
(and sufficient) condition of the optimum d*
• Equilibrium of greedy OD pairs minimizing a certain path
cost function fP (Wardrop Equilibrium)
'
• E.g. Minimum-Congestion fP   f l ( l )
lP
 New
Question
• Given fP, how may we convergence to the Wardrop
Equilibrium (WE) ?
 Possible answer: all OD pairs use a no-regret algorithm
 Intuitively:
• The mean extra cost incurred by not having used ONLY
the cheapest path (regret) is bounded by zero
page 12
Dynamic Traffic Engineering
Federico Larroca
The Algorithm: iAWM
 Our choice:
LtPsi  0 i  1,.., ns
Incrementally Adaptive Weighted Majority
The path’s regret (measures
how bad it performed)
for t  1,..,  do
Receive the path cost fPt si i  1,.., ns
t 1
s
W 
t 1
Psi
L  min L
i 1,.., ns
t
s
1
log ns 
  min  , 2 t 1 
Ls 
4
1
ts 
1   st
  
i 1,.., ns
 Pt  

t 1
t  LPsi
s
t 1
t  LPsi
s
t
s
si
Simple: best paths route
more traffic
Wst
i  1,.., ns
Adjust the demand vector : d Pt si   Pt si d s i  1,.., ns
Receive the outcome yst
Update the paths regret : LtPsi  LtPsi1  yst  fPt si i  1,.., ns
Regret: accumulated
Controls the speed.
difference with outcome yts
Self-regulated based
on the best regret!!
end for
t
t
y

min
f
 It works with y  f . In particular we used s i 1,.., n Psi
s
t
s
page 13
t
Psi
Dynamic Traffic Engineering
Federico Larroca
A Flow-Level Simulation
 Real
 We
page 14
Network with real TMs (one every 5 min.)
apply iAWM every 1 min.
Dynamic Traffic Engineering
Federico Larroca
A Simulation
 Results
for the Minimum-Congestion Load-Balancing
Very Bad!
 What’s
 iAWM-R
•
When a suspicious situation
occurs for a certain number of
consecutive times: Reset!
LtPsi  0 i  1,.., ns
•
•
One of the paths has a very
bad history (very big regret LtP)
When in an anomalous
situation history should be
ignored: iAWM-R
Excellent!
page 15
Dynamic Traffic Engineering
wrong?
Federico Larroca
Agenda
Introduction
Objective
Function
Attaining
the Optimum
Evaluation
• The three objective functions
• The cost of an arbitrary choice
• A comparison with Robust Routing
Conclusions
page 16
Dynamic Traffic Engineering
and Future Work
Federico Larroca
The Three Objective Functions

min umax : MinMaxU (Minimum Maximum Utilization)

max
d
d
 d
s PPs
P
log  ABWP  : MaxU (Maximum Utility)
L

min
d
 f   : MinQ (Minimum Queue)
l 1
l
l
How do they perform?
• Link Utilization (ul)
• Path Available Bandwidth (ABWP)
• Total Mean Congestion (∑fl(ρl))
page 17
Dynamic Traffic Engineering
Federico Larroca
Results in Abilene
each Objective
Function
and for(u
each
TM, repeatedly
Link
Utilization
l)
apply iAWM-R
for the corresponding fP MinMaxU
until convergence
MinMaxU - MinQ
- MaxU
 For
Conclusions: • MinMaxU performs only slightly better
• MinQ and MaxU perform very similarly
page 18
Dynamic Traffic Engineering
Federico Larroca
Results in Abilene
Path Available Bandwidth (ABWP)
MaxU / MinMaxU
MaxU / MinQ
Conclusions: • MaxU outperforms MinMaxU
• MinQ and MaxU perform very similarly
page 19
Dynamic Traffic Engineering
Federico Larroca
Results in Abilene
Total Mean Congestion ( ∑fl(ρl) )
(MaxU or MinMaxU) / MinQ
Conclusion:
page 20
• MinQ outperforms MinMaxU and MaxU
Dynamic Traffic Engineering
Federico Larroca
Agenda
Introduction
Objective
Function
Attaining
the Optimum
Evaluation
• The three objective functions
• The cost of an arbitrary choice
• A comparison with Robust Routing
Conclusions
page 21
Dynamic Traffic Engineering
and Future Work
Federico Larroca
Results in Abilene
happens when
use the M/M/1
Link we
Utilization
(ul)instead of our
regression?
What is the impact?
MinMaxU - MinQ(CNWLS)
MinMaxU - MinQ(M/M/1)
 For each Objective Function and for each TM, repeatedly
apply iAWM-R for the corresponding “estimation” of fl (l )
(CNWLS or M/M/1) until convergence
 What
Conclusion:
page 22
• The precise choice of fl (l ) is not significant
Dynamic Traffic Engineering
Federico Larroca
Results in Abilene
Total Mean Congestion ( ∑fl(ρl) )
MinQ(M/M/1) / MinQ(CNWLS)
Conclusion:
page 23
• M/M/1 obtains very poor results
Dynamic Traffic Engineering
Federico Larroca
Agenda
Introduction
Objective
Function
Attaining
the Optimum
Evaluation
• The three objective functions
• The cost of an arbitrary choice
• A comparison with Robust Routing
Conclusions
page 24
Dynamic Traffic Engineering
and Future Work
Federico Larroca
Robust Routing
 Robust
Routing
• Unique routing configuration for all possible traffic
matrices in some uncertainty set X
• Uncertainty set:
- Largest values of links load previously seen
- A set of previously observed TMs
• Objective: Optimize worst-case performance
min max
d X
page 25
Dynamic Traffic Engineering
 l 
l
max    
l
 cl  l cl
Federico Larroca
DLB vs RR
Case 1 – Normal operation
Maximum Link Utilization
Total Mean Congestion
Conclusions: • DLB and RR perform similarly
• Under normal operation RR is enough
page 26
Dynamic Traffic Engineering
Federico Larroca
DLB vs RR
Case 2 – TM outside X
Maximum Link Utilization
Total Mean Congestion
Conclusion: • If the traffic demand is outside the uncertainty
set the obtained performance in RR is very poor
• DLB obtains very good results
page 27
Dynamic Traffic Engineering
Federico Larroca
DLB vs RR
Case 3 – Big X
Maximum Link Utilization
Total Mean Congestion
Conclusion: • If the uncertainty set is too big, the obtained
performance for a particular demand may be poor
page 28
Dynamic Traffic Engineering
Federico Larroca
Agenda
Introduction
Objective
Function
Attaining
the Optimum
Evaluation
• The three objective functions
• The cost of an arbitrary choice
• A comparison with Robust Routing
Conclusions
page 29
Dynamic Traffic Engineering
and Future Work
Federico Larroca
Conclusions
 Which
is the best objective function?
• MinQ ( min ∑fl(ρl) )
 How
may the optimum be attained? Is there a way to
adapt convergence speed on-line?
• Yes! No-Regret Algorithms
• Very fast and stable
 Alternatives to Dynamic Load-Balancing?
• RR is adequate if no anomalies
• Else, some form of dynamism is needed!
• Traffic and Topology Uncertainty??
page 30
Dynamic Traffic Engineering
Federico Larroca
Future Work
 Wireless
Mediums
• What is the best objective function?
• No-Regret algorithms for on-line adaptation (e.g. power
control)
 Extending DLB to a pure-IP architecture
• Multi-Topology routing? (problem: choosing the logical
topologies)
 Future Internet: multi-homing and LISP (Locator/ID
Separator Protocol) will generalize multi-path
• How should load-balancing be performed?
page 31
Dynamic Traffic Engineering
Federico Larroca
Publications










Pedro Casas, Federico Larroca, Jean-Louis Rougier and Sandrine Vaton, “Comparative Study and New Directions of
Traffic Engineering Techniques for Dynamic Traffic,” submitted for fast-tracking in Computer Communications (COMCOM)
Journal (Elsevier).
Federico Larroca and Jean-Louis Rougier, “Minimum delay load-balancing via nonparametric regression and no-regret
algorithms,” submitted to IEEE/ACM Transactions on Networking.
Pedro Casas, Federico Larroca, Jean-Louis Rougier and Sandrine Vaton, “Robust Routing vs Dynamic Load- Balancing: A
Comprehensive Study and New Directions" in proceedings of the 7th International Workshop on the Design of Reliable
Communication Networks (DRCN 2009). Washington D.C., USA, October 2009.
Pedro Casas, Federico Larroca and Sandrine Vaton, “Robust Routing Mechanisms for Intradomain Traffic Engineering in
Dynamic Networks" in proceedings of IEEE/IFIP 6th Latin American Network Operations and Management Symposium
(LANOMS 2009). Punta del Este, Uruguay, October 2009.
Federico Larroca and Jean-Louis Rougier, “Robust Regression for Minimum-Delay Load-Balancing" in proceedings of the
21st International Teletraffic Congress (ITC 21). Paris, France, September 2009.
Federico Larroca and Jean-Louis Rougier, “Routing Games for Traffic Engineering" in proceedings of the IEEE
International conference on Communications (ICC 2009). Dresden, Germany, June 2009.
Federico Larroca and Jean-Louis Rougier, “Minimum-Delay Load-Balancing Through Non-Parametric Regression" in
proceedings of the 8th International IFIP-TC 6 Networking Conference (NETWORKING ‘09). Aachen, Germany, May 2009.
Federico Larroca and Jean-Louis Rougier, “A Fair and Dynamic Load-Balancing Mechanism" in proceedings of the
International Workshop on Traffic Management and Traffic Engineering for the Future Internet (FITraMEn 08). Porto,
Portugal, December 2008. Selected to appear on Traffic Management and Traffi Engineering for the Future Internet, First
Euro-NF International Workshop, FITraMEn 2008, Porto, Portugal, December 11-12, 2008, Revised Selected Papers edited
by LNCS, Springer.
Andrés Ferragut, Daniel Kofman, Federico Larroca, and Sara Oueslati, “Design and analysis of flow aware load balancing
mechanisms for multi-service networks" in proceedings of the 4th EURO-NGI Conference on Next Generation Internet
Networks (NGI 2008). Krakow, Poland, April 2008.
Andrés Ferragut, Daniel Kofman, Federico Larroca, and Sara Oueslati, “Design and analysis of flow aware load balancing
mechanisms for multi-service networks - Extended Abstract" presented at the EuroFGI Workshop on IP QoS and Traffic
Control. Lisbon, Portugal, December 2007.
page 32
Ingénierie de Trafic Dynamique
F. Larroca
Thank you!
page 33
Dynamic Traffic Engineering
Federico Larroca