# Approximate Distributed Bellman Ford Algorithms

Original Publication Date: 1992-Aug-01

Included in the Prior Art Database: 2005-Mar-24

## Publishing Venue

IBM

## Related People

Awerbuch, B: AUTHOR [+3]

## Abstract

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. We propose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (< 3). We call these algorithms approximate DBF algorithms. The modifications proposed to the original algorithm are very simple and easy to implement. The message complexity of the first algorithm, called the multiplicative approximate DBF, is O(nmlog(nW)) where W is the maximum length over all edges of an n-nodes m-edges network.

**This text was extracted from an ASCII text file.**

**This is the abbreviated version, containing approximately 42% of the total text.**

Approximate Distributed Bellman Ford Algorithms

Routing
algorithms based on the distributed Bellman-Ford

algorithm (DBF) suffer from exponential message complexity in some

scenarios. We propose two modifications
to the algorithm which

result in a polynomial message complexity without adversely affecting

the response time of the algorithm.
However, the new algorithms may

not compute the shortest path. Instead,
the paths computed can be

worse than the shortest path by at most a constant factor (< 3). We

call these algorithms approximate DBF algorithms. The modifications

proposed to the original algorithm are very simple and easy to

implement. The message complexity of the
first algorithm, called the

multiplicative approximate DBF, is O(nmlog(nW)) where W is the

maximum length over all edges of an n-nodes m-edges network. The

message complexity of the second algorithm, called the additive

approximate DBF, is O( nm) where w is
the minimum length over all

edges in the network. For more details
see (1).

THE DBF ALGORITHM

Let DBF(s,t)
be the distributed Bellman-Ford algorithm that

finds the shortest path in G between s and t.
Refer to (2) for a

detailed description of this algorithm.

Informally,
during the algorithm each node x maintains a label,

a(x), which is the current known shortest distance from s to x, and a

variable parent(x) which contains the identity of its previous node

on the current known shortest path from s to x.
Initially, a(s)=0,

a(x)=B, and parent(x) is undefined for all x * s. When the algorithm

terminates, a(x)=d(s,x); in particular a(t)=d(s,t) which is the

desired value. At this time, parent(x)
contains the identity of the

penultimate node on the shortest path from s to x.

DBF consists
of two basic rules: the adopting rule and the

sending rule. The adopting rule
determines how to update the

current label according to a message from a neighboring node. The

sending rule determines what values to propagate to the neighbors and

is applied whenever a node adopts a new label.

The adopting rule: If x, with a label a(x), receives a'(x) from z, x

adopts a'(x) only if a'(x) < a(x). If
a'(x) is adopted, then the

value of parent(x) is set to z.

The sending rule: Let a(x) be a new label adopted by x and let y1,

... , yl be the neighbors of x other
than parent(x). Then for all 1

& i & 1, x sends a(x)+ l(x,yi) to yi .

THE MULTIPLICATIVE APPROXIMATION

We present
now a parameterized algorithm, called the

multiplicative approximate distributed Bellman Ford and denoted by

MADBF(s,t,a). The parameter a is greater
or equal to 1. This

algorithm returns a path from s to t the length of which is at most

and(s,t). The message complexity of this
algorithm is bounded by

The only difference between MADBF and DBF is in the adopting rule.

The multiplicative adopting rule: If x, with a label b(x), receives

b'(x) from z, then x adopts b'(x) only if If b'(x)...