Multi-Priority Alternative Journey and Routing Protocol: um Algoritmo para Roteamento em Redes Tolerantes a Atrasos e Desconexões Previsíveis

• Gabriel Argolo UFF
• Lúcia M. A. Drummond UFF
• Anna Dolejsi UFF
• Anand Subramanian UFF

DOI: https://doi.org/10.5753/wtf.2010.23103

Resumo

Este trabalho propõe o algoritmo distribuído Multi-Priority Alternative Journey and Routing Protocol (MP-AJRP) para roteamento em Redes Tolerantes a Atrasos e Desconexões, considerando as restrições de largura de banda dos enlaces e de capacidade dos buffers dos nós. O MP-AJRP é uma versão aprimorada do algoritmo AJRP e tem como objetivo entregar o maior número de mensagens aos destinos considerando rotas alternativas e múltiplas prioridades para escalonamento de mensagens. Com o intuito de avaliar o algoritmo, foram realizados experimentos utilizando os traces com o histórico de contatos dos nós da rede DieselNet. Os resultados mostraram que o MP-AJRP entregou em torno de 76% das mensagens e obteve desempenho superior a determinados algoritmos que consideram a replicação de mensagens.

Referências

Argolo, A., Dolejsi, L. D. A., E.Uchoa, e Subramanian, A. (2009). Roteamento em redes tolerantes a atrasos e desconexões com restrições de buffer e largura de banda. In XLI Simpósio Brasileiro de Pesquisa Operacional.

Balasubramanian, A., Levine, B., e Venkataramani, A. (2007). Dtn routing as a resource allocation problem. In ACM SIGCOMM, pages 373–384.

Bui-Xuan, B., Ferreira, A., e Jarry, A. (2003). Evolving graphs and least cost journeys in dynamic networks. In Modeling and Optimization in Mobile, Ad-Hoc, and Wireless Networks, pages 141–150.

Burgess, J., Gallagher, B., Jensen, D., e Levine, B. N. (2006). Maxprop: Routing for vehicle-based disruption-tolerant networks. In IEEE Infocom, pages 1–11.

Cerf, V. (2007). Rfc 4838: Dtn architecture. Technical report, IETF.

Chen, C. (2005). Advanced routing protocol for satellite and space networks. Master’s thesis, Georgia Institute of Technology.

Jain, S., Fall, K., e Patra, S. (2004). Routing in a delay tolerant network. In ACM SIG-COMM, pages 145–158.

Lindgren, A., Doria, A., e Schelén, O. (2004). Probabilistic routing in intermittently connected networks. In SAPIR Workshop, pages 239–254.

Merugu, S., Ammar, M., e Zegura, E. (2004). Routing in space and time in networks with predictable mobility. Technical report, Georgia Institute of Technology.

Oliveira, C. T. e Duarte, O. C. M. B. (2007). Uma análise da probabilidade de entrega de mensagens em redes tolerantes a atrasos e desconexões. In XXV Simpósio Brasileiro de Redes de Computadores, pages 293–305.

Oliveira, E. C. R. e Albuquerque, C. V. N. (2009). Nectar: A dtn routing protocol based on neighborhood contact history. In 24th ACM Symposium on Applied Computing, pages 359–365.

Peleg, D. (2000). Distributed Computing: a locality-sensitive approach (Monographs on Discrete Mathematics and Applications). Society for Industrial Mathematics.

Ramanathan, R., Basu, P., e Krishnan, R. (2007). Towards a formalism for routing in challenged networks. In ACM MobiCom workshop on Challenged Networks, pages 3–10.

Santos, A., Rocha, G., Drummond, L., e Gorza, M. (2008). Algoritmos distribuídos para roteamento em redes tolerantes a atrasos e desconexões. In Workshop em Sistemas Computacionais de Alto Desempenho, pages 35–42.

Spyropoulos, T., Psounis, K., e Raghavendra, C. S. (2005). Spray and wait: An efficient routing scheme for intermittently connected mobile networks. In ACM WDTN, pages 252–259.

Vahdat, A. e Becker, D. (2000). Epidemic routing for partially connected ad hoc networks. Technical report, Duke University.