Max-Flow Min-Cost Routing in a Future-Internet with Improved QoS Guarantees

Abstract

A Constrained Multicommodity Maximum-Flow-Minimum-Cost routing algorithm is presented. The algorithm computes maximum-flow routings for all smooth unicast traffic demands within the Capacity Region of a network subject to routing cost constraints. The edge cost can be a distance, reliability, congestion or an energy metric. It is shown that every network has a finite Bandwidth-Cost capacity. The Bandwidth-Distance and the Bandwidth-Energy capacities are explored. The routing algorithm requires the formulation of two Linear Programs (LPs). The first LP finds a multicommodity Maximum-Flow, when the flows are constrained to a sub-graph of the network to enforce cost constraints. The second LP minimizes the routing cost, given that the maximum-flow is fixed. A related Constrained Multicast-Max-Flow-Min-Cost algorithm is also presented, to maximize the throughput of a multicast tree using network coding, subject to routing cost constraints. These algorithms have polynomial-time solutions, whereas traditional multipath routing algorithms can be NP-Hard. The addition of routing cost constraints can significantly reduce the size of the LPs, resulting in faster solutions, with lower edge utilizations and with higher energy efficiencies. The application of these algorithms to route aggregated video streams from cloud data centers in a Future-Internet network, with improved throughput, energy-efficiency and QoS guarantees is presented.