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.

This work is collaborated with Mung Chiang and Jennifer Rexford (Princeton).

Dr. Dahai Xu is currently a research staff in AT&T Labs. After receiving his Ph.D. degree in Computer Science and Engineering from University at Buffalo in 2005, he spent two years as a postdoctoral research associate in Department of Electrical Engineering at Princeton University. His research interests include Internet design, control and management; Algorithm design and fast implementation; Large-scale non-linear network optimization; Secure communication in wireless ad hoc networks. More information can be found at http://www.research.att.com/~dahaixu/.