Scheduling Flows on a Switch to Optimize Response Times
Hamidreza Jahanjou, Rajmohan Rajaraman, David Stalfa · 2020
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.