Algoritmos Distribuídos para Roteamento em Redes Tolerantes a Atrasos e Desconexões

  • Anna Dolejsi Santos UFF
  • Gabriel Argolo M. Rocha UFF
  • Lúcia M. A. Drummond UFF
  • Melba Lima Gorza UFF

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

Bui-Xuan, B., Ferreira, A., Jarry, A., "Evolving Graphs and Least Cost Journeys in Oynamic Networks", in Proceedings of WiOpt - Mode ling and Optimization in Mobile, Ad-Hoc, and Wireless Networks. INRIA Press, March 2003, pp. 141-150.

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.
Publicado
29/10/2008
SANTOS, Anna Dolejsi; ROCHA, Gabriel Argolo M.; DRUMMOND, Lúcia M. A.; GORZA, Melba Lima. Algoritmos Distribuídos para Roteamento em Redes Tolerantes a Atrasos e Desconexões. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 9. , 2008, Campo Grande. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2008 . p. 35-42. DOI: https://doi.org/10.5753/wscad.2008.17665.