1/358
Comprehensive vocabulary flashcards covering the architecture, addressing, two-level routing tables, flow classification and scheduling, fault tolerance, packaging, power/heat characteristics, and evaluation results of the scalable commodity data center network architecture by Al-Fares, Loukissas, and Vahdat.
Scalable Interconnection Bandwidth
A primary design goal requiring that an arbitrary host in the data center can communicate with any other host at the full bandwidth of its local network interface.
Economies of Scale (Data Center Design)
The design principle of leveraging cheap, off-the-shelf commodity Ethernet switches as the foundational building block for large-scale data center networks, analogous to how commodity PCs displaced SMPs and MPPs.
Backward Compatibility (Architecture Design Goal)
The requirement that the interconnect architecture works seamlessly with unmodified end hosts running standard Ethernet, IP, and TCP protocols and unmodified applications.
Inter-Node Communication Bandwidth
The principal performance bottleneck in large-scale computing clusters, where remote data exchange is required before local computation or I/O can proceed.
MapReduce Data Shuffling
The phase in MapReduce processing requiring massive inter-node communication to transport intermediate data from the map phase across cluster nodes before proceeding with the reduce phase.
Cluster-Based File Systems
Distributed storage systems (such as GFS, GPFS, and XFS) running across cluster nodes that require remote-node access to execute I/O operations.
Inverted Index Querying
A web search communication pattern that requires parallel communication with every node in a cluster hosting the index to return the most relevant results.
Service-Oriented Architecture (SOA)
A software architecture where servicing a single user request (such as retrieving a web page) requires coordination and communication with hundreds of individual sub-services on remote nodes.
Parallel Scientific Applications
Large-scale computational workloads that exhibit significant inter-node communication requirements across cluster nodes.
InfiniBand
A specialized, non-commodity communication fabric and protocol that scales to thousands of nodes but is expensive and not natively compatible with standard TCP/IP applications.
Myrinet
A proprietary high-performance computing interconnect leveraging fat-tree topologies, source routing, and host-measured round-trip latency for load balancing.
Commodity Ethernet Switch Approach
The practice of using off-the-shelf Ethernet switches and routers to interconnect cluster machines, supporting standard TCP/IP, operating systems, and familiar management tools.
Symmetric Multiprocessors (SMPs)
Specialized multiprocessor computing systems that have largely been replaced by clusters of commodity personal computers.
Massively Parallel Processors (MPPs)
Supercomputing architectures that historically leveraged custom interconnect fabrics and have largely been superseded by commodity clusters.
Single-Path Routing Bottleneck
A limitation in hierarchical tree networks where routing over a single path concentrates all traffic at higher levels, limiting overall cluster bandwidth to the root switch capacity.
Switch (Paper's Working Definition)
A networking device that performs both layer-2 Ethernet switching and layer-3 IP routing.

Three-Tiered Interconnect Topology (Figure 1)
A hierarchical data center tree architecture consisting of edge switches at the leaves, aggregation switches in the middle tier, and core switches at the root.
Core Tier (Hierarchical Design)
The top root layer of a multi-tiered data center network consisting of high-end switches that aggregate traffic between aggregation switches.
Aggregation Tier (Hierarchical Design)
The middle layer of switches in a three-tier hierarchical tree topology that multiplexes traffic between edge switches and core switches.
Edge Tier (Hierarchical Design)
The leaf layer in a hierarchical data center network where switches directly connect to end hosts.
Two-Tiered Network Design
A hierarchical tree interconnect consisting only of edge and core tiers, typically limited to supporting between 5,000 and 8,000 hosts.
Leaf Switch Port Configuration (Traditional)
A switch deployed at the edge of a hierarchy with 48 to 288 GigE ports for host connectivity and multiple 10 GigE uplinks to the aggregation tier.
Core Switch Port Density (Traditional)
High-end switching elements located in the aggregation and core tiers that feature 32 to 128 10 GigE ports.
High-End Edge Switch Model (Study Baseline)
A 48-port GigE switch equipped with four 10 GigE uplinks, representing the edge tier baseline in the authors' background study.
High-End Core Switch Model (Study Baseline)
A 128-port 10 GigE switch used in the aggregation and core tiers representing the high-end density baseline.
Oversubscription
The ratio of the worst-case achievable aggregate bandwidth among end hosts to the total bisection bandwidth of a communication topology.
1:1 Oversubscription
A network state where all hosts can simultaneously communicate with arbitrary other hosts at the full bandwidth of their local network interfaces (e.g., 1Gbps).
5:1 Oversubscription
A network oversubscription level where only 20% of available host bandwidth is available for worst-case communication patterns.
Typical Data Center Oversubscription Range
Oversubscription levels commonly seen in standard data center designs, typically ranging from 2.5:1 (400Mbps) to 8:1 (125Mbps).
Multi-Rooted Tree
A hierarchical topology featuring multiple core switches designed to provide multi-path diversity and eliminate the single-root bandwidth bottleneck.
Singly Rooted Core Host Limit (1:1 Oversubscription)
The maximum cluster size that can be supported at 1:1 oversubscription using a single 128-port 10 GigE switch at the core without multi-path routing: exactly 1,280 nodes.
Equal-Cost Multi-Path (ECMP)
A routing technique supported on enterprise switches that enables static load splitting among multiple parallel equal-cost paths to a destination.
Static Load Splitting (ECMP)
The mechanism by which ECMP allocates traffic across multiple paths without taking flow bandwidth into account, often leading to bottlenecked oversubscription.
ECMP Path Multiplicity Limit
The practical limitation in commercial switches restricting ECMP path diversity to typically 8 to 16 equal-cost paths.
ECMP Routing Table Multiplicative Growth
The rapid expansion of forwarding table entries as the number of parallel paths considered increases, leading to higher switch cost and lookup latency.
Assumed Cost of 48-Port GigE Switch
An assumed equipment cost of $7,000 for each 48-port GigE switch deployed at the edge of the hierarchical network.
Assumed Cost of 128-Port 10 GigE Switch
An assumed equipment cost of $700,000 for each 128-port 10 GigE switch deployed in the aggregation and core layers.
Estimated Cost for 20,000 Hosts at 1:1 Oversubscription
Approximately $37 million for traditional hierarchical switching hardware to deliver non-blocking full bisection bandwidth to 20,000 hosts.

Cost Comparison Curve by Oversubscription (Figure 2)
A plot depicting network equipment cost against host count for 1:1, 3:1, and 7:1 oversubscription hierarchies compared to the commodity fat-tree.
GigE vs. 10 GigE Price Differential (2008)
Roughly a factor of 5 differential in price per port per bit/sec when comparing GigE to 10 GigE switches.
2002 Hierarchical 10 GigE Switch
A 28-port 10 GigE switch supporting a maximum non-blocking cluster of 4,480 hosts at a cost of $25.3K per GigE host.
2002 Fat-Tree GigE Switch
A 28-port GigE switch supporting a maximum non-blocking fat-tree cluster of 5,488 hosts at a cost of $4.5K per GigE host.
2004 Hierarchical 10 GigE Switch
A 32-port 10 GigE switch supporting a maximum non-blocking cluster of 7,680 hosts at a cost of $4.4K per GigE host.
2004 Fat-Tree GigE Switch
A 48-port GigE switch supporting a maximum non-blocking fat-tree cluster of 27,648 hosts at a cost of $1.6K per GigE host.
2006 Hierarchical 10 GigE Switch
A 64-port 10 GigE switch supporting a maximum non-blocking cluster of 10,240 hosts at a cost of $2.1K per GigE host.
2006 Fat-Tree GigE Switch
A 48-port GigE switch supporting a maximum non-blocking fat-tree cluster of 27,648 hosts at a cost of $1.2K per GigE host.
2008 Hierarchical 10 GigE Switch
A 128-port 10 GigE switch supporting a maximum non-blocking cluster of 20,480 hosts at a cost of $1.8K per GigE host.
2008 Fat-Tree GigE Switch
A 48-port GigE switch supporting a maximum non-blocking fat-tree cluster of 27,648 hosts at a cost of $0.3K per GigE host.
Port Density Scalability Barrier
The historical constraint where traditional hierarchical cluster size was strictly bound by the maximum port density of available high-end switches.
Technical Infeasibility of 27,648-Node 10 Gbps Hierarchical Cluster
The inability to construct a non-blocking 27,648-node 10 Gbps cluster using traditional hierarchies due to the complete lack of Ethernet standards or products faster than 10 GigE.
Hypothetical 48-Port 10 GigE Fat-Tree Cost
Over $690 million, representing the theoretical cost of interconnecting 27,648 nodes at 10 Gbps full bandwidth using near-commodity 48-port 10 GigE switches.
Charles Clos (1953)
The Bell Labs researcher who originally designed multi-stage non-blocking switching networks using interconnected small telephone crossbar switches.
Clos Network
A class of multi-stage switching topologies that delivers high aggregate bandwidth for many end devices by interconnecting many small, uniform switches.
Fat-Tree Topology (Leiserson 1985)
A network topology where communication links increase in total capacity moving up the tree toward the root, implemented here using identical commodity switching elements.
Parameter k in k-ary Fat-Tree
The number of ports on every switch in the topology, which also determines the number of pods in the network.
Pod (in a k-ary Fat-Tree)
A modular unit of the fat-tree consisting of two layers of switches (edge and aggregation), each layer containing k/2 switches.
Edge Layer within a Pod
The lower layer of k/2 switches in a pod, where each switch directly connects to k/2 end hosts.
Aggregation Layer within a Pod
The upper layer of k/2 switches in a pod, which interconnects the pod's edge switches with the external core switches.
Lower-Layer Switch Connectivity
In each pod, each k-port lower-layer switch connects to k/2 end hosts and uses its remaining k/2 ports to connect to the pod's k/2 aggregation switches.
Core Switches in a k-ary Fat-Tree
The top-level switches in the fat-tree, numbering exactly (k/2)2, each with k ports connecting to one port in each of the k pods.
Core Switch Port Connectivity Rule
The rule establishing that the i-th port of any core switch connects directly to pod i.
Aggregation-to-Core Stride Rule
The cabling scheme where consecutive ports of each aggregation switch in a pod connect to core switches at (k/2) strides.
Total Hosts Formula in k-ary Fat-Tree
The mathematical capacity of a k-ary fat-tree, defined as 4k3 total supported hosts.
Switch Homogeneity Advantage
The operational and economic benefit resulting from all switching elements across the entire fat-tree being identical commodity switches.
Rearrangeably Non-Blocking
A network property meaning that for any arbitrary communication pattern among hosts, there exists some set of paths that can saturate the full network interface bandwidth of all hosts.
Packet Reordering Constraint
The operational challenge of multi-path routing where TCP performance degrades if packets belonging to the same flow are delivered out of order.
Subnet Definition in Proposed Fat-Tree
The subnet formed by all hosts directly connected to the same edge switch; intra-subnet traffic is purely layer-2 switched, while all other traffic is layer-3 routed.

Simple Fat-Tree Topology with k=4 (Figure 3)
The minimal non-trivial fat-tree topology instance featuring 4 pods, 4 core switches, 16 switches total, and 16 end hosts.
Pod Count in a k=48 Fat-Tree
Exactly 48 pods.
Switches per Pod in a k=48 Fat-Tree
48 switches per pod (24 edge switches and 24 aggregation switches).
Total Core Switches in a k=48 Fat-Tree
Exactly (48/2)2=242=576 core switches.
Total Switches in a k=48 Fat-Tree
A total of 2,880 commodity switches (48×48=2,304 pod switches plus 576 core switches).
Hosts per Edge Switch in a k=48 Fat-Tree
24 end hosts connected to each lower-layer switch.
Total Host Capacity in a k=48 Fat-Tree
Exactly 4483=27,648 end hosts.
Total Subnets in a k=48 Fat-Tree
Exactly 1,152 subnets (each consisting of 24 hosts).
Equal-Cost Paths Between Remote Hosts (k=48)
576 distinct equal-cost paths through the core switches between any pair of hosts located in different pods.
Hardware Cost of k=48 Fat-Tree Interconnect
$8.64 million, compared to $37 million for a traditional hierarchical design supporting 20,000 nodes.
Wiring Complexity Drawback
An inherent challenge of fat-tree topologies resulting from large numbers of copper and fiber cables fanning out across multiple tiers.
Traffic Diffusion (First Half of Journey)
The routing phase where outgoing packets ascend through pod switches and spread evenly among core switches.
Deterministic Routing (Second Half of Journey)
The routing phase where a core switch directs a packet along a single downward link into the destination pod.
Filtering Traffic Diffusers
The operational role of the lower and upper pod switches, which filter intra-pod traffic toward local subnets while diffusing inter-pod traffic upward.
OSPF2 Hop-Count Bottleneck
The limitation where standard OSPF selects only a single shortest-path based on hop count out of (k/2)2 choices, concentrating traffic onto a single port.
Core Congestion via OSPF Arrival Interleaving
Severe congestion caused when arbitrary timing of OSPF messages leads multiple switches to select the same small subset of core switches.
Prefix Explosion in OSPF-ECMP
A scaling failure where providing multi-path across pods requires each lower-level pod switch to maintain k×(k/2)2 prefix entries.
Deterministic Entropy via Host IDs
The use of the least-significant byte of the destination IP address to deterministically distribute outgoing flows evenly across core switches while avoiding packet reordering.
Private IP Address Block (10.0.0.0/8)
The private IPv4 address allocation block utilized for all hosts and switches within the cluster network.
Pod Switch IP Addressing Format
10.pod.switch.1, where pod∈[0,k−1] and switch∈[0,k−1] numbered from left to right, bottom to top.
Core Switch IP Addressing Format
10.k.j.i, where j and i denote the switch's coordinates in the (k/2)2 core switch grid, each coordinate in [1,k/2].
Host IP Addressing Format
10.pod.switch.ID, where ID∈[2,k/2+1] represents the host's position in that subnet from left to right.
Addressing Scheme Theoretical Host Limit
Up to 4.2 million hosts supported by the addressing convention within the 10.0.0.0/8 block.
Subnet Mask per Lower-Layer Switch
A /24 subnet prefix assigned to each lower-layer edge switch, accommodating k/2 connected hosts.

Two-Level Routing Table Structure (Figure 4)
A forwarding table containing primary left-handed prefixes and secondary right-handed suffix tables matching host IDs.
Primary Routing Table
The first-level routing table storing standard left-handed network prefix masks that either terminate or point to a secondary suffix table.
Secondary Routing Table
The second-level table containing right-handed suffix masks and output ports, evaluated when a primary lookup yields a non-terminating prefix.
Terminating First-Level Prefix
A primary table prefix entry that does not reference a secondary table and immediately determines the packet's output port.
Non-Terminating First-Level Prefix
A primary table prefix entry (such as 0.0.0.0/0) that points to a secondary suffix table for further matching.
Left-Handed Prefix Mask
A standard network bitmask of the form 1m032−m that matches the most-significant bits of an IP address.
Right-Handed Suffix Mask
A bitmask of the form 032−m1m that matches the least-significant bits (host ID) of an IP address.
Maximum Prefixes per Pod Switch
No more than k/2 first-level prefixes stored in the routing table of any pod switch.
Maximum Suffixes per Pod Switch
No more than k/2 second-level suffixes stored in the secondary table of any pod switch.