This research shows that simple distributed algorithms, which essentially emulate physical liquid propagation thru a terrain, can be used to solve multi-commodity flow problem. These algorithms can also be used for packet routing, where no notion of path is used: packets just flow downwards on the virtual terrain and magically reach the destination.
Distributed Multi-commodity flow: circuit model
This research shows that simple distributed algorithms, using essentially gradient descent can compute optimal multi-commodity flow. These algorithms can also be used for circuit routing, where flows converge to final near-optimal flow in a number of parallel phases, so that in each phase shortest path is used by each flow, in the metric which is exponential in the congestion.
This material is based upon work supported by the National Science Foundation under Grant No. 0617883, 0515080, 0240551, 0311795
Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).