Melhorando a Utilização de Recursos em Redes MPLS para Demandas Variantes no Tempo

• Augusto C. Carlson UFSC
• Jean-Marie Farines UFSC
• Eduardo Camponogara UFSC

Resumo

Este artigo trata da otimização do uso global de recursos em uma rede MPLS intra-domínio, para situações de demandas de fluxos com perfis predefinidos de banda variantes no tempo. Uma abordagem baseada em caminhos para lidar com múltiplas restrições de QoS e proposta como uma alternativa à abordagem baseada em fluxos encontrada na literatura. O problema de roteamento off-line é formulado em programação linear inteira e uma heurística para roteamento on-line foi desenvolvida. Inicialmente, a formulação e a heurística lidam somente com a utilização de banda. Em seguida, apresenta-se uma extensão para tratar múltiplas restrições de QoS sem efetuar alterações nos algoritmos e heurísticas desenvolvidos. Em contraposição, a abordagem baseada em fluxo necessita de alterações na sua implementação para considerar restrições adicionais, o que implica a solução de subproblemas NP-Difíceis.

Referências

Ahuja, R. K., Magnanti, T. L., e Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

Awduche, D. O. (1999). MPLS and traffic engineering in IP networks. IEEE Communications Magazine, 37(12):42–47.

Banerjee, G. e Sidhu, D. (2002). Comparative analysis of path computation techniques for MPLS traffic engineering. Computer Networks: The Int. Journal of Computer and Telecommunications Networking, 40(17):149–165.

Beasley, J. E. e Christofides, N. (1989). An algorithm for the resource constrained shortest path problem. Networks, 19:379–394.

Carlson, A. C. (2007). Roteamento Baseado em Caminhos com Perfis Variantes no Tempo. Dissertação (Mestrado em Engenharia Elétrica), Centro Tecnológico, Universidade Federal de Santa Catarina, Florianópolis.

Carlson, A. C., Farines, J.-M., e Camponogara, E. (2007). Roteamento com perfis de banda variantes no tempo: Uma abordagem baseada em caminhos. In Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos 2007.

Cormen, T. H., Leiserson, C. E., Rivest, R. I., e Stein, C. (2001). Introduction to Algorithms. MIT Press, 2 edition.

Dias, R. A., Farines, J.-M., Camponogara, E., Willrich, R., e Campestrini, A. O. (2004). Engenharia de tráfego dinâmica em redes IP sobre tecnologia MPLS: Otimização baseada em heurísticas. In Simpósio Brasileiro de Redes de Computadores 2004.

Fourer, R., Gay, D. M., e Kernighan, B. W. (2002). AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, 2 edition.

ILOG (2006). CPLEX. [link].

Kar, K., Kodialam, M., e Lakshman, T. (2000). Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications. IEEE Journal on Selected Areas in Communications, 18(12):2566–2579.

Mieghem, P. V. e Kuipers, F. A. (2004). Concepts of exact QoS routing algorithms. IEEE/ACM Transactions on Networking, 12(5):851–864.

Orda, A. e Sprintson, A. (2003). Precomputation schemes for QoS routing. IEEE/ACM Transactions on Networking, 11(4):578–591.

Plotkin, S. A. (1995). Competitive routing of virtual circuits in ATM networks. IEEE Journal of Selected Areas in Communications, 13(6):1128–1136.

Ricciato, F. e Monaco, U. (2005). Routing demands with time-varying bandwidth profiles on a MPLS network. Computer Networks: The Int. Journal of Computer and Telecommunications Networking, 47:47–61.

Rossum, G. V. (2006). Python patterns – implementing graphs. [link].

Shima, R. B. (2006). Caminhos Mínimos sob Restrições: Uma Revisão e Aplicações. Dissertação (Mestrado em Engenharia Elétrica), Centro Tecnológico, Universidade Federal de Santa Catarina, Florianópolis.

Suri, S., Waldvogel, M., Bauer, D., e Warkhede, P. R. (2003). Profile-based routing and traffic engineering. Computer Communications, 26(4):351–365.

Wang, Z. e Crowcroft, J. (1999). Bandwidth-delay based routing algorithms. In Proceedings of IEEE GLOBECOM.