A more detailed look at BGP
Routing vs. Forwarding
Net Nxt Hop
Copyright By PowCoder代写 加微信 powcoder
R1 Direct R3 R1 R3 R1
Default to upstream router
Forwarding always works Routing can be badly broken
Net Nxt Hop
Forwarding: determine next hop Routing: establish end-to-end paths
Net Nxt Hop
R4 R3 R3 R4 Direct R4
Technology of Distributed Routing
Link State
• Topology information is flooded within the routing domain
• Best end-to-end paths are computed locally at each router.
• Based on minimizing some notion of distance
• Works only if policy is shared and uniform
• Examples: OSPF , IS-IS
Distance Vector
• Each router knows little about network topology
• Only best next-hops are chosen by each router for each destination network.
• Does not require any notion of distance
• Does not require uniform policies at all routers
• Examples: RIP , BGP
• Best end-to-end paths result from composition of all next-hop choices
• Best end-to-end paths determine next-hops.
The Gang of Four
Link State Vectoring
OSPF IS-IS
Inter-domain and Intra-domain routing
IGP = Interior Gateway Protocol EGP = Exterior Gateway Protocol
Metric based: OSPF, IS-IS, RIP, EIGRP (cisco)
Policy based: BGP
The Routing Domain of BGP is the entire Internet
Physical Connectivity
Anchorage, AK
AT&T IP Backbone
Year end 2001
Seattle Spokane
Minneapolis
R St. Moines
Rolling Syracuse
Albany Hartford
Cambridge Framingham
Stamford P
Portland Worcester Manchester
Rapids Birmingham
Baltimore Newark Bohemia
Detroit Pittsburgh
Harrisburg
t White Plains
Cedar Knolls
Salt Lake City
South Bend
Sacramento
San Francisco Francisco
San Vegas
Cleveland Akron DaytonColumbus
Silver Springs
Indianapolis
Cincinnati Louisville
Birmingham
Redwood City
Colorado Springs
Florissant
Greensboro
Richmond Raleigh
Camden, NJ
Ls os Angeles LA-Airport
Albuquerque
Oklahoma City
San Antonio
Jacksonville
Remote GSR Access Router Remote Access Router
Note: Connectivity and nodes shown are targeted for deployment; actual deployment
may vary. Maps should not be used to predict service availability.
TampaR Lauderdale
W. Palm Beach
Backbone Node
Rev. 6-4-01
San Juan PR
Sprint, USA
Internet Initiative Japan (IIJ)
IIJ, Tokyo
Telstra international
UUNet, Europe
wiscnet.net
UW-Superior
UW-Eau Claire
Clintonville
UW-Stevens Point
Fox Valley TC UW-Oshkosh
UW- W-Whitewater
Stiles Jct.
UW-River Falls
Qwest and Other Provider(s)
Internet 2 &
UW-Milwaukee UW-Parkside
Chicago – 2 (Winter ’02)
UW-La Crosse
Dodgeville
UW-Platteville
w Peering – Public and Private
w Commodity Internet Transit
w Internet2
w Merit and Other State Networks w National Education Network
w Regional Research Peers
Gigabit Ethernet
OC-12 (622Mbps)
OC-3 (155Mbps) DS-3 (45Mbps) T1 (1.5Mbps)
Chicago – 1
(Summer ’02)
(Summer ’02)
(Summer ’02)
(Summer ’03)
(Summer ’03)
(Winter ’02)
(Winter ’02)
Relationships Between Networks
Customers and Providers
Customer pays provider for access to the Internet
IP traffic
The “Peering” Relationship
Peers provide transit between their respective customers
Peers do not provide transit between peers
Peers (often) do not exchange $$$
peer peer provider customer
traffic traffic NOT allowed allowed
Connectivity vs Reachibility
Connectivity does not imply reachability (A and C may not be able to reach each other)
Peering Provides Shortcuts
Peering also allows connectivity between the customers of “Tier 1” providers.
peer peer provider customer
Peering Wars
• Reduces upstream transit costs
• Can increase end-to- end performance
• May be the only way to connect your customers to some part of the Internet (“Tier 1”)
Don’t Peer
You would rather have
Peers are usually your competition
Peering relationships may require periodic renegotiation
Peering struggles are by far the most contentious issues in the ISP world!
Peering agreements are often confidential.
• BGP = Border Gateway Protocol
• Is a Policy-Based routing protocol
• Is the de facto EGP of today’s global Internet
• Relatively simple protocol, but configuration is complex and the entire world can see, and be impacted by mistakes.
• 1989 : BGP-1 [RFC 1105]
– Replacement for EGP (1984, RFC 904)
• 1990 : BGP-2 [RFC 1163]
• 1991 : BGP-3 [RFC 1267]
• 1995 : BGP-4 [RFC 1771]
– Support for Classless Interdomain Routing (CIDR)
BGP Route Announcements
12.125.133.90
AS 6431 AT&T Research
135.207.0./16
AS 7018 AT&T
12.127.0.121
RIPE NCC RIS project
135.207.0.0/16
Next Hop = 12.125.133.90 Path = 6431
Every time a route announcement crosses an AS
boundary, the Next Hop attribute is changed to the IP
address of the border router that announced the route.
135.207.0.0/16
Next Hop = 12.127.0.121 Path = 7018 6431
Routers Talking to Routers
Routing info
Routing info
• Routing computation is distributed among routers within a routing domain
• Computation of best next hop based on routing information is the most CPU/memory intensive task on a router
• Routing messages are usually not routed, but exchanged via layer 2 between physically adjacent routers (internal BGP and multi-hop external BGP are exceptions)
Autonomous Systems (ASes)
An autonomous system (AS) is a large network or group of networks that has a unified routing policy and that has been assigned an Autonomous System Number (ASN)
… the administration of an AS appears to other ASes to have a single coherent interior routing plan and presents a consistent picture of what networks are reachable through it.
RFC 1930: Guidelines for creation, selection, and registration of an Autonomous System
AS Numbers (ASNs)
ASNs are 16 bit values. 64512 through 65535 are “private”
Currently over 11,000 in use.
• Genuity (f.k.a. BBN): 1 • MIT: 3
• Harvard: 11
• UC San Diego: 7377
• AT&T: 7018, 6341, 5074, …
• UUNET: 701, 702, 284, 12199, … • Sprint: 1239, 1240, 6211, 6242, … •…
ASNs represent units of routing policy
AS Graphs Can Be Fun
Part of Worldcom’s Global ARD
The subgraph showing all ASes that have more than 100 neighbors in full
graph of 11,158 nodes. July 6, 2001. Point of view: AT&T route-server
AT&T North America
AS Graph != Internet Topology
BGP was designed to throw away information!
The AS graph may look like this.
Reality may be closer to this…
A Bit of OGI’s AS Neighborhood
AS 2914 Verio
AS 7018 AT&T
AS 1239 Sprint
U of Washington
AS 3356 Level 3
AS 3356 Level 3
AS 3807 U of Montana
Portland Regional Education Network
AS 7774 U of Alaska
AS 6366 Portland State U
AS 11964 OGI
Oregon Health Sciences U
128.223.0.0/16
Sources: ARIN, Route Views, RIPE
AS 2914 Verio
AS 701 UUNET
AS 3701 Oregon Joint
Graduate Schools Of Engineering
AS 1239 Sprint
AS 293 ESN
AS 3582 U Oregon
128.223.0.0/16
U Corp for Advanced Internet Development
AS 4600 U Oregon
A Bit of U Oregon’s AS Neighborhood
Sources: ARIN, Route Views, RIPE
Partial View of cs.wisc.edu Neighborhood
AS 3549 Global Crossing
AS 1 Genuity
AS 2381 WiscNet
UW Academic
AS 209 Qwest
UW Milwaukee
AS 3136 UW Madison
129.89.0.0/16
128.105.0.0/16
130.47.0.0/16
BGP Operations (Simplified)
Establish session on TCP port 179
BGP speaker
Exchange all active routes
BGP session
Exchange incremental updates
While connection
is ALIVE exchange
route UPDATE messages
Two Types of BGP Neighbor Relationships
• External Neighbor (eBGP) in a different Autonomous Systems
• Internal Neighbor (iBGP) in the same Autonomous System
iBGP is routed (using IGP!)
Border router iBGP
Four Types of BGP Messages
• Open : Establish a peering session.
• Keep Alive : Handshake at regular intervals.
• Notification : Shuts down a peering session.
• Update : Announcing new routes or withdrawing previously announced routes.
announcement =
prefix + attributes values
BGP Attributes
Value Code
—– ———————————
6 ATOMIC_AGGREGATE
7 AGGREGATOR
12 ADVERTISER
13 RCID_PATH / CLUSTER_ID
14 MP_REACH_NLRI
15 MP_UNREACH_NLRI
16 EXTENDED COMMUNITIES
255 reserved for development
3 NEXT_HOP
4 MULTI_EXIT_DISC
5 LOCAL_PREF
8 COMMUNITY
9 ORIGINATOR_ID
10 CLUSTER_LIST
Most important attributes
Not all attributes need to be present in every announcement
From IANA: http://www.iana.org/assignments/bgp-parameters
Ones to remember
– AS path: ASs the announcement traversed
– Next-hop: where the route was heard from
– Origin: Route came from IGP or EGP
– Local pref: Statically configured ranking of routes within AS
– Multi Exit Discriminator: preference for where to exit network
– Community: opaque data used for inter-ISP policy
Announcing a route
192.0.2.0/24
For 192.0.2.0/24 Next Hop
Other attributes
Attributes are Used to Select
192.0.2.0/24 pick me!
192.0.2.0/24 pick me!
192.0.2.0/24 pick me!
Given multiple
routes to the same prefix, a BGP speaker must pick at most one best route
(Note: it could reject them all!)
192.0.2.0/24 pick me!
Route Selection Summary
Highest Local Preference
Enforce relationships
Shortest ASPATH Lowest MED i-BGP < e-BGP
Lowest IGP cost to BGP egress
traffic engineering
Lowest router ID
Throw up hands and break ties
BGP Route Processing
Receive BGP Updates
Based on Attribute Values
Transmit BGP Updates
Open ended programming.
Constrained only by vendor configuration language
Apply Policy = filter routes & tweak attributes
Apply Policy = filter routes & tweak attributes
Apply Import Policies
Install forwarding Entries for best Routes.
Apply Export Policies
IP Forwarding Table
Join EGP with IGP For Connectivity
10.10.10.11
10.10.10.10
AS 1 192.0.2.1 AS 2 192.0.2.0/30
Forwarding Table
destination next hop
192.0.2.0/30
10.10.10.10
Join EGP with IGP For Connectivity
135.207.0.0/16
Next Hop = 192.0.2.1
10.10.10.10
AS 1 192.0.2.1 AS 2 192.0.2.0/30
Forwarding Table
destination next hop
192.0.2.0/30
10.10.10.10
135.207.0.0/16
Join EGP with IGP For Connectivity
10.10.10.10
AS 1 192.0.2.1 AS 2 192.0.2.0/30
135.207.0.0/16
Next Hop = 192.0.2.1
Forwarding Table
destination next hop
192.0.2.0/30
10.10.10.10
destination next hop
135.207.0.0/16 192.0.2.1
135.207.0.0/16
Join EGP with IGP For Connectivity
135.207.0.0/16
Next Hop = 192.0.2.1
10.10.10.10
AS 1 192.0.2.1 AS 2 192.0.2.0/30
Forwarding Table
destination next hop
192.0.2.0/30
10.10.10.10
Forwarding Table
destination next hop
135.207.0.0/16
192.0.2.0/30 10.10.10.10
10.10.10.10
destination next hop
135.207.0.0/16 192.0.2.1
135.207.0.0/16
Implementing Customer/Provider and Peer/Peer relationships
Two parts:
• Enforce transit relationships – Outbound route filtering
• Enforce order of route preference
– provider < peer < customer
Traffic Engineering with BGP
Tweak Tweak Tweak
• For inbound traffic
– Filter outbound routes
– Tweak attributes on outbound routes in
the hope of influencing your neighbor’s best route selection
• For outbound traffic
– Filter inbound routes
– Tweak attributes on inbound routes to
influence best route selection
inbound traffic
outbound routes
outbound traffic
inbound routes
In general, an AS has more control over outbound traffic
135.207.0.0/16
AS Path = 1239 7018 6341
ASPATH Attribute
135.207.0.0/16
AS Path = 1755 1239 7018 6341
135.207.0.0/16
AS Path = 1129 1755 1239 7018 6341
135.207.0.0/16
AS Path = 7018 6341
135.207.0.0/16 AS Path = 6341
135.207.0.0/16
AS Path = 3549 7018 6341
135.207.0.0/16
AS Path = 7018 6341
135.207.0.0/16
Prefix Originated
AS 1129 Global Access
AS 1755 Ebone
AS 1239 Sprint
AS 12654 RIPE NCC
RIS project
AS7018 AT&T
AS 3549 Global Crossing
AT&T Research
Shorter Doesn’t Always Mean Shorter
BGP says that path 4 1 is better
than path 3 2 1?!
Exporting internal
state would dramatically increase global instability and amount of routing state
Interdomain Loop Prevention
Don’t Accept!
BGP at AS YYY will never accept a route with ASPATH containing YYY.
12.22.0.0/16
ASPATH = 1 333 7018 877
Traffic Often Follows ASPATH
AS 1 AS 2 AS 3 AS 4
135.207.0.0/16
135.207.0.0/16 ASPATH = 3 2 1
IP Packet Dest = 135.207.44.66
... But It Might Not
AS 2 filters all subnets with masks longer than /24
135.207.0.0/16 ASPATH = 1
135.207.0.0/16 ASPATH = 3 2 1
135.207.44.0/25 ASPATH = 5
135.207.0.0/16
IP Packet Dest = 135.207.44.66
135.207.44.0/25
From AS 4, it may look like this packet will take path 3 2 1, but it actually takes path 3 2 5
AS Graphs Depend on Point of View
primary link
backup link
Set Local Pref = 100 for all routes from AS 1
Set Local Pref = 50
for all routes from AS 1
Forces outbound traffic to take primary link, unless link is down.
We’ll talk about inbound traffic soon ...
Implementing Backup Links with Local Preference (Outbound Traffic)
primary link
Forces outbound traffic to take primary link, unless link is down.
backup link
Set Local Pref = 100 for all routes from AS 1
Set Local Pref = 50
for all routes from AS 3
Multihomed Backups (Outbound Traffic)
Shedding Inbound Traffic with ASPATH Padding. Yes, this is a Glorious Hack ...
192.0.2.0/24 ASPATH=2 2 2
192.0.2.0/24 ASPATH = 2
primary backup customerAS 2 192.0.2.0/24
Padding will (usually) force inbound
traffic from AS 1
to take primary link
... But Padding Does Not Always Work
192.0.2.0/24 ASPATH = 2
192.0.2.0/24
ASPATH = 2 2 2 2 2 2 2 2 2 2 2 2 2 2
primary backup
customerAS 2 192.0.2.0/24
AS 3 will send
traffic on “backup”
link because it prefers customer routes and local preference is considered before ASPATH length!
Padding in this way is often
used as a form of load
Hot Potato Routing: Go for the Closest Egress Point
192.44.78.0/24
IGP distances
This Router has two BGP routes to 192.44.78.0/24.
Hot potato: get traffic off of your network as Soon as possible. Go for egress 1!
Getting Burned by the Hot Potato
High bandwidth Provider backbone
Content Web Farm
Low bandwidth customer backbone
Many customers want their provider to carry the bits!
tiny http request huge http reply
Cold Potato Routing with MEDs (Multi-Exit Discriminator Attribute)
Prefer lower MED values
Content Web Farm
192.44.78.0/24 MED = 15
192.44.78.0/24
This means that MEDs must be considered BEFORE IGP distance!
Note1 : some providers will not listen to MEDs Note2 : MEDs need not be tied to IGP distance
192.44.78.0/24 MED = 56
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com