Transcript interdomain_routing

COMP/ELEC 429/556
Introduction to Computer Networks
Inter-domain routing
Some slides used with permissions from Edward W.
Knightly, T. S. Eugene Ng, Ion Stoica, Hui Zhang
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
1
Autonomous Systems (AS)
• Internet is not a single network!
• The Internet is a collection of networks, each controlled
by a different administration
• An autonomous system (AS) is a network under a single
administrative control
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
2
Example
Interior router
Border router
AS-1
AS-3
AS-2
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
3
Implications
• ASs want to choose own local routing algorithm
– AS takes care of getting packets to/from their own hosts
– Intradomain routing: shortest path, load balance, etc.
• ASs want to choose own non-local routing policy
– Interdomain routing must accommodate this to a degree
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
4
Previous focus: Intra-Domain Routing
Interior router
Border router
AS-1
AS-3
AS-2
Intra-domain routing protocol aka Interior Gateway Protocol
(IGP)
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
5
Today’s focus: Inter-Domain Routing
Interior router
Border router
AS-1
AS-3
AS-2
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
6
Inter-Domain Routing Considerations
• Global connectivity is at stake
• Inevitably leads to one single protocol that everyone must speak
– Unlike many choices in intra-domain routing
• What are the requirements?
– Scalability
– Flexibility in choosing routes
• If you were to choose, link state based or distance vector
based?
• Border Gateway Protocol (BGP)
– A hybrid between link state and distance vector
– “Path vector”
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
7
Border Gateway Protocol Part I: E-BGP
AS2
AS1
E-BGP
border router
interior router
 Two types of routers
 Border router, Interior router
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
8
BGP Operations (Simplified)
Establish session on
TCP port 179
AS1
BGP session
Exchange all
active routes
AS2
Exchange incremental
updates
T. S. Eugene Ng
While connection
is ALIVE exchange
route UPDATE messages
eugeneng at cs.rice.edu
Rice University
9
BGP Update Messages
• Update : Announcing new routes or withdrawing previously
announced routes.
Update
=
Destination IP address prefix + attributes values
(e.g. a routing path)
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 10
Part I: E-BGP, Share connectivity
information across ASs
you can reach net
prefix A via addr and
the path is “AS2”
AS2
E-BGP
AS1
addr
R1
A
BGP table at R1:
dest network prefix AS path next hop
A
AS2
addr
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University
11
Part II: I-BGP, Carrying Info within an AS
E-BGP update
I-BGP updates
T. S. Eugene Ng
• I-BGP used to
disseminate learned
routes to all routers in
AS
eugeneng at cs.rice.edu
Rice University 12
Part II: I-BGP, Carrying Info within an AS
you can reach net
B via addr1 and the
path is “AS3”
E-BGP
I-BGP
you can reach net
B via addr2 and
the path is “AS3 AS2”
E-BGP
addr2
AS1
you can reach net
B via addr1 and the
path is “AS3”
A
AS2
addr1
AS3
B
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 13
Attributes are Used to Select Best Routes
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
T. S. Eugene Ng
Given multiple
routes to the same
prefix, a BGP speaker
must pick at most
one best route
eugeneng at cs.rice.edu
Rice University 14
Example: Multiple AS Paths
AS9 128.2/16
AS701
128.2/16
9 701
AS7018
128.2/16
9 7018 1239
AS1239
AS73
Default choice: Pick shortest path
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 15
Shorter Doesn’t Always Mean better
Is path 4 1 better
than path 3 2 1?
AS 4
AS 3
AS 2
AS 1
AS can use custom policies other than shortest path
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 16
Benefits of BGP Design
• Path Vector style routing
– Distance vector algorithm with extra information
– For each route, store the complete path (ASs)
• Advantages:
– can make policy choices (choose among many possible
learned paths) based on set of ASs in path
– can easily avoid loops
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 17
Announcing and Choosing Routes
• BGP may learn many different paths for a destination
network
• Learns only reachability information, no performance
metrics
– Not about optimizing anything
– All about policy (business and politics)
• What a BGP speaker announces or not announces to
a neighbor determines what routes may get used by
that neighbor
• Router chooses among paths based on policy
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 18
Nontransit vs. Transit ASes
ISP 2
ISP 1
Traffic NEVER
flows from ISP 1
through NET A to ISP 2
(At least not intentionally!)
NET A
Internet Service
providers (often)
are transit
networks
Nontransit AS
might be a corporate
or campus network.
IP traffic
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 19
Selective Transit
NET B
NET A provides transit
between NET B and NET C
and between NET D
and NET C
NET C
NET A
NET A DOES NOT
provide transit
Between NET D
and NET B
NET D
IP traffic
Most transit networks transit in a selective manner…
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 20
Customers and Providers
provider
provider
customer
customer
IP traffic
Customer pays provider for access to the Internet
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 21
The Peering Relationship
peer
provider
Peers provide transit between
their respective customers
peer
customer
Peers do not provide transit
between peers
traffic
allowed
T. S. Eugene Ng
traffic NOT
allowed
Peers (often) do not exchange $$$
eugeneng at cs.rice.edu
Rice University 22
Peering Provides Shortcuts
Peering also allows connectivity between
the customers of “Tier 1” providers.
T. S. Eugene Ng
eugeneng at cs.rice.edu
peer
provider
peer
customer
Rice University 23
Import Routes
provider route
peer route
From
provider
customer route
From
provider
From
peer
From
peer
From
customer
T. S. Eugene Ng
ISP route
From
customer
eugeneng at cs.rice.edu
Rice University 24
Export Routes
provider route
peer route
To
provider
customer route
From
provider
To
peer
To
peer
To
customer
T. S. Eugene Ng
ISP route
To
customer
eugeneng at cs.rice.edu
filters
block
Rice University 25
How can routes be marked as “provider”,
“peer”, “customer”, “isp” ?
Use “Community Attribute” in route announcement
A community attribute is 32 bits
By convention,
first 16 bits is
ASN indicating
who is giving it
an interpretation
T. S. Eugene Ng
community
number
Used for signaling
within and between
ASs
Very flexible
BECAUSE it
has no predefined
meaning
eugeneng at cs.rice.edu
Rice University 26
BGP Issues
• BGP designed for policy not performance
• Susceptible to router misconfiguration
– Blackholes: announce a route you cannot reach
• Slow convergence time
– Rate limiting and route flap dampening
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 27
Combining IGP and BGP
IGP Process
BGP Process
IGP Routing tables
BGP Routing tables
OS kernel
Forwarding Table Manager
Forwarding Table
T. S. Eugene Ng
eugeneng at cs.rice.edu
Rice University 28
Combine BGP and IGP Tables to Create Forwarding Table
I-BGP: 135.207.0.0/16
Next Hop = 192.0.2.1
135.207.0.0/16
E-BGP
10.10.10.10
IGP
destination
next hop
192.0.2.0/30
AS 1
192.0.2.1
AS 2
192.0.2.0/30
10.10.10.10
Forwarding Table
destination
next hop
+
BGP
destination
next hop
135.207.0.0/16
192.0.2.1
T. S. Eugene Ng
135.207.0.0/16
192.0.2.0/30
eugeneng at cs.rice.edu
10.10.10.10
10.10.10.10
Rice University 29