Scheduling Coflows in Multi-Core OCS Networks with Performance Guarantee Xin Wanga , Hong Shena , Hui Tianb , Dong Wanga a
School of Engineering and Technology, Central Queensland University, Australia School of Information and Communication Technology, Griffith University, Australia
I. I NTRODUCTION In large-scale distributed systems such as MapReduce [1], Spark [2] and Dryad [3], a job typically consists of multiple communication stages. Each stage generates a set of parallel flows, and the next computation stage cannot start until all flows in the current stage have finished. Motivated by this synchronization barrier, the coflow abstraction [4] was introduced to group semantically related flows into a unified scheduling object, enabling coordinated scheduling and performance optimization. Taking the shuffle stage of MapReduce as an example (Fig. 1), intermediate results are transferred from each map worker to each reduce worker. Since each reduce worker must collect all required inputs before continuing execution, the completion time of the shuffle stage is dominated by the slowest flow. This also illustrates that optimizing only the individual flow completion time (FCT) is insufficient; more crucial is optimizing the coflow completion time (CCT), defined as the completion time of the last flow in the coflow, thereby more directly improving end-to-end job performance. Most existing research [5]–[15] on coflow scheduling is based on the single-core electrical packet switching (EPS)
Coflow
Output Data
Abstract—Coflow provides a key application-layer abstraction for capturing communication patterns, enabling the efficient coordination of parallel data flows to reduce job completion times in distributed systems. Modern data center networks (DCNs) are employing multiple independent optical circuit switching (OCS) cores operating concurrently to meet the massive bandwidth demands of application jobs. However, existing coflow scheduling research primarily focuses on the single-core setting, with multicore fabrics only for EPS (electrical packet switching) networks. To address this gap, this paper studies the coflow scheduling problem in multi-core OCS networks under the not-all-stop reconfiguration model in which one circuit’s reconfiguration does not interrupt other circuits. The challenges stem from two aspects: (i) cross-core coupling induced by traffic assignment across heterogeneous cores; and (ii) per-core OCS scheduling constraints, namely port exclusivity and reconfiguration delay. We propose an approximation algorithm that jointly integrates crosscore flow assignment and per-core circuit scheduling to minimize the total weighted coflow completion time (CCT) and establish a provable worst-case performance guarantee. Furthermore, our algorithm framework can be directly applied to the multi-core EPS scenario with the corresponding approximation ratio under packet-switched fabrics. Trace-driven simulations using real Facebook workloads demonstrate that our algorithm effectively reduces weighted CCT and tail CCT.
Input Data
arXiv:2604.08242v1 [cs.DC] 9 Apr 2026
b
Map stage
Shuffle stage
Reduce stage
Fig. 1: Coflow Abstraction in MapReduce
model, where the data center network (DCN) is abstracted as a single non-blocking switch fabric with full bisection bandwidth, which simplifies the characterization of port bandwidth constraints and algorithm design. However, with the continuous growth of data center communication scale, the EPS architecture is gradually showing pressure in terms of bandwidth expansion and corresponding cost and energy consumption. To address this, optical circuit switching (OCS) has been introduced into the single-core scenario to improve transmission efficiency by establishing dedicated high-bandwidth circuits for bulk data transfers. Under this single-core OCS model, several coflow schedulers have been developed [16]– [20]. Beyond pure EPS/OCS, prior work has further extended the single-core setting to hybrid EPS-OCS fabrics and studied coflow scheduling with coexisting packet- and circuit-switched resources [21]–[24]. However, the single-core abstraction is no longer well aligned with modern data center architectures. Industry reports [25], [26] suggest that modern DCN fabrics can employ parallel designs, with multiple heterogeneous network cores operating concurrently to scale aggregate bandwidth. In practice, different generations of network architectures often coexist, forming heterogeneous parallel networks (HPNs) in which multiple independent network cores jointly serve the same set of hosts [27]. Motivated by this architectural parallelism, a few studies have investigated coflow scheduling in multi-core EPS networks, leveraging parallel packet-switched fabrics to increase capacity [27], [28]. Meanwhile, parallelism is also emerging in optical switching fabrics. Google’s Jupiter architecture replaces the traditional spine layer with a datacenter interconnection layer consisting of multiple parallel OCS core, evolving into a direct-connect topology that enables flexible,
datacenter-scale capacity upgrades and reconfigurations [29]. Although multi-core OCS infrastructures have been adopted nowadays, coflow scheduling in multi-core OCS networks remains largely unexplored. This multi-core OCS architecture allows for flexible capacity expansion, but fundamentally changes the scheduling model. In multi-core OCS networks, scheduling becomes significantly more challenging. Unlike packet switching, OCS is subject to two key constraints: (i) port exclusivity, meaning that each ingress/egress port can participate in at most one circuit connection at any given time; and (ii) reconfiguration delay, meaning that circuit switching incurs a non-negligible delay δ, typically ranging from hundreds of microseconds to milliseconds. Furthermore, OCS reconfiguration mechanisms are generally divided into two types: the all-stop and notall-stop models (see Subsection III-C). The former relies on preemptive scheduling, in which flows from the same coflow can interrupt each other. The latter depends on nonpreemptive scheduling, ensuring that flows within the same coflow are completed without interruption once started. This paper focuses on the more general and practically relevant notall-stop (asynchronous) model, which further exacerbates the complexity of resource coupling and scheduling decisions. When multiple OCS cores operate in parallel, coflow scheduling must jointly determine (i) how to assign traffic (flows) to different cores, and (ii) how to configure circuits within each core, while respecting one-to-one port exclusivity and non-negligible reconfiguration delay under the not-all-stop model. These cross-core coupled decisions and OCS-specific constraints make the problem substantially more complex than in single-core OCS or multi-core EPS setups. This paper investigates multi-coflow scheduling in multi-core OCS networks and presents an approximation algorithm that integrates crosscore flow assignment with per-core circuit scheduling. To the best of our knowledge, this is the first work that provides a provable performance guarantee for minimizing the total weighted CCT in multi-core OCS networks, thereby filling a notable research gap. Furthermore, we demonstrate that our proposed algorithm framework can be directly applied to multi-core EPS networks by removing reconfiguration delays and replacing OCS-specific lower bounds with their EPS counterparts to yield the corresponding performance guarantee. The rest of this paper is organized as follows: Section II reviews related research and provides a comparative analysis; Section III introduces the system model and formal problem formulation; Section IV describes our proposed multiple coflow scheduling algorithm and its theoretical performance guarantees; Section V reports experimental results using a realistic Facebook trace; Section VI concludes this paper. Additional proofs and supplementary results are provided in the appendix. II. R ELATED W ORK Coflow scheduling has been studied under various DCN switching models. Previous research has largely focused on the single-core EPS abstraction, while more recently coflow
scheduling has been extended to single-core OCS scenarios, including pure OCS fabrics and hybrid EPS-OCS networks, under both all-stop and not-all-stop reconfiguration models. Meanwhile, a smaller body of work has also considered multicore EPS networks, where multiple packet-switched cores operate concurrently to extend aggregate bandwidth. This section reviews related work from these perspectives and provides a comparative summary in Table I. A. Coflow Scheduling in Single-Core EPS Networks Varys [6] proposed two greedy heuristic algorithms, i.e., smallest-effective-bottleneck-first (SEBF) and minimumallocation-for-desired-duration (MADD), to greedily schedule coflows in single-core EPS networks based on bottleneck completion times, aiming to minimize the overall CCT. In decentralized scenarios, Barrat [7] alleviated head-of-line blocking issues for small coflows through multiplexing techniques, while D-CAS [8] also focused on decentralized scheduling. Aalo [9] employed a discretized coflow-aware least-attained service (D-CLAS) algorithm, which can operate efficiently without requiring prior knowledge of flow information. CODA [10] was the first study to apply machine learning to identify coflows between individual flows. Recently, Wang et al. [11] developed an online coflow scheduling model based on deep reinforcement learning (DRL) for multi-stage jobs. In subsequent research, Wang et al. [12] combined limited multiplexing with a DRL framework to reduce the average weighted CCT while maintaining fairness. Rapier [33] was the first to jointly consider routing and coflow scheduling to minimize the CCT. However, all of the above methods are primarily heuristic and do not provide provable worst-case guarantees. At the theoretical level, various approximation algorithms have been proposed. Qiu et al. [13] proposed a deterministic algorithm with a constant approximation ratio of 67 3 for minimizing the total weighted CCT. Khuller et al. [30] modeled the problem as a concurrent open-shop problem and designed a 12-approximation algorithm. Shafiee et al. [14] achieved a 5-approximation via linear programming (LP), while Wang et al. [15] designed a 2-approximation algorithm by simplifying the process, and avoiding LP solving. Im et al. [31] formulated the matroid coflow scheduling problem and proposed a 2approximation algorithm for minimizing the weighted CCT. Shafiee et al. [34] proposed a polynomial-time algorithm with a provable performance guarantee. B. Coflow Scheduling in Single-Core OCS Networks Research on single-core OCS-based scheduling, including pure OCS scheduling and hybrid OCS-EPS scheduling, remains relatively limited. Given the two main OCS reconfiguration paradigms, namely the all-stop model and the not-allstop model, we review the relevant research under each model separately. 1) All-Stop Reconfiguration Model: OMCO [16] was the first online algorithm to schedule multiple coflows in singlecore pure OCS networks. Reco-Sin [17] and Reco-Mul+ [18]
TABLE I: COMPARISON AMONG RELATED WORK Works Varys [6], Barrat [7], D-CAS [8], CODA [10] Qiu et al. [13], Khuller et al. [30], Shafiee et al. [14], Im et al. [31] OMCO [16] Sunflow [19], Reco-Sin [17], Reco-Mul+ [18], GOS [20] Co-scheduler [22], ONS [24] Wang et al. [21], Wang et al. [23] Weaver [27], Chen [32], Chen [28] Our Work
Single-Core EPS-Enable OCS-Enable " ✘ " ✘ ✘ " ✘ " " " " " ✘ ✘ ✘ ✘
were the first algorithms that achieved an approximation ratio of 2 for single coflow scheduling and an approximation ratio of 8M for multiple coflows in single-core pure OCS networks, respectively, where M is the number of coflows. All of the above methods relied on the Birkhoff-von Neumann (BvN) [35] decomposition. In addition, Wang et al. [21] developed approximation algorithms with provable performance guarantees for both single and multiple coflow scheduling in singlecore hybrid EPS-OCS networks. All these methods assumed OCS operates under the all-stop model. 2) Not-All-Stop Reconfiguration Model: Sunflow [19] first proposed a constant-factor approximation algorithm for singlecoflow scheduling in single-core pure OCS networks, as well as a heuristic method for multiple coflow scheduling. GOS [20] further proposed a 4-approximation algorithm for multicoflow scheduling in single-core pure OCS networks. In the context of hybrid networks, Co-scheduler [22] was the first to simultaneously consider optical-electrical hybrid-switching characteristics and coflow structures, but it lacks formal performance guarantees. ONS [24] presented an online heuristic algorithm aimed at minimizing the total CCT in single-core hybrid networks, but it also lacks theoretical guarantees. All of these approaches assume the not-all-stop reconfiguration model. C. Coflow Scheduling in Multi-Core EPS Networks
Performance Guarantee ✘ " ✘ " ✘ " " "
a provably approximation algorithm for coflow scheduling in multi-core OCS networks under not-all-stop (asynchronous) reconfiguration, together with a worst-case performance guarantee. III. S YSTEM M ODEL AND P ROBLEM F ORMULATION In this section, we present the system model, including the network architecture, traffic abstraction, and OCS reconfiguration mechanism. Then, we formally define the multi-coflow scheduling problem in heterogeneous parallel (i.e., multi-core) networks (HPNs), and prove its computational hardness. For clarity and consistency, the main notations used throughout the paper are summarized in Table II. A. Network Architecture We consider a heterogeneous multi-core data center network (DCN) architecture, modeled as K independent, non-blocking N × N switches operating in parallel, as shown in Fig. 2. Each core corresponds to an optical circuit switch, indexed by k ∈ {1, . . . , K}. Source Servers s1
r1
r1
Destination Servers d1
OCS 1
Servers r2
s2
r2
d2
OCS 2 ...
Optical Circuit Switch (OCS)
...
...
Coflow scheduling over multi-core EPS networks has received increasing attention in recent years. Weaver [27] studied the single-coflow scheduling problem in a heterogeneous parallel network (HPN), and proposed an O(K)-approximation algorithm, where K denotes the number of network cores. Chen [32] further investigated scheduling in multi-coflow HPNs and developed an O logloglogKK -approximation algorithm. In addition to heterogeneous cores, Chen [28] also considered identical parallel networks and proposed coflow-level approximation algorithms with approximation ratios 4K + 1 and 4K for arbitrary and zero release times, respectively, where K is the number of identical cores. In summary, current research has explored the coflow scheduling problem in single-core EPS and OCS architectures, as well as in multi-core EPS networks. However, to our knowledge, coflow scheduling in multi-core OCS fabrics remains largely unexplored. This paper fills this gap by developing
Multi-Core EPS-Enable OCS-Enable ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ " ✘ "
sN
dN K uplinks per source server
rK
rK OCS K
K downlinks per destination server
Fig. 2: Heterogeneous Multi-Core DCN Architecture The network interconnects N source servers {s1 , . . . , sN } and N destination servers {d1 , . . . , dN }. Each source server is equipped with K parallel uplinks, each connected to a specific OCS core, and each destination server has K corresponding downlinks. For each core k, source server si is connected to ingress port i, and destination server dj is connected to egress port j, where i, j ∈ {1, . . . , N }. Each core k operates independently at a per-port transmission rate rk , capturing
TABLE II: Mathematical Notations Symbol
Definition
M M K K N Cm Fm Dm k Dm fm (i, j) k (i, j) fm tkm (i, j) dm (i, j) dkm (i, j) ρm ρkm τm
Set of coflows Number of coflows, i.e., M = |M| Set of parallel OCS cores Number of OCS cores, i.e., K = |K| Number of ingress/egress ports per core The m-th coflow, where 1 ≤ m ≤ M Set of flows in Cm Demand matrix of Cm Portion of Dm assigned to core k Flow from ingress port i to egress port j of Cm Subflow of fm (i, j) transmitted on core k k (i, j) on core k Circuit establishment time of fm Data size of fm (i, j) k (i, j) Data size of fm Maximum row or column sum of Dm k Maximum row or column sum of Dm Maximum number of nonzero entries (flows) in any row or column of Dm Maximum number of nonzero entries (flows) in any row or k column of Dm Global coflow order Prefix-aggregated matrix of first m coflows under π, i.e., P D1:m ≜ m ℓ=1 Dπ(ℓ) Prefix-aggregated matrix on core k under π, i.e., P k k D1:m ≜ m ℓ=1 Dπ(ℓ) Maximum row or column sum of D1:m k Maximum row or column sum of D1:m Maximum number of nonzero entries (flows) in any row or column of D1:m Maximum number of nonzero entries (flows) in any row or k column of D1:m Per-port transmission rate of core k P k Aggregate port transmission rate, i.e., R = K k=1 r Weight of Cm Reconfiguration delay Completion time of the portion of coflow Cm assigned to core k k Completion time of coflow Cm , i.e., Tm = maxk Tm
k τm
π D1:m k D1:m
ρ1:m ρk1:m τ1:m k τ1:m
rk R wm δ k Tm Tm
heterogeneous link capacities across cores. Thus, traffic can be distributed across multiple cores, while circuit scheduling is performed independently within each core. B. Traffic Abstraction We employ the coflow abstraction [4] to model applicationlevel communication requirements in HPNs. A coflow captures a collection of parallel flows that must be completed jointly to represent one communication stage of an application across a set of machines. Let M = {C1 , . . . , CM } denote the set of coflows. Each coflow Cm consists of a set of flows Fm . For each m and each port pair (i, j) with 1 ≤ i, j ≤ N , the flow fm (i, j) ∈ Fm represents traffic from ingress port i to egress port j with data size dm (i, j). Accordingly, Cm is represented by an N × N demand matrix Dm = [dm (i, j)]1≤i,j≤N . C. Reconfiguration Mechanism Due to the circuit-switching nature of OCS, each core k establishes a one-to-one matching between ingress and egress ports at any given time. Formally, a feasible circuit
configuration corresponds to a matching in the bipartite graph induced by ingress and egress ports, ensuring that each port participates in at most one active circuit. Circuit reconfiguration incurs a fixed delay δ. During the reconfiguration process, the ports involved in the circuit change are unavailable for data transmission.
2 0 8 3 5 0 5 2 4
Coflow Demand Matrix
Ing.1
Egr.1
Egr.3
Egr.3
Egr.3 .3
Ing.2
Egr.2
Egr.1
Egr.2
.1
Ing.3
Egr.3
Egr.2
Egr.1
Idle Circuit
Egr.1 Time
(a) Circuit Scheduling in all-stop Model
Reconfiguration Delay Circuit Scheduling
Egr.3
Ing.1
Egr.1
Egr.3
Ing.2
Egr.2
Egr.1
Ing.3
Egr.3
Egr.2
Egr.1 Time
(b) Circuit Scheduling in not-all-stop Model
Fig. 3: Circuit Reconfiguration Models in an OCS Core The circuit configuration evolves according to one of two standard reconfiguration models: all-stop or not-all-stop, as illustrated in Fig. 3. In the all-stop model (Fig. 3(a)), reconfiguration is synchronous: whenever the configuration changes, all ongoing transmissions are suspended. This model is conceptually simple and is often associated with preemptive scheduling. However, global suspension may introduce unnecessary port idleness and reduce resource utilization. In contrast, the not-all-stop model (Fig. 3(b)) allows asynchronous reconfiguration, where only ports participating in the circuit update are interrupted, while other established circuits continue transmitting. Thus, transmissions on unaffected circuits can proceed uninterrupted, whereas only the updated ports incur the reconfiguration delay. In this setting, once a flow starts transmitting on a circuit, its transmission is typically non-preemptive. While the model improves link utilization and reduces unnecessary interruptions, it increases scheduling complexity due to asynchronous reconfiguration. This paper focuses on the scheduling problem under the not-all-stop reconfiguration model. D. Problem Definition Given a set of coflows M = {C1 , . . . , CM } that arrive simultaneously, each coflow Cm is represented by an N × N demand matrix Dm and is associated with a positive weight wm . We consider scheduling all flows fm (i, j) over a K-core OCS network under the asynchronous reconfiguration model. A feasible schedule consists of the following components: (i) Global Coflow Ordering. A permutation π of {1, ..., M } that specifies the global execution order of coflows. (ii) Cross-Core Flow Assignment. For each coflow Cm with k K a demand matrix Dm , determine an assignment Dm k=1 PK k k such that Dm = k=1 Dm , where Dm = dkm (i, j) 1≤i,j≤N denotes the portion of Dm assigned to core k, satisfying
PK k dkm (i, j) ≥ 0 and k=1 dm (i, j) = dm (i, j), for all 1 ≤ i, j ≤ N . (iii) Intra-Core Circuit Scheduling. For each core k and k each subflow fm (i,j) with dkm (i, j) > 0, determine a circuit k schedule Sm = i, j, tkm (i, j) that specifies the circuit k establishment time tkm (i, j) of fm (i, j). Under the not-all-stop k model, transmission of subflow fm (i, j) starts at tkm (i, j) + δ dk (i,j) k and completes at Tm (i, j) = tkm (i, j) + δ + mrk . The completion time of the portion of coflow Cm on core k is k k Tm = maxi,j Tm (i, j) and the overall coflow completion time k (CCT) is Tm = maxk Tm . Our objective is to minimize the total weighted CCT: PM min m=1 wm Tm .
port load as ρkm = max maxi dkm,i , maxj dkm,j . Further PN k k 1 dkm (i, j) > 0 and τm,j = more, define τm,i = k j=1 PN 1 d (i, j) > 0 , which denote the number of nonzero m i=1 entries in row i and column j, respectively, where 1[·] is the indicator function. k K k For a given assignment Dm , define TLB (·) as the k=1 CCT lower-bound function of the traffic assigned to core k. k For any nonzero demand matrix Dm ̸= 0N ×N , the per-core lower bound is given by k k k k TLB Dm = max max Lm,i , max Lm,j , (1) 1≤i≤N
dk
dk
E. Hardness Analysis When the reconfiguration delay δ = ∞, scheduling a single coflow in a single-core OCS network reduces to the nonpreemptive open-shop scheduling problem with the objective of minimizing the makespan, which is NP-hard [36]. Moreover, even for a two-port OCS network, the singlecoflow scheduling problem remains NP-hard for any finite reconfiguration 0 < δ < ∞ [19]. The multi-core OCS scheduling problem considered in this paper strictly generalizes the single-core case. In particular, any single-core instance can be embedded into a K-core network by assigning all traffic to one designated core and leaving the remaining cores idle. Hence, single-coflow scheduling in multi-core OCS networks is NP-hard. Furthermore, the multicoflow problem is also NP-hard since it strictly generalizes the single-coflow setting as a special case when M = 1. IV. M ULTI -C ORE C OFLOW S CHEDULING In this section, we develop an approximation algorithm for multi-coflow scheduling in multi-core OCS networks under the not-all-stop reconfiguration model and establish a provable approximation ratio. We start by deriving the lower bound on the coflow completion time (CCT), which characterizes the minimum possible completion time in a heterogeneous multicore OCS network, to guide algorithm design and performance analysis. A. Derivation of the Lower Bound Consider a coflow Cm with demand matrix Dm = dm (i, j) 1≤i,j≤N . Define the i-th ingress load and j-th PN egress load of Dm as dm,i = j=1 dm (i, j) and dm,j = PN d (i, j), respectively. Then, define theomaximum port i=1 m n load as ρm = max maxi dm,i , maxj dm,j . In a K-core OCS network, let rkPdenote the per-port transmission rate of K core k, and let R = k=1 rk denote the aggregated port rate. k K 1) Per-core Lower Bound: Let {Dm }k=1 be any asPK k k signment such that D = D , where Dm = m m k=1 k dm (i, j) 1≤i,j≤N denote the portion of Dm assigned to core k. For each core k, define the per-port loads dkm,i = PN k PN k k j=1 dm (i, j), dm,j = i=1 dm (i, j), and the maximum
1≤j≤N
k k + τm,i δ and Lkm,j = rm,j + τm,j δ. where Lkm,i = rm,i k k The per-core lower bound is derived from the port exclusivity and reconfiguration delay constraints. Since each port can participate in at most one circuit at a time, the ingress port i requires at least dkm,i /rk transmission time. Moreover, each nonzero flow incident to that port requires a circuit k establishment, introducing at least τm,i δ total reconfiguration delay. The same argument applies to each egress port j. k 2) Global Lower Bound: Note that TLB (·) depends on the k K specific flow assignment {Dm }k=1 , which is determined by the scheduling algorithm. To derive an approximation ratio against the optimal schedule, we therefore require a global lower bound that depends only on the original demand matrix Dm and network parameters, independent of any particular assignment and schedule. Define TLB (·) as the global CCT lower-bound function of the traffic. Let TLB (Dm ) denote the global lower bound of coflow Cm . For any demand matrix Dm ̸= 0N ×N , we obtain
TLB (Dm ) = δ +
ρm . R
(2)
k k denote the completion time of the portion of Dm Let Tm coflow Cm assigned to core k. Lemma 1 (Global Lower Bound). In a K-core OCS network, for any coflow Cm with demand matrix Dm , the completion time of any feasible schedule satisfies Tm ≥ TLB (Dm ) = δ + ρRm . Proof: The per-core lower bound (Eq. (1)) can be relaxed as (
) maxi dkm,i maxj dkm,j ≥ max + δ, +δ rk rk ρk 1 + δ. = k max max dkm,i , max dkm,j + δ = m i j r rk (3) k k Since any feasible schedule kon core k satisfies Tm Dm ≥ k k k TLB Dm and Tm = maxk Tm Dm , we obtain k TLB
k Dm
ρk k k Tm ≥ max TLB . Dm ≥ δ + max m k k rk
(4)
Using the fact that the maximum is no smaller than the weighted average, hence PK k ρkm PK k ρkm k=1 r · r k k=1 ρm max k ≥ P = . (5) K k k r R k=1 r Finally, let p∗ be a port (ingress or egress) P attaining the K maximum load in Dm , so that ρm = dm,p∗ = k=1 dkm,p∗ . Since ρkm = maxdkm,p ≥ dkm,p∗ , for each k, we have p
K X k=1
ρkm ≥
K X
dkm,p∗ = ρm .
(6)
k=1
Combining the above inequalities yields ρm Tm ≥ δ + = TLB (Dm ) . R This completes the proof.
•
Work-Conserving: When there are no higher-priority flows on a port pair, lower-priority flows can be processed, thus ensuring that no allowed port pair is unnecessarily idle.
Algorithm 1 Multi-coflow Scheduling in Multi-Core OCS Networks M Input: demand matrices {Dm = [dm (i, j)]}m=1 ; weights k K M {wm }m=1 ; core rates r k=1 ; reconfiguration delay δ oM n k and Output: global order π, assignments Dπ(m) m=1 oM n k for all cores schedules Sπ(m) m=1
(7)
B. Approximation Algorithm Algorithm 1 consists of three components: (i) global coflow ordering, (ii) cross-core flow assignment, and (iii) intra-core circuit scheduling. The algorithm is designed based on the perk core lower bound TLB (·) and the global lower bound TLB (·). 1) Global Coflow Ordering: We compute a global permutation π over all coflows and enforce it consistently across all cores. Each coflow Cm is assigned a priority score wm /TLB (Dm ), where TLB (Dm ) captures a fundamental lower bound on the minimum completion time of Cm in the multicore network. Coflows are then ordered in non-increasing order of this score. This rule favors coflows with high weights and low inherent service requirements, approximating the weighted shortest-processing-time (WSPT) principle. 2) Cross-Core Flow Assignment: Coflows are processed sequentially according to π. Each flow is assigned entirely to a single core, and flow splitting is prohibited to avoid packet reordering, buffering overhead, and additional controlplane complexity in practical multi-core OCS deployments [27], [32]. Restricting assignment to the flow granularity preserves analytical tractability while maintaining practical implementability. For each flow fπ(m) (i, j), we select the core that yields the minimum per-core prefix lower bound after assignment, thereby controlling the growth of the maximum prefix lower bound across cores. The assignment order of flows within a coflow does not affect the approximation guarantee. In practice, assigning larger flows earlier may help reduce their impact on the final coflow completion time (CCT). 3) Intra-Core Circuit Scheduling: After assignment, each core schedules its assigned traffic independently while respecting the global order π. The per-core circuit scheduling policy satisfies the following properties: • Port-Exclusive: Each ingress and egress port participates in at most one active circuit at any time, satisfying the one-to-one port matching constraint of OCS. • Non-Preemptive: Once a flow starts transmission, it proceeds to completion without interruption, avoiding additional reconfiguration overhead.
▷ COFLOW ORDERING 1: for m = 1 to M do 2: sm ← wm /TLB (Dm ), ▷ TLB (Dm ) = δ + ρm /R 3: end for 4: π (1 : M ) ← Sort coflows in non-increasing order of sm ▷ FLOW ASSIGNMENT k 5: Initialize D1:0 ← 0N ×N for all k = 1, . . . , K 6: for m = 1 to M do k k 7: Initialize D1:m ← D1:m−1 for all k = 1, . . . , K k 8: Initialize Dπ(m) ← 0N ×N for all k = 1, . . . , K 9: Fπ(m) = fπ(m) (i, j) | dπ(m) (i, j) > 0 10: Sort Fπ(m) in non-increasing order of dπ(m) (i, j) 11: for each flow fπ(m) (i, j) in Fπ(m) do k k 12: k ∗ ← argmink TLB D1:m ⊕ dπ(m) (i, j) 13: Assign the entire flow fπ(m) (i, j) to core k ∗ k∗ k∗ 14: Dπ(m) = Dπ(m) ⊕ dπ(m) (i, j) ∗ k k∗ 15: D1:m ← D1:m ⊕ dπ(m) (i, j) 16: end for 17: end for ▷ CIRCUIT SCHEDULING 18: for k = 1 to K do 19: for m = 1 to M do k 20: Sπ(m) ←∅ 21: end for o SM n k 22: F k = m=1 fπ(m) (i, j) | dkπ(m) (i, j) > 0 ▷ follow the global order π 23: while F k ̸= ∅ do k 24: for each fπ(m) (i, j) ∈ F k do 25: if both ingress i and egress j are idle then k Tπ(m) (i, j) ← tkπ(m) (i, j) + δ + k ▷ tπ(m) (i, j) ← earliest feasible time k 27: Add i, j, tkπ(m) (i, j) to Sπ(m) k 28: Remove fπ(m) (i, j) from F k 29: end if 30: end for 31: end while 32: end for
26:
dk π(m) (i,j) rk
The algorithm operates as follows. First, the global coflow priority order is determined (Lines 1-4). For each coflow Cm , we compute a priority score sm = wm /TLB (Dm ) (Line 2), where TLB (Dm ) = δ + ρm /R is the minimum possible
processing time of Cm when scheduled alone on the multicore network. Coflows are then sorted in non-increasing order of sm to obtain the global execution order π(1 : M ) (Line 4). Next, the algorithm enters the flow assignment phase (Lines 5-17). For each core maintain a prefix-aggregated Pm k, we k k matrix D1:m = D ℓ=1 π(ℓ) representing the aggregated traffic assigned to core k from the first m coflows under k π. D1:0 is initialized for each core k (Line 5). Then, for each coflow Cπ(m) processed in order (Line 6), we initialize k k D1:m ← D1:m−1 for all k (Line 7), meaning that each core inherits the prefix load contributed by the previous m − 1 coflows before assigning any flow of Cπ(m) . We also initialize k the per-core assignment matrices Dπ(m) to zero (Line 8). Let Fπ(m) denote the set of nonzero flows in Cπ(m) (Line 9), which is sorted in non-increasing order of size (Line 10). For each flow fπ(m) (i, j) ∈ Fπ(m) (Line 11), we tentatively k places it on every core k by forming D1:m ⊕ dπ(m) (i, j), k which increases the (i, j) entry of D1:m by dπ(m) (i, j), k i.e., D1:m + dπ(m) (i, j) Eij , where Eij ∈ RN ×N is the standard basis matrix whose (i, j)-th entry equals 1. It then k k selects k ∗ ← argmink TLB D1:m ⊕ dπ(m) (i, j) (Line 12), i.e., the core that yields the smallest per-core lower bound after adding this flow. The entire flow is assigned to core k ∗ k∗ k∗ (Line 13), and both Dπ(m) and D1:m are updated accordingly (Lines 14-15). After all flows of Cπ(m) are assigned, the n oK k matrices Dπ(m) constitute its cross-core assignment, k=1 k K and D1:m k=1 are used for the next coflow. After assignment, circuit scheduling is performed independently on each core (Lines 18–32). For each core k k, we first initialize the circuit schedule Sπ(m) for all coflowsn (Lines 19-21). We then construct the set F k = o SM k k m=1 fπ(m) (i, j) | dπ(m) (i, j) > 0 , which contains all flows assigned to core k (Line 22). The scheduling process respects the global order π. While F k is non-empty (Line 23), the scheduler scans the flows in F k according to π (Line k 24), and selects flow fπ(m) (i, j) sequentially whose ingress port i and egress port j are both idle (Line 25). Such a flow is scheduled at the earliest feasible time when both ports k become available, and its completion time is Tπ(m) (i, j) ← dk (i,j) (Line 26). The scheduled flow is tkπ(m) (i, j) + δ + π(m) rk k then recorded in Sπ(m) (Line 27) and removed from F k (Line
28). C. Analysis of Performance Guarantees 1) Derivation of Assignment-Phase Prefix Bound: Let π denote the global coflow order produced by the ordering phase of Algorithm 1. For any m ∈ {1, . . . , M }, define the prefix-aggregated demand matrix D1:m = P m k Dπ(ℓ) , and for each core k ∈ {1, . . . , K}, D1:m = Pℓ=1 P m N k Dπ(ℓ) . Let d1:m,i = j=1 d1:m (i, j) and d1:m,j = Pℓ=1 N d (i, j) denote the row and column loads of i=1 1:m D1:m = d1:m (i, j) 1≤i,j≤N , respectively, and define the maximum port load ρ1:m = max {maxi d1:m,i , maxj d1:m,j }. PN Let τ1:m,i = = j=1 1 [d1:m (i, j) > 0] and τ1:m,j
PN
i=1 1 [d1:m (i, j) > 0] denote the number of nonzero entries in row i and column j of D1:m , respectively, where 1[·] is the indicator function. Define the maximum number of nonzero entries in any row or column of D1:m as τ1:m = max {maxi τ1:m,i , maxj τ1:m,j }. Let rmax = maxk rk .
Lemma 2 (Assignment-Phase Prefix Bound). m = kFor any K 1, . . . , M , the prefix-aggregated matrices D1:m k=1 produced by the assignment phase of Algorithm 1 satisfy ρ1:m k k maxk TLB D1:m ≤ rmax + τ1:m δ. Proof: Consider any non-empty core k1 after processing the first m coflows. Let f¯k1 (i, j) be the last flow assigned to core k1 during the assignment of the first m coflows, and let d¯k1 (i, j) denote its size. Let D̄k1 be the aggregate demand matrix on core k1 immediately before assigning f¯k1 (i, j). Then, the final aggregate demand on core k1 is k1 = D̄k1 ⊕ d¯k1 (i, j) . D1:m
(8)
Algorithm 1 assigns each flow greedily to the core with the minimum per-core prefix lower bound. Therefore, when f¯k1 (i, j) was assigned, for any other core k2 , k1 k2 D̄k1 ⊕ d¯k1 (i, j) ≤ TLB TLB D̄k2 ⊕ d¯k1 (i, j) , (9) where D̄k2 denotes the aggregate matrix on core k2 at that time. k By the monotonicity of TLB (·), we can easily obtain k2 k2 TLB D̄k2 ⊕ d¯k1 (i, j) ≤ TLB (D1:m ) . (10) Combining the above inequalities yields, for any k2 k1 k1 k2 TLB D1:m ≤ TLB (D1:m ) , k1 k1 k1 where TLB D1:m = TLB D̄k1 ⊕ d¯k1 (i, j) . Since Eq. (11) holds for all k2 , we have k1 k1 k TLB D1:m ≤ min TLB (D1:m ) . k
(11)
(12)
Because k1 is an arbitrary non-empty core, taking the maximum over k gives k k k max TLB D1:m ≤ min TLB (D1:m ) . (13) k
k
k Finally, by the definition of TLB (·) (Eq. (1)), applied to the matrix D1:m , we can get k TLB (D1:m ) = max max L1:m,i , max L1:m,j i j (14) ρ1:m ≤ k + τ1:m δ, r d
d
where L1:m,i = 1:m,i +τ1:m,i δ and L1:m,j = 1:m,j +τ1:m,j δ. rk rk 1 Taking the minimum over k and using mink r1k = rmax yields ρ 1:m k k max TLB D1:m ≤ min + τ δ 1:m k k rk (15) ρ1:m ≤ + τ1:m δ. rmax This completes the proof.
2) Derivation of Scheduling-Phase Prefix Bound: Let Tπ(m) denote the final CCT of Cπ(m) under Algorithm 1. Define the lower bound k k TLB D1:m = max maxi Lk1:m,i , maxj Lk1:m,j , where Lk1:m,i =
dk dk 1:m,i k k δ and Lk1:m,j = 1:m,j δ. + τ1:m,i + τ1:m,j rk rk
Lemma 3 (Scheduling-Phase Prefix Bound). For any m ∈ {1, . . . , M }, the completion time of coflow Cπ(m) satisfies k k k Tπ(m) = maxk Tπ(m) ≤ 2 maxk TLB D1:m . k Proof: Consider any core k for which Dπ(m) ̸= 0, i.e., coflow Cπ(m) has at least one nonzero flow on core k. Let (i⋆ , j ⋆ ) be the port-pair corresponding to the last completed flow of Cπ(m) on core k, and denote its size by d⋆ = dkπ(m) (i⋆ , j ⋆ ) > 0. Let t⋆ = tkπ(m) (i⋆ , j ⋆ ) be the k circuit establishment time of fπ(m) (i⋆ , j ⋆ ). Under not-all-stop k ⋆ ⋆ reconfiguration, the flow fπ(m) (i , j ) starts transmission at time t⋆ + δ and completes at k Tπ(m) (i⋆ , j ⋆ ) = t⋆ + δ +
d⋆ . rk
(16)
Since (i⋆ , j ⋆ ) corresponds to the last completed flow of Cπ(m) on core k, the completion time of Cπ(m) on core k satisfies k k k Tπ(m) = maxTπ(m) (i, j) = Tπ(m) (i⋆ , j ⋆ ) . i,j
Combining the transmission and reconfiguration bounds yields dk1:m,i⋆ − d⋆ k + τ1:m,i (18) ⋆ − 1 δ. rk By the same argument for the egress port j ⋆ , we obtain Bi⋆ (t⋆ ) ≤
dk1:m,j ⋆ − d⋆ k + τ1:m,j (19) ⋆ − 1 δ, rk PN k k where dk1:m,j ⋆ = d (i, j ⋆ ) and τ1:m,j = ⋆ k i=1 1:m PN ⋆ 1 d (i, j ) > 0 . 1:m i=1 k Since the flow fπ(m) (i⋆ , j ⋆ ) can be transmitted only when ⋆ ⋆ both port i and j are idle, we have Bj ⋆ (t⋆ ) ≤
t⋆ ≤ Bi⋆ (t⋆ ) + Bj ⋆ (t⋆ ) dk1:m,i⋆ + dk1:m,j ⋆ − 2d⋆ k k + τ1:m,i ⋆ + τ1:m,j ⋆ − 2 δ. k r (20) Combining Eq. (20) with Eq. (16) and Eq. (17) gives ≤
d⋆ rk dk1:m,i⋆ + dk1:m,j ⋆ k k + τ1:m,i ≤ ⋆ + τ1:m,j ⋆ δ. k r Therefore, we can get k Tπ(m) = t⋆ + δ +
dk1:m,i⋆ k k k + τ1:m,i ⋆ δ ≤ TLB D1:m , k r
(17)
Consider the scheduling policy on core k, which is portexclusive, non-preemptive, and work-conserving, and respects the global priority order π. For any time t < t⋆ , at least one of the two ports i⋆ and j ⋆ must be busy. Let Bi⋆ (t⋆ ) and Bj ⋆ (t⋆ ) denote the total busy times of ports i⋆ and j ⋆ over the interval [0, t⋆ ), respectively. We now upper bound Bi⋆ (t⋆ ). Let dk1:m,i⋆ = PN k ⋆ ⋆ load on port i at core j=1 d1:m (i , j) be the prefix k PN k ⋆ k, and let τ1:m,i = 1 d ⋆ 1:m (i , j) > 0 denote the j=1 number of distinct nonzero port pairs incident to i⋆ in the k prefix matrix D1:m . Port i⋆ can be busy during the interval ⋆ [0, t ) due to two causes: (1) Transmission busy time bound on i⋆ . Before the circuit ⋆ ⋆ (i , j ) is established, any transmission incident to i⋆ must k , correspond to a nonzero entry in the prefix matrix D1:m k ⋆ ⋆ and cannot include the transmission of the flow fπ(m) (i , j ) itself. Hence, the total amount of prefix data that can be transmitted through port i⋆ before t⋆ is at most dk1:m,i⋆ − d⋆ . Since the per-port rate is rk , the total transmission busy time ⋆ dk ⋆ −d on i⋆ before t⋆ is bounded by 1:m,irk . (2) Reconfiguration busy time bound on i⋆ . Port i⋆ is k k incident to at most τ1:m,i ⋆ distinct nonzero port pairs in D1:m . ⋆ ⋆ ⋆ Since (i , j ) is the pair established at time t , there can be k ⋆ at most τ1:m,i prior ⋆ − 1 circuit establishments involving i ⋆ to t . Each such establishment incurs a delay δ on the ports involved. Therefore, the total circuit establishment time on i⋆ ⋆ k before t is is bounded by τ1:m,i⋆ − 1 δ.
(21)
(22)
and
dk1:m,j ⋆ k k k + τ1:m,j (23) ⋆ δ ≤ TLB D1:m . k r Combining the above inequalities with Eq. (21), we obtain k k k Tπ(m) ≤ 2TLB D1:m . (24)
Finally, taking the maximum over all cores yields k k k Tπ(m) = max Tπ(m) ≤ 2 max TLB D1:m . k
k
(25)
This completes the proof. 3) Derivation of Deterministic Approximation Ratio: ∗ Let Tm denote the optimal completion time of Cm in an optimal schedule. and let wmax = maxm wm and wminn= minm wm . Define τmax = maxm τm , where τm = o P P max maxi j 1 [dm (i, j) > 0] , maxj i 1 [dm (i, j) > 0] . max Theorem 1. Algorithm 1 achieves a 2M w wmin ψ-approximation for minimizing the weighted CCT inPa multi-core OCS network, PM M ∗ max i.e., m=1 wm Tm ≤ 2M w m=1 wm Tm , where ψ = wmin ψ max {K, τmax } and τmax ≤ N , where N is the number of ingress/egress ports per core.
Proof: Relabel the coflows according to the execution order π, so that C1 , . . . , CM follow the order produced by Algorithm 1. For each m, combining Lemma 2 and Lemma 3 yields ρ1:m + τ1:m δ . (26) Tm = Tπ(m) ≤ 2 rmax
Multiplying both sides by wm and summing over m gives M M X X ρ1:m wm Tm ≤ 2 wm + τ1:m δ . (27) rmax m=1 m=1 Pm Pm Using ρ1:m ≤ s=1 ρs and τ1:m ≤ s=1 τs , we obtain M X
wm Tm ≤ 2
m=1
M X
wm
m=1
=2
m X ρs
s=1
≤ 2wmax
rmax M X
+ τs δ
rmax
s=1
M X ρs
+ τs δ
X M
wm
m=s
(M − m + 1)
m=1
PM ≤ 2M wmax
m=1 ρm
ρm + τm δ rmax !
+ M δτmax
rmax
.
(28) By Lemma 1, for every coflow Cm , the optimal completion ∗ ≥ TLB (Dm ) = δ + ρRm . Thus time of Cm satisfies Tm M X
M X
ρm ∗ wm δ + wm Tm ≥ R m=1 m=1 ! PM m=1 ρm ≥ wmin M δ + . R
Consider an H-core EPS network, where each core h ∈ {1, ..., H} provides per-port rate rh . The total PH transmission h aggregated rate is R = h=1 r , and rmax = maxh rh . Let ∗ Tem denote the completion time of coflow Cm in an optimal schedule for the multi-core EPS network. For any demand ρhm h h matrix Dm , the per-core EPS lower bound is TeLB Dm = rh , ∗ and the global EPS lower bound is Tem ≥ TeLB (Dm ) = ρRm , where ρhm and ρm denote the maximum ingress/egress port h loads of Dm and Dm , respectively [27]. Theorem 2. The EPS variant of Algorithm 1 achieves max the weighted a 2M w wmin H-approximation for minimizing PM e CCT in a multi-core EPS network, i.e., m=1 wm Tm ≤ wmax PM ∗ e 2M H wmin m=1 wm Tm . Proof: The algorithm retains the same scheduling framework as in the OCS case. We remove the reconfiguration k delay δ and replace the OCS-specific lower bounds TLB (·) and h TLB (·) by the EPS lower bounds TeLB (·) and TeLB (·). Following the same prefix-based analysis, we obtain the completion time of coflow Cm ρ1:m h h . D1:m ≤2 Tem ≤ 2 max TeLB h rmax
(31)
wmax R wmax m=1 wm Tm ≤ 2M · ≤ 2M H . ∗ e w r wmin min max w T m=1 m m
(32)
(29)
Finally PM
e
PM Combining the above bounds yields PM
PM
wmax m=1 wm Tm · ≤ 2M PM ∗ wmin m=1 wm Tm
m=1 ρm
rmax PM
wmax max wmin wmax ≤ 2M ψ, wmin ≤ 2M
This completes the proof. Based on Theorem 2, we can further derive the following corollaries.
+ M δτmax
m=1 ρm
+ Mδ R , τmax
R
(30)
rmax
R ≤ K and τmax ≤ N . where ψ = max {K, τmax }, rmax This completes the proof. Based on Theorem 1, we immediately derive the following corollaries.
Corollary 1. In the unweighted case (i.e., wmax = wmin ), Algorithm 1 is 2M ψ-approximation for minimizing PM the total CCT in a multi-core OCS network, i.e., m=1 Tm ≤ PM ∗ 2M ψ m=1 Tm , where ψ = max {K, τmax }. Corollary 2. In the single-coflow case (i.e., M = 1), Algorithm 1 is 2ψ-approximation for minimizing the CCT in a multi-core OCS network, i.e., T ≤ 2ψT ∗ , where ψ = max {K, τmax }. In fact, Algorithm 1 can be directly applied to a multicore EPS network by replacing the OCS-specific lower bounds k TLB (·) and TLB (·) while ignoring reconfiguration delay δ. The corresponding approximation guarantees and detailed proofs are as follows.
Corollary 3. In the unweighted case (i.e., wmax = wmin ), the EPS variant of Algorithm 1 is 2M H-approximation for minimizing the unweighted P CCT in a multi-core EPS Ptotal M M ∗ . network, i.e., m=1 Tem ≤ 2M H m=1 Tem Corollary 4. In the single-coflow case (i.e., M = 1), the EPS variant of Algorithm 1 is 2H-approximation for minimizing the CCT in a multi-core EPS network, i.e., T ≤ 2HT ∗ . In addition to the worst-case approximation ratio charactermax ized by the conservative factor M w wmin , we further derive two refined approximation guarantees in multi-core OCS networks. Specifically, we establish (i) a deterministic approximation ratio characterized by the weight concentration parameter, and (ii) an expected approximation ratio under a normally distributed weight model. The detailed proofs are deferred to the Appendix. V. E XPERIMENTAL E VALUATIONS In this section, we evaluate the performance of the proposed Algorithm 1 using the Facebook trace [37]. We first describe the experimental setup, and then present detailed performance results and analysis.
SUNFLOW-CORE Replace the per-core circuit scheduling module with the single-core scheduler Sunflow [19] under the not-all-stop model. The global order and crosscore assignment follow Algorithm 1. • RAND-SUNFLOW Replace the cross-core flow assignment with randomized core selection (rate-proportional), and schedule the traffic on each core using Sunflow. The global coflow order remains the same as in Algorithm 1.
A. Experimental Setup
B. Baseline Solutions Since there is no existing multi-coflow scheduler tailored to multi-core OCS networks under the not-all-stop reconfiguration model, we construct representative baselines by ablating or replacing key components of Algorithm 1 (O URS). We consider the following baselines: • RHO-ASSIGN Replace the τ -aware cross-core flow assignment with a ρ-only policy that assigns each flow to the core minimizing ρk1:m /rk , i.e., ignoring the reconfigk δ; the global coflow order and per-core uration term τ1:m scheduling remain the same as Algorithm 1. • RAND-ASSIGN Replace the cross-core flow assignment with randomized core selection, assigning each flow to core k with probability proportional to rk . The global coflow order and per-core scheduling remain the same as Algorithm 1.
We first conduct an ablation study under the default setting to understand the contribution of each component in Algorithm 1. We then vary key system parameters, including the number of OCS cores K and the corresponding per-core rate vector, the number of ports N , the number of coflows M , and the reconfiguration delay δ, to examine how the performance gap changes with network size, workload intensity, and reconfiguration overhead. 1) Ablation under the Default Setting: Fig. 4 reports the normalized total weighted CCT and normalized tail CCT (p95/p99) under the default setting, where all results are normalized to O URS. Compared with O URS, RHO-ASSIGN incurs 1.64× higher total weighted CCT and approximately 1.67× higher tail CCT, indicating that ignoring reconfiguration overhead in cross-core assignment leads to significantly inferior placements. RAND-ASSIGN performs slightly better than RHO-ASSIGN, but still yields 1.31× that of O URS. The performance gap widens drastically when replacing the corelevel circuit scheduler with Sunflow (SUNFLOW-CORE), where the normalized total weighted CCT increases to 2.64× and the normalized tail CCT surges to nearly 4×. The worst case is RAND-SUNFLOW, with 3.03× total weighted CCT and about 4.7× tail CCT. Rates=[10.0, 20.0, 30.0], =8.0 3 2 1 0
Rates=[10.0, 20.0, 30.0], =8.0 Norm. Tail CCT
where O URS denotes Algorithm 1. Hence, NormW (O URS) = 1 by definition, and larger values indicate worse performance relative to O URS. In addition, we report tail CCT metrics (p95/p99) to evaluate the long-tail performance. Default Parameters. Unless otherwise specified, we use the following default settings: (i) number of ingress/egress ports N = 16; (ii) number of coflows M = 100, randomly sampled from the trace; (iii) number of cores K = 3; (iv) core rate vector [10, 20, 30]; (v) aggregated port rate R = 60; and (vi) reconfiguration delay δ = 8.
C. Experimental Results
Norm. Total Weighted CCT
This subsection describes the workload, evaluation metrics, and default parameter settings. Workload: We utilize the widely adopted Facebook trace [37], collected from a MapReduce cluster comprising 3000 machines and 150 racks. This dataset has been extensively employed in prior coflow scheduling research [11], [12], [18], [19], [21], [23], [27]. The trace contains 526 coflows, which are typically simplified into a 150-port network while preserving the original arrival interval pattern. Each coflow records the set of receivers, the number of bytes received, and the associated sender at the receiver level rather than the flow level. To construct the N × N demand matrix for each coflow, we convert receiver-level demands into sender-receiver flows as follows. For each receiver, the total received bytes are pseudouniformly distributed across the associated senders, with a small random perturbation introduced to prevent perfectly uniform splitting. We then randomly select N machines from the trace as servers and map them to ingress and egress ports, thereby generating an N -port coflow instance. Performance Metrics: Our primary objective is to minimize PM the total weighted coflow completion time (CCT), m=1 wm Tm . We evaluate all schemes using the normalized total weighted CCT, defined as PM wm Tm (A) , (33) NormW (A) ≜ PM m=1 m=1 wm Tm (O URS )
•
E S N N W OUR -ASSIG -ASSIG W-COR UNFLO D O O L N H F D-S R N RA SUN A R
4
Norm. p95 Norm. p99
2 0
E S N N W OUR -ASSIG -ASSIG W-COR UNFLO D O O L N H F D-S R N RA SUN A R
Fig. 4: Normalized total weighted CCT and tail CCT (p95/p99) under the default setting for different algorithm variants. 2) Impact of Reconfiguration Delay (δ-Sensitivity): We evaluate sensitivity to reconfiguration delay by fixing N = 16 and M = 100, and varying δ ∈ {2, 4, 6, 8, 10, 12}. For each K ∈ {3, 4, 5}, we compare the imbalanced (heterogeneous) and balanced (homogeneous) core rate vectors, as shown in Fig. 5, Fig. 6 and Fig. 7. • K = 3 (Fig. 5). O URS is robust to increasing δ under both rate settings. Under imbalanced rates case, RHOASSIGN and RAND-ASSIGN incur approximately 1.4×
Norm. Total Weighted CCT
3.5
Norm. Total Weighted CCT
and 1.3× the total weighted CCT of O URS, respectively, while SUNFLOW-CORE and RAND-SUNFLOW perform substantially worse. All schemes show improved performance under balanced rates, and O URS still achieves the lowest total weighted CCT.Under balanced rates, all schemes improve, but O URS still achieves the lowest total weighted CCT.
5.0 4.5 4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5
K=5, Imbalanced Rates=[5.0, 5.0, 10.0, 15.0, 25.0] K=5, Balanced Rates=[12.0, 12.0, 12.0, 12.0, 12.0] OURS RHO-ASSIGN RAND-ASSIGN
2
4
6
8
Reconfiguration Delay
10
12
2
4
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
6
10
8
Reconfiguration Delay
12
K=3, Imbalanced Rates=[10.0, 20.0, 30.0]
K=3, Balanced Rates=[20.0, 20.0, 20.0]
Fig. 7: Normalized total weighted CCT versus reconfiguration delay δ for K = 5.
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
TABLE III: Normalized total weighted CCT versus number of ports N for K=3.
6
10
6
10
3.0 2.5 2.0 1.5 1.0 0.5
N 2
4
8
Reconfiguration Delay
12
2
4
8
Reconfiguration Delay
12
4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5
K = 4 (Fig. 6). The same trend persists with more cores. Under imbalanced rates, RHO-ASSIGN is about 1.45× to 1.75× worse than O URS, while RANDASSIGN is about 1.34× to 1.43× worse. Under balanced rates, RHO-ASSIGN ranges from 1.22× to 1.46×, and RAND-ASSIGN remains close to O URS at about 1.03×-1.06×. In contrast, SUNFLOW-CORE and RAND-SUNFLOW remain substantially worse, at about 2.78×-2.88× and 2.90×-3.07×, respectively. K=4, Imbalanced Rates=[5.0, 10.0, 20.0, 25.0]
K=4, Balanced Rates=[15.0, 15.0, 15.0, 15.0]
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
6
10
6
10
2
4
8
Reconfiguration Delay
12
2
4
8
Reconfiguration Delay
12
Fig. 6: Normalized total weighted CCT versus reconfiguration delay δ for K = 4. K = 5 (Fig. 7). Under imbalanced rates, RHOASSIGN and RAND-ASSIGN are approximately 1.42×1.73× and 1.51×-1.70× worse than O URS, respectively. SUNFLOW-CORE exhibits a much larger degradation, ranging from about 2.93× to 3.19×, while RANDSUNFLOW performs worst at about 3.90×-4.39×. Under balanced rates, SUNFLOW-CORE and RANDSUNFLOW remain substantially higher than O URS, at approximately 2.90×–3.17× and 3.14×–3.29×, respectively. 3) Impact of the Number of Ports (N -Scaling): We next evaluate scalability with respect to the fabric size under different numbers of OCS cores. Specifically, we fix the number of coflows to M = 100 and the reconfiguration delay to δ = 8, and vary the number of ports N ∈ {8, 12, 16, 24, 32} •
RA-AS
SU-CO
RA-SU
8 12 16 24 32
1.380 1.503 1.640 1.657 1.524
8 12 16 24 32
1.134 1.115 1.435 1.269 1.331
1.246 1.255 1.322 1.341 1.370
2.951 2.749 2.647 2.245 2.008
3.637 3.224 3.179 2.768 2.539
Balanced rates: [20, 20, 20] 1.049 1.044 1.063 1.023 1.038
3.060 2.682 2.640 2.195 2.055
3.167 2.770 2.792 2.327 2.151
. We consider K ∈ {3, 4, 5} with both heterogeneous and homogeneous rate configurations, as shown in Table. III, IV and V, respectively. Under different port scales, core counts, and rate vector settings (balanced/unbalanced), O URS consistently achieves the lowest total weighted CCT among all compared baselines (RH-AS, RA-AS, SU-CO and RA-SU), with the most significant advantage under heterogeneous (unbalanced) core rates. 4) Impact of the Number of Coflows (M -Scaling): We further study how the performance gap evolves as the number of coflows M increases under different numbers of OCS cores. We fix the fabric size to N = 16 and the reconfiguration delay to δ = 8, and vary the number of coflows M ∈ {50, 100, 150, 200, 250}. We report results for K ∈ {3, 4, 5} under heterogeneous (imbalanced) and homogeneous (balanced) rate vectors in Fig. 8-10. 6
Norm. Total Weighted CCT
•
RH-AS
Imbalanced rates: [10, 20, 30]
Fig. 5: Normalized total weighted CCT versus reconfiguration delay δ for K = 3.
Norm. Total Weighted CCT
SUNFLOW-CORE RAND-SUNFLOW
5
K=3, Rates=[10.0, 20.0, 30.0] (Imbalanced)
K=3, Rates=[20.0, 20.0, 20.0] (Balanced)
OURS RHO-ASSIGN RAND-ASSIGN
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
SUNFLOW-CORE RAND-SUNFLOW
4 3 2 1 0
50
100
150
200
Number of Coflows M
250
50
100
150
200
Number of Coflows M
250
Fig. 8: Normalized total weighted CCT versus number of coflows M for K = 3.
RH-AS
RA-AS
SU-CO
RA-SU
Imbalanced rates: [5, 10, 20, 25] 8 12 16 24 32
1.380 1.617 1.749 1.816 1.965
1.422 1.425 1.473 1.450 1.530
3.307 3.018 2.876 2.485 2.347
4.175 3.920 3.742 3.153 3.101
Balanced rates: [15, 15, 15, 15] 8 12 16 24 32
1.163 1.322 1.456 1.634 1.601
1.099 1.060 1.008 1.059 1.056
3.208 2.970 2.783 2.513 2.350
3.365 3.147 2.913 2.699 2.469
TABLE V: Normalized total weighted CCT versus number of ports N for K=5. N
RH-AS
RA-AS
SU-CO
RA-SU
Imbalanced rates: [5, 5, 10, 15, 25] 8 12 16 24 32
1.329 1.639 1.733 1.706 1.839
1.593 1.590 1.701 1.717 1.846
3.438 3.148 3.149 2.689 2.553
4.808 4.506 4.461 3.772 3.768
Balanced rates: [12, 12, 12, 12, 12] 8 12 16 24 32
1.192 1.367 1.586 1.684 1.611
1.162 1.113 1.095 1.052 1.033
3.381 3.194 3.052 2.680 2.462
3.616 3.413 3.294 2.898 2.641
K = 3 (Fig. 8) Under heterogeneous rates, RHO-ASSIGN and RAND-ASSIGN stay around 1.29×-1.64×, while SUNFLOW-CORE and RANDSUNFLOW grow to about 2.65×-2.75× and 2.76×3.30×. Under balanced rates, RHO-ASSIGN/RANDASSIGN move closer to O URS as M increases, reaching approximately 1.10× and 1.02× at M = 250, respectively. In contrast, SUNFLOW-CORE and RANDSUNFLOW remain significantly higher, reaching about 2.72× and 2.85× at M = 250. • K = 4 (Fig. 9) With heterogeneous rates, RHOASSIGN and RAND-ASSIGN are consistently worse than O URS by about 1.69×-1.83× and 1.38×-1.43×, respectively, while SUNFLOW-CORE and RANDSUNFLOW increase with M , reaching about 3.08× and 3.91× at M = 250. With balanced rates, RHOASSIGN decreases as M grows, down to about 1.23×, while RAND-ASSIGN becomes highly competitive, ranging from approximately 0.97× to 1.05×). However, SUNFLOW-CORE and RAND-SUNFLOW still remain substantially worse, staying around 2.53×-3.09×. • K = 5 (Fig. 10) Under heterogeneous rates [5, 5, 10, 15, 25], the gaps further widen as M increases. SUNFLOW-CORE rises from approximately 2.85× to •
Norm. Total Weighted CCT
N
6 5
K=4, Rates=[5.0, 10.0, 20.0, 25.0] (Imbalanced) OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
K=4, Rates=[15.0, 15.0, 15.0, 15.0] (Balanced) OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
4 3 2 1 0
50
100
150
200
Number of Coflows M
250
50
100
150
200
Number of Coflows M
250
Fig. 9: Normalized total weighted CCT versus number of coflows M for K = 4. 6
Norm. Total Weighted CCT
TABLE IV: Normalized total weighted CCT versus number of ports N for K=4.
5
K=5, Rates=[5.0, 5.0, 10.0, 15.0, 25.0] (Imbalanced) K=5, Rates=[12.0, 12.0, 12.0, 12.0, 12.0] (Balanced) OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
OURS RHO-ASSIGN RAND-ASSIGN
SUNFLOW-CORE RAND-SUNFLOW
4 3 2 1 0
50
100
150
200
Number of Coflows M
250
50
100
150
200
Number of Coflows M
250
Fig. 10: Normalized total weighted CCT versus number of coflows M for K = 5.
3.25×, and RAND-SUNFLOW from approximately 3.93× to 4.57×, whereas RHO-ASSIGN/RANDASSIGN remain around 1.46×-1.75× and 1.59×1.68×. With balanced rates, RHO-ASSIGN and RAND-ASSIGN move closer to O URS as M grows (down to about 1.18× and 1.02×), while SUNFLOWCORE and RAND-SUNFLOW still increase to about 3.29× and 3.46× at M = 250. VI. C ONCLUSIONS This paper investigates the multi-coflow scheduling problem in multi-core data center networks, focusing particularly on multiple OCS cores operating in parallel under the not-allstop (asynchronous) reconfiguration model. In this scenario, the scheduler must jointly account for (i) the coupled capacity constraints across heterogeneous OCS cores due to cross-core traffic assignment and (ii) the intra-core feasibility constraints induced by port exclusivity and asynchronous reconfiguration delay. We develop an approximation algorithm for minimizing the total weighted coflow completion time (CCT) and establish a global worst-case performance guarantee. Specifically, in a K-core N × N OCS network, our algorithm achieves max a 2M w wmin max {K, τmax }-approximation where M is the number of coflows, wmax and wmin are the maximum and minimum coflow weights, respectively, and τmax ≤ N captures the maximum coflow traffic intensity across cores. This bound explicitly characterizes how OCS core parallelism (K) and coflow structure (τmax ) affect worst-case performance. Furthermore, the same framework can be directly applied to multi-core EPS networks by replacing the OCS-specific
lower bounds and setting the reconfiguration delay to zero, max yielding a 2M w wmin H-approximation scheduler, where H is the number of EPS cores. Extensive trace-driven simulations further demonstrate that our method consistently reduces the weighted CCT compared to all baselines. A promising direction for future work is online scheduling in multi-core OCS networks, where coflows arrive over time, and their demand matrices may be only partially observed. key objective is to develop online policies with provable competitive ratios that can characterize and balance robustness, reconfiguration efficiency, and performance under uncertainty, thereby providing theoretical foundations for designing practical system policies. A PPENDIX A. Deterministic Approximation Ratio via Weight Concentration Parameter We refine the worst-case approximation bound by characterizing itPin terms of the weight concentration parameter M w2 Γw = M PMm=1 m2 , where w1 , . . . , wM > 0 are arbitrary
Proof: Rewrite the left-hand side by swapping the summation order: M m M M X X X X wπ(m) aπ(s) = aπ(s) wπ(m) . (37) m=1
s=1
Using the given condition that aπ(s) ≤ ψTLB Dπ(s) for all s, we substitute this upper bound into Eq. (37): M X
aπ(s)
s=1
M X
M M X X wπ(m) ≤ ψ TLB Dπ(s) wπ(m) .
m=s
s=1
m=s
s=1
m=s
(38) Based on the Cauchy–Schwarz inequality and a standard convexity argument, the ratio between the weighted prefix sum and the weighted lower bound sum is maximized when the weight distribution is most concentrated (i.e., when a single weight dominates). This maximum ratio is formally captured by Γw . Applying the concentration factor yields the desired result: M M m M X X X X wπ(m) wπ(m) aπ(s) ≤ ψ TLB Dπ(s) m=1
s=1
m=1 wm
weights. This yields a deterministic approximation guarantee that depends explicitly on the dispersion of coflow weights max rather than solely on the ratio w wmin . Lemma 4 (Relaxed Global Lower Bound). For every coflow ∗ ∗ Cm , the optimal completion time Tm satisfies Tm ≥ ρm TLB (Dm ) = δ + R (Lemma 1), we can further obtain m TLB (Dm ) ≥ ψ1 rρmax + τm δ , where ψ = max {K, τmax }. Proof: Since the aggregated port rate R satisfies R=
K X
rk ≤ Krmax ≤ ψrmax .
m . Moreover, because τm ≤ We can obtain ρRm ≥ ψrρmax τm τmax ≤ ψ, we have δ ≥ ψ δ. Hence
δ+
ρm τm ρm ≥ δ+ R ψ ψrmax ρm 1 + τm δ . = ψ rmax
Finally ρm 1 TLB (Dm ) = δ + ≥ R ψ
ρm + τm δ . rmax
(36)
This completes the proof.
(39) This completes the proof. Now we are ready to state a deterministic approximation guarantee in terms of Γw and explicitly track the factor ψ = max {K, τmax }. Theorem 3. ForP any non-negative weights 1 , . . . , wM , AlgoPw M M ∗ rithm 1 satisfies w T ≤ 2ψΓ m m w m=1 m=1 wm Tm , where PM 2 w Γw = M PMm=1 m2 and ψ = max {K, τmax }. m=1 wm
Proof: Similarly, under the execution order π and reindex the coflows accordingly as C1 , . . . , CM . According to Eq. (28), we have ! M M M X X X wm Tm ≤ 2 as wm , (40) m=s
s=1
ρs
where as = rmax + τs δ. By Lemma 3, for each s we have ρ a 1 s s TLB (Ds ) ≥ + τs δ = . (41) max {K, τmax } rmax ψ Hence, as ≤ ψTLB (Ds ). According to Lemma 5, we can obtain ! ! M M M M X X X X as wm ≤ ψ TLB (Ds ) wm s=1
Lemma 5 (Weighted Prefix Bound via Γw ). Suppose that for each coflow Cm , there exists a per-coflow lower bound TLB (Dm ) such that am ≤ ψTLB (Dm ), for m = 1, . . . , M , where ψ = max {K, τmax }. Then, for any permutation π P of {1, . . . , M }, PM m the inequality holds: w a ≤ m=1 π(m) s=1 π(s) PM Γw ψ m=1 wπ(m) TLB Dπ(m) .
wπ(m) TLB Dπ(m) .
m=1
m=1
(35)
M X
≤ Γw ψ
(34)
k=1
m=s
s=1
m=s
m=s
s=1 M X
≤ ψΓw
(42)
wm TLB (Dm ) .
m=1
Substituting Eq. (42) back to Eq. (40), we obtain M X m=1
wm Tm ≤ 2ψΓw
M X m=1
wm TLB (Dm ) .
(43)
∗ Finally, since TLB (Dm ) ≤ Tm for all m, we get M X
wm Tm ≤ 2ψΓw
m=1
M X
∗ wm Tm .
(44)
m=1
E[Γw ] → 1 +
This completes the proof. B. Expected Approximation Ratio under A Normal Distribution Weight Model We next consider a stochastic weight model and analyze the expected approximation ratio. Specifically, we assume that the weights are independent and identically distributed according to a normal distribution. Assumption 1 (Normal Weight Model). The coflow weights i.i.d. are random variables w1 , w2 , . . . , wM ∼ N µ, σ 2 with 2 = µ > 0 and σ 2 > 0. Hence, E [wm ] = µ and E wm 2 2 µ +σ . In implementations, negative weights can be truncated if needed; when µ ≫ σ, the probability of negative weights is negligible and such truncation does not affect the asymptotic analysis. The following lemma characterizes the asymptotic behavior of Γw under Assumption 1. Lemma 6 (Asymptotic of Γw underP Normal Weight Model). M (2) Under Assumption 1, define W = = m=1 wm and W PM σ2 W (2) a.s. 2 − − → 1 + . In w . Then, as M → ∞, Γ = M 2 2 w m=1 m W µ 2 particular, E [Γw ] → 1 + σµ2 as M → ∞. Proof: Let X be a generic random variable with distribution X ∼ N µ, σ 2 . Then E [X] = µ and E X 2 = µ2 + σ 2 . Since w1 , . . . , wM are i.i.d., the strong law of large numbers implies that, almost surely, M 1 X W a.s. = wm −−→ E [X] = µ, M M m=1
(45)
and M W (2) 1 X 2 a.s. 2 = w −−→ E X = µ2 + σ 2 . M M m=1 m
(46)
Hence Γw = M
1 (2) 2 2 W (2) σ2 a.s. µ + σ MW = − − → = 1 + . (47) 2 1 W2 µ2 µ2 W M
To establish convergence in expectation, it suffices to verify uniform integrability. By Chebyshev’s inequality, 4σ 2 P W < µ2 M ≤ 2 → 0. µ M
(48)
On the event {W ≥ (µ/2) M }, Γw ≤
M 4 1 X 2 w . µ2 M m=1 m
2 = µ2 + σ 2 < ∞, the right-hand side has Since E wm uniformly bounded expectation. Therefore {Γw } is uniformly integrable, implying convergence in expectation, i.e.,
(49)
σ2 . µ2
(50)
This completes the proof. Combining Theorem 3 with Lemma 6 yields the following Theorem 4. Theorem 4. Suppose Assumption 1 holds. Then, as the number of coflows M → ∞, the approximation h Pexpected i M wm Tm ratio of Algorithm 1 satisfies E Pm=1 ≤ 2 1+ M ∗ m=1 wm Tm 2 σ µ2 max {K, τmax } + o (1), where o(1) → 0 as M → ∞. ACKNOWLEDGEMENT This work is supported by Department of Environment, Science and Innovation of Queensland State Government under Quantum 2032 Challenge Program (Project #Q2032001) and Key-Area Research and Development Plan of Guangdong Province #2020B010164003. The corresponding author is Hong Shen. R EFERENCES [1] J. Dean and S. Ghemawat, “Mapreduce: simplified data processing on large clusters,” Communications of the ACM, vol. 51, no. 1, pp. 107–113, 2008. [2] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauly, M. J. Franklin, S. Shenker, and I. Stoica, “Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing,” in 9th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 12), 2012, pp. 15–28. [3] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, “Dryad: distributed data-parallel programs from sequential building blocks,” in Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, 2007, pp. 59–72. [4] M. Chowdhury and I. Stoica, “Coflow: A networking abstraction for cluster applications,” in Proceedings of the 11th ACM Workshop on Hot Topics in Networks, 2012, pp. 31–36. [5] M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica, “Managing data transfers in computer clusters with orchestra,” ACM SIGCOMM Computer Communication Review, vol. 41, no. 4, pp. 98–109, 2011. [6] M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow scheduling with varys,” in Proceedings of the 2014 ACM conference on SIGCOMM, 2014, pp. 443–454. [7] F. R. Dogar, T. Karagiannis, H. Ballani, and A. Rowstron, “Decentralized task-aware scheduling for data center networks,” ACM SIGCOMM Computer Communication Review, vol. 44, no. 4, pp. 431–442, 2014. [8] S. Luo, H. Yu, Y. Zhao, B. Wu, S. Wang et al., “Minimizing average coflow completion time with decentralized scheduling,” in 2015 IEEE International Conference on Communications (ICC). IEEE, 2015, pp. 307–312. [9] M. Chowdhury and I. Stoica, “Efficient coflow scheduling without prior knowledge,” ACM SIGCOMM Computer Communication Review, vol. 45, no. 4, pp. 393–406, 2015. [10] H. Zhang, L. Chen, B. Yi, K. Chen, M. Chowdhury, and Y. Geng, “Coda: Toward automatically identifying and scheduling coflows in the dark,” in Proceedings of the 2016 ACM SIGCOMM Conference, 2016, pp. 160– 173. [11] X. Wang and H. Shen, “Online scheduling of coflows by attentionempowered scalable deep reinforcement learning,” Future Generation Computer Systems, vol. 146, pp. 195–206, 2023. [12] X. Wang, H. Shen, and H. Tian, “Efficient and fair: Information-agnostic online coflow scheduling by combining limited multiplexing with drl,” IEEE Transactions on Network and Service Management, vol. 20, no. 4, pp. 4572–4584, 2023.
[13] Z. Qiu, C. Stein, and Y. Zhong, “Minimizing the total weighted completion time of coflows in datacenter networks,” in Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, 2015, pp. 294–303. [14] M. Shafiee and J. Ghaderi, “An improved bound for minimizing the total weighted completion time of coflows in datacenters,” IEEE/ACM Transactions on Networking, vol. 26, no. 4, pp. 1674–1687, 2018. [15] Z. Wang, H. Zhang, X. Shi, X. Yin, Y. Li, H. Geng, Q. Wu, and J. Liu, “Efficient scheduling of weighted coflows in data centers,” IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 9, pp. 2003–2017, 2019. [16] C. Xu, H. Tan, J. Hou, C. Zhang, and X.-Y. Li, “Omco: Online multiple coflow scheduling in optical circuit switch,” in 2018 IEEE International Conference on Communications (ICC). IEEE, 2018, pp. 1–6. [17] C. Zhang, H. Tan, C. Xu, X.-Y. Li, S. Tang, and Y. Li, “Reco: Efficient regularization-based coflow scheduling in optical circuit switches,” in 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2019, pp. 111–121. [18] H. Tan, C. Zhang, C. Xu, Y. Li, Z. Han, and X.-Y. Li, “Regularizationbased coflow scheduling in optical circuit switches,” IEEE/ACM Transactions on Networking, vol. 29, no. 3, pp. 1280–1293, 2021. [19] X. S. Huang, X. S. Sun, and T. E. Ng, “Sunflow: Efficient optical circuit scheduling for coflows,” in Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies, 2016, pp. 297–311. [20] T. Zhang, F. Ren, J. Bao, R. Shu, and W. Cheng, “Minimizing coflow completion time in optical circuit switched networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 2, pp. 457–469, 2020. [21] X. Wang, H. Shen, and H. Tian, “Scheduling coflows in hybrid opticalcircuit and electrical-packet switches with performance guarantee,” IEEE/ACM Transactions on Networking, vol. 32, no. 3, pp. 2299–2314, 2024. [22] Z. Li and H. Shen, “Co-scheduler: Accelerating data-parallel jobs in datacenter networks with optical circuit switching,” in 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2019, pp. 186–195. [23] 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, 2025. [24] R. Jiang, T. Zhang, and C. Yi, “Effective coflow scheduling in hybrid circuit and packet switching networks,” in 2023 IEEE Symposium on Computers and Communications (ISCC). IEEE, 2023, pp. 1156–1161. [25] Cisco White Paper. (2016), “The future is 40 gigabit ethernet,” https://www.cisco.com/c/dam/en/us/products/collateral/switches/catalyst6500-series-switches/white-paper-c11-737238.pdf. [26] Cisco. (2016), “Cisco global cloud index: Forecast and methodology, 2015–2020,” https://www.cisco.com/c/dam/en/us/solutions/collateral/serviceprovider/global-cloud-index-gci/white-paper-c11-738085.pdf. [27] X. S. Huang, Y. Xia, and T. E. Ng, “Weaver: Efficient coflow scheduling in heterogeneous parallel networks,” in 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2020, pp. 1071–1081. [28] C.-Y. Chen, “Efficient approximation algorithms for scheduling coflows with total weighted completion time in identical parallel networks,” IEEE Transactions on Cloud Computing, vol. 12, no. 1, pp. 116–129, 2023. [29] L. Poutievski, O. Mashayekhi, J. Ong, A. Singh, M. Tariq, R. Wang, J. Zhang, V. Beauregard, P. Conner, S. Gribble et al., “Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking,” in Proceedings of the ACM SIGCOMM 2022 Conference, 2022, pp. 66–85. [30] S. Khuller and M. Purohit, “Brief announcement: Improved approximation algorithms for scheduling co-flows,” in Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016, pp. 239–240. [31] S. Im, B. Moseley, K. Pruhs, and M. Purohit, “Matroid coflow scheduling.” in ICALP, 2019, pp. 1–13. [32] C.-Y. Chen, “Scheduling coflows for minimizing the total weighted completion time in heterogeneous parallel networks,” Journal of Parallel and Distributed Computing, vol. 182, p. 104752, 2023. [33] Y. Zhao, K. Chen, W. Bai, M. Yu, C. Tian, Y. Geng, Y. Zhang, D. Li, and S. Wang, “Rapier: Integrating routing and scheduling for coflow-
aware data center networks,” in 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE, 2015, pp. 424–432. [34] M. Shafiee and J. Ghaderi, “Scheduling coflows with dependency graph,” IEEE/ACM Transactions on Networking, vol. 30, no. 1, pp. 450–463, 2021. [35] G. Birkhoff, “Tres observaciones sobre el algebra lineal,” Univ. Nac. Tucuman, Ser. A, vol. 5, pp. 147–154, 1946. [36] T. Gonzalez and S. Sahni, “Open shop scheduling to minimize finish time,” Journal of the ACM (JACM), vol. 23, no. 4, pp. 665–679, 1976. [37] “Facebooktrace,” https://github.com/coflow/coflow-benchmark, 2019.