O(K)-Approximation Coflow Scheduling in K -Core Optical Circuit Switching Networks Xin Wanga , Hong Shena , Hui Tianb , Ye Taoa a
arXiv:2604.22146v1 [cs.DC] 24 Apr 2026
b
School of Engineering and Technology, Central Queensland University, Australia School of Information and Communication Technology, Griffith University, Australia
Abstract—Coflow has emerged as a fundamental applicationlayer abstraction in distributed systems, representing communication dependencies and enabling collaborative management of related flows to enhance job completion efficiency. To meet the increasing bandwidth demands of modern data center networks (DCNs), optical circuit switches are widely deployed due to their high capacity and energy efficiency. Simultaneously, DCN deployments are evolving towards heterogeneous parallel architectures, where multiple independent optical circuit switching (OCS) cores operate concurrently to facilitate bandwidth expansion and incremental upgrades. However, existing research on coflow scheduling in multi-core switching fabrics primarily focuses on electrical packet switching (EPS) networks, with a few known results on OCS networks without or with a poor performance guarantee. This paper studies the coflow scheduling problem in multicore OCS networks under the not-all-stop (i.e., asynchronous) reconfiguration model, focusing on two major challenges of overcoming cross-core coupling for inter-core traffic allocation and satisfying the constraints of port exclusivity and reconfiguration overhead for intra-core circuit scheduling. To minimize total weighted coflow completion time (CCT), we propose an efficient algorithm by integrating linear programming-guided (LP-guided) global coflow ordering, inter-core flow allocation and intra-core circuit scheduling that achieves approximation ratios of 8K and (8K + 1) for zero and arbitrary release times of coflows, respectively, where K is the number of OCS cores. It significantly max K -approximation, improves the known result of O M w wmin where wmax and wmin are the maximum and minimum weights of M input coflows, respectively. This framework is also applicable to H-core EPS networks, providing approximation guarantees of 4H and (4H + 1) for zero-time and arbitrary-time release, respectively. Trace-driven experiments using a real Facebook workload further show that the proposed algorithm delivers strong practical performance in both total weighted CCT and tail CCT.
I. I NTRODUCTION Distributed computing frameworks, such as MapReduce [1], Spark [2] and Dryad [3], structure jobs as interdependent communication stages separated by synchronization barriers. Each subsequent computation stage begins only after all parallel flows in the current stage have completed. To aggregate semantically related flows into a unified scheduling entity, the coflow abstraction [4] has been introduced, enabling collaborative optimization. For instance, during the MapReduce shuffle stage, each reduce worker must receive all intermediate outputs from all map workers before continuing execution. Conse-
quently, the completion of the shuffle phase is determined by the slowest individual flow, indicating that optimizing only flow completion time (FCT) is insufficient to improve joblevel performance. Instead, the focus should shift to coflow completion time (CCT), defined as the completion time of the last flow within a coflow, as it more directly determines endto-end application efficiency. Prior research [5]–[16] on coflow scheduling has predominantly utilized the single-core electrical packet switching (EPS) model. In this model, the data center network (DCN) is abstracted as a single non-blocking switching fabric with full bisection bandwidth, simplifying the characterization of port-capacity constraints and facilitating scheduler design. Nevertheless, with the increasing traffic demands of modern data centers, EPS-based architectures encounter significant challenges related to scalability, deployment costs, and power consumption. To mitigate these issues, optical circuit switches have been incorporated into single-core DCN architectures, enabling dedicated high-capacity circuits for large-volume data transmission, thereby improving communication efficiency. Several coflow scheduling schemes [17]–[21] have been proposed within the single-core optical circuit switching (OCS) model. In addition to pure packet-switched and circuitswitched designs, recent research has extended the single-core model to hybrid EPS-OCS architectures, where packet and circuit resources coexist and are jointly optimized for coflow scheduling [22]–[25]. The traditional single-core abstraction is increasingly inadequate for representing modern data center architectures. Industry reports [26], [27] demonstrate that modern DCN architectures are evolving toward parallel designs, where multiple heterogeneous network cores operate concurrently to enhance aggregate bandwidth. In practical deployments, different generations of network architectures are often preserved and integrated rather than completely replaced, forming heterogeneous parallel networks (HPNs), in which multiple independent cores share the same set of hosts [28]. In response to this architectural evolution, previous research has investigated coflow scheduling in multi-core EPS networks, leveraging parallel packet-switched fabrics to increase network capacity [28], [29]. Parallelism is also becoming increasingly prevalent in circuit-switched fabrics. For example, Google’s Jupiter architecture replaces the traditional spine layer with a
datacenter interconnect layer composed of multiple parallel OCS cores, forming a directly connected architecture that supports flexible, data center-scale capacity upgrades and reconfigurations [30]. Although such multi-core OCS infrastructures have been deployed, the corresponding coflow scheduling mechanisms remain insufficiently studied. Such architectures enable greater flexibility in capacity scaling and fundamentally alters the scheduling model. Coflow scheduling in multi-core OCS networks faces numerous challenges. Unlike packet-switched networks, OCSbased systems are subject to two main constraints. First, port exclusivity restricts each ingress or egress port to participating in only one circuit at any given time. Second, each circuit reconfiguration incurs a non-negligible delay δ, typically ranging from hundreds of microseconds to milliseconds. Existing OCS reconfiguration mechanisms are generally divided into the all-stop and not-all-stop models (see Subsection III-C). In the all-stop (i.e., synchronous) model, whenever the circuit configuration changes, all ongoing transmissions are paused. In contrast, the not-all-stop (i.e., asynchronous) model only interrupts the ports involved in the circuit update, while transmissions on unaffected circuits continue uninterrupted. This paper focuses on the not-all-stop model, which is more practically relevant but also more challenging, as it further complicates resource coupling and scheduling decisions. When multiple OCS cores operate in parallel, coflow scheduling must jointly determine flow allocation across cores and circuit scheduling within each core, while respecting one-to-one port exclusivity and non-negligible reconfiguration overhead under the not-all-stop model. In contrast to single-core OCS scheduling or multi-core EPS scheduling, the combination of inter-core traffic coupling and OCS-specific switching constraints makes this problem more challenging. This study addresses the multi-coflow scheduling problem in multi-core OCS networks and introduces an approximation algorithm with a provable guarantee for minimizing the total weighted CCT. Notably, the proposed approach significantly advances the prior work [31] by establishing an wmax O M wmin K -approximation bound for the same multi-core OCS scenario. Additionally, the proposed framework can be naturally applied to multi-core EPS networks by setting the reconfiguration delay to zero (i.e., δ = 0) and substituting the OCS-specific lower bounds with the corresponding lower bounds tailored to the EPS setting, thereby yielding approximation guarantees. The main contributions of this paper are summarized as follows: We formulate the coflow scheduling problem in multicore OCS networks under the not-all-stop reconfiguration model and propose an efficient algorithm that combines LP-guided global coflow ordering, inter-core flow allocation and intra-core circuit scheduling. • We show that our algorithm achieves approximation ratios of 8K and (8K + 1) for zero-release and arbitraryrelease times of coflows, respectively, in a K-core OCS •
network, enabling a performance guarantee based solely on the architectural layout of the switching fabric rather than on input features. It represents a significant improvement over the known result, which has an approximation ratio proportional to the product of the coflow max-tomax min weight ratio w wmin , the number of coflows M and K. • We demonstrate that the proposed algorithm framework can be naturally applied to multi-core EPS networks. Specifically, for an H-core EPS network, the algorithm achieves approximation ratios of 4H and (4H + 1) under zero-release and arbitrary-release settings, respectively, thus providing a unified approximation perspective for multi-core OCS and EPS architectures. • We conduct extensive trace-driven simulations using real Facebook workloads to evaluate the proposed algorithm. The results demonstrate that the algorithm achieves superior overall performance, consistently outperforming representative ablation baselines and significantly reducing both total weighted CCT and tail CCT, thereby validating its practical effectiveness. The remainder 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 the proposed multiple coflow scheduling algorithm and its theoretical performance guarantees; Section V presents experimental results using a realistic Facebook trace; Section VI concludes this paper. II. R ELATED W ORK Coflow scheduling has been investigated across a range of data center network (DCN) switching models. Initial research focused on the single-core electrical packet switching (EPS) model. Later studies expanded coflow scheduling to singlecore optical circuit switching (OCS) scenarios, encompassing both pure OCS and hybrid EPS-OCS architectures, and considering both all-stop and not-all-stop reconfiguration mechanisms. Additionally, research has explored multi-core EPS architectures, where multiple packet-switched cores operate simultaneously to enhance aggregate bandwidth. However, coflow scheduling in multi-core OCS networks remains underexplored. This section reviews relevant literature from these perspectives and presents a comparative summary in Table I. A. Coflow Scheduling in Single-Core EPS Networks Orchestra [5] is widely considered the first study to introduce the coflow abstraction and demonstrate that even a simple FIFO-based strategy can significantly improve performance through coflow-aware scheduling. Varys [7] proposed two greedy heuristics: smallest-effective-bottleneck-first (SEBF) and minimum-allocation-for-desired-duration (MADD), for greedily scheduling coflows based on bottleneck completion time in single-core EPS networks, with the goal of minimizing the overall CCT. In decentralized environments, Barrat [8] used multiplexing techniques to solve the head-of-line
TABLE I: COMPARISON AMONG RELATED WORK Works Varys [7], Barrat [8], D-CAS [9], CODA [11] Qiu et al. [14], Khuller et al. [32], Shafiee et al. [15] OMCO [17] Sunflow [20], Reco-Sin [18], Reco-Mul+ [19], GOS [21] Co-scheduler [23], ONS [25] Wang et al. [22], Wang et al. [24] Weaver [28], Chen [33], Chen [29] Wang et al. [31], Our Work
Single-Core EPS-Enable OCS-Enable " ✘ " ✘ ✘ " ✘ " " " " " ✘ ✘ ✘ ✘
blocking problem of small coflows, while D-CAS [9] also focused on decentralized coflow scheduling. Aalo [10] and NCDRF [34] are two well-known information-agnostic coflow schedulers that prioritize efficiency and fairness, respectively. Specifically, Aalo [10] proposed a discretized coflow-aware least-attained service (D-CLAS) algorithm that can operate efficiently without prior knowledge of flow information. In contrast, NC-DRF [34] was designed to ensure isolation using load-balancing principles. CODA [11] was the first to apply machine learning to identify coflows between individual flows. Recently, Wang et al. [12] proposed a multi-stage online job scheduling framework based on deep reinforcement learning (DRL). In subsequent work, Wang et al. [13] combined limited multiplexing with DRL to reduce the average weighted CCT while maintaining fairness. However, these methods are predominantly heuristic and lack provable worst-case performance guarantees. At the theoretical level, several approximation results have been established. Qiu et al. [14] proposed a deterministic algorithm with an approximation ratio of 67 3 to minimize the total weighted CCT. Khuller et al. [32] modeled the problem as a concurrent open-shop problem and derived a 12-approximation algorithm. Shafiee et al. [15] subsequently improved this bound to 5 using a linear programming (LP) approach, while Wang et al. [16] achieved a 2-approximation algorithm by simplifying the process and eliminating the need for LP solving. Most of these works focus on singlestage coflow scheduling without considering the dependencies between coflows within a job. Tian et al. [35] were the first to investigate the scheduling of dependent coflows for multistage jobs, establishing an approximation ratio of (2N + 1), where N represents the number of hosts. Subsequently, Shafiee et al. [6] developed a polynomial-time algorithm with an µ log(N ) approximation ratio of O log(log(N )) , where µ represents the maximum number of coflows in the job. B. Coflow Scheduling in Single-Core OCS Networks Research on coflow scheduling for single-core OCS architectures, including pure OCS and hybrid OCS-EPS architectures, remains relatively limited. Given the two main OCS reconfiguration paradigms, the all-stop model and the not-allstop model, this paper reviews the existing literature under both settings.
Multi-Core EPS-Enable OCS-Enable ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ " ✘ "
Provable Guarantee ✘ " ✘ " ✘ " " "
1) All-Stop Reconfiguration Model: OMCO [17] was the first online algorithm for multi-coflow scheduling in singlecore pure OCS networks. Reco-Sin [18] and Reco-Mul+ [19] established the first approximation guarantees for singlecoflow and multi-coflow scheduling in a single-core pure OCS network, with approximation ratios of 2 and 8M , respectively, where M represents the number of coflows. The above methods are based on Birkhoff-von Neumann (BvN) decomposition [36]. Furthermore, Wang et al. [22] developed approximation algorithms with provable performance guarantees for both single and multiple coflow scheduling in a single-core hybrid EPS-OCS network. All these methods assume that the OCS operates under the all-stop model. 2) Not-All-Stop Reconfiguration Model: Under the not-allstop model, Sunflow [20] first proposed a constant-factor approximation algorithm for single-coflow scheduling in singlecore pure OCS networks, and a heuristic method for scheduling multiple coflows. Subsequently, GOS [21] developed a 4-approximation algorithm for multi-coflow scheduling in a single-core pure OCS network. In a hybrid optical-electrical environment, Co-scheduler [23] first considered both opticalelectrical hybrid-switching characteristics and coflow structures, although it did not provide formal performance guarantees. ONS [25] proposed an online heuristic algorithm for minimizing the total CCT in single-core hybrid EPS-OCS networks, also without theoretical performance bounds. All these methods are based on the not-all-stop reconfiguration model. C. Coflow Scheduling in Multi-Core EPS Networks In recent years, the coflow scheduling problem in multicore EPS networks has attracted increasing attention. Weaver [28] studied single-coflow scheduling in heterogeneous parallel networks (HPNs), and proposed an O(K)-approximation algorithm, where K is the number of network cores. Chen [33] further studied scheduling in HPNs the multi-coflow and derived an O logloglogKK -approximation algorithm. Furthermore, Chen [29] considered identical parallel networks and developed coflow-level approximation algorithms with approximation ratios of 4K + 1 and 4K for arbitrary and zero release times, respectively, where K represents the number of identical cores.
D. Coflow Scheduling in Multi-Core OCS Networks
TABLE II: Mathematical Symbols
Previous studies have examined the coflow scheduling problem in single-core EPS and OCS architectures, as well as in multi-core EPS networks. However, theoretical advancements in multi-core OCS environments remain limited. To the best of our knowledge, Wang et al. [31] were the first to analyze multicoflow scheduling in multi-core OCS networks, establishing max an O M w wmin K -approximation guarantee, where M is the number of coflows, K denotes the number of OCS cores, and wmax and wmin are the maximum and minimum coflow weights, respectively. Consequently, the approximation ratio is influenced by both the network size and input-dependent parameters, including the number of coflows and the weight range. In contrast, this work introduces a provable approximation algorithm for multi-coflow scheduling in a K-core OCS network under the not-all-stop (asynchronous) reconfiguration model, achieving an O (K)-approximation guarantee that depends solely on the architectural parameter K. This result represents a substantial improvement over the previously established bound for the same setting. III. S YSTEM M ODEL AND P ROBLEM F ORMULATION This section introduces the system model, including the network architecture, traffic abstraction, and optical circuit switching (OCS) reconfiguration mechanism. Based on this model, the multi-coflow scheduling problem in heterogeneous parallel networks (HPNs) is formally defined, and its computational complexity is analyzed. The main symbols used in this paper are summarized in Table II. A. Network Architecture This paper considers an HPN composed of K independent, non-blocking OCS cores operating in parallel, as illustrated in Fig. 1. The index set of OCS cores is denoted by K = {1, . . . , K}, where each core k ∈ K corresponds to one OCS. The index sets of source and destination servers are denoted by I and J , respectively, with |I| = |J | = N . The network interconnects N source servers {si : i ∈ I} and N destination servers {dj : j ∈ J }. Accordingly, each core forms an independent, non-blocking N × N switching fabric. K uplinks
Servers
r1
r1 OCS 1
s1
d1 r2
...
Source Servers
d2
...
...
sN
r2 OCS 2
s2
Optical Circuit Switch (OCS)
K downlinks
rK
rK OCS K
dN Destination Servers
Fig. 1: Heterogeneous Multi-Core DCN Architecture
Symbol
Definition
C M M K K N I, J
The set of coflows The index set of coflows The number of coflows, i.e., M = |M| The index set of parallel OCS cores The number of OCS cores, i.e., K = |K| The number of ingress/egress ports per core The index sets of source servers and destination servers, i.e., |I| = |J | = N p Any port in I ∪ J Cm The m-th coflow, where 1 ≤ m ≤ M Fm The set of flows in Cm Dm The demand matrix of Cm k Dm The portion of Dm allocated to core k fm (i, j) The flow from ingress port i to egress port j of Cm k (i, j) The subflow of fm (i, j) transmitted on core k fm k (i, j) on core The circuit establishment time of fm tkm (i, j) k k (i, j) dm (i, j) /dkm (i, j) The data size of fm (i, j) /fm k The load incident to port p in Dm /Dm ρm,p /ρkm,p k τm,p /τm,p The number of nonzero entries incident to port p in k Dm /Dm k ρm /ρkm The maximum port load in Dm /Dm k τm /τm The maximum number of nonzero entries in k Dm /Dm D1:m The prefix-aggregated demand matrix of first m P coflows, i.e., D1:m = m ℓ=1 Dℓ k D1:m The prefix-aggregated demand matrix k for P on core k k the first m coflows i.e., D1:m = m ℓ=1 Dℓ ρ1:m,p /ρk1:m,p The aggregate load incident to port p in k D1:m /D1:m k τ1:m,p /τ1:m,p The number of nonzero entries incident to port p in k D1:m /D1:m k ρ1:m /ρk1:m The maximum aggregate load in D1:m /D1:m k τ1:m /τ1:m The maximum number of nonzero entries in k D1:m /D1:m k r The per-port transmission rate of core k R The aggregated port P transmission rate across all cores, i.e., R = k∈K rk wm The weight of Cm am The release time of Cm δ The reconfiguration delay k Tm The completion time of the portion of coflow Cm allocated to core k Tm The completion time of coflow Cm
Each source server is equipped with K parallel uplinks, each of which connects to a different OCS core; each destination server has K corresponding downlinks. In core k, source server si is connected to ingress port i, and destination server dj is connected to egress port j, where i ∈ I and j ∈ J . Each core k ∈ K operates independently at a per-port transmission rate rk , capturing the heterogeneity in link capacities across cores. Therefore, traffic can be allocated across multiple cores, while circuit scheduling P is performed independently within each core. Let R = k∈K rk represent the aggregated port transmission rate across all cores. B. Traffic Abstraction We utilize the coflow abstraction [4] to model applicationlevel communication requirements in HPNs. A coflow contains a set of parallel flows that must be completed jointly to realize
a single communication stage of an application across multiple machines. Let C ≜ {Cm : m ∈ M} be the set of coflows, where M = {1, ..., M } is the index set of coflows. Each coflow Cm contains a set of flows Fm . For each m ∈ M and port pair (i, j) ∈ I × J , the flow fm (i, j) ∈ Fm represents traffic from source server si (equivalently, ingress port i) to destination server dj (equivalently, egress port j) with data size dm (i, j). Accordingly, each coflow Cm is characterized by a demand matrix Dm = [dm (i, j)]i∈I,j∈J of dimension |I| × |J | (i.e., N × N ). C. Reconfiguration Mechanism Due to the circuit-switching nature of OCS, each core k establishes a one-to-one matching between its ingress and egress ports at any given time. A circuit configuration can be represented as a matching in the bipartite graph induced by the ingress and egress ports, ensuring that each port participates in at most one active circuit. Each circuit reconfiguration incurs a fixed delay δ. During reconfiguration, the affected ports 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
Ing.2
Egr.2
Egr.1
Egr.2
Ing.3
Egr.3
Egr.2
Egr.1
Idle Circuit
.3 .1
Egr.3
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
a positive weight wm , and a release time am ≥ 0. The goal is to schedule all flows fm (i, j) on a K-core OCS network under the asynchronous (not-all-stop) reconfiguration model. A feasible schedule includes the following components: • Global Coflow Ordering: A permutation of M = {1, ..., M } that specifies the global priority order of coflows. During execution, this order is enforced among coflows that have already been released. • Inter-Core Flow Allocation: For each coflow Cm with k , demand matrix Dm , determine an allocation Dm k∈K P k k where k ∈ K such that D = D . Here, D = m m k∈K m k dm (i, j) i∈I,j∈J denotes the portion of Dm allocated P to core k, satisfying dkm (i, j) ≥ 0 and k∈K dkm (i, j) = dm (i, j), ∀ (i, j) ∈ I × J . • Intra-Core Circuit Scheduling: For each core k ∈ K and k k each subflow fm (i, j) with a dmk (i, j) > 0, determine k circuit schedule Sm = i, j, tm (i, j) , where tkm (i, j) k represents the circuit establishment time of fm (i, j). Each subflow can be scheduled only after the release time of its coflow, i.e., tkm (i, j) ≥ am , since coflow Cm is unavailable before time am . Under the not-all-stop model, the transmission of subflow k k (i, j) = (i, j) starts from tkm (i, j) + δ and completes at Tm fm k d (i,j) tkm (i, j) + δ + mrk . The completion time of the portion k = of coflow Cm assigned to core k is defined as Tm k (i, j), and the overall coflow completion max(i,j)∈I×J Tm k time (CCT) is Tm = maxk∈K PTm . The goal is to minimize the total weighted CCT: min m∈M wm Tm . E. Hardness Analysis
Egr.1 Time
(b) Circuit Scheduling in not-all-stop Model
Fig. 2: Circuit Reconfiguration Models in an OCS Core The circuit configurations evolve according to two standard reconfiguration models, namely the all-stop or not-all-stop models, as shown in Fig. 2. In the all-stop model (Fig. 2(a)), reconfiguration is synchronous: whenever the configuration changes, all ongoing transmissions are paused. This model is conceptually simple and is often associated with preemptive scheduling. However, such global suspension may lead to unnecessary port idleness and reduced resource utilization. In contrast, the not-all-stop model (Fig. 2(b)) adopts asynchronous reconfiguration, in which only the ports involved in the circuit update are interrupted, while other established circuits continue transmitting. In this setting, once a flow begins transmission on a circuit, the transmission is typically nonpreemptive. Although this model improves link utilization and reduces unnecessary interruptions, it also increases scheduling complexity due to asynchronous reconfiguration. D. Problem Definition Consider a set of coflows C, where each coflow Cm ∈ C is associated with a demand matrix Dm = [dm (i, j)]i∈I,j∈J ,
When the reconfiguration delay δ is infinity, i.e., δ = ∞, the scheduling problem for a single coflow in a single-core OCS network reduces to a non-preemptive open-shop scheduling problem with the objective of minimizing the makespan, which is NP-hard [37]. Furthermore, even in two-port OCS networks, the single-coflow scheduling problem remains NP-hard for any finite reconfiguration delay where 0 < δ < ∞ [20]. The multi-core OCS scheduling problem considered in this paper is a strict generalization of the single-core case. Specifically, any instance on a single-core OCS network can be represented as a K-core network by allocating all traffic to one core and leaving the remaining cores idle. Therefore, the single-coflow scheduling problem in a multi-core OCS network is also NP-hard. Consequently, the multi-coflow problem is NP-hard as well, since the single-coflow case is a special case corresponding to M = 1. IV. M ULTI -C ORE C OFLOW S CHEDULING This section presents an approximation algorithm (Algorithm 1) for multi-coflow scheduling in heterogeneous multicore OCS networks under the not-all-stop reconfiguration model, and establishes its provable performance guarantees. The proposed method consists of three main components: (i) LP-guided global coflow ordering, (ii) inter-core flow allocation, and (iii) intra-core circuit scheduling.
To support algorithm design, we derive a local singlecore lower bound associated with a given inter-core flow allocation, which characterizes the minimum completion time requirement on a single core. To support the approximation analysis, we then construct a prefix-aware global lower bound via an ordering-based linear programming (LP) relaxation, which characterizes the overall scheduling performance. A. Derivation of the Lower Bounds Consider a coflow Cm with demand matrix Dm = dm (i, j) i∈I,j∈J . For any port p ∈ I ∪ J , the aggregate traffic load incident to port p is defined as (P dm (i, j), if p = i ∈ I, ρm,p ≜ Pj∈J d if p = j ∈ J , i∈I m (i, j), and the corresponding reconfiguration count, i.e., the number of nonzero entries incident to port p, is defined as (P 1[dm (i, j) > 0], if p = i ∈ I, τm,p ≜ Pj∈J if p = j ∈ J . i∈I 1[dm (i, j) > 0], The maximum port load in Dm is defined as ρm ≜ maxp∈I∪J ρm,p , and the maximum number of nonzero entries in Dm is defined as τm ≜ maxp∈I∪J τm,p . In a K-core OCS network, let rk P represent the per-port transmission rate of core k, and let R = k∈K rk denote the aggregate port rate across all cores. any allocation 1)k Single-Core Lower Bound:P Consider k k = such that D = , where Dm D D m k∈K m k m k∈K dm (i, j) i∈I,j∈J denotes the portion of Dm allocated to core k. For each core k ∈ K and each port p ∈ I ∪ J , the incident traffic load and reconfiguration count on core k are defined as (P dk (i, j), if p = i ∈ I, k ρm,p ≜ Pj∈J km if p = j ∈ J , i∈I dm (i, j), and k τm,p ≜
(P
1[dkm (i, j) > 0], k i∈I 1[dm (i, j) > 0],
Pj∈J
if p = i ∈ I, if p = j ∈ J .
k The maximum port load of Dm is defined as ρkm ≜ k maxp∈I∪J ρm,p , and the maximum number of nonzero entries k k k in Dm is defined as τm ≜ maxp∈I∪J τm,p . For a given k k allocation Dm k∈K , let TLB (·) denote the CCT lower bound of the traffic allocated to core k. Since each port can only participate in one circuit at a time, transmitting the total load incident to port p on core k requires at least ρkm,p /rk . In addition, each nonzero flow incident to that port requires one circuit establishment, leading to a total k reconfiguration delay of at least τm,p δ. Taking the maximum over all ports yields the lower bound. For any nonzero demand k matrix Dm ̸= 0|I|×|J | , the single-core lower bound is given by k k TLB Dm ≜ max Lkm,p , (1) p∈I∪J
where Lkm,p =
ρk m,p k + τm,p δ. rk
Lemma 1 (Single-Core Lower Bound). In a K-core OCS k network, for any nonzero assigned demand matrix Dm ̸= 0|I|×|J | , the completion time of the portion of coflow Cm as k signed to core k satisfies Tm ≥ maxp∈I∪J
ρk m,p k + τm,p δ rk
.
k k The lower kbound TLB Dm depends on the specific flow allocation Dm k∈K and is therefore allocation-dependent. To derive an approximation ratio relative to the optimal schedule, we need a global lower bound that depends only on the original demand matrix Dm and network parameters, rather than on any particular allocation or schedule. Prior work [31] established the allocation-independent single-coflow lower bound TLB (Dm ) ≜ δ + ρRm . However, this bound applies only to a single coflow and does not capture prefix interactions among multiple coflows, which are crucial for analyzing the total weighted CCT. As a result, relying on this bound alone may lead to an approximation factor that scales with the number of coflows M . To overcome this limitation, we next develop a prefix-aware global lower bound via an ordering-based LP relaxation, which explicitly captures the cumulative transmission and reconfiguration workloads induced by preceding coflows. 2) Prefix-Aware Lower Bound: Inspired by the classical ordering-based LP relaxation framework, which has been widely used in multi-coflow scheduling for single-core EPS networks [15], we formulate the following LP relaxation for the multi-core OCS scheduling problem. To capture the aggregate service capability of the multicore OCS network, we adopt an aggregated resource view for each source or destination port p ∈ I ∪ J . Under this view, traffic can be processed in parallel across K cores, where each core k provides a per-port transmission rate rk . Therefore, the aggregate P transmission rate available for port p across all cores is k∈K rk (= R). Furthermore, since each port p independently participates in circuit reconfiguration operations across different cores, and each such operation on each core requires δ time units, each core contributes a reconfiguration-processing rate of at most 1/δ. Hence, the aggregate reconfiguration-processing rate associated with port p across all cores is at most K/δ. The LP formulation introduces a relaxed ordering variable xm,m′ ∈ [0, 1], which represents the completion precedence relation between coflows Cm and Cm′ . The ordering variables satisfy the constraint, i.e., xm,m′ + xm′ ,m = 1, ∀m ̸= m′ .
(2)
In an exact integer programming (IP) formulation, xm,m′ ∈ {0, 1}, where xm,m′ = 1 indicates that coflow Cm completes before coflow Cm′ and xm,m′ = 0 otherwise. In the LP relaxation, xm,m′ is allowed to take any value in [0, 1], i.e., 0 ≤ xm,m′ ≤ 1, ∀m ̸= m′ .
(3)
From the aggregated resource perspective, the formulation imposes two necessary capacity constraints for each coflow Cm and each port p ∈ I ∪ J : (i) Transmission-Capacity Constraints: By the time coflow Cm completes, all coflows ordered before Cm , together with Cm itself, must have already transmitted all traffic incident to port p. Since the available aggregate transmission rate available on port p is R, the cumulative transmitted load by time Tm cannot exceed RTm . Hence, X 1 ρm′ ,p xm′ ,m , ∀m, p. (4) Tm ≥ ρm,p + R ′ m ̸=m
(ii) Reconfiguration-Capacity Constraints: Similarly, when coflow Cm completes, all reconfiguration operations associated with coflows ordered before Cm , together with those required by Cm , must also have been completed on port p. Since the aggregate reconfiguration-processing rate available on port p is upper bounded by K/δ, the cumulative number of such reconfiguration operations cannot exceed (K/δ) Tm . Therefore, X δ τm,p + τm′ ,p xm′ ,m , ∀m, p. (5) Tm ≥ K ′ m ̸=m
In addition, since coflow Cm cannot complete before it is released, we impose the release-time constraints Tm ≥ am , ∀m.
(6)
Collecting the above constraints, we obtain the following LP relaxation: X min wm Tm , s.t. (2) − (6) . m∈M
Let Tem , x em,m′ denote the optimal solution to the LP ∗ denote the completion time of coflow relaxation, and let Tm Cm in an optimal feasible schedule to the original problem. Since any feasible schedule for the original problem induces a feasible integral solution to the LP, the formulation is a valid relaxation of the original scheduling problem. Consequently, the objective value of the LP relaxation provides a valid lower bound optimal value of the original problem, namely PM on the ∗ em ≤ PM wm Tm w T . m m=1 m=1 B. Approximation Algorithm Our algorithm framework adopts an LP-guided combinatorial construction, rather than a standard LP-rounding paradigm. The LP relaxation plays two roles: (i) its objective value provides the lower bound usednin the o approximation analysis, and (ii) its completion values Tem serve as surrogate m∈M priority indicators for constructing the global coflow ordering. Importantly, the feasible scheduling scheme is not obtained by rounding in the LP solution; instead, the final feasible scheduling scheme (including flow allocation and circuit scheduling) is directly generated by a greedy combinatorial procedure. The
core of the analysis is then to prove that the objective value of the constructed feasible schedule is at most a constant-factor multiple of the objective value of the LP relaxation, thereby establishing the approximation ratio of our algorithm. Consistent with the intuitive three-stage framework adopted in [31], Algorithm 1 consists of three components: (i) global coflow ordering, (ii) inter-core flow allocation, and (iii) intracore circuit scheduling. The key difference in our approach lies in the LP-guided global ordering and the corresponding approximation analysis. 1) LP-guided Global Coflow Ordering: We first solve the ordering-based LP relaxation introduced in Subsection IV-A2. Let Tem denote the value of the LP variable Tm associated with coflow Cm in the LP solution, which serves as a lower bound on its completion time in the original scheduling problem. The coflows are then sorted in non-decreasing order of Tem , and re-indexed accordingly so that Te1 ≤ Te2 ≤ · · · ≤ TeM , with ties broken arbitrarily. This LP-guided order is adopted as the global coflow priority order throughout the algorithm. During scheduling, this order is enforced among released coflows. Unless otherwise specified, all subsequent coflow indices refer to this reordered sequence. 2) Inter-Core Flow Allocation: The inter-core flow allocation is a prefix-aware greedy assignment procedure. Coflows are processed sequentially according to the re-indexed order. Each flow is allocated entirely to a single core, and flow splitting is not allowed to avoid packet reordering, buffering overhead, and additional control-plane complexity in practical multi-core OCS deployments [28]. Restricting allocation to the flow level ensures both analytical tractability and practical implementability. For each flow fm (i, j), the algorithm selects the core that minimizes the single-core prefix lower bound k k TLB D1:m ⊕ dm (i, j) after allocation. Intuitively, this rule aims to prevent any single core from becoming the dominant prefix bottleneck, thereby reducing the cumulative queuing and blocking effects that subsequent coflows may encounter on overloaded cores, and thus indirectly reducing the final weighted total CCT. The internal processing order of flows within a coflow does not affect the approximation guarantee. In practice, allocating larger flows earlier may reduce their impact on the final total weighted CCT. 3) Intra-Core Circuit Scheduling: After the allocation phase, each core independently schedules the traffic allocated to it, while adhering to the global coflow priority order among released coflows. The intra-core circuit scheduling phase employs a greedy earliest-feasible port-matching scheduler, following a fixed global coflow order: it scans subflows according to the global coflow order and schedules the first released subflow with both its ingress and egress ports idle at the earliest feasible time. The design goal is to avoid unnecessary port idleness and maximize core utilization, thereby improving the final performance of each core. The intra-core circuit scheduling policy exhibits the following properties: • Port-Exclusive: Each ingress and egress port can participate in at most one active circuit at any given time,
thus satisfying the one-to-one port matching constraint of OCS. • Non-Preemptive: Once a flow begins transmission, it continues until completion without interruption, avoiding additional reconfiguration overhead. • Work-Conserving: When no high-priority flows are waiting to be processed on a port pair, low-priority flows can be processed first, ensuring that no eligible port pairs remain idle. The algorithm first determines the global coflow priority order by solving the LP relaxation of the original problem (Lines 1-2). The coflows are then sorted in non-decreasing order of Tem and re-indexed accordingly, so that Te1 ≤ Te2 ≤ · · · ≤ TeM . Subsequently, the algorithm enters the flow allocation phase (Lines 3-15). core k ∈ K, a prefix-aggregated matrix PmFor each k k = D is maintained to represent the aggregate D1:m ℓ=1 ℓ traffic allocated to core k from the first m coflows in the rek is initialized indexed order. For each core k, the matrix D1:0 to zero (Line 3). For each coflow Cm processed sequentially k k (Line 4), for all k ∈ K , D1:m is set to D1:m−1 to ensure that each core inherits the prefix load of the first m − 1 coflows before any flow of Cm is allocated (Line 5). The k per-core allocation matrices Dm are also initialized to zero for all k ∈ K (Line 6). Let Fm denote the set of nonzero flows in Cm (Line 7), which is then sorted in non-increasing order of dm (i, j) (Line 8). For each flow fm (i, j) ∈ Fm (Line 9), the algorithm tentatively places it on every core k k by constructing D1:m ⊕ dm (i, j), which increases the (i, j)k th entry of D1:m by dm (i, j). This operation is equivalent to k D1:m +dm (i, j) Eij , where Eij ∈ RN ×N is the standard basis matrix with a 1 in entry (i, j) and zeros elsewhere. The core k ∗ k k is then selected as k ∗ ← argmink∈K TLB D1:m ⊕ dm (i, j) (Line 10), corresponding to the core that yields the minimum single-core lower bound after adding this flow. The entire flow k∗ k∗ is allocated to core k ∗ (Line 11), and both Dm and D1:m are updated accordingly (Lines 12-13). After all flows in C have m k been allocated, the Dm k∈K represent its inter-core matrices k allocation, and D1:m are carried forward to the next k∈K iteration. In the final phase, intra-core circuit scheduling is performed independently on each core (Lines 16–30). For each k core k ∈ K, the circuit schedule Sm for each coflow m ∈ M is initialized (Lines 17-19). The set F k ≜ k S k is constructed, containing m∈M fm (i, j) | dm (i, j) > 0 all unfinished subflows allocated to core k (Line 20). Scheduling decisions are made over the released subflows in F k according to the re-indexed global coflow priority order. While F k is non-empty (Line 21), the scheduler scans the subflows in F k in that order (Line 22), and sequentially selects the k first released subflow fm (i, j) whose ingress port i and egress port j are both idle (Line 23). The selected subflow is then scheduled at the earliest feasible circuit establishment time tkm (i, j), which is no earlier than the release time am of its coflow and is constrained by the availability of ports i and j. Its
Algorithm 1 Multi-Coflow Scheduling in Multi-Core OCS Networks Input: demand matrices {Dm = [dm (i, j)]}m∈M; weights {wm }m∈M ; release times {am }m∈M ; core rates rk k∈K ; reconfiguration delay δ k and circuit schedOutput: flow allocations Dm m∈M,k∈K k ules Sm m∈M,k∈K for all cores ▷ COFLOW ORDERING 1: n Solveothe LP relaxation and obtain the optimal solution Tem m∈M em and re-index: 2: Sort coflows in non-decreasing order of T Te1 ≤ Te2 ≤ · · · ≤ TeM ▷ FLOW ALLOCATION k 3: Initialize D1:0 ← 0N ×N for all k ∈ K 4: for m = 1 to M do k k 5: Initialize D1:m ← D1:m−1 for all k ∈ K k 6: Initialize Dm ← 0N ×N for all k ∈ K 7: Fm ≜ {fm (i, j) | dm (i, j) > 0} 8: Sort Fm in non-increasing order of dm (i, j) 9: for each flow fm (i, j) in Fm do k k 10: k ∗ ← argmink∈K TLB D1:m ⊕ dm (i, j) 11: Allocate the entire flow fm (i, j) to core k ∗ k∗ k∗ ⊕ dm (i, j) = Dm 12: Dm k∗ k∗ 13: D1:m ← D1:m ⊕ dm (i, j) 14: end for 15: end for ▷ CIRCUIT SCHEDULING 16: for each k ∈ K do 17: for each m ∈ M do k ←∅ 18: Sm 19: end for k S 20: F k ≜ m∈M fm (i, j) | dkm (i, j) > 0 ▷ processed in the re-indexed global order 21: while F k ̸= ∅ do k (i, j) ∈ F k do 22: for each fm k 23: if fm (i, j) is released and both ingress i and egress j are idle then dk (i,j) k (i, j) ← tkm (i, j) + δ + mrk 24: Tm ▷ tkm (i, j) ← earliest feasible time no earlier than am k 25: Add i, j, tkm (i, j) to Sm k 26: Remove fm (i, j) from F k 27: end if 28: end for 29: end while 30: end for dk (i,j)
k completion time is given by Tm (i, j) ← tkm (i, j)+δ + mrk k (Line 24). The scheduled subflow is then recorded in Sm (Line k 25) and removed from F (Line 26).
C. Analysis of Performance Guarantees For each coflow Cm and each port p ∈ I ∪ J , let ρm,p denote the aggregate traffic load of Cm incident to port p, and let τm,p denote the number of nonzero flow entries of
Cm incident to port p. For any prefix set LP m = {1, . . . , m}, m define the prefix-aggregated matrix D ≜ 1:m ℓ=1 Dℓ , and for Pm k k each core k, define D1:m ≜ ℓ=1 Dℓ . For any port p ∈ I ∪ J , let ρ1:m,p and τ1:m,p denote the aggregate traffic load and the number of nonzero entries incident to port p in D1:m , respectively. Let ρ1:m and τ1:m denote the maximum aggregate traffic load and the maximum number of nonzero entries incident to any port in D1:m , respectively. Specifically, define ρ1:m ≜ maxp∈I∪J ρ1:m,p and τ1:m ≜ maxp∈I∪J τ1:m,p . Let rmax ≜ maxk∈K rk . Our proof proceeds in three steps. First, we use the LP constraints to derive prefix-aware global bounds on ρ1:m and τ1:m in terms of Tem . Second, we show that the greedy inter-core flow allocation transforms these global prefix bounds into a bound on the maximum per-core prefix lower k k bound maxk TLB D1:m . Third, we prove that the completion time of coflow Cm under the intra-core circuit scheduling policy is upper bounded by a constant-factor multiple of k k maxk TLB D1:m . Combining these three ingredients yields the claimed approximation guarantee. 1) Derivation of Ordering-Phase Prefix Bound: Lemma 2 (Transmission-Capacity Prefix Bound). For any prefix set Lm = {1, . . . , m} and any fixed port p ∈ I ∪ J , Pm Pm 2 1 e ℓ=1 ρℓ,p ) . Consequently, ρ1:m ≤ ℓ=1 ρℓ,p Tℓ ≥ 2R ( 2RTem . Proof: The proof follows the similar prefix-based analysis for ordering LP relaxations [15]. We first establish the transmission bound. By the transmission-capacity constraints in Eq. (4), for each ℓ ∈ Lm , X 1 ρq,p xq,ℓ . (7) Teℓ ≥ ρℓ,p + R q̸=ℓ
Multiplying both sides by ρℓ,p and summing over ℓ = 1, . . . , m, we obtain m X ℓ=1
m m X m X 1 X 2 ρℓ,p ρq,p xq,ℓ ρℓ,p Teℓ ≥ ρ + ℓ,p . R q=1 ℓ=1
(8)
ℓ=1
q̸=ℓ
Now consider any pair ℓ, q with 1 ≤ ℓ < q ≤ m. Since the LP imposes xℓ,q + xq,ℓ = 1, we have ρℓ,p ρq,p xq,ℓ + ρq,p ρℓ,p xℓ,q = ρℓ,p ρq,p . Therefore, m X m X X ρℓ,p ρq,p xq,ℓ = ρℓ,p ρq,p . (9) ℓ=1 q=1 q̸=ℓ
1≤ℓ<q≤m
which implies m X ℓ=1
1 ρℓ,p Teℓ ≥ 2R
m X
!2 ρℓ,p
.
(10)
ℓ=1
Next, since the LP completion values are ordered nondecreasingly, we have Teℓ ≤ Tem for every ℓ ≤ m. Hence, !2 m m X 1 X e Tm ρℓ,p ≥ ρℓ,p , (11) 2R ℓ=1
ℓ=1
which implies m X
ρℓ,p ≤ 2RTem .
(12)
ℓ=1
Taking the maximum over all p ∈ I ∪ J gives ρ1:m ≤ 2RTem .
(13)
This completes the proof. Lemma 3 (Reconfiguration-Capacity Prefix Bound). For any prefix set Lm = {1, . . . , m} and any fixed port p ∈ I ∪ Pm Pm 2 δ e J, ℓ=1 τℓ,p Tℓ ≥ 2K ( ℓ=1 τℓ,p ) . Consequently, τ1:m ≤ 2K e δ Tm . Proof: The proof for the reconfiguration bound is analogous. By the reconfiguration-capacity constraints in Eq. (5), for each ℓ ∈ Lm , X δ τℓ,p + τq,p xq,ℓ . (14) Teℓ ≥ K q̸=ℓ
Repeating the same argument yields τ1:m ≤
2K e Tm . δ
(15)
This completes the proof. 2) Derivation of Allocation-Phase Prefix Bound: Lemma 4 (Allocation-Phase Prefix kBound). For any m ∈ M, the prefix-aggregated matrices D1:m generated by the k∈K k k allocation phase of Algorithm 1 satisfy maxk∈K TLB D1:m ≤ ρ1:m + τ δ. 1:m rmax Proof: Consider any non-empty core k1 after processing the first m coflows. Let f¯k1 (i, j) be the last flow allocated to core k1 during the allocation of the first m coflows in Lm , and let d¯k1 (i, j) denote its size. Let D̄k1 be the aggregate demand matrix on core k1 immediately before allocating f¯k1 (i, j). The k1 final aggregate demand on core k1 is D1:m = D̄k1 ⊕ d¯k1 (i, j). Since Algorithm 1 allocates each flow greedily to the core with the minimum single-core prefix lower bound, when f¯k1 (i, j) was allocated, for any core k2 ∈ K, k1 k2 TLB D̄k1 ⊕ d¯k1 (i, j) ≤ TLB D̄k2 ⊕ d¯k1 (i, j) , (16) where D̄k2 denotes the aggregate matrix on core k2 at that time. k By the monotonicity of TLB (·), it follows that k2 k2 TLB D̄k2 ⊕ d¯k1 (i, j) ≤ TLB (D1:m ) . (17) Combining the above inequalities gives, for every k2 ∈ K, k1 k1 k2 TLB D1:m ≤ TLB (D1:m ) , (18) k1 k1 k1 where TLB D1:m = TLB D̄k1 ⊕ d¯k1 (i, j) . Since this holds for all k2 ∈ K, we obtain k1 k1 k ≤ min TLB (D1:m ) . (19) TLB D1:m k∈K
Because k1 is an arbitrary nonempty core, taking the maximum over all k ∈ K gives k k k max TLB D1:m ≤ min TLB (D1:m ) . (20) k∈K
k∈K
k Finally, by the definition of TLB (·) (Eq. (1)) applied to the matrix D1:m , ρ1:m k TLB (D1:m ) = max Lk1:m,p ≤ k + τ1:m δ, (21) p∈I∪J r ρ
where Lk1:m,p = 1:m,p + τ1:m,p δ. rk 1 , we Taking the minimum over k and using mink r1k = rmax obtain ρ ρ 1:m 1:m k k D1:m ≤ min max TLB + τ δ ≤ + τ1:m δ. 1:m k k rk rmax (22) This completes the proof. 3) Derivation of Scheduling-Phase Prefix Bound: Let Tm denote the final coflow completion time (CCT) of Cm under Algorithm 1. Lemma 5 (Scheduling-Phase Prefix Bound). For any m ∈ M, the completion time of coflow Cm satisfies Tm = k k k ≤ am + 2 maxk∈K TLB D1:m . maxk∈K Tm k ̸= 0, i.e., coflow Proof: Fix any core k ∈ K such that Dm Cm has at least one nonzero flow allocated to core k. Let (i⋆ , j ⋆ ) be the port-pair corresponding to the last completed flow of Cm on core k, and let d⋆ = dkm (i⋆ , j ⋆ ) > 0 denote its size. Let t⋆ = tkm (i⋆ , j ⋆ ) be the circuit establishment time k (i⋆ , j ⋆ ). Since Cm cannot be scheduled before its of flow fm release time, we have t⋆ ≥ am . k Under not-all-stop reconfiguration, the flow fm (i⋆ , j ⋆ ) ⋆ starts transmission at time t + δ and completes at k Tm (i⋆ , j ⋆ ) = t⋆ + δ + ⋆
d⋆ . rk
Because (i , j ) corresponds to the last completed flow of Cm on core k, we have i,j
ρk
ρk1:m,i⋆ − d⋆ k + τ1:m,i ⋆ − 1 δ. k r By the same argument for the egress port j ⋆ , Bi⋆ (am , t⋆ ) ≤
Bj ⋆ (am , t⋆ ) ≤
ρk1:m,j ⋆ − d⋆ k + τ1:m,j ⋆ − 1 δ. k r
(25)
(26)
Since for any time t ∈ [am , t⋆ ) at least one of the two ports i⋆ and j ⋆ is busy, the interval length is bounded by the sum of their busy times: t⋆ − am ≤ Bi⋆ (am , t⋆ ) + Bj ⋆ (am , t⋆ ) ρk1:m,i⋆ + ρk1:m,j ⋆ − 2d⋆ k k + τ1:m,i ⋆ + τ1:m,j ⋆ − 2 δ. rk (27) ⋆ k = t⋆ + δ + drk gives Substituting this into Tm ≤
ρk1:m,i⋆ + ρk1:m,j ⋆ k k + τ1:m,i ⋆ + τ1:m,j ⋆ δ. (28) k r k k By the definition of TLB D1:m , we have
k Tm ≤ am +
and
(24)
Now consider the scheduling policy on core k, which is port-exclusive, non-preemptive, and work-conserving, and respects the global priority order. For any time t ∈ [am , t⋆ ), at least one of the two ports i⋆ and j ⋆ must be busy; k otherwise, the flow fm (i⋆ , j ⋆ ) could have been scheduled earlier, contradicting the definition of t⋆ . Let Bi⋆ (am , t⋆ ) and Bj ⋆ (am , t⋆ ) denote the total busy times of ports i⋆ and j ⋆ over [am , t⋆ ), rePN thek interval ⋆ k spectively. Define ρ1:m,i⋆ ≜ j=1 d1:m (i , j) as the prefix k load incident to port i⋆ on core k, and define τ1:m,i ⋆ ≜ k PN ⋆ 1 d (i , j) > 0 as the number of distinct nonzero 1:m j=1 k . port pairs incident to i⋆ in the prefix matrix D1:m ⋆ ⋆ Port i can be busy during [am , t ) for two reasons: (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 ,
⋆ ⋆ −d
total transmission busy time on i⋆ is at most 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 prior at most τ1:m,i ⋆ − 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 at most τ1:m,i⋆ − 1 δ. Combining the above two bounds yields
(23)
⋆
k k k Tm = maxTm (i, j) = Tm (i⋆ , j ⋆ ) .
k excluding the transmission of flow fm (i⋆ , j ⋆ ) itself. Hence, the total amount of prefix data that can be transmitted through port i⋆ before time t⋆ is at most ρk1:m,i⋆ − d⋆ , and thus the
ρk1:m,i⋆ k k k + τ1:m,i ⋆ δ ≤ TLB D1:m , rk
(29)
ρk1:m,j ⋆ k k k + τ1:m,j ⋆ δ ≤ TLB D1:m . k r
(30)
k k k Tm ≤ am + 2TLB D1:m .
(31)
Hence, Finally, taking the maximum over all cores yields k k k Tm = max Tm ≤ am + 2 max TLB D1:m . k∈K
k∈K
(32)
This completes the proof. 4) Derivation of Deterministic Approximation Ratio: Theorem 1. Algorithm 1 achieves an (8K + 1)approximation for minimizing the total weighted CCT in PM OCS ∗ network, i.e., PM a heterogeneous multi-core w T ≤ (8K + 1) m m m=1 m=1 wm Tm , where K is the number of OCS cores. Proof: By Lemma 2 and Lemma 3, for any m ∈ M, the prefix transmission and reconfiguration bottlenecks satisfy e ρ1:m ≤ 2RTem and τ1:m ≤ 2K δ Tm . By Lemma 4, we
k k 1:m ≤ rρmax D1:m have maxk∈K TLB + τ1:m δ, where rmax ≜ maxk∈K rk . Substituting the above prefix bounds yields k k max TLB D1:m
k∈K
Since R = Therefore,
P
k∈K r
k
2RTem ≤ + 2K Tem . rmax
(33)
R ≤ K. ≤ Krmax , it follows that rmax
k max TLB k∈K
k D1:m
≤ 4K Tem .
(34)
Furthermore, by Lemma 5, the completion time of coflow Cm under Algorithm 1 satisfies Tm ≤ am + k k 2 maxk∈K TLB D1:m . Combining the above inequalities yields Tm ≤ am + 8K Tem . (35) According to Eq. (6), for each m, we have Tem ≥ am . Hence Tm ≤ Tem + 8K Tem ≤ (8K + 1) Tem .
(36)
Multiplying both sides by wm and summing over all m ∈ M, we obtain M X
wm Tm ≤ (8K + 1)
M X
wm Tem .
(37)
m=1
m=1
Since the LP objective provides a lower bound on the optimal weighted CCT of the original problem, thus, M X
wm Tem ≤
m=1
M X
∗ wm Tm .
(38)
m=1
Combining the above inequalities gives M X
wm Tm ≤ (8K + 1)
m=1
M X
∗ wm Tm .
(39)
m=1
This completes the proof. Corollary 1. Algorithm 1 achieves an 8K-approximation for minimizing the total weighted CCT when all coflows are released at time zero (i.e.,Pam = 0) in a heterogeneous multiPM M ∗ core OCS network, i.e., m=1 wm Tm ≤ 8K m=1 wm Tm , where K is the number of OCS cores. Besides multi-core OCS networks, Algorithm 1 can also be naturally applied to multi-core EPS networks by removing the reconfiguration-capacity constraints (Eq. 5) from the LP relaxation and replacing the OCS-specific lower bounds k TLB (·) and TLB (·), and ignoring reconfiguration delay δ (i.e., δ = 0). The overall three-stage algorithm framework remains unchanged: coflows are first ordered globally, then flows are allocated across cores, and finally each core schedules its allocated traffic independently. Consider an H-core EPS network, where each core h ∈ H = {1, provides per-port transmission rate rh . Let P ..., H} h h R = h∈H r and rmax = maxh∈H r . For any demand h matrix Dm allocated to core h, define the single-core lower ρhm h h ≜ rh , and define the global EPS bound of EPS as T LB Dm ∗ lower bound as T LB (Dm ) ≜ ρRm [28]. Let T m denote the
completion time of coflow Cm in an optimal schedule for the multi-core EPS network. Theorem 2. Algorithm 1 (EPS variant) achieves a (4H + 1)-approximation for minimizing P the weighted CCT M in a multi-core EPS network, i.e., ≤ m=1 wm T m PM ∗ (4H + 1) m=1 wm T m . Proof: The ordering-phase prefix analysis remains valid with only the transmission-capacity constraints, yielding ρ1:m ≤ 2RTbm , where Tbm denotes the LP completion value of coflow Cm in the EPS ordering LP. Since reconfiguration is absent, the allocation-phase prefix bound becomes ρ1:m h h max T LB D1:m ≤ . (40) h∈H rmax Following the same prefix-based analysis, the completion time of coflow Cm in the EPS setting satisfies ρ1:m h h T m ≤ am + 2 max T LB D1:m ≤ am + 2 h∈H rmax (41) RTbm ≤ am + 4H Tbm . = am + 4 rmax Finally, we can get M X
wm T m ≤ (4H + 1)
m=1
M X
∗
wm T m .
(42)
m=1
This completes the proof. Corollary 2. Algorithm 1 (EPS variant) achieves a 4Happroximation for minimizing the total weighted CCT when all coflows are released at time zero (i.e.,Pam = 0) in a M heterogeneous multi-core EPS network, i.e., m=1 wm T m ≤ PM ∗ 4H m=1 wm T m , where H is the number of EPS cores. V. E XPERIMENTAL E VALUATIONS In this section, we evaluate the performance of the proposed Algorithm 1 through trace-driven simulations based on a realistic Facebook workload. A. Experimental Setup This subsection describes the workload, evaluation metrics, and default parameter settings. Workload: We employ the widely adopted Facebook trace [38], collected from a MapReduce cluster consisting of 3000 machines and 150 racks. This data trace has been extensively used in prior coflow scheduling studies [12], [13], [19], [20], [22], [24], [28]. It contains 526 coflows and is commonly reduced to a 150-port network while preserving the original inter-arrival characteristics. For each coflow, the trace provides receiver-level information, including the set of receivers, the traffic received by each receiver, and the corresponding sender, rather than explicit flow-level demands. To construct the N ×N demand matrix for each coflow, we transform the receiverlevel traffic into sender-receiver flows. Specifically, for each receiver, the total received traffic is distributed pseudo-uniformly among its associated senders, introducing a small random
B. Baseline Solutions To the best of our knowledge, there is currently no prior scheduler specifically designed for multi-coflow scheduling in multi-core OCS networks under the not-all-stop reconfiguration model. We therefore construct representative baselines by replacing or ablating individual components of Algorithm 1 (O URS). • WSPT-ORDER Following prior work [31], considering a heuristic global coflow ordering rule in place of the LPguided ordering of Algorithm 1. Specifically, each coflow Cm is assigned a priority score wm /TLB (Dm ), where TLB (Dm ) = δ + ρRm . Coflows are subsequently sorted in non-increasing order based on this score. This ordering rule prioritizes coflows with higher weights and lower intrinsic service requirements, thereby approximating the weighted shortest-processing-time (WSPT) principle. The inter-core flow allocation and intra-core circuit scheduling procedures remain unchanged from those in Algorithm 1. • SUNFLOW-S Replace the intra-core circuit scheduling module in Algorithm 1 with Sunflow [20] under the notall-stop model. The global coflow order and inter-core flow allocation remain unchanged.
C. Experimental Results We first evaluate the performance of Algorithm 1 under the default setting. We then vary the reconfiguration delay δ and the number of ports N to examine how performance changes. To cover different multi-core network configurations, we consider K = 3, 4, 5 under both imbalanced-rate and balanced-rate settings. Finally, we report the approximation ratios for different values of δ. 1) Performance under the Default Setting: Fig. 3 reports the normalized total weighted CCT and normalized tail CCT (p95/p99) under the default setting, with all results normalized to O URS. LOAD-ONLY increases the normalized total weighted CCT to 1.37×, while the normalized p95 and p99 tail CCT rise to 1.33× and 1.32×, respectively. This confirms that ignoring reconfiguration overhead during intercore allocation leads to inferior flow placements. Replacing the intra-core scheduler with Sunflow (SUNFLOW-S) yields a similar increase in total weighted CCT (1.38×), but causes much more severe tail degradation, with p95 and p99 reaching 2.22× and 2.26×. BvN-S performs the worst, reaching 4.34× normalized total weighted CCT, 6.89× normalized p95, and 7.07× normalized p99. Rates=[10.0, 20.0, 30.0], δ=8.0
Rates=[10.0, 20.0, 30.0], δ=8.0
5
8
4
Norm. Tail CCT
where Tem (LP ) denotes the objective value of the LP relaxation. Default Parameters. Unless stated otherwise, we adopt the following default parameters: (i) number of ports N = 10; (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.
BvN-S Replace the intra-core circuit scheduling module in Algorithm 1 with Birkhoff-von Neumann (BvN) decomposition [36] under the all-stop model. Since BvN decomposition applies to doubly stochastic matrices, the demand matrix must first be transformed into a doubly stochastic form before decomposition is performed. The global coflow order and inter-core flow allocation remain unchanged. • LOAD-ONLY Replace the τ -aware inter-core flow allocation in Algorithm 1 with a load-only policy. Each flow is assigned to the core that minimizes ρk1:m /rk , i.e., the k reconfiguration term τ1:m δ is ignored. The global coflow order and intra-core circuit scheduling remain unchanged. •
Norm. Total Weighted CCT
perturbation to avoid perfectly uniform splitting. Finally, N machines are randomly selected from the trace as servers and mapped to ingress and egress ports, yielding an N -port coflow instance. Performance Metrics: Our primary optimization objective is to minimize P the total weighted coflow completion time M (CCT), given by m=1 wm Tm . We evaluate all schemes using the normalized total weighted CCT , defined as PM wm Tm (A) , NormW (A) ≜ PM m=1 m=1 wm Tm (O URS ) where O URS denotes Algorithm 1. By definition, NormW (O URS) = 1, and a larger value indicates worse performance relative to O URS. In addition, we also report tail CCT statistics, specifically p95 and p99 CCT. These metrics capture the latency experienced by the most delayed coflows and are particularly useful for reflecting the impact of inter-core contention, port conflicts, and reconfiguration overhead on long-tail performance. Finally, to quantify the gap between practical performance and the theoretical worst-case guarantee, we report the approximation ratio of O URS, defined as PM m=1 wm Tm (O URS ) , Approx ≜ P M e m=1 wm Tm (LP )
3 2 1 0
Norm. p95 Norm. p99
6 4 2 0
OU
RS
WS
ER
RD
-O PT
Y NL
-O
AD LO
S WLO
S
F UN
S
N-
Bv
OU
RS
WS
ER
RD
-O PT
Y NL
-O
AD LO
SU
S WLO
NF
S N-
Bv
Fig. 3: Normalized Total Weighted CCT and Tail CCT (p95/p99) under the Default Setting. Notably, WSPT-ORDER slightly outperforms O URS, achieving 0.92× normalized total weighted CCT. This result is consistent with common workload characteristics in data center networks, where coflow sizes are typically heavy-tailed and flow sizes within each coflow can be highly skewed. In such cases, efficient completion behavior is typically dominated by a small number of large flows, making WSPT-based
SUNFLOW-S
Rates=[10.0, 20.0, 30.0]
1.0
OURS
BvN-S
Rates=[20.0, 20.0, 20.0]
CDF
0.8 0.6 0.4 0.2 0.0
Rates=[5.0, 10.0, 20.0, 25.0]
1.0
Rates=[15.0, 15.0, 15.0, 15.0]
CDF
0.8 0.6 0.4 0.2 0.0 1.0
Rates=[5.0, 5.0, 10.0, 15.0, 25.0]
CDF
0.6 0.4 0.2 0.0 2
3
4
Normalized Value
5
6
6
6
Rates=[12.0, 12.0, 12.0, 12.0, 12.0]
0.8
1
Norm. Total Weighted CCT
LOAD-ONLY
Norm. Total Weighted CCT
WSPT-ORDER
Norm. Total Weighted CCT
OURS
6
1
2
3
4
Normalized Value
5
6
Fig. 4: CDF of Normalized Weighted CCT for K = 3, 4, 5.
ordering highly competitive in practice. This observation does not contradict our theoretical results. Our LP-guided ordering method is primarily designed to support the approximation analysis and establish provable worst-case guarantees, whereas the WSPT-based priority rule may better match the structure of these real-world workloads, thereby yielding a slightly lower empirically weighted CCT. 2) Performance Evaluation: To further examine the stability of the relative performance, Fig. 4 presents the CDF of the normalized total weighted CCT under imbalanced and balanced rate settings for K = 3, 4, 5. 3) Impact of Reconfiguration Delay (δ-Sensitivity): Table III evaluates the impact of reconfiguration delay δ = 2, 4, 6, 8, 10, 12 on final performance for K = 3, 4, 5, under both imbalanced and balanced rate settings. Among the baselines, WSPT-ORDER performs closest to O URS, and in some cases even achieves values slightly below 1. In contrast, LOAD-ONLY consistently performs worse, especially under imbalanced-rate settings, confirming that ignoring reconfiguration overhead during inter-core allocation leads to inferior flow placements. BvN-S exhibits the largest performance gap, with its normalized total weighted CCT typically ranging from approximately 3.6× to 5.2×. 4) Impact of the Number of Ports (N -Scaling): Fig. 5 illustrates the normalized total weighted CCT as the number of ports varies over N ∈ {8, 12, 16, 24, 32}, with M = 100 and δ = 8. Overall, across all settings, O URS consistently outperforms LOAD-ONLY, SUNFLOW-S, and BvN-S, while WSPT-ORDER remains the strongest baseline and stays close to O URS. Furthermore, as the number of cores increases, the
WSPT-ORDER
LOAD-ONLY
SUNFLOW-S
BvN-S
Rates=[10.0, 20.0, 30.0]
Rates=[20.0, 20.0, 20.0]
Rates=[5.0, 10.0, 20.0, 25.0]
Rates=[15.0, 15.0, 15.0, 15.0]
Rates=[5.0, 5.0, 10.0, 15.0, 25.0]
Rates=[12.0, 12.0, 12.0, 12.0, 12.0]
4
2
0
4
2
0
4
2
0 8
12
16
24
Number of Ports N
32
8
12
16
24
Number of Ports N
32
Fig. 5: Normalized Total Weighted CCT versus Number of Ports N for K = 3, 4, 5.
advantage of our method over LOAD-ONLY, SUNFLOW-S, and BvN-S becomes more significant. 5) Approximation Ratio versus Reconfiguration Delay: Fig. 6 shows the approximation ratio of O URS under different reconfiguration delay δ, values, for both zero-release and arbitrary-release settings. Two observations are immediately evident. First, the observed approximation ratios are consistently much lower than the proven worst-case guarantees of 8K and 8K + 1. Across all test configurations, the approximation ratios remain within a much narrower range, mostly between 2.5 and 5.0, rather than approaching the corresponding theoretical bounds. This indicates that the approximation guarantees are conservative, primarily providing robustness in the worst case, while the proposed algorithm performs significantly better in practice on representative instances. Second, the approximation ratio under zero-release time is consistently lower than that under arbitrary-release time. This is expected, as introducing release times adds additional time constraints, making the scheduling problem more challenging. 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 inter-core traffic allocation and (ii) the intra-core feasibility constraints
TABLE III: Normalized Total Weighted CCT versus Reconfiguration Delay δ for K = 3, 4, 5. δ
WSPT
LOAD
SUN
δ
BvN
Imbalanced rates: [10, 20, 30] 2 4 6 8 10 12
1.0433 1.0222 0.9221 0.9156 0.9938 0.9259
1.3067 1.4272 1.4343 1.3734 1.4895 1.5980
1.4525 1.4257 1.3453 1.3767 1.4334 1.3290
0.9947 0.9722 0.9512 0.9965 0.9544 0.9639
1.1150 1.0824 1.1293 1.2076 1.1736 1.2806
1.5056 1.3479 1.3904 1.4087 1.4047 1.3850
2 4 6 8 10 12
1.0289 0.9744 0.9720 0.9683 0.9460 0.9542
3.8005 3.8702 4.1295 4.3552 4.3997 4.4360
2 4 6 8 10 12
1.0014 0.9793 0.9558 0.8771 0.9843 0.9488
Approximation Ratio Approximation Ratio
1.2248 1.2630 1.3127 1.3644 1.5260 1.5116
Zero release times Rates=[20.0, 20.0, 20.0]
6
4
2 4
6
8
10
12
Rates=[5.0, 10.0, 20.0, 25.0]
2
4
6
8
10
12
Rates=[15.0, 15.0, 15.0, 15.0]
6
4
2 2
4
6
8
10
12
Rates=[5.0, 5.0, 10.0, 15.0, 25.0]
Approximation Ratio
1.1777 1.4584 1.4905 1.5270 1.4413 1.6088
2
4
6
8
10
12
Rates=[12.0, 12.0, 12.0, 12.0, 12.0]
6
4
2 2
4
6
8
10
Reconfiguration Delay δ
12
1.4508 1.5451 1.5090 1.4803 1.4787 1.4203
1.4542 1.5781 1.5298 1.4022 1.5788 1.5195
(b) K = 4
Rates=[10.0, 20.0, 30.0]
2
SUN
2
BvN
3.6356 4.2780 4.4032 4.4713 4.5854 4.4858
Balanced rates: [15, 15, 15, 15]
(a) K = 3 With release times
LOAD
Imbalanced rates: [5, 10, 20, 25]
3.7783 4.0436 4.0609 4.3356 4.4845 4.3408
Balanced rates: [20, 20, 20] 2 4 6 8 10 12
WSPT
4
6
8
10
Reconfiguration Delay δ
12
Fig. 6: Approximation Ratio versus Reconfiguration Delay δ for K = 3, 4, 5.
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 heterogeneous K-core OCS network, the algorithm achieves an (8K + 1)-approximation for arbitrary release times, and an 8K-approximation when all coflows are released at time zero. These guarantees explicitly capture the impact of core parallelism on the scheduling complexity and provide the provable approximation bounds for multi-coflow scheduling in
3.6922 4.3146 4.4905 4.3379 4.8410 4.8772
δ
WSPT
LOAD
SUN
BvN
Imbalanced rates: [5, 5, 10, 15, 25] 2 4 6 8 10 12
0.9113 0.9831 0.9834 0.9553 0.9671 0.9917
1.0732 1.3271 1.3387 1.4922 1.5511 1.5567
1.5024 1.6377 1.5864 1.5969 1.5683 1.6362
3.6627 4.3848 4.7461 4.8355 4.8308 5.1677
Balanced rates: [12, 12, 12, 12, 12] 2 4 6 8 10 12
1.0741 0.9431 0.9798 0.9393 0.8742 0.8310
1.0858 1.2338 1.2338 1.4397 1.4383 1.4200
1.4734 1.6177 1.5875 1.5784 1.4913 1.5154
3.6548 4.4731 4.7659 4.8658 4.7138 4.7411
(c) K = 5
multi-core OCS networks under asynchronous reconfiguration. We further show that the same algorithm framework can be naturally applied to H-core EPS networks by replacing the OCS-specific lower bounds and setting the reconfiguration delay to zero. In that setting, the resulting EPS variant achieves a (4H + 1)-approximation for arbitrary release times, and a 4H-approximation when all coflows are released at time zero. A promising direction for future research is online scheduling in multi-core OCS networks, where coflows arrive dynamically, and their demand matrices may be only partially observed. The main objective is to develop online algorithms with provable competitive ratios, thereby establishing theoretical foundations for the design of practical system policies. 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. Shafiee and J. Ghaderi, “Scheduling coflows with dependency graph,” IEEE/ACM Transactions on Networking, vol. 30, no. 1, pp. 450–463, 2021.
[7] 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. [8] 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. [9] 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. [10] M. Chowdhury and I. Stoica, “Efficient coflow scheduling without prior knowledge,” ACM SIGCOMM Computer Communication Review, vol. 45, no. 4, pp. 393–406, 2015. [11] 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. [12] 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. [13] 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. [14] 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. [15] 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. [16] 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. [17] 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. [18] 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. [19] 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. [20] 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. [21] 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. [22] 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. [23] 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. [24] 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. [25] 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. [26] 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. [27] 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.
[28] 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. [29] 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. [30] 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. [31] X. Wang, H. Shen, H. Tian, and D. Wang, “Scheduling coflows in multi-core ocs networks with performance guarantee,” arXiv preprint arXiv:2604.08242, 2026. [Online]. Available: https://doi.org/10.48550/arXiv.2604.08242 [32] 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. [33] 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. [34] L. Wang and W. Wang, “Fair coflow scheduling without prior knowledge,” in 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2018, pp. 22–32. [35] B. Tian, C. Tian, B. Wang, B. Li, Z. He, H. Dai, K. Liu, W. Dou, and G. Chen, “Scheduling dependent coflows to minimize the total weighted job completion time in datacenters,” Computer Networks, vol. 158, pp. 193–205, 2019. [36] G. Birkhoff, “Tres observaciones sobre el algebra lineal,” Univ. Nac. Tucuman, Ser. A, vol. 5, pp. 147–154, 1946. [37] 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. [38] “Facebooktrace,” https://github.com/coflow/coflow-benchmark, 2019.