UTILIZAÇÃO DE FLUXO MAXIMO PARA ORDENAÇÃO DE REQUISIÇÃO DO PROBLEMA DE ROTEAMENTO E ALOCAÇÃO DE COMPRIMENTOS DE ONDA

UTILIZAÇÃO DE FLUXO MAXIMO PARA ORDENAÇÃO DE REQUISIÇÃO DO PROBLEMA DE ROTEAMENTO E ALOCAÇÃO DE COMPRIMENTOS DE ONDA

Silva, Artur de Alvarenga; Morais, Bruna Silva de; Martins, Alexandre Xavier; Silva, Thiago Augusto de Oliveira

Artigo Completo:

A ideia principal da pesquisa é a implementação do algoritmo de fluxo máximo para ordenação das requisições no problema de roteamento e alocação de comprimentos de onda Routing and Wavelength Assignment(RWA) . Na literatura o problema consiste em atender as demandas definidas na topologia virtual, sendo possível destacar duas abordagens. A primeira variante é o MIN-RWA, no qual o objetivo geral é atender as requisições com o menor número de comprimentos de onda e a outra variação é o MAX-RWA, no qual tem a finalidade de maximizar o número de requisições atendidas com um número fixo de comprimentos de ondas. Neste estudo será considerado o MIN-RWA. Este estudo aborda uma adaptação do método proposto por SKORIN-KAPOV, esse consiste na ordenação através do tamanho do caminho mínimo de cada requisição. Através da implementação do método de fluxo máximo, pode-se propor dois novos métodos que foram as combinações dos algorítimos de fluxo máximo e o do caminho mínimo, junto a isso foram implementadas três maneiras para definir o método de criação dos grafos. Os resultados obtidos com as variações foram confrontados com o que já está definido na literatura a fim de mensurar os ganhos do presente trabalho.

A ideia principal da pesquisa é a implementação do algoritmo de fluxo máximo para ordenação das requisições no problema de roteamento e alocação de comprimentos de onda Routing and Wavelength Assignment(RWA) . Na literatura o problema consiste em atender as demandas definidas na topologia virtual, sendo possível destacar duas abordagens. A primeira variante é o MIN-RWA, no qual o objetivo geral é atender as requisições com o menor número de comprimentos de onda e a outra variação é o MAX-RWA, no qual tem a finalidade de maximizar o número de requisições atendidas com um número fixo de comprimentos de ondas. Neste estudo será considerado o MIN-RWA. Este estudo aborda uma adaptação do método proposto por SKORIN-KAPOV, esse consiste na ordenação através do tamanho do caminho mínimo de cada requisição. Através da implementação do método de fluxo máximo, pode-se propor dois novos métodos que foram as combinações dos algorítimos de fluxo máximo e o do caminho mínimo, junto a isso foram implementadas três maneiras para definir o método de criação dos grafos. Os resultados obtidos com as variações foram confrontados com o que já está definido na literatura a fim de mensurar os ganhos do presente trabalho.

Palavras-chave:

DOI: 10.5151/spolm2019-215

Referências bibliográficas

• [1] SKORIN-KAPOV, N. Routing and wavelength assignment in optical networks using bin packing based algorithms. European Journal of Operational Research, Elsevier, v. 177, n. 2, p. 1167{1179, 2007. 1, 3, 4, 5, 6, 7, 8, 11 [2] ZANG, H. et al. A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks. Optical networks magazine, v. 1, n. 1, p. 47{60, 2000. 2 [3] MARTINS, A. X. Metaheursticas e Formulac~oes para a resoluc~ao do Problema de Roteamento e Alocação de Comprimentos de Onda em Redes Opticas. Tese (Doutorado) | Universite Blaise Pascal-Clermont-Ferrand II, 2011. 2 [4] LI, G.; SIMHA, R. The partition coloring problem and its application to wavelength routing and assignment. In: Proceedings of the First Workshop on Optical Networks. Dallas, USA: [s.n.], 2000. p. 1{19. 3 [5] BANERJEE, D.; MUKHERJEE, B. A practical approach for routing and wavelength assignment in large wavelength-routed optical networks. IEEE Journal on Selected Areas in Communications, v. 14, n. 5, p. 903{908, 1996. 3 [6] NORONHA, T.; RIBEIRO, C. Routing and wavelength assignment by partition colouring. European Journal of Operational Research, v. 171, n. 3, p. 797{810, 2006. 3 [7] BRELAZ, D. New methods to color the vertices of a graph. Communications of the ACM, v. 256, p. 251{256, 1979. 3 [8] MANOHAR, P.; MANJUNATH, D.; SHEVGAONKAR, R. Routing and wavelength assignment in optical networks from edge disjoint path algorithms. IEEE Communications Letters, v. 6, n. 5, p. 211{213, 2002. 3 [9] GAREY, M.; JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: Freeman, San Francisco, 1979. 3 [10] NORONHA, T. F.; RESENDE, M. G.; RIBEIRO, C. C. Eficient implementations of heuristics for routing and wavelength assignment. In: SPRINGER. International Workshop on Experimental and Eficient Algorithms. [S.l.], 2008. p. 169{180. 4, 5, 7 [11] MARTINS, A. X. et al. Variable neighborhood descent with iterated local search for routing and wavelength assignment. Computers & Operations Research, Elsevier, v. 39, n. 9, p. 2133{2141, 2012. 5, 7, 11

Como citar:

Silva, Artur de Alvarenga; Morais, Bruna Silva de; Martins, Alexandre Xavier; Silva, Thiago Augusto de Oliveira; "UTILIZAÇÃO DE FLUXO MAXIMO PARA ORDENAÇÃO DE REQUISIÇÃO DO PROBLEMA DE ROTEAMENTO E ALOCAÇÃO DE COMPRIMENTOS DE ONDA", p-2975-2986. In: Anais do XIX Simpósio de Pesquisa Operacional & Logística da Marinha. São Paulo: Blucher, 2020.
ISSN 21756295, DOI 10.5151/spolm2019-215