Capillary Routing

Already its name suggests that this is a kind of dispersed communication flow covering numerous paths. The definition of the capillary routing and its layers is in the description of an iterative process transforming a simple flow into a capillary routing.

Capillary routing discovers the alternate paths by delegating the load of a single path route to other links. It also reaches the load balance by minimizing the upper bound value of the flow for all links. In the first layer the full mass of the flow is broken across a few parallel highways. The parallelization (spreading) factor at the first layer is an integer. If there are places where the entire traffic must pass through a single link the spreading factor will be one.

The shortest path solution

After application of the objective discovering the first layer

By maintaining the flow below the upper bound obtained in the first layer, further equilibration is being applied to the remaining portion of the flow. The remaining flow is additionally equilibrated by minimizing the value of the second upper bound applied on all links still maintaining a degree of freedom (links that are not the bottlenecks of the previous layer).

The new objective (with the constraints maintaining the previous objective) discovers the footprint of the second layer of the capillary routing

Thus we discovered the main routes of the second layer. The second layer’s upper bound is added as an additional constraint (always maintaining the first constraint) and the discovering of the successive layers is continued. The capillary routing discovery is continued iteratively until the entire footprint of the flow is discovered and completely equilibrated.

Let us build the capillary routing, layer by layer on the network of the below example with 7 nodes. The top node of the diagram is the sending node and the bottom node is the receiving node. All links has descending direction.

We will compute also the ARON rating for each layer of the capillary routing assuming Shannon capacity and that the stream constantly tolerates 10% of packet losses.

	link	load	redundancy need
	1	0.5	0.8
	2	0.5	0.8
	3	0.5	0.8
	4	0	0
	5	0	0
	6	0.5	0.8
	7	0	0
	8	0	0
	9	0.5	0.8
			ARON=4

In the first layer of the capillary routing we reduce the load of bottleneck links 1 and 2 to their minimal value of . Links 3, 6 and 9 are not bottleneck links and their loads can be further delegated to other links. The ARON rating of the first layer is equal to 4.

	link	load	redundancy need
	1	0.5	0.8
	2	0.5	0.8
	3	0.333333	0.35
	4	0.166667	0.08
	5	0.166667	0.08
	6	0.333333	0.35
	7	0	0
	8	0.333333	0.35
	9	0.333333	0.35
			ARON=3.16

In the second layer we reduce the load of the current bottleneck links 6, 8, and 9 to their minimal value of . The ARON rating of this layer is now 3.16. Link 3 is not a bottleneck link, and its load can be further delegated over link 4.

	link	load	redundancy need
	1	0.5	0.8
	2	0.5	0.8
	3	0.25	0.2
	4	0.25	0.2
	5	0.166667	0.08
	6	0.333333	0.35
	7	0.083333	0
	8	0.333333	0.35
	9	0.333333	0.35
			ARON=3.13

In the third layer we equilibrate the bottlenecks of the current layer, links 3 and 4. Their load is reduced to .

In the last solution the load of link 5 is and the load of link 7 is . There is no freedom left for the flow after the solution of the third layer, so if we follow the layering, link 5 will be the only bottleneck link of the forth layer with its load of and link 7 will be the only bottleneck of the fifth last layer with its load of .

Progress of the capillary routing through its first three layers is shown in the plot below.

In the figure below we present an example of the capillary routing on a network with 120 nodes. We present first four layers of the capillary routing, i.e. four routing suggestions on the same network. In the first layer the flow is following two paths, thus the load for the first layer is 0.5 (see the information bar on the left from the plots). Solid lines on the path are marking the links, which are the bottlenecks of the layer, paths in dashed lines, are the links with a degree of freedom (whose load can be further delegated). The flow follows a spreader path in the second layer, whose links carry no more than of the traffic, except the bottleneck links of the first layer. The 3^rd layer is yet more spreader and its links, except the few bottleneck links of the first and second layers, are carrying not more than of the traffic (follow the vertical information bar on the left side of the figure). Although only four layers are visualized, the capillary routing is computed for first 10 layers, and the loads of the layers are displayed in the vertical information bar. The entire network contains 950 links, which are not shown if no flow is routed through them. 91 is the total number of all bottleneck links in all 10 layers.

In [Ma03] it’s been studied concept of hop-by-hop packet recovery with packet level FEC. In this study, the author simplified the network topology into two categories: (i) parallel and (ii) serial connection of links, assuming that a link can be abstracted into a sub-network without connectivity to other links (sub-networks). However contrary to the author’s belief the generality of this routing model suffers noticeably from such simplifications. Topologies not fitting into the model of the author are especially frequent in a uniform network environment, such as MANET, which is precisely a subject of a study of the author (the above example of a network with 120 nodes is a snapshot of MANET as well).

In the below diagram where a is the sending node and b is the receiving node the underlying network is a small example of the topology which is not fitting in the model of [Ma03]. Network is a symmetric directed graph, each line representing a pair of opposed arcs. The network cannot be represented simply via a sequence of parallel and serial links.

It becomes obvious, when we define different objectives on the same network. When we seek for the shortest path flow, we obtain a single path routing carrying the entire flow (the figure below).

Shortest path solution

Max-flow solution

In the max-flow objective over the same network with the same peers, the flow however may even follow on certain links, a direction opposite to that of the shortest path solution (the link between the two middle nodes of the shortest path).