Transcript Towards an Accurate AS-level Traceroute Tool

Internet Routing: Measurement,
Modeling, and Analysis
ACM Sigmetrics 2005 Tutorial
Dr. Jia Wang
[email protected]
AT&T Labs Research
Florham Park, NJ 07932, USA
http://www.research.att.com/~jiawang/
Prof. Zhuoqing Morley Mao
[email protected]
Department of EECS
University of Michigan
Ann Arbor, MI 48109, USA
http://www.eecs.umich.edu/~zmao/
Outline
1.
2.
3.
4.
Overview of Inter-domain routing
Measuring inter-domain paths
BGP Measurement
BGP Modeling
Our opinions should not be taken to represent AT&T policies
2
Part I: Overview of Interdomain Routing
Internet
 Loose cooperative effort of Internet
Service Providers (ISPs)
 E.g., AT&T, Sprint, UUNet, AOL
 Best effort service
 Connectedness
 Anyone connected to the Internet can
exchange traffic with anyone else
connected to the Internet
4
Internet routing
routes
Control plane:
exchange routes
Internet
: Routing session
Data plane:
forward traffic
IP traffic
Fail over to alternate route
rusty.cs.berkeley.edu
www.cnn.com
IP=169.229.62.116
Prefix=169.229.0.0/16
IP=64.236.16.52
5
Prefix=64.236.16.0/20
Internet routing domain
 Autonomous routing domain
 Network devices under same technical and administrative
control
 Common routing policy
 E.g., ISPs, enterprise networks
 Autonomous system
 Autonomous routing domain with an AS number (ASN)
 AS numbers: 16 bits integer
 Public AS number: 1 – 64511
 Private AS number: 64512 – 65535
 Examples
 AT&T: 7018, 6431, …
 Sprint: 1239, 1240, …
 MIT: 3
6
More than 20,000 ASes today
Internet
Autonomous
System
ISP
Level3
Calren
Berkeley
ISP
ISP
Qwest
ISP
business
ISP
ISP
AT&T
Sprint UUnet
ISP
ISP
IP traffic
University
company
GNN
CNN
7
Internet routing architecture
Intra-domain
routing
Calren
Berkeley
Level3
IP traffic
Internet
Inter-domain
routing
GNN
CNN
8
Intra-domain routing
 Run within a certain network infrastructure
 Optimize routes taken between points within
a network
 Internal Gateway Protocols (IGPs)




Metrics based
OSPF (Open Shortest Path First)
RIP (Routing Information Protocol)
IS-IS (Intermediate System to Intermediate
System)
9
Inter-domain routing
 Run between networks
 Provide full connectivity of entire
Internet
 External Gateway Protocol (EGP)
 Policy based
 BGP (Border Gateway Protocol)
10
Link state protocols
 Examples: OSPF, IS-IS
 Based on Dijkstra’s shortest path computation
 Each router periodically floods immediate
reachability information to other routers
 Fast convergence
 High communication and computation
overhead
 Not scalable for large networks
 Requires periodic refreshes
11
Vectoring protocols
 Distance vs. Path Vector
 Distance: hop count (RIP)
 Path: entire path (BGP)
 Helps identify loops
 Supports policy-based routing based on path
 Minimal communication overhead
 Takes longer to converge, i.e., in
proportion to the maximum path length
12
Link state vs. vectoring
Link state Vectoring
IGP
EGP
OSPF
IS-IS
RIP
BGP
BGP is a path vector protocol
13
Classful addressing
 IPv4: 32 bits
 Five classes of networks
Class
Address
Mask
# of networks # of hosts
A
0*
255.0.0.0
128
~1.6M
B
10*
255.255.0.0
16384
65535
C
110*
255.255.255.0
~2.1M
255
D
Used for multicast
E
Reserved and currently unused
Improve scaling factor of routing in the Internet => classless
14
CIDR: Classless Inter-domain
Routing (RFC1519)
 No implicit mask based on the class of the network
 Explicit masks passed in the routing protocol
 Allow aggregation and hierarchical routing
IP address: 12.70.0.0
Address
Mask
Mask: 255.255.252.0
00001100 00100110 00000000 00000000
11111111 11111111 11000000 00000000
Network prefix
CIDR representation: 12.70.0.0/22
Host
identifier
15
Address aggregation
12.70.0.0/24
12.70.1.0/24
12.70.2.0/24
12.70.3.0/24
Internet
ISP A
12.71.0.0/16
ISP B
12.70.0.0/22
12.71.0.0/16
16
Routing and forwarding
 Routing
 The decision process of choosing optimal
path that is consistent with the
administrative or technical policy
 Forwarding
 The act of receiving a packet, doing a
lookup, and copying a packet to the next
hop
17
Classless forwarding
Internet
12.70.0.20
10.20.128.10
10.20.128.1
10.20.0.1
IP traffic
10.20.1.1
135.120.0.1
Prefix
12.70.0.0/24
12.70.0.0/16
12.0.0.0/8
0.0.0.0
Next hop
10.20.0.1
10.20.1.1
10.20.128.1
10.20.128.10
18
Inter-domain routing with CIDR
support
 BGP-4 [RFC1771]






De facto EGP
Carry routing information between ASes
Path vector protocol
Policy based routing
Run on top of TCP for reliability
Basic operations
 Set up BGP session
 Exchange all candidate routes
 Send incremental updates
19
Establish BGP session
Establish neighboring session
between 12.10.0.1 and 12.10.0.2
12.10.0.1
Prefix
135.120.0.0/24
68.35.0.0/16
TCP 179
Next hop
10.128.0.1
10.192.1.1
12.10.0.2
Prefix
12.70.0.0/24
12.9.0.0/16
Next hop
10.20.0.1
10.20.1.1
20
Exchange all candidate routes
12.70.0.0/24
12.9.0.0/16
10.20.0.1
10.20.1.1
12.10.0.1
12.10.0.2
135.120.0.0/24
68.35.0.0/16
Prefix
135.120.0.0/24
68.35.0.0/16
12.70.0.0/24
12.9.0.0/16
Next hop
10.128.0.1
10.192.1.1
10.20.0.1
10.20.1.1
10.128.0.1
10.192.1.1
Prefix
12.70.0.0/24
12.9.0.0/16
135.120.0.0/24
68.35.0.0/16
Next hop
10.20.0.1
10.20.1.1
10.128.0.1
10.192.1.1
21
Send incremental updates
Withdraw 12.9.0.0/16
12.10.0.1
Prefix
135.120.0.0/24
68.35.0.0/16
12.70.0.0/24
12.9.0.0/16
12.10.0.2
Next hop
10.128.0.1
10.192.1.1
10.20.0.1
10.20.1.1
Prefix
12.70.0.0/24
12.9.0.0/16
135.120.0.0/24
68.35.0.0/16
Next hop
10.20.0.1
10.20.1.1
10.128.0.1
10.192.1.1
22
BGP messages
 OPEN: set up a peering session
 UPDATE: announce new routes or
withdraw previously announced routes
 NOTIFICATION: shut down a peering
session
 KEEPALIVE: confirm active connection
at regular interval
23
Internal vs. external BGP
Internet
I-BGP
E-BGP
update
E-BGP
I-BGP
update
AS B
AS C
AS A
24
Scaling I-BGP for large AS
 Route reflectors
 Confederations
AS 1000
E-BGP
update
EBGP
RR
RR
IBGP
AS 65010
IBGP EBGP
AS 65020
Only best paths
being sent by
RR
25
Establish connectivity
Prefix
135.120.0.0/16
AS 3
Next hop AS path
12.10.0.5 2 1
Prefix
135.120.0.0/16
IBGP
Next hop AS path
12.10.0.1 1
12.10.0.6
EBGP
12.10.0.5
AS 2
AS 1
135.120.0.0/16
IBGP
EBGP
12.10.0.1
12.10.0.2
IBGP
Prefix
135.120.0.0/16
Next hop AS path
12.10.0.1 1 26
IGP and BGP working together
Prefix
135.120.0.0/16
AS 3
IBGP
Next hop AS path
12.10.0.1 1
Prefix
12.10.0.0/30
135.120.0.0/16
12.10.0.6
Next hop
10.10.0.1
10.10.0.1
EBGP
12.10.0.5
AS 1
12.10.0.1
135.120.0.0/16
EBGP
AS 2
12.10.0.2
10.10.0.1
IBGP
IBGP
Prefix
135.120.0.0/16
Next hop AS path
12.10.0.1 1
27
Policy routing
ISP2
ISP1
traffic
Connectivity DOES NOT
imply reachability!
ISP3
ISP4
traffic
Cust1
Cust2
Policy determines how traffic
can flow on the Internet
28
BGP routing process
Routes
received
from peers
Apply
input
policy
Select
best
route
Best
routes
Apply
output
policy
Routes
advised
to peers
Routing Forwarding
table
table
BGP is not shortest path routing!
29
Best route selection






Highest local preference
Shortest AS path
Lowest MED (Multi-Exit-Discriminator)
I-BGP < E-BGP
Lowest I-BGP cost to E-BGP egress
Tie breaking rules
30
Best route selection
 Highest local preference
 To enforce economical relationships
between domains





Shortest AS path
Lowest MED (Multi-Exit-Discriminator)
I-BGP < E-BGP
Lowest I-BGP cost to E-BGP egress
Tie breaking rules
31
Best route selection
 Highest local preference
 Shortest AS path
 Compare the quality of routes, assuming
shorter AS-path length is better




Lowest MED (Multi-Exit-Discriminator)
I-BGP < E-BGP
Lowest I-BGP cost to E-BGP egress
Tie breaking rules
32
Best route selection
 Highest local preference
 Shortest AS path
 Lowest MED (Multi-Exit-Discriminator)
 To implement “cold potato” routing
between neighboring domains
 I-BGP < E-BGP
 Lowest I-BGP cost to E-BGP egress
 Tie breaking rules
33
Best route selection




Highest local preference
Shortest AS path
Lowest MED (Multi-Exit-Discriminator)
I-BGP < E-BGP
 Prefer EBGP routes to IBGP routes
 Lowest I-BGP cost to E-BGP egress
 Tie breaking rules
34
Best route selection





Highest local preference
Shortest AS path
Lowest MED (Multi-Exit-Discriminator)
I-BGP < E-BGP
Lowest I-BGP cost to E-BGP egress
 Prefer routes via the nearest IGP neighbor
 To implement “hot potato” routing
 Tie breaking rules
35
Best route selection
Highest local preference
Shortest AS path
Lowest MED (Multi-Exit-Discriminator)
I-BGP < E-BGP
Lowest I-BGP cost to E-BGP egress
Tie breaking rules








Router ID based: lowest router ID
Age based: oldest route
36
BGP route propagation
 Not all possible routes propagate
 Commercial relationships determine policies
for
 Route import
 Route selection
 Route export
37
Typical AS relationships
 Provider-customer
 customer pay money for transit
 Peer-peer
 typically exchange respective customers’ traffic for
free
 Siblings
 Mutual transit agreement
 Provide connectivity to the rest of the Internet for
each other
38
AS relationships translate
into BGP export rules
 Export to a provider or a peer
 Allowed: its routes and routes of its
customers and siblings
 Disallowed: routes learned from other
providers or peers
 Export to a customer or a sibling
 Allowed: its routes, the routes of its
customers and siblings, and routes learned
from its providers and peers
39
Which AS paths are legal?
 Valley-free:
 After traversing a provider-customer or
peer-peer edge, cannot traverse a
customer-provider or peer-peer edge
 Invalid path: >= 2 peer links, downhilluphill, downhill-peer, peer-uphill
40
Example of valley-free paths
[1 2 3], [1 2 6 3] are valley-free
X
X
[1 4 3], [1 4 5 3] are not valley free
41
Inferring AS relationships
 Identify the AS-level hierarchy of Internet
 Not shortest path routing





Predict AS-level paths
Traffic engineering
Understand the Internet better
Correlate with and interpret BGP update
Identify BGP misconfigurations
 E.g., errors in BGP export rules
42
Existing approaches
 On inferring Autonomous Systems Relationships in
the Internet, by L. Gao, IEEE Global Internet, 2000.
 Characterizing the Internet hierarchy from multiple
vantage points, by L. Subramanian, S. Agarwal, J.
Rexford, and R. Katz, IEEE Infocom, 2002.
 Computing the Types of the Relationships between
Autonomous Systems, by G. Battista, M. Patrignani,
and M. Pizzonia, IEEE Infocom, 2003.
 On AS-level Path Inference, by Z. Mao, L. Qiu, J.
Wang, and Y. Zhang, ACM Sigmetrics, 2005.
43
Policy routing causes path
inflation
 End-to-end paths are significantly longer than
necessary
 Why?
 Topology and routing policy choices within an ISP,
between pairs of ISPs, and across the global
Internet
 Peering policies and interdomain routing lead to
significant inflation
 Interdomain path inflation is due to lack of BGP
policy to provide convenient engineering of good
paths across ISPs
44
Path inflation
 Based on
[Mahajan03]
 Comparing
actual
Internet
paths with
hypothetical
“direct” link
45