Otimizando o Desempenho do SimRWA 2.0 usando a Técnica de

Otimizando o Desempenho do SimRWA 2.0 usando a
Técnica de Profiler para Identificação de Gargalos
Gilvan M. Durães1, André C. B. Soares, William F. Giozza
NUPERC – Universidade Salvador – UNIFACS
R. Ponciano de Oliveira, 126, Rio Vermelho – 41950-275 – Salvador, BA – Brazil
[email protected], {andre.soares, giozza}@unifacs.br
Abstract. The SimRWA is a simulation tool for RWA (Routing and Wavelength
Assignment) algorithms and survivability technique in all optical networks. In
this paper the profiler technique is used to identify bottlenecks in the source
code of SimRWA. Once identified the main bottlenecks, they were eliminated,
resulting in a response time reduction of about 35%.
Resumo. O SimRWA é uma ferramenta para simulação de algoritmos RWA e
de técnicas de sobrevivência em redes ópticas transparentes. Este artigo
apresenta uma otimização do desempenho do SimRWA usando a técnica de
profiler para a identificação de gargalos do código. Os resultados alcançados
implicaram numa redução de aproximadamente 35% no tempo de resposta do
SimRWA.
Palavras-Chave: redes ópticas, simulador, profiler.
1. Introdução
Atualmente tem sido desenvolvida uma nova geração de redes de transporte baseada em
uma infra-estrutura óptica inteligente que utiliza a multiplexação WDM – Wavelength
Division Multiplexing. Essa nova tecnologia de redes, chamada de redes ópticas, é
apontada como um dos principais veículos para atender, de forma satisfatória, a
crescente demanda de banda passante nas redes de transporte, provocada pelo
crescimento do número de usuários da Internet e o surgimento de novas aplicações
envolvendo voz e vídeo como vídeo sob demanda, teleconferência, imagens médicas de
alta resolução, etc.
As redes ópticas podem ser classificadas em opacas ou transparentes
[Ramaswami e Sivarajan, 1998]. As redes ópticas opacas realizam roteamento no nível
eletrônico sendo necessária a utilização de conversores OEO – Óptico-Eletro-Óptico.
As redes ópticas transparentes realizam roteamento no nível óptico eliminando os
conversores OEO. Os conversores OEO são responsáveis pela inserção de atrasos de
processamento além de aumentar o custo dos equipamentos [Mouftah e Ho, 2002]. Por
isso a evolução das redes ópticas aponta para as redes ópticas transparentes.
No estabelecimento de uma conexão entre dois nós através de uma rede óptica
transparente é necessário escolher uma rota e alocar um comprimento de onda. Esse
problema é conhecido na literatura como o problema RWA – Routing and Wavelength
1
Bolsista de Iniciação Científica (PIBIC FAPESB), aluno do curso de Ciência da Computação da
Universidade Salvador.
Assignment. O problema RWA pode ser classificado em estático ou dinâmico [Soares e
Giozza, 2004]. O problema RWA estático tem como objetivo minimizar o número de
comprimentos de onda necessários para atender um conjunto de conexões conhecidas
previamente. Já no problema RWA dinâmico, as conexões não são conhecidas
previamente. Nesse caso o objetivo é selecionar uma rota e alocar um comprimento de
onda, minimizando a probabilidade de bloqueio de futuras conexões, dado um conjunto
de comprimento de onda.
Na ausência de conversores de comprimento de onda, uma conexão deve utilizar
o mesmo comprimento de onda em todos os enlaces físicos que compõem o caminho
óptico. Essa propriedade é conhecida como continuidade obrigatória de comprimento de
onda.
Conversores de comprimento de onda são dispositivos localizados nos nós da
rede óptica que possibilitam a conversão de um comprimento de onda de entrada em
outro comprimento de onda de saída. Esses dispositivos permitem uma melhor
utilização dos comprimentos de onda, minimizando a probabilidade de bloqueio de
conexões [Chu et al., 2003].
Conversores de comprimento de onda são dispositivos ainda caros. Uma
alternativa para eliminar os custos dos conversores de comprimento de onda é a adoção
de algoritmos de alocação de comprimento de onda. Esses algoritmos devem minimizar
a probabilidade de bloqueio de futuras conexões numa rede óptica transparente. Vários
trabalhos recentes demonstram que os algoritmos de roteamento e alocação de
comprimento de onda são os principais instrumentos para diminuir a probabilidade de
bloqueio em redes ópticas transparentes [Pan HW DO, 2003] [Zang et al., 2000] [Barry e
Subramaniam, 1997].
Dada a complexidade da solução analítica para o cálculo da probabilidade de
bloqueio de conexões em redes ópticas transparentes e a inexistência de sistemas reais
disponíveis para a realização de medições, é indispensável a utilização de simuladores
de redes ópticas para a realização destes estudos.
O SimRWA é uma ferramenta para simulação de algoritmos de alocação de
comprimentos de onda e rotas em redes ópticas transparentes permitindo comparar esses
algoritmos sob diferentes condições de tráfego e utilizando topologias genéricas [Soares
et al.,2004]. Além disso, o SimRWA possibilita o estudo dos algoritmos de roteamento
e alocação de comprimentos de onda sob o dimensionamento do número e do tipo de
transmissores e receptores nos nós da rede óptica [Soares et al.,2005c] e sob diferentes
técnicas de sobrevivência [Soares et al., 2005b]. Ele foi desenvolvido utilizando a
linguagem de programação JAVA.
O uso do SimRWA para estudos de redes ópticas modelando cenários
complexos requer altos tempos de resposta, mesmo utilizando máquinas com um alto
poder de processamento. Diante disso, surge o interesse em otimizar a ferramenta com o
objetivo de diminuir o tempo de resposta.
Este artigo descreve os passos da aplicação da técnica profiler no SimRWA e
como a técnica de profiler contribuiu para identificação de gargalos no SimRWA. Além
disso, são detalhadas as modificações realizadas com o objetivo de eliminar e/ou reduzir
os gargalos identificados.
O restante deste artigo está organizado da seguinte forma: a Seção 2 apresenta as
motivações e objetivos deste trabalho. A Seção 3 descreve a técnica de profiler,
evidencia os gargalos identificados no SimRWA 2.0 [Soares et al.,2005a] e apresenta a
seqüência de alterações feitas no seu código fonte. Por fim, a conclusão é apresentada
na Seção 4.
2. Motivações e Objetivos
Após a utilização do SimRWA para a realização de diversos estudos de avaliação de
desempenho foi identificado um alto tempo de resposta para simulações mais
complexas. Diante disso, foi feito um estudo de desempenho com relação ao tempo de
resposta do SimRWA. Nesse estudo foi utilizada a topologia da rede NSFNET (Figura
1).
Figura 1. Topologia da rede NSFNET.
Foram simulados os algoritmos Random, Most Used, Least Used, Max-Sum e
Relative Capacity Loss utilizando roteamento fixo de menor caminho (algoritmo de
Dijkstra) [Soares e Giozza, 2004]. Todos os enlaces são bidirecionais utilizando para
cada sentido uma fibra óptica multiplexando 40 comprimentos de onda. As intensidades
de tráfego por nó foram 10, 30, 50, 70, 90, 110, 130 e 150 Erlangs. Foram realizadas 4
replicações de 100.000 requisições de conexões para cada intensidade de tráfego. As
simulações foram executadas em um PC AMD Semprom(tm) 2600+ 1,6 GHz, 240 MB
de RAM, com Windows XP SP2, apenas na Máquina Virtual Java (JVM) e o tempo de
resposta do SimRWA foi de aproximadamente 112 minutos o que consideramos um alto
tempo de resposta. Diante desse tempo de resposta significativamente alto, surgiu o
interesse de otimizar o SimRWA e, devido ao grande número de métodos em todas as
70 classes do SimRWA, utilizar ferramenta de profiler para identificação de gargalos de
processamento.
3. Identificando e Eliminado Gargalos de Processamento do SimRWA 2.0
O profiler é uma técnica de otimização que permite detectar falhas no código que
podem causar retardo na aplicação. Durante a execução do aplicativo em teste o profiler
mantém um registro de todas as chamadas dos métodos, gerando em tempo de
execução, dados estatísticos sobre: criação de objetos, coleta de lixo e uso de recursos
do sistema (processador, memória, rede, disco) para cada método, indicando o seu nome
e sua classe. Estas informações são necessárias para diagnosticar erros e problemas de
desempenho relacionados ao código. A técnica de profiler é geralmente empregada
através da utilização de uma ferramenta de profiler (software) que analisa a utilização
dos recursos do computador em função da execução de um código fonte específico (e.g.
classes Java) [BORLAND SOFTWARE CORPORATION, 2005], [APPPERFECT
CORPORATION, 2005] [YOURKIT LCC, 2005]. Dessa forma, uma ferramenta de
profiler pode ser composta por módulos que analisam a utilização de recursos sob
diferentes aspectos:
a) Profiler da Memória – é a parte responsável por investigar problemas
relacionados à memória. Esta opção mostra as classes carregadas, quais métodos usam
a memória excessivamente, escapes de memória, referências e detalhes da coleta
automática de lixo.
b) Profiler do Processador – esta opção fornece informações sobre a utilização
do processador, como o número de vezes que um método é invocado, o seu tempo de
execução e o tempo total da aplicação.
c) Thread Profiler – permite analisar o processo de execução de cada parte do
aplicativo, relatando seus estados (executando, esperando, bloqueado, parado). Caso
exista um deadlock, ponto em que o aplicativo fica bloqueado devido à espera de partes
do processo por um evento que pode nunca ocorrer, o Thread Profiler mostra todas as
partes envolvidas.
d) Profiler do Sistema – fornece informações detalhadas sobre os recursos do
sistema que estão sendo usados pelos vários processos em execução na máquina:
utilização da rede, quantidade de pacotes enviados e recebidos, percentagem de
utilização do processador, memória livre e memória utilizada, escrita e leitura do disco.
Neste trabalho foi utilizado o Optimizeit Enterprise Suite 6.0 for JAVA
[BORLAND SOFTWARE CORPORATION, 2005] e especialmente o profiler do
processador para identificar os métodos mais invocados e com maiores tempos de
execução no SimRWA.
3.1. Os Gargalos do SimRWA 2.0
Para este trabalho, todas as simulações feitas seguem o cenário descrito na Seção 2.
Os resultados dos tempos de resposta apresentados nesta Seção foram obtidos
submetendo o SimRWA 2.0 ao Optimizeit Enterprise Suite 6.0 for JAVA. Para cada
tempo apresentado foi feita uma média aritmética de 5 execuções da ferramenta de
profiler. Isso foi feito devido a variabilidade dos resultados para um mesmo cenário
estudado em diferentes execuções do Optimizeit Enterprise Suite 6.0 for JAVA. Os
tempos dos métodos são tempos absolutos acumulados durante toda a simulação, ou
seja, o Optimizeit pára de incrementar o tempo de um método quando este invoca um
outro método.
Na Tabela 1 destacamos os métodos com maiores tempos de execução da versão
2.0, bem como a média do tempo total das simulações fornecidos pela ferramenta de
profiler.
Tabela 1. Métodos da versão 2.0 com maiores tempos de execução.
Método
Tempo (ms)
%
procuraNo()
4.225.079
31,25
caminhoLivreParaRota()
2.125.975
15,73
interfacceParaNoA()
1.680.884
12,43
proximoDeAOtimo()
1.643.186
12,15
Rcl.heuristicaAtual()
784.414
5,80
lambdaLivreParaNoA()
699.117
5,17
getDestino()
447.921
3,31
insere()
290.065
2,15
13.519.291
100
Total
A Tabela 1 apresenta os principais métodos candidatos a otimização, isto é os
métodos que representam gargalos de processamento do SimRWA.
As subseções a seguir apresentam a seqüência de alterações feitas no código
fonte e as comparações de desempenho entre versões.
3.2 Primeira Alteração.
Foi encontrado no método caminhoLivreParaRota() invocação desnecessária do método
proximoDeAOtimo(), conforme mostra a Figura 2.
Figura 2. Invocação desnecessária do método proxDeAOtimo() no método
caminhoLivreParaRota() do SimRWA 2.0.
Observe que a variável noOri (linha 8) estava recebendo o retorno do método
proxDeAOtimo(noOri), mas este retorno já estava armazenado na variável noAdj (linha
2). Sendo assim, necessário apenas copiar o valor de noAdj para noOri.
Este mesmo tipo de erro foi encontrado e corrigido em mais 11 métodos,
gerando a versão 2.1 do SimRWA. Os resultados de desempenho são apresentados na
Tabela 2.
Tabela 2. Comparação de desempenho entre as versões 2.0 e 2.1 do SimRWA
SimRWA 2.1
Método
Ganho em Relação a
versão 2.0
Tempo(ms)
%
Tempo(ms)
%
procuraNo()
4.266.039
31,25
40.960
0,30
caminhoLivreParaRota()
1.991.875
15,73
-134.100
-0,99
interfacceParaNoA()
1.722.241
12,43
41.357
0,31
proximoDeAOtimo()
1.134.115
12,15
-509.071
-3,77
Rcl.heuristicaAtual()
791.063
5,80
6.648
0,05
lambdaLivreParaNoA()
730.053
5,17
30.936
0,23
getDestino()
444.391
3,31
-3.530
-0,03
insere()
353.393
2,15
63.328
0,47
12.925.859
100
-593.431
-4,39
Total
Conforme observado, houve uma melhora significativa nos tempos dos métodos
caminhoLivreParaRota() e proximoDeAOtimo() e, consequentemente, uma queda de
4,39% no tempo total da simulação.
3.3 Segunda Alteração.
O método procuraNo(), na versão 2.1 do SimRWA, ainda é o método que mais tempo
de CPU consome.
No SimRWA, o Vector 2“listaNoRota3” de inteiros armazena os identificadores
dos respectivos objetos da classe ElementosNo 4especificados por um objeto da classe
Rota. Assim, quando é necessário acessar e/ou alterar os atributos de um objeto da
classe ElementosNo, é chamado o método procuraNo() para que, depois de procurar no
Vector “listaNo”, retorne o nó “ElementoNo” correspondente ao identificador
armazenado no Vector “listaNoRota”.
2
Classe do pacote java.util.
Atributo da Classe Rota que pertence ao SimRWA, especifica quais os nós compõem uma determinada
rota.
4
Classe do SimRWA que representa um nó óptico.
3
Figura 3. O método procuraNo().
A solução encontrada foi armazenar uma referência para o próprio objeto da
classe ElementoNo em “ listaNoRota” e não apenas o seu identificador, assim, não é
mais necessário invocar o método procuraNo() para acessar os atributos de cada objeto
da classe ElementoNo pertencente a uma rota.
Esta solução foi aplicada obtendo-se a versão 2.2 do SimRWA. A Tabela 3
mostra o desempenho obtido na versão 2.2 em relação à versão anterior.
Tabela 3. Comparação de desempenho entre as versões 2.1 e 2.2 do SimRWA
SimRWA 2.2
Método
Ganho em Relação a
versão 2.1
Tempo(ms)
%
Tempo(ms)
%
34
0,00
-4.266.005
-33,0
caminhoLivreParaRota()
1.734.415
17,59
-257.460
-1,99
interfacceParaNoA()
2.145.285
21,75
423.044
3,27
proximoDeAOtimo()
1.813.117
18,38
679.002
5,25
Rcl.heuristicaAtual()
777.163
7,88
-13.900
-0,11
lambdaLivreParaNoA()
716.805
7,27
-13.248
-0,10
getDestino()
484.839
4,92
40.448
0,31
insere()
311.851
3,16
-41.542
-0,32
9.862.473
100
-3.063.386
-23,70
procuraNo()
Total
Conforme esperado, houve uma grande diminuição no tempo gasto em
procuraNo() e uma queda de 23,7% no tempo total da simulação.
Todavia, os métodos interfacceParaNoA() e proximoDeAOtimo() aumentaram
seus tempos devido ao Vector “ listaNoRota” armazenar referências para objetos da
classe ElementoNo e não mais inteiros como antes. A terceira alteração foi feita nestes
métodos.
3.4 Terceira Alteração.
Agora, após a diminuição quase que total do tempo gasto por procuraNo(), os 3
métodos que mais se destacam são: caminhoLivreParaRota(), interfacceParaNoA() e
proximoDeAOtimo().
Ambos os métodos, apresentam invocações repetitivas de outros métodos. Como
exemplo, a Figura 4 mostra o método interfacceParaNoA(). Observa-se que foi tirada
do loop a invocação do método getId() (linha 9) e atribuído o seu retorno à variável idA
antes de entrar no loop (linha 5).
Figura 4. Invocações repetitivas do método getId() no método
interfacceParaNoA().
O mesmo ocorre nos métodos caminhoLivreParaRota() e proximoDeAOtimo()
com os métodos getDestino() e getId(), respectivamente.
Essa foi a alteração feita gerando a versão 2.3 do SimRWA e os resultados
seguem na Tabela 4.
Tabela 4. Comparação de desempenho entre as versões 2.2 e 2.3 do SimRWA
SimRWA 2.3
Método
Ganho em Relação a
versão 2.2
Tempo(ms)
%
Tempo(ms)
%
97
0,00
63
0,00
caminhoLivreParaRota()
1.658.328
17,59
-76.087
-0,77
interfacceParaNoA()
2.031.661
21,55
-113.624
-1,15
proximoDeAOtimo()
1.747.270
18,53
-65.847
-0,67
Rcl.heuristicaAtual()
787.936
8,36
10.773
0,11
lambdaLivreParaNoA()
769.926
8,17
53.122
0,54
getDestino()
212.426
2,25
-272.414
-2,76
procuraNo()
insere()
Total
241.396
2,56
-70.456
-0,71
9.429.292
100
-433.181
-4,39
3.5 Desempenho Acumulado.
A Tabela 5 compara a versão 2.0 do SimRWA, antes da aplicação das otimizações, com
a versão 2.3 do SimRWA, após as eliminações dos principais gargalos, localizadas nos
métodos críticos identificados pelo Optimizeit.
Ressaltamos que foram feitas 5 simulações idênticas para cada versão e todos os
tempos apresentados são resultados da média aritmética destas simulações.
Tabela 5. Comparação de desempenho entre as versões 2.0 e 2.3 do SimRWA
SimRWA 2.3
Método
Ganho em Relação a
versão 2.0
Tempo(ms)
%
Tempo(ms)
%
97
0,00
-4.224.983
-31,25
caminhoLivreParaRota()
1.658.328
17,59
-467.647
-3,46
interfacceParaNoA()
2.031.661
21,55
350.777
2,5
proximoDeAOtimo()
1.747.270
18,53
104.085
0,77
Rcl.heuristicaAtual()
787.936
8,36
3.522
0,03
lambdaLivreParaNoA()
769.926
8,17
70.809
0,52
getDestino()
212.426
2,25
-235.496
-1,74
insere()
241.396
2,56
-48.670
-0,36
9.429.292
100
-4.089.998
-30,25
procuraNo()
Total
A diminuição do tempo de resposta em cerca de 30%, após pequenas alterações
no código evidencia a grande importância da técnica profiler, ao revelar os métodos
críticos do SimRWA os quais foram modificados. É importante ressaltar que a
identificação dos gargalos não seria trivial sem a utilização da ferramenta de profiler,
dado o grande número de classes e métodos do SimRWA. Além disso, devemos
evidenciar também que a eliminação dos gargalos identificados pela ferramenta de
profiler foi feita através de uma análise cuidadosa dos métodos críticos, posteriormente
otimizados por nossa equipe.
Para medir a real otimização (em termos de tempo de resposta) do SimRWA 2.3
em relação a versão 2.0 realizamos o mesmo estudo descrito na Seção 2. Desta vez,
medimos o tempo de resposta da versão 2.3 sem a utilização da ferramenta de profiler.
O tempo para a simulação desse último experimento foi de aproximadamente 73
minutos, ou seja, o SimRWA 2.3 gastou aproximadamente 35% a menos do tempo do
SimRWA 2.0. Essas simulações foram realizadas apenas na Máquina Virtual Java
(JVM). Ressaltamos que também foram feitas 5 simulações idênticas tanto na versão 2.0
como na versão 2.3 do SimRWA para esta comparação e que os tempos apresentados
são resultados da média aritmética destas simulações.
O ganho de aproximadamente 5% quando as simulações são feitas apenas na
Máquina Virtual Java é em decorrência do não processamento da ferramenta de profiler
durante tais simulações.
4. Conclusão
A implantação de redes ópticas transparentes para compor a futura infra-estutrura de
transporte dos backbones dos provedores de serviço de telecomunicações é uma
tendência mundial. Os algoritmos de alocação de comprimento de onda e as estratégias
de roteamento estudados constituem-se em instrumentos valiosos na otimização dos
recursos das redes ópticas transparentes. Principalmente quando a tecnologia de
conversores de comprimento de onda ainda não está amadurecida e competitiva.
Atualmente, a utilização de ferramentas para simulação de redes ópticas transparentes é
de grande importância para a realização de dimensionamentos e estudos comparativos.
Com o objetivo de reduzir o tempo de resposta da ferramenta SimRWA
apresentamos neste trabalho a utilização da técnica de profiler para identificação de
gargalos que posteriormente foram eliminados com nossa intervenção. Após a
realização da otimização descrita neste artigo foi possível alcançar uma diminuição de
aproximadamente 35% no tempo de resposta do SimRWA. É importante evidenciar que
a diminuição do tempo de resposta é um grande incentivo para que sejam realizadas
simulações de cenários mais realísticos e consequentemente mais complexos.
Referências
Ramaswami, R. e Sivarajan, K. N. (1998). Optical Network - A Practical Perspective.
Morgan Kaufmann Publishers.
Mouftah, H. T. and Ho, P. (2002). Optical Networks - Architecture and Survivability.
Kluwer Academic Publishers.
Soares, A. C. B. e Giozza, W. F. (2004). Avaliação de desempenho de algoritmos para
alocação dinâmica de comprimentos de onda em redes ópticas transparentes. In
Simpósio Brasileiro de Redes de Computadores 2004, pages 661–674.
Chu, X., Li, B., e Chlamtac, I. (2003a). Wavelength converter placement under different
rwa algorithms in wavelength-routed all optical networks. IEEE TRANSACTION
ONCOMMUNICATIONS, pages 607–617.
Pan, D., Qi, Z., Zhao, J., and Ji, Y. (2003). A new dynamic wavelength assignment
algorithm:load equalization algorithm. In International Conference on
Communication technology, pages734– 737.
Zang, H., Jue, J. P., e Mukherjee, B. (2000). A review of routing and wavelength
assignment approaches for wavelength-routed optical WDM network. Optical
Network Magazine.
Barry, R. A. e Subramaniam, S. (1997). The max-sum wavelength assignment algorithm
in wdm ring networks. In OFC ’97.
Soares, A. C. B., Neto, J. C. M., e Giozza, W. F. (2004). SimRWA: Uma ferramenta
para avaliação de desempenho de algoritmos para alocação de comprimentos de onda
e rotas em redes ópticas transparentes. In III Salão de Ferramentas do Simpósio
Brasileiro de Redes de Computadores, pages 915–922.
Soares, A. C. B., Assis, K. D. R., e Giozza, W. F. (2005c). WDM Mesh Networks under
Limitations in the Number of Transceivers per Node . In ICT 2005.
Soares, A. C. B., Neto, J. C. M., e Giozza, W. F. (2005b). Sobrevivência em redes
ópticas wdm sob influência de algoritmos de alocação de rota e de comprimentos de
onda. In Simpósio Brasileiro de Telecomunicações - SBrT.
Soares, A. C. B., Neto, J. C. M., e Giozza, W. F. (2005a). SimRWA 2.0: Uma
ferramenta para avaliação de desempenho de algoritmos RWA e de técnicas de
sobrevivência em redes ópticas transparentes. In IV Salão de Ferramentas do
Simpósio Brasileiro de Redes de Computadores.
AppPerfect, “Java Testing and Monitoring Solutions”,
http://www.appperfect.com, acessado em 27/01/2006.
disponível
em
Optimizeit™ Enterprise Suite, “Uma Solução de Performance Completa para Java”,
disponível em http://www.borland.com/br/products/optimizeit/, acessado em
27/01/2006.
YourKit, “The Industry Leader in Java
http://www.yourkit.com/, acessado em 27/01/2006.
Profiling”,
disponível
em