Achieving minimum-routing-cost maximum-flows in infrastructure wireless mesh networks

A multicommodity Minimum-Cost Maximum-Flow algorithm for routing multiple unicast traffic flows in infrastructure wireless mesh networks, represented as commodities to be routed in an undirected or directed graph, is presented. The routing-cost per edge can be any metric, i.e, a delay, a SNR, etc. To minimize resource-usage and transmission power, the routing-cost is formulated as a Bandwidth-Distance product, where high-bandwidth backhaul flows are routed over shorter distance paths. The routing algorithm requires the formulation of two linear-programming (LP) problems. The first LP performs constrained multicommodity flow maximization, where the traffic flowing between any source/destination pair is constrained to a sub-graph of the original graph to enforce distance constraints. The second LP performs multicommodity cost minimization, under the constraint that the aggregate flow is maximized. Both LPs can be solved in polynomial time. No other multicommodity unicast routing algorithm can achieve a larger Maximum-flow, or the same Maximum-flow rate with a lower cost. The algorithm can also be faster than other known Maximum-Flow algorithms. Given the physical interference model and an appropriate antenna model, every vector of commodity flow-rates within the Capacity Region of an infrastructure network can be scheduled to achieve rigorous throughput and QoS guarantees, using a recently-proposed scheduling algorithm. The algorithm is tested in a hexagonal infrastructure wireless mesh network to maximize backhaul traffic flows.