Network flow optimization and distributed control algorithms

This thesis concerns the problem of designing distributed algorithms for achieving efficient and fair bandwidth allocations in a resource constrained network. This problem is fundamental to the design of transmission protocols for communication networks, since the fluid models of popular protocols such as TCP and Proportional Fair Controller can be viewed as distributed algorithms which solve the network flow optimization problems corresponding to some fairness criteria. Because of the convexity of the optimization problem as well as its decoupling structure, there exist classical dual algorithm and primal/dual algorithm which are both distributed. However, the main difficulty is the possible instability of the dynamics of these algorithms caused by transmission delays. We use customized Lyapunov-Krasovskii functionals to obtain the stability conditions for these algorithms in networks with heterogeneous time-varying delays. There are two main features of our results. The first is that these stability conditions can be enforced by a small amount of information exchange among relevant users and links. The second is that these stability conditions only depend on the upper bound of delays, not on the rate of delay variations. We further our discussion on scalable algorithms with minimum information to maintain stability. We present a design methodology for such algorithms and prove the global stability of our scalable controllers by the use of Zames-Falb multipliers. Next we extend this method to design the first scalable and globally stable algorithm for the joint multipath routing and flow optimization problem. We achieve this by adding additional delays to different paths for all users. Lastly we discuss the joint single path routing and flow optimization problem, which is a NP hard problem. We show bounded price of anarchy for combined flow and routing game for simple networks and show for many-user networks, simple Nash algorithm leads to approximate optimum of the problem