Explicit Path Control in Commodity Data Centers: Design and Applications

1. What is XPath?

XPath is a simple and practical design for explicit path control in commodity data centers. XPath explicitly identifies an end-to-end path with a path (or tunnel) ID and leverages a two-step compression algorithm to pre-install all the desired paths into IP tables of commodity switches.

2. Why Explicit Routing in Data Center Networks?

Data center networks (DCNs) are often designed with multiple paths between any two nodes. Equal Cost Multi-Path routing (ECMP) is the state-of-the-art for multi-path routing and load-balancing in DCNs. In ECMP, a switch locally decides the next hop from multiple equal cost paths by calculating a hash value, typically from the source and destination IP addresses and transport port numbers. Applications therefore cannot explicitly control the routing path in DCNs. However, many emerging DCN applications such as provisioned IOPS, fine-grained flow scheduling, bandwidth guarantee, etc., all require explicit routing path control over the underlying topologies.

3. XPath Overview

Figure 1. XPath overview

As shown in fiugre 1, to leverage XPath for explicit path control, we can employ a logically centralized controller, called XPath manager, to control the network. The XPath manager has three main modules: routing table computation, path ID resolution, and failure handling. Servers have client modules for path ID resolution and failure handling. Note that XPath manager doesn't have to be implemented in a centralized way.

4. Compression Algorithm

One cannot enumerate all possible paths in a DCN as the number can be extremely large. However, we observe that DCNs do not intend to us all possible paths but a set of desired paths that are sufficient to exploit the topology redundancy. Even though, the challenge is that the sheer number of desired paths in large DCNs is still large, e.g., a Fattree (k = 64) has over 232 paths among ToRs (Top-of-Rack switches), exceeding the size of IP table with 144K entries, by many magnitudes. To tackle the above challenge, we introduce a two-step compression to encode all the desired paths into IP tables with limited routing entries.

Remark: The algorithm mentioned above is designed for arbitrary DCN topologies. However, specially for tree-based DCN topologies, we find that path compression can be done much more efficiently. We are currently working on another algorithm which aims to leverage the characteristics of tree-based topologies to better compress the desired paths.

5. Implementation

Figure 2. The software stacks of XPath on servers

We have implemented XPath on both Windows and Linux platforms, and deployed it on a 54-server Fattree testbed with commodity switches for experiments. In what follows, we describes the implementation on Linux. The implementation on Windows is similar.

6. XPath Applications

We use two utility cases to show that applications can benefit from the explicit path control of XPath. More cases can be found in our paper.

Figure 3. XPath utility case #1: we leverage XPath to make necessary bandwidth easier to implement for provisioned IOPS.

Figure 4. XPath utility case #2: we leverage XPath to assist zUpdate to accomplish DCN update with zero loss.

7. Publications

8. Source code

9. People