Show simple item record

dc.contributor.advisorDuarte Junior, Elias Procópiopt_BR
dc.contributor.authorCestari, José Marcelo Almeida Pradopt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informáticapt_BR
dc.date.accessioned2017-10-10T17:05:55Z
dc.date.available2017-10-10T17:05:55Z
dc.date.issued2001pt_BR
dc.identifier.urihttp://hdl.handle.net/1884/48819
dc.descriptionOrientador: Elias Procópio Duarte Jrpt_BR
dc.descriptionDissertação (mestrado) - Universidade Federal do Paranápt_BR
dc.description.abstractResumo: Neste trabalho é apresentado um novo algoritmo para o diagnóstico distribuído de redes de topologia arbitrária baseado no algoritmo do Carteiro Chinês. Um agente móvel, isto é, um processo que é executado e transmitido entre os nodos da rede, percorre seqüencialmente todos os enlaces, de acordo com o caminho determinado pelo algoritmo do Carteiro Chinês. O agente, chamado Agente Chinês, vai testando os enlaces detectando novos eventos e disseminando as informações obtidas para os demais nodos da rede. Quando todos os nodos do sistema recebem a informação sobre um evento, o diagnóstico se completa. Neste trabalho assume-se que falhas não particionam a rede, e que um novo evento só ocorre após o diagnóstico do evento anterior. São apresentadas provas rigorosas do melhor e pior caso da latência do algoritmo, isto é, o tempo necessário para completar um diagnóstico. São apresentados também resultados experimentais obtidos através da simulação do algoritmo em vários tipos diferentes de topologia, dentre eles, hipercubos de 16, 64 e 128 vértices, grafo D 1,2 com 9 vértices, além de um grafo randômico com 50 vértices e probabilidade de aresta igual a 10%, e a topologia da Rede Nacional de Pesquisa (RNP). São simuladas falhas de um enlace em cada grafo, são medidos o número de mensagens geradas e o tempo necessário para que o diagnóstico se complete. Os resultados indicam que o tempo necessário para realizar o diagnóstico é, na média, menor que o pior caso apresentado, e que o número de mensagens disseminadas é freqüentemente menor que o requerido por outros algoritmos semelhantes.pt_BR
dc.description.abstractAbstract: This work presents a new algorithm for distributed diagnosis of general topology networks. A mobile agent visits all links sequentially, following the path generated by the Chinese Postman algorithm. The agent, called Chinese Agent, tests the links detecting new events and disseminates event information to the rest of the network. When all nodes of the system receive the information about the event, the diagnosis is complete. This work assumes that faults do not partition the network, and that a new event only occurs after the previous event has been diagnosed. Rigorous proofs of the best and the worst case of the latency of the algorithm are presented. Experimental results are also presented which were obtained from the simulation of the algorithm on different types of topologies, like hypercubes with 16, 64 and 128 nodes, the D 1,2 graph with 9 nodes, a random graph with 50 nodes and link probability equal to 10%, and the Brazilian National Research Network (RNP) topology. One link fault is simulated in each graph, both the number of messages and the algorithm's latency were measured. The results show that the time necessary to complete the diagnosis is, in average, smaller than the worst case. A comparison with other algorithms shows that the number of messages generated by the proposed algorithm is frequently smaller than the number of messages required by others similar algorithms.pt_BR
dc.format.extent92 f. : grafs. ; 30cm.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.relationDisponível em formato digitalpt_BR
dc.subjectTesespt_BR
dc.subjectAlgoritmos de computadorpt_BR
dc.subjectRedes locais de computaçãopt_BR
dc.subjectProcessamento eletronico de dados - Processamento distribuidopt_BR
dc.subjectCiencia da Computaçãopt_BR
dc.titleUma abordagem distribuída baseada no algoritmo do carteiro chinês para diagnóstico de redes de topologia arbitráriapt_BR
dc.typeDissertaçãopt_BR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record