Capillary routing

Capillary routing

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.

External links

* [http://switzernet.com/people/emin-gabrielyan/060129-capillary-documentation/ Capilary routing documentation]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Voice over IP — Digital voice redirects here. For the commercial service, see Comcast Digital Voice. Voice over Internet Protocol (Voice over IP, VoIP) is a family of technologies, methodologies, communication protocols, and transmission techniques for the… …   Wikipedia

  • Voice over Internet Protocol — (VoIP, IPAEng|vɔɪp) is a protocol optimized for the transmission of voice through the Internet or other packet switched networks. VoIP is often used abstractly to refer to the actual transmission of voice (rather than the protocol implementing… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Fault-tolerant design — In engineering, Fault tolerant design, also known as fail safe design, is a design that enables a system to continue operation, possibly at a reduced level (also known as graceful degradation), rather than failing completely, when some part of… …   Wikipedia

  • Fault-tolerant system — This article contains specific implementations of fault tolerant systems. For general theory, see fault tolerant design. Fault tolerance or graceful degradation is the property that enables a system (often computer based) to continue operating… …   Wikipedia

  • Failure transparency — In a distributed system, failure transparency refers to the extent to which errors and subsequent recoveries of hosts and services within the system are invisible to users and applications.huh For example, if a server fails, but users are… …   Wikipedia

  • human cardiovascular system — ▪ anatomy Introduction       organ system that conveys blood through vessels to and from all parts of the body, carrying nutrients and oxygen to tissues and removing carbon dioxide and other wastes. It is a closed tubular system in which the… …   Universalium

  • hydrologic sciences — Introduction       the fields of study concerned with the waters of the Earth. Included are the sciences of hydrology, oceanography, limnology, and glaciology.       In its widest sense hydrology encompasses the study of the occurrence, the… …   Universalium

  • photoengraving — /foh toh en gray ving/, n. 1. a photographic process of preparing printing plates for letterpress printing. 2. a plate so produced. 3. a print made from it. [1870 75; PHOTO + ENGRAVING] * * * Any of several processes for producing printing plates …   Universalium

  • Centrifugal Micro-fluidic Biochip — The centrifugal mico fluidic biochip or centrifugal micro fluidic biodisk is a type of lab on a chip technology that can be used to integrate processes such as separating, mixing, reaction and detecting molecules of nano size in a single piece of …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”