A Scalable, Commodity Data Center Network Architecture Flashcards

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/358

flashcard set

Earn XP

Description and Tags

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.

359 Terms

1
New cards

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.

2
New cards

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.

3
New cards

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.

4
New cards

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.

5
New cards

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.

6
New cards

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.

7
New cards

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.

8
New cards

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.

9
New cards

Parallel Scientific Applications

Large-scale computational workloads that exhibit significant inter-node communication requirements across cluster nodes.

10
New cards

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.

11
New cards

Myrinet

A proprietary high-performance computing interconnect leveraging fat-tree topologies, source routing, and host-measured round-trip latency for load balancing.

12
New cards

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.

13
New cards

Symmetric Multiprocessors (SMPs)

Specialized multiprocessor computing systems that have largely been replaced by clusters of commodity personal computers.

14
New cards

Massively Parallel Processors (MPPs)

Supercomputing architectures that historically leveraged custom interconnect fabrics and have largely been superseded by commodity clusters.

15
New cards

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.

16
New cards

Switch (Paper's Working Definition)

A networking device that performs both layer-2 Ethernet switching and layer-3 IP routing.

17
New cards
<p>Three-Tiered Interconnect Topology (Figure 1)</p>

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.

18
New cards

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.

19
New cards

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.

20
New cards

Edge Tier (Hierarchical Design)

The leaf layer in a hierarchical data center network where switches directly connect to end hosts.

21
New cards

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.

22
New cards

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.

23
New cards

Core Switch Port Density (Traditional)

High-end switching elements located in the aggregation and core tiers that feature 32 to 128 10 GigE ports.

24
New cards

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.

25
New cards

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.

26
New cards

Oversubscription

The ratio of the worst-case achievable aggregate bandwidth among end hosts to the total bisection bandwidth of a communication topology.

27
New cards

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., 1 Gbps1\,\text{Gbps}).

28
New cards

5:1 Oversubscription

A network oversubscription level where only 20% of available host bandwidth is available for worst-case communication patterns.

29
New cards

Typical Data Center Oversubscription Range

Oversubscription levels commonly seen in standard data center designs, typically ranging from 2.5:1 (400 Mbps400\,\text{Mbps}) to 8:1 (125 Mbps125\,\text{Mbps}).

30
New cards

Multi-Rooted Tree

A hierarchical topology featuring multiple core switches designed to provide multi-path diversity and eliminate the single-root bandwidth bottleneck.

31
New cards

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.

32
New cards

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.

33
New cards

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.

34
New cards

ECMP Path Multiplicity Limit

The practical limitation in commercial switches restricting ECMP path diversity to typically 8 to 16 equal-cost paths.

35
New cards

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.

36
New cards

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.

37
New cards

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.

38
New cards

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.

39
New cards
<p>Cost Comparison Curve by Oversubscription (Figure 2)</p>

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.

40
New cards

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.

41
New cards

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.

42
New cards

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.

43
New cards

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.

44
New cards

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.

45
New cards

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.

46
New cards

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.

47
New cards

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.

48
New cards

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.

49
New cards

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.

50
New cards

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.

51
New cards

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.

52
New cards

Charles Clos (1953)

The Bell Labs researcher who originally designed multi-stage non-blocking switching networks using interconnected small telephone crossbar switches.

53
New cards

Clos Network

A class of multi-stage switching topologies that delivers high aggregate bandwidth for many end devices by interconnecting many small, uniform switches.

54
New cards

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.

55
New cards

Parameter kk in kk-ary Fat-Tree

The number of ports on every switch in the topology, which also determines the number of pods in the network.

56
New cards

Pod (in a kk-ary Fat-Tree)

A modular unit of the fat-tree consisting of two layers of switches (edge and aggregation), each layer containing k/2k/2 switches.

57
New cards

Edge Layer within a Pod

The lower layer of k/2k/2 switches in a pod, where each switch directly connects to k/2k/2 end hosts.

58
New cards

Aggregation Layer within a Pod

The upper layer of k/2k/2 switches in a pod, which interconnects the pod's edge switches with the external core switches.

59
New cards

Lower-Layer Switch Connectivity

In each pod, each kk-port lower-layer switch connects to k/2k/2 end hosts and uses its remaining k/2k/2 ports to connect to the pod's k/2k/2 aggregation switches.

60
New cards

Core Switches in a kk-ary Fat-Tree

The top-level switches in the fat-tree, numbering exactly (k/2)2(k/2)^2, each with kk ports connecting to one port in each of the kk pods.

61
New cards

Core Switch Port Connectivity Rule

The rule establishing that the ii-th port of any core switch connects directly to pod ii.

62
New cards

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)(k/2) strides.

63
New cards

Total Hosts Formula in kk-ary Fat-Tree

The mathematical capacity of a kk-ary fat-tree, defined as k34\frac{k^3}{4} total supported hosts.

64
New cards

Switch Homogeneity Advantage

The operational and economic benefit resulting from all switching elements across the entire fat-tree being identical commodity switches.

65
New cards

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.

66
New cards

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.

67
New cards

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.

68
New cards
<p>Simple Fat-Tree Topology with $$k=4$$ (Figure 3)</p>

Simple Fat-Tree Topology with k=4k=4 (Figure 3)

The minimal non-trivial fat-tree topology instance featuring 4 pods, 4 core switches, 16 switches total, and 16 end hosts.

69
New cards

Pod Count in a k=48k=48 Fat-Tree

Exactly 48 pods.

70
New cards

Switches per Pod in a k=48k=48 Fat-Tree

48 switches per pod (24 edge switches and 24 aggregation switches).

71
New cards

Total Core Switches in a k=48k=48 Fat-Tree

Exactly (48/2)2=242=576(48/2)^2 = 24^2 = 576 core switches.

72
New cards

Total Switches in a k=48k=48 Fat-Tree

A total of 2,880 commodity switches (48×48=2,30448 \times 48 = 2,304 pod switches plus 576 core switches).

73
New cards

Hosts per Edge Switch in a k=48k=48 Fat-Tree

24 end hosts connected to each lower-layer switch.

74
New cards

Total Host Capacity in a k=48k=48 Fat-Tree

Exactly 4834=27,648\frac{48^3}{4} = 27,648 end hosts.

75
New cards

Total Subnets in a k=48k=48 Fat-Tree

Exactly 1,152 subnets (each consisting of 24 hosts).

76
New cards

Equal-Cost Paths Between Remote Hosts (k=48k=48)

576 distinct equal-cost paths through the core switches between any pair of hosts located in different pods.

77
New cards

Hardware Cost of k=48k=48 Fat-Tree Interconnect

$8.64 million, compared to $37 million for a traditional hierarchical design supporting 20,000 nodes.

78
New cards

Wiring Complexity Drawback

An inherent challenge of fat-tree topologies resulting from large numbers of copper and fiber cables fanning out across multiple tiers.

79
New cards

Traffic Diffusion (First Half of Journey)

The routing phase where outgoing packets ascend through pod switches and spread evenly among core switches.

80
New cards

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.

81
New cards

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.

82
New cards

OSPF2 Hop-Count Bottleneck

The limitation where standard OSPF selects only a single shortest-path based on hop count out of (k/2)2(k/2)^2 choices, concentrating traffic onto a single port.

83
New cards

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.

84
New cards

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)2k \times (k/2)^2 prefix entries.

85
New cards

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.

86
New cards

Private IP Address Block (10.0.0.0/810.0.0.0/8)

The private IPv4 address allocation block utilized for all hosts and switches within the cluster network.

87
New cards

Pod Switch IP Addressing Format

10.pod.switch.110.pod.switch.1, where pod∈[0,k−1]pod \in [0, k-1] and switch∈[0,k−1]switch \in [0, k-1] numbered from left to right, bottom to top.

88
New cards

Core Switch IP Addressing Format

10.k.j.i10.k.j.i, where jj and ii denote the switch's coordinates in the (k/2)2(k/2)^2 core switch grid, each coordinate in [1,k/2][1, k/2].

89
New cards

Host IP Addressing Format

10.pod.switch.ID10.pod.switch.ID, where ID∈[2,k/2+1]ID \in [2, k/2+1] represents the host's position in that subnet from left to right.

90
New cards

Addressing Scheme Theoretical Host Limit

Up to 4.2 million hosts supported by the addressing convention within the 10.0.0.0/810.0.0.0/8 block.

91
New cards

Subnet Mask per Lower-Layer Switch

A /24/24 subnet prefix assigned to each lower-layer edge switch, accommodating k/2k/2 connected hosts.

92
New cards
<p>Two-Level Routing Table Structure (Figure 4)</p>

Two-Level Routing Table Structure (Figure 4)

A forwarding table containing primary left-handed prefixes and secondary right-handed suffix tables matching host IDs.

93
New cards

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.

94
New cards

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.

95
New cards

Terminating First-Level Prefix

A primary table prefix entry that does not reference a secondary table and immediately determines the packet's output port.

96
New cards

Non-Terminating First-Level Prefix

A primary table prefix entry (such as 0.0.0.0/00.0.0.0/0) that points to a secondary suffix table for further matching.

97
New cards

Left-Handed Prefix Mask

A standard network bitmask of the form 1m032−m1^m 0^{32-m} that matches the most-significant bits of an IP address.

98
New cards

Right-Handed Suffix Mask

A bitmask of the form 032−m1m0^{32-m} 1^m that matches the least-significant bits (host ID) of an IP address.

99
New cards

Maximum Prefixes per Pod Switch

No more than k/2k/2 first-level prefixes stored in the routing table of any pod switch.

100
New cards

Maximum Suffixes per Pod Switch

No more than k/2k/2 second-level suffixes stored in the secondary table of any pod switch.