Computação Distribuída de Conectividade de Redes de Topologia Arbitrária

Andréa Weber, Elias Procópio Duarte

The Distributed Network Connectivity algorithm allows every node in a general topology network to determine which portions of the network are reachable and unreachable. The algorithm consists of three phases: test, dissemination, and connectivity computation. During the testing phase each link is tested by one of the adjacent nodes at alternating testing intervals. Upon the detection of a new unresponsive link, the tester starts the dissemination phase, in which a distributed breadth-first tree is employed to inform the other connected nodes about the event. At any time, any working node may run the third phase, in which a graph connectivity algorithm shows the network connectivity. We prove bounds on the worst case latency of the algorithm. Simulation results of the dissemination of one event are presented for a number of network topologies, and compared to other algorithms.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: