A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*
Abstract & Details
Research Area
COMPUTER SCIENCE AND ENGINEERING
Keywords
MIST
Abstract
Communication in networks suffers if a link fails. When the links are edge of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnect the network. Most often, the link is restored quickly. A good policy to deal with this sort of transient link failures is swap rerouting s, where the temporarily broken link is replaced by a single swap link from the underlying graphs. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. Then 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 advice a distributed algorithm that efficiently computes all of these swap links and we explain, how to route message across swap edges with a compact routing scheme. lastly, we consider the computation of swap edges in an arbitrary spanning tree, where swap edges are chosen to reduce the time required to adapt routing in case of a failures, and give efficient distributed algorithms for two variants of this problem.
License
This work is licensed under a Creative
Commons
Attribution-ShareAlike 4.0 International License.
Author Information
| # | Name | Institute / Affiliation |
|---|---|---|
| 1 | MR. DIPAK GOVARDHAN BHUSARI | ADITYA ENGINEERING COLLEGE, BEED |
| 2 | Mr. Prasad Ramkrishna Kulkarni | Aditya polytechnic college Beed. |
How to Cite
Use the following formats to cite this article in your research.
APA Style
BHUSARI, MR. DIPAK GOVARDHAN & Kulkarni, Mr. Prasad Ramkrishna (2016). A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*. International Journal of Advance Research and Innovative Ideas In Education, 2(4), 922-927.
MLA Style
BHUSARI, MR. DIPAK GOVARDHAN, and Mr. Prasad Ramkrishna Kulkarni. "A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*." International Journal of Advance Research and Innovative Ideas In Education, vol. 2, no. 4, 2016, pp. 922-927.
IEEE Style
MR. DIPAK GOVARDHAN BHUSARI and Mr. Prasad Ramkrishna Kulkarni, "A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*," International Journal of Advance Research and Innovative Ideas In Education, vol. 2, no. 4, pp. 922-927, 2016.
Vancouver Style
BHUSARI MR. DIPAK GOVARDHAN, Kulkarni Mr. Prasad Ramkrishna. A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*. International Journal of Advance Research and Innovative Ideas In Education. 2016;2(4):922-927.
Harvard Style
BHUSARI, MR. DIPAK GOVARDHAN & Kulkarni, Mr. Prasad Ramkrishna (2016) 'A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*', International Journal of Advance Research and Innovative Ideas In Education, 2(4), pp. 922-927.
Chicago Style
BHUSARI, MR. DIPAK GOVARDHAN and Mr. Prasad Ramkrishna Kulkarni. "A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*." International Journal of Advance Research and Innovative Ideas In Education 2, no. 4 (2016): 922-927.
Turabian Style
BHUSARI, MR. DIPAK GOVARDHAN and Mr. Prasad Ramkrishna Kulkarni. "A Distributed Algorithm for Finding All Best Swap Edges Of a Minimum Diameter Spanning Tree*." International Journal of Advance Research and Innovative Ideas In Education 2, no. 4 (2016): 922-927.
Related Research
EduQuest AI: A Gamified Learning Platform for Interactive and Personalized Digital Education
Download PDF
Distributed Real-Time Stream Analytics and Ingestion Engine for High-Velocity Big Data Architectures
Download PDF