Transcript Introduction to Internet Routing

Introduction to BGP
Lixin Gao
ECE Dept.
UMASS, Amherst
7/16/2015
ECE697F: Special Topics-Internet Routing
1
Border Gateway Protocol (BGP)


Dynamic Inter-AS Routing Protocol
Goals:
 Exchange reachability information between ASes
 Apply


local policies for
selecting route
receiving and announcing route
ECE697F: Special Topics-Internet Routing
2
BGP Sessions



Used for Exchange Reachability Information
iBGP : fully meshed, might not directly connected,
 Alternative to fully meshed: confederation, route reflector
eBGP
eBGP
iBGP
AS701
AS7018
AS1
ECE697F: Special Topics-Internet Routing
3
Route Information Exchange

Route Announcement

Local Policies
1.2.0.0/16 (1)
1.2.0.0/16 (7018,1)
eBGP
iBGP
AS701
1.2.0.0/16 (1)
1.2.0.0/16 (1)
1.2.0.0/16 (7018,1)
1.2.0.0/16 (7018,1)
1.2.0.0/16 ( )
AS7018
1.2.0.0/16 (1)
AS1
1.2.0.0/16 (1)
1.2.0.0/16
ECE697F: Special Topics-Internet Routing
4
Route Announcement


Network Prefix: 12.0.0.0/8
Attributes: for reaching network prefix
 AS path
 Next hop : next hop IP addr
 Local Preference
 Multiple Exit Discriminator (MED)
 Community Set
 Origin code
 Atomic Aggregate
 Aggregator
ECE697F: Special Topics-Internet Routing
 …..
5
AS Path




Sequence of ASes traversed
Loop avoidance
Path selection: Path Length
Policy: AS7018 in AS path is more preferred
ECE697F: Special Topics-Internet Routing
6
Next Hop



Next hop IP address to reach network prefix
EBGP: next hop IP addr of announcer
iBGP
 From same AS:IP address of announcer
 From diff AS: next hop unchanged
AS7018
AS1
2.3.4.1
3.4.5.2
1.2.0.0/16 (1) 2.3.4.1
1.2.0.0/16 (1) 2.3.4.1
1.2.0.0/16
1.2.0.0/16 ( ) 3.4.5.2
ECE697F: Special Topics-Internet Routing
7
Next hop

Determine next hop in forwarding table
 Combing Inter-AS and Intra-AS routing table
 Recursive route lookup
 BGP abstract topology in AS level
ECE697F: Special Topics-Internet Routing
8
Local Preference


Local to AS
 carry in iBGP session but not eBGP session
Used to influence path selection
 Select the highest Local Pref path
eBGP
iBGP
AS701
1.2.0.0/16 (1) 100
1.2.0.0/16 (1) 100
1.2.0.0/16 (7018,1) 200
1.2.0.0/16 (7018,1) 200
1.2.0.0/16 ( ) 300
AS7018
1.2.0.0/16 (1) 90
AS1
1.2.0.0/16 (1) 90
1.2.0.0/16
ECE697F: Special Topics-Internet Routing
9
Multiple Exit Discriminator (MED)


Used for path selection
 select an entry point among several to an AS
(smaller MED is preferred)
 meaningful among paths from the same AS
 may use Intra-AS routing cost metrics
AS701
Non-transitive
1.2.0.0/16 (1) 200
1.2.0.0/16 (1) 100
AS1
1.2.0.0/16
ECE697F: Special Topics-Internet Routing
10
Community Set


Used for grouping destination
Simplify policy setting
AS701
1.2.0.0/16 (1) 1000
1.2.0.0/16 (1) 1000
3.0.0.0/18 (7018) 1000
3.0.0.0/16 (7018) 1000
3.0.0.0/8
AS7018
AS1
1.2.0.0/16
ECE697F: Special Topics-Internet Routing
11
Origin Code



IGP
 interior to the originating AS.
EGP
 learned via EGP (Exterior Gateway Protocol)
Incomplete
 unknown
ECE697F: Special Topics-Internet Routing
12
Atomic Aggregate

Aggregation that loses
information
ECE697F: Special Topics-Internet Routing
13
Aggregator


Optional
For route that is an aggregation
ECE697F: Special Topics-Internet Routing
14
Announcement Processing



Input Policy Engine
 Receive from neigboring Ases new announcements
 Attribute Manipulation and Filter announcement
 Store announcements (Incremental protocol)
Path Selection among announcements
Output Policy Engine
 Attribute Manipulation
 Send to neighboring Ases new announcements
ECE697F: Special Topics-Internet Routing
15
Input Policy Engine



Set local preference
Filter routes with the same AS number (loop
avoidance)
Filter bogus routes
ECE697F: Special Topics-Internet Routing
16
Path Selection Process







For each prefix,
Prefer largest Local Preference
Prefer route this router originates
Prefer shorter AS path
prefer the lowest origin code (IGP<EGP<INCOMPLETE).
Prefer path with lowest MED
Prefer route with lowest IP addr
ECE697F: Special Topics-Internet Routing
17
Output Policy Engine







Send to neighbors only the best path
Send to neighbors only the best path changes
Set MED
Set Community set
Set Atomic Aggregate
Set next hop
Append AS number
ECE697F: Special Topics-Internet Routing
18
Routing Information Storage



Adj-RIBs-In
 routes received
 Input to route selection
Loc-RIB
 Routes selected by selection process
 Output of route selection
Adj-RIBs-Out
 announcements to neighbor
 Output of Output Policy Engine
ECE697F: Special Topics-Internet Routing
19
BGP Session Implementation




OPEN message
 establish TCP session
KEEPALIVE message
 keep session going
Update message
 announcement or withdrawal
Notification message
 error in announcement
ECE697F: Special Topics-Internet Routing
20