1 of 54

1

CS 168, Summer 2025 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Ankit Singla, Murphy McCauley

Datacenter Routing

Lecture 19 (Datacenters 2)

2 of 54

Datacenter Routing

Lecture 19, CS 168, Summer 2025

Datacenter Routing

Datacenter Addressing

Virtualization and Encapsulation

Virtualization
Overlay and Underlay Networks
Multi-Tenancy and�Private Networks

3 of 54

Why are Datacenters Different? – Multiple Paths

Recall: In a Clos network, there are many paths between two servers.

Our routing algorithms so far pick a single path from source to destination.

How do we modify our routing protocols to find multiple paths?

4 of 54

Why are Datacenters Different? – Multiple Paths

We want routing protocols to find multiple paths between two hosts.

2

A

R3

B

2

1

A

B

C

D

Bandwidth:

If A→B only used a single path, it can only send at 1 Gbps.
If A→B split traffic across both paths, it can send at 2 Gbps.
Our routing protocols can only send traffic along one path.

Coordination:

A→B and C→D might send along the same path, overloading it.
C→D should switch to using the bottom path instead.
Our routing protocols don't assume coordination between flows.

1 on all links

R1

R2

R4

R1

R2

R3

R4

5 of 54

Why are Datacenters Different? – Multiple Paths

Equal Cost Multi-Path (ECMP) finds all of the shortest paths (with equal cost).

Then, we load-balance packets across those paths.

2

A

R1

R2

R3

R4

B

2

1

A

R1

R2

R3

R4

B

C

D

Bandwidth:

If A→B only used a single path, it can only send at 1 Gbps.
If A→B split traffic across both paths, it can send at 2 Gbps.
Our routing protocols can only send traffic along one path.

Coordination:

A→B and C→D might send along the same path, overloading it.
C→D should switch to using the bottom path instead.
Our routing protocols don't assume coordination between flows.

1 on all links

6 of 54

ECMP Load-Balancing

If there are multiple shortest paths, how does the router load-balance packets between those paths?

We need a function to compute a link for each packet: f(packet) → link.
Routers receive a packet and run this function to pick a link.
What's a good f?

A

B

Top path is not the shortest. Packets won't be sent this way.

R1 has to load-balance packets out of these 2 links.

R1

Payload

Layer 4 Header

Layer 3 Header

Link 1

Link 3

Link 2

f

=

Link ____

7 of 54

ECMP Load-Balancing Strategy #1 – Round-Robin

Round-robin: Ignore packet contents, and alternate sending between links.

Link 1, 2, 1, 2, 1, 2, ...

Problem: TCP packet reordering.

Equal-cost paths might have different latency. (Cost could be based on something else.)
If odd packets on slow path, and even packets on fast path:�The recipient gets all the even packets before the odd packets.
Recipient has to buffer packets, resulting in poor performance.

Payload

Destination port

Source port

f

=

Link ____

Protocol (TCP/UDP)

Destination IP

Source IP

8 of 54

ECMP Load-Balancing Strategy #2 – Destination-Based

Use destination IP to choose link.

Problem: If lots of sources sending to the same destination, one link is overloaded.

Payload

Destination port

Source port

f

=

Link ____

Protocol (TCP/UDP)

Destination IP

Source IP

9 of 54

ECMP Load-Balancing Strategy #3 – Source-Based

Use source IP to choose link.

Problem: If the same source is sending to lots of destinations, one link is overloaded.

Payload

Destination port

Source port

f

=

Link ____

Protocol (TCP/UDP)

Destination IP

Source IP

10 of 54

ECMP Load-Balancing Strategy #4 – IP-Based

Use source and destination IP to choose link.

Using both values helps spread out packets across links.

Problem: What if there are multiple large flows between the same two servers?

Payload

Destination port

Source port

f

=

Link ____

Protocol (TCP/UDP)

Destination IP

Source IP

11 of 54

ECMP Load-Balancing Strategy #5 – Flow-Based

Use 5 values to choose link:

Source and destination IP.
Source and destination port.
Protocol (TCP or UDP).

This is called per-flow load-balancing.

Each flow has a unique 5-tuple.
All packets in the same flow use the same link (no reordering problems).
Modern commodity routers have support for reading these 5 values.

Payload

Destination port

Source port

f

=

Link ____

Protocol (TCP/UDP)

Destination IP

Source IP

Note: This does not account for flows being different sizes. Tracking flow size is more complex, for not a lot of benefit.

12 of 54

Multi-Path Distance-Vector Protocols

How do we adjust distance-vector protocols to support multiple paths?

Recall distance-vector: Routers advertise paths and costs.
If the advertised path is better than the current best path, accept.

A

R1

B

R3

R2

R4

I'm R2.�I can reach B with cost 2.

R1's forwarding table
To:	Via:	Cost:
B	R2	3

13 of 54

Multi-Path Distance-Vector Protocols

Normal distance-vector:

If the advertised path has the same cost as the current best-known cost, reject.

A

R1

B

R3

R2

R4

I'm R4.�I can reach B with cost 2.

R1's forwarding table
To:	Via:	Cost:
B	R2	3

I already have a cost-3 path to B.

Your path is not better, so I'll ignore it.

14 of 54

Multi-Path Distance-Vector Protocols

Multi-path distance-vector:

If the advertised path has the same cost as the current best-known cost, accept.
The forwarding table can now store multiple next-hops per destination.
Use f (load-balancing) to choose a next-hop for each packet.

R1's forwarding table
To:	Via:	Cost:
B	R2	3
B	R4	3

Your path is equally good.�I'll remember both paths.

A

R1

B

R3

R2

R4

I'm R4.�I can reach B with cost 2.

15 of 54

Multi-Path Link-State Protocols

Recall link-state: Each router stores the full network graph.

Each router uses the graph to calculate shortest path to each destination.
Must extend protocol to calculate all shortest paths to each destination.
The forwarding table can now store multiple next-hops per destination.

Just like multi-path distance-vector.

16 of 54

Datacenter Addressing

Lecture 19, CS 168, Summer 2025

Datacenter Routing

Datacenter Addressing

Virtualization and Encapsulation

Virtualization
Overlay and Underlay Networks
Multi-Tenancy and�Private Networks

17 of 54

Why are Datacenters Different? – Scaling Routing

Scaling routing protocols in datacenters:

Distance-vector: Separate advertisements per destination.

In a datacenter: 100,000+ destinations being advertised.

Link-state: Advertisements get flooded along every link.

In a datacenter: Clos networks can have 10,000+ links.

Recall: Clos networks scale by using commodity switches.

Memory, CPU, and forwarding table resources are limited.
We can't store table entries for every destination.

18 of 54

Topology-Aware Addressing

We can scale routing using hierarchical addressing.

On the Internet: Hierarchy is based on geography and organizations.
In datacenters: Hierarchy is based on physical organization in the datacenter.

The address tells us where in the building the host is.
Exploits the idea that the topology is regular (e.g. racks organized in rows).

19 of 54

Topology-Aware Addressing

10.1.0.0/16

10.3.1.0/24

10.3.2.0/24

10.4.1.0/24

10.4.2.0/24

10.2.1.0/24

10.2.2.0/24

10.1.1.0/24

10.1.2.0/24

10.1.1.1

10.1.1.2

10.1.2.1

10.1.2.2

10.2.1.1

10.2.1.2

10.2.2.1

10.2.2.2

10.3.1.1

10.3.1.2

10.3.2.1

10.3.2.2

10.4.1.1

10.4.1.2

10.4.2.1

10.4.2.2

R's forwarding table
To:	Use:
10.1.0.0/16	Link 1
10.2.0.0/16	Link 2
10.3.0.0/16	Link 3
10.4.0.0/16	Link 4

10.4.0.0/16

10.3.0.0/16

10.2.0.0/16

R

20 of 54

Topology-Aware Addressing

Routing aggregation makes our forwarding tables:

Smaller: One entry represents a range of hosts.
More stable: If a host inside a subnet goes away, R's table doesn't change.

Nice example of what can be achieved in a controlled network.

Requires the operator to assign all the addresses.

R's forwarding table
To:	Use:
10.1.0.0/16	Link 1
10.2.0.0/16	Link 2
10.3.0.0/16	Link 3
10.4.0.0/16	Link 4

21 of 54

Virtualization

Lecture 19, CS 168, Summer 2025

Datacenter Routing

Datacenter Addressing

Virtualization and Encapsulation

Virtualization
Overlay and Underlay Networks
Multi-Tenancy and�Private Networks

22 of 54

Physical Datacenter Limitations

If we hosted applications directly on servers, we'd have some problems.

Google introduces a new application: Somebody has to install a new server.
The application grows: Somebody has to install more servers.
A link goes down: Somebody has to move the server somewhere else.

Fundamental issue:

Physical datacenters are rigid and structured.
But, applications are constantly changing.

Hosts are rapidly added, removed, and moved.

Changing physical infrastructure is hard.

23 of 54

Physical Datacenter Limitations

Scaling is another problem.

A lightweight application might not need all the server resources.
But the application still wants its own server (e.g. for security reasons).
Inefficient use of resources.

Routing is another problem.

Applications might want to choose their own IP addresses.

Example: It wants to follow organizational hierarchy.
Its chosen address might not be consistent with datacenter addresses.

If the application moves elsewhere in the datacenter, it might want to keep its original address.

But the datacenter addressing requires us to change addresses.

24 of 54

Physical Datacenter Limitations

Applications choosing IP addresses is incompatible with our datacenter addressing.

Applications moving and keeping the same IP address is also incompatible.

R1

R2

R3

R

10.1.0.0/16

10.2.0.0/16

10.3.0.0/16

I am a Google search server, and I want to use IP address 192.0.2.1.

I am a YouTube server, and I want to use IP address 10.16.1.2.

R's forwarding table
To:	Next hop:
10.2.0.0/16	R2
10.3.0.0/16	R3
192.0.2.1	R1
10.16.1.2	R1

We can't aggregate these rows!

25 of 54

Virtual Machines

Virtualization lets us run one or more virtual machines on a single physical machine.

Each virtual machine (VM) provides the illusion of a dedicated physical machine.
The physical machine runs a hypervisor that gives each VM its own operating system, and manages resources between VMs.

Physical server (hardware)

Hypervisor (software)

VM 1

VM 3

VM 2

I want to write to disk.

VM 1 thinks it's talking to its own hardware disk, but it's actually talking to the hypervisor.

The hypervisor talks to the hardware disk (and ensures each VM gets its own dedicated slice of disk).

26 of 54

Virtual Machines

Why is virtualization useful?

We can rapidly add, remove, and move VMs without touching physical servers.
Multiple applications can run on a single server.

Hypervisor can enforce separation of servers (e.g. for security).
More efficient use of resources.

Physical server (hardware)

Hypervisor (software)

VM 1

VM 3

VM 2

27 of 54

Virtual Switches

The physical server has a single network card (NIC) and a single IP address.

We need to give each VM the illusion of its own dedicated NIC and IP address.
The physical NIC receives packets meant for several VMs.

Solution: Run a virtual switch in software, on the server.

Does the same things as a real switch (e.g. forwards packets).
Each VM is connected to the virtual switch (in software).
The virtual switch uses the physical NIC to send and receive packets.

Server 1.1.1.1

VM1

R1

Virtual Switch

VM2

192.0.2.1

192.168.1.2

10.16.1.2

VM3

Note: Virtual switches can run in software on a general-purpose CPU because they serve less traffic than a real-world hardware switch. (Just the traffic from the VMs on that server.)

28 of 54

Overlay and Underlay Networks

Lecture 19, CS 168, Summer 2025

Datacenter Routing

Datacenter Addressing

Virtualization and Encapsulation

Virtualization
Overlay and Underlay Networks
Multi-Tenancy and�Private Networks

29 of 54

Routing with Virtualization

VMs let us easily add/remove servers, and use server resources efficiently.

But we still haven't solved our routing problem.

VM addresses don't fit in the datacenter addressing scheme.
Datacenter routers can't use aggregation to scale.

Server 1.1.1.1

VM1

R1

Virtual Switch

VM2

192.0.2.1

192.168.1.2

10.16.1.2

VM3

30 of 54

Problem: Routing with Virtualization

Key problem: We have 2 different addressing systems to think about.

Think of them as two "sub-layers" inside Layer 3 (IP).

The underlay network thinks in terms of physical addresses.

Physical servers and routers in the datacenter.
Addresses based on datacenter topology.

The overlay network (VMs) thinks in terms of virtual addresses.

Addresses based on organizational hierarchy.

Underlay

Overlay

Server 1 1.1.1.1

R1

R2

R3

R4

Virtual Switch

V2

V1

V3

192.0.2.1

192.168.1.2

10.16.1.2

Server 2 2.2.2.2

Virtual Switch

V5

V4

V6

10.7.7.7

10.8.8.8

192.0.5.7

Layering helps us separate organization schemes.

One way of addressing is based on physical topology It's saying