Algoritmos Distribuídos para Roteamento em Redes Tolerantes a Atrasos e Desconexões
Resumo
Redes tolerantes a atrasos e desconexões (DTNs) são uma classe de redes que apresentam frequentes partições e longos atrasos. Redes com estas características possuem uma variedade de aplicações como comunicações entre dispositivos com restrições de energia, comunicações rurais, submarinas e interplanetárias. Neste trabalho, nós propomos dois algoritmos distribuídos para roteamento em redes DTN previsíveis, que consideram o menor número de saltos e o tempo de chegada mais cedo ao destino. Eles produzem como saída uma tabela de roteamento para cada nó da rede. Durante a fase de construção da tabela, são realizadas críticas nos intervalos de tempo dos enlaces adjacentes visando minimizar a quantidade de mensagens e bits enviados na rede. Os algoritmos foram avaliados experimentalmente para verificar a redução do número de mensagens trocadas na versão com crítica quando comparada à versão que não realiza crítica nos intervalos. Os resultados mostraram que a crítica reduz significativamente a quantidade de mensagens trafegadas, obtendo um ganho de até 88% para determinadas topologias de rede.
Referências
Chen, C., "Advanced Routing Protocol for Satellite and Space Networks", Master's Thesis, Georgia lnstitute of Technology, 2005.
Ferreira, A., "On Models and Algorithms for Dynamic Communication Networks: The Case for Evolving Graphs". In Proceedings of 4º recontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL2002), pages 155-161, Meze, France, 2002. INRIA Press.
Ferreira, A., Galtier, J., Penna, P., "Topological Desigo, Routing and Hand-over in Satellite Networks", in Handbook o f Wireless Networks and Mobile Computing, I. Stojmenovic, Ed. John Wiley and Sons, 2002, pp. 473-507.
Goldman, A., Monteiro, J., Ferreira, A., " Performance Evaluation of Dynamic Networks using an Evolving Graph Combinatorial Model", 2006.
Hubbel, Y. C., Sanders, L. M., "A Comparison of the IRIDIUM and AMPS systems", IEEE Network, 12(2):52-59, 1997.
Jain, S., Fali, K., Patra, S., "Routing in a Oelay Tolerant Network". In Proceedings of ACM SIGCOMM, 2004.
Jones, E.P.C, Li, L., and Ward, A.A.S., "Practical Routing in Delay Tolerant Networks". In WOTN 2005: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking. New York, NY, USA: ACM Press, 2005, pp. 237-243.
Leopold, R. J., "Low-earth Orbit Global Celular Communications Network". In Proceedings of IEEE International Conference on Communications (ICC), pages 1108-1111, 1991.
Merugu, S., Ammar, M., Zegura, E., "Routing in Space and Time in Networks with Predictable Mobility". Technical Report GIT-CC-04-7, Georgia Institute o f Technology, 2004.
Oliveira, C. T. and Duarte, O. C. M. B. "Uma Análise da Probabilidade de Entrega de Mensagens em Redes Tolerantes a Atrasos e Desconexes", in XXV Simpósio Brasileiro de Redes de Computadores - SBRC'2007, pp. 293-305, Belém, PA, Brasil.
Peleg, D. ., "Distributed Computing: a locality sensitive approach", SIAM Monographs on Discrete Mathematics and Applications 5, 2000.
Perkins, C. E., and Royer, E. M., "Ad-hoc On-demand Oistance Vector Routing", in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), February 1999, pp. 90-100.
"Delay-Tolerant Networking Architecture", RFC4838, 2007.
