Theory of Multi-Path Maxmin Rate Allocation

This paper provides a foundation theory for maxim in rate allocation over a communications network. This paper is the first one to provide a comprehensive multi-path and multi-level (due to line 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. This paper also introduces the concepts of over-provisioned links and efficient paths and their inter-relationship with bottlenecks. The results of this paper also show the usefulness of linear programming duality theory in multi-objective lexicographic optimization problem