Roteamento Dinâmico Tolerante a Falhas Baseado em Avaliação de Fluxo Máximo
Resumo
Este trabalho propõe uma estratégia de roteamento tolerante a falhas e dinâmico, que permite aos roteadores intermediários, que podem possuir informações mais recentes de alterações na topologia, interferirem na escolha do caminho utilizado. A estratégia de roteamento proposta baseia-se na escolha de arestas para roteamento utilizando cálculo de fluxo máximo em grafos, aumentando o número de caminhos disjuntos, o que valoriza a redundância de caminhos e, por conseqüência, ampliam a possibilidade de utilização de desvios ou caminhos alternativos. Critérios de distância da rota são utilizados como critérios secundários. Provas formais da correção do algoritmo são apresentadas.
Referências
C. Huitema. Routing in the Internet. Prentice Hall, Upper Saddle River, 2nd edition, 1999.
Y. Rekhter and T. Li. RFC 1771: A Border Gateway Protocol 4 (BGP-4), March 1995.
C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed internet routing convergence. In SIGCOMM, pages 175–187, 2000.
J. Chandrashekar, Z. Duan, Z. L. Zhang, and J. Krasky. Limiting path exploration in BGP, 2005. disponı́vel em [link].
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.
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.
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.
Java Technology. http://java.sun.com.
Jonatan Schroeder. Roteamento Dinâmico Tolerante a Falhas Baseado em Avaliação de Fluxo Máximo. Master’s thesis, Universidade Federal do Paraná - UFPR, Curitiba, March 2006.
L. R. Ford Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, second edition, 1990.
E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.
Y. Rekhter and T. Li. RFC 1771: A Border Gateway Protocol 4 (BGP-4), March 1995.
C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed internet routing convergence. In SIGCOMM, pages 175–187, 2000.
J. Chandrashekar, Z. Duan, Z. L. Zhang, and J. Krasky. Limiting path exploration in BGP, 2005. disponı́vel em [link].
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.
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.
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.
Java Technology. http://java.sun.com.
Jonatan Schroeder. Roteamento Dinâmico Tolerante a Falhas Baseado em Avaliação de Fluxo Máximo. Master’s thesis, Universidade Federal do Paraná - UFPR, Curitiba, March 2006.
L. R. Ford Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, second edition, 1990.
E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.
Publicado
29/05/2006
Como Citar
SCHROEDER, Jonatan; DUARTE JR., Elias Procópio.
Roteamento Dinâmico Tolerante a Falhas Baseado em Avaliação de Fluxo Máximo. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 7. , 2006, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2006
.
p. 171-181.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2006.23361.
