Coflow scheduling and resource sharing games in congested networks

Abstract

This thesis studies a problem at the nexus of network optimization and network economics: how to allocate network resources (e.g., routing paths and link bandwidths) efficiently in congested networks? Motivated by practice, we investigate two specific problems, coflow scheduling in a centralized congested network and competitive behaviors of selfish network entities.

Communication in data-parallel applications often involves a collection of parallel flows. Traditional techniques (e.g., individual flow scheduling) do not perform well in optimizing such collections. Thus, the coflow abstraction was proposed, which is a set of related parallel flows that occur typically between two stages of a task. The first part of the thesis focuses on coflow scheduling in a centrally controlled environment. Firstly, we study routing and scheduling of multiple coflows to minimize the total weighted coflow completion time. We derive an online algorithm called OMCoflow, and prove its competitive ratio. To the best of our knowledge, OMCoflow is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Secondly, we study the routing and scheduling of multiple coflows to maximize the number of coflows that can meet their deadlines. We show the performance bound of this problem and derive another online algorithm, called EarlyCo. Besides their efficiency and effectiveness, we also investigate several important merits of OMCoflow and EarlyCo such as ease of implementation, scalability and work conservation.

In the second part of the thesis, through the noncooperative game framework, we study the competitive behaviors of selfish entities sharing the network resources. Firstly, we investigate the problem to route a given set of selfish tasks in hybrid networks, where wired and wireless links are synergistically mixed together to achieve flexibility and reliability. The competitive behaviors of selfish agents are modeled as a noncooperative game, which is proved to be ordinal potential, and the existence of a pure-Nash Equilibrium (pure-NE) is therefore guaranteed. We also design a routing scheme to achieve a pure-NE for all the agents. Secondly, motivated by possible agent and resource failures, we study two models of congestion games with failures. The first is congestion games with both resource and agent failures, called CG-RAF, where each agent chooses several resources with the minimum expected cost. The second is congestion games with only correlated resource failures, called CG-CRF, where resources are provided in packages, and their failures can be correlated with each other. Each agent will choose multiple packages for reliability’s sake and utilize the survived one with the minimum cost. We analyze the important properties of these two games including the existence of pure-NE and its efficiency. Finally, we discuss various applications of CG-RAF and CG-CRF in the networking field. To the best of our knowledge, this is the first work that studies congestion game with both resource and agent failures.