Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Approximate Distributed Bellman Ford Algorithms

IP.com Disclosure Number: IPCOM000109417D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 3 page(s) / 176K

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)...