24-01-2013, 04:45 PM
Always Acyclic Distributed Path Computation
1Always Acyclic.doc (Size: 189.5 KB / Downloads: 33)
Abstract:-
Distributed routing algorithms may give rise to transient loops during path recomputation, which can pose significant stability problems in high-speed networks. We present a new algorithm, Distributed Path Computation with Intermediate Variables (DIV), which can be combined with any distributed routing algorithm to guarantee that the directed graph induced by the routing decisions remains acyclic at all times. The key contribution of DIV, besides its ability to operate with any routing algorithm, is an update mechanism using simple message exchanges between neighboring nodes that guarantees loop-freedom at all times. DIV provably outperforms existing loop-prevention algorithms
in several key metrics such as frequency of synchronous updates and the ability to maintain paths during transitions. Simulation results quantifying these gains in the context of shortest path routing are presented. In addition, DIV’s universal applicability is illustrated by studying its use with a routing that operates according to a nonshortest path objective. Specifically, the routing seeks robustness against failures by maximizing the number of next-hops available at each node for each destination.
Algorithm Explanation:
The two algorithms: (i) link-state algorithms (also known as topology broadcast) and (ii) distance-vector algorithms .In both approaches, nodes choose successor (next-hop) nodes for each destination based only on local information, with the objective that the chosen paths to the destination be efficient in an appropriate sense e.g., having the minimum cost. Because end-to-end paths are formed by concatenating computational results at individual nodes, achieving a global objective implies consistency across nodes both in computation and in the information on which those computations are based.
Example:
Time-to-Live (TTL) field in packet headers or a TTL set to a large value. In the presence of a routing loop, a packet caught in the loop comes back to the same nodes repeatedly, thereby artificially increasing the traffic load many folds on the affected links and nodes. The problem, a significant issue even with unicast packets,
Proposed System:
Link-state algorithms, of which the OSPF protocol is a well-known embodiment; disseminate the state of each node’s local links to all other nodes in the network by means of reliable flooding. After receiving link-state updates from the rest of the nodes, each node independently computes a path to every destination. The period of potential information inconsistency across nodes is small so that routing loops, if any, are very short-lived. On the flip side, link-state algorithms can have quite high overhead in terms of communication storage, and computation. These are some of the reasons for investigating alternatives as embodied in distance-vector algorithms, which are the focus of this paper.
Robust Routing Module:
We illustrate the benefits of this decoupling using a cost function that instead of the standard shortest path distance function, seeks to maximize the number of next-hops available at all nodes for each destination. The availability of multiple next-hops ensures that the failure of any one link or neighbor does not impede a node’s ability to continue forwarding traffic to a destination. A failure results in the loss of at most one next hop to a destination, so that the node can continue forwarding packets on the remaining ones without waiting for new paths to be computed. In other words, the routing is robust to local failures. This may be an appropriate objective in settings where end-to-end latency is small and bandwidth plentiful,