# Experimentation Environments for Data Center Routing Protocols: A Comprehensive Review
## 2 Routing in the Data Center
### Fat-Tree Topology  
A tree-based topology is one of the most representative topology classes for Data Center Networks (DCNs), including basic tree, fat-tree, and 5-stage Clos. A fat-tree data center topology is a particular case of a Clos network [3] where high bisection bandwidth is achieved by interconnecting commodity switches. The fat-tree topology idea was initially proposed for supercomputing [13] and adapted for data center networks [4; 5]. Fat-tree networks are topologically partially ordered graphs and \"level\" denotes the set of nodes at the same height in such a network. In Figure 1, a fat tree with three levels is depicted. The top-level is called Top of Fabric (ToF) or Core and comprises Core switches. The immediately lower level (aggregation level) is composed of Spine switches. Finally, at level zero (edge level), there are Leaf switches. Let us introduce the concept of _Point of Delivery_ (PoD). A PoD is a subset of a fat-tree network typically containing only Leaf and Spine nodes that are fully interconnected. A node in a PoD communicates with nodes in other PoDs via the ToF. The fat-tree topology consists of \(k\) PoDs, numbered left to right from _Pod-0_ to _Pod-(k-1)_, with three layers of switches: leaf switches, spine switches, and core switches. Thus, in a \(k\) PoD fat-tree topology, there are \(k\) switches (each with \(k\) ports) in each PoD arranged in two layers of \(k/2\) switches, one layer for leaf switches and the other for spine switches. Each leaf switch is connected to \(k/2\) spine switches. There are \((k/2)^{2}\) core switches, each of which connects to \(k\) PoDs. With this topology description, the \(k\) factor can be used to calculate the number of nodes in each level of the fabric. Table 1 adopted from [5] summarizes the topological information for a fat tree in terms of the \(k\) factor. Note that there are two types of fat trees: single-plane and multi-plane. In a multi-plane topology (the fat-tree type described above), each ToF node connects to \(k\) PoDs. Contrarily, each ToF node connects to every spine node in a single-plane fat tree. With this configuration, even if all ToFs but one are down, the connectivity between leaves is guaranteed. However, it presents a significant drawback: the number of ports needed for each ToF increase significantly, which might be unfeasible if \(k\) is too large. In this paper, we will always refer to multi-plane fat-tree topologies, following the notation introduced above and describing the fat-tree in terms of the \(k\) factor. Observe that there are other terminologies for describing fat trees, for example, the one used in the RIFT (Routing In Fat Trees) protocol draft [10]. That terminology specifies three parameters: \(K_{LEAF}\), describing the number of ports pointing north or south for the leaf nodes, and \(K_{TOP}\), which describes the same for the spine nodes. Finally, they denote \begin{table}
\begin{tabular}{l l} \hline \hline
**Number of Pods** & \(k\) \\ \hline Core Switches & \((k/2)^{2}\) \\ Spine Switches & \(k^{2}/2\) \\ Leaf Switches & \(k^{2}/2\) \\ Total Switches & \(5k^{2}/4\) \\ Number of Links & \(k^{3}/2\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Fat-Tree topology summary [5]. by \(R\) the redundancy factor, i.e., the number of links from a ToF to a PoD. Following this notation, the topology shown in Figure 1 can be described as \(K_{LEAF}=2\), \(K_{TOP}=2\), \(R=1\). Deploying a topology with these properties has certain benefits for the data center. First, all switches are of the same type with the same number of ports, minimizing down-time periods and reducing operating costs (OPEX). Moreover, there are multiple paths between any pair of hosts. In particular, in a \(k\) fat-tree topology, there are \(k/2\) paths between two Leaf switches within a pod (intra-pod), and there are \(k\) paths between any two Leaf switches that are across pods (inter-pod).