Border Gateway Protocol (BGP4)
Download
Report
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