Nesta seção será definido o cenário onde foram feitas as simulações e as análises. Serão explic- itadas as redes a serem analisadas, o funcionamento básico dos principais RWAs analisados nessas redes e o ambiente de simulação que foi criado.
3.2.1 Funcionamento RWAs Analisados
Os algoritmos analisados independente de serem tratados de forma separada ou conjunta, foram todos implementados de uma forma centralizada e terão o funcionamento básico baseado no pseudo- código abaixo:
Entrada: Grafo G=(V,E)
Requisições: Γ = {τ1, τ2,....τr}
Número de comprimentos de onda: W Processamento:
Para 1 ≤ j ≤|Γ| faça
Se houver rota entre (Ns, Nd) para τj então
Para 1 ≤ i ≤ W encontrar λi contíguo livre
Saída:
Requisições atendidas e bloqueadas
Todos os algoritmos possuem como entrada um grafo G = (V, E), que representa a rede que está sendo analisada. Os mesmos possuem como entrada também um conjunto de requisições geradas de forma aleatória e o número de comprimentos de onda que será analisado em cada rede. Para cada requisição é verificado na rede se existe uma rota para a requisição e se existem comprimentos
de onda livres e contíguos para cada uma delas. Como saída dos algoritmos ter-se-á as requisições atendidas ou as requisições bloqueadas. A rede G será armazenada em uma matriz I quadrada de ordem i, onde a intersecção da linha i com a coluna j corresponde a um nó denotado por dij. As requisições Γ = {τ1, τ2,....τr} serão representadas através de uma matriz Rij= L × 2, onde L
representa o número de requisições a serem analisadas.
R/WA Fixo/Primeiro-Encaixe
O R/WA Fixo/Primeiro-Encaixe centralizado, ilustrado pelo pseudocódigo da Figura 3.1, re- cebe como entrada o grafo G (que representa a topologia) e a requisição a ser analisada (τ (Ns, Nd)).
Durante a execução do algoritmo é buscada uma rota em um único caminho mais-curto determi- nado através da utilização do algoritmo de Dijkstra para cada requisição (Passo 1). Caso seja encontrada a rota, é escolhido o primeiro comprimento de onda livre em todos os enlaces da rota (restrição de continuidade) de menor índice (Passo 2). Caso uma das condições anteriores não seja satisfeita, ou as duas não sejam satisfeitas, a requisição sendo analisada é bloqueada (Passo 3). Caso contrário a mesma é alocada. Como saída do algoritmo tem-se a requisição alocada ou a requisição bloqueada. No caso da requisição bloqueada, a mesma entra no cálculo da probabilidade de bloqueio.
Figura 3.1: Pseudocódigo Fixo/Primeiro-Encaixe
R/WA Fixo-Alternado/Primeiro-Encaixe
O R/WA Fixo-Alternado/Primeiro-Encaixe centralizado, ilustrado pelo pseudocódigo da Figura 3.2, recebe como entrada o grafo G (que representa a topologia) e a requisição a ser analisada (τ (Ns, Nd)). Durante a execução do algoritmo é buscada uma rota no primeiro caminho mais-
curto (considerado a rota principal), o qual é determinado através da utilização do algoritmo de Dijkstra para cada requisição . Caso seja encontrada a rota, é escolhido o primeiro comprimento de onda livre e contínuo em todos os enlaces da rota (restrição de continuidade)(Passo 1). Caso o caminho/rota não atenda à requisição, é buscada uma rota no segundo caminho mais-curto (rota alternativa), a qual também é encontrada pela aplicação do algoritmo de Dijkstra e se for encon- trada essa rota, é escolhido o primeiro comprimento de onda que também esteja livree contínuo em todos os enlaces do caminho (Passo 2 e Passo 3). Se a busca for feita nas duas rotas e uma
das condições anteriores não for satisfeita, ou as duas não forem satisfeitas, a requisição sendo analisada é bloqueada. Como saída do algoritmo tem-se a requisição alocada ou bloqueada e a requisição bloqueada entra no cálculo da probabilidade de bloqueio.
Figura 3.2: Pseudocódigo Fixo-Alternado/Primeiro-Encaixe
RWA Melhor-Encaixe
O RWA Melhor-Encaixe centralizado, ilustrado pelo pseudocódigo da Figura 3.3, recebe como entrada o grafo G (que representa a topologia) e a requisição a ser analisada (τ (Ns, Nd)). Durante
a execução do algoritmo é feita uma cópia da topologia que está sendo analisada para cada com- primento de onda. Em cada uma dessas cópias, diante de uma determinada requisição gerada é buscado o caminho mais-curto através do algoritmo de Dijkstra (Passo 1). Depois é comparada a rota encontrada em cada uma das cópias e é escolhida a cópia que apresenta o menor custo dentre todas as rotas encontradas . Em seguida, aquele caminho é excluído da cópia da topologia escolhida (Passo 2). Como pode ser verificado, neste tipo de RWA, o roteamento e a alocação de comprimentos de onda são feitos de forma conjunta. Como saída do algoritmo tem-se a requisição alocada ou bloqueada e a requisição bloqueada entra no cálculo da probabilidade de bloqueio.
Figura 3.3: Pseudocódigo Melhor-Encaixe
3.2.2 Redes Analisadas
As três redes utilizadas nas simulações e análises são as redes ilustradas pela Figura 3.4 e são: NFSNET, USA e PAN-EUROPÉIA. A NFSNET consiste em uma rede de backbone composta
por 16 nós e 25 enlaces bidirecionais. A USA é uma rede de backbone composta por 24 nós e 43 enlaces bidirecionais. A PAN-EUROPÉIA é uma rede de backbone formada por 28 nós e 41 enlaces também bidirecionais.
Figura 3.4: Redes NFSNET, USA e PAN-EUROPÉIA
3.2.3 Definição do Modelo de Análise
Durante todo o processo de simulação o modelo de análise considerado possue algumas re- strições, que são explicitadas abaixo:
• As requisições são randomicamente/incrementalmente geradas e são servidas em uma maneira FIFO;
• Todos os enlaces são bidirecionais;
• Os algoritmos de roteamento a serem analisados serão fixo e fixo-alternado;
• A heurística de alocação de comprimentos de onda usada (W A) nas simulações em combi- nação com os algoritmos de roteamento citados anteriormente é Primeiro-Encaixe.
• É analisado também o algoritmo Melhor-Encaixe, que faz a análise do problema RWA de forma conjunta.
• A Probabilidade de Bloqueio é computada semelhante ao modelo utilizado em [30]:
Pb = Rna/Rg (3.2)
onde Rna representa o número de requisições não atendidas e Rg representa o número de
requisições geradas;
• A carga/tráfego é calculada em Erlang segundo fórmula proposta por [42] e o tempo entre chegada das requisições obedecem a distribuição de Poisson [44];
• Os parâmetros das simulações: rede, RWA, número de comprimentos de onda (W ) e número de requisições (K) estão ilustrados através da Tabela 3.1. Então, a execução de uma sim- ulação consiste dos seguintes quatro parâmetros (rede, RWA, W , K). Os valores utilizados para as requisições foram K = 100 e K = 2000 e os resultados foram obtidos a partir de uma média de 100 (cem) execuções.
Tabela 3.1: Cenário simulado
Rede RWA W K NFSNET (16 nós) Fixo/Primeiro-Encaixe [4,..,12] 100/2000 NFSNET (16 nós) Fixo-Alternado/Primeiro-Encaixe [4,..,12] 100/2000 NFSNET (16 nós) Melhor-Encaixe [4,..,12] 100/2000 USA(24 nós) Fixo/Primeiro-Encaixe [4,..,12] 100/2000 USA(24 nós) Fixo-Alternado/Primeiro-Encaixe [4,..,12] 100/2000 USA(24 nós) Melhor-Encaixe [4,..,12] 100/2000 PAN-Européia (28 nós) Fixo/Primeiro-Encaixe [4,..,12] 100/2000 PAN-Européia (28 nós) Fixo-Alternado/Primeiro-Encaixe [4,..,12] 100/2000 PAN-Européia (28 nós) Melhor-Encaixe [4,..,12] 100/2000 3.2.4 Simulações
O programa de simulação criado consiste em vários programas separados onde cada um simula o comportamento dos mesmos conjuntos de requisições geradas para diferentes RWAs e o mesmo foi implementado na linguagem do Matlab 7.4.0. Os parâmetros de entrada do simulador, conforme Tabela 3.1, são a rede (com o número de nós), o intervalo de comprimentos de onda no qual aquela rede será analisada, o algoritmo de roteamento e alocação de comprimentos de onda, e a quantidade de requisições que o programa quer simular. O programa termina somente quando o número de requisições escolhido é alcançado. Na chegada de uma requisição é gerado o seu tempo de permanência na rede. O evento seguinte é a chegada da próxima requisição. Antes de se verificar se os recursos requeridos pela nova requisição estão disponíveis na rota desejada, o programa decrementa a(s) conexão(ões) em andamento na rede pelo tempo entre chegadas das requisições. Após o decremento, são desativadas aquelas conexões para as quais não tenha sido constatada a
existência de tempo residual. Feito isso, caso haja algum comprimento de onda disponível na rota desejada, a chamada é estabelecida e também é atualizada uma estrutura de dados (matriz de segmentos) do programa que gerencia todas as conexões existentes. Caso nenhum comprimento de onda esteja disponível, a requisição é bloqueada e entra no cálculo da probabilidade de bloqueio. As simulações foram realizadas em dois tipos de computadores: computador Intel Core 2 Duo de 1.83 Ghz com 2 Gb de RAM e sistema operacional Windows XP e computador Intel Core 2 Duo 2.0 Ghz com 3 Gb de RAM e sistema operacional Windows Vista. Foram realizadas dois tipos de simulaões: estática e dinâmica.O objetivo de se realizar os dois tipos de simulações é verificar a diferença de funcionamento dos RWAs em 2 (duas) situações diferentes.
Na simulação estática foram realizadas simulações nas 3 (três) redes citadas anteriormente com 100 (cem) requisições, considerando o tempo de alocação infinito e a taxa entre chegada de requisições de 1s segundo distribuição de Poisson. Nesse tipo de simulação as requisições não são desalocadas. Esse teste foi realizado com o intuito de analisar qual dos três algoritmos citados anteriormente apresenta um melhor desempenho em relação à quantidade total de requisições alocadas que podem ser mantidas na rede WDM. Na simulação dinâmica também foram realizadas simulações nas 3(três) redes citadas anteriormente com 2000 (duas mil) requisições, tempo de alocação constante de 180 s (3 minutos) e com uma taxa de chegada entre requisições de µ = 1s segundo a distribuiçáão de Poisson. Quando o tempo entre requisições é pequeno, como 1s, o número de requisições alocadas na rede torna-se maior.