Transcript BGP - Seneca - School of Information & Communications Technology

Introduction to BGP
What Is BGP?
 Border Gateway Protocol BGP-4
 The de-facto interdomain routing protocol
 BGP enables policy in routing:
 Which information gets advertised and how
 BGP is a Distance Vector like protocol
 Within an AS, Internal Gateway Protocol (IGP or I-
BGP)
Internet Structure
3
Original idea
Backbone service provider
“ Consumer” ISP
Small
corporation
Large corporation
“Consumer ” ISP
Small
corporation
CS 640
“Consumer”ISP
Small
corporation
“Consumer ” ISP
Small
corporation
4
Internet Structure
Today
Large corporation
“Consumer ” ISP
Peering
point
Backbone service provider
“ Consumer” ISP
Large corporation
Small
corporation
CS 640
“Consumer”ISP
Peering
point
Route Propagation in the Internet
5
 Autonomous System (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




CS 640
hosts know local router
local routers know site routers
site routers know core router
core routers know everything
6
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
 recent Internet standard
 uses link-state algorithm
 supports load balancing
 supports authentication
CS 640
EGP: Exterior Gateway Protocol
7
 Overview
 Original standard for Internet routing protocol (c 1983)
 designed for tree-structured Internet


Single backbone
concerned with reachability, not optimal routes
 Protocol messages
 neighbor acquisition: one router requests that another be its peer;
peers exchange reachability information
 neighbor reachability: one router periodically tests if the another is
still reachable; exchange HELLO/ACK messages;


routing updates: peers periodically exchange their routing tables
(including route weights) using a basic distance vector method

CS 640
uses a k-out-of-n rule: ¼ to stay up, ¾ to establish
There can be multiple connections between ASs
Limits of EGP
8
 At first glance, EGP seems like a distance vector protocol
since updates carry lists of destinations and distances – but
distances are NOT reliable.
 EGP was designed to support tree topologies, not meshes


False routes injected by accident can have really bad consequences
(black holes) – there is no easy way for dealing with this problem
Loops can easily occur – all we are doing is forwarding routing tables
 EGP was not designed to easily support fragmented IP
packets – all data is assumed to fit in MTU.
 Solutions to these and other EGP problems were all manual
CS 640
BGP-4: Border Gateway Protocol
9
 BGP-1 developed in 1989 to address problems with EGP.
 Assumes Internet is an arbitrarily interconnected set of ASs
 AS traffic types
 Local


starts or ends within an AS
Transit

passes through an AS
 AS Types
 stub AS: has a single connection to one other AS


multihomed AS: has connections to more than one AS


refuses to carry transit traffic
transit AS: has connections to more than one AS

CS 640
carries local traffic only
carries both transit and local traffic
BGP-4 contd.
 Each AS has:
 one or more border routers


10

Handles inter-AS traffic




local network names
other reachable networks (transit AS only)
gives path information including path weights (MEDs)
withdrawn routes
one BGP speaker for an AS that participates in routing
BGP speaker establishes BGP sessions with peers and advertises:
 BGP goal: find loop free paths between ASs
 Optimality is secondary goal
 It’s neither a distance-vector nor a link-state protocol
 Hard problem
 Internet’s size (~12K active ASs) means large tables in BGP routers
 Autonomous domains mean different path metrics
 Need for flexibility
CS 640
BGP Example
11
 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
Customer P
(AS 4)
128.96
192.4.153
Customer Q
(AS 5)
192.4.32
192.4.3
Customer R
(AS 6)
192.12.69
Customer S
(AS 7)
192.4.54
192.4.23
Regional provider A
(AS 2)
Backbone network
(AS 1)
Regional provider B
(AS 3)
 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
CS 640
Some BGP details
12
 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
 Most of the same messages as EGP
 Open, Update, Notify, Keepalive
 BGP session have only recently been made secure
CS 640
BGP in practice
13
 10-20 “tier 1” ASs which are the Internet backbone
 Clearly convergence is an issue – why?
 Black holes are always a potential problem
 There are lots of BGP updates every day!
 BGP is really the heart of the Internet
 BGP is a means by which network operators
control congestion in the Internet.
 BGP is really a big problem!
CS 640
How A BGP graph Looks Like
AS 2
AS 5
AS 4
AS 3
AS 1
 Each AS has
designated BGP
routers
 BGP routers of an AS
communicate
internally with
another protocol
(IGP)
What is different with BGP?
 BGP goal: enable business relationships
 Opts for: flexibility, scalability
 Performance optimization is secondary
Some Basic Numbers
• ~20,000 Autonomous Systems approx.
• Corporate Networks
• ISP Internal Networks
• National Service Providers
• Identified by ASN a 16 bit value
• Assigned by IANA
• Superlinear growth
Size of the Routing Table at the core of
the Internet
17
Number of prefixes
140000
120000
100000
80000
60000
40000
20000
0
Aug-87
May-90
Jan-93
Oct-95
Jul-98
Apr-01
Jan-04
Source: http://www.telstra.net/ops/bgptable.html
Routing is Based on Prefixes
 A BGP Routing table has prefixes for entries
 For a IP address of a packet, find longest match
 Example: packet IP 128.32.101.1
 128.32.0.0/16 match for 16 bits
 128.32.101.0/24 is a longer match
 No matches:
 128.1.1.4
 128.32.5.0/24
Prefix Matching in More Detail
 For a IP address of a packet, find longest match
 Example: Compare
 packet IP 128.32.101.1
 With 128.32.0.0/16
 IP
: 01000000. 001000000. 01100101 .00000001
 Mask : 11111111. 111111111. 00000000 .00000000
 AND : 01000000. 001000000. 00000000 .00000000
 Prefix : 01000000. 001000000. 00000000. 00000000
 Equal? Yes
Advertising Routing Information
 Each AS advertises what it can reach from each BGP
router
 Policies I: filter what you advertise
 Policies II: filter from what you hear advertised
 Build up a BGP routing table

Remember which prefix you hear from which link
What Does a Routing Table Look Like?
Prefix
Origin
AS
Path
128.32.0.0/16
123
14 56 123
123
34 101 203 123
15
50 15 15
128.32.101.0/24
 Origin AS “owns” the address
Basic AS relationships
 Customer – Provider
 Customer pays Provider for service
 The Customer is always right
 Peer to Peer: mutual cooperation
 Ex. MCI and AT&T
 Sibling-Sibling
 Ex. AT&T research and AT&T wireless
The Internet as a Directed Graph
 Every edge is bidirectional
 Business relationships are
represented
Provider
Peer
Customer
Peer
The Initial Idea
 Data flows between customers-providers
 Top level providers are peers
 They exchange information to ensure connectivity
 What can possibly go wrong?
And then came the rain…
 Thousands of ASs
 Complicated relationships
 Multiple providers for one AS!!
 Multihoming
 Traffic engineering
 I want to use multiple paths and load balance
AS Relationships
200
100
10
11
1
2
12
3
Provider
Peer
13
4
 Customer – Provider: customer pays and is always right
 Peer to Peer: Exchange traffic only between their customers
 Sibling-Sibling: Exchange traffic at will
Customer
Peer
The Rules of BGP Routing
 Transit traffic: traffic that does not go to my
customers (or their customers)
 A provider carries any traffic to or from a customer
 Peers exchange traffic only if between their
customers
How BGP Policy Restricts Routing
Provider
100
200
Peer
Customer
Peer
10
11
1
2
12
13
3
4
 Routing rules:
 Provider accept everything
 Peer only if it is for its
customers
 Path Properties:


Up then down
No up-down-up, at most 1 peerpeer steps
Implementing BGP Rules
 What do you do with an advertisement:
 Through customer link
 Advertise to all (customers, peers, providers)
 Through provider link
 Advertise to customer only (and possibly siblings)
 Through peer link
 Advertise to customer only (and possibly siblings)
 Through sibling link
 Advertise to all
How Policies Affect Routing
 A Provider will get rid of
Customer 1
ISP1
ISP2
Customer 2
traffic as soon as possible,
 But a Provider will carry
the traffic for its customer
 Did anyone say traffic is
asymmetric?