Transcript link weights - UniNa STiDuE

Intra-domain Traffic Engineering
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Outline
●
●
●
Introduction to Internet Traffic Engineering
IP-based Traffic Engineering
MPLS-based Traffic Engineering
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Do IP networks manage themselves?
●
In some sense, yes:
–
–
●
But, does the network run efficiently?
–
–
●
Congested link when idle paths exist?
High-delay path when a low-delay path exists?
How should routing adapt to the traffic?
–
–
●
TCP senders send less traffic during congestion
Routing protocols adapt to topology changes
Avoiding congested links in the network
Satisfying application requirements (e.g., delay)
… essential questions of Traffic Engineering
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Traffic Engineering
●
What is Traffic Engineering?
–
Control and optimization of routing, to steer traffic
through the network in the most effective way
“Internet traffic engineering is defined as that aspect of
Internet network engineering dealing with the issue of
performance evaluation and performance optimization
of operational IP networks. Traffic Engineering
encompasses the application of technology and
scientific principles to the measurement,
characterization, modeling, and control of Internet
traffic”
RFC 3272 – Overview and Principles of Internet TE
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Traffic Engineering
●
Two fundamental approaches:
–
IP-based Traffic Engineering
–
MPLS-based Traffic Engineering
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
IP-based Traffic Engineering
●
Using traditional routing protocols:
–
–
–
–
Routers flood information to learn topology
Routers determine “next hop” to reach other routers
Path selection based on link weights (shortest path)
Link weights configured by network operator
2
3
2
1
1
1
3
5
4
3
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Approaches for setting the link
weights
●
Conventional static heuristic
–
Proportional to physical distance
• Cross-country links have higher weights
• Minimizes end-to-end propagation delay
– Inversely proportional to link capacity
• Smaller weights for higher-bandwidth links
• Attracts more traffic to links with more capacity
●
Can we do better?
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Approaches for setting the link
weights
●
A traffic engineered approach
– Collect measurements of traffic and topology
– Tune the weights based on the offered traffic
– Network management system sets the link weights
– Acting on network-wide view of traffic and topology
– Directly minimizes metrics like max link utilization
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
TE approach: Measure, Model and Control
Network-wide
“what if” model
Offered
Topology/
traffic
Configuration
measure
Changes to
the network
control
Operational network
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
IP-based Traffic Engineering
●
Topology
–
●
Traffic matrix
–
●
Configurable parameters for routing protocol
Performance objective
–
●
Offered load between points in the network
Link weights
–
●
Connectivity and capacity of routers and links
Balanced load, low latency, …
Question: Given the topology and the traffic
matrix, which link weights should be used?
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
IP-based Traffic Engineering
●
Instrumentation
–
–
●
Network-wide models
–
–
●
Topology: monitoring of the routing protocols
Traffic matrix: fine-grained traffic measurement
Representations of topology and traffic
“What-if” models of shortest-path routing
Network optimization
–
–
Efficient algorithms to find good configurations
Operational experience to identify key constraints
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Topology/Routing
●
Router configuration files
–
–
–
–
●
Daily snapshot of network assets & configuration
Software to parse the router config commands
Network-wide view of topology & routing policies
Also useful for detecting configuration mistakes
Routing monitors
–
–
–
–
–
Online monitoring of routing protocol messages
Real-time view of routes via neighboring ASes
Real-time view of paths within the AS
Software for aggregating and querying the data
Also useful for detecting and diagnosing anomalies
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Formalizing the Optimization Problem
●
Input: graph G(R,L)
–
–
–
●
Input: traffic matrix
–
●
R is the set of routers
L is the set of unidirectional links
cl is the capacity of link l
Mi,j is traffic load from router i to j
Output: setting of the link weights
–
–
wl is weight on unidirectional link l
Pi,j,l is fraction of traffic from i to j traversing link l
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Formalizing the Optimization Problem
●
A solution to the optimization problem cannot
freely allocate the traffic load between two
routers
–
–
●
The traffic between two routers can only flow along a
shortest weighted path (routing protocols work this
way)
This constraint implies that we achieve a sub-optimal
solution to the general routing problem
In case multiple shortest weighted paths exist,
traffic can be split among them
–
In practice, this is allowed by OSPF by means of the
ECMP (Equal Cost Multi-Path) function
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Formalizing the Optimization Problem
●
To enforce the optimal solution, it is necessary to split
traffic along multiple shortest paths
Values of Pi,j,l
0.25
0.25
0.5
1.0
0.25
0.5
1.0
0.25
0.5
0.5
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Complexity of the Optimization Problem
●
NP-complete optimization problem
–
–
●
No efficient algorithm to find the link weights
Even for simple objective functions
What are the implications?
–
Have to resort to searching through weight settings
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Optimization based on local search
●
Start with an initial setting of the link weights
–
–
–
●
Compute the objective function
–
–
–
●
E.g., same integer weight on every link
E.g., weights inversely proportional to capacity
E.g., existing weights in the operational network
Compute the all-pairs shortest paths to get Pi,j,l
Apply the traffic matrix Mi,j to get link loads ul
Evaluate the objective function from the ul/cl
Generate a new setting of the link weights
repeat
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Making the search efficient
●
Avoid repeating the same weight setting
–
–
–
●
Avoid computing shortest paths from scratch
–
–
●
Explore settings that changes just one weight
Apply fast incremental shortest-path algorithms
Limit number of unique values of link weights
–
●
Keep track of past values of the weight setting
… or keep a small signature of past values
Do not evaluate setting if signatures match
Do not explore 216 possible values for each weight
Stop early, before exploring all settings
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Application to AT&T's backbone network
●
Performance of the optimized weights
–
–
–
Search finds a good solution within a few minutes
Much better than link capacity or physical distance
Competitive with multi-commodity flow solution
●
●
Optimal routing possible with more flexible routing
protocols (e.g. MPLS)
How AT&T changes the link weights
–
–
–
–
Maintenance every night from midnight to 6am
Predict effects of removing link(s) from network
Reoptimize the link weights to avoid congestion
Configure new weights before disabling equipment
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
To learn more...
●
Overview papers
–
●
Traffic measurement
–
–
●
R. Caceres, N. Duffield, A. Feldmann, et al., “Measurement and analysis of
IP network usage and behavior”, IEEE Communications Magazine, May
2000
A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, F. True,
“Deriving traffic demands for operational IP networks: Methodology and
experience”, IEEE/ACM Transactions on Networking, June 2001
Topology and configuration
–
●
B. Fortz, J. Rexford, M. Thorup, “Traffic engineering with traditional IP
routing protocols”, IEEE Communication Magazine, October 2002
A. Feldmann, J. Rexford, “IP network configuration for intradomain traffic
engineering”, IEEE Network Magazine, September/October 2001
Intradomain route optimization
–
B. Fortz, M. Thorup, “Internet traffic engineering by optimizing OSPF
weights”, Proc. Of IEEE INFOCOM 2000
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Traffic Engineering
●
Two fundamental approaches:
–
IP-based Traffic Engineering
–
MPLS-based Traffic Engineering
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Multi-Protocol Label Switching
●
Multi-Protocol
–
Encapsulate a data packet
●
–
Put an MPLS header in front of the packet
●
●
Could be IP, or some other protocol (e.g., IPX)
Actually, can even build a stack of labels…
Label Switching
–
–
MPLS header includes a label
Label switching between MPLS-capable routers
IP packet
MPLS header
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Forwarding Equivalence Class (FEC)
●
Rule for grouping packets
–
–
●
Packets that should be treated the same way
Identified just once, at the edge of the network
Example FECs
–
Destination prefix
●
●
–
Src/dest address, src/dest port, and protocol
●
●
–
Longest-prefix match in forwarding table at entry point
Useful for conventional destination-based forwarding
Five-tuple match at entry point
Useful for fine-grain control over the traffic
Sent by a particular customer site
●
●
Incoming interface at entry point
Useful for virtual private networks
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
LSP (Label Switched Path) Setup
●
Protocols used to automatically establish LSPs:
–
–
LDP (Label Distribution Protocol – RFC 3036)
RSVP (with the objects needed to request/map labels)
●
–
–
Exploit IP routing tables information to establish paths and
bind FECs to LSPs
CR-LDP (Constraint-based Routing LDP – RFC 3212)
RSVP-TE (TE extension to RSVP – RFC 3209)
●
Support establishment of explicit paths
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Explicit routing
●
●
●
LSPs can be established along paths other than
the shortest path
More flexibility than destination-based IP routing
In an MPLS network, it is (in theory) possible to
implement the optimal solution to the general
routing problem (multi-commodity flow problem)
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
TE with constraint-based routing
●
Explicit routing + fine-grained FEC definition
–
●
●
Allows to select a suitable path for each flow
We can select a path that meets the QoS
requirements of the flow
Knowledge of network resource usage is required
–
Extend OSPF to disseminate the extra information
(OSPF-TE – RFC 3630)
●
●
Maximum bandwidth, maximum reservable bandwidth,
unreserved bandwidth, TE metric, etc.
The MPLS ingress LSR (Label Switching Router)
computes the constraint-based path and
establishes the corresponding explicit LSP
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
TE with constraint-based routing
●
Given the network topology and the flow
requirements, how to select a path?
–
–
●
A feasible path is such that R(l)>B on all the links
–
●
We assume that flow requirements are expressed in
terms of requested bandwidth B between a source s
and a destination d
The residual bandwidth on each link is R(l)
If we prune all the links such that R(l)<B, all the
paths between s and d in the pruned topology are
feasible
What feasible path can we choose?
–
The goal is to optimize resource usage
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Widest Shortest Path (WSP)
●
●
WSP selects the path with the minimum hop
count among all feasible paths
In case several such path exist, the one the
maximal residual bandwidth is selected
–
●
The residual bandwidth of a path is the minimum
among the residual bandwidths of its links
R. Guerin, D. Williams, and A. Orda, “QoS routing mechanisms and OSPF
extensions,” in Proc. IEEE Globecom, 1997
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Other TE algorithms
●
Most of TE algorithms
–
–
–
●
●
prune links with insufficient bandwidth
assign a cost to each link in the pruned topology
select the least cost path
Different techniques to assign costs
The cost may be an increasing function of link
load
–
–
Slightly loaded links are preferred
Heavily loaded links are discouraged
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Minimum Interference Routing
(MIRA)
●
Given the knowledge of ingress-egress pairs, MIRA
selects the path which minimizes the interference
–
●
●
The minimum interference path between a particular
ingress-egress pair is the path which maximizes the
minimum maxflow between all other ingress-egress pairs
This problem is NP-hard
–
●
Interference on an ingress-egress pair (s,d) due to routing a
flow between some other ingress-egress pair is defined as the
decrease in the maximum network flow between s and d
Set link weights proportional to maxflow reduction
K. Kar, M. Kodialam, and T. Lakshman, “Minimum Interference Routing of
Bandwidth Guaranteed Tunnels with MPLS Traffic Engineering Applications,”
IEEE Journal on Selected Areas in Communications, vol. 18, no. 12, pp. 25662579, December 2000.
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group
Simple Minimum Interference
Routing (SMIRA)
●
The interference on an ingress-egress pair is evaluated by
means of a k-shortest-path-like computation instead of a
maxflow computation
–
–
–
–
●
●
The set of k paths is determined by first computing the widestshortest path between s and d
Then, all the links along this path with a residual bandwidth
equal to the bottleneck bandwidth of the path are pruned
The second path is the widest-shortest path in the pruned
topology
This procedure is repeated until either k paths are found or no
more paths are available
The cost of links belonging to the set of k paths is
increased proportionally to the weight of the path and the
ratio of bottleneck bandwidth to residual bandwidth.
I. Iliadis and D. Bauer, “A New Class of Online Minimum-Interference
Routing Algorithms,” Networking 2002, LNCS 2345, pp. 959-971, 2002.
Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group