Building Capillary Routing
One approach for building the capillary routing is derived straight from the iterative definition of the capillary routing. With an LP model first minimize the maximal value of the load. Find the bottleneck links of the first layer. Minimize the maximal load of remaining links and identify the bottleneck links of the second layer. Remove the bottleneck links of the second layer and continue the iteration on the remaining links…
In this approach we reach quickly problems with very tiny loads, which make the LP method very sensible to precision errors. It is better to keep the values of parameters and variables always in the same order of grandeur.
In order to keep the values of parameters and variables on the same scale we are applying a different LP method. The routing of a given layer of capillary routing is discovered by increase of the flow (solving the max flow problem) instead of decreasing the maximal value of loads of links. The resulting flows of these two methods are identical except that the proportions are different by the flow increase factor of the max flow solution.
The LP problem of the successive layer is obtained by removal of bottlenecks from the network, producing thus new sources and sinks in the network.
Below is an example of the capillary routing discovery process from the first layer through the max flow solution of the second layer:
|
Initial problem with one source and one sink node |
Maximally increase the flow and adjust the flow out coefficients at nodes |
|
Identify the bottleneck links (dashed) |
Remove the bottleneck links from the network adjusting correspondingly the flow out coefficients at adjacent nodes |
|
Again solve the max flow problem (respecting a
synchronous grow of flows at all sources and sinks) |
Thus if the flow problem of a synchronous multiple-multicast at a layer l is defined as follows:
-
set of nodes 
,
-
set of links 
, where 
and 
, and
-
flow-out values 
for all
And in its max-flow solution:
-
the synchronous flow increase factor for all nodes is 
and
-
the set of bottlenecks is 
(where 
)
Then the new problem of the
successive layer: 
, 
and 
is defined as follows:
-
-
-
After certain number of applications of the max-flow with corresponding modifications of the problem, we will finally obtain a network having no source and sink nodes. At this moment the iteration stops. All links followed by the flow in the capillary routing will be enclosed in bottlenecks of one of the layers.
Only the initial problem (at the layer 1) is definitively a unicast problem. All successive layers, in general are synchronous multiple-multicast problems (a uniform flow from set of sources to set of sinks, where all rates of transmissions by sources and all rates of receptions by sinks are proportional, via each node’s proportionality coefficient, to a single variable), and thus do not belong to the simple class of “network linear programs” [Fourer03].
The absolute flow 
traversing the link 
in the capillary
routing must be computed according the following equation:
where
l is the layer for which
Description of the bottleneck identification was deliberately left for the end of the section, since behind this single phase are hidden solutions to several LP problems. Bottlenecks of each max flow solution are discovered in a bottleneck hunting loop. Each iteration of the hunting loop is an LP cost minimizing problem that reduces the load of traffic over all links being suspected as bottlenecks. Only links maintaining their load high will be passed to the next iteration. Links undergoing to load reduction under the LP objective are removed from the suspect list and the iteration stops if there are no more links reducing their load.