Fat tree topology

Fat trees are the canonical network topology where

• endpoints (nodes) connect up to leaf (edge) switches
• half the ports of leaf switches connect down to endpoints, and the other half connect up to the next layer of switches
• etc

Non-blocking fat trees

Nonblocking fat trees are a straightforward way to ensure that any two endpoints on a network have full, non-blocking bandwidth between each other.

We’ll describe the properties of these topologies in terms of $k$, the switch radix, which is determined by switch vendors. If Arista talks about a 64-port 800G switch, $k=64$. If they say you can split each port into $8\times 100\text{G}$ links, then $k=512$.

Two-level

Two-level nonblocking trees are created by connecting every edge switch to every core switch:

It’s pretty straightforward because these trees have

• $\frac{k}{2}$ core switches, with all ports facing down
• $k$ edge switches, with half ports facing down, half facing up
• $\frac{3k}{2}=1.5k$ total switches

There are

• $\frac{k}{2}$ endpoints per edge
• $\frac{k^2}{2}$ endpoints total

Three-level

Three-level nonblocking trees are created by forming pods, whereby

1. Endpoints connect up to one of $k/2$ edge switches
2. Each edge switch connects up to $k/2$ aggregation switches
3. Aggregation switches connect up to a distinct set of $k/2$ switches

For example, here is an example using four-port switches ($k=4$):

Edge and aggregation switches both use half of their $k$ ports to connect down, and the other half to connect up. The core switches use all their ports to connect down to aggregation switches.

These trees have:

• $\frac{k^2}{4}$ core switches
• $\frac{k^2}{2}$ aggregation switches
• $\frac{k^2}{2}$ edge switches
• $\frac{5k^2}{4}=1.25k^2$ total switches

There are

• $k$ pods
• $k/2$ edges per pod
• $k/2$ endpoints per edge
• $\frac{k^3}{4}$ endpoints total

Three-level trees are significantly more expensive than two-level trees because the total switch count scales as $O(k^2)$ instead of $O(k)$. This is the reason why tapered trees or alternative topologies like dragonfly are used at large scales.