Inter-domain Routing
Border Gateway Protocol
Original idea
Copyright By PowCoder代写 加微信 powcoder
Internet Structure
Internet Structure
Route Propagation in the Internet
• AutonomousSystem(AS)
– corresponds to an administrative domain
– examples: University, company, backbone network – assign each AS a 16-bit number
• Two-level route propagation hierarchy
– interior gateway protocol (each AS selects its own) – exterior gateway protocol (Internet-wide standard)
• Routes information is propagated at various levels – hosts know local router
– local routers know site routers
– site routers know core router
– core routers know everything
Popular Interior Gateway Protocols
RIP: Route Information Protocol
– distributed with BSD Unix
– distance-vector algorithm
– based on hop-count (infinity set to 16)
OSPF: Open Shortest Path First – uses link-state algorithm
– supports load balancing
– supports authentication
BGP-4: Border Gateway Protocol
• BGP-1 developed in 1989 to address problems with EGP.
• Assumes Internet is an arbitrarily interconnected set of ASs
• AS traffic types
• starts or ends within an AS
• passes through an AS
• AS Types
– stub AS: has a single connection to one other AS • carries local traffic only
– multihomed AS: has connections to more than one AS • refuses to carry transit traffic
– transit AS: has connections to more than one AS • carries both transit and local traffic
• Customer/Provider • Peer
AS relationships
• Each AS has:
BGP-4 contd.
– oneormoreborderrouters • Handles inter-AS traffic
– At least one BGP speaker for an AS that participates in routing
– BGP speaker establishes BGP sessions with peers and advertises:
• local network names
• other reachable networks (transit AS only)
• gives path information
• withdrawn routes
• BGP goal: find loop free paths between ASs
– Optimality is secondary goal
– It’sneitheradistance-vectornoralink-stateprotocol
• Hard problem
– Internet’s size (~90K active ASes, cicra 2021 ) means large tables in BGP routers
– Autonomous domains mean different path metrics
– Need for flexibility
BGP details
• Inter-domain routing protocol for the Internet – Prefix-based path-vector protocol
– Policy-based routing based on AS paths
– Continues to evolve over the years
• Each AS has one (or more) speakers
– Speakers announces/withdraws routes to neighbors
Basic BGP Operation
BGP speakers
Establish session
Exchange all active routes
BGP session
Exchange incremental updates
While connection is ALIVE exchange
route UPDATE messages
CSE 123 – Lecture 16: Border Gateway Protocol
Step by step
• A node learns multiple paths to destination – Stores all of the routes
– Applies policy to select a single active route
– … and may advertise the route to its neighbors
• IncrementalUpdates
– Announcement
• On selecting a new active route, add own node ID to path • … and (optionally) advertise to each neighbor
– Withdrawal
• If the active route is no longer available
• … send a withdrawal message to the neighbors
BGP Example
• Speaker for AS2 advertises reachability to P and Q
– network 128.96, 192.4.153, 192.4.32, and 192.4.3, can be reached directly from AS2
• Speaker for backbone advertises
– networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached along the path (AS1, AS2).
• Speaker can cancel previously advertised paths
Some BGP details
• Path vectors are most important innovation in BGP
– Enables loop prevention in complex topologies
– If AS sees itself in the path, it will not use that path
• Routes can be aggregated
– Based on CIDR (classless) addressing
• Routes can be filtered
• Runs over TCP
• ASes can apply a variety of policies
BGP in practice
• 10-20 “backbone” ASs which are fairly richly connected to each other
• Other “lower tier” ASs hang off the backbone networks -> Customers
– Some of them may also connect with each other at peering points à Peers
• Corporations connect as Customers to lower tier ASs or to backbone ASs depending on their need/willingness to pay
Policy with BGP
• BGP provides capability for enforcing various policies
• Policies are not part of BGP: they are provided to BGP as configuration information
• Enforcespoliciesby
– Choosing appropriate paths from multiple alternatives – Controlling advertisement to other AS’s
Illustrating BGP Policies
peer peer provider customer
Frank’s Internet Barn
Which route should
Frank pick to 13.13.0.0./16?
13.13.0.0/1616
Policy I: Prefer Customer routing
Route learned from customer preferred over
route learned from peer, preferred over route learned from provider
peer peer provider customer
local pref = 80
local pref = 100
local pref = 90
Set appropriate “local pref”
to reflect preferences:
Higher Local preference values are preferred
13.13.0.0/1617
Policy II: Import Routes
provider route peer route customer route ISP route
From customer
From customer
Policy II: Export Routes
provider route peer route customer route ISP route
To provider
From provider
To customer
To customer
filters block
Route learned From
BGP Policies Summarized
Advertise to
Customer Provider Peer
✓ ✗ ✗ Peer ✓✗✗
Export Policies: Valley-Free Routes
• “Valley-free” routing
– Label links as (+1, 0, -1) for provider, peer and
– In any valid path should only see sequence of +1,
followed by at most one 0, followed by sequence of -1
Export incentives
• How to make these choices?
– Prefer-customer routing: LOCAL_PREF
– Valley-free routes: control route advertisements
(see previous slides)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com