1 of 37

Discussion 5

1

CS 168, Summer 2025 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Iuniana Oprescu

BGP 📣

2 of 37

Logistics

  • Project 2: Routing
    • Deadline: Thursday, July 10th
  • Midterm on July 22nd, 7-9pm (put it in your calendar)!
    • You can bring two 8.5” x 11” cheat sheets, each two-sided (4 sides total)
    • Scope TBD

​

3 of 37

Routing

  • Interdomain Routing
  • Export & Selection
  • Types of ASes

4 of 37

Interdomain Routing

  • Interdomain routing is between autonomous systems (AS)
    • Similar goals as intradomain routing with scalability + policy compliance
    • Autonomous systems want privacy and autonomy
  • Border gateway protocol (BGP) is current design
    • Extends on top of DV (with some crucial differences)

5 of 37

Export & Selection

  • If you are an AS:
    • Route Selection
      • Where you send your packets
      • Determine how to choose a valid route to a given IP prefix, when multiple paths through ASes
    • Route Export
      • Which ASes will receive your route
      • Other ASes will select your route and send traffic to you

6 of 37

Export & Selection

UC Berkeley

AT&T

Google

Comcast

Facebook

Stanford this way!

Stanford this way!

UCB and Facebook export their route to Stanford

They agree to carry AT&T’s traffic to Stanford

7 of 37

Export & Selection

UC Berkeley

AT&T

Google

Comcast

Facebook

Stanford this way!

AT&T selects route through UC Berkeley

AT&T might now send traffic to Stanford via UCB

8 of 37

Export & Selection

UC Berkeley

AT&T

Google

Comcast

Facebook

Stanford this way!

AT&T exports route to Google only

Agrees to carry Google’s traffic to Stanford, but not Comcast’s

9 of 37

Types of ASes (domains)

  • Stub: only sends/receives traffic for its users
    • companies, universities, etc.
  • Transit: carries traffic for other ASes
    • Global ISPs (Tier 1): fully connected mesh
    • Regional ISPs (Tier 2)
    • Local ISPs (Tier 3)
  • Lower tiers buy service from higher tiers
  • What’s the relationship between AS and ISP?
    • All ISPs are ASes, but not all ASes are ISPs
    • E.g. UC Berkeley is not an ISP but it is an AS

Tier 1 ASes

A

B

C

10 of 37

Business Relationship among ASes

  • Two ASes will connect only if they have business relationship:
    • Customer-Provider
      • Provider B carries customer A’s traffic for a fee
    • Peers
      • Peers A, B carry each other’s traffic for free
  • What roles can a global ISP (Tier 1) have?
    • Provider to Tier 2 or Tier 3
    • Peer to other global ISP (tier 1)
    • Not a customer!

11 of 37

Business Relationship Restrictions

  • The graph of peering relations can be cyclic
    • The peer of my peer can also be my peer
    • For example, global ISPs all peer with each other
  • The graph of customer-provider relations must be acyclic

12 of 37

BGP: The Big Picture

  • How does this fit with what we’ve learned so far?

13 of 37

Three parts of Gateway Protocols

  • eBGP
    • Between border routers in different ASes
    • Learn about external routes
  • iBGP
    • Between border routers and other routers within a single AS
    • Learn which border router to use to reach external destinations
  • IGP
    • The protocol used for intradomain routing (e.g. OSPF).
      • Shortest path to subnet in the same AS
      • Shortest path to border router for given external network
    • Just a different name for L3 routing as we’ve talked about earlier

14 of 37

BGP Route Attributes

  • Attributes: Parameters used in route selection
    • Local attributes
      • ASes keep them private
      • Not included in eBGP route announcements
      • E.g. LOCAL_PREF
    • Nonlocal attributes:
      • propagated with eBGP route announcements
      • E.g. AS_PATH

15 of 37

Route Selection in Priority Order

Priority

Rule

Remarks

1

LOCAL PREF

Pick highest LOCAL PREF

2

ASPATH

Pick shortest ASPATH length

3

IGP cost

Lowest IGP cost to next hop (egress router)

4

MED

Lowest MED preferred

5

Router ID

Smallest next-hop router’s IP address as tie-breaker

  • Classless addressing is used

16 of 37

Priority Oscillation

17 of 37

Policy Oscillation

3

0

1

2

Each node prefers route through neighbor over direct route.

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

18 of 37

Policy Oscillation 1

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 advertises 1→0 to 2

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

19 of 37

Policy Oscillation 2

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

3 advertises 3→0 to 1

20 of 37

Policy Oscillation 3

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

1 withdraws its path of 1→0 from 2 (because 1 now takes 1->3->0)

21 of 37

Policy Oscillation 4

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

2 now advertises 2→0 to 3 �(3 would take it as it favors its neighbor)

22 of 37

Policy Oscillation 5

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

3 now withdraws 3→0 from 1

23 of 37

Policy Oscillation 6

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

1 again advertises its path 1→0

24 of 37

Policy Oscillation 7

3

0

1

2

Each node prefers route through neighbor over direct route.

Suppose initially each node only knows the shortest path to 0 (green arrow).

1 knows 1→0

2 knows 2→0

3 knows 3→0

​

1 prefers reaching 0 through 2 or 3

2 prefers reaching 0 through 1 or 3

3 prefers reaching 0 through 1 or 2

​

Back to where we started! :(

2 withdraws its path 2→0 from 3

25 of 37

Why doesn’t this happen in reality?

  • Gao-Rexford!

26 of 37

Gao-Rexford Policy

Destination prefix advertised by…

Export route to…

Customer

Everyone� (providers, peers, other customers)

Peer

Customers

Provider

Customers

27 of 37

Routing Follows the Money

Traffic allowed

Traffic not allowed

Peers do not provide transit to other peers!

A

B

C

D

E

F

G

28 of 37

Gao-Rexford Policy Continued

​

​

​

​

​

​

​

    • Green arrow is where you learn the route
    • Purple arrows are where you export the route
    • With Gao-Rexford
      • The AS policy graph is a DAG
      • Routes are “valley free”/”single-peaked”

peers

providers

customers

29 of 37

Gao-Rexford avoids Policy Oscillation

  • Example shown before did not use Gao-Rexford (why?)
    • 1, 2, and 3 are peers
    • 0 is the provider to 1, 2, and 3
    • Peers don’t advertise route learned from providers to each other
      • i.e. 1 would never advertise 1->0 (learned from 1’s provider 0) to 2 (1’s peer)

3

0

1

2

Destination prefix advertised by…

Export route to…

Peer

Customers

30 of 37

Worksheet

  • True/False
  • Interdomain vs Intradomain
  • BGP

31 of 37

Question 1: True/False

32 of 37

Worksheet

  • True/False
  • Interdomain vs Intradomain
  • BGP

33 of 37

Question 2: Interdomain vs Intradomain

34 of 37

Worksheet

  • True/False
  • Interdomain vs Intradomain
  • BGP

35 of 37

Question 3: BGP

36 of 37

Question 3: BGP

37 of 37

Questions?

Feedback Form: https://tinyurl.com/cs168-su25-disc-feedback