Capillary routing
 | This article was nominated for deletion. The discussion was closed on 23 September 2013 with a consensus to merge the content into the article Multipath routing. If you find that such action has not been taken promptly, please consider assisting in the merger instead of re-nominating the article for deletion. To discuss the merger, please use the destination article's talk page. (September 2013) |
 | This article needs attention from an expert in Computing. Please add a reason or a talk parameter to this template to explain the issue with the article. (February 2009) |
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (August 2009) |
In networking and in graph theory, capillary routing, for a given network, is a multi-path solution between a pair of source and destination nodes. Unlike shortest-path routing or max-flow routing for any network topology only one capillary routing solution exists.
Capillary routing can be constructed by an iterative linear programming (LP) process transforming a single-path flow into a capillary route. First minimize the maximal value of the load of all links by minimizing an upper bound value applied to all links. The full mass of the flow will be split equally across the possible parallel routes. Find the bottleneck links of the first layer (see below) and fix their load at the found minimum. Minimize similarly the maximal load of all remaining links without the bottleneck links of the first layer. This second iteration further refines the path diversity. Find the bottleneck links of the second layer. Minimize the maximal load of all remaining links, but now without the bottlenecks of the second layer as well. Repeat this iteration until the entire communication footprint is enclosed in the bottlenecks of the constructed layers.
At each layer, after minimizing the maximal load of links, the bottlenecks of the layer are discovered in a bottleneck hunting loop. At each iteration of the hunting loop, we minimize the load of the traffic over all links having maximal load and being suspected as bottlenecks. Links not maintaining their load at the maximum are removed from the suspect list. The bottleneck hunting loop stops if there are no more links to remove.
The animated image shows capillary routing footprint between a pair of nodes in a mobile ad-hoc network.