Uma Nova Representação do Espaço de Soluções para Arrefecimento Simulado em Problemas de Alocação de Circuitos Virtuais
Resumo
A otimização de circuitos virtuais em redes é muitas vezes resolvidas com heurísticas, como o Arrefecimento Simulado (AS), devido a topologia e demanda complexas. Para agilizar a execução do AS, muitas técnicas utilizam representações insuficientes ou complexas. Esse trabalho define um espaço de soluções para AS que faz a descoberta de caminhos e alocação dos fluxos simultaneamente. A proposta representa todo o espaço de soluções, ao custo de uma dimensionalidade maior. Compara-se a proposta com outras heurísticas e observa-se que a proposta é viável, ao custo de mais tempo para execução. Essa representação tem potencial para cenários onde respostas somente com κ-menores caminhos não são suficientes para atingir resultados quase ótimos.
Palavras-chave:
Gerenciamento de Redes, Arrefecimento Simulado, Otimização, Engenharia de Rede, Análise de Rede
Referências
Agarwal, S., Kodialam, M., e Lakshman, T. V. (2013). Traffic engineering in software defined networks. Em 2013 Proceedings IEEE INFOCOM, páginas 2211–2219.
Bertsekas, D. P. e Gallager, R. G. (1992). Data Networks. Prentice-Hall International Editions. Prentice-Hall International, Englewood Cliffs, NJ, 2. ed edition.
Eren, M. e Ersoy, C. (2002). Optimal Virtual Path Routing Using a Parallel Annealed Genetic Algorithm.
Farrugia, N., Briffa, J. A., e Buttigieg, V. (2023). Solving the multicommodity flow problem using an evolutionary routing algorithm in a computer network environment. PLOS ONE, 18(4):e0278317.
Frazier, P. I. (2018). A Tutorial on Bayesian Optimization. arXiv:1807.02811 [stat].
Geman, S. e Geman, D. (1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):721–741.
Hagberg, A. A., Schult, D. A., e Swart, P. J. (2008). Exploring network structure, dynamics, and function using networkx. Em Varoquaux, G., Vaught, T., e Millman, J., editors, Proceedings of the 7th Python in Science Conference, páginas 11 – 15, Pasadena, CA USA.
Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., e Oliphant, T. E. (2020). Array programming with NumPy. Nature, 585(7825):357– 362.
Hunter, J. D. (2007). Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 9(3):90–95.
Kirkpatrick, S., Gelatt, C. D., e Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598):671–680.
La-Roque, E., Batista, C., e Araújo, J. (2020). A Parallel Strategy for a Genetic Algorithm in Routing Wavelength Assignment Problem Using GPU with CUDA. Em Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), páginas 740–751. SBC.
Lima, E. L. (2020). Álgebra Linear. Coleção Matemática Universitária. Associação Instituto Nacional de Matemática Pura e Aplicada, Rio de janeiro, RJ, 10 edition.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., e Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6):1087–1092.
Meurer, A., Smith, C. P., Paprocki, M., Čertík, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J. K., Singh, S., Rathnayake, T., Vig, S., Granger, B. E., Muller, R. P., Bonazzi, F., Gupta, H., Vats, S., Johansson, F., Pedregosa, F., Curry, M. J., Terrel, A. R., Roučka, v., Saboo, A., Fernando, I., Kulal, S., Cimrman, R., e Scopatz, A. (2017). Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103.
Pióro, M. e Medhi, D. (2008). Routing, Flow, and Capacity Design in Communication and Computer Networks. The Morgan Kaufmann Series in Networking. Elsevier/Morgan Kaufmann, Amsterdam, nachdr. edition.
Riedl, A. (2002). A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics. Em IEEE Workshop on IP Operations and Management, páginas 166–170.
Šeremet, I. e Čaušević, S. (2020). Advancing Multiprotocol Label Switching Traffic Engineering with Segment Routing in Software Defined Network environment. Em 2020 19th International Symposium INFOTEH-JAHORINA (INFOTEH), páginas 1–6.
Yaghini, M., Momeni, M., e Sarmadi, M. (2012). A Simplex-based simulated annealing algorithm for node-arc capacitated multicommodity network design. Applied Soft Computing, 12(9):2997–3003.
Bertsekas, D. P. e Gallager, R. G. (1992). Data Networks. Prentice-Hall International Editions. Prentice-Hall International, Englewood Cliffs, NJ, 2. ed edition.
Eren, M. e Ersoy, C. (2002). Optimal Virtual Path Routing Using a Parallel Annealed Genetic Algorithm.
Farrugia, N., Briffa, J. A., e Buttigieg, V. (2023). Solving the multicommodity flow problem using an evolutionary routing algorithm in a computer network environment. PLOS ONE, 18(4):e0278317.
Frazier, P. I. (2018). A Tutorial on Bayesian Optimization. arXiv:1807.02811 [stat].
Geman, S. e Geman, D. (1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):721–741.
Hagberg, A. A., Schult, D. A., e Swart, P. J. (2008). Exploring network structure, dynamics, and function using networkx. Em Varoquaux, G., Vaught, T., e Millman, J., editors, Proceedings of the 7th Python in Science Conference, páginas 11 – 15, Pasadena, CA USA.
Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., e Oliphant, T. E. (2020). Array programming with NumPy. Nature, 585(7825):357– 362.
Hunter, J. D. (2007). Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 9(3):90–95.
Kirkpatrick, S., Gelatt, C. D., e Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598):671–680.
La-Roque, E., Batista, C., e Araújo, J. (2020). A Parallel Strategy for a Genetic Algorithm in Routing Wavelength Assignment Problem Using GPU with CUDA. Em Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), páginas 740–751. SBC.
Lima, E. L. (2020). Álgebra Linear. Coleção Matemática Universitária. Associação Instituto Nacional de Matemática Pura e Aplicada, Rio de janeiro, RJ, 10 edition.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., e Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6):1087–1092.
Meurer, A., Smith, C. P., Paprocki, M., Čertík, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J. K., Singh, S., Rathnayake, T., Vig, S., Granger, B. E., Muller, R. P., Bonazzi, F., Gupta, H., Vats, S., Johansson, F., Pedregosa, F., Curry, M. J., Terrel, A. R., Roučka, v., Saboo, A., Fernando, I., Kulal, S., Cimrman, R., e Scopatz, A. (2017). Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103.
Pióro, M. e Medhi, D. (2008). Routing, Flow, and Capacity Design in Communication and Computer Networks. The Morgan Kaufmann Series in Networking. Elsevier/Morgan Kaufmann, Amsterdam, nachdr. edition.
Riedl, A. (2002). A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics. Em IEEE Workshop on IP Operations and Management, páginas 166–170.
Šeremet, I. e Čaušević, S. (2020). Advancing Multiprotocol Label Switching Traffic Engineering with Segment Routing in Software Defined Network environment. Em 2020 19th International Symposium INFOTEH-JAHORINA (INFOTEH), páginas 1–6.
Yaghini, M., Momeni, M., e Sarmadi, M. (2012). A Simplex-based simulated annealing algorithm for node-arc capacitated multicommodity network design. Applied Soft Computing, 12(9):2997–3003.
Publicado
19/05/2025
Como Citar
SILVA, Fernando D. M.; COSTA, Luís Henrique M. K..
Uma Nova Representação do Espaço de Soluções para Arrefecimento Simulado em Problemas de Alocação de Circuitos Virtuais. In: WORKSHOP DE GERÊNCIA E OPERAÇÃO DE REDES E SERVIÇOS (WGRS), 30. , 2025, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 113-126.
ISSN 2595-2722.
DOI: https://doi.org/10.5753/wgrs.2025.8863.
