Opportunistic Optical Link Scheduling in the Scalable Matching Model

1

Opportunistic Optical Link Scheduling in the Scalable Matching Model

arXiv:2610.38004v1 [cs.NI] 27 Oct 2026

Marcos T. Henriques and Olga Goussevskaia

Abstract—The Scalable Matching Model (SMM) is a useful abstraction for reconfigurable datacenter networks. In SMM, a set of n (Top-of-Rack) electrical packet switches is connected via a set of optical circuit switches (OCS), each realizing a p × p matching, where p is the number of ports per switch. In the case when p ≪ n, bounded-degree networks utilize only a small portion of the OCS infrastructure at each point in time, especially when traffic patterns are skewed and bursty. In this work, we propose the Opportunistic Optical Link Scheduling (OOLS), a set of lightweight OCS link scheduling routines, designed to augment bounded-degree reconfigurable network topologies by leveraging idle OCS resources. We evaluate the performance of OOLS in the SMM through simulations, using synthetic and real-world data-center workloads. Our simulation results show that OOLS substantially improves performance, lowering communication costs and boosting throughput. Index Terms—Reconfigurable Data Center Networks, SelfAdjusting Networks, Optical Circuit Switching, Heuristics

I. I NTRODUCTION The growing reliance on data-centric applications across various domains, coupled with advances in AI and machine learning, has significantly increased communication traffic in data center networks [1], [2]. Traditionally, data center network designs have relied on static topologies, like Clos [3], [4], hypercube [5], [6], or expander [7], [8]. Such architectures are essentially demand-oblivious and perform well for uniform allto-all traffic patterns. Traffic in data centers, however, is known to be bursty and skewed [1], [9]. Recent progress in optical circuit switching (OCS) has enabled demand-aware reconfigurable data center networks (RDNs) to emerge [10]–[15]. Several technologies support this new paradigm, including nanosecond-scale tunable lasers [16], digital micromirror devices [17], liquid-crystal-on-silicon wavelength-selective switches [18], and microcombs and semiconductor optical amplifiers [19]. One common abstraction for RDNs is the ToR-MatchingToR (TMT) model [20]–[24], in which n (Top-of-Rack) electrical packet switches are linked via a set of optical circuit switches, each realizing a p × p matching, where p is the number of OCS ports per switch. Interesting optimization problems arise in this context, e.g., regarding which is the best combination between electrical packet switches and OCSs [25], [26]. There is still, however, no consensus in the community on which RDN design is optimal [10]. TMT can be used as a testbed for Self-Adjusting Networks (SAN) [10], [27]–[33]. SANs optimize their physical topology M.T. Henriques and O. Goussevskaia are with the Computer Science Department, Universidade Federal de Minas Gerais (UFMG), 31270-901 Belo Horizonte, Brazil. E-mails: marcoshenriques@dcc.ufmg.br, olga@dcc.ufmg.br

toward the demand they serve in an online manner, i.e., without prior knowledge of the traffic, with the requirement that the network remain connected and have bounded degree [34]. Previous studies have shown that, in the case when p ≪ n, SANs typically utilize only a small portion of the OCS infrastructure at each point in time, especially when spatial and temporal locality of the workload is high, i.e. traffic is skewed and bursty [35], [36]. This unexplored idle capacity motivates us to develop opportunistic scheduling strategies for these network architectures. Our work is based on the Scalable Matching Model (SMM) [35], [36], a generalization of the TMT model [22]. SMM introduces the constraint that the number of ports of each OCS is bounded by a constant, i.e., p = O(1). SMM guarantees strict non-blocking (i.e., any point-to-point connection can always be established), uses a minimum number of OCSs to realize any dynamic bounded-degree topology, and allows to execute existing SAN algorithms on top of it, while preserving the performance (amortized communication cost) guarantees of the latter. We present the Opportunistic Optical Link Scheduling (OOLS), a set of lightweight OCS link scheduling routines, designed to integrate with TMT RDN architectures. OOLS leverages idle OCS ports to dynamically augment a SAN topology with opportunistic routing shortcuts. We implemented OOLS in combination with multiple SAN algorithms using OpticNet [36], a framework for simulating RDNs in the TMT model. We performed extensive simulations using both synthetic and real data center workloads, with variable temporal and spatial locality. The simulation results show that OOLS significantly increases the concurrency of the RDN system and optimizes not only the system’s throughput and makespan, but also the total communication cost. Our experiments also revealed a trade-off between efficiency improvement and resource utilization, as a function of p (the number of OCS ports per switch). In particular, the smaller the OCS, the higher the potential gains of opportunistic link scheduling. Overall, OOLS proved to be an effective and efficient mechanism to utilize idle OCS capacity in RDNs, especially in network architectures that utilize OCSs of limited size. In Sec. II, we present the model and necessary notation; in Sec. III, the OOLS algorithm; in Sec. IV, the evaluation framework; in Sec. V, the simulation results; in Sec. VI, the related work; finally, in Sec. VII, we present our conclusion. II. M ODEL We consider a network topology that connects a set V of n communication nodes (e.g., top-of-rack switches, ToRs),

2

and a sequence σ of m messages σi (si , di ) ∈ V × V , with source si and destination di ; m can be infinite. The sequence σ is revealed over time in an online manner. SANs: SANs are designed to minimize the communication cost through a sequence of network topologies N0 , N1 , . . ., where each Nt = (V, Et ) belongs to some desired graph family N . For scalability reasons, the networks should have bounded degree (≤ k). Adjustments: To adjust the topology smoothly over time, the network is reconfigured (locally) through adjustments that preserve the desired properties of the graph family N . SANs like SplayNet [29] are based on Binary Search Trees (BST) and extend the classical zig, zig-zig and zig-zag rotations, first introduced for splay trees [37]. Each splay operation updates a constant number of links, at a constant cost, and roughly halves the depth of every node along the communication path. This halving effect makes splaying efficient in an amortized cost analysis. TMT: The TMT [21], [22] is a model for reconfigurable data center networks (RDN), based on a two-layer architecture, in which a set of (leaf-layer) ToRs is connected using a set of (spine-layer) reconfigurable Optical Circuit Switches (OCS). Each OCS dynamically connects its input-output port-pairs via a matching1 , which changes over time. SMM: The Scalable Matching Model [35], [36] is a generalization of the TMT model [21], [22]. Let N be the family of bounded degree (≤ k) graphs on a set V of n nodes (static leaf-layer ToR switches) and Nt ∈ N be a network topology at time t. Let SW = {sw1 , . . . , swn′ } be a set of OCSs, of size n′ = f (n, p, k), where each switch swi ∈ SW internally connects its p = O(1) input-output port pairs via a matching M (i, t) of size ≤ p. At each time t, the network Nt is equal ′ to the union of all these matchings: Nt = Mt = ∪ni=1 M (i, t). TMT port configuration: Before the RDN starts operating, the TMT architecture must be configured, such that for each (undirected) edge in the network topology Nt , there must be a static (duplex) link connecting an output port of u to an input port of some OCS swx ∈ SW , i.e., ∃swx ∈ SW |(u, v) ∈ M (x, t), ∀(u, v) ∈ Nt . Time model: Time is divided into synchronous rounds, and each round consists of a constant number of time slots. In a round, multiple (independent) nodes can make adjustments concurrently. We assume that nodes and communication between them are reliable. Makespan: Consider a sequence σ of m messages, a SAN algorithm A, any initial network N0 ∈ N , and a message σi (si , di ) ∈ σ, generated at time bi and delivered at time ei . In terms of time, the objective of a SAN is to minimize the makespan, defined as: max ei − bi . 1≤i≤m

Work: The communication cost can be partitioned into reconfiguration and routing costs. The reconfiguration cost is proportional to the number of (link) adjustments performed by a SAN algorithm A to deliver a message σi ∈ σ. If α is the cost of a single edge adjustment, then the reconfiguration cost for the entire network is defined as linkAdj(Nt−1 , Nt ) = 1 A matching is defined as a set of at most p non-adjacent input–output port

pairs.

P α · swx ∈SW |M (x, t) \ M (x, t − 1)|. The service, or routing cost of a message σi ∈ σ is proportional to the length of the (shortest) path distNei (si , di ), Nei ∈ N . We assume that routing a message incurs a cost of 1 unit per hop ((u, v) ∈ Nt ). Consider any initial network N0 , a sequence of m messages σi (si , di ) ∈ σ and algorithm A. Let tmax = max ei . 1≤i≤m

We define the total communication cost as: C(A, N0 , σ)

D(A, N0 , σ) + R(A, N0 , σ), where(1) m X = (distNei (si , di ) + 1), (2) =

D(A, N0 , σ) R(A, N0 , σ)

=

i=1 tX max

α·

linkAdj(Nt−1 , Nt ).

(3)

t=1

OpticNet RDN: OpticNet [35], [36] is a framework for modeling TMT architectures and simulating SAN algorithms in RDN environments. OpticNet partitions the set of nodes V into C = ⌈n/p⌉ clusters Ci ⊆ V, |Ci | = p, and the set of optical switches SW into two subsets, unit switches (SW ∪ ) and cross switches (SW × ), such that: SW = SW ∪ ∪ SW × , 2 where |SW | = k2 · ⌈n/p⌉ if k is the maximum vertex degree 2 of Nt ∈ N . If Nt is a BST, then |SW | = (⌈n/p⌉2 + ⌈n/p⌉).

(4)

OpticNet port mapping: Nodes are assigned to clusters as follows: ∀(u, v) ∈ V × V , if u < v then u ∈ Ci , v ∈ Cj , where: i = min (⌊u/p⌋ , ⌊v/p⌋), j = max (⌊u/p⌋ , ⌊v/p⌋). Each cluster Ci is assigned to a group of k switches in SW ∪ , and each distinct pair of clusters (Ci , Cj ), i ̸= j is assigned to a group of 2k switches of type SW × . The in↔out portpairs are defined according to the type (unit or cross) of each ∪ OCS switch swx ∈ SW , as swi·⌈k/2⌉+x : Ci × Ci , ∀ 0 ≤ × i < C, 0 ≤ x < ⌈k/2⌉, swidx(i,j)+x : Ci × Cj , ∀ 0 ≤ i < j < C, 0 ≤ x < k, where the cluster-index is defined as idx(i, j) = k2 · i · (2 · C − 1 − i) + k · (j − i − 1). For the special case of a BST topology, the definitions above become: ∪ sw2i+x × swidx(i,j)+x

idx(i, j)

:

Ci × Ci , ∀ 0 ≤ i < C, 0 ≤ x < 2,

Ci × Cj , ∀ 0 ≤ i < j < C, 0 ≤ x < 2,   n − i − 1) + 2 · (j − i − 1).(5) = i · (2 · p :

Figure 3a illustrates a port mapping example for a BST network with n = 8, p = 4, C = 2, and |SW | = 8. III. O PPORTUNISTIC O PTICAL L INK S CHEDULING Opportunistic Optical Link Scheduling (OOLS) is a set of routines designed to integrate with a TMT network architecture [21] and leverage idle optical switch ports to create shortcut routing paths opportunistically. In particular, we implemented OOLS within the OpticNet framework [?]. Augmented network topology: OOLS adds opportunistic links to the SAN topology as long as there are available 2 W.l.o.g., we assume that OCS switches are full-duplex, i.e., provide bidirectional communication. Note that this assumption can be removed by replacing each full-duplex switch with two simplex switches.

3

Controller

ToR Node 1.Node:informDemand()

2.1.OOLS:findOpportunisticPaths(σ) false

repeat

true

2.2.SAN:getRotationsToPerform(σ)

3. Node:routingStep() 2.3.OpticNet:updateNetworkTopology()

Fig. 1: OOLS and OpticNet integration.

OCS ports for that. Given a network Nt ∈ N of maximum vertex degree k, the maximum vertex degree of the augmented network becomes kC. For the special case of a BST, this number is 2C +2, where C = ⌈n/p⌉ is the number of clusters. We refer to the augmented network as NU t . Extended notation: Consider a round t ≥ 1. OOLS creates an additional matching MHL (x, t) (⊈ E(Nt )) for each ′ switch swx ∈ SW . Note that NU t = ∪nx=1 MU (x, t), where MU (x, t) = M (x, t) ∪ MHL (x, t). We refer to the set of opportunistic link matchings at a time t as MHLt . The set of all matchings at a time t is denoted by MU t = Mt ∪ MHLt . Finally, we denote by L(s, d) and L(s, w, d) the opportunistic paths of one hop and two hops, connecting nodes s to d, σ(s, d) ∈ σ, w ∈ V ; and we denote by (t − 1), t′ and (t + 1) the previous, current, and subsequent (simulation) rounds, respectively. Integration with OpticNet: Figure 1 illustrates the integrated workflow of OOLS and OpticNet. The simulation proceeds in synchronous rounds, during which the network topology can be adjusted and messages can traverse at most one hop. Each round is further divided into three time-slots. Leaf-layer nodes generate the demand (Step 1: Node:InformDemand) and route messages (σ(s, d) ∈ σ) (Step 3: Node:routingStep). A centralized controller mediates the communications between the leaf (ToR) and spine (OCS) switch layers (Step 2: OpticNet:controllerStep). It maintains an up-to-date global view of the topology (Nt , ∀t ≥ 1), manages the dynamic mapping of links ((u, v) ∈ Et )) to matchings (MU (x, t) ∈ MU t ) and matchings to optical switches (swx ∈ SW ) (Step 2.3: OpticNet:updateNetworkTopology()), and keeps track of link adjustments (MU (x, t) \ MU (x, t − 1), ∀swx ∈ SW ) (Step 2.2: SAN:getRotationsToPerform(σ)). OOLS acts in the beginning of the controller step (Step 2.1: OOLS:findOpportunisticPaths(σ)). OOLS:findOpportunisticPaths (Algorithm 1): In each round t, for each node s ∈ V , carrying a message σ(s, d) ∈ σ, OOLS verifies if there is any path to the destination node d ∈ V , of length one or two, in the augmented network topology NU t . If there is, routing of message σ(s, d)

is allowed, i.e., the message will be sent in Step 3 of the current round. If not, then it attempts to create a one-hop opportunistic link (OOLS-1H). If the attempt is successful, then L(s, d) is created and the message will be sent in Step 3 of the current round. Else, it tries to create (partially, if existing links can be utilized) a two-hop opportunistic path L(s, w, d) (OOLS-2H). If successful, the message will be sent in Step 3 of the current and the following rounds. Else, the message is left to be handled by the SAN algorithm (Step 2). Consider a message σ(s, d) ∈ σ, in which s belongs to cluster Cs and d to cluster Cd . Let i = min(s, d) and j = max(s, d). We denote the set of switches associated with the cluster pair (Cs , Cd ) by Ssd = {swz ∈ SW ∪ | i · 4 ≤ z < (i + 1) · 4}, if i = j, and Ssd = {swz ∈ SW × | idx(i, j) ≤ z < idx(i, j) + 4}, otherwise (idx(i, j) defined as in Eq. (5)). OOLS-1H: First, we look for a one-hop path L(s, d) in NU t′ . If such a path does not exist, then we try to create one: • Case 1 (RouteSD): A one-hop path L(s, d) exists in NU t if ∃swz ∈ Ssd | (s, d) ∈ MU (z, t′ ). • Case 2 (CreateSD): L(s, d) is created if ∃swz ∈ Ssd | ∀x ∈ Cd : (s, x) ∈ / MU (z, t′ ) ∧ ∀x ∈ Cs : (x, d) ∈ / ′ MU (z, t ). Example: Figure 2 illustrates the execution of OOLS-1H for the DiSplayNet SAN with n = 12, p = 4, C = 3, |SW | = 12, in round 46. Observe that Case 1 (RouteSD) evaluates to true when the message being processed is, e.g., σ(10, 12). Case 2 (CreateSD) evaluates to true when the message being processed is σ(4, 9) (or σ(9, 4)). Note that the maximum vertex degree of the augmented network topology is upper bounded by 2C + 2 = 8. Algorithm 1 OOLS:findOpportunisticPaths(σ) if RouteSD then %OOLS-1H, OOLS-2H allow s to forward σ(s, d) to d 3: return true 4: if RouteSWD then %OOLS-2H 5: allow s to forward σ(s, d) to w 6: return true 7: if CreateSD then%OOLS-1H, OOLS-2H 8: add (s, d) to MHLt 9: return true 10: if LR1Hop then %OOLS-1H with LR 11: remove links conflicting with (s, d) from MHLt 12: add (s, d) to MHLt 13: return true 14: if CreateSWOrCreateWD then %OOLS-2H 15: add (s, w) or (w, d) to MHLt 16: return true 17: if CreateSWCreateWD then %OOLS-2H 18: add (s, w) and (w, d) to MHLt 19: return true 20: if LR2Hops then %OOLS-2H with LR 21: remove links conflicting with (s, w) or (w, d) from MHLt 22: add (s, w) and (w, d) to MHLt 23: return true 24: return false 1: 2:

4

OOLS-2H: If OOLS-1H returns false for a given message σ(s, d) ∈ σ, then we look for a two-hop path L(s, w, d) in NU t′ . If such a path does not exist, then we try to reuse an already existing link (s, w) or (w, d) from NU t′ and create the remaining half of the path. If no such opportunity is found, we search for a relay node w ∈ V and try to create both hops from scratch: Case 3 (RouteSWD): A two-hop path L(s, w, d) exists in NU t′ if ∃w ∈ V | (w ̸= s ∧ w ̸= d) ∧ ∃swx ∈ Ssw | (s, w) ∈ MU (x, t′ ) ∧ d ∃swy ∈ Sw | (w, d) ∈ MU (y, t′ ). • Case 4 (CreateSWOrCreateWD): There is a cluster Cw and a relay node w ∈ Cw , such that one hop of the L(s, w, d) path already exists in NU t′ and the other hop can be created. The insertion of the opportunistic link is successful if: ∃w ∈ V | (w ̸= s ∧ w ̸= d) ∧ (∃swx ∈ Ssw | (s, w) ∈ MU (x, t′ ) ∧ d ∃swz ∈ Sw | (∀v ∈ Cd : (w, v) ∈ / MU (z, t′ )) ∧ ′ (∀v ∈ Cw : (v, d) ∈ / MU (z, t )) ∨ •

d ∃swy ∈ Sw | (w, d) ∈ MU (y, t′ ) ∧ w ∃swz ∈ Ss | (∀v ∈ Cw : (s, v) ∈ / MU (z, t′ )) ∧ ′ (∀v ∈ Cs ) : (v, w) ∈ / MU (z, t )). • Case 5 (CreateSWCreateWD): There is a cluster Cw and a relay node w ∈ Cw , such that the L(s, w, d) path can be created. The insertion of the new link is successful if: ∃w ∈ Cw , Cw ∈ topC(Cs ) | (w ̸= s ∧ w ̸= d) ∧ / MU (x, t′ )) ∧ ∃swx ∈ Ssw | (∀v ∈ Cw : (s, v) ∈ ′ (∀v ∈ Cs : (v, w) ∈ / MU (x, t )) ∧ d | (∀v ∈ Cd : (w, v) ∈ / MU (y, t′ )) ∧ ∃swy ∈ Sw ′ (∀v ∈ Cw : (v, d) ∈ / MU (y, t )).

Note that, when combining the Cases 1 through 5, Case 3 (RouteSWD) should be executed before Case 2 (CreateSD), to avoid creating unnecessary one-hop opportunistic links. Example: Figure 3b illustrates the execution of OOLS-2H for the same network shown in Figure 2, right before adding the opportunistic path L(5, 0, 7). Observe that Case 1 (RouteSWD) evaluates to true for the message σ(1, 6) (w = 2). Case 4 (CreateSWOrCreateWD) evaluates to true for σ(7, 1) (w = 0). Case 5 (CreateSWCreateWD) evaluates to true for σ(5, 7) (w = 0). OOLS never overwrites non-opportunistic links ((u, v) ∈ Nt ), and whenever a SAN link adjustment (rotation) occurs, new (BST) links always overwrite any opportunistic links that occupy the same OCS ports. Moreover, old opportunistic links are overwritten by newer opportunistic links using cache replacement policies, such as Least Recently Used (LRU) or Least Frequently Used (LFU). OOLS with LR: When OOLS fails to find free OCS ports to add an opportunistic link (within the limited search space of topC candidate switches), it removes older conflicting opportunistic links using a cache replacement policy. Link Replacement (LR) is activated in two cases, described below: •

Case 6 (LR1Hop): For each swz ∈ Ssd , we consider the set of all opportunistic links (s, x) ∈ MHL (z, t′ )

incident to s (when the d output port is free) or d ((x, d) ∈ MHL (z, t′ ), when the s input port is free). We remove the one with the lowest LR score (LFU or LRU). The insertion of the new link L(s, d) is successful iff: ∃swz ∈ Ssd | (∀x ∈ Cd : (s, x) ∈ / MU (z, t′ ) \ {lsx } ∧ ∀x ∈ Cs : (x, d) ∈ / MU (z, t′ )) ∨ (∀x ∈ Cd : (s, x) ∈ / MU (z, t′ ) ∧ ∀x ∈ Cs : (x, d) ∈ / MU (z, t′ ) \ {lxd }), where: lxd = arg minMHL (z,t′ ),swz ∈Ssd (LR(x, d)), lsx = arg minMHL (z,t′ ),swz ∈Ssd (LR(s, x)). • Case 7 (LR2Hops): Given the set of candidate clusters Cw ∈ topC(Cs ), ∀w ∈ Cw , we search for a switch swy ∈ Ssw , such that either both (input and output) ports (s, w) are free (i.e. ∈ / MU (z, t; )), or become free by removing one opportunistic link (either ls,x or lxw ) from d MHL (z, t′ ); then we repeat the search in Sw for the second hop (w, d). Consider the set of all switch pairs (swy , swz ) that satisfy the condition above. Then, the new link will be inserted into the pair with the lowest combined score (LR(ls )+LR(ld )), where ls (ld ) is either lsx (lwx ) or lxw (lxd ), depending on which (if any) link was removed from swy (swz ), LR(∅) = 0, and: lxd = arg minMHL (z,t′ ),swz ∈Swd (LR(x, d)), lwx = arg minMHL (z,t′ ),swz ∈Swd (LR(w, x)), lsx = arg minMHL (z,t′ ),swz ∈Ssw (LR(s, x)), lxw = arg minMHL (z,t′ ),swz ∈Ssw (LR(x, w)). The insertion of the new link is successful iff: ∃w ∈ Cw , Cw ∈ topC(Cs )|(w ̸= s ∧ w ̸= d) ∧ (∃swy ∈ Ssw : (s, w) ∈ MU (y, t′ ) ∨ (∀x ∈ Cs : (x, w) ∈ / MU (y, t′ ) \ {lxw } ∧ ∀x ∈ Cw : (s, x) ∈ / MU (y, t′ ) ∨ ∀x ∈ Cs : (x, w) ∈ / MU (y, t′ ) ∧ ∀x ∈ Cw : (s, x) ∈ / MU (y, t′ ) \ {lsx } ∨ ∀x ∈ Cs : (x, w) ∈ / MU (y, t′ ) ∧ ∀x ∈ Cw : (s, x) ∈ / MU (y, t′ ))) ∧ d : (w, d) ∈ MU (z, t′ ) ∨ (∃swz ∈ Sw (∀x ∈ Cw : (x, d) ∈ / MU (z, t′ ) \ {lxd } ∧ ∀x ∈ Cd : (w, x) ∈ / MU (z, t′ ) ∨ ∀x ∈ Cw : (x, d) ∈ / MU (z, t′ ) ∧ ∀x ∈ Cd : (w, x) ∈ / MU (z, t′ ) \ {lwx } ∨ ∀x ∈ Cw : (x, d) ∈ / MU (z, t′ ) ∧ ∀x ∈ Cd : (w, x) ∈ / MU (z, t′ ))).

Example: Consider an example execution of OOLS with LR, illustrated in Figure 2, in round 46. Case LR1Hop evaluates to true for, e.g., the message σ(2, 6). Case LR2Hop, on the other hand, evaluates to true for σ(10, 7) (using node w = 3 as relay). Complexity Given a message σ(s, d) ∈ σ, the computational complexity of OOLS-1H (Cases 1,2, and 6) is bounded by |Ssd |, which is ≤ 4, ∀(u, v) ∈ V × V for the special case of a BST, and O(k) for the more general case of a boundeddegree network family N , where k is the maximum vertex degree in Nt ∈ N . The cost of OOLS-2H (Cases 3,4,5 and 7) is dominated by the size of the search space for the relay

5

12 nodes – round 46

12 nodes – round 0

𝑀∪

12 nodes – round 92

𝑠𝑤1 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤2 ∈ 𝑆𝑊 𝑀∪

𝑠𝑤5 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤6 ∈ 𝑆𝑊

𝑠𝑤9 ∈ 𝑆𝑊 𝑀× 𝑠𝑤10 ∈ 𝑆𝑊 𝑀×

𝑠𝑤1 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤2 ∈ 𝑆𝑊 𝑀∪

𝑠𝑤5 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤6 ∈ 𝑆𝑊

𝑠𝑤9 ∈ 𝑆𝑊 𝑀× 𝑠𝑤10 ∈ 𝑆𝑊 𝑀×

𝑠𝑤1 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤2 ∈ 𝑆𝑊 𝑀∪

1

1

1

9

9

9

9

9

1

1

9

1

1

1

1

𝑠𝑤5 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤6 ∈ 𝑆𝑊

1

9

9

9

9

9

1

1

9

1

1

1

1

9

9

9

9

9

1

1

9

2

2

2

2

10

10

10

10

10

2

2

10

2

2

2

2

10

10

10

10

10

2

2

10

2

2

2

2

10

10

10

10

10

2

2

10

3

11

4

12

𝑀∪

3

3

3

3

11

11

11

11

11

3

3

11

3

3

3

3

11

11

11

11

11

3

3

11

3

3

3

3

4

4

4

4

12

12

12

12

12

4

4

12

4

4

4

4

12

12

12

12

12

4

4

12

4

4

4

4

𝑀×

𝑠𝑤11 ∈ 𝑆𝑊 𝑀× 𝑠𝑤12 ∈ 𝑆𝑊 𝑀×

𝑠𝑤3 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤4 ∈ 𝑆𝑊 𝑀∪

𝑠𝑤7 ∈ 𝑆𝑊 𝑀× 𝑠𝑤8

1

5

9

5

5

9

5

5

5

5

5

1

1

2

6

10

6

6

10

6

6

6

6

6

2

2

7

11

7

7

7

7

7

3

3

7

11

7

8

12

8

8

8

8

8

4

4

8

12

8

𝑠𝑤3 ∈ 𝑆𝑊 𝑀∪ 𝑠𝑤4 ∈ 𝑆𝑊 𝑀∪

𝑠𝑤7 ∈ 𝑆𝑊 𝑀× 𝑠𝑤8 ∈ 𝑆𝑊

5

5

5

5

5

1

6

6

6

6

6

2

7

7

7

7

7

3

3

7

11

7

8

8

8

8

8

4

4

8

12

8

∈ 𝑆𝑊 𝑀×

𝑀∪

𝑠𝑤9 ∈ 𝑆𝑊 𝑀× 𝑠𝑤10 ∈ 𝑆𝑊 𝑀×

11

11

11

11

11

3

12

12

12

12

12

4

𝑠𝑤11 ∈ 𝑆𝑊 𝑀× 𝑠𝑤12 ∈ 𝑆𝑊 𝑀×

𝑠𝑤3 ∈ 𝑆𝑊

5

9

5

5

9

5

5

5

5

5

1

6

10

6

6

10

6

6

6

6

6

2

7

11

7

7

7

7

7

3

3

7

11

7

7

11

8

12

8

8

8

8

8

4

4

8

12

8

8

12

𝑀∪

𝑠𝑤4 ∈ 𝑆𝑊

𝑀∪

𝑀×

𝑠𝑤11 ∈ 𝑆𝑊

1

5

9

5

5

9

2

6

10

6

6

10

𝑠𝑤7 ∈ 𝑆𝑊 𝑀× 𝑠𝑤8

∈ 𝑆𝑊

𝑀×

𝑠𝑤12 ∈ 𝑆𝑊 𝑀×

Fig. 2: OOLS-1H execution: DiSplayNet, n = 12, p = 4, C = 3, |SW | = 12, rounds 0 (first), 46 (middle), and 92 (final).

0 4

𝐶0 × 𝐶0

𝐶1 × 𝐶1

𝑠𝑤0∪

𝑠𝑤2∪

𝐶0 × 𝐶1 𝑠𝑤6×

0

0

4

4

1

1

5

5

2

2

6

6

3

3

7

7

...

0

4

1

5

2

6

1

5

6 3

𝑠𝑤3∪

𝑠𝑤1∪

2

3

7

𝑠𝑤7×

0

0

4

4

4

0

1

1

5

5

5

1

2

2

6

6

3

3

7

7

7

...

6

2

7

3

(a) Only SAN links (BST w/ n = 8, p = 4, C = (b) OOLS-2H (n = 2, |SW | = 8) 8, p = 8, |SW | = 2)

Fig. 3: OpticNet link-to-port mapping: (a) Only SAN links; (b) Augmented topology w/ 2-hop OOLS path L(5, 0, 7).

The controller node handles prioritization rules among nodes participating in each (routing and link adjustment) operation to ensure they don’t join in conflicting operations. To prevent multi-round adjustments (e.g. a zig-zag splay) from being interrupted by messages with higher priority, OpticNet handles conflicts around such adjustments by assigning maximum priority to messages related to them, and nodes are never locked for more than one round. OOLS adopts and extends this strategy, in line with some related work [30], [33]. To prevent routing inconsistency, nodes participating in OOLS-1H operations are locked for the current round, and nodes involved in OOLS-2H are locked for the current and the subsequent rounds. IV. E VALUATION

node w, which can belong to one of as many as C = O(n/p) clusters. To reduce complexity, for each cluster Ci , 1 ≤ i ≤ C, we maintain a priority list topC(Ci ) of < C clusters Cj , j ̸= i, sorted by (non-decreasing) number of occupied links, i.e., |{(u, v) ∈ MHL (z, t′ ), swz ∈ Suv , u ∈ Ci , v ∈ Cj }|. For a message σ(s, d), we limit the search space to at most min(C, topC) candidate clusters Cw ∈ topC(Cs ), s ∈ Cs , where Cs is the cluster of s. From each of these (least occupied) clusters Cw , we select (uniformly at random) a subset of at most min(p, topC) nodes w ∈ Cw , and check the feasibility conditions (Cases 3, 4, 5, 7) for all switches in Ssw d d |) = O(1) for BST, and Sw , which runs in time O(|Ssw | + |Sw and O(k) for a bounded-degree topology). If the insertion of the two-hop opportunistic link L(s, w, d) is successful, we update the priority list topC(Cs ). Putting everything together, we have min(C, topC) · min(p, topC) · O(k) + O(log(C)). For the special case of BST, with |Suv | ≤ 4, ∀(u, v) and topC = O(1), the cost of OOLS-2H is upper bounded by O(k + log(C)) = O(log( np )) per message. Concurrency: To handle concurrent requests for link adjustments, OpticNet adopts an optimistic approach, i.e., conflicts are dealt with upon occurrence. In order to ensure deadlock and starvation freedom, concurrent requests are executed according to a priority. Given two messages σi ∈ σ and σj ∈ σ, we say that σi has a higher priority than σj if bi < bj .

Baselines: To evaluate the performance of OOLS, we used the OpticNet3 simulation framework and the following SAN algorithms as baselines: 4 • DSN: SemiDiSplayNet , an enhanced version of DisplayNet [31] with additional splay rotations. DisplayNet is a distributed and concurrent version of SplayNet [29]; • CBN: CBNet [33], a distributed and concurrent generalization of CBTree [38]. DiSplayNet is the most dynamic SAN in terms of network reconfiguration. Given a message σ(s, d), the source node s performs splaying rotations until de (s, d) = 1 and only then forwards the message content to the destination node d. In SemiDisplayNet, there are additional top-down semisplay rotations, some of which also involve routing. CBNet, on the other hand, uses locally stored counters, s decides whether to perform splaying or to forward the message to an intermediate node v along the path to d. In the latter case, v becomes the carrier of σ(s, d) and repeats the procedure until the message reaches the destination d. On average, CBNet performs a much lower number of splaying operations, while preserving a similar total communication cost, compared to SemiDiSplayNet. 3 https://github.com/caiocaldeira3/OpticalNet 4 https://github.com/caiocaldeira3/SemiDisplayOpticNet

6

TABLE I: Workload parameters. Workload pFabric (Trace 0.5) [39] Facebook [40] HPC (Multigrid) Bursty [9] Skewed [9] ProjecToR [17]

T (σ) 0.431 1.000 0.535 0.400 1.000 0.997

N T (σ) 0.986 0.904 0.820 1.000 0.400 0.467

n 144 367 1024 128 128 128

V. S IMULATION R ESULTS m 1, 000, 000 1, 000, 000 1, 000, 000 10, 000 10, 000 10, 000

OOLS versions: We implemented the following variations of OOLS5 ,6 : OOLS-1H(DSN): the DSN-based one-hop OOLS; OOLS-1H(CBN): the CBN-based one-hop OOLS; • OOLS-2H(DSN): the DSN-based two-hop OOLS; • OOLS-2H(CBN): the CBN-based two-hop OOLS; • OOLS-2H(DSN,LRU): the DSN-based two-hop OOLS with LRU cache (link) replacement; • OOLS-2H(DSN,LFU): the DSN-based two-hop OOLS with LFU cache replacement; • •

Metrics: We used the following metrics to evaluate the performance of the simulated algorithms: Throughput (defined as the total number of messages delivered per round); • Makespan (defined in Eq. (II)); • Total work (defined in Eq. (1)); • Switch activation: the percentage of simulation rounds, relative to the makespan, in which an OCS switch performed either a routing or a reconfiguration operation; •

Workloads: To quantify the locality of reference in a workload, we use the concept of trace complexity [9]. In this context, we distinguish between temporal (T (σ)) and spatial components (N T (σ)) of locality. We used a set of diverse traffic workloads (σ) with variable length (m), network size (n), and spatial (N T (σ)) and temporal (T (σ)) localities, as listed in Table I. Note that N T (σ) and T (σ) ∈ [0, 1], such that values closer to 1 indicate lower locality, and values closer to 0 indicate higher locality. In particular, we have that: ProjecToR7 and Skewed have high spatial and low temporal locality; • PFabric and Bursty have high temporal and low spatial locality; 8 • HPC has relatively high temporal and spatial locality; • Facebook has low temporal and spatial locality. •

Simulation parameters: The sequence of messages in each workload was simulated following the Poisson distribution with λ = 1 expected messages per time slot. Since each simulation round of OpticNet is comprised of three time slots, plus one time slot for logging, a sequence of m messages takes, on average, ≈ m/1.48 = 0.68m simulation rounds to be generated (which is also the expected lower bound for the makespan). 5 https://github.com/marcostiagofh/OOLS-CBN 6 https://github.com/marcostiagofh/OOLS-DSN 7 https://www.microsoft.com/en-us/research/project/ projector-agile-reconfigurable-data-center-interconnect/ 8 https://portal.nersc.gov/project/CAL/overview.htm

In this section we present and discuss our simulation results. In Sec. V-A, we analyze the throughput and makespan; in Sec. V-B, we analyze the total work (communication cost); in Sec. V-C, we analyze the cache replacement strategies; in Sec. V-D and Sec.V-E, we analyze the activity distribution with constant and variable switch size, resp.; and, finally, in Sec. V-F we present some concluding remarks. A. Throughput and Makespan In Figure 4, we compare the throughput, defined as the total number of messages delivered per round, of the baseline SAN algorithms (CBN and DSN) to the two-hop OOLS implemented over those algorithms (OOLS-2H(CBN) and OOLS2H(DSN), resp.). Note that the makespan is represented by the maximum round index on the x-axis. Figures 4a through 4f show the results for all datasets. To facilitate the comparative analysis among different datasets, the size of the OCS switch, measured in the number of ports, p, has been chosen such that p ≈ 16, where n is the number of network nodes (ToRs), n in all workloads. We can observe that, in all scenarios, the makespan achieved by the baselines is at least 1.7m (CBN) and 2.0m (DSN), where m is the total number of messages exchanged during each simulation. Two-hop OOLS, on the other hand, delivers all messages in less than 0.7m rounds in all workloads. This reveals that OOLS significantly increases the concurrency of the system, relative to the baseline SAN algorithms, which struggle to sustain concurrency due to costly locking operations required during conflicting rotations. In particular, for p = ⌈n/16⌉, the makespan reductions achieved by one-hop and two-hop OOLS, resp., were: 81% and 81% in pFabric (Fig. 5a), 70% and 82% in Facebook (Fig. 5b), 40% and 85% in HPC (Fig. 5c), 75% and 79% in Bursty (Fig. 5d), 76% and 76% in Skewed (Fig. 5e), and 61% and 66% in ProjecToR (Fig. 5f). Already in one-hop version, OOLS performed better in pFabric. In the same workload, OOLS maintained the same performance in the two-hop version. This may indicate that OOLS favors primarily temporal locality, but also higher values of n (which distinguishes pFabric from Bursty) to reduce makespan. B. Communication Cost (Total Work) In Figure 5, we analyze the total communication cost (Eq. (1)), partitioned into service cost (Eq. (2)), link updates (Eq. (3)), and, additionally, opportunistic links (created by OOLS), in all scenarios from Figure 5, with the addition of a variable switch size p ∈ [⌈n/16⌉, ⌈n/8⌉, ⌈n/4⌉, n]. Moreover, we included the results for the one-hop OOLS (OOLS-1H(DSN)) and excluded the CBN baseline. First, note that the baseline (DSN) is invariant to the value of p, as expected. In all datasets, OOLS decreases the total communication cost as it does with the makespan, especially with a lower p value, given a fixed n. In particular, for p = ⌈n/16⌉, two-hop OOLS reduces the total cost by 96%, 96%, 91%, 94%, 96%, 91%, for the pFabric (Fig. 5a),

1 2 Time (rounds) x106

3

CBN DSN OOLS−2H(CBN) OOLS−2H(DSN)

0

2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

2 4 Time (rounds) x106

CBN DSN OOLS−2H(CBN) OOLS−2H(DSN)

0

1

2 3 Time (rounds) x106

4

(a) pFabric (n = 144, p = 9, m = 106 )

(b) Facebook (n = 367, p = 23, m = 106 )

(c) HPC (n = 1024, p = 64, m = 106 )

2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

CBN DSN OOLS−2H(CBN) OOLS−2H(DSN)

0

1 2 Time (rounds) x104

(d) Bursty (n = 128, p = 8, m = 104 )

3

CBN DSN OOLS−2H(CBN) OOLS−2H(DSN)

0

1 2 Time (rounds) x104

3

(e) Skewed (n = 128, p = 8, m = 104 )

Requests completed/round

Requests completed/round

0

2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

Requests completed/round

CBN DSN OOLS−2H(CBN) OOLS−2H(DSN)

Requests completed/round

2.8 2.6 2.4 2.2 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

Requests completed/round

Requests completed/round

7

CBN DSN OOLS−2H(CBN) OOLS−2H(DSN)

0

0.5

1 1.5 Time (rounds) x104

2

2.5

(f) ProjecToR (n = 128, p = 8, m = 104 )

Fig. 4: Throughput over all datasets (⌈n/p⌉ = 16).

Facebook (Fig. 5b), HPC (Fig. 5c), Bursty (Fig. 5d), Skewed (Fig. 5e), and ProjecTor (Fig. 5f) workloads, respectively. For p = n, these values become 93%, 88%, 77%, 87%, 88%, 70%, respectively. Comparing one-hop and two-hop OOLS, the latter outperforms the former in all scenarios, also in total work reduction, confirming that after all one-hop link opportunities have been used up, two-hop links remain available for OOLS. In particular, when p = ⌈n/16⌉, the cost reductions achieved by one-hop and two-hop OOLS, resp., were: 92% and 96% in pFabric (Fig. 5a), 76% and 96% in Facebook (Fig. 5b), 62% and 91% in HPC (Fig. 5c), 83% and 94% in Bursty (Fig. 5d), 95% and 96% in Skewed (Fig. 5e), and 86% and 91% in ProjecToR (Fig. 5f).

we observe in the pFabric scenario (Fig. 6a): the link update portion of the total communication cost of OOLS is close to zero for all values of p except p = n and, therefore, the total communication cost is almost a constant, with or without cache replacement. In the scenarios with higher link update cost (Fig. 6b and Fig. 6c), we observe that link (cache) replacement significantly reduces the total communication cost of OOLS, which increases with the switch size (p). E.g., even when p = n, OOLS-2H(DSN, LRU) reduced the total work by 51% in HPC, and by 38% in Facebook, relative to OOLS-2H without link replacement. Finally, we observe that LRU slightly outperforms LFU, especially in workloads with higher temporal locality, like pFabric (Fig. 6a) and HPC (Fig. 6c).

C. Link (cache) Replacement In Figure 6, we analyze the impact of cache replacement strategies (LFU and LRU) on the total communication cost of OOLS (two-hop, DSN-based). We focus on workloads with variable network size (pFabric (n = 144), Fig. 6a, Facebook (n = 367), Fig. 6b, and HPC (n = 1024), Fig. 6c) and scenarios with variable switch size (p ∈ [⌈n/16⌉, ⌈n/8⌉, ⌈n/4⌉, n]). Firstly, note that because DSN is a SAN algorithm that prioritizes rotations over message forwarding, its service cost generally approximates m, i.e. a constant close to a lower bound of one hop per message. Therefore, even though OOLS is designed to reduce both the service cost and the link update cost, in the case of DSN, OOLS affects almost exclusively the link update cost. As a result, the gain obtained by OOLS and, in particular, by cache replacement heuristics, is very small in scenarios where the number of rotations is close to zero. This is what

D. OCS Activity Distribution (constant switch size) In Figure 7, we show the CDF (Cumulative Distribution Function), over the set of all optical switches, of the percentage of rounds (relative to the total simulation time) in which at least one message has been routed through each switch. We compare the behavior of one-hop OOLS, two-hop OOLS, both running in combination with DSN, to the DSN baseline (without opportunistic link scheduling). Note that a rapidly rising CDF curve points to sparser activity bursts, while a slower-rising curve indicates a more even distribution of OCS activity in time. We observe that, in all simulated scenarios, the fastest-rising CDF curve is that of the two-hop OOLS, and the slowest-rising curve is that of the baseline (DSN), which reveals that optical switches are less active over time in OOLS than in DSN. This can be explained by the fact that OOLS reduces the number

8

(a) pFabric (n = 144, m = 106 )

(b) Facebook (n = 367, m = 106 )

(c) HPC (n = 1024, m = 106 )

(d) Bursty (n = 128, p = 8, m = 104 )

(e) Skewed (n = 128, m = 104 )

(f) ProjecToR (n = 128, m = 104 )

Fig. 5: Total work over all datasets (DSN-based SANs, var. switch size p). The % numbers are relative to the cost of DSN.

(a) pFabric (n = 144, m = 106 )

(b) Facebook (n = 367, m = 106 )

(c) HPC (n = 1024, m = 106 )

Fig. 6: OOLS with Link Replacement (LR): Total work (variable p). The % numbers are w.r.t. the cost of OOLS without LR.

of hops needed to deliver some messages, which reduces the total communication cost, resulting in lower switch activity over time. In workloads with very high spatial locality, like Skewed (Fig. 7e) and ProjecTor (Fig. 7f), the two-hop OOLS exhibited the highest OCS inactivity. In the former scenario, approximately 95% of switches were active 0% of the rounds, i.e., completely idle. In the latter, almost 92% of the switches were inactive 100% of the time. This is due to the small OCS size (p = ⌈n/16⌉), which results in a greater number of OCS switches used by OpticNet, whereas the demand is concentrated at an extremely small subset of nodes. Note that in all the other workloads, 0% of switches remained inactive 100% of the time. In workloads with high spatial locality and high temporal locality, like HPC (Fig. 7c), (two-hop) OOLS exhibited the lowest OCS inactivity: approx. 95% of switches were active at least 4% of the simulation rounds. This is due to the demand, which is spread over a larger subset of nodes, the SAN topology, which is more dynamic, and the greater total reconfiguration cost (number of link updates).

E. OCS Activity Distribution (variable switch size) We now analyze the behavior of the two-hop OOLS (running in combination with DSN) in scenarios with increasing OCS size (number of ports) p ∈ [8, 16, 32, 128], in three scenarios with network size n = 128: Bursty, Skewed, and ProjecToR. Figure 8 depicts the CDF (over the set SW ) of the % of active rounds per switch. We observe that, in all scenarios (Fig. 8a, Fig. 8b, Fig. 8c), the CDF curve is shifted to the right with increasing values of p, i.e., a greater number of switches are activated in a greater number of simulation rounds, and a greater % of ports per switch are activated at least once during the simulation. E.g., in the Skewed workload, for p = 8, only 4% of switches are activated at least once during the entire simulation (Fig. 8b, red line). On the other hand, when p = 128, all 100% (4 out of 4) of switches are activated ≥ 50% of the time (Fig. 8b, black line). This is because, when p increases, even though the demand sequence remains the same, it is spread over fewer available OCS ports, resulting in a higher switch activation ratio.

9

(a) pFabric (n = 144, p = 9, m = 106 )

(b) Facebook (n = 367, p = 23, m = 106 )

(c) HPC (n = 1024, p = 64, m = 106 )

(d) Bursty (n = 128, p = 8, m = 104 )

(e) Skewed (n = 128, p = 8, m = 104 )

(f) ProjecToR (n = 128, p = 8, m = 104 )

Fig. 7: CDF % active switches per round over all datasets (DSN-based SANs, ⌈n/p⌉ = 16).

(a) Bursty (n = 128, p = 8, m = 104 )

(b) Skewed (n = 128, p = 8, m = 104 )

(c) ProjecToR (n = 128, p = 8, m = 104 )

Fig. 8: OOLS-2H(DSN): CDF % active switches per round (variable switch size p).

F. Final remarks In all workloads, OOLS significantly increased the concurrency of the system, relative to the baseline SAN algorithms (DiSplayNet and CBNet). E.g., for p = ⌈n/16⌉, the twohop OOLS achieved a reduction in makespan of at least 70% in all workloads, relative to DSN. The reduction in communication cost was even greater than in makespan. The two-hop OOLS reduced the total cost by at least 91% and 70%, for p = ⌈n/16⌉ and p = n, respectively. Comparing one-hop and two-hop OOLS, the latter outperforms the former in all scenarios. The performance of OOLS is further enhanced by the use of cache (link) replacement strategies (LRU or LFU), especially in scenarios with high reconfiguration costs and high temporal locality. The simulation results pointed to a trade-off between efficiency improvement and resource utilization, as a function of switch size p. On the one hand, when p decreases, OOLS achieves lower switch and port % activation but greater gains in throughput and communication cost. This is due to the fact that the number of idle OCS ports to be allocated opportunistically by OOLS is upper bounded by the total number of ports, given by opp ≤ p × |SW | − n + 1, where |SW | is the total number of optical switches in the OpticNet system (defined in Eq. (4)), and (n − 1) is the

minimum number of edges in any connected topology. For a BST network on n nodes, to  opp is  inversely proportional   p: opp ≤ p · |SW | − n = p n2 /p2 + p ⌈n/p⌉ − n ≤ n2 /p . On the other hand, when p increases, the demand is spread over fewer OCS ports, resulting in higher switch and port % activation, but also lower gains in throughput and communication cost, relative to the baselines. VI. R ELATED W ORK RDNs can be categorized based on whether topology reconfigurations are driven by traffic demand. Demand-oblivious designs [16], [41]–[43] operate according to fixed reconfiguration schedules, independent of workload characteristics, whereas demand-aware approaches [2], [17], [28], [29], [31] explicitly adapt connectivity in response to observed traffic. Hybrid architectures combining both paradigms have also been explored [44]. Making decisions at sub-second timescales limits the ability to gather complete traffic information, suggesting the need for hybrid control designs that combine distributed, centralized, and possibly hierarchical coordination [2]. So far, there seem too be no consensus in the community on which RDN design is optimal [10]. In [25], the problem of Maximum Switching Capacity was formulated, as follows: given a set of n terminal nodes and a set of identical p × p switches, the objective is to maximize the total number of

10

connections, while ensuring the strict non-blocking condition, i.e., that any point-to-point connection can be established. In [26], a so-called multiple-plane twisted-folded Clos network (MP-TF Clos) was proposed, to increase switching capacity, while relaxing the strict non-blocking requirement. This type of design incorporates intermediary switches between terminal node pairs, which requires a connection admission control mechanism. VII. C ONCLUSION In this work, we presented OOLS, comprised of a set of lightweight real-time routines, designed to leverage idle OCS resources in RDN architectures. Our work is based on the Scalable Matching Model (SMM) [36]. SMM supports small OCS devices in exchange for a set of (n) larger (ToR) electrical packet switches (typically available for a lower perport price than OCS hardware [45]). SMM guarantees strict non-blocking, uses a minimum number of OCSs to realize any (dynamic) bounded-degree network topology, and allows executing existing SAN algorithms on top of it while preserving the performance (amortized communication cost) guarantees of the latter. In our experiments, OOLS significantly improved the performance of SAN algorithms, lowering communication cost and boosting throughput. We conclude by noting that RDNs are a promising but still experimental concept. Many questions remain open regarding the effects of dynamic topologies on higher protocol layers [46], [47], static and dynamic optimality of SAN algorithms [28], [48], [49], and the optimal trade-off between maximizing throughput while minimizing latency [43], [50]. R EFERENCES [1] K.-T. Foerster, T. Marette, S. Neumann, C. Plant, Y. Sadikaj, S. Schmid, and Y. Velaj, “Analyzing the communication clusters in datacenters,” in Proceedings of the ACM Web Conference 2023, ser. WWW ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 3022–3032. [2] L. e. a. Poutievski, “Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking,” in Proceedings of the ACM SIGCOMM 2022 Conference, ser. SIGCOMM ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 66–85. [3] A. Singh, J. Ong, A. Agarwal, G. Anderson, A. Armistead, R. Bannon, S. Boving, G. Desai, B. Felderman, P. Germano et al., “Jupiter rising: A decade of clos topologies and centralized control in google’s datacenter network,” Proc. ACM SIGCOMM Computer Communication Review (CCR), vol. 45, no. 4, pp. 183–197, 2015. [4] V. Liu, D. Halperin, A. Krishnamurthy, and T. Anderson, “F10: A fault-tolerant engineered network,” in Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, ser. NSDI’13. Berkeley, CA, USA: USENIX Association, 2013, pp. 399– 412. [5] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “BCube: a high performance, server-centric network architecture for modular data centers,” ACM SIGCOMM Computer Communication Review (CCR), vol. 39, no. 4, pp. 63–74, 2009. [6] H. Wu, G. Lu, D. Li, C. Guo, and Y. Zhang, “MDCube: a high performance network structure for modular data center interconnection,” in ACM International Conference on Emerging Networking Experiments and Technologies (CONEXT), 2009, pp. 25–36. [7] S. Kassing, A. Valadarsky, G. Shahaf, M. Schapira, and A. Singla, “Beyond fat-trees without antennae, mirrors, and disco-balls,” in Proc. ACM SIGCOMM, 2017, pp. 281–294. [8] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: Networking data centers, randomly,” in Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), vol. 12, 2012, pp. 17–17.

[9] C. Avin, M. Ghobadi, C. Griner, and S. Schmid, “On the complexity of traffic traces and implications,” in Proc. ACM SIGMETRICS, 2020. [10] C. Avin and S. Schmid, “Revolutionizing datacenter networks via reconfigurable topologies,” Commun. ACM, vol. 68, no. 6, p. 44–53, Jun. 2025. [Online]. Available: https://doi.org/10.1145/3708980 [11] J. Li, H. Gong, F. De Marchi, A. Gong, Y. Lei, W. Bai, and Y. Xia, “Uniform-cost multi-path routing for reconfigurable data center networks,” in Proceedings of the ACM SIGCOMM 2024 Conference, ser. ACM SIGCOMM ’24. New York, NY, USA: Association for Computing Machinery, 2024, p. 433–448. [12] M. Hall, K.-T. Foerster, S. Schmid, and R. Durairajan, “A survey of reconfigurable optical networks,” Optical Switching and Networking, vol. 41, Sep. 2021, publisher Copyright: © 2021 Elsevier B.V. [13] C. Liang, X. Song, J. Cheng, M. Wang, Y. Liu, Z. Liu, S. Zhao, and Y. Cui, “NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter Network,” in ACM SIGCOMM Conference. New York, NY, USA: Association for Computing Machinery, 2024, p. 415–432. [14] V. Addanki, C. Avin, and S. Schmid, “Mars: Near-optimal throughput with shallow buffers in reconfigurable datacenter networks,” in ACM SIGMETRICS, 2023. [15] J. Zerwas, C. Gyorgyi, A. Blenk, S. Schmid, and C. Avin, “Duo: A high-throughput reconfigurable datacenter network using local routing and control,” in ACM SIGMETRICS, 2023. [16] H. Ballani, P. Costa, R. Behrendt, D. Cletheroe, I. Haller, K. Jozwik, F. Karinou, S. Lange, K. Shi, B. Thomsen et al., “Sirius: A flat datacenter network with nanosecond optical switching,” in Proc. ACM SIGCOMM, 2020, pp. 782–797. [17] M. Ghobadi, R. Mahajan, A. Phanishayee, N. Devanur, J. Kulkarni, G. Ranade, P.-A. Blanche, H. Rastegarfar, M. Glick, and D. Kilper, “ProjecToR: Agile Reconfigurable Data Center Interconnect,” in Proc. ACM SIGCOMM. New York, NY, USA: ACM, 2016, pp. 216–229. [18] A. Shakeri, M. Garrich, A. Bravalheri, D. Careglio, J. Sole-Pareta, and A. Fumagalli, “Traffic allocation strategies in wss-based dynamic optical networks,” Journal of Optical Communications and Networking, vol. 9, no. 4, pp. B112–B123, 2017. [19] A. S. Raja, S. Lange, M. Karpov, K. Shi, X. Fu, R. Behrendt, D. Cletheroe, A. Lukashchuk, I. Haller, F. Karinou, B. Thomsen, K. Jozwik, J. Liu, P. Costa, T. J. Kippenberg, and H. Ballani, “Ultrafast optical circuit switching for data centers using integrated soliton microcombs,” Nature Communications, vol. 12, no. 1, 2021. [20] E. Feder, I. Rathod, P. Shyamsukha, R. Sama, V. Aksenov, I. Salem, and S. Schmid, “Lazy self-adjusting bounded-degree networks for the matching model,” in Proc. IEEE Conference on Computer Communications (INFOCOM), 2022. [21] ——, “Toward self-adjusting networks for the matching model,” in 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021. [22] C. Avin, C. Griner, I. Salem, and S. Schmid, “An online matching model for self-adjusting tor-to-tor networks,” 2020. [23] K. Hanauer, M. Henzinger, L. Ost, and S. Schmid, “Dynamic demandaware link scheduling for reconfigurable datacenters,” in IEEE INFOCOM, 2023. [24] K. Hanauer, M. Henzinger, S. Schmid, and J. Trummer, “Fast and heavy disjoint weighted matchings for demand-aware datacenter topologies,” in IEEE INFOCOM 2022 - IEEE Conference on Computer Communications. IEEE, May 2022, p. 1649–1658. [25] T. Mano, T. Inoue, K. Mizutani, and O. Akashi, “Redesigning the nonblocking clos network to increase its capacity,” IEEE Trans. on Netw. and Serv. Manag., vol. 20, no. 3, p. 2558–2574, Sep. 2023. [Online]. Available: https://doi.org/10.1109/TNSM.2022.3228909 [26] E. Oki, R. Taniguchi, K. Anazawa, and T. Inoue, “Design of MultiplePlane Twisted and Folded Clos Network Guaranteeing Admissible Blocking Probability,” IEEE Transactions on Network and Service Management, vol. 22, no. 3, pp. 2278–2294, 2025. [27] C. Avin and S. Schmid, “Toward demand-aware networking: A theory for self-adjusting networks,” in ACM SIGCOMM Computer Communication Review (CCR), 2018. [28] ——, “Renets: Statically-optimal demand-aware networks,” in Proc. SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), 2021. [29] S. Schmid, C. Avin, C. Scheideler, M. Borokhovich, B. Haeupler, and Z. Lotker, “Splaynet: Towards locally self-adjusting networks,” IEEE/ACM Trans. Netw., vol. 24, no. 3, pp. 1421–1433, 2016. [30] B. Peres, O. A. d. O. Souza, O. Goussevskaya, C. Avin, and S. Schmid, “Distributed self-adjusting tree networks,” IEEE Transactions on Cloud Computing, 2021.

11

[31] B. Peres, O. Souza, O. Goussevskaia, S. Schmid, and C. Avin, “Distributed self-adjusting tree networks,” in Proc. IEEE INFOCOM, 2019. [32] O. A. d. O. Souza, O. Goussevskaia, and S. Schmid, “CBNet: Minimizing Adjustments in Concurrent Demand-Aware Tree Networks,” in IEEE Int. Parallel and Distributed Processing Sym. (IPDPS), 2021, pp. 382–391. [33] O. A. de O. Souza, O. Goussevskaia, and S. Schmid, “CBNet: Demandaware tree topologies for Reconfigurable Datacenter Networks,” Computer Networks, vol. 213, p. 109090, 2022. [34] C. Avin, K. Mondal, and S. Schmid, “Demand-aware network designs of bounded degree,” in Proc. International Symposium on Distributed Computing (DISC), 2017. [35] C. A. Caldeira, O. A. de O. Souza, O. Goussevskaia, and S. Schmid, “OpticNet: Self-Adjusting Networks for ToR-Matching-ToR Optical Switching Architectures,” in IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, 2023, pp. 1–10. [36] C. Caldeira, O. A. de Oliveira Souza, O. Goussevskaia, and S. Schmid, “Optical self-adjusting data center networks in the scalable matching model,” in IEEE/ACM Transactions on Cloud Computing (TCC), 2024. [37] D. Sleator and R. Tarjan, “Self-adjusting binary search trees,” Journal of the ACM (JACM), vol. 32, no. 3, pp. 652–686, 1985. [38] Y. Afek, H. Kaplan, B. Korenfeld, A. Morrison, and R. E. Tarjan, “Cbtree: A practical concurrent self-adjusting search tree,” in Proc. DISC. Berlin, Heidelberg: Springer-Verlag, 2012, pp. 1–15. [39] M. Alizadeh, S. Yang, M. Sharif, S. Katti, N. McKeown, B. Prabhakar, and S. Shenker, “PFabric: Minimal near-Optimal Datacenter Transport,” in Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, ser. SIGCOMM ’13. New York, NY, USA: Association for Computing Machinery, 2013, p. 435–446. [Online]. Available: https://doi.org/10.1145/2486001.2486031 [40] A. Roy, H. Zeng, J. Bagga, G. Porter, and A. C. Snoeren, “Inside the social network’s (datacenter) network,” in Proceedings of the 2015 ACM SIGCOMM, ser. SIGCOMM ’15. New York, NY, USA: ACM, 2015, pp. 123–137. [41] W. M. Mellette, R. McGuinness, A. Roy, A. Forencich, G. Papen, A. C. Snoeren, and G. Porter, “Rotornet: A scalable, low-complexity, optical datacenter network,” in Proc. ACM SIGCOMM, 2017, pp. 267–280. [42] W. M. Mellette, R. Das, Y. Guo, R. McGuinness, A. C. Snoeren, and G. Porter, “Expanding across time to deliver bandwidth efficiency and low latency,” arXiv preprint arXiv:1903.12307, 2019. [43] D. Amir, T. Wilson, V. Shrivastav, H. Weatherspoon, R. Kleinberg, and R. Agarwal, “Optimal oblivious reconfigurable networks,” in Proc. of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022. [44] C. Griner, J. Zerwas, A. Blenk, S. Schmid, M. Ghobadi, and C. Avin, “Cerberus: The power of choices in datacenter topology design (a throughput perspective),” in Proc. ACM SIGMETRICS, 2022. [45] “Polatis Series 6000,” www.polatis.com, [Online; accessed 10-May2022]. [46] K. Aykurt, J. Zerwas, A. Blenk, and W. Kellerer, “When TCP Meets Reconfigurations: A Comprehensive Measurement Study,” IEEE Transactions on Network and Service Management, vol. 21, no. 2, pp. 1372– 1386, 2024. [47] J. Zerwas, I. Poese, S. Schmid, and A. Blenk, “On the Benefits of Joint Optimization of Reconfigurable CDN-ISP Infrastructure,” IEEE Transactions on Network and Service Management, vol. 19, no. 1, pp. 158–173, 2022. [48] C. Levy and R. Tarjan, “A new path from splay to dynamic optimality,” in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1311–1330. [49] E. D. Demaine, D. Harmon, J. Iacono, and M. Pǎtraşcu, “Dynamic optimality—almost,” SIAM Journal on Computing, vol. 37, no. 1, pp. 240–251, May 2007. [50] X. Wang, H. Shen, and H. Tian, “Optimal Partitioning of Traffic Demand for Coflow Scheduling in Hybrid Switches,” IEEE Transactions on Network and Service Management, vol. 22, no. 6, pp. 5972–5986, 2025.

Related documents

• Opportunistic Optical Link Scheduling in the Scalable Matching Model#1488796
• THz-SynC: Collective Synthesis with Contextual-Bandit-Assisted Coordination for Reconfigurable Hybrid Optical-THz AI Datacenters#926875
• Cooperative Dueling DQN SAC Learning for Energy Efficiency in Dynamic OWC Networks#1233305
• Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals#1063372
• Fundamentals of queueing theory#1331382