Roteamento Dinâmico Tolerante a Falhas Baseado em Avaliação de Fluxo Máximo
Abstract
This work proposes a fault-tolerant dynamic routing strategy, in which intermediate routers, having more recent information about topology changes, are able to switch the path employed. The proposed routing strategy chooses network edges for routing based on maximum flow evaluation, in order to increase the number of disjoint paths, enhancing the path redundancy, and so extending the possibility of using detours, or alternative paths. Route distance is employed as a secondary criterion. Formal proofs for correctness of the algorithm are also presented.
References
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.
Published
2006-05-29
How to Cite
SCHROEDER, Jonatan; DUARTE JR., Elias Procópio.
Roteamento Dinâmico Tolerante a Falhas Baseado em Avaliação de Fluxo Máximo. In: FAULT TOLERANCE WORKSHOP (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.
