Transcript ieee03 - Princeton University

Traffic Engineering for ISP Networks
Jennifer Rexford
IP Network Management and Performance
AT&T Labs - Research; Florham Park, NJ
http://www.research.att.com/~jrex
1
Outline
 Internet
routing protocols
 Traffic engineering using traditional protocols
– Optimizing network configuration to prevailing traffic
– Requirements for topology, routing, and traffic info
 Traffic
demands
– Volume of load between edges of the network
– Technique for measuring the traffic demands
 Route
optimization
– Tuning the link weights to the offered traffic
– Incorporating various operational constraints
 Conclusions
2
Autonomous Systems (ASes)
 Internet
divided into ASes
– Distinct regions of administrative control (~14,000)
– Routers and links managed by a single institution
– Service provider, company, university, …
 Hierarchy
of ASes
– Large, tier-1 provider with a nationwide backbone
– Medium-sized regional provider with smaller backbone
– Small network run by a single company or university
 Interaction
between ASes
– Internal topology is not shared between ASes
– … but, neighbors interact to coordinate routing
3
Path Traversing Multiple ASes
Path: 6, 5, 4, 3, 2, 1
4
3
5
2
7
1
6
Web server
Client
4
Interdomain Routing: Border Gateway Protocol
 ASes
exchange info about who they can reach
– IP prefix: block of destination IP addresses
– AS path: sequence of ASes along the path
 Policies
configured by the AS’s network operator
– Path selection: which of the paths to use?
– Path export: which neighbors to tell?
“I can reach 12.34.158.0/24
via AS 1”
“I can reach 12.34.158.0/24”
1
12.34.158.5
2
3
5
Intradomain Routing: OSPF or IS-IS
 Shortest
path routing based on link weights
– Routers flood the link-state information to each other
– Routers compute the “next hop” to reach other routers
 Weights
configured by the AS’s network operator
– Simple heuristics: link capacity or physical distance
– Traffic engineering: tuning the link weights to the traffic
2
3
2
1
1
1
3
5
4
3
6
Motivating Problem: Congested Link
 Detecting
that a link is congested
– Utilization statistics reported every five minutes
– Sample probe traffic suffers degraded performance
– Customers complain (via the telephone network?)
 Reasons
why the link might be congested
– Increase in demand between some set of src-dest pairs
– Failed router/link within the AS causes routing change
– Failure/reconfiguration in another AS changes routes
 Challenges
– Know the cause, not just the manifestations
– Predict the effects of possible changes to link weights
7
Traffic Engineering in an ISP Backbone
 Topology
of the ISP backbone
– Connectivity and capacity of routers and links
 Traffic
demands
– Offered load between points in the network
 Routing
configuration
– Link weights for selecting paths
 Performance
objective
– Balanced load, low latency, …
 Question:
Given the topology and traffic demands
in an IP network, what link weights should be used? 8
Modeling Traffic Demands
 Volume
of traffic V(s,d,t)
– From a particular source s
– To a particular destination d
– Over a particular time period t
 Time
period
– Performance debugging -- minutes or tens of minutes
– Time-of-day traffic engineering -- hours or days
– Network design -- days to weeks
 Sources
and destinations
– Individual hosts -- interesting, but huge!
– Individual prefixes -- still big; not seen by any one AS!
– Individual edge links in an ISP backbone -- hmmm….
9
Traffic Matrix
Traffic matrix: V(in,out,t) for all pairs (in,out)
in
out
10
Problem: Hot Potato Routing
 ISP is
in the middle of the Internet
– Multiple connections to multiple other ASes
– Egress point depends on intradomain routing
 Problem
with point-to-point models
– Want to predict impact of changing intradomain routing
– But, a change in weights may change the egress point!
2
4
1
3
11
Traffic Demand: Multiple Egress Points
 Definition: V(in,
{out}, t)
– Entry link (in)
– Set of possible egress links ({out})
– Time period (t)
– Volume of traffic (V(in,{out},t))
 Computing
the traffic demands
– Measure the traffic where it enters the ISP backbone
– Identify the set of egress links where traffic could leave
– Sum over all traffic with same in, {out}, and t
12
Traffic Mapping: Ingress Measurement
Packet
measurement (e.g., Netflow, sampling)
– Ingress point i
– Destination prefix d
– Traffic volume Vid
ingress
i
destination
d
13
Traffic Mapping: Egress Point(s)
Routing
data (e.g., forwarding tables)
– Destination prefix d
– Set of egress points ed
destination
d
14
Traffic Mapping: Combining the Data
 Combining
multiple types of data
– Traffic: Vid (ingress i, destination prefix d)
– Routing: ed (set ed of egress links toward d)
– Combining: sum over Vid with same ed
ingress
i
egress set
15
Application on the AT&T Backbone
 Measurement
data
– Netflow data (ingress traffic)
– Forwarding tables (sets of egress points)
– Configuration files (topology and link weights)
 Effectiveness
– Ingress traffic could be matched with egress sets
– Simulated flow of traffic consistent with link loads
 Challenges
– Loss of Netflow records during delivery (can correct for it!)
– Egress set changes between table dumps (not very many)
– Topology changes between configuration dumps (just one!)
16
Traffic Analysis Results
 Small
number of demands contribute most traffic
– Optimize routes for just the heavy hitters
– Measure a small fraction of the traffic
– Must watch out for changes in load and set of exit links
 Time-of-day
fluctuations
– Reoptimize routes a few times a day (three?)
 Traffic
(in)stability
– Select routes that are good for different demand sets
– Reoptimize routes after sudden changes in load
17
Three Traffic Demands in San Francisco
18
Underpinnings of the Optimization
 Route
prediction engine (“what-if” tool)
– Model the influence of link weights on traffic flow
» Select a closest exit point based on link weights
» Compute shortest path(s) based on link weights
» Capture splitting over multiple shortest paths
– Sum the traffic volume traversing each link
 Objective
function
– Rate the “goodness” of a setting of the link weights
– E.g., “max link utilization” or “sum of exp(utilization)”
19
Weight Optimization
 Local
search
– Generate a candidate setting of the weights
– Predict the resulting load on the network links
– Compute the value of the objective function
– Repeat, and select solution with lowest objective function
 Efficient
computation
– Explore the “neighborhood” around good solutions
– Exploit efficient incremental graph algorithms
 Performance
results on AT&T’s network
– Much better than simple heuristics (link capacity, distance)
– Quite competitive with multi-commodity flow solution
20
Incorporating Operational Realities
 Minimize
changes to the network
– Changing just one or two link weights is often enough
 Tolerate
failure of network equipment
– Weights settings usually remain good after failure
– … or can be fixed by changing one or two weights
 Limit
the number of distinct weight values
– Small number of integer values is sufficient
 Limit
dependence on accuracy of traffic demands
– Good weights remain good after introducing random noise
 Limit
frequency of changes to the weights
– Joint optimization for day and night traffic matrices
21
Conclusions
 Our
approach
– Measure: network-wide view of traffic and routing
– Model: data representations and “what-if” tools
– Control: intelligent changes to operational network
 Application
in AT&T’s network
– Capacity planning
– Customer acquisition
– Preparing for maintenance activities
– Comparing different routing protocols
 Ongoing
work: interdomain traffic engineering
22
To Learn More…

Overview papers
– “Traffic engineering for IP networks”
(http://www.research.att.com/~jrex/papers/ieeenet00.ps)
– “Traffic engineering with traditional IP routing protocols”
(http://www.research.att.com/~jrex/papers/ieeecomm02.ps)

Traffic measurement
– "Measurement and analysis of IP network usage and behavior”
(http://www.research.att.com/~jrex/papers/ieeecomm00.ps)
– “Deriving traffic demands for operational IP networks”
(http://www.research.att.com/~jrex/papers/ton01.ps)

Topology and configuration
– “IP network configuration for intradomain traffic engineering”
(http://www.research.att.com/~jrex/papers/ieeenet01.ps)

Intradomain route optimization
– “Internet traffic engineering by optimizing OSPF weights”
(http://www.ieee-infocom.org/2000/papers/165.ps)
– “Optimizing OSPF/IS-IS weights in a changing world”
(http://www.research.att.com/~mthorup/PAPERS/change_ospf.ps)
23