Transcript Impact of Hot-Potato Routing Changes in IP Networks

IMPACT OF HOT-POTATO ROUTING
CHANGES IN IP NETWORKS
Authors
Renata Teixeira , Aman Shaikh and Jennifer Rexford(AT&T),
Tim Griffin(Intel)
http://www-cse.ucsd.edu/~teixeira
Presenter : Farrukh Shahzad
Internet Routing
Architecture
Web
Server
AT&T
Verio
UCSD
AOL
Sprint
interdomain routing (BGP)
User
SIGMETRICS’04
intradomain routing (OSPF,IS-IS)
Changes in one AS
End-to-end performance
may impact traffic
depends on all ASes
and routing in other ASes
along the path
2
Distance-vector &Link state routing
 Distance vector routing





It involves two factors: the distance or metric, of a destination,
and the vector, or direction to take to get there.
Routing information is only exchanged between directly
connected neighbors.
A router knows from which neighbor a route was learned, but it
does not know where that neighbor learned the route
A router can't see beyond its own neighbors. This aspect of
distance vector routing is sometimes referred to as "routing by
rumor."
Measures like split horizon and poison reverse are employed to
avoid routing loops.
SIGMETRICS’04
3
Distance-vector &Link state routing
 Link-state routing
 In contrast, requires that all routers know about the paths
reachable by all other routers in the network.
 Link-state information is flooded throughout the link-state
domain (an area in OSPF ) to ensure all routers possess a
synchronized copy of the area's link-state database.
 From this common database, each router constructs its own
relative shortest-path tree, with itself as the root, for all known
routes.
 BGP is DV routing protocol
 OSPF is LS Routing Protocol
SIGMETRICS’04
4
Interaction between IGP and BGP
 A router combines the BGP and IGP information
to construct a forwarding table.
 BGP exchanges route advertisements with neighboring
domains, and propagate reachability information within
AS.
 IGP protocol, such as OSPF, computes shortest paths
based on configurable link weights.
 The interaction between IGP and BGP
 Hot potato routing.
SIGMETRICS’04
5
Hot-Potato Routing
multiple connections
to the same peer
dst
New York
San Francisco
ISP network
10
9
Dallas
Hot-potato routing = route to closest egress point
when there is more than
one route to destination
SIGMETRICS’04
6
Hot-Potato Routing Change
dst
New York
San Francisco
- failure
- planned maintenance 11
- traffic engineering
ISP network
9
11
Consequences:
Transient forwarding instability
Traffic shift
Inter-domain routing changes
SIGMETRICS’04
10
Dallas Routes to thousands
of destinations switch
exit point!!!
7
Approach In Paper
 Understanding impact in real networks
 How often hot-potato changes happen?
 How many destinations do they affect?
 What are the convergence delays?
 Main contributions
 Methodology for measuring hot-potato
changes
 Characterization on AT&T’s IP backbone
SIGMETRICS’04
8
Challenges for Identifying
Hot-Potato Changes
 Cannot collect data from all routers
 OSPF: flooding gives complete view of topology
 BGP: multi-hop sessions to several vantage points
 A single event may cause multiple messages
 Group related routing messages in time
 Router implementation affects message timing(PDelay)
 Real Time & Controlled experiments of router in the lab
 Many BGP updates caused by external events
 Classify BGP routing changes by possible causes
SIGMETRICS’04
9
Measurement Methodology
BGP updates
BGP monitor
A
B
AT&T
backbone
OSPF Monitor
OSPF
messages
Replay routing decisions from
vantage point A and B to identify
hot-potato changes
SIGMETRICS’04
10
Measurement Methodology
SIGMETRICS’04
12
Sections Details
 Section III- A: presents the measurement infrastructure
used to collect BGP updates and OSPF LSAs.
 Section III-B : describe how to compute the distance vector
from the OSPF LSAs in.
 Section III-C : explains the classification of BGP routing
changes in terms of the possible causes. This sets the stage
for the discussion in next section.
 Section III-D : How to associate BGP routing changes with
related distance changes that occur close in time
SIGMETRICS’04
13
Measurement Infrastructure


iBGP session allows the monitor to see changes in the “egress point” of BGP
routes.
The BGP monitor also dumps a snapshot of its routes four times a day to provide
an initial view of the best route for each prefix for each vantage point, For later
classify the type of BGP change as discussed in Section III-C
SIGMETRICS’04
14
Classifying BGP Rt Changes
SIGMETRICS’04
15
 The large volume of BGP updates shows
exploration of multiple alternate routes when a
router switches from one best path to another .
 IGP distance changes cause a router inside the
AS to switch from one stable route to another
with a different egress point.
SIGMETRICS’04
16
BGP Reaction Time to Distance Changes
(i) Rerun the IGP shortest-path computation
(ii) Apply the BGP decision process to select the best route
(iii) Send update messages to BGP neighbors for the routes that
have changed.
SIGMETRICS’04
17
Transfer Delay for Multiple Prefixes
1-The LSA is flooded throughout the network and each router
computes new distances. For example, A and B compute new distances of 21
and 11, respectively.
2- After their scan timers elapse, and rerun the BGP decision
process. If runs first, selects the egress point with a distance of 20, since this is
smaller than 21. Sometime afterwards, A selects egress point C.
3- B sends the new route (with egress point E ) to A, A and selects egress
point with a distance of 19.
SIGMETRICS’04
18
Temporal and Spatial Variability(distance
changes effect)
SIGMETRICS’04
19
Hot-Potato Variation Across
Prefixes
SIGMETRICS’04
20
IMPLICATIONS OF HOT POTATOES
 Performance Degradation
 Routing and Traffic Shifts
 Slow Forwarding-Plane Convergence
 Measurement Inaccuracies
 Active Probes of the Forwarding Plane
 External Analysis of BGP Updates
SIGMETRICS’04
21
Conclusion
 Hot-potato routing plays an important role in
 BGP routing changes, and that BGP updates can
lag 60 seconds (or more!) behind the related IGP
events
 The frequency and impact of hot-potato routing
depends on the topology and configuration of
the network under study
 routing is usually a major contributor to large
traffic variations. In particular, hot-potato
routing changes are responsible for the largest
shifts in the traffic matrix
SIGMETRICS’04
22
…conclusion
 Setting IGP link weights without accounting for
possible changes in the egress points can lead to
routing configurations that cause unnecessary
congestion.
SIGMETRICS’04
23
Thanks
SIGMETRICS’04
24