The classical multi-commodity problem is to minimize a convex objective function of link utilizations for a given set of traffic demands. An open problem is whether and how to realize its optimal solution using a destination-based, hop-by-hop forwarding, where each node independently determines traffic splitting across its outgoing links based on a global view of link weights. It has been known that solving a dual problem of the multi-commodity problem results in a set of link weights such that all the traffic will be routed along the shortest paths to the destination. However, these link weights are not useful in practice because they do not enable the nodes to determine how to split traffic over multiple shortest paths. In this work, we show that splitting traffic over multiple paths as an exponential function of path length can achieve the optimal distribution of traffic. The result is based on our new Network Entropy Maximization framework for routing-protocol design.
Copyright. All Rights Reserved.