Transcript Routing Overview - University of California, Berkeley

Interdomain Routing
EECS 122: Lecture 11
Department of Electrical Engineering and Computer Sciences
University of California
Berkeley
Review
44

5
2
2

B
66
B
BGP
Intradomain
7
IntraDomain
4
8

RIP

3
3
6
13
13
Formulate the routing
problem as a Shortest
Path Problem
Link State v/s Distance
Vector
Both work reasonably well
in a well engineered
network
11
2
10
OSPF
IntraDomain
3
1
IntraDomain
13
IGRP
C
A
February 25, 2003
12
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
2
Today

Why Hierarchical Routing?



Interconnections
Addressing
Interdomain Routing

BGP
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
3
Hierarchical Routing



Is a natural way for routing
to scale
 Size
 Network Administration
 Governance
Allows multiple metrics at
different levels of the
hierarchy
Exploits address
aggregation and allocation
February 25, 2003
5
44
7
8
RIP
66
11
22
1
33
Inter Domain
Routing
10
OSPF
13
13
12
IGRP
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
4
The Importance of Interconnections


The internet is an interconnection of unequal
networks
Interconnection arrangements drive




the competitive landscape
the robustness of the network
End-to-end performance
Interconnection is central to all large networks




Voice
Data
Wireless
Cable
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
5
Interconnections and Competition

www.thelist.com

How many ISP’s in the 415 area code?



That start with A-C: about 200…
Just DSL that start with A-C: about 80
In the telephone network

How many independent telephone companies in
1894-1902 in the US?



3039 commercial companies, 979 co-operatives
By controlling interconnection Bell got rid of them
Interconnection is now regulated (CLECs)
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
6
Big Picture
Large ISP
Large ISP
Stub
Small ISP
Dial-Up
ISP
Stub
Access
Network
Stub
Abhay
Parekh,
EE122 S2003:Updated
from of diverse networks
TheFebruary
Internet
contains
a
large
number
25, 2003
7
Stoica EE122 F2002
Two ways to interconnect IP Networks…

Peering


The business relationship whereby ISPs
reciprocally provide to each other connectivity to
each others’ transit customers
Transit

The business relationship whereby one ISP
provides (usually sells) access to all destinations
in it’s routing table
William B. Norton, “Internet Service Providers and Peering”
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
8
Peering
Figure from
William B. Norton, “Internet Service Providers and Peering”
West and East Peer with USNet but they can’t reach each other
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
9
Transit
February 25, 2003
Figure from
William B. Norton, “Internet Service Providers and Peering”
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
10
Benefits of Transit v/s Peering
William B. Norton, “Internet Service Providers and Peering”
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
11
Moving from Transit to Peering
William B. Norton, “Internet Service Providers and Peering”
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
12
Name of the Game: Reachability

Interdomain routing is about implementing policies
of reachabilty



Routing efficiency and performance is important, but not
essential
ISPs could be competitors and do not want to share
internal network statistics such as load and topology
Use Border Gateway Protocol (BGP)


Border routers communicate over TCP port 179
A Path Vector Protocol


Communicate entire paths: Route Advertisements
A Router Can be involved multiple BGP sessions
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
13
BGP in concept
you can reach
net A via me
AS2
BGP
AS1
R3
R2
traffic to A
R1
table at R1:
dest next hop
A
R2
A
R
border router
internal router
Share connectivity information across ASes
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
14
I-BGP and E-BGP
IGP: Interior Gateway Protocol.
Example: OSPF
I-BGP
IGP
R2
R3
A
AS1
E-BGP
announce B
AS2
R1
AS3
R5
R4
R
border router
internal router
February 25, 2003
B
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
15
BGP

Border Routers



from the same AS speak IBGP
from different AS’s speak EBGP
EBGP and IBGP are essentially the same
protocol



IBGP can only propagate routes it has learned
directly from its EBGP neighbors
All routers in the same AS form an IBGP mesh
Important to keep IBGP and EBGP in sync
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
16
Sharing routes



One router can participate in many BGP sessions.
Initially … node advertises ALL routes it wants neighbor to
know (could be > 50K routes)
Ongoing … only inform neighbor of changes
AS1
BGP Sessions
AS3
AS2
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
17
Four message types




Open: Session establishment id exchange
Notification: exception driven information
Keep Alive: soft state
Update: path vector information
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
18
BGP Update Message

Contains information about




New Routes
Withdrawn Routes: No longer valid
Path Attributes:
Attribute information allows policies to be
implemented
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
19
Issues

How are the routes advertised?


Addressing
How are routing policies implemented?
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
20
Addressing

Every router must be able to forward based
on *any* destination IP address

One strategy: Have a row for each address


There would be 10^8 rows!
Better strategy: Have a row for a range of
addresses

If addresses are assigned at random that wouldn’t work
too well


MAC addresses
Addresses allocation is a big deal.
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
21
Class-base Addressing

Addressing reflects internet hierarchy


32 bits divided into 2 parts:
Class A
8
0
0 network
0

Class B
16
network
10
0

Class C
February 25, 2003
host
host
24
110
network
host
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
~2 million nets
256 hosts
22
Class-based addresses did not scale
well
Example: an organization initially needs 100 addresses






Allocate it a class C address
Organization grows to need 300 addresses
Class B address is allocated. (~64K hosts)
That’s overkill -a huge waste
Only about 8200 class B addresses!
Artificial Address crises
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
23
Current Solution: Classless Internet
Domain Routing (CIDR)




CIDR allows networks to be assigned on arbitrary bit
boundaries.
 Address ranges can be assigned in chunks of 2k k=1…32
Idea - use aggregation - provide routing for a large
number of customers by advertising one common prefix.
 This is possible because nature of addressing is hierarchical
Summarization reduces the size of routing tables, but
maintains connectivity.
Aggregation

Scalability and survivability of the Internet
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
24
Current Solution: Classless Internet
Domain Routing (CIDR)
Suppose fifty computers in a network are
assigned IP addresses 128.23.9.0 - 128.23.9.49


They share the prefix 128.23.9
Is this the longest prefix?
 Range is 01111111 00001111 00001001 00000000 to



01111111 00001111 00001001 00110001
How to write 01111111 00001111 00001001 00X?
Convention: 128.23.9.0/26
There are 32-27=6 bits for the 50 computers
 26 = 64 addresses
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
25
Classless Inter-domain Routing Addresses



Specify a range of addresses by a prefix: X/Y
 The prefix common to the entire range is the first Y bits of X.
 X: The first address in the range has prefix X
 Y: 232-Y addresses in the range
Example 128.5.10/23
 Common prefix is 23 bits: 01000000 00000101 0000101
 Number of addresses: 29 = 512
Prefix aggregation

Combine two address ranges
128.5.10/24 and 128.5.11/24 gives 128.5.10/23
Routers match to longest prefix


February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
26
Assigning IP address (Ideally)



A host gets its IP address from the IP address block of its
organization
An organization gets an IP address block from its ISP’s
address block
An ISP gets its address block from its own provider OR
from one of the 3 routing registries:




ARIN: American Registry for Internet Numbers
RIPE: Reseaux IP Europeens
APNIC: Asia Pacific Network Information Center
Each Autonomous System (AS) is assigned a 16-bit
number (65536 total)

Currently 10,000 AS’s in use
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
27
Advertising a Route

One router telling another one



The prefix
IP address of the next hop
Path list of AS’s that the announcement has
passed through



Since announcement propagates from destination, this
yields the path
No refresh messages required
The announcing router will follow the path
itself
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
28
BGP Routing Table Scaling


Many small networks
Aggregation hides a lot…
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
29
BGP Update Message

Contains information about



New Routes
Withdrawn Routes: No longer valid
Path Attributes:





Path Weights
Multple Exit Discriminators
Local Preferences
Etc.
Attribute information allows policies to be
implemented
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
30
BGP: A Path-vector protocol
ner-routes>show ip bgp
BGP table version is 6128791, local router ID is 4.2.34.165
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal
Origin codes: i - IGP, e - EGP, ? - incomplete
Network
Next Hop
Metric LocPrf Weight Path
* i3.0.0.0
4.0.6.142
1000
50
0 701 80 i
* i4.0.0.0
4.24.1.35
0
100
* i12.3.21.0/23
192.205.32.153
0
50
0 7018 4264 6468 ?
* e128.32.0.0/16
192.205.32.153
0
50
0 7018 4264 6468 25 e
0 i
 Every route advertisement contains the entire AS path
 Generalization of distance vector
 Can implement policies for choosing best route
 Can detect loops at an AS level
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
31
Multihoming

B
5
44
7
8
IBGP
RIP
66

22
a
IBGP
33
1
IGRP A
February 25, 2003
Two or more
interdomain
connections between
the same AS’s
Two or more
interdomain
connections between a
customer and different
ISPs
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
32
Multiexit Discriminators (MEDs)
One AS influences the decisions
of a neighboring AS
B
5
44
7
8
IBGP
RIP
66
22
x
IBGP
33
1
IGRP A
February 25, 2003
•AS_A wants to tell AS_B that network x is closer to router 2
than to router 3
•Router 2 advertises a smaller MED value for x than Router 3
•AS_B prefers the path to x that does not go through 6 and 3
•AS_B does not propagate MEDS from AS_A any further
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
33
Routing Process Overview
Routes
received
from
neighbors
accept,
deny, set
preferences
Import
Policy
Engine
Choose
best route
Decision
process
BGP table
February 25, 2003
forward,
not forward
set MEDs
Routes
used by
router
Export
Policy
Engine
Routes
sent to
neighbors
IP routing
table
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
34
Attribute: Local Preference
140.20.1.0/24




Used to indicate preference
among multiple paths for the
AS1
same prefix anywhere in the
Internet.
AS3
AS2
The higher the value the
more preferred
AS4
Exchanged between IBGP
peers only. Local to the AS. BGP table at AS4:
Destination
AS Path
Local Pref
Often used to select a
specific exit point for a
140.20.1.0/24 AS3 AS1 300
particular destination
140.20.1.0/24 AS2 AS1 100
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
35
Choosing best route

Choose route with highest LOCAL_PREF




If multiple choices, select route with shortest hopcount
If multiple choices for same neighboring AS,
choose path with max MED value
Choose route based on lowest origin type



Preference-based routing
IGP < EGP < INCOMPLETE
Among IGP paths, choose one with lowest cost
Finally use router ID to break the tie.
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
36
BGP Policies

Multiple ways to implement a “policy”

Decide not propagate advertisements


Decide not to consider MEDs but use shortest hop



I’m not carrying your traffic
Hot potato routing
Prepend own AS# multiple times to fool BGP into
not thinking AS further away
Many others…
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
37
Transit vs. Nontransit AS
Transit traffic = traffic whose source and destination are outside the AS
Nontransit AS: does not carry transit traffic
• Advertise own routes only
• Do not propagate routes learned from other AS’s
r1
• Advertises its own routes PLUS routes
learned from other AS’s
ISP1
ISP1
r3 ISP2
r1
r3
r2
r2
February 25, 2003
Transit AS: does carry transit traffic
r3
r1
r1
r2
ISP2
r3
r2,r3
r2,r1
AS1
AS1
r2
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
38
Customer-Transit Problem
Large ISP
r3
r1
r1
Large ISP
r3
r2,r3
r2,r1
Small ISP
r2
 Assume that the small ISP is a customer of two large ISPs
 If customer ISP does not obey export rules
 forwards advertisements from one large ISP to another
 Carries huge volume of transit traffic between two large
ISPs
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
39
BGP and Performance



BGP isn’t designed for policy routing not performance
 Hot Potato routing is most common but suboptimal
 Performance isn’t the greatest
20% of internet paths inflated by at least 5 router hops
Very susceptible to router misconfiguration
 Blackholes: announce a route you cannot reach

October 1997 one router brought down the internet for 2 hours
Flood update messages (don’t store routes, but keep asking your
neighbors to clue you in). 3-5 million useless withdrawals!
In principle, BGP could diverge
 Various solutions proposed to limit the set of allowable policies
 Focuses on avoiding “policy cycles”


February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
40
4/1-4/16 2002
•1,224,733 IP addresses,
•2,093,194 IP links,
•932,000 destinations,
•70% of globally routable network prefixes;
•10,999 ASes (84% of ASes),
•34,209 peering sessions
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
41
Skitter Legend

Plot the AS based on polar co-ordinates (r,θ):

r = 1- log (As degree +1 / Max Degree+1)


Higher the degree lower the radius
Θ = longitude of AS headquarters
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
42
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
43
Summary



The Internet is composed of various ASes which
use BGP to inter-network themselves
The Internet uses classless addressing
BGP as a routing protocol





Path-vector based
Supports route-aggregation
Supports preferential routing
Uses Import and Export policies
BGP is the protocol that “holds” the Internet
together
February 25, 2003
Abhay Parekh, EE122 S2003:Updated from
Stoica EE122 F2002
44