1 of 27

Discussion 4

1

CS 168, Summer 2025 @ UC Berkeley

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

Routing II 📩

2 of 27

Logistics

  • Project 1B: Basic Traceroute
    • Deadline: Thursday, July 3rd (you can still file an extension!)
  • Project 2: Routing
    • Deadline: Thursday, July 10th

​

​

  • Midterm on July 22nd, 7-9pm (put it in your calendar)!

​

3 of 27

Routing

  • Link-State Routing
  • IP Addressing

4 of 27

Link State Routing

Each router knows its own local “link state”:

  • State of each link to its neighbor (up/down)
  • Associated costs

4

2

1

5 of 27

Link State Routing

  1. Router floods its link state to all other routers.
  2. Each router learns global network topology
  3. Then, computes shortest path themselves!
    • With Dijkstra’s, etc

4

2

1

6 of 27

Link State Routing

  1. Router floods its link state to all other routers.
  2. Each router learns global network topology
  3. Then, computes shortest path themselves!
    • With Dijkstra’s, etc

4

2

1

7 of 27

Distance Vector vs Link State

  • Distance-Vector
    • Global computation (distributed across all nodes)
    • Only local data (local node plus whatever our neighbors told us).
  • Link-State
    • Local computation
    • Using global data (from all parts of the network)

8 of 27

Routing

  • Link-State Routing
  • IP Addressing

9 of 27

Requirements of Addressing

  • Scalable Routing
    • Minimize state exchange needed to create paths
  • Efficient Forwarding
    • Small forwarding tables
    • Fast lookups
  • Host must be able to recognize packet is for them
    • An end-to-end check on routing
    • L3: IP addresses (dynamically assigned)

10 of 27

IP Address

  • 32 bits (for IPv4), split into 4 bytes, written in decimal (each decimal between 0 and 255)
  • Network prefix: /<bits>
    • Size of network address, counting from the leftmost bit
    • Example: 1.2.2.0/23

​

1.2.2.0/23

​

0000 0001 0000 0010 0000 0010 0000 0000

first 23 bits for network address

last 9 bits for host address

11 of 27

Network prefixes (netmasks)

  • Prefix dedicated to network address
  • How can we tell if a host is in a network?
    • Check if the prefix matches!

​

​

Mask: 123.96.0.0/12

01111011 . 01100000 . 00000000 . 00000000

​

Addr: 123.100.42.6

01111011 . 01100100 . 00101010 . 00000110

12 of 27

Classful Addressing

  • Network classes:
    • A (/8): first 8 bits devoted to network
      • First bit is fixed to 0.
      • first byte from 0 to 127
      • Can have ~16M hosts, only 2^7 = 128 nets.

​

    • B (/16): first 16 bits devoted to network (first byte from 128 to 191)
      • First two bits are fixed to 10
      • Can have ~65K hosts, ~16K nets

​

    • C (/24): first 24 bits devoted to network (first byte from 192 to 223)
      • First three bits are fixed to 110
      • Can have only 254 hosts (255 is reserved for last byte) ~2M nets

Network bits

Host bits

Network bits

Host bits

Network bits

Host bits

13 of 27

Classful Addressing

  • Network classes:
    • A (/8): first 8 bits devoted to network
    • B (/16): first 16 bits devoted to network (first byte from 128 to 191)
    • C (/24): first 24 bits devoted to network (first byte from 192 to 223)

​

  • Why is this a bad idea?
    • Very limited choices lead to waste of addresses

​

​

14 of 27

Classless Inter-Domain Routing (CIDR)

  • Use two 32-bit numbers to represent a network
    • Network address = IP Address bitwise AND Subnet Mask
      • IP Address is 192.138.12.2
      • Subnet Mask is 255.248.0.0

​

​

​

​

  • Flexible division of bits:
    • More choices for the size of the network and hosts
  • Offers better size routing table and efficient IP address space

IP Address

Subnet Mask

​

1100 0000 . 1000 1010 . 0000 1100 . 0000 0010

1111 1111 . 1111 1000 . 0000 0000 . 0000 0000

network address 192.136.0.0/13

15 of 27

Prefixes

  • Easy to Add New Hosts
    • New host (5.6.7.213)
    • Forwarding table doesn’t need to be updated!

​

host

host

host

LAN 1

...

host

host

host

LAN 2

...

WAN

WAN

1.2.3.4

1.2.3.7

1.2.3.156

5.6.7.8

5.6.7.9

5.6.7.212

1.2.3.0/24

5.6.7.0/24

forwarding table

host

5.6.7.213

router

router

router

16 of 27

Worksheet

  • Link-State Routing
  • More L3 Link State
  • IP Addressing

17 of 27

Question 1: Link-State Routing

18 of 27

Worksheet

  • Link-State Routing
  • More L3 Link State
  • IP Addressing

19 of 27

Question 2: More L3 Link State

20 of 27

Question 2: More L3 Link State

21 of 27

Question 2: More L3 Link State

22 of 27

Question 2: More L3 Link State

23 of 27

Worksheet

  • Link-State Routing
  • More L3 Link State
  • IP Addressing

24 of 27

Question 3: IP Addressing

25 of 27

Question 3: IP Addressing

26 of 27

Question 3: IP Addressing

27 of 27

Questions?

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