Interdomain Routing:�Border Gateway Protocol (BGP)

UW CSE-461

1

Authors

Hari Balakrishnan

• Fujitsu Professor at MIT EECS
• Berkeley PhD
• Lots of notable contributions:
• P4
• Mobile Sensing
• Etc.

Nick Feamster

• Neubauer Professor of CS at the U of Chicago
• MIT PhD
• Advised by Hari
• Lots of notable contributions:
• Measurement
• SDN
• Etc.

2

Structure of the Internet

• Networks (ISPs, CDNs, etc.) group with IP prefixes
• Networks are richly interconnected, often using IXPs

CSE 461 University of Washington

4

Effects of Independent Parties

• Each party selects routes to suit its own interests
• e.g, shortest path in ISP

​

• What path will be chosen for A2→B1 and B1→A2?
• What is the best path?

CSE 461 University of Washington

5

Effects of Independent Parties (2)

• Selected paths are longer than overall shortest path
• And asymmetric too!
• This is a consequence of independent goals and decisions, not hierarchy and scale

Routing Policies

• Capture the goals of different parties
• Could be anything
• E.g., Internet2 only carries non-commercial traffic
• Common policies we’ll look at:
• ISPs give transit service to customers
• ISPs give peer service to each other

CSE 461 University of Washington

6

CSE 461 University of Washington

7

Routing Policies – Transit

• One party (customer) gets transit service from another party (ISP)
• ISP accepts traffic for customer from the rest of Internet
• ISP sends traffic from customer to the rest of Internet
• Customer pays ISP for the privilege

Non-

customer

CSE 461 University of Washington

8

Routing Policies – Peer

• Both party (ISPs in example) get peer service from each other
• Each ISP accepts traffic from the other ISP only for their customers
• ISPs do not carry traffic to the rest of the Internet for each other
• ISPs don’t pay each other

Customer A1

ISP A

Customer A2

Customer B1

ISP B

Customer B2

Routing with BGP (Border Gateway Protocol)

• iBGP is for internal routing
• eBGP is interdomain routing for the Internet
• Path vector, a kind of distance vector

9

Routing with BGP (2)

• Parties like ISPs are called AS (Autonomous Systems)
• AS numbers assigned by regional Internet Assigned Numbers Authority (IANA) like APNIC
• AS’s configure (often manually) their internal BGP routes/advertisements
• External routes go through complicated filters for forwarding/filtering
• AS BGP routers communicate with each other to keep consistent routing rules

CSE 461 University of Washington

10

Routing with BGP (2)

• Border routers of ASes announce BGP routes
• Route announcements have IP prefix, path vector, next hop
• Path vector is list of ASes on the way to the prefix
• List is to find loops
• Route announcements move in the opposite direction to traffic

CSE 461 University of Washington

11

Routing with BGP (3)

• Application-layer protocol (uses TCP)
• Types of BGP Messages
• Open: Create a relationship
• Keepalive: Still here (reset timeouts)
• Update: A route changed
• Notification: Error message
• Route Refresh: Please send me the route again

​

UW CSE-461

12

Routing with BGP (5)

CSE 461 University of Washington

13

Prefix

Routing with BGP (5)

CSE 461 University of Washington

14

Routing with BGP (6)

Policy is implemented in two ways:

​

1. Border routers of ISP announce paths only to other parties who may use those paths
• Filter out paths others can’t use
2. Border routers of ISP select the best path of the ones they hear in any, non-shortest way

CSE 461 University of Washington

15

Routing with BGP (7)

• transit: AS1 says [B, (AS1, AS3)], [C, (AS1, AS4)] to AS2

CSE 461 University of Washington

16

Routing with BGP (8)

• customer (other side of transit): AS2 says [A, (AS2)] to AS1

CSE 461 University of Washington

17

Routing with BGP (9)

• peer: AS2 says [A, (AS2)] to AS3, AS3 says [B, (AS3)] to AS2

CSE 461 University of Washington

18

Routing with BGP (10)

• AS2 has two routes to B (AS1, AS3) and chooses AS3 (Free!)

CSE 461 University of Washington

19

Internet Exchange Points (IXPs)

• Centralized location for AS interconnect
• Often “public” - anyone can join (if they can pay)
• Usually interesting organizationally, though some big (multi-IXP) players
• Many-to-many instead of 1-1
• Often operates a “route server” to reduce the n-to-n complexity of a ton of peering relationships

20

21

BGP Communities

• Basically labels attached to BGP messages
• Very common trick we’ve seen in routing earlier
• Few with predefined meanings
• NO_EXPORT (0xFFFFFF01) -> Advertise only within AS
• NO_ADVERTISE (0xFFFFFF02) -> Don’t advertise at all
• NO_EXPORT_SUBCONFED (0xFFFFFF03) -> Advertise only with subconfederation
• NOPEER (0xFFFFFF04) -> “Need not” advertise to peers

22

BGP Communities

• User defined BGP communities
• Can be anything, mostly define specific routes
• e.g., “This route is through ATT Canada”
• e.g, :3356:2003 (AS 3356 says 2003)
• Provides a mechanism for “prioritizing” BGP routes
• Backups
• Send to 3353:2003 instead of 3353:150 for some reason
• Blackholing - want to blackhole nearest the AS
• send 3353:9999 to indicate that peer needs to blackhole 3353

23

UW CSE-461

26

UW CSE-461

27

28

BGP Thoughts

• Much more beyond basics to explore!
• Policy is a substantial factor
• Can independent decisions be sensible overall?
• Other important factors:
• Convergence effects
• How well it scales
• Integration with intradomain routing
• And more …

CSE 461 University of Washington

29

Cellular Routing

Addressing in Cellular

• Everyone has a unique physical identifier: SIM Card
• IMSI: “International Mobile Subscriber Identity”
• Has associated mobile provider
• Has K_i secret auth key
• Phone number not present
• Known as “msisdn”

IMSI: identifier per SIM

UW CSE-461

32

3 Digit�Country Code

2 or 3 Digit�Network Code

10 or 9 Digit�Mobile Subscription Identification Number

Always 15 Total Decimal Digits

(An annoying representation to us CS people : ) )

MSISDN

Question…

• Why use two identifiers (IMSI & MSISDN)?

• Backwards compatibility! MSISDN shared with fixed line phone network
• Allows business-level mapping between phone # and actual sim…
• Can keep your phone number when you lose/upgrade your phone!
• But opens the door to “social engineering” sim-swap attacks : (

​

UW CSE-461

34

Cellular Core Networks

In-network routing

1. User dials phone number
2. Number is “looked up” in some database
• If “in network” -> HSS/HLR
• If “out of network”, see next slide
3. If local, we get the associated IMSI
4. Check that sender and send and receiver can receive
5. Look up tower group of IMSIs last registration
6. Page the receiver
7. Bill them both

Out-of-network Routing

• Signaling System No. 7 (SS7)
• Performs number translation, local number portability, prepaid billing, Short Message Service (SMS), roaming, and other stuff
• Either directly connected or connected through aggregators such as Sybase
• Business vs Protocols

Out-of-network Routing

• IP Exchange (IPX)
• Cellular equivalent of IXP
• Interconnect for IP-based telecommunications
• e.g., Voice-over-IP (VoIP)

Cellular Lookups

• An SSP telephone exchange receives a call to an 0800 number. This causes a trigger within the SSP that causes an SCP (Service Control Point) to be queried using SS7 protocols (INAP, TCAP). The SCP responds with a geographic number, e.g. 0121 XXX XXXX, and the call is actually routed to a phone.

​

In small groups…

• What is one advantage of the telephone way of doing things relative to what we saw with BGP?
• What is one advantage of BGP?

UW CSE-461

40

Some food for thought:

• Which network has become more relevant?
• How do the architecture and affordances of a network influence how it grows and develops?