Transcript CS244a: An Introduction to Computer Networks

Inter-Domain Routing:
BGP, Routing Policies, etc.
•
Overview of BGP
•
Internet Settlement Models
–
–
–
–
Network Domains and Autonomous Systems (ASes)
Internet Interconnection Structure and BGP
Basic BGP Features
BGP Path Selection Criteria
–
–
AS Relationships
BGP Policies
Readings: Do the required readings
CSci5221:
Inter-Domain Routing and
BGP
1
Routing in the Internet
• The Global Internet consists of Autonomous Systems
(AS) interconnected with each other:
– Stub AS: small corporation: one connection to other AS’s
– Multihomed AS: large corporation (no transit): multiple
connections to other AS’s
– Transit AS: provider, hooking many AS’s together
• Two-level routing:
– Intra-AS: administrator responsible for choice of
routing algorithm within network
– Inter-AS: unique standard for inter-AS routing: BGP
CSci5221:
Inter-Domain Routing and
BGP
2
Internet Architecture
Internet: “networks of networks”!
International
lines
NAP
Internic
regional
network
national
network
ISP
company
on-line
services
ISP
university
company
access via
modem
LANs
CSci5221:
Inter-Domain Routing and
BGP
3
Internet Routing
routes
Control plane:
exchange routes
Internet
: Routing session
Data plane:
forward traffic
IP traffic
rusty.cs.berkeley.edu
IP=169.229.62.116
Prefix=169.229.0.0/16
CSci5221:
Fail over to alternate route
Inter-Domain Routing and
BGP
www.cnn.com
IP=64.236.16.52
Prefix=64.236.16.0/20
4
Internet comprised of Many
Ases (autonomous systems)
Internet
Autonomous
System
ISP
Level3
Calren
Berkeley
CSci5221:
ISP
ISP
Qwest
ISP
business
ISP
ISP
AT&T
Sprint UUnet
ISP
ISP
IP traffic
Inter-Domain Routing and
BGP
University
company
GNN
CNN
5
ASs & AS Numbers (ASNs)
Currently over 14,000 in use.
•
•
•
•
•
•
•
•
•
Genuity: 1
MIT: 3
Harvard: 11
Yale: 29
UCLA: 52
AT&T: 7018, 5075, …, 6341, …
UUNET: 701, 702, 284, 12199, …
Sprint: 1239, 1240, 6211, 6242, …
…
ASNs represent units of routing policy
64512 through 65535 are “private”
CSci5221:
Inter-Domain Routing and
BGP
6
Having Internet Connectivity
• To have complete Internet connectivity you
must be able to reach all destinations on
the net.
• Your packets have to get delivered to
every destination. This is easy (default
routes).
• Packets from everywhere else have to
“find you”. This is done by having your
ISP(s) advertise routes for you.
CSci5221:
Inter-Domain Routing and
BGP
7
BGP: The Glue of Internet
• To allow networks (ASs) to tell other networks
(ASs) about “routes” (parts of the IP address
space) that they are “responsible” for and how to
reach them
– Using “route advertisements”, or “promises” - also called
“NLRI” or “network-layer reachability information”
– “Path-vector” routing protocol
• Policy-based: allow ISPs to richly express their
routing policy, both in selecting outbound paths
and in announcing internal routes
– keep this in mind as we progress!
• Relatively “simple” protocol, but configuration is complex
and the entire world can see, and be impacted by, your
mistakes
CSci5221:
Inter-Domain Routing and
BGP
8
Network Interconnections
• Exchange Point
– Layer 2 or Layer 3
• Private Circuit
– May be provided by a third
party
CSci5221:
Inter-Domain Routing and
BGP
9
U of Minnesota Neighborhood
AS 7018
AT&T
AS 1
Genuity
AS 3908
SuperNet (Qwest)
AS 57
UMN
GigaPoP
AS 1998
State of
Minnesota
AS 217
UMN
128.101.0.0/16
CSci5221:
Inter-Domain Routing and
BGP
10
BGP: Some Basics
• BGP exchanges routes between ASs.
• When routes are exchanged, ASNs are stamped on
the routes “on the way out”
– adding one “AS hop” per network traversed -> AS path
– no concept of pipe size, internal router hop-count,
congestion -> in some sense BGP treats all ASs the same
• Routes are exchanged over “peering sessions”,
which run on top of TCP
– The routes are “objects”, or “bags” of “attributes”
• BGP is actually two protocols
– iBGP, designed for “internal” route exchange
– eBGP, designed for “external” route exchange
• 1995: BGP-4 [RFC 1771]
– Support for Classless Interdomain Routing (CIDR)
CSci5221:
Inter-Domain Routing and
BGP
11
BGP (Peering) Sessions
• BGP session set up over TCP
– When session set up, both sides flood the other end with
all of their best BGP routes
– Over time, only incremental updates are exchanged
– If session dies, all associated routes must be withdrawn
• BGP peers (neighbors) must be specified explicitly
• BGP session set-up: Cisco Example
Router A in AS 1
router bgp 1
neighbor 129.213.1.1 remote-as 2
Router B in AS 2
router bgp 1
neighbor 129.213.1.2 remote-as 1
CSci5221:
Inter-Domain Routing and
BGP
12
BGP Messages
• OPEN: set up a peering session
• UPDATE: announce new routes or withdraw
previously announced routes
• NOTIFICATION: shut down a peering
session
• KEEPALIVE: confirm active connection at
regular interval
CSci5221:
Inter-Domain Routing and
BGP
13
BGP Operations (Simplified)
Establish session on
TCP port 179
AS1
router A
129.213.1.2
BGP session
Exchange all
active routes
Exchange incremental
updates
CSci5221:
Inter-Domain Routing and
BGP
router B
129.213.1.1
AS2
While connection
is ALIVE exchange
route UPDATE messages
14
Establish a BGP Session
Establish neighboring session
between 12.10.0.1 and 12.10.0.2
TCP 179
12.10.0.1
Prefix
135.120.0.0/24
68.35.0.0/16
CSci5221:
Next hop
10.128.0.1
10.192.1.1
Inter-Domain Routing and
BGP
12.10.0.2
Prefix
12.70.0.0/24
12.9.0.0/16
Next hop
10.20.0.1
10.20.1.1
15
Exchange All Candidate Routes
12.70.0.0/24
12.9.0.0/16
10.20.0.1
10.20.1.1
12.10.0.1
12.10.0.2
135.120.0.0/24
68.35.0.0/16
Prefix
135.120.0.0/24
68.35.0.0/16
12.70.0.0/24
12.9.0.0/16
CSci5221:
Next hop
10.128.0.1
10.192.1.1
10.20.0.1
10.20.1.1
Inter-Domain Routing and
BGP
10.128.0.1
10.192.1.1
Prefix
12.70.0.0/24
12.9.0.0/16
135.120.0.0/24
68.35.0.0/16
Next hop
10.20.0.1
10.20.1.1
10.128.0.1
10.192.1.1
16
Send Incremental Updates
Withdraw 12.9.0.0/16
12.10.0.1
Prefix
135.120.0.0/24
68.35.0.0/16
12.70.0.0/24
12.9.0.0/16
CSci5221:
12.10.0.2
Next hop
10.128.0.1
10.192.1.1
10.20.0.1
10.20.1.1
Inter-Domain Routing and
BGP
Prefix
12.70.0.0/24
12.9.0.0/16
135.120.0.0/24
68.35.0.0/16
Next hop
10.20.0.1
10.20.1.1
10.128.0.1
10.192.1.1
17
BGP: Net Prefixes, ASNs and Route
Advertisements
BGP route advertisement:
Net prefix: 207.8.128.0/17
AS path: 4969 6461
AS 12001
AS 4969
AS 6461
AS 701
CSci5221:
Inter-Domain Routing and
BGP
AS 5000
18
BGP Route Advertisement
• Think of a BGP route as a “promise”
– If I advertise 207.8.128.0/17, I promise that if you
deliver traffic destined to any IP address within
207.8.128.0/17 to me, I know how to deliver it (at least
as well as anyone else)
• By making sure these routes, or “promises”, are
heard by all ASes, your provider ensures a return
path for all of your packets
– Sending packets out is easier than getting them back.
– Sending routes out causes IP traffic to come in
CSci5221:
Inter-Domain Routing and
BGP
19
Internal BGP (iBGP)
vs. external BGP (eBGP)
Internet
iBGP
eBGP
update
eBGP
iBGP
update
AS B
AS C
AS A
CSci5221:
Inter-Domain Routing and
BGP
20
eBGP vs. iBGP Sessions
• eBGP: between (usually directly-connected) routers in
different Ass
• iBGP: between (BGP-speaking) routers in same AS
• Different (operational) rules and polices apply!
AS
1239
AS 7007
XP
AS 701
AS 6079
AS 4006
CSci5221:
Inter-Domain Routing and
BGP
21
iBGP
• iBGP speakers are (usually) fully meshed: why?
• iBGP session set up:
AS 3847
Router A in AS 3847
router bgp 3847
neighbor 129.213.1.1 remote-as 3847
neighbor 128.28.10.2 remote-as 3847
Router B in AS 3847
router bgp 3847
neigbhor 129.213.1.2 remote-as 3847
neighbor 127.101.1.1 remote-as 3847
A
c
B
Router C in AS 3847
router bgp 3847
neigbhor 128.28.10.1 remote-as 3847
neigbhor 127.101.1.2 remote-as 3847
CSci5221:
Inter-Domain Routing and
BGP
22
eBGP vs. iBGP
eBGP Rules:
• By default, only talks to directly-connected
router.
• Sends the one best BGP route for each
destination.
• Sends all of the important “attributes”; omits the
“local preference” attribute.
• Adds (prepends) the speaker’s ASN to the “ASPath” attribute.
• Usually rewrites the “next-hop” attribute.
CSci5221:
Inter-Domain Routing and
BGP
23
eBGP vs. iBGP
iBGP Rules:
• Can talk to routers many hops away by default.
• Can only send routes it “injects”, or routes heard directly
from an external peer.
• Thus, requires a full mesh.
• Sends all attributes.
• Leaves the “as-path” attribute alone.
• Doesn’t touch the “next hop” attribute.
• With iBGP, next-hop is not a router directly connected.
– So a “recursive lookup” is needed.
– After the next-hop is found, a second lookup is made to figure
out how to send the packet “in the direction” of the next-hop.
CSci5221:
Inter-Domain Routing and
BGP
24
iBGP Route Distribution Restriction
• Assume AS1239 sends route 170.10.0.0/16 to AS2828.
Router A will send that route to Routers B and C
• When Router B receives 170.10.0.0/16, it will not
propagate that route to Router C because it was learned
from an iBGP neighbor. Router C will behave similarly
B
D
E
AS 2828
C
CSci5221:
Inter-Domain Routing and
BGP
170.10.0.0/16
A
AS 1239
25
Making BGP Scalable
• Address and route aggregation
• iBGP fully meshed, not scalable for large AS
• Two mechanisms:
– BGP route reflector (RR)
•
•
•
•
•
Client: used to identify “client” of the RR(s).
Non-client: identifies standard BGP peers.
Cluster: a group of clients under same RR(s).
Cluster-id: unique identifier for a cluster.
Originator-id: router-id of the originator of the route.
– BGP confederation, e.g.,
–
–
–
–
–
CSci5221:
Fully-mesh all BGP speakers at a POP
Use fake ASNs at each POP
Between POPs, use eBGP rules (send everything)
Within POPs, use iBGP rules
Preserve local_prefs between POPs
Inter-Domain Routing and
BGP
26
Scaling iBGP for Large AS
• Route reflectors
• Confederations
AS 1000
eBGP
update
eBGP
RR
RR
iBGP
AS 65010
iBGP eBGP
AS 65020
Only best paths
being sent by
RR
CSci5221:
Inter-Domain Routing and
BGP
27
Establish Connectivity
Prefix
135.120.0.0/16
AS 3
Next hop AS path
12.10.0.5 2 1
Prefix
135.120.0.0/16
IBGP
Next hop AS path
12.10.0.1 1
12.10.0.6
EBGP
12.10.0.5
AS 2
AS 1
135.120.0.0/16
IBGP
EBGP
12.10.0.1
12.10.0.2
IBGP
Prefix
135.120.0.0/16
CSci5221:
Inter-Domain Routing and
BGP
Next hop AS path
12.10.0.1 1
28
IGP and BGP Working Together
Prefix
135.120.0.0/16
AS 3
IBGP
Next hop AS path
12.10.0.1 1
Prefix
12.10.0.0/30
135.120.0.0/16
12.10.0.6
Next hop
10.10.0.1
10.10.0.1
EBGP
12.10.0.5
AS 1
12.10.0.1
135.120.0.0/16
EBGP
AS 2
12.10.0.2
10.10.0.1
IBGP
IBGP
Prefix
135.120.0.0/16
CSci5221:
Inter-Domain Routing and
BGP
Next hop AS path
12.10.0.1 1
29
BGP Messages: Four Types
• 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.
route announcement
=
prefix + attributes values
CSci5221:
Inter-Domain Routing and
BGP
30
What Is an Attribute?
...
Next
Hop
AS
Path
MED
...
...
• Attribute encoded in a TLV (type-length-value) format.
• Attribute length is 4 bytes long
• Attributes can be transitive (across ASs) or nontransitive (between AS neighbors only)
• Some are mandatory: e.g., AS Path, Next-Hop, etc.
CSci5221:
Inter-Domain Routing and
BGP
31
BGP Attributes
Value
----1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
...
255
Code
--------------------------------ORIGIN
AS_PATH
NEXT_HOP
MULTI_EXIT_DISC
LOCAL_PREF
ATOMIC_AGGREGATE
AGGREGATOR
COMMUNITY
ORIGINATOR_ID
CLUSTER_LIST
DPA
ADVERTISER
RCID_PATH / CLUSTER_ID
MP_REACH_NLRI
MP_UNREACH_NLRI
EXTENDED COMMUNITIES
Reference
--------[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1771]
[RFC1997]
[RFC2796]
[RFC2796]
[Chen]
[RFC1863]
[RFC1863]
[RFC2283]
[RFC2283]
[Rosen]
reserved for development
From IANA: http://www.iana.org/assignments/bgp-parameters
CSci5221:
Inter-Domain Routing and
BGP
Most
important
attributes
Not all attributes
need to be present in
every announcement
32
AS Path Attribute
AS 1129
135.207.0.0/16
AS Path = 1755 1239 7018
6341
AS 1755
Ebone
AS 1239
Sprint
135.207.0.0/16
AS Path = 6341
AS 6341
135.207.0.0/16
AS Path = 1129 1755 1239 7018 6341
ASRIPE
12654
NCC
135.207.0.0/16
AS Path = 7018 6341
AS7018
RIS project
135.207.0.0/16
AS Path = 3549 7018 6341
AT&T
AT&T Research
135.207.0.0/16
Prefix Originated
CSci5221:
Global Access
Inter-Domain Routing and
BGP
135.207.0.0/16
AS Path = 7018 6341
AS
3549
Global Crossing
How to detect loop using AS path?
33
Origin Attribute
• One of the mandatory, but minor, attributes of a
BGP route is the origin. It is one of (in order of
preference):
– IGP (i) (from a network statement)
– EGP (e) (from an external peer)
– Unknown (?) (from IGP redistribution)
• It can be re-set, but that is not often done.
• It is almost-last in the path selection algorithm.
CSci5221:
Inter-Domain Routing and
BGP
34
Inserting Routes into BGP
• How do routes get into BGP?
– You have to insert routes into BGP, and someone had to insert
external routes that you get into BGP somewhere else in the
first place.
• Two main ways:
– network statements: “network x.y.z.q [mask a.b.c.d]”
• MUST have an EXACTLY matching IGP route, e.g.,
router bgp 1
network 192.213.0.0 mask 255.255.0.0
……
ip route 192.213.0.0 255.255.0.0 null 0
– redistributing from OSPF, static, etc...
• redistribute <igp-protocol> <protocol-id>
– need to be careful, must filter externally learned routes!
• redistribute static
CSci5221:
Inter-Domain Routing and
BGP
35
Next Hop Attribute
AS 6201
• Next-hop IP address to
reach a network.
198.3.97.0/24
A
• Router A will advertise
198.3.97.0/24 to router B with a
next-hop of 207.240.24.202.
• With iBGP, the next-hop does not
change.
• IGPs should carry route to nexthops, using intelligent forwarding
decision (i.e., via IGP).
.202
207.240.24.200/30
.201
AS 3847
B
C
CSci5221:
Inter-Domain Routing and
BGP
36
iBGP and Next-Hop: Example
In AS 2828:
• Router A: “next hop” for 170.10.0.0/16 will be the
serial interface on Router D in AS1239 router
• This is true even in Router B’s and Router C’s
forwarding table.
B
D
E
AS 2828
C
CSci5221:
Inter-Domain Routing and
BGP
170.10.0.0/16
A
AS 1239
37
Local Preference Attribute
• Local to AS
– transitive throughout your
network. It is never
advertised to an eBGP peer.
AS 3847
• Used to influence BGP
path selection
• Default 100
F
G
E
C
208.1.1.0/24
D
80
– Highest local-pref preferred
• For example, you can express
the policy “prefer private
connect” by making the
“local_pref” be 150 and
leaving all other peers at 100.
CSci5221:
Inter-Domain Routing and
BGP
208.1.1.0/24
100
Preferred by all
AS3847 routers
A
B
208.1.1.0/24
AS 6201
38
Multi-Exit Discriminator (MED)
• Indication to external peers of preferred path into
an AS
– Advertised to external neighbors
– Neighbors are not obliged to heed it
• Affects routes with same AS path
* Lowest MED preferred
• A commonly used attribute by ISPs
– Usually based on IGP metric
– For example, big ISPs with multiple connections with each other
use MED to indicate which PoP is “closest” to an advertised
route, thus more preferred
• It comes after AS_PATH in evaluation, and thus
isn’t quite as much of a “hammer” as local-pref
CSci5221:
Inter-Domain Routing and
BGP
39
MED Attribute: Example
128.11.10/24
AS 1
+5
+20
AS 701
CSci5221:
Inter-Domain Routing and
BGP
40
Community Attribute
• Defined in RFC 1997
• 32-bit integer:
– represented as two 16-bit integer x:y
• Used to group routes (“net prefixes”)
– Each route could be member of multiple communities
• Transitive: carried across ASs
• Very useful in applying policies
• Well-known communities
– No-Export: do not advertise to eBGP peers
– No-advertise: do not advertise to any peer
– Local-AS: do not advertise outside local AS (only used with
“confederations”)
CSci5221:
Inter-Domain Routing and
BGP
41
Community Attribute: Example
AS 500
AS 400
200.10.0.0/16
200.10.0.0/16 300:9
AS 300
160.10.0.0/16 300:1
160.10.0.0/16 300:1
170.10.0.0/16 300:1
170.10.0.0/16 300:1
AS 100
AS 200
160.10.0.0/16
CSci5221:
Inter-Domain Routing and
BGP
170.10.0.0/16
42
Attributes are Used to
Select Best Routes
192.0.2.0/24
pick me!
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!)
CSci5221:
Inter-Domain Routing and
BGP
43
Policy Routing
ISP2
ISP1
traffic
Connectivity DOES NOT
imply reachability!
ISP3
ISP4
traffic
Cust1
Cust2
Policy determines how traffic
can flow on the Internet
CSci5221:
Inter-Domain Routing and
BGP
44
BGP Route Processing
Open ended programming.
Constrained only by vendor configuration language
Receive Apply Policy =
filter routes &
BGP
Updates tweak
attributes
Apply Import
Policies
Based on
Attribute
Values
Best
Routes
Best Route
Selection
Best Route
Table
Apply Policy =
filter routes &
tweak
attributes
Transmit
BGP
Updates
Apply Export
Policies
Install forwarding
Entries for best
Routes.
IP Forwarding Table
45
Best Route Selection Rule
Highest Local Preference
Enforce relationships
(provider-customer, peer)
Shortest ASPATH
Origin: prefer IGP over BGP over INCOMPLETE
Lowest MED
iBGP < eBGP (i.e. prefer eBGP)
Lowest IGP cost
to BGP egress
Traffic Engineering
Lowest router ID
Throw up hands and
break ties
CSci5221:
Inter-Domain Routing and
BGP
46
Typical AS Relationships
• Provider-customer
– customer pay money for transit
• Peer-peer
– typically exchange respective customers’ traffic for free
• Siblings
– Mutual transit agreement
– Provide connectivity to the rest of the Internet for each other
CSci5221:
Inter-Domain Routing and
BGP
47
Internet Business Model (Simplified)
Pay to use
Provider
Free to use
Preferences implemented with
local preference manipulation
Peer
Get paid
to use
Customer
Destination
• Customer/Provider: One AS pays another for reachability to
some set of destinations
• “Settlement-free” Peering: Bartering. Two ASes exchange
routes with one another.
CSci5221:
Inter-Domain Routing and
BGP
48
Customers and Providers
provider
provider
IP traffic
customer
customer
Customer pays provider for access to the Internet
CSci5221:
Inter-Domain Routing and
BGP
49
The Peering Relationship
peer
peer
provider
customer
traffic
allowed
CSci5221:
traffic NOT
allowed
Inter-Domain Routing and
BGP
Peers provide transit between
their respective customers
Peers do not provide transit
between peers
Peers (often) do not exchange $$$
50
Peering Provides Shortcuts
Peering also allows connectivity between
the customers of “Tier 1” providers.
CSci5221:
Inter-Domain Routing and
BGP
peer
provider
peer
customer
51
Which AS Paths are “Legal”?
• Valley-free:
– After traversing a provider-customer or peer-peer edge,
cannot traverse a customer-provider or peer-peer edge
– Invalid path: >= 2 peer links, downhill-uphill, downhillpeer, peer-uphill
CSci5221:
Inter-Domain Routing and
BGP
52
Example of Valley-Free Paths
[1 2 3], [1 2 6 3] are valley-free
X
X
[1 4 3], [1 4 5 3] are not valley free
CSci5221:
Inter-Domain Routing and
BGP
53
AS relationships translate into
BGP export rules
• Export to a provider or a peer
– Allowed: its routes and routes of its customers and
siblings
– Disallowed: routes learned from other providers or peers
• Export to a customer or a sibling
– Allowed: its routes, the routes of its customers and
siblings, and routes learned from its providers and peers
CSci5221:
Inter-Domain Routing and
BGP
54
Filtering and Rankings
Filtering: route advertisement
Customer
Primary
Competitor
CSci5221:
Ranking: route selection
Backup
Inter-Domain Routing and
BGP
55
BGP Router - Processing Routes
• For each route received:
– If it’s a valid route AND passes any filters, it must be
put into the BGP routing table.
– Then, unless it is replacing a duplicate, a best-path
computation must be run on all candidate BGP routes of
the same prefix.
– Then, if the best route changed, the RIB and/or FIB
must be updated.
– This process is done for ALL incoming BGP routes.
CSci5221:
Inter-Domain Routing and
BGP
56
BGP Policy Configuration
• Some Cisco BGP filtering mechanisms:
– To decide what routes can and can’t go to various other
routers, you can “filter” using:
• “distribute lists” (“prefix filters”) - lists of routes
• “filter lists” (“as-path filters”) - lists of regular
expressions matching or denying ASs
• “route maps” (“BGP Basic programs”) that allow you
to match and change most BGP attributes
CSci5221:
Inter-Domain Routing and
BGP
57
What policy looks like in Cisco
IOS
eBGP Session
Inbound “Route Map”
(import policy)
CSci5221:
Inter-Domain Routing and
BGP
58
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
traffic
outbound
routes
inbound
routes
In general, an AS has more
control over outbound traffic
CSci5221:
Inter-Domain Routing and
BGP
59
Tuning Inbound BGP Routes
(i.e., outbound traffic)
• Inbound BGP routes make traffic go out
– Having a route means that an outbound packet can use it
as basis for a forwarding decision (well, the router can)
– It is far easier to control outbound traffic than inbound
• Goal is generally to provide fastest, lowest-loss,
path for all destinations,
i.e., to optimize connectivity “quality”, whatever that is
– E.g., to optimize throughput and latency
– to reduce transit costs, say,
• squash traffic via a certain provider,
• prefer customer than peer/provider paths, and prefer peer
than provider paths
– to load balance, or to ensure reliability with back-up
routes
CSci5221:
Inter-Domain Routing and
BGP
60
Controlling Outbound BGP Routes
(i.e., inbound traffic)
• Outbound BGP routes make traffic come in
– It’s a lot harder to control inbound traffic as other ASs’
policies complicate your life!
• If you are a stub AS with a single connection
– Not much you need to do except to filter out routes not in your AS
• If you are a multi-homed stub AS,
– Want to control through which link/provider that traffic to certain
destinations in your AS may take, to load balance or for back-up
• If you are an ISP, you want to minimize transit cost,
– carry transit traffic from customers only !
– use “hot-potato” routing to hand off traffic to
peers/providers as soon as possible
– to load balance, or to ensure reliability with back-up routes
CSci5221:
Inter-Domain Routing and
BGP
61
Shedding Inbound Traffic with ASPATH
Padding Hack
AS 1
provider
192.0.2.0/24
ASPATH = 2 2 2
192.0.2.0/24
ASPATH = 2
primary
backup
customer
192.0.2.0/24
AS 2
Padding will (usually)
force inbound
traffic from AS 1
to take primary link
62
Padding May Not Shut Off All
Traffic
AS 1
AS 3
provider
provider
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
customer
192.0.2.0/24
AS 2
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
balancing
63
Hot Potato Routing: Go for the Closest
Egress Point
192.44.78.0/24
egress 2
egress 1
15
56
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!
64
Getting Burned by the Hot Potato
Heavy
Content
Web Farm
2865
High bandwidth
Provider backbone
17
SFF
Low bandwidth
customer backbone
NYC
15
56
San Diego
Many customers want
their provider to
carry the bits!
tiny http request
huge http reply
65
Inter-Domain Traffic Engineering
Customer B
• Better to cooperate?
– Negotiate where to send
– Inbound and outbound
– Mutual benefits
Provider B
• But, how to do it?
multiple
peering
points
Early-exit
routing
– What info to exchange?
– How to prioritize the many
choices?
– How prevent cheating?
• Open research
territory
Provider A
Customer A
CSci5221:
Inter-Domain Routing and
BGP
66