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

Abstract

This work proposes the distributed algorithm Multi-Priority Alternative Journey and Routing Protocol (MP-AJRP) for routing in Delay-disruption Tolerant Networks, considering constraints such as links’ bandwidth and nodes’ buffer capacity. The MP-AJRP is an improved version of the AJRP algorithm and its goal is to deliver the largest number of messages to the destinations, considering alternative routes as well as multi-priorities for message scheduling. In order to evaluate the algorithm, several experiments were done using the traces produced with the contact history of the DieselNet nodes. The results showed that MP-AJRP delivered about 76% of messages and had a better performance when compared to certain algorithms that use message replication.

References

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.