Gafni-Bertsekas

The link-reversal routing protocol invented by Eli M. Gafni and Dimitri P. Bertsekas in 1981 [Gafni1981] has been designed for packet-radio networks, where routes should be maintained among mobile nodes to a central station. The algorithm was meant to work proactively. The elegant principle of the link-reversal distributed algorithms has become the basis for other routing algorithms such as LMR or TORA.

Changes in network topology should only affect local nodes and so reduce protol overhead. It also makes little sense to try to maintain a shortest path to a destination in networks where the topology changes rapidly. Instead it may be better to try to have any route to a destination , even if this is not an ideal one. Why not have even multiple possible routes to a given destination and so provide redundancy?

Link reversal routing algorithms are based on a principle known from graph theory. The distributed algorithm tries to maintain a "directed acyclic graph" which is destination oriented. It does so by reversing edge directions in the graph when needed. There is one such DAG for every destination and this graph is called "destination oriented" when there is only one vertex (node) which has no outgoing edge. This node must be the destination.

A graph is acyclic, when one can find no path through it that leads twice through the same vertex. In fact a directed acyclic graph is also a tree. Thought as a tree the destination, the sink, would be the base of the tree.

It can easily be proven that a DAG must have a sink which is the destination where we want to route to:

1. Suppose a DAG had no sink.
2. if we pick any node e.g. v1 out of the DAG
3. since the node we picked is no sink (see 1.) it must have an outgoing edge to another node, say (v1,v2)
4. if we consider this node v2 now. Because of 1. v2 is also no sink and must have an outgoing edge to another node
5. the focus on our last assumption is the word "another". If the outgoing edge would lead us to a previous node we would have discovered a cycle.
6. But the number of nodes in a graph must be finite and we can't go on forever by connecting to a new node without causing a cycle.
7. So clearly if we stop somewhere there must be a node which has no outgoing edge: the sink of our DAG.

So what the distributed algorithm does is to reverse the direction of links at nodes which have lost their last downstream neighbour (=outgoing edges). There are two flavours of doing this: full reversal and partial reversal.

The full reversal method

In the DAG below node #6 has lost its downstream link (ignore the numbers for now, they will explained below)

Iteration 1: Node 6 causes a reversal of the remaining edges

Iteration 2:

Iteration3:

Iteration 4: The graph is now again a destination oriented DAG

Implementation
Every node has a table which constains the tuples {a(i);i} and a list of downstream node's ids for every destination. There is one such a tuple for every destination, so for every DAG. Over the whole DAG the tuples shall be maintained in lexigrographical order. The destination oriented DAG constitutes a totally ordered set. An edge from i to j is a downstream edge if the tuple {a(i);i} has a higher lexicographical position than {a(j);j}, an upstream link otherwise. Since i is the id of the node, there can not be twice the same tuple in the graph.

If a node loses its last downstream link for a given destination it sets a(i) to the highest value of all its neighbours a-values plus 1. This is in fact the reversal of all the edges to the neighbours.

The tuple {a(i);i} can be considered as a measure for the "height" of a node. Analogous to water the communication to a destination flows always downstream and the destination node is always the deepest point.

The partial reversal method

Rather than reversing all the edge directions to the neighbours, only the edges which have not been recently reversed are reversed. A node remembers which links have been reversed the last iteration and only reverses the links which have not been reversed recently.

Link from 6 to destination gets broken

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Implementation
The implementation could be list-based or based on the concept of heights described below:[`Vainio2002`]

Each node has a table of triples (a,b,i) for itself (i) and its neighbours. A lexicographical order again determines the topology of the DAG for every destination.

If (a(i),b(i),i) lexicographically smaller than (a(j),b(j),j):

a(i) gets (the minimum from all the neighbour's a(n)) + 1
b(i) gets:
- (the minimum of all the neighbour's b(n)) - 1, if a(i) would be equal to a neighbours a(n) after this iteration
- otherwise it will be left unchanged

The result is again the maintainance of a totally ordered set which results in a DAG which is destination oriented.

Performance considerations

Unfortunately both algorithms won't converge if the network gets partitioned. The links in the network partition that got disconnected from the destination would reverse forever, as shown below:

The time complexity of the algorithm depends on twice the longest connected path in the affected network segment. The communication complexity (number of messages exchanged) depends on the longest connected path times the maximum connectivity times the number of nodes affected by a topological change. [Vainio2002]

If there wasn't the problem with the disconnected network portion, the GB-algorithms would behave well in a highly connected network with medium to high mobility.

A topological change has only local effects, so there are no routing messages which travel through big portions of the network. Each node has to know only about its neighbours for a given destination. An action gets only triggered by a violation of the global ordering. Links that remain part of the destination-oritented DAG never participate in teh link reversal process. The idea of a DAG ensures loop-free routes every time. Routes may be redundant (multiple routes to one destination), which increases reliability of packet delivery.

It has been assumed above, that the communication between the nodes was reliable. So there has to be an underlying link level protocol to ensure this. (because of hidden and exposed terminal issue)

References