We investigate offline and online algorithms for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ without the NBA. We first study offline $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ for a restricted class of instances, called $$\alpha $$ -small, where the size of each flow is at most $$\alpha $$ times the capacity of its bottleneck edge, and present an $$O(\log (1/(1-\alpha )))$$ -approximation algorithm. Next, our main result is an online $$O(\log \log c_{\max })$$ -competitive algorithm for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ where $$c_{\max }$$ is the largest edge capacity, improving upon the previous best bound of $$O(\log c_{\max })$$ due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline $$O(\min (\log n, \log m, \log \log c_{\max }))$$ -approximation algorithm and an online $$O(\min (\log m, \log \log c_{\max }))$$ -competitive algorithm for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ , where n is the number of flows and m is the number of edges.

We study the scheduling of flows on a switch with the goal of optimizing metrics related to the response time of the flows. The input is a sequence of flow requests on a switch, where the switch is represented by a bipartite graph with a capacity on each vertex (port), and a flow request is an edge with associated demand. In each round, a subset of edges can be scheduled under the constraint that the total demand of the scheduled edges incident on any vertex is at most the capacity of the vertex. This class of scheduling problems has applications in datacenter networks, and has been extensively studied. Previous work has essentially settled the complexity of metrics based on completion time. The objective of average or maximum response time, however, is more challenging. To the best of our knowledge, there are no prior approximation algorithms results for these metrics in the context of flow scheduling.

Many modern datacenter applications involve large-scale computations composed of multiple data flows that need to be completed over a shared set of distributed resources. Such a computation completes when all of its flows complete. A useful abstraction for modeling such scenarios is a coflow, which is a collection of flows (e.g., tasks, packets, data transmissions) that all share the same performance goal. In this paper, we present the first approximation algorithms for scheduling coflows over general network topologies with the objective of minimizing total weighted completion time. We consider two different models for coflows based on the nature of individual flows: circuits, and packets. We design constant-factor polynomial-time approximation algorithms for scheduling packet-based coflows with or without given flow paths, and circuit-based coflows with given flow paths. Furthermore, we give an O(log n/log log n)-approximation polynomial time algorithm for scheduling circuit-based coflows without given flow paths (here n is the number of network edges).