CLF: An Online Coflow-Aware Packet Scheduling Algorithm

Literature on coflow-aware packet scheduling for input-queued switches is limited. Yet most of them are offline algorithms, requiring (unrealistic) a priori knowledge of all coflows and solving (time-consuming) linear programming (LP) problems for determining their expected coflow completion times (CCTs). In this paper, we propose an efficient online packet scheduling algorithm called Critical Line First (CLF). In CLF, coflows are ordered based on their easy-to-find ideal CCTs, or would-be-CCTs. In scheduling, coflows with the smallest would-be-CCTs are considered first; for each coflow chosen, packets on most heavily loaded rows/columns, i.e., critical lines, of the coflow traffic matrix are scheduled first. To avoid starvation, we propose to limit the number of times a coflow can be preempted by other coflows. Extensive simulation results show that our CLF outperforms all existing algorithms.