Dual approach to multi-path maxmin rate allocation

In computer networking, flow control is the process of managing the rate of data transmission between two nodes to efficiently use bandwidth and to prevent congestion between each node. Multi-path Multi-level maxmin rate allocation is the optimal flow control mechanism to achieve fairness and efficiency.; This dissertation provides a fundamental theory for maxmin rate allocation over a communication network. We propose a comprehensive multi-path, multi-level (due to the lexicographic multi-objective nature) optimization theory. The multi-path maxmin problem is orders of magnitude harder than the single-path problem. The main problem is the non-uniqueness of lower level solutions; since higher level solutions depend on lower level solutions, the non-uniqueness makes the problem highly complex. A trading theory to clarify the ambiguous meaning between dual variables and slackness variables in the dual optimality condition is derived. Based on trading theory, a dual approach algorithm to solve multi-path maxmin problems and an extended CPG algorithm which makes maxmin solution less sensitive to network variation are proposed. This dissertation also introduces the concepts of over-provisioned links, efficient paths and their inter-relationship with bottlenecks. The results of this research also show the usefulness of linear programming duality theory in multi-objective lexicographic optimization problem.; There are three possibilities to implement maxmin flow control mechanism: centralized method, distributed centralized method and distributed method. We discuss the pros and cons of each method. Based on relative maxmin, the need of global information is eliminated so that distributed method can be developed. A distributed method is proposed to achieve sub-optimal relative maxmin solution.