Coflow Scheduling Based on Line Graph Theory

Cooperative Flows (Coflow) is a set of usually independent flows which are related to each other as part of a computation process. Hence, the coflow completion depends on the completion of its corresponding flows that are dependent to each other. Due to the independency of flows from each other, they can be executed in any order. Such property of flows in one coflow leads us towards designing algorithms for flow scheduling within a coflow. A proper scheduling algorithm can decrease coflow completion time or Coflow Completion Time (CCT). A lot of algorithms have been proposed which decrease execution time of coflows. Most of them use Linear Programming (LP) as an optimization method to define the scheduling problem formally for small scale network topologies and then propose a heuristic algorithm to solve the larger scale networks. In this paper we propose an algorithm to schedule coflows based on line graph theory. Using line graph and vertex coloring algorithms we can color independent edges with the same color, recalling that the edges in line graph represent the nodes in original graph that can be selected to send/receive data independently and simultaneously.

کلیدواژه ها:

flow scheduling ، coflow scheduling ، optical switches ، datacenter ، the graph theory