Abstract
Modern datacenter traffic is often highly skewed, yet network topologies are frequently designed for uniform, worst-case scenarios. This paper presents CACD (Communication-Aware Continuous-Discrete), a framework that leverages information theory to design sparse, robust networks. By mapping nodes to a 1D cyclic space using Shannon-Fano-Elias coding, CACD ensures that frequently communicating nodes are placed closer together, resulting in expected path lengths proportional to the entropy of the traffic matrix.
The Challenge of Non-Uniform Traffic
Traditional network topologies, such as Clos or hypercubes, are typically optimized for high bisection bandwidth regardless of actual usage patterns. However, real-world datacenter traffic is rarely uniform; it is often dominated by a small subset of high-activity nodes.
While "demand-aware" topologies exist, they often force a compromise between efficiency and resilience. Tree-based structures like SplayNets handle skewed traffic well but are fragile—a single node failure can partition the network. Conversely, robust grids or random graphs do not naturally minimize distances between high-traffic pairs. The authors aim to bridge this gap with a design that is simultaneously efficient, sparse, fair, and robust.
The CACD Framework
The CACD design bridges continuous geometric spaces and discrete graph structures through a multi-step process:
- Continuous Foundation: The model begins with a continuous graph on a 1D cyclic space (a circle). In this space, edges are defined by mathematical shifts (left, right, and backward).
- Entropy-Based Mapping: Using Shannon-Fano-Elias coding, the circle is partitioned into segments. Each node is assigned a segment length proportional to its communication probability ($p_i$). High-activity nodes receive larger segments, naturally attracting more connections.
- Discretization: A discrete edge is formed between two nodes if their segments in the continuous space are connected by the underlying continuous graph.
- Greedy Routing: A dual-mode routing scheme (forward and backward) allows the network to achieve path lengths bounded by the entropy of the traffic distribution.
Key Insights: Topology as Coding
The core innovation of CACD is treating physical structure as a form of compression. Just as Huffman coding uses fewer bits for frequent symbols, CACD uses shorter paths for frequent communication pairs. The authors prove that the expected path length (EPL) is bounded by $H(p) + 2$, where $H(p)$ is the entropy of the traffic. This provides a formal guarantee that performance scales with traffic predictability.
Furthermore, CACD ensures "degree fairness." Unlike star topologies where a central hub is overwhelmed, a node's degree in CACD is proportional to its own activity level. Because the design is based on De Bruijn graph properties, it inherits high edge expansion, providing significantly better resilience to failures than tree-based designs.
Results and Performance
Evaluations using Zipf’s Law distributions on networks of 300 to 1,000 nodes revealed several key advantages:
- Path Efficiency: In highly skewed scenarios, CACD path lengths dropped to 3–5 hops, while standard designs remained at approximately 18 hops.
- Sparsity and Scalability: Total edges are capped at roughly $4n$, and path lengths grow with entropy $H(p)$ rather than the more aggressive $O(\log n)$ seen in traditional networks.
- Failure Resilience: Under a 10% random edge failure rate, CACD maintained a message success rate exceeding 80%, outperforming non-coding-based greedy routing schemes.
Future Directions
While CACD offers a robust theoretical foundation, the current model is limited to a 1D circle and assumes a fixed demand matrix. Future work may explore higher-dimensional spaces (like a torus) to improve path diversity and develop reconfigurable versions of the topology that can adapt to shifting real-time traffic patterns. Additionally, translating these algorithmic segments into physical hardware, such as optical switches, remains a key engineering challenge.
Summary updated