{'fraction_non_alphanumeric': 0.03805505013356045, 'fraction_numerical': 0.012233363013433472, 'mean_word_length': 4.7264464641986255, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Kevin: de Bruijn-based topology with demand-aware links and greedy routing

We propose Kevin, a novel demand-aware reconfigurable rack-to-rack datacenter network realized with a simple and efficient control plane. In particular, Kevin makes effective use of the network capacity by supporting integrated and multi-hop routing as well as work-conserving scheduling. To this end, Kevin relies on local greedy routing with small forwarding tables which require local updates only during topological reconfigurations, making this approach ideal for dynamic networks. Specifically, Kevin is based on a de Bruijn topology (using a small number of optical circuit switches) in which static links are enhanced with opportunistic links.


INTRODUCTION
The performance of many cloud applications, e.g., related to distributed machine learning, batch processing, or streaming, critically depends on the bandwidth capacity of the underlying network. High network throughput requirements are also introduced by today's trend of resource disaggregation in datacenters, where fast access to remote resources (e.g., GPUs or memory) is critical for the overall system performance [1,2]. Accordingly, over the last years, great efforts have been made to improve the throughput of datacenter networks [3][4][5][6].
Reconfigurable datacenter networks come in two flavors: oblivious and demand-aware [28,29]. Oblivious RDCNs such as RotorNet [10], Opera [11], and Sirius [30], rely on quickly and periodically changing interconnects between racks, to emulate a complete graph. Such emulation was shown to provide high throughput and is particularly well-suited for all-to-all traffic patterns [26]. In contrast, demand-aware RD-CNs allow to optimize the topological shortcuts, depending on the traffic pattern. Demand-aware networks such as Pro-jecToR [17], Gemini [25], or Cerberus [26], among many others [8,9,13,16,17,23,24,31,32], are attractive since datacenter traffic typically features much temporal and spatial structure: traffic is bursty and skewed, and a large fraction of communicated bytes belong to a small number of elephant flows [16,17,[33][34][35][36]. By adjusting the datacenter topology to support such flows, e.g., by providing direct connectivity between intensively communicating source and destination racks, network throughput can be increased further (even if done infrequently [25]).
However, the operation of reconfigurable datacenter networks comes with overheads and limitations. In general, existing RDCNs typically rely on a hybrid topology which combines static (electrical) and dynamic (optical) parts. While such a combination is often very powerful [17], current architectures support only fairly restricted routing. First, communication on the (dynamic) optical topology is often limited to a one or two hops, constraining the possible path diversity, and hence capacity, of the optical network [17,25,26,30,37]. Furthermore, routing is usually segregated: flows are either only forwarded along the static or the dynamic network, but not a combination of both [17,26,38]. The restriction to segregated routing also entails overheads as it requires significant buffering while the reconfigurable links are not available. As static links are always available for packet forwarding in hybrid datacenter networks, this segregation is also not work conserving. Demand-aware RDCNs may introduce additional delays as they require potentially timeconsuming optimizations.
Johannes Zerwas et al.
Xpander [40] Sirius [30] ProjecToR [17] Gemini [25] Cerberus [26]  This paper is motivated by the desire to overcome these limitations, and to better exploit the available link resources, by supporting a general multi-hop and integrated (i.e., nonsegregated) routing. Specifically, we envision a datacenter network in which packets can be forwarded in a workconserving manner, along any available link, be it static or dynamic, and in which a routing path can combine both link types. Such an integrated and work-conserving routing also has the potential to avoid long buffering times and hence delays: if a reconfigurable link is currently unavailable, packets can directly be forwarded to the other available (static) links. However, going beyond segregated and 1-or 2-hop routing, requires a novel network control plane: traditional routing protocols based on shortest paths are not designed for highly dynamic topologies and the frequent recomputation of routes can become infeasible [39]. Furthermore, to keep update cost low and provide a high scalability, it is desirable to have small forwarding tables.
To this end, we propose a simpler and more efficient control plane for RDCNs which avoids flow forwarding delays by supporting local and greedy integrated routing: the forwarding rules depend on local information only, i.e., the set of direct neighbors as well as information in the packet header (in particular, the destination); they are hence not affected by topological changes in other parts in the network and do not have to be updated under reconfigurations. This can significantly reduce control plane overheads during topological adjustments, maintaining a simple routing and control, and is hence well-suited for highly dynamic networks. As we will show, the greedy routing approach is also compact and only requires small forwarding tables.
In particular, we present Kevin, a novel demand-aware reconfigurable datacenter network which leverages such a local control plane using a de Bruijn topology (built from a small number of optical switches), in which static links are enhanced with opportunistic links. Kevin uses logical addressing, and is based on a receiver-based approach for the efficient detection of elephant flows as well as the local and collision-free scheduling of demand-aware links. The control plane of Kevin can be realized both using centralized or distributed algorithms. In both cases, it reduces buffer requirements and delays, supports very small forwarding tables based on standard longest common prefix matching, and enables fast and local route updates as well as short path lengths. Kevin is well-suited to be realized using the Sirius [30] architecture. In summary, we make the following contribution: • We present Kevin, a novel and pratical reconfigurable datacenter architecture which supports efficient multi-hop, integrated and work-conserving routing, to push the performance limits in datacenter networks. The simplicity of Kevin relies on the observation that adding shortcuts to a static de Bruijn topology allows to continue supporting greedy local routing.

PUTTING KEVIN INTO PERSPECTIVE
To put Kevin into perspective with the most recent proposals for datacenter network designs, we use Table 1. We first consider Xpander [40], a state-of-the-art static and demandoblivious topology, which is based on expander graphs. While Xpander has many attractive properties, according to recent results (including the ones in this work), we expect that reconfigurable datacenter networks (i.e., based on dynamic topologies) can provide an improved performance. We next consider Sirius [30], a recent proposal by authors from Microsoft, as an example of a dynamic and demandoblivious topology (similar to [10,11]). Such topologies have been shown to be very effective as well, but still have several potential deficits. First and foremost, they do not feature demand-aware links: while the role and use of demand-aware topology components in future datacenters is generally still subject to ongoing discussions, empirical studies show that demand-awareness can improve throughput under today's typical skewed workload distributions [25,26]. Furthermore, current dynamic and demand-oblivious designs are limited to at most 2-hop routing on dynamic links, and are not work conserving. There also remain some open questions regarding the complexity of the control and routing of these systems.
Then there are also systems which are dynamic and demand-aware. Systems like ProjecToR [17] use a combination of demand-aware optical and electric switches, but do not support integrated mutli-hop routing (ProjecToR uses only 1-hop on demand-aware links), are not work conserving, and the control complexity is not fully determined. Gemini [25], a recent proposal by authors from Google, makes the case for demand-aware links in production level datacenters, but it currently implements only infrequent topology updates (about once a day). Lastly, Cerberus relies on a combination of three topologies: static, dynamic oblivious, and dynamic demand-aware, which together, potentially provide higher throughput. However, it supports only 1-hop routing on the demand-aware links, and its control and routing mechanisms are left abstract and require further investigation.
In contrast to all the above systems, Kevin features all the desired properties listed in Table 1. It supports integrated multi-hop routing as in Xpander, it uses demandaware links as ProjecToR, it is work conserving as Gemini, it enables fast topology updates as in Cerberus, and it is based on simple control and routing.
To put the novelty of our contribution into perspective, we note that the overheads and limitations of shortest path routing has already been studied in several contexts, including dynamic and mobile networks such as ad-hoc networks where greedy approaches such as geo-routing can be an attractive alternative [41]. We are also not the first to observe the benefits of de Bruijn based networks in dynamic settings, and there exist peer-to-peer [42][43][44][45] and parallel architectures [46] which rely on de Bruijn graphs. However, to the best of our knowledge, we are the first to study such an approach in the context of reconfigurable and demand-aware datacenter networks.

THE KEVIN RDCN
The rack-to-rack network provided by Kevin is based on the ToR-Matching-ToR (TMT) model [10,26]: top-of-rack (leaf) switches are interconnected by a set of optical spine switches. Each spine switch provides a × directed matching between its input-output ports. Depending on the switch type, the matching can dynamically change over time. In particular, Kevin is hybrid, in the sense that one part of the topology model is demand-oblivious and static using spine switches (i.e., static matchings), and the other part is dynamic and demand-aware using reconfigurable spine switches (i.e., dynamic matchings), and = + . Figure 1, presents an example of the TMT model with eight ToR switches and three spine switches, from which two are static and one is dynamic. Each ToR-spine link in the figure represents one directed uplink and one directed downlink. It is important to note that abstractly, we use spine switches, each implementing an × matching, but each matching can be split across a set of several smaller switches, like in Sirius [30].
In order to maximize performance, Kevin uses dynamic, demand-aware links to provide shorter paths for elephant flows, while other flows are transmitted via the combined (static + dynamic) topology. A key feature of Kevin is that it supports integrated multi-hop routing across both switch types. This is in contrast to previous works that rely on segregated and single-hop forwarding for demand-aware links [17,26]. Moreover routing in Kevin is efficient, by relying on logical addressing and a local control plane, implementing greedy routing. Thus, links can always be used immediately, with a work-conserving scheduler. To detect elephant flows, Kevin leverages a simple sketch, sampling the flow sizes and then adjusting flow paths accordingly. In the following, we present the different components of Kevin in detail.

The Hybrid Topology
Kevin combines two topologies, a static, demand-oblivious topology (the "backbone"), and a dynamic, opportunistic, demand-aware topology into a unified one. Both topologies are built from matching switches according to the TMT model, forming a augmented de Bruijn network [47].
• Static and demand-oblivious de Bruijn topology (backbone): The static topology of Kevin relies on a de Bruijn graph. It is formed by static optical circuit switches or patch panels. • Demand-aware topology: The static topology is enhanced by reconfigurable matchings, also implemented with optical circuit switches. The demand-aware (DA) links add shortcuts on top of the static de Bruijn topology.
We first discuss the static de Bruijn topology, and how it can be built from a constant number of matchings (already two matchings suffice).
3.1.1 The Static de Bruijn Topology. We start with formally defining the de Bruijn topology [48].  Note that the directed neighbors of node are determined by a left shift operation on the address of and entering a new symbol ∈ [ − 1] as the right most (least significant) symbol. It is well known that the de Bruijn topology has the following properties: (1) Considering self-loops, ( , ) is a -regular directed graph (2) ( , ) supports greedy routing with paths of length at most The following observation will be relevant for our network design, it is a consequence of Property (1) above and Hall's theorem [49]: ( , ) topology can be constructed from the union of directed perfect matchings. It follows from Observation 1 that we can build a ( , ) topology with static spine switches.
3.1.2 Greedy and LPM Routing in de Bruijn Topology. It is well known that the de Bruijn topology supports greedy routing from a source to a destination based solely on the  address of . That is, to choose the next-hop toward each node on the route needs to know the address of and the address of its neighbors. The next-hop is chosen as the neighbor which minimizes the de Bruijn distance to . The de Bruijn distance between two nodes , denoted as dist DB ( , ) is the minimum number of shift operations needed to transform address to address. The main observation is that each such shift implies a directed edge and the next-hop in the routing. For example, the de Bruijn distance between node = 011 and = 001 is dist DB ( , ) = 3 and route from to in (2, 3) is 011 → 110 → 100 → 001 (see also Figure 2). Note that in each hop the distance to is reducing.
A less-known fact is that routing on the de Bruijn topology can be realized via a simple forwarding table that is based on a longest prefix match (LPM) [50]. To build the forwarding table for a node it only needs to know the address of each neighbor and the outgoing port that connects to it. Algorithm 1 describes the forwarding table building (for simplicity only for the (2, 3) case) and Figure 3 shows the forwarding table of node 011 and how it is built from its neighbors 110 and 111. Note that rule 1 * * , is removed from the table in the reduce process since it will never be used.
Following Algorithm 1, we can state the following about the size of the forwarding table of each node:  We can now discuss the DA links and how they are merged into the hybrid topology.

The
Demand-aware Topology. The simplicity of Kevin relies on the observation that adding shortcuts to the static de Bruijn topology is easy and allows to continue supporting greedy and LPM routing. Recall that in our model we have switches or matchings for DA links. For now consider these links as arbitrary links. Later we discuss how to choose these links based on flow sizes. Let = ( , ) be a de Bruijn topology over the set of nodes. Let be a directed matching on × . Let = ∪ be the union of the directed graphs and with the same set of nodes . We can claim the following about . Claim 1. If we perform Algorithm 1 on each node in , then supports integrated, multi-hop, greedy, LPM routing with forwarding table size of ( + 1) .
Proof sketch. First we show that supports greedy routing, namely the next-hop is the neighbor with the shortest de Bruijn distance to the destination. While greedy routing on the static topology reduces the distance function in each hop by exactly one, DA links can reduce it by more than one hop. From the greedy routing it is clear that LPM forwarding will work and that the path is integrated in a multi-hop manner. □ Figure 4 demonstrates the (2, 3) topology with the addition of a single demand-aware matching (showing only one DA link from 011 to 100). The figure also presents the new forwarding table at node 011, which is constructed using Algorithm 1. If we consider as before the route from = 011 to = 001 it will now be shorter 011 → 100 → 001. In fact, all addresses with LPM 00 * will use the new DA port for forwarding on node 011. Note also that routes toward addresses with LPM 0 * * , like 010, have now two equal length routes (of length three), for example, 011 → 100 → 001 → 010 or 011 → 110 → 101 → 010.
Following Claim 1, we can extend this example to more than one matching and support demand-aware matchings. Formally, for integers , , ≥ 2 and = ( ) , we denote by ( , , ) the Kevin topology with = + spine switches, backbone network ( , log ), and demandaware switches. We can state the following about the hybrid topology of Kevin.

Scheduling of Demand-Aware Links
Kevin relies on a control plane which can use centralized or decentralized scheduling of the DA links. The centralized scheduling benefits from the global view, while the decentralized scheduling supports fast reaction. We use Sirius' [30] reconfiguration model also for DA links: spine switches use passive gratings while (sending) ToR switches rely on tunable lasers which determine the link to set up in the corresponding switch (matching). This property is useful for the distributed version of the scheduling where the receivers provide permissions to senders to reconfigure links. All algorithms use the command 'Set DA-link ( , , )' which means that sender ToR tunes its laser on port to establish a direct link to ToR via switch . Recall that each ToR has up-link toward the spine switches so we identify port with switch .  Return NULL based on an estimate of the demand or measurement of the traffic in the network. We denote this estimation by a demand matrix . Both algorithms sort the demands in by decreasing order and for each ( , ) demand in , they try to add a DA link to the network. In case the algorithm decides to set a DA link, we assume that the reconfiguration time is and during this time the link is not available for use. Additionally when a DA link is set, it stays connected for a reservation time of before it can be replaced, if needed. The first algorithm Breadth-First-Search (BFS)-DA-links, shown in Algorithm 2, takes a global perspective. For each demand ( , ) ∈ in decreasing order, it searches for the shortest possible path that could be created between and by adding a shortcut to the de Bruijn backbone. From the source , the search follows the path on the static topology part toward until a node with at least one available DAport has been found (line 12), denote it as . The available DA ports of are denoted as ℎ (line 4). In turn, a destination-based breadth first search is preformed until a node with available DA port in ℎ is found (line 5). We denote the available port in as . If the new path (with the shortcut) is equal or shorter than the greedy path on the current Kevin topology using static + DA links (line 6), the algorithm creates a shortcut via a DA link between and on the 'th spine switch (line 7). Note that initially = and = , but at a later stages of the algorithm it will create integrated multi-hop paths in Kevin.
The second centralized algorithm, Greedy-DA-links, shown in Algorithm 3, is a simple version of greedy -matchings (known also as -matching for undirected graphs [51]). The algorithm iterates over the requests ( , ) ∈ in decreasing order and only connects a direct link between and if they have available ports on the same DA switch . The greedy matching is a simplified version of the BFS-DA-links algorithm, nevertheless, its shortcuts also support integrated multi-hop as before, and a similar version of it is easier to implemented in a distributed way, as we explain next.
3.2.2 Distributed scheduling of DA-links. The distributed scheduling algorithm, DistDA, shown in Algorithm 4, combines similar approaches as presented in ProjecToR [17] and Sirius [30]. It implements a distributed, threshold-based greedy matchings algorithm. The algorithm is triggered by destination-based elephant detection of flows from a source. For instance, this can be done in P4 using sketches [52] as we discuss in more details later. If any of the destinations detects a source(-ToR) as elephant it checks if it has available DAports. If available, it sends an offer, PortRequest( ), to the elephant source ToR via the static topology part where is a list of available ports. Upon reception, the source/sender checks for an available DA-port on its side. If a port is available, it acknowledges the request via a PortApprove( ) message and set the link on port . If no DA-port is available at the source, the request is declined. The receiver ToR continues to generate PortRequests for other elephants. An agreed DA-link, i.e., the ports at sending and receiving ToR, is reserved for fixed period of time . Afterwards, the ports can be assigned to new requests and the circuit might be reconfigured. However, the circuit is not pro-actively torn down but kept alive until an appropriate request arrives. We note that while our distributed scheduler is simple, it is effective as we will see next. We leave the study of more sophisticated schedulers (e.g., based on distributed stable matchings [17] or online algorithms [53]) for future work.

Implementation and Practical Aspects
3.3.1 Implementation and Cost. As mentioned earlier, we envision that Kevin could be implemented using the Sirius architecture [30]. Sirius is also captured by the TMT model, but one of its great advantages is that instead of spine switches, Sirius uses a single layer of gratings. The Arrayed Wavelength Grating Routers (AWGR) are simple and passive without moving parts and do not consume power. Still, each grating diffracts ("forwards") incoming light from input to output ports, based on the wavelength, abstractly creating a matching. Reconfiguration is then performed by a physical-layer ToR switch (or directly on servers) equipped with transceivers containing tunable lasers that can change the wavelength used to carry the data toward the gratings through an optical fiber.
Sirius has been presented as a demand-oblivious architecture which provides fast end-to-end reconfiguration, due to a pre-determined, static schedule that specifies the connectivity at any given fixed-size timeslot. However, Sirius' architecture is in principle also well-suited for demand-aware scheduling, with a slower end-to-end reconfiguration delay.
As Kevin differs from Sirius only in the scheduling and routing, the cost and power consumption of Kevin will be similar to Sirius. In [30], the authors showed that Sirius' power and cost are about 25% that of an electrically switched Clos network (ESN). That said, unfortunately, a direct comparison of the performance of Kevin and Sirius is currently not possible as Sirius' simulation code is not available, we therefore concentrate on the comparison to static expander topologies which are also state-of-the-art datacenter networks [40].
Recently, Cerberus [26] which can potentially also be built on the Sirius architecture, demonstrated that using 1-hop DA links (and keeping some demand-oblivious dynamic links as in Sirius or RotorNet [10]) can increase the network throughput. We, therefore, believe that besides the conceptual contribution of Kevin, in terms of performance it could enhance any demand-oblivious existing design.
3.3.2 IP Addressing and LPM Forwarding. We embed the de Bruijn address into the hosts' IP addresses. Our approach uses IPv4 but can also be implemented using IPv6. Depending on the number of ports per ToR, a single symbol of the de Bruijn address takes one or multiple bits of the IP address: Thus, the full de Bruijn address occupies · bits of the IP address. In order to use LPM to implement the forwarding, we split the IP address into three parts. The first bits mark the base network that is assigned to Kevin. The following ′ = · bits identify the ToR by means of the de Bruijn address while the remaining bits identify the host/VM inside the rack, i.e., each ToR is assigned a /( + ′ ) prefix. For the example of Figure 4(a), the de Bruijn address can directly be mapped to an IP address/prefix and occupies only 3 address bits. Using 10.0.0.0/8 as a base IP prefix, an exemplary forwarding table for ToR 5 = 011 is shown in Figure 4(c). Following Algorithm 1 each node can build its IP forwarding table locally based on its ToR neighbors' addresses. In particular, when a new DA links is established for a node's port and it knows the ToR address of the new neighbor, the forwarding table can be updated locally (without recomputing shortest paths).

CONCLUSION
To address the limitations and overheads of existing reconfigurable datacenter networks, we proposed Kevin, a simple and flexible architecture which supports integrated multihop routing and demand-aware links. Kevin is work conserving and enables fast topology updates and simple control. We argued that a realization of Kevin using a Sirius topology reconfiguration model may be particularly interesting.
We understand our work as a next step towards more practical and scalable demand-aware reconfigurable datacenter networks, and believe that our work opens several interesting avenues for future research. In particular, while we demonstrated the benefits of greedy and local routing on a de Bruijn topology, we believe that our approach is more general and applicable to other network topologies that support greedy local routing.