Roteamento Tolerante a Falhas Baseado em Caminhos Robustos
Resumo
Protocolos de roteamento apresentam uma latência, isto é, um intervalo de tempo para atualizar suas tabelas de rotas em toda a rede, após uma alteração na topologia. Esta latência de convergência pode gerar potenciais perdas de pacotes ou conexões na rede. Este trabalho propõe uma estratégia para roteamento dinâmico, permitindo que roteadores intermediários que possuam informações mais recentes de alterações na topologia interfiram no caminho utilizado. Este roteamento é baseado em caminhos robustos, escolhidos utilizando critérios de conectividade, que valorizam a redundância de caminhos. Uma comparação de resultados experimentais obtidos através de simulação da abordagem baseada nestes caminhos com uma seleção de caminhos por Dijkstra, em um ambiente sujeito a falhas, demonstra que as alterações de caminho feitas em caminhos robustos são 40% menores que as encontradas por Dijkstra.Referências
J. Chandrashekar, Z. Duan, Z. L. Zhang, and J. Krasky. Limiting path exploration in BGP. disponível em http://www-users.cs.umn.edu/~jaideepc/papers/epic-tr.pdf.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, second edition, 1990.
E. P. Duarte Jr., R. Santini, and J. Cohen. Delivering packets during the routing convergence latency interval through highly connected detours. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’2004), pages 495–504, Florence, Italy, 2004.
L. R. Ford Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
R. E. Gomory and T. C. Hu. Multi-terminal network flows. In SIAM Journal on Applied Mathematics, volume 9, pages 551–556, 1961.
D. Gusfield. Very simple method for all pairs network flow analisys. In SIAM Journal on Computing, volume 19(1), pages 143–155, 1990.
Java 2 Platform, Enterprise Edition (J2EE). http://java.sun.com/j2ee.
Java Technology. http://java.sun.com.
JDigraph. http://jdigraph.dev.java.net.
C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed internet routing convergence. In SIGCOMM, pages 175–187, 2000.
D. Pei, X. Zhao, L. Wang, D. Massey, A. Mankin, S. Wu, and L. Zhang. Improving BGP convergence through consistency assertions. In INFOCOM, New York, 2002.
Y. Rekhter and T. Li. RFC 1771: A Border Gateway Protocol 4 (BGP-4), March 1995.
R. Santini, E. P. Duarte Jr., J. Schroeder, P. R. Torres Jr., and J. Cohen. Roteamento tolerante a falhas baseado em desvios de alta conectividade. Technical report, Universidade Federal do Paraná, 2004.
J. Schroeder, A. L. P. Guedes, and E. P. Duarte Jr. Computing the minimum cut and maximum flow of undirected graphs. Technical report, Universidade Federal do Paraná, 2004.
The Jakarta Site - Apache Jakarta Tomcat. http://jakarta.apache.org/tomcat.
L. Wang, D. Massey, K. Patel, and L. Zhang. FRTR: A scalable mechanism for global routing table consistency. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’2004), pages 465–474, Florence, Italy, 2004.
B. M. Waxman. Routing of multipoint connections. In IEEE Journal of Selected Areas in Communications, volume 6(9), pages 1617–1622, 1988.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, second edition, 1990.
E. P. Duarte Jr., R. Santini, and J. Cohen. Delivering packets during the routing convergence latency interval through highly connected detours. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’2004), pages 495–504, Florence, Italy, 2004.
L. R. Ford Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
R. E. Gomory and T. C. Hu. Multi-terminal network flows. In SIAM Journal on Applied Mathematics, volume 9, pages 551–556, 1961.
D. Gusfield. Very simple method for all pairs network flow analisys. In SIAM Journal on Computing, volume 19(1), pages 143–155, 1990.
Java 2 Platform, Enterprise Edition (J2EE). http://java.sun.com/j2ee.
Java Technology. http://java.sun.com.
JDigraph. http://jdigraph.dev.java.net.
C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed internet routing convergence. In SIGCOMM, pages 175–187, 2000.
D. Pei, X. Zhao, L. Wang, D. Massey, A. Mankin, S. Wu, and L. Zhang. Improving BGP convergence through consistency assertions. In INFOCOM, New York, 2002.
Y. Rekhter and T. Li. RFC 1771: A Border Gateway Protocol 4 (BGP-4), March 1995.
R. Santini, E. P. Duarte Jr., J. Schroeder, P. R. Torres Jr., and J. Cohen. Roteamento tolerante a falhas baseado em desvios de alta conectividade. Technical report, Universidade Federal do Paraná, 2004.
J. Schroeder, A. L. P. Guedes, and E. P. Duarte Jr. Computing the minimum cut and maximum flow of undirected graphs. Technical report, Universidade Federal do Paraná, 2004.
The Jakarta Site - Apache Jakarta Tomcat. http://jakarta.apache.org/tomcat.
L. Wang, D. Massey, K. Patel, and L. Zhang. FRTR: A scalable mechanism for global routing table consistency. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’2004), pages 465–474, Florence, Italy, 2004.
B. M. Waxman. Routing of multipoint connections. In IEEE Journal of Selected Areas in Communications, volume 6(9), pages 1617–1622, 1988.
Publicado
09/05/2005
Como Citar
SCHROEDER, Jonatan; DUARTE JR., Elias P..
Roteamento Tolerante a Falhas Baseado em Caminhos Robustos. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 6. , 2005, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 25-36.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2005.23365.
