Acceleration of distributed minimax flow optimization in networks

摘要

A single commodity network with multiple sources and sinks is modeled by a graph, where a vertex represents a node and a link between two connected nodes is modeled by a weighted edge. The weight of an edge represents the capacity of the link. We provide a distributed method to assign a flow to each link such that the traffic flows generated by the sources reach the sinks while a specific convex cost function, namely the p-norm of the network flow, is minimized. As p ↑ ∞ the flow optimizes the minimax cost function in the network, i.e., the traffic flow is assigned to the links such that the traffic on the most utilized link is minimized, while the network flow is conserved. It is shown that with a given network configuration and channel capacities, the flow allocation based on optimizing the minimax cost function results in the largest set of feasible source traffic rates, i.e., if it is feasible to route a set of sources to a set of destinations in the network, then the minimax flow allocation will achieve it. Our proposed method for finding the optimal flow involves iterations that minimize a quadratic approximation of the cost function in each step. We show that all of the steps for finding the optimal flow can be implemented distributedly, where instead of a centralized network controller, the nodes iteratively use the local state information of their neighbors to update their output flow. We propose an algorithm that accelerates the convergence of iterations significantly, and compare it with other acceleration methods.