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 the shortest path routing or max-flow routing for any network topology only one capillary routing solution exists. The word networking can refer to: the activity of creating, expanding and maintaining networks such as: social networks business networks computer networks For other possible meanings, see network. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...

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. In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ...

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. Capillary routing is invented by Emin Gabrielyan.

External links

Capilary routing documentation