FastReChain: Highly Responsive and Low-Overhead Centralized Route Scheduling in Clos Datacenter Networks
Zihan Zhu, Dongchao Wu, Zhanbang Zhang, Jian Yang · 2025
Read FastReChain: Highly Responsive and Low-Overhead Centralized Route Scheduling in Clos Datacenter Networks by Zihan Zhu, Dongchao Wu, Zhanbang Zhang, Jian Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12265.txt.
Introduction
Zihan Zhu and colleagues speed up rewiring plans for data centers built on optical circuit switches. These switches steer light paths directly between machines, saving power and upgrade costs. The catch is computing the port map: which links to set, while disturbing running jobs as little as possible.
Exact solvers crawl on large clusters, and greedy shortcuts tear up too many live links. The team's FastReChain algorithm models the problem from both directions at once, a bidirectional view that trims the search. Simulations on real traffic traces showed it beating the standard routes. The authors present it as the scheduling core for optical clusters that must stay responsive.
Catalog record
| CREATOR | Zihan Zhu, Dongchao Wu, Zhanbang Zhang, Jian Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-12265
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
FastReChain: Highly Responsive and Low-Overhead Centralized Route Scheduling in Clos Datacenter Networks Zihan Zhu, Dongchao Wu, Zhanbang Zhang, Jian Yang Abstract Ever since Clos topologies were used in datacenter networks (DCNs), a practical centralized scheduling algorithm that supports dynamic scheduling has been absent. The introduction of optical switches in DCNs as a future-proof solution exacerbates this problem due to several properties of optical switches, such as the fact that they are generally bufferless and therefore rely on centralized scheduling, and that they have long switching times and therefore require the number of rearrangements to be minimized. In this paper, we propose a centralized scheduling algorithm that achieves theoretical maximum throughput even in one-rate bidirectional Clos networks, while producing schemes with near-minimal numbers of rearrangements. It is the only algorithm that directly supports bidirectional Clos networks and has a time efficiency high enough to support dynamic scheduling to date. For static minimal rewiring, its running time ranges from a fraction to a few hundredths of other algorithms, and the number of rearrangements has also been steadily improved, allowing for more frequent adjustments and less impact on ongoing communications. In addition, the algorithm is very flexible and can support various functional requirements in real-world environments. We achieve this result through the replacement chain concept and bitset optimization. 1 Introduction Clos topologies have been the de-facto standard architecture in datacenter networks (DCNs) to achieve high-speed and large-capacity switching, at Cisco [ 7 ] , Facebook [ 10 ] , Microsoft [ 13 ] , Google [ 25 ] , etc. Different variants of Clos DCN structures have been proposed, such as Fat Tree [ 1 ] , VL2 [ 13 ] , etc. However, a perfect solution to the scheduling and rewiring tasks of Clos datacenter networks has long been absent. According to different division principles, Clos network scheduling algorithms can be divided into centralized and distributed algorithms, and can also be divided into dynamic algorithms and static algorithms [ 4 ] . Distributed scheduling algorithms independently select the route of traffic data in each switch, which requires buffers in the switches. Centralized scheduling algorithms plan the routing scheme in all switches from a global perspective. Static scheduling algorithms generate the corresponding routing scheme based on traffic data within a period of time, while dynamic scheduling algorithms dynamically adjust the routing scheme based on real-time traffic data. Compared to centralized scheduling algorithms, distributed scheduling algorithms do not have centralized control over the network, and therefore cannot fully utilize the network’s link bandwidth resources. Moreover, distributed scheduling algorithms require multiple iterations to converge. On the other hand, centralized scheduling algorithms have the potential to fully utilize link bandwidth resources, and rescheduling can be completed instantly as long as the routing scheme is calculated fast enough. However, centralized scheduling algorithms involve the rearrangement of existing connections, which is rather complex. The time complexity of existing centralized scheduling algorithms (such as algorithms based on matrix decomposition [ 20 , 17 ] , bipartite graph matching [ 4 ] , bipartite graph edge coloring [ 26 , 16 ] , and Hall’s theorem [ 4 ] ), even for scheduling a single connection, is related to the number of network ports and, therefore, cannot support the needs for dynamic scheduling in actual situations. The introduction of optical switches in DCNs as a future-proof solution, which was discussed by Hitesh Ballani et al. [ 3 ] and Yisong Zhao et al. [ 30 ] also calls for a practical centralized scheduling algorithm. Electrical switches are expected to encounter bottlenecks after a few generations due to the inability to continue to increase pin density on the Ball Grid Array (BGA) packages [ 9 ] . Optical switches have several advantages: They are not limited by BGA packaging, thus bypassing the bottleneck of electrical switches; do not require optical-electrical-optical conversion, thus reducing the cost of expensive transceivers; are transparent to modulation formats, thus supporting higher throughput; have no buffering or packet inspection overhead, thus having lower latency [ 3 ] . Many studies on the use of optical switches in datacenter networks have been proposed, such as LumosCore [ 15 ] , TROD [ 5 ] , OSA [ 6 ] , Helios [ 11 ] , and the work of Valerija Kamchevska et al. [ 19 ] . However, optical switches are typically bufferless and therefore rely on centralized scheduling. They also have long switching times and are, therefore, sensitive to the number of rearrangements. This places demands on the number of rearrangements in the routing schemes produced by the centralized scheduling algorithm. Therefore, we aim at the centralized scheduling problem with the goal of minimizing the number of rearrangements. In contrast, previous works did not consider the number of rearrangements, but focused only on obtaining a feasible routing scheme. Nevertheless, our algorithm still outperforms these works in terms of dynamic scheduling, since the time complexities of these works are strictly related to the size of the network. Some network architectures also use optical switches for live expansion. For example, Google’s Jupiter once introduced an optical switched datacenter network interconnection (DCNI) layer between spine blocks and aggregation blocks to enable fast, reliable, and efficient rewiring of links among the blocks [ 25 ] . Live expansion requires minimal rewiring, which is similar to our problem in terms of the essential problem model and the goal of minimizing the number of rearrangements (or rewiring). For convenience, we refer to the problem as the minimal rewiring problem and the corresponding algorithms as minimal rewiring algorithms, but note that they are for both purposes. Existing minimal rewiring algorithms, as mentioned above, cannot support dynamic scheduling, which is more in line with real-world situations. Even for static scheduling, they are either too coarse-grained, resulting in unnecessarily low algorithm efficiency, such as the integer linear programming (ILP)-based algorithms proposed by Google [ 29 , 27 ] , or do not sufficiently minimize the number of rearrangements, such as the algorithm of Shuyuan Zhang et al. [ 28 ] . Moreover, none of these algorithms can be directly applied to bidirectional Clos networks without conversion to symmetric Clos networks, whereas the bidirectional Clos network is more suitable for optical switches. In this paper, we propose a centralized scheduling algorithm for Clos networks that has the following advantages: • Achieves a time complexity in practice far less than linear with the number of network ports and real-time performance in actual network scale through the replacement chain concept and bitset optimization; • Maximizes network connectivity (i.e. achieves theoretical maximum throughput) in proportional (see Definition 5 ) one-rate Clos networks (proven in Section 4.3 ), and should have a high probability of achieving maximum connectivity in non-uniform one-rate Clos networks; • Adaptively trades off algorithm running time and number of rearrangements to ensure stable performance, especially in terms of dynamic routing (explained in Section 5.3 ); • For the static minimal rewiring problem, achieves a smaller number of rewiring and a shorter running time than all existing algorithms (shown in Section 6.4 ), allowing more frequent expansions and less impact on ongoing communications; • The algorithm itself is very flexible, working on a first-come, first-served basis, and various