LightBlog
Contact at mumbai.academics@gmail.com or 8097636691/9323040215
Responsive Ads Here

Friday, 23 February 2018

A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree(2011)




A Distributed Algorithm for Finding 

All Best Swap Edges of a Minimum 

Diameter Spanning Tree(2011)

ABSTRACT:
            Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network. Most often, the link is restored rapidly. A good policy to deal with this sort of transient link failures is swap rerouting, where the temporarily broken link is replaced by a single swap link from the underlying graph. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. The selection of high quality swap links is essential; it must follow the same objective as the originally chosen communication subnetwork. We are interested in a minimum diameter tree in a graph with edge weights (so as to minimize the maximum travel time of messages). Hence, each swap link must minimize (among all possible swaps) the diameter of the tree that results from swapping. We propose a distributed algorithm that efficiently computes all of these swap links, and we explain how to route messages across swap edges with a compact routing scheme. Finally, we consider the computation of swap edges in an arbitrary spanning tree, where swap edges are chosen to minimize the time required to adapt routing in case of a failure, and give efficient distributed algorithms for two variants of this problem.
Existing System:
            For communication in computer networks, often only a subset of the available connections is used to communicate at any given time. If all nodes are connected using the smallest number of links, the subset forms a spanning tree of the network. This has economical benefits compared to using the entire set of available links, assuming that merely keeping a link active for potentially sending messages induces some cost. Furthermore, as only one path exists between any communication pair, a spanning tree simplifies routing and allows small routing tables. Depending on the purpose of the network, there is a variety of desirable properties of a spanning tree.
Proposed System:
            One downside of using a spanning tree is that a single link failure disconnects the network. Whenever link failures are transient, i.e., a failed link soon becomes operational again, the momentarily best possible way of reconnecting the network is to replace the failed link by a single other link, called a swap link. Among all possible swap links, one should choose a best swap with respect to the original objective that is in our case, a swap that minimizes the diameter of the resulting swap tree. Note that the swap tree is different from a minimum diameter spanning tree of the underlying graph that does not use the failed link. The reason for preferring the swap tree to the latter lies in the effort that a change of the current communication tree requires
SYSTEM REQUIREMENTS SPECIFICATION:
HARDWARE REQUIREMENTS:
Processor                     :           Pentium IV
Ram                               :           512 MB
Hard disk                      :           80 GB
SOFTWARE REQUIREMENTS:
Front End                      :           Java
Operating System       :           Windows XP

No comments:

Post a Comment