APPROXIMATE DISTRIBUTED BELLMAN-FORD ALGORITHMS

Routing algorithms based on the distributed Bellman-Ford algorithm (DB F) suffer from exponential message complexity in some scenarios. We pr opose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of th e 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 approxim ate DBF algorithms. The modifications proposed to the original algorit hm are very simple and easy to implement. The message complexity of th e first algorithm, called the multiplicative approximate DBF, is O(nml og(nDELTA)) where DELTA is the maximum length over all edges of an n-n odes m-edges network. The message complexity of the second algorithm, called the additive approximate DBF, is O(DELTA/deltanm) where delta i s the minimum length over all edges in the network.