Transcript Border Gateway Protocol (BGP4)

Unicast Routing Protocols
1
Outline




Routing basic
RIP
OSPF
BGP
2
Routing Basic





IP Routing
Autonomous System (AS)
IGP/EGP
Distance-vector(DV)/Link-state(LS)
How routing protocol works?
3
IP Routing

Route entry






Destination/netmask
Nexthop
Longest-match
Default-route
Equal Cost Multipath Protocol(ECMP)
Static routing/Dynamic routing
4
Autonomous System (AS)
AS 100




Collection of networks with same policy
Usually under single administrative control
IGP to provide internal connectivity
Identified by a short number

Public & Private AS numbers


public: 1 - 64511
private: 64512 – 65535
5
What Is an IGP?




Interior Gateway Protocol
Within an Autonomous System
Carries information about internal
prefixes
Examples—

RIP, OSPF, ISIS…
6
What Is an EGP?




Exterior Gateway Protocol
Used to convey routing information
between ASes
Independent from the IGP
Current EGP is BGP4
7
Why Do We Need an EGP?

Scaling to large network




Hierarchy
Limit scope of failure
Define administrative boundary
Policy

Control reachability to prefixes
8
Hierarchy of Routing Protocols
Other ISP’s
BGP4
BGP4 / IGP
BGP4
BGP4/Static
Customers
Customers
9
Distance-vector (Bellman-Ford)

Routers only know their local state


link metric and neighbor estimates
Examples –

RIP, BGP (path-vector)
10
Link-state

Routers have knowledge of the
global state



topology database
global optimization (Shortest Path First
- Dijkstra)
Examples –

OSPF, ISIS
11
How Routing Protocol works?


Neighbor Discovery
Route Exchange between neighbors



learning/flooding/invalidation/refresh
Best route choice and routing table
management
Responsibility




Fast convergence and loop-free
Scalability
Robustness
Some control of routing choices
12
Routing Information Protocol (RIP)




RIP basic
General operation
RIP v2 VS RIP v1
Conclusion
13
RIPv2 basic


Distance-vector protocol
Metric – hops



Metric is increased when routes are
updated to neighbors
Network span limited to 15 (16 means
unreachable)
Encapsulated as UDP packets, port
520
14
RIPV2 General operation






On startup, send request on all interfaces.
When a request is received, a response is sent.
- Response contains entire routing table.
A response is also gratuitously sent every 30s.
– Response contains entire routing table.
A response is also sent when update detected.
- Response only contains changed routes.
Route metric is set to 16 when network
becomes inaccessible or not refreshed during 6
update periods(180s)
Invalid routes are flushed after another 4
update periods(120s)
15
Count of infinity

What happens when a link dies?
A
B
C
A: 0
B: 1, B
C: 2, B
A: 1, A
B: 0
C: 1, C
A: 2, B
B: 1, B
C: 0
A: 0
B: 1, B
C: 2, B
A: 1, A
B: 0
C: 3, A
A: 2, B
B: 1, B
C: 0
A: 0
B: 1, B
C: 4, B
A: 1, A
B: 0
C: 3, A
A: 2, B
B: 1, B
C: 0
A: 0
B: 1, B
C: 15, B
A: 1, A
B: 0
C: 16, A
A: 2, B
B: 1, B
C: 0
16
Split horizon
To speed up convergence
 Simple
- do not claim reachability for a
destination network to the neighbor
from which the route was learned.
 Poison
reverse
- includes such routes in updates, but
sets their metrics to infinity
17
Split horizon - simple
A
B
C
A: 0
B: 1, B
C: 2, B
A: 1, A
B: 0
C: 1, C
A: 2, B
B: 1, B
C: 0
A: 0
B: 1, B
C: 16, B
A: 1, A
B: 0
C: 16
A: 2, B
B: 1, B
C: 0
18
Split horizon – poison reverse
A
A: 0
B: 1, B
C: 2, B
A: 0
B: 1, B
C: 16, B
B
C: 16
C
A: 1, A
B: 0
C: 1, C
A: 2, B
B: 1, B
C: 0
A: 1, A
B: 0
C: 16
A: 2, B
B: 1, B
C: 0
19
RIPv2 vs RIPv1



224.0.0.9 - broadcast
Variable Length Subnet Mask(VLSM)
- Classless Inter-Domain
Routing (CIDR, no prefix/subnet
information, derived from address
class)
Authentication - none
20
Conclusion



Simplicity
Slow convergence
Not suited for large and complex
networks
21
Open Shortest Path First (OSPF)






OSPF Basic
OSPF Neighbors
OSPF Area
SPF and LSA database
OSPF Messages
Conclusion
22
OSPF Basic


Encapsulated as RAW IP packets,
protocol ID 89
Uses metrics—path cost(1–65,535)
23
OSPF Basic - general operation





Use Hello Protocol to establish neighbors
All routers exchange Link State Advertisement
(LSA) to build and maintain a consistent database
Each router runs SPF on LSA database
independently and gets optimal routes
Periodic flooding of LSAs every 30 minutes
LSA age




0 when created
Incremented as time elapsed.
Max age 3600 indicates invalid
Remove a LSA by incrementing age to 3600,
reflooding and flushing.
24
OSPF Network type



Broadcast
Point-to-Point/Point-to-Multipoint
NBMA(Non-Broadcast Multiple
Access)
25
Neighbor discovery

Hello packets

Periodically Multicasting 224.0.0.5,
including



RouterId, AreaId, Netmask, hello interval,
Priority, DR, BDR, Neighbor list
Neighbor state machine
Works differently on different network
26
DR/BDR/Others



For broadcast and NBMA networks
Optimize the flooding procedure
Designated Router(DR)




Backup Designated Router(BDR)



Adjacent to all routers
Describe all routers on the network
Send updates to all routers on the network
Adjacent to all routers
Act as new DR when previous DR fails
Others

Only adjacent to DR/BDR, only send updates
to DR/BDR
27
OSPF Area

Why divide the network into different
areas?





32 bit number
Backbone area – area 0 or 0.0.0.0




Limit the scope of updates and computational
overhead
independent SPF computing in each area
inject aggregated information on routes into
other areas
All areas must connect to backbone area.
Backbone area must be continuous
Virtual link when the above fails
Area Border Routers(ABR)
28
Virtual Link
Area 0
Area 1
ABR
ABR
Virtual link
Area 2
ABR
Area 3
29
Shortest Path First
3
A
B
1
C
10
7
4
D
30
Candidat
e
Root
cost
SPF tree
Description
A, A, 0
Root tree
A, B, 3
A, C, 1
A, D, 10
3
1
10
A, A, 0
Add adjacent links to A into Candidate and
calculate cost to A.
A, B, 3
A, D, 10
C, D, 7
3
10
8
A, A, 0
A, C, 1
Choose the lowest cost link (A, C, 1),
add it into SPF tree and remote it from Candidate.
Add adjacent links to C into Candidate and
calculate cost to A. Because the new lowest cost to
D is 8, <A, D, 10> is remoted.
C, D, 7
B, D, 4
8
7
A, A, 0
A, C, 1
A, B, 3
Choose the lowest cost link(A, B, 3),
Add it into SPF tree and remote it from Candidate.
Add adjacent links to B into Candidate and
calculate cost to A. because the new lowest cost to
D is 7, <C, D, 7> is removed.
A,
A,
A,
B,
Choose the lowest cost link(B, D, 4),
Add it into SPF tree and remote it from Candidate.
Because the Candidate is empty, the process is
over.
A, 0
C, 1
B, 3
D, 4
31
OSPF SPF process


SPF calculation is performed
independently for each area
Router LSA



Each router creates a router LSA for each area
Describe links to an area
 DR/BDR(broadcast)
 Neighboring router(point-to-point)
 Prefix/mask(stub network)
 metric
Network LSA


Only DR creates a network LSA for a network
Describe all routers on the network
32
Inter-area routes

Network Summary LSA


Created by ABR
Advertise optimal routes in one area
into another area
Prefix/mask
 Metric


Flood only in one area
33
Inter-AS routes


Autonomous System Border Router(ASBR)
Autonomous System External LSA




Created by ASBR
Describe routes redistributed from other AS
 Prefix/mask
 Metric
Flood across area in an AS(except stub area)
ASBR summary LSA


Created by ABR
Describe ASBR routers in one area
 ASBR router id
 metric
34
Stub area


AS External LSA are forbidden in
stub area
Why stub area?



When many networks are connected
only via one router
All external networks aggregated into
default route
Reduce routing table sizes
35
OSPF Messages

Hello


Database description


Used to request LSAs
Link-state update


Used to describe brief information of LSA
Link-state request


Used to establish neighbor relationship
Used to update LSAs
Link-state acknowledgment

Used to assure LSA flooding reliable by
including brief description of received LSA
36
Conclusion



2-level hierarchical model
Faster convergence
Relatively low, steady state bandwidth
requirements
37
Border Gateway Protocol (BGP)








BGP Basic
BGP Peers
BGP Updates – NLRI and Path Attributes
Synchronization with IGP
Route Reflector and AS Confederation
Routing policy
BGP Messages
Conclusion
38
BGP Basic





Based on TCP connection, port 179
BGP peer is configured manually
BGP Peers exchange
Update messages containing Network
Layer Reachability Information (NLRI)
Path attributes are with NLRI to avoid
loop and facilitate policy control
No routes refresh
39
BGP Peers - eBGP
eBGP
A
C
AS 101
AS 100
220.220.16.0/24
220.220.8.0/24
B
eBGP
Peers in different AS’s
are called External Peers
D
eBGP
E
AS 102
220.220.32.0/24
eBGP TCP/IP
Peer Connection
Note: eBGP Peers normally should be directly connected.
40
BGP Peers - iBGP
A
AS 100
C
iBGP
iBGP
AS 101
220.220.16.0/24
220.220.8.0/24
B
D
E
Peers in the same AS
are called Internal Peers
iBGP TCP/IP
Peer Connection
AS 102
220.220.32.0/24
Note: iBGP Peers don’t have to be directly connected. Loopback
interface are normally used as peer connection end-points.41In
this case, recursive route look-up is needed.
Full mesh
AS 100
A
C
B
D
 Each
iBGP speaker must peer with every other
iBGP speaker in the AS (full mesh)
 IBgp speaker never floods routes received from
another iBGP peer to any other iBGP peer.
42
BGP Updates — NLRI



Network Layer Reachability
Information
Used to advertise feasible routes
Composed of:


Network Prefix
Mask Length
43
BGP Updates — Path Attributes

Used to convey information
associated with NLRI









Origin - mandatory
AS path - mandatory
Next hop - mandatory
Local preference
Multi-Exit Discriminator (MED)
Community
Origin
Aggregator
Rich policy control
44
Origin

Conveys the origin of the prefix

Three values:




IGP - Generated using “network” statement
 ex: network 35.0.0.0
EGP - Redistributed from EGP
Incomplete - Redistribute IGP
 ex: redistribute ospf
IGP < EGP < INCOMPLETE
45
AS-Path Attribute



Sequence of ASes a
route has traversed
Loop detection
Apply policy
AS 300
AS 200
AS 100
170.10.0.0/16
180.10.0.0/16
Network
Path
180.10.0.0/16 300 200 100
170.10.0.0/16 300 200
AS 400
150.10.0.0/16
AS 500
Network
180.10.0.0/16
170.10.0.0/16
150.10.0.0/16
Path
300 200 100
300 200
300 400
46
AS-Path Loop detection


AS 200
AS 100
170.10.0.0/16
180.10.0.0/16
Sequence of ASes a route has
traversed
Loop detection
AS 300
180.10.0.0/16
dropped
AS 400
150.10.0.0/16
AS 500
180.10.0.0/16
170.10.0.0/16
150.10.0.0/16
300 200 100
300 200
300 400
47
Next Hop Attribute
AS 200
AS 300
140.10.0.0/16
192.10.1.0/30
C
150.10.0.0/16
.1
.2
D
E
Network
Next-Hop
150.10.0.0/16 192.10.1.1
160.10.0.0/16 192.10.1.1
B
.2
Path
200
200 100
192.20.2.0/30
Network
Next-Hop
150.10.0.0/16 192.10.1.1
160.10.0.0/16 192.10.1.1
.1
A
Network
Next-Hop
160.10.0.0/16 192.20.2.1
Path
200
200 100
Path
100
AS 100
160.10.0.0/16

Next hop to reach a network
Usually a local network is the next hop in
eBGP session
Next Hop updated between eBGP Peers

Next hop not changed between iBGP peers
48


BGP Update
Messages
Local Preference
AS 100
160.10.0.0/16
AS 200
AS 300
D
Multi-homed AS
500
• Only for iBGP
• Local to an AS
• Path with highest
local preference wins
E
A
B
AS 400
800
C
160.10.0.0/16
> 160.10.0.0/16
500
800
49
Multi-Exit Discriminator (MED)
AS 200
C
preferred
192.68.1.0/24
2000
192.68.1.0/24
A
• Used to convey the relative
preference of entry points
• Comparable if paths are from
the same AS
• Path with lower MED wins
• IGP metric can be conveyed as
MED
1000
B
192.68.1.0/24
AS 201
50
Communities
Service Provider AS 200
C
Local Preference
110
120
D
Community:201:110
Community:201:120
A
•Used to group destinations
•Each destination could be
member of multiple
communities
•Flexibility to scope a set of
prefixes within or across AS
for applying policy
Community
201:110
201:120
B
192.68.1.0/24
Customer AS 201
51
BGP Updates —
Withdrawn Routes


Used to “withdraw” network reachability
Each Withdrawn Route is composed of:


Network Prefix
Mask Length
52
Synchronization with IGP
1880
C
A
D
OSPF
690
35/8
209
B



C not running BGP (non-pervasive BGP)
A won’t advertise 35/8 to D until the IGP is in
sync
Turn synchronization off!

Run pervasive BGP
53
Alternative to Full Mesh –
Router-reflection
AS 100
RR
Client
Client






Route Reflector (RR)
Client peers
Non-client peers
Non-client
Non-client
Non-client peers are full-mesh connected
RR reflects routes from non-client peers to all client peers
RR reflects routes from client peers to all non-client peers and other
client peers
54
Alternative to Full Mesh –
Confederation
Member-AS 65531
Member-AS 65532
AS Confederation 100
•Divided into member AS, marked by private AS number
•Full-mesh in member AS
•Peers between member AS are most similar with eBGP, except that
inserted AS path is confederation AS path
•When routes get out of AS confederation, remove confederation AS
path
55
Routing Policy

Why?




To steer traffic through preferred paths
Inbound/Outbound prefix filtering
To enforce Customer-ISP agreements
How ?



AS based route filtering - filter list
Prefix based route filtering - distribute list
BGP attribute modification - route maps
56
BGP Messages

OPEN


UPDATE


To exchange routing information(NLRI,
Path attributes, Withdrawn routes)
KEEPALIVE


To negotiate and establish peering
To maintain peering session
NOTIFICATION

To report errors (results in session reset)
57
Conclusion



The single extant protocol for interdomain
routing
Fundamentally simple algorithms but can
provide complex and flexible policy
control
More future applications, such as
BGP/MPLS VPN networks
58