Transcript BGP

Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet
Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Recall: Subnets
223.1.1.2
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
IP addressing: CIDR
CIDR: Classless InterDomain Routing
subnet portion of address of arbitrary length
 address format: a.b.c.d/x, where x is # bits in
subnet portion of address

Subnet part or
CIDR-block
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
IP addresses: how to get one?
Q: How does network get subnet part of IP
addr?
A: gets allocated portion of its provider ISP’s
address space
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
Hierarchical addressing: route aggregation
Hierarchical addressing allows efficient advertisement of routing
information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
ISP1
“Send me anything
with addresses
beginning
200.23.16.0/20”
Border Router
200.23.30.0/23
ISP2
“Send me anything
with addresses
beginning
199.31.0.0/16”
This way, the whole 32 bit address does not need to be examined
Internet
Hierarchical addressing: more specific
routes
ISP2 has a more specific route to Organization 1
Organization 0
200.23.16.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
ISP1
“Send me anything
with addresses
beginning
200.23.16.0/20”
Border Router
200.23.30.0/23
ISP2
Organization 1
200.23.18.0/23
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
Internet
Longest prefix matching
Border Router Forwarding Table
Prefix Match
200.23.16.0/20
200.23.18.0/23
199.31.0.0/16
otherwise
Link Interface
0
1
1
2
If a packet with destination address 200.23.18.12 arrives at the boarder
router, then is it forwarding to interface 0 or 1?
Since interface 1 has a longer match, it goes to interface 1
A Problem with Longest Match and subnetting
In order to improve reliability, organization 7 has a backup link with ISP1.
This way, if ISP1 has problems or ISP1’s provider has problems, then
organization 7 is still reachable.
Will this work?
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
ISP1
“Send me anything
with addresses
beginning
……”
Border Router
200.23.30.0/23
ISP2
“Send me anything
with addresses
beginning
…..
Internet
Hierarchical Routing
Our routing study thus far - idealization
 all routers identical
 network “flat”
… not true in practice
scale: with 200 million destinations:

can’t store all dest’s in routing tables!

Memory for address table must be very fast
•

How fast? How long can an address lookup
take on a 10GBit interface?
routing table exchange would swamp links!

There are ~ 1 million links

If link state was exchanged every 10
seconds and each link state is 20B, then
each router receives and processes
160Mbps in link announcements

But, perhaps, only changes in link state
could be distributed.
administrative autonomy


internet = network of networks
each network admin wants to control
routing in its own network

ATT does not want sprint to know what
their topology is
•
•

Trade secret
Improves security
ATT wants to select a routing protocol and
parameters without getting sprints
permission
Hierarchical Routing
aggregate routers into regions,
“autonomous systems” (AS)
 Single administrative domain
 Routers in the same AS run same
routing protocol




“intra-AS” routing protocol
routers in different AS can run
different intra-AS routing
protocol
An ISP may be made of 1 or more
ASs


ATT-USA = 1 AS and ATT-Europe
is another
Some stub networks are an AS
•
•
UD is an AS
Some companies have routers but
are not Ass
ASs have their own number,
assigned by ICANN
 There are ~50K ASs

Gateway router
 Direct link to router in another
AS
 Gateway routers run a common
inter-networking routing protocol
 For inter-AS routing, the
destinations are always ASs

Actually, destinations are always
ASs. But for inter-AS routing, it
does not make much sense for a
destination to be a single endhost.
Simple example
Connections to other ASs and the rest of the Internet
AS2
Service provider of AS1 (e.g., AS1=UD and AS2=cogent)
E
(Recall that ASs (ISPs) sometiems
meet at NAPs. E.g., google: MAEEast)
An AS could also meet its provider
at a POP.
The rest of the internet
Stub network (at the edge of the network)
These tables are made with RIP, OSPF, ISIS, etc
B
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
A
AS1
A
C
10.1.1.0/24
A
10.1.1.1/24
10.1.4.0/22
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
A
Q: How can routers in AS1 know
where to send pkts with
destination not in AS1?
A: Easy, if a pkt is for an “unknown”
address, send it to B.
Specifically, B advertises a link
to prefix 0.0.0.0/0
This is called a default route,
and it can be statically set (no
need for any routing protocol
beside OSPF)
AS2
Service provider of AS1 (e.g., AS1=UD and AS2=cogent)
E
The rest of the internet
Stub network (at the edge of the network)
These tables are made with RIP, OSPF, ISIS, etc
B
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
0.0.0.0/32
A
A
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
A
0.0.0.0/32
E
AS1
C
10.1.1.0/24
A
10.1.1.1/24
10.1.4.0/22
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
A
0.0.0.0/32
A
We need to put prefixes 1.1.0.0/16, 1.2.0.0/16, 2.2.0.0/16 in the forwarding tables
Specifically, B should announce to A that is can reach 1.1.0.0/16 and 1.2.0.0/16, and D should announce it can reach 2.2.0.0/16
How to get there?
1.
B must learn from E that 1.1.0.0/16 and 1.2.0.0/16 are reachable through E
2.
A must learn that 2.2.0.0/16 is reachable through D
3.
B and A must distribute this information throughout AS1
But 1 and 2 need a exterior inter-networking routing protocol
3 need interior inter-networking routing protocol
EBGP and IBGP – border gateway routing protocol can accomplish this
1.2.0.0/16
1.1.0.0/16
AS2
E
These tables are made with RIP, OSPF, ISIS, etc
B
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
A
AS1
A
C
10.1.1.0/24
A
10.1.1.1/24
Forwarding table
Prefix
Next hop
10.1.1.0/23
C
10.1.2.0/22
A
10.1.4.0/22
D
AS3
2.2.0.0/16
Interconnected ASes
3c
3a
3b
AS3
1a
2a
1c
1d
1b
Intra-AS
Routing
algorithm
2c
AS2
AS1
Inter-AS
Routing
algorithm
Forwarding
table
2b
 forwarding table
configured by both
intra- and inter-AS
routing algorithm


intra-AS sets entries
for internal dests
inter-AS & intra-As
sets entries for
external dests
Example: Setting forwarding table in router 1d
 suppose AS1 learns (via inter-AS protocol) that subnet
x reachable via AS3 (gateway 1c) but not via AS2.
 inter-AS protocol propagates reachability info to all
internal routers.
 router 1d determines from intra-AS routing info that
its interface I is on the least cost path to 1c.
 installs forwarding table entry (x,I)
x
3c
3a
3b
AS3
1a
2a
1c
1d
1b AS1
2c
2b
AS2
Example: Choosing among multiple ASes
 now suppose AS1 learns from inter-AS protocol that subnet x
is reachable from AS3 and from AS2.
 to configure forwarding table, router 1d must determine
towards which gateway it should forward packets for dest x.
 this is also job of inter-AS routing protocol!
 If both gateways are equivalent, then the intra-AS routing
protocol will route packets to the best gateway
• This is called hot potato routing: send packet towards closest of two
routers.
x
3c
3a
3b
AS3
1a
2a
1c
1d
1b
2c
AS2
AS1
2b
Hot Potato Routing
128.4.0.0/16
AS1
A
AS2
B
Pkt arrives with dest in 124.4.0.0/16
AS2 could give send the pkt to gateway B – hot potato routing.
But AS1 would prefer AS2 to carry its own traffic.
So AS1 might require that AS2 gives higher priority to gateway A.
In which case, AS1 could inject traffic into AS2 with destination in 128.4.0.0/16 at gateway B
Example: Choosing among multiple ASes
 now suppose AS1 learns from inter-AS protocol that
subnet x is reachable from AS3 and from AS2.
 to configure forwarding table, router 1d must
determine towards which gateway it should forward
packets for dest x.
 this is also job of inter-AS routing protocol!
 hot potato routing: send packet towards closest of
two routers.
Learn from inter-AS
protocol that subnet
x is reachable via
multiple gateways
Use routing info
from intra-AS
protocol to determine
costs of least-cost
paths to each
of the gateways
Hot potato routing:
Choose the gateway
that has the
smallest least cost
Determine from
forwarding table the
interface I that leads
to least-cost gateway.
Enter (x,I) in
forwarding table
Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): the de
facto standard
 BGP provides each AS a means to:
1.
2.
3.
Obtain subnet reachability information from
neighboring ASs.
Propagate reachability information to all ASinternal routers.
Determine “good” routes to subnets based on
reachability information and policy.
 allows subnet to advertise its existence to
rest of Internet: “I am here”
BGP basics
 pairs of routers (BGP peers) exchange routing info
over semi-permanent TCP connections: BGP sessions
 BGP sessions need not correspond to physical
links.
 when AS2 advertises a prefix to AS1:
 AS2 promises it will forward datagrams towards
that prefix.
 AS2 can aggregate prefixes in its advertisement
• But this can cause problems when some prefixes have
backup links
eBGP session
3c
3a
3b
AS3
1a
AS1
iBGP session
2a
1c
1d
1b
2c
AS2
2b
Distributing reachability info
 using eBGP session between 3a and 1c, AS3 sends
prefix reachability info to AS1.
 1c can then use iBGP do distribute new prefix
info to all routers in AS1
 1b can then re-advertise new reachability info
to AS2 over 1b-to-2a eBGP session
 when router learns of new prefix, it creates entry
for prefix in its forwarding table.
eBGP session
3c
3a
3b
AS3
1a
AS1
iBGP session
2a
1c
1d
1b
2c
AS2
2b
Path attributes & BGP routes
 advertised prefix includes BGP attributes.
 prefix + attributes = “route”
 two important attributes:
 AS-PATH: contains ASs through which prefix
advertisement has passed: e.g, AS 67, AS 17
 NEXT-HOP: indicates specific internal-AS router
to next-hop AS. (may be multiple links from
current AS to next-hop-AS)
 when gateway router receives route
advertisement, uses import policy to
accept/decline.
BGP route selection
 router may learn about more than 1 route
to some prefix. Router must select route.
 elimination rules:
1.
2.
3.
4.
local preference value attribute: policy
decision
shortest AS-PATH
closest NEXT-HOP router: hot potato routing
additional criteria
BGP messages
 BGP messages exchanged using TCP.
 BGP messages:
OPEN: opens TCP connection to peer and
authenticates sender
 UPDATE: advertises new path (or withdraws old)
 KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
 NOTIFICATION: reports errors in previous msg;
also used to close connection

BGP routing policy
legend:
B
W
X
A
provider
network
customer
network:
C
Y
 A,B,C are provider networks
 X,W,Y are customer (of provider networks)
 X is dual-homed: attached to two networks
X does not want to route from B via X to C
 .. so X will not advertise to B a route to C

BGP routing policy (2)
legend:
B
W
X
A
provider
network
customer
network:
C
Y
 A advertises path AW to B
 B advertises path BAW to X
 Should B advertise path BAW to C?
 No
way! B gets no “revenue” for routing CBAW
since neither W nor C are B’s customers
 B wants to force C to route to w via A
 B wants to route only to/from its customers!
BGP route processing


BGP advertises and withdraws paths with the UPDATE message
UPDATE has three fields





Router to withdraw
Attributes of routes to prefixes in NLRI
NLRI
The NLRI is a list of prefixes that the list of attributes applies to. If two prefixes
have different attributes, then these two prefixes need to be announced with
different UPDATE messages.
In OSPF each path is a list of routes and a total cost (two attributes). In BGP, routes
have many attributes, cost (in AS hops) is but one.
configuration
from
peers
input
policy routing
engine decision
configuration
routing
table
output
policy
engine
to
peers
RIBs
 Routing information base (RIB) – a list of routes (attributes and all)
 Adj-RIB-In: RIB learned from neighbor (many of these)
 Adj-RIB-Out: RIB to be sent to neighbor (many of these)
 Loc-RIB: RIB for local use (only one of these)
peer
Adj-rib-in
Adj-rib-out
peer
Adj-rib-in
Adj-rib-out
peer
Adj-rib-out
peer
Adj-rib-out
peer
peer
Adj-rib-in
peer
Adj-rib-in
Input
Policy
engine
BGP
Loc-RIB
decision
Input
Policy
engine
peer
Sample routing environment
•deny 0/0 from AS1
•Give 192.213.1.0/24 form
AS1 better preference
•Accept other routes
AS1
192.213.1.0/24
0/0
AS2
input
policy
engine
192.213.1.0/24
193.214.10.0/24
0/0
decision
process
•Do not propagate 0/0
•Do not send 193.214.10.0/24 to AS4
•Give 192.213.1.0/24 with metric = 10
to AS3
routes
•Use 0/0 from AS2
•Use 192.213.1.0/24 from AS1
•Use 193.214.10.0/24 from AS2
•Use 172.16.10.0/24 from AS5 (this
AS)
output
policy
engine
AS3
•193.214.10.0/24 path=(AS5, AS2)
•192.213.1.0/24 path=(AS5, AS1)
metric=10
•172.16.10.0/24 path=(AS5)
•172.16.10.0/24 path=(AS5)
•192.213.1.0/24 path=(AS5 AS1)
AS4
Fun with BGP
 Routeviews.org collects and archives BGP
announcements
 One way to use routeviews is with dig



At the linux prompt
dig txt 4.128.aspath.routeviews.org
Outputs various stuff and
• Answer section:
– 4.128.aspath.routeviews.org 600 IN TXT “5056 1238 174 34”
“128.4.0.0” “16”
• Syntax = ASPath “Prefix” “prefix length”
 Now use whois -h whois.arin.net "a ASXX" to learn
about ASs where XX is an AS number. E.g., whois h whois.arin.net "a AS34" gives information about
AS34
 Try with some other AS
Check out a collection of path
announcements

Open bgp030408p39.Partial



http://www.eecis.udel.edu/~bohacek/Classes/ELEG651Spring2008/bgp030508p39.Partial
An old (2003) partial list of BGP announcements received by several routers
Check which ASs peer with UD (ASN 34)
Why different Intra- and Inter-AS routing ?
Policy:
 Inter-AS: admin wants control over how its traffic
routed, who routes through its net.
 Intra-AS: single admin, so no policy decisions needed
Scale:
 hierarchical routing saves table size, reduced update
traffic
Performance:
 Intra-AS: can focus on performance
 Inter-AS: policy may dominate over performance