A distributed depth first search based algorithm for edge connectivity estimation
Yükleniyor...
Tarih
2020
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
IEEE
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
The edge connectivity of a network is the minimum number of edges whose removal disconnect the network. The edge connectivity determines the minimum number of edge-disjoint paths between all nodes. Hence finding the edge connectivity can reveal useful information about reliability, alternative paths and bottlenecks. In this paper, we propose a cost-effective distributed algorithm that finds a lower bound for the edge connectivity of a network via finding at most c depth-first-search trees, where c is the edge connectivity. The proposed algorithm is asynchronous and does not need any synchronization between the nodes. In the proposed algorithm, the root node starts a distributed depth-first-search algorithm, and the nodes select next node in the tree based on their available edges to maximize the total number of established trees. The simulation results show that the proposed algorithm finds the edge connectivity with an average of 48% accuracy ratio.
Açıklama
16th International Conference on Network and Service Management (CNSM) / 2nd International Workshop on Analytics for Service and Application Management (AnServApp) / 1st International Workshop on the Future Evolution of Internet Protocols (IPFuture) -- NOV 02-06, 2020 -- ELECTR NETWORK
Anahtar Kelimeler
Distributed Algorithms, Edge Connectivity, Depth First Search, Spanning Tree, K-Connectivity, Minimum Cut
