Download PDF
ads:
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial
DISSERTAÇÃO
apresentada à UTFPR
para obtenção do grau de
MESTRE EM CIÊNCIAS
por
EDUARDO YABCZNSKI
ALGORITMOS PARA SOLUÇÃO DO PROBLEMA DE ATRIBUIÇÃO
DE CAPACIDADES DISCRETAS EM REDES TCP/IP
Banca Examinadora:
Presidente e Orientador:
Prof. Dr. EMILIO CARLOS GOMES WILLE UTFPR
Examinadores:
Prof
a
. Dr
a
. KEIKO VERÔNICA ONO FONSECA UTFPR
Prof. Dr. EDUARDO PARENTE RIBEIRO UFPR
Curitiba, 23 de novembro de 2007.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
EDUARDO YABCZNSKI
ALGORITMOS PARA SOLUÇÃO DO PROBLEMA DE ATRIBUIÇÃO
DE CAPACIDADES DISCRETAS EM REDES TCP/IP
Dissertação apresentada ao Programa de Pós-
Graduação em Engenharia Elétrica e Informática
Industrial da Universidade Tecnológica Federal
do Paraná como requisito parcial para a obtenção
do título de "Mestre em Ciências" - Área de
Concentração: Telemática.
Orientador: Prof. Dr. Emilio Carlos Gomes
Wille
Curitiba
2007
ads:
AGRADECIMENTOS
O meu mais profundo agradecimento ao meu orientador Emilio C. G. Wille pela dedicação,
ajuda, e principalmentepelaimensa paciência. Soumuitograto e espero conservar sua amizade.
Aos meus pais Nelson e Neuzi, pelo amor, apoio e confiança.
À minha irmã Erika, que colaborou assumindo os compromissos do lar.
Aos amigos Clóvis, Marisângela, Kleber, Lincoln e Tamara que sempre estiveram prontos
a ajudar. Quando precisarem, contem comigo.
SUMÁRIO
Lista de Figuras .............. . . . . . . . . . . ........ . . . . . . . . . . . .. . . . . . . . . . . ........ . . . vi
Lista de Tabelas ... . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . ........ . . . . . . . . . . .. . . vii
Lista de Abreviaturas . . . . . .. . . . . . . . . . . . ........ . . . . . . . . . . ........ . . . . . . . . . . .. . . . . . viii
Resumo . . ........ . . . . . . . . . . ........ . . . . . . . . . . .. . . . . . . . . . . ........ . . . . . . . . . . . ..... ix
Abstract........ . . . . . . . . . . . ........ . . . . . . . . . . .. . . . . . . . . . . ........ . . . . . . . . . . ....... x
1 INTRODUÇÃO .. . . ........ . . . . . . . . . . .. . . . . . . . . . . . ........ . . . . . . . . . . ........ . . 11
1.1 OBJETIVOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 ESTRUTURA DA DISSERTAÇÃO . . . . . . . . . . . . . . . . . . . . . . . 13
2 METODOLOGIA. . . ........ . . . . . . . . . . ........ . . . . . . . . . . . .. . . . . . . . . . . ........ . 14
2.1 METODOLOGIA DE PROJETO DE REDES IP . . . . . . . . . . . . . . . . 14
2.2 TRADUTOR DE QoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 MODELO DE REDES IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 MODELOS DE TRÁFEGO . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Modelo de Fila M
[X]
/M/1 . . . . . . . . . . . . . . . . . . . . . . . . 17
3 ATRIBUIÇÃO DE CAPACIDADES DISCRETAS. . . . ........ . . . . . . . . . . ........ . 19
3.1 REVISÃO BIBLIOGRÁFICA . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 O PROBLEMA DE ATRIBUIÇÃO DE CAPACIDADES . . . . . . . . . . . . 21
3.3 PROPOSTAS DE SOLUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1 Busca Exaustiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Otimização por Enxame de Partículas . . . . . . . . . . . . . . . . . . 24
3.3.3 Aplicando PSO no Planejamento de Redes . . . . . . . . . . . . . . . 26
3.3.4 Heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 COMPLEXIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 UM LIMITANTE INFERIOR PARA O CUSTO DE REDE . . . . . . . . . . . 29
4 ATRIBUIÇÃO DE BUFFER. . . . . . . . . ........ . . . . . . . . . . . ........ . . . . . . . . . . .. . . . 32
4.1 FORMULAÇÃO MATEMÁTICA . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 SOLUÇÃO EXISTENTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3 PROPOSTA DE SOLUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.1 Método para a Solução do BA . . . . . . . . . . . . . . . . . . . . . . 35
4.4 COMPLEXIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 SIMULAÇÕES E VALIDAÇÃO DOS RESULTADOS. .... . . . . . . . . . . .. . . . . . . . . . . 38
5.1 CENÁRIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 RESULTADOS NUMÉRICOS E ANÁLISE . . . . . . . . . . . . . . . . . . . 39
5.3 SIMULAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6 CONCLUSÃO E TRABALHOS FUTUROS .. . . . . . . . . ........ . . . . . . . . . . . ....... 52
Referências Bibliográficas. . . . . . . ........ . . . . . . . . . . .. . . . . . . . . . . ........ . . . . . . . . . . . . 55
ANEXO ...... . . . . . . . . . . ........ . . . . . . . . . . .. . . . . . . . . . . ........ . . . . . . . . . . ......... . 57
Anexo A - Matriz ∆ Referente a Topologia #1 . . . . . . . . . . . . . . . . . . . . . 57
v
LISTA DE FIGURAS
2.1 Diagrama de blocos da metodologia empregada no trabalho. . . . . . . . . . . 14
2.2 RestriçõesRTT para a camada de transportedadas pelo tradutor de QoS (WILLE,
2004) (figura conforme original) . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1 Rede de computadores com 3 nós e 6 enlaces. . . . . . . . . . . . . . . . . . . 22
5.1 Curvas M
[X]
/M/1/B e da equação (4.10) para o enlace 4. . . . . . . . . . . . . 45
5.2 Latência para 3 enlaces, topologia #2, N
s
= 5 . . . . . . . . . . . . . . . . . . 48
5.3 Latência para 3 enlaces, topologia #2, N
s
= 10 . . . . . . . . . . . . . . . . . . 48
5.4 Latência para 3 enlaces, topologia #2, CR . . . . . . . . . . . . . . . . . . . . 48
5.5 Latência para 4 enlaces, topologia #3, N
s
= 5 . . . . . . . . . . . . . . . . . . 50
5.6 Latência para 4 enlaces, topologia #3, N
s
= 10 . . . . . . . . . . . . . . . . . . 50
5.7 Latência para 4 enlaces, topologia #3, CR . . . . . . . . . . . . . . . . . . . . 51
LISTA DE TABELAS
5.1 Topologias utilizadas nos testes. . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 PSO para topologia #1 e tráfego #1.a. . . . . . . . . . . . . . . . . . . . . . . 39
5.3 PSO para topologia #1 e tráfego #1.b. . . . . . . . . . . . . . . . . . . . . . . 40
5.4 PSO para topologia #2, tráfego #2.a e conjunto com 5 capacidades. . . . . . . . 41
5.5 PSO para topologia #2, tráfego #2.a e conjunto com 10 capacidades. . . . . . . 41
5.6 PSO para topologia #3, tráfego #3.a e conjunto com 5 capacidades. . . . . . . . 42
5.7 PSO para topologia #3, tráfego #3.a e conjunto com 10 capacidades. . . . . . . 42
5.8 Teste com a rede de 48 enlaces. . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.9 Cálculos para topologia #1, tráfego #1.a e conjunto com 5 capacidades. . . . . 45
5.10 Dados de 3 enlaces da topologia #2. . . . . . . . . . . . . . . . . . . . . . . . 46
5.11 Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 5 e topologia #2. 46
5.12 Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 10 e topologia #2. 47
5.13 Resultados da simulação e do modelo M
[X]
/M/1/B para CR e topologia #2. . . 47
5.14 Dados de 4 enlaces da topologia #3 . . . . . . . . . . . . . . . . . . . . . . . . 49
5.15 Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 5 e topologia #3. 49
5.16 Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 10 e topologia #3. 49
5.17 Resultados da simulação e do modelo M
[X]
/M/1/B para CR e topologia #3. . . 49
Lista de Abreviaturas
AEC Ajuste do Enlace Crítico
BA Buffer Assignment
CA Capacity Assignment
CTMC Continuous Time Markov Chain
ES Exaustive Search
GA Genetic Algorithms
IP Internet Protocol
LRD Long Range Dependent
NS Network Simulator
PSO Particle Swarm Optimization
QoS Quality-of-Service
RED Random Early Detection
RTT Round Trip Time
SA Simulated Annealing
SLA Service Level Agreement
TCP Transmission Control Protocol
viii
RESUMO
A presente dissertação trata do dimensionamento de redes IP sujeitas ao tráfego TCP. A
metodologiausada foi recentemente apresentada na literatura e consiste em mapear as restrições
do usuário em restrições da camada de rede, e no uso de um modelo refinado de tráfego TCP.
Os problemas considerados correspondem à Atribuição de Capacidades (Capacity Assignment)
discretas e à Atribuição de Buffer (Buffer Assignment). Na formulação destes problemas leva-
se em consideração restrições de qualidade de serviço (Quality-of-Service) vistas pelo usuário
final.
No problema de Atribuição de Capacidades discretas, os valores de capacidades para cada
enlace são escolhidos de um conjunto discretos de valores. Para a solução deste problema são
propostas três técnicas: Busca Exaustiva (ES - Exaustive Search), Otimização por Enxame de
Partículas (PSO - Particle Swarm Optimization)e uma heurística baseada em restrições. Ainda,
para o problema CA, é proposto um algoritmo para calcular um limitante para o custo de rede.
O problema de Atribuição de Buffer busca atribuir o tamanho dos buffers da rede, de forma
otimizada. Para solução deste problema é proposto um método que faz uso de uma função
analítica aproximada para o cálculo de probabilidade de perda de pacotes na rede.
As técnicas de solução propostas são verificadas pela comparação dos desempenhos teóri-
cos calculados com aqueles obtidos via simulação usando o software NS-2.
ABSTRACT
This dissertationis concerned with the dimensioning of IP networkswhen submitted to TCP
traffic. The methodology used was recently presented in the related literature and it consists in
mapping restrictions of the user into restrictions of the network layer, and in the use of a refined
TCP traffic model. The problemstaken into account are the Discrete Capacity Assignment (CA)
and the Buffer Assignment (BA). Quality of Services (QoS) restrictions as seen by the end-user
are considered in the work up of these problems.
In the issue of Discrete Capacity Assignment, capacity values for each network link are
chosen based on a set of discrete values. Three techniques are proposed to deal with it: Exaus-
tive Search (ES), Particle Swarm Optimization(PSO) and a restriction based heuristic. Also, for
comparation purposes, an algorithmto calculate a lower bound for the network cost is proposed.
The Buffer Assignment issue tries to assign buffer network sizes in an optimized way.
To deal with it a method that uses a closed form analytic function to calculate packet loss
probability is proposed.
These proposed techniques are verified by the comparison of theoretical performance cal-
culated values with the results obtained through simulation using the NS-2 package.
11
1 INTRODUÇÃO
Diversos modelos matemáticos para projeto e planejamento, de forma otimizada, redes de
comutação de pacotes, foram extensivamente investigados no passado e tiveram início com o
trabalho clássico de Kleinrock (KLEINROCK, 1976),(GERLA; KLEINROCK, 1977). Contudo
esses modelos consideravam somente a infra-estrutura da camada de rede, ignorando fatores
como a qualidade de serviço (QoS - Quality-of-Service) para usuários finais e o acordo de
nível de serviço (SLA - Service Level Agreement). Hoje em dia estes modelos tornaram-se
inapropriados, pois pela rede de telecomunicações circula uma variedade de serviços críticos
que necessitam que a rede garanta certos níveis de qualidade aos usuários finais. Portanto é
necessário criar novos modelos e metodologias que permitam um planejamento adequado dos
recursos da rede para a entrega dos inúmeros serviços com a qualidade de serviço desejada e ao
mesmo tempo a baixo custo.
Análises recentes do tráfego na Internet mostram que o processo de chegada dos pacotes
IP nas interfaces dos roteadores não é um processo de Poisson (PAXSON; FLOYD, 1995),
pois há correlação entre pacotes que chegam em instantes diferentes, exibindo características
LRD (Long Range Dependent) (PARK; WILLINGER, 2000). Este comportamento pode ser
atribuído aos mecanismos de controle do protocolo TCP e faz com que os modelos tradicionais
(M/M/1 e M/M/1/B) não modelem corretamente a rede. Em (FRALEIGH; TOBAGI; DIOT,
2003), os autores pela primeira vez utilizam um modelo de tráfego LRD, mais especificamente,
um modelo baseado em Movimento Browniano Fracional (Fractional Brownian Motion). In-
felizmente, a expansão deste modelo para considerar problemas gerais de análise e projeto, é
difícil, pois não é possível obter uma função matemática fechada que expresse as relações entre
tráfego, capacidades e atrasos de filas.
Em (WILLE, 2004) o autor propõem uma metodologia de projeto de redes IP que con-
sidera a dinâmica das redes de pacotes, assim como os efeitos dos protocolos nas diferentes
camadas e na QoS experimentada pelos usuários finais. Primeiramente, os índices de desem-
penho dos usuários finais são mapeadas em índices de desempenho da camada de transporte e
dessa, mediante outro mapeamento, para índices de desempenho da camada de rede. Este pro-
12
cesso de mapeamento é então usado em conjunto com um modelo de tráfego TCP/IP (proposto
em (GARETTO; TOWSLEY, 2003), que produz uma boa estimativa do desempenho da rede
sujeita à padrões de tráfego real) para o dimensionamento de uma rede IP.
O processo de dimensionamento pode ser visto como um processo de otimização, onde
se busca minimizar uma função custo e ao mesmo tempo satisfazer uma série de restrições
associadas ao desempenho da rede.
Porém, em (WILLE, 2004), no processo de otimização utilizado, são considerados valores
contínuos de capacidades. Geralmente este não é o caso em sistemas realísticos. No pre-
sente trabalho, será apresentado o problema de Atribuição de Capacidades (CA - Capacity
Assignment) discretas, sujeito a restrições de QoS fim-a-fim, onde os valores de capacidades de
tráfego para cada enlace, são escolhidos de um conjunto discreto de valores, bem como serão
propostas algumas técnicas de solução.
Ao considerar o protocolo da camada de transporte como sendo TCP, também é necessário
resolver o problema de Atribuição de Buffer (BA - Buffer Assignment) que resulta na atribuição
do tamanhodos buffers da rede, de forma otimizada. Neste trabalho é proposta uma novatécnica
de solução para o caso droptail.
1.1 OBJETIVOS
O objetivo desse trabalho é apresentar algumas técnicas de solução para dois problemas
comumente encontrados ao se planejar e projetar uma rede de pacotes IP de forma otimizada:
o problema de Atribuição de Capacidade (CA) e o problema de Atribuição de Buffer (BA).
Estes dois problemas podem ser vistos como dois problemas de otimização onde se busca mi-
nimizar uma função custo e ao mesmo tempo satisfazer uma série de restrições associadas ao
desempenho da rede.
Para o problema de Atribuição de Capacidade discretas, sujeito a restrições de QoS fim-a-
fim, onde os valores de capacidades de tráfego para cada enlace, são escolhidos de um conjunto
discreto de valores, serão consideradas como restrições os atrasos médios nas transmissões fim-
a-fim. Como propostas de solução serão utilizadas a busca exaustiva, a otimização por enxame
de partículas e uma heurística baseada em restrições. Um método para encontrar um limitante
inferior para o custo da rede, utilizando valores contínuos de capacidades, também é proposto.
Para o problema de Atribuição de Buffer, que resulta na atribuição do tamanho dos buffers
da rede, de forma otimizada, serão consideradas como restrições a probabilidade de perdas de
13
pacotes nas transmissões fim-a-fim. Como proposta de solução, será empregada uma função
analítica aproximada e um algoritmo baseado no método de Iteração Linear.
1.2 ESTRUTURA DA DISSERTAÇÃO
Esta dissertação está organizada em seis capítulos. No capítulo 2 é apresentada a metodo-
logia utilizada na dissertação e o modelos de infra-estrutura de redes e de tráfego. No capítulo
3 é abordado o problema de atribuição de capacidades discretas. Neste capítulo é feita uma
pequena revisão bibliográfica e apresentada a formulação do problema, bem como um exemplo
ilustrando as dificuldades na obtenção de resultados satisfatórios. Ainda, neste capítulo, serão
propostas algumas técnicas para a solução do problema. O Capítulo 4 descreve o problema de
atribuição de buffers para os enlaces da rede e sua formulação. Também, neste capítulo, são
apresentados um método de solução existente e uma nova proposta de solução para o problema.
No Capítulo 5 apresentam-se resultados utilizando os métodos/algoritmospropostos bem como
simulações utilizando o software Network Simulator (MCCANNE; FLOYD, 1995) para validar
as propostas. E, finalmente, o Capítulo 6 apresenta a discussão dos resultados e as propostas
para trabalhos futuros.
14
2 METODOLOGIA
Neste capítuloencontra-se uma breve introdução sobre a metodologiaempregadaem (WILLE,
2004) e utilizada nesta dissertação, onde as restrições de QoS do usuário são mapeadas em
restrições da camada de rede. Na primeira seção é apresentado o diagrama que representa a
metodologia empregada. Na segunda seção é mostrado quais as camadas e quais as variáveis
presentes no processo de mapeamento de restrições entre as camadas TCP/IP. Na terceira seção
é visto como a infra-estrutura de rede é modelada. Na quarta seção é apresentado o modelo de
fila utilizado para representar o tráfego.
2.1 METODOLOGIA DE PROJETO DE REDES IP
A metodologia para projetos de redes IP empregada aqui, é a mesma proposta em (WILLE,
2004),(WILLE et al., 2006),(WILLE et al., 2004) e será resumida nesta e na próxima seção.
O problema de dimensionamento é dividido em vários subproblemas que são resolvidos sepa-
radamente. Este tipo de aproximação na resolução do problema de otimização de rede, produz
resultados sub-ótimos mas se faz necessário devido a dificuldade (complexidade) em se obter
uma solução global. A figura 2.1 mostra o diagrama que representa a metodologia empregada,
onde se observam dois grandes blocos (Tradutor de QoS e Procedimentos de Otimização).
CA
L
t
BA
T
h
Valores ´otimos
para as
vari´aveis
do projeto
P
loss
Procedimentos
de
Otimiza¸c˜ao
Tradutor
de
QoS
RT T
• Topologia
• Custos
• Matriz de Tr´afego
Figura 2.1: Diagrama de blocos da metodologia empregada no trabalho.
Como restrições de entrada serão consideradas, para todo par origem-destino, as especifi-
15
cações de QoS do usuário. Após passar pelo tradutor de QoS, as restrições de QoS da camada
de usuário são mapeadas em restrições de camadas inferiores até a camada de rede.
O bloco responsável pelo processo de otimização da rede tem como entradas, a descrição
da topologia física da rede, a matriz de tráfego, o esquema de roteamento e as expressões de
custo em função das variáveis do projeto (capacidade de enlaces e tamanho de buffers), além da
saída do tradutor de QoS. As saídas do bloco de otimização, correspondem aos valores ótimos
(sub-ótimos) para as variáveis do projeto.
Na metodologia empregada, o problema de atribuição de capacidade para os enlaces, é
resolvido separadamente do problema de atribuição de buffer. Primeiramente o processo de
otimização para atribuição de capacidades discretas para os enlaces é resolvido considerando
buffers infinitos. Só então, o processo de otimização para atribuição de buffer é resolvido.
2.2 TRADUTOR DE QoS
Segundo (WILLE, 2004), considerando a arquitetura de protocolos presentes na Internet,
nota-se que pelo menos dois processos de mapeamento devem ser considerados: primeiro as
restrições de QoS da camada de aplicação são mapeadas em restrições de QoS da camada de
transporte, depois as restrições da camada de transporte são mapeadas em restrições da camada
de rede, como RTT (Round Trip Time) e probabilidade de perda de pacotes (P
loss
).
O mapeamento do QoS da camada de transporte para o QoS da camada de rede é o mais
crítico, pois o TCP implementa algoritmos para controle de erro, controle de fluxo e congesti-
onamento. Neste caso o mapeador de QoS aceita como entradas de restrições a latência média
(tempo médio para envio de um determinado arquivo usando o protocolo TCP) permitida na
transferência de arquivos (L
t
) ou o throughput mínimo (T
h
). A saída do mapeador de QoS é for-
mada pelo RTT máximo e pelo P
loss
que satisfazem ambas as restrições de entrada. Tomando
como base o artigo (MELLIA; CARPANI; LO CIGNO, 2002) em que foram realizadas medi-
das da distribuição de comprimento de arquivos na Internet, é possível dizer que 85% de todo
o fluxo TCP possui menos que 20 pacotes. Para esses fluxos será considerado como restrição,
a latência máxima permitida na transferência de arquivos (L
t
). Enquanto que fluxos maiores
estarão sujeitos à restrição de throughput mínimo (T
h
).
Geralmente os modelos do TCP tem como entrada parâmetros da camada de rede, isto é,
RTT e P
loss
, e como saída o throughput ou a latência de transferência de arquivos do protocolo
TCP. Para modelar a latência do TCP foi usado o modelo descrito em (CARDWELL; SAVAGE;
ANDERSON, 2000) e chamado aqui de modelo CSA devido ao nome dos autores. Ao consi-
16
derar o throughput será utilizado o modelo presente em (FRALEIGH; TOBAGI; DIOT, 2003)
e chamado aqui de modelo PFTK.
Depois de fixar os valores para as restrições de throughput (T
h
) e probabilidade de perdas
(P
loss
), foi possível obter (por inversão dos modelos TCP) a curva RTT versus latência L
t
. É
esta curva que o tradutor de QoS utiliza para mapear as restrições da camada de transporte em
restrições da camada de rede. A figura 2.2 mostra uma série de curvas RTT versus L
t
para vários
valores de P
loss
. O throughput também é usado para limitar o valor do RTT. Como critério de
projeto tais curvas foram obtidas para fluxos menores ou iguais a 20 pacotes (WILLE, 2004),
entretanto outros valores poderiam ser usados.
File Transfer Latency [s]
Figura 2.2: Restrições RTT para a camada de transporte dadas pelo tradutor de QoS (WILLE,
2004) (figura conforme original)
2.3 MODELO DE REDES IP
A infra-estrutura de rede IP será representada por um grafo direcionado G = (V,E), ondeV
é um conjuntode nós (com cardinalidade N) e E é um conjunto de arestas (com cardinalidade L).
Um caminho é uma sequência (v
1
,e
1
,v
2
,e
2
,··· , v
n−1
,e
l
,v
n
) de nós e arestas. As extremidades
da aresta e
l
∈ E são os nós (v
n
,v
n+1
) ∈ V. Um nó representa um roteador e uma aresta representa
um enlace conectando dois roteadores. Cada interface de saida (com seus respectivos buffers)
de cada roteador, será modelada como uma fila.
O tráfego para cada par origem(s)-destino(d), é transmitido pela rede através de um único
caminho (roteamento não bifurcado), escolhido por um algoritmo de roteamento fixo. Isto
permite que o fluxo f
ij
em cada enlace (i, j), seja facilmente obtido através das tabelas de
17
roteamento e da matriz de tráfego
Γ. O fluxo f
ij
é definido como a quantidade de informação
que trafega (é transmitida)no enlace (i, j) (por segundo). A matriz de tráfego
Γ= {
γ
sd
} é obtida
do tráfego requisitado entre os nós, onde
γ
sd
é a taxa média de transmissão do nó de origem s
ao nó de destino d.
Tanto o fluxo f
ij
, quanto a capacidade C
ij
, definida como a máxima quantidade de infor-
mação que pode ser transmitida pelo enlace (i, j), são dados em bits por segundo (bps). Cada
buffer de cada interface de saida de cada roteador, pode suportar no máximo B
ij
pacotes, e d
ij
será o comprimento físico do enlace (i, j) dados em quilômetros.
2.4 MODELOS DE TRÁFEGO
Para obter uma formulação útil para o problema de projetos de redes é necessário que essa
formulação expresse, com a maior precisão possível, as métricas de interesse, e ao mesmo
tempo tenha baixa complexidade.
Como ditoanteriormente, o processo de chegadados pacotes IP nas interfaces dosroteadores
não é um processo de Poisson (PAXSON; FLOYD, 1995), pois há correlação entre pacotes que
chegam em instantes diferentes exibindo características LRD. Este comportamento é atribuído
aos mecanismos de controle do protocolo TCP e faz com que os modelos tradicionais (M/M/1
e M/M/1/B) não modelem corretamente a rede. Contudo, considerar o modelo de tráfego
como sendo LRD não é nada prático, pois a obtenção de uma fórmula fechada se torna muito
difícil. Para contornar este problema, neste trabalho utiliza-se o modelo de filas M
[X]
/M/1 com
chegada em grupos.
Este modelo foi extensivamente analisado, mostrando-se capaz de prever os indicadores de
desempenho de filas alimentadas por tráfego TCP com boa precisão (GARETTO; TOWSLEY,
2003).
2.4.1 Modelo de Fila M
[X]
/M/1
Como o modelo clássico de filas M/M/1 não é capaz modelar a correlação existente entre
pacotes que chegam nas interfaces dos roteadores em instantes diferentes, é adotado o mo-
delo de filas M
[X]
/M/1, que melhor representa o tráfego em rajadas produzido pelo protocolo
TCP. Este modelo representa uma fila Markoviana com chegadas em grupo. O tamanho do
grupo varia entre 1 e W com distribuição [X], onde W é o tamanho máximo (em segmentos)
da janela TCP. A distribuição [X] é obtida considerando o número de segmentos que a fonte
18
TCP envia em um RTT. Dada a distribuição de comprimento dos fluxos presentes na rede,
é possível calcular a distribuição de tamanho de pacotes [X], através do modelo estocástico do
TCP presente em (GARETTO;TOWSLEY, 2003). Considerando os comprimentos dos pacotes
exponencialmente distribuídos com média 1/
µ
(bits/pacote) (KLEINROCK, 1976),(GERLA;
KLEINROCK, 1977), taxa de chegada
λ
=
µ
. f (pacotes/segundo), e o fator de utilização do
enlace
ρ
= f/C, o atraso médio dos pacotes dado pelo modelo de fila M
[X]
/M/1, pode ser es-
crito como (note que os índices (i, j) foram ignorados para simplificar) (CHAO; MIYAZAWA;
PINEDO, 1999):
T =
K
µ
1
C− f
com K =
m
[X]
+ m

[X]
2m
[X]
(2.1)
onde m
[X]
e m

[X]
correspondem ao primeiro e segundo momentos da distribuição [X].
Ao considerar a probabilidade de perdas, é necessário extender o modelo de filas para
M
[X]
/M/1/B, onde B é o tamanho do buffer. Neste caso, a probabilidade de perda de pacotes é
calculada através da solução da Cadeia de Markov em Tempo Contínuo (CTMC - Continuous
Time Markov Chain) (CHAO; MIYAZAWA; PINEDO, 1999).
19
3 ATRIBUIÇÃO DE CAPACIDADES
DISCRETAS
Este capítulo tem por finalidade apresentar os métodos propostos para a solução do pro-
blema CA discreto. No problema CA discreto as capacidades alocadas para cada enlace da
rede são escolhidas de um conjunto de capacidades discretas. Esta escolha é realizada tendo
como objetivo minimizar o custo da rede e satisfazer as restrições de atrasos nas transmissões
fim-a-fim. Na primeira seção será vista uma pequena revisão bibliográfica. Na segunda seção
o problema de atribuição de capacidades discretas será formulado e também será mostrado um
pequeno exemplo. Na seção três serão apresentadas as propostas de soluções para o problema
CA. Na seção quatro é feita uma análise da complexidade das soluções propostas. Por último é
apresentado como calcular um limitande inferior, com valores contínuos, para o problema CA,
tendo por objetivo encontrar uma solução que será usada para comparar os resultados obtidos
através dos modelos propostos para o problema CA discreto, quando não for possível obter o
valor ótimo discreto devido ao alto tempo de processamento.
3.1 REVISÃO BIBLIOGRÁFICA
A característica comum entre os três trabalhoscitados nesta seção e a dissertação, é o fato de
todos trabalharem com alocação de capacidades discretas, tendo como restrição alguma métrica
relacionada com o atraso na transmissão.
Maruyama e Tang propõem em (MARUYAMA; TANG, 1977) uma heurística para resolver
o problema da alocação de capacidades discretas com diferentes classes de pacotes IP. O ob-
jetivo é minimizar o custo e satisfazer as restrições de atrasos médios especificados para as
diferentes classes de pacotes. O problema de alocação de capacidades é formulado tendo como
restrições um atraso médio de transmissão para cada classe e um conjunto de capacidades dis-
cretas, e seus respectivos custos, para a escolha da capacidade a ser alocada para cada en-
lace. Em seguida, cada classe de pacotes é classificada em um nível de prioridade (Priority
Assignment), objetivando minimizar o custo da rede satisfazendo as restrições. Esta classifi-
20
cação se faz de acordo com o comprimento dos pacotes, o requerimento de atraso na transmis-
são, o comprimento médio do caminho fim-a-fim e a taxa de transmissão. O algoritmo utilizado
para a solução do problema limita a quantidade de níveis de prioridade pelo número de classes,
para não tornar o tempo de execução proibitivamente alto. Diversos testes são realizados e
mostram uma sensível diminuição no custo ao se considerar diferentes níveis de prioridades
para as diferentes classes de pacotes.
Em (ERSOY; LEVI; GUMRAH, 2000), os autores propuseram duas meta-heurísticas ba-
seadas em inteligência artificial para resolver o problema exposto no artigo de Maruyama e
Tang (MARUYAMA; TANG, 1977): Alocação de capacidades discretas em redes com serviços
com prioridades. No artigo (ERSOY; LEVI; GUMRAH, 2000) são feitas comparações entre
dois métodos de inteligência artificial: Têmpera Simulada (SA - Simulated Annealing) e Algo-
rítmos Genéticos (GA - Genetic Algorithms), e o método determinístico de Maruyama e Tang,
chamado de MT-CA. O método SA, fundamentado na analogia com a termodinâmica ao simu-
lar o resfriamento de um conjunto de átomos aquecidos, mostrou ser o mais eficiente e rápido.
Isto fica bem claro quando o tamanho da rede aumenta e o número de classes de pacotes é
grande. Observou-se que o método GA, baseado nas leis da evolução genética, é mais lento do
que o método SA e mais rápido do que o método MT-CA. Outra observação é que o aumento
do tempo computacional do GA, com o aumeto da rede, é bem menor do que o aumento do
tempo computacional sofrido pelo MT-CA, tornando o método GA aplicável principalmente
em problemas que envolvem redes grandes.
No artigo (LIU; IGARASHI; MIYAMOTO,1990), os autores desenvolvemum métodopara
resolver o problema de alocação de capacidades discretas minimizando o custo da rede. Dado
um conjunto de capacidades discretas e seus respectivos custos, para cada enlace é selecionada
a velocidade (tipo) e o número de canais (capacidades), tendo como restrições o atraso médio
fim-a-fim nas transmissões de cada par origem-destino. O método é dividido em três estágios:
O estágio 1 (escolha da velocidade do enlace) e o estágio 2 (cálculo do número de canais para
o enlace) tratam de problemas de otimização não-linear com restrições. No terceiro estágio
(cálculo da solução ótima) é onde ocorre, de fato, a otimização do problema. Neste estágio
são apresentadas as formulações para o cálculo do custo da rede e avaliados os resultados. O
algoritmo previne um aumento desnecessário no valor da capacidade alocada para o enlace
através de duas funções: uma que calcula a significância do enlace, dado pelo número de rotas
que passa pelo enlace; e outra que avalia a economia através da variação que sofre o resultado
do cálculo do atraso médio para o enlace com a variação dos custos dos canais escolhidos.
Além das diferenças evidentes entre os traballhos e a dissertação, tais como: classificação
21
de classes de pacotes em vários níveis de prioridades (MARUYAMA; TANG, 1977),(ERSOY;
LEVI; GUMRAH, 2000) e quantidade de canais alocados para os enlaces (LIU; IGARASHI;
MIYAMOTO, 1990); uma outra diferença muito importante, e não tão evidente, é sobre o mo-
delo de filas utilizado. Nos artigos, o modelo utilizado é o modelo M/M/1, enquanto que na
dissertação, o modelo utilizado é o M
[X]
/M/1 (seguindo o exposto no capítulo 2).
3.2 O PROBLEMA DE ATRIBUIÇÃO DE CAPACIDADES
Nesta seção será apresentado o problema de atribuição de capacidades discretas (CA -
Capacity Assigment), isto é, o problema de seleção de capacidades para os enlaces. Neste
trabalho o problema CA é resolvido considerando como restrições os atrasos (médios) nas
transmissões fim-a-fim. Selecionando i) a função custo, ii) o modelo de roteamento, e iii) as
restrições de capacidades, é possível obter diferentes formulações para o problema CA. Serão
considerados neste trabalho: i) custo linear, ii) roteamento não bifurcado, e iii) capacidades dis-
cretas. Seja a função custo g(d
ij
,C
ij
) =
υ
ij
.d
ij
.C
ij
, onde
υ
ij
é o custo monetário do enlace (i, j)
em $/Mbps/km/ano
1
. Seja
δ
sd
ij
uma função indicadora com o valor 1 se o enlace (i, j) fizer parte
do caminho (s,d) e 0 caso contrário, e S o conjunto de capacidades discretas com cardinalidade
N
s
. Assim, dados: a topologia da rede, o tráfego imposto e o roteamento (fixo), o problema CA
discreto é formulado como sendo o seguinte problema de otimização:
Z
CA
= min
∑
i, j
g(d
ij
,C
ij
) (3.1)
sujeito à:
T
sd
=
K
µ
∑
i, j
δ
sd
ij
C
ij
− f
ij
≤ Atraso
sd
∀ (s,d) (3.2)
f
ij
=
∑
s,d
δ
sd
ij
γ
sd
∀ (i, j) (3.3)
C
ij
> f
ij
> 0 ∀ (i, j) (3.4)
C
ij
∈ S ∀ (i, j) (3.5)
onde Atraso
sd
é o atraso permitido na transmissão fim-a-fim, para o seu cálculo toma-se o RTT
(dividido por dois), obtido do capítulo 2, subtraido do retardo de propagação do caminho. A
função objetivo (3.1) representa o custo total da rede, que é a soma das funções custo de cada
enlace (i, j). A equação (3.2) é a restrição de atraso fim-a-fim para cada par origem-destino. Isto
1
Neste trabalho será utilizado
υ
ij
= 1.00 por simplicidade.
22
quer dizer que a soma total do atraso
T
sd
experimentado pelos fluxos roteados pelo caminho
(s,d), não excederá o Atraso
sd
. Considera-se que o conjunto de pares origem-destino tem
cardinalidade N
m
. A equação (3.3) define o fluxo médio de dados em um enlace. As restrições
(3.4) são restrições de não-negatividade.
1
2
3
12
21
2332
31 13
Figura 3.1: Rede de computadores com 3 nós e 6 enlaces.
Para um melhor entendimentoserá mostradoum pequeno exemploreferente a rede da figura
3.1 formada por três nós e seis enlaces. Quer-se enviar dados do nó 1 para o nó 3 através dos
enlaces (1,2) e (2, 3), e do nó 2 para o nó 1 através dos enlaces (2, 3) e (3,1). Dados os fluxos
f = ( f
12
, f
23
, f
31
, f
21
, f
32
, f
13
), os comprimentros dos enlaces d = (d
12
,d
23
,d
31
,d
21
,d
32
,d
13
),
as restrições atraso = (Atraso
13
,Atraso
21
), as capacidades disponíveis S = (s
1
,s
2
,s
3
,s
4
) e a
matriz
∆ =
δ
sd
ij
=
1 1 0 0 0 0
0 1 1 0 0 0
(3.6)
Devemos encontrar os valores das capacidades dos enlaces C = (C
12
,C
23
,C
31
,C
21
,C
32
,C
13
)
(dentre as disponíveis), visando minimizar o custo e respeitar as restrições.
O número de colunas da matriz ∆ é referente aos enlaces usados na rota entre a origem-
destino e as linhas são referentes às restrições Atraso
sd
. Então:
T
13
=
K
µ
δ
13
12
C
12
− f
12
+
δ
13
23
C
23
− f
23
≤ Atraso
13
(3.7)
T
21
=
K
µ
δ
21
23
C
23
− f
23
+
δ
21
31
C
31
− f
31
≤ Atraso
21
(3.8)
Para respeitar o Atraso
13
, por exemplo, pode-se escolher uma capacidade alta para o enlace
(1,2) e/ou (2,3), mas isso aumentaria o custo. Outro fator que dificulta a escolha da capacidade,
é a amarração entre as várias rotas (s, d). Ao tentar minimizar o custo da rede diminuindo
a capacidade escolhida para um enlace, aumenta o atraso na transmissão em todos os pares
origem-destino que trafegam por aquele enlace. Isto pode acarretar a violação da restrição de
23
atraso permitido (Atraso
sd
) para algum desses pares (exemplo:
T
13
e T
21
amarrado pelo enlace
(2,3)). Na tentativa de minimizar o custo da rede, diminuindo o valor de C
23
, as restrições
Atraso
21
e/ou Atraso
13
podem ser violadas. Lembrando que C
ij
> f
ij
> 0,∀(i, j).
3.3 PROPOSTAS DE SOLUÇÃO
O problema CA discreto, como apresentado na seção anterior, é umproblema de otimização
combinatorial, e o ótimo global pode ser encontrado utilizando o método de busca exaustiva
(Exaustive Search - ES). Contudo este algoritmo consome muito tempo computacional. Uma
solução sub-ótima, e aceitável, pode ser obtida com menor tempo de processamento, utilizando
o método de otimização por enxame de partículas (PSO). Tanto a busca exaustiva, quanto o
método de otimização por enxame de partículas, foram utilizados para a solução do problema
CA. Também é apresentada uma heurística simples para encontrar soluções admissíveis para o
problema CA.
3.3.1 Busca Exaustiva
O algoritmo de busca exaustiva testa todas as combinações possíveis para a solução do
problema e armazena aquela que produzir o melhor resultado. No problema de otimização do
custo da rede, são testadas todas as combinações possíveis de capacidades para todos os enlaces
e armazenada aquela que produzir o menor custo satisfazendo as restrições. Tendo um conjunto
S de capacidades discretas para escolher para cada enlace e sendo L o número de enlaces, então,
para cada enlace (i, j) ∈ L são testadas todas as capacidades presentes no conjunto S. A cada
teste, as restrições são verificadas. Tanto no caso de satisfazer ou não as restrições, uma nova
combinação de capacidades nos enlaces é testada até que todas as combinações possíveis sejam
testadas. Nos casos em que as restrições são satisfeitas e o custo apresentado pela combinação
das capacidades nos enlaces for o menor custo até o momento, seu valor é armazenado. Para
o primeiro enlace varia-se o valor da capacidade, enquanto os outros enlaces, presentes no
cálculo do custo da rede, se mantêm fixos. Tendo testado todas as capacidades para o primeiro
enlace, varia-se o valor da capacidade para o segundo enlace, variando também o valor da
capacidade para o primeiro enlace, enquanto os outros enlaces se mantêm com as capacidades
fixas. Testando todas as combinações, entre esses dois enlaces, já que os outros são fixos, varia-
se o valor da capacidade para o terceiro enlace, variando também o valor da capacidade para o
primeiro e segundo enlaces. Todos os outros enlaces se mantêm com as capacidades fixas. Este
processo se repete até que todas as combinações possíveis entre todos os enlaces, usando todas
24
as capacidades, sejam testadas.
3.3.2 Otimização por Enxame de Partículas
Introduzido em 1995 por Kennedy e Eberhart (KENNEDY; EBERHART, 1995), a otimiza-
ção por enxame de partículas é uma técnica heurística de computação evolucionária, baseada
em população e inspirada em propriedades que surjem do comportamento coletivo de alguns
animais: bando de pássaros, enxame de abelhas e cardume de peixes. Por exemplo, em um
bando de pássaros, a velocidade de cada elemento é dinamicamente ajustada de acordo com a
velocidade dos elementos ao redor. A influência de um pássaro sobre outro, permite que seja
mantida uma distância média entre eles. Fazendo uma analogia com o PSO: os pássaros, voando
em um espaço tri-dimensional em busca de alimentos, correspondem às partículas percorrendo
um espaço n-dimensional a procura de uma solução para o problema. A cada instante (t), a
posição e a velocidade das partículas são ajustadas de acordo com a posição e a velocidade no
instante (t − 1):
V
i
(t) = V
i
(t− 1) +
ϕ
1
.r
1
.[X
blp
− X
i
(t− 1)] +
ϕ
2
.r
2
.[X
bgp
− X
i
(t− 1)] (3.9)
X
i
(t) = X
i
(t− 1) +V
i
(t) (3.10)
onde
ϕ
1
e
ϕ
2
são constantes positivas, r
1
e r
2
são variáveis aleatórias normalmente distribuídas
entre 0 e 1; X
i
(t) = (x
i1
(t),x
i2
(t),· ·· ,x
id
(t)) representa a posição atual da i-ésima partícula;
d é a dimensão da partícula, X
blp
2
representa a melhor posição da partícula (dada pelo seu
melhor fitness); X
bgp
3
representa a melhor posição de todo o enxame até o momento; V
i
(t) =
(v
i1
(t),v
i2
(t),· ·· ,v
id
(t)) é a velocidade da i-ésima partícula. De fato, este últimotermo não tem
a dimensão de velocidade, mas a terminologia usada aqui é a mesma proposta originalmente
(KENNEDY; EBERHART, 1995).
A equação (3.10) descreve como a posição das partículas é dinamicamente ajustada, con-
siderando o deslocamento no espaço n-dimensional dado pela equação (3.9). Observe que a
equação (3.9) é formada por três partes. A primeira parte, chamada de momentum, impede que
a velocidade mude abruptamente. A segunda parte é a parte cognitiva, que permite a partícula
aprender com a sua própria experiência de vôo, memorizando a melhor posição encontrada até
o momento. A terceira parte é a parte social, que representa a colaboração entre as partículas, e
permite que a partícula aprenda com a experiência de vôo do enxame. O ajuste entre estas três
partes determina a convergência global ou local.
2
blp - best local position.
3
bgp - best group position.
25
Quando a soma das três componentes da equação (3.9) excede o valor ±V
max
, especificado
pelo usuário, a velocidade é grampeada para este valor. Isto é necessário para evitar que a
velocidade exploda, crescendo cada vez mais a cada iteração. Valores altos de V
max
fazem com
que as partículas fiquem potencialmente passando sobre as soluções boas, sem nunca atingí-
las. Por outro lado, valores baixos de V
max
podem levar a uma convergência local (mínimo ou
máximo local). Usualmente V
max
é fixo, mas a variação dinâmica também pode ser empregada.
Para avaliar o quão bom é um resultado encontrado por uma partícula é calculado o seu
fitness. O fitness geralmente é uma função baseada na função que se quer maximizar ou mini-
mizar.
O procedimento para implementação do PSO original é mostrado a seguir (KENNEDY; EBER-
HART, 2001):
1. Inicialize a população de partículas com posições e velocidades distribuídas aleatoria-
mente no espaço n-dimensional de busca.
2. Calcule o fitness de cada partícula, composto de n variáveis.
3. Compare o fitness de cada partícula, com o do seu próprio X
blp
. Se o valor corrente é
melhor do que o fitness produzido pelo seu próprio X
blp
, atribua a X
blp
o valor corrente
X
i
(t).
4. Atribua a X
bgp
a partícula que representa o melhor fitness encontrado dentre todas as
partículas. Em algumas implementações, topologias de diferentes vizinhanças são usadas
para encontrar seus X
bgp
.
5. Mude a velocidade e a posição da partícula, de acordo com as equações (3.9) e (3.10) e
se necessário grampeie para ±V
max
o valor da velocidade antes de calcular a posição.
6. Volte ao passo 2 até que o critério de parada seja satisfeito. Normalmente um fitness
suficientemente bom ou um número máximo de iterações.
Existem muitas variações do algoritmo descrito. Em geral são usadas várias estratégias para
manter a diversidadeevitando a convergênciarápida (geralmente para ótimos locais). Explosões
periódicas do enxame podem ser utilizadas ao ser observada uma aglutinação das partículas,
aleatorizando novamente suas posições, mas mantendo X
bgp
(LOPES; COELHO, 2005).
Originalmente o PSO foi criado para resolver problemas em um espaço contínuo (variáveis
contínuas). Uma importante implementação foi criada utilizando valores binários, sendo pos-
sível usar o PSO para resolver problemas combinatoriais (LOPES; HEMBECKER; GODOY
26
JR., 2007), (EBERHART; HU; SHI, 2003). Nesta implementação cada elemento do vetor X
i
(t)
é um bit, e a velocidade é usada como uma probabilidade para determinar se cada bit estará
no estado 0 ou 1. Depois do cálculo da velocidade da n-ésima dimensão da i-ésima partícula
(equação (3.9) desta vez com valores binários), é utilizada uma função sigmóide para ajudar a
decidir qual valor terá a partícula.
s(v
in
) =
1
1+ exp(−v
in
)
(3.11)
se r
i
< s(v
in
) então x
in
= 1; de outra forma x
in
= 0. r
i
é uma variável aleatória normalmente
distribuída entre 0 e 1.
Outro incremento muito importante no PSO original foi o uso do peso de inércia w, que
multiplica o termo de velocidade na equação (3.9). Valores altos de w facilitam a busca global,
enquanto valores baixos facilitam a busca local. Geralmente w começa com valores altos e é
decrementado durante a execução do algoritmo (SHI, 2004).
3.3.3 Aplicando PSO no Planejamento de Redes
Como dito anteriormente, a solução do problema CA corresponde a selecionar uma capaci-
dade para cada enlace (dentre um conjunto pré-determinado), sempre respeitando as restrições
de atraso.
Um ponto importante quando se trabalha com processos de otimização com restrições, é de
como tratar essas restrições. Para trabalhar com as restrições, são propostas duas modificações
no PSO original.
1. Durante a inicialização, todas as partículas são repetitivamente inicializadas até satisfaze-
rem todas as restrições.
2. Após o cálculo e arredondamento de X
i
(t) (equação (3.10)), se a capacidadeC
ij
for menor
que o respectivo fluxo f
ij
, o próximo valor de S é escolhido até que a restrição (3.4) seja
satisfeita.
O algoritmo PSO proposto penaliza a partícula (se as restrições não forem satisfeitas)
usando a seguinte função fitness:
fitness =
∑
(i, j)
g(d
ij
,C
ij
), se
T
sd
≤ Atraso
sd
∀ (s,d)
Q·
∑
(i, j)
g(d
ij
,C
ij
), de outro modo
(3.12)
27
Como o que se quer é um fitness baixo e que respeite as restrições, a função fitness penaliza
as partículas que não respeitarem as restrições, multiplicando o fitness dessas pelo fator de
penalização Q. O procedimento a seguir é utilizado na aplicação do PSO para o problema CA
discreto: após o cálculo das equações (3.9) e (3.10), cada variável x
in
é arredondada para um
inteiro maior ou igual a ela. Então este valor é mapeado para um elemento do conjunto S de
capacidades. Por exemplo: tendo quatro valores de S para serem selecionados como possíveis
capacidades de cada enlace, então xmin = 1 e xmax = 4 (onde este intervalo representa os
índices dos valores de S). Seja, X
i
= (0.45, 2.67,2.21) após o arredondamento obtém-se X
i
=
(1,3,3). Se S = (15,20,50,75) então C = (15, 50,50). Mas se f = (12,54,19), a partícula é
arrumada, o que resulta em X
i
= (1,4, 3), gerando C = (15,75,50), que finalmente é utilizado
no cálculo do fitness. Depois de calculado o fitness, X
blp
e X
bgp
, o critério de parada é verificado,
e se não foi atingido, o ciclo se repete.
3.3.4 Heurística
Aqui será mostrada uma heurística simples que permite encontrar soluções admissíveis para
o CA discreto. O objetivo desta heurística não é o de minimizar o custo, e sim o de satisfazer
as restrições, procurando sempre usar os menores valores de capacidade. Esta heurística será
batizada como Ajuste do Enlace Crítico (AEC).
Heurística:
1. Atribua a cada enlace umacapacidade maior que o fluxo de dados que trafega pelo enlace.
Esta capacidade é escolhida como sendo a menor capacidade do conjunto discreto S de
capacidades (para satisfazer a equação (3.4)).
2. Verifique as restrições de atraso (equação (3.2)):
(a) Caso sejam satisfeitas, o algoritmo termina
(b) Caso alguma restrição não seja satisfeita, o algoritmo avança.
3. Determine o enlace de maior atraso (enlace crítico) presente no cálculo da restrição de
atraso (não respeitado) e atribua um valor maior, escolhido do conjunto discreto S de
capacidades, para a capacidade desse enlace.
4. Retorne ao item 2.
Caso a capacidade do enlace no item 3 já seja a maior capacidade do conjunto S, escolhe-
se o segundo enlace crítico presente no cálculo da restrição, para ter a capacidade aumentada.
28
Caso a capacidade do enlace já seja a maior capacidade do conjunto S, escolhe-se o terceiro
enlace crítico, e assim por diante.
3.4 COMPLEXIDADE
Ao se analisar a complexidade dos métodos propostos é preciso observar a taxa com que
este número varia com a variação da dimensão do problema. Assume-se que a avaliação de uma
solução candidata (verificação de admissibilidade) apresenta complexidade
ψ
av
(proporcional
ao número de restrições N
m
).
Para o método de busca exaustiva a complexidade computacional é dada por O(N
L
s
.
ψ
av
),
onde L é o número de enlaces e N
s
é a cardinalidade do conjunto S de capacidades discretas.
É fácil observar, que o tempo de processamento sofre maior influência do número de enlaces
presentes na rede que do número de capacidades a escolher.
Apesar de não garantir o resultado ótimo, o PSO é de fácil implementação e sua complexi-
dade computacional é relativamente baixa (reduzindo o tempo de processamento para encontrar
uma resposta). Sabendo que N
p
é o número de partículas e N
itr
é o número de iterações do PSO,
a complexidade computaconal é O(N
p
.N
itr
.
ψ
av
). É importantelembrar que o número de enlaces
da rede e o número de capacidades a escolher, influenciam diretamente no número de partículas
e no número de iterações do PSO. Geralmente quanto maior o número de combinações pos-
síveis causado pelo aumento do número de enlaces ou/e de capacidades a escolher, maior deve
ser o número de partículas e/ou o número de iterações. Sendo o PSO um algorítmo heurístico,
faz-se necessário executá-lo algumas vezes afim de obter uma estatística do resultado e/ou en-
contrar o resultado ótimo. Ainda assim, o tempo de processamento é pequeno comparado com
o método de busca exaustiva.
Paraa heurísticaproposta no trabalho, a complexidadecomputacionalé dada por O(L
2
.
ψ
av
).
O algoritmo parte com uma solução candidata que é avaliada, com complexidade
ψ
av
. Se a
solução não é admissível, realiza-se o ajuste do enlace crítico com complexidade O(L). Por
fim o algoritmo itera em média L/2 vezes. A implementação é simples, porém não se pre-
ocupa em minimizar o custo, e sim, satisfazer as restrições, o que nem sempre trará resultados
satisfatórios.
29
3.5 UM LIMITANTEINFERIORPARAO CUSTODEREDE
Com o aumento da dimensão da rede, calcular o menor custo, utilizando capacidades dis-
cretas, pelo método de busca exaustiva, torna-se muito caro computacionalmente. Caso não
seja possível (viável) a obtenção de um valor ótimo para o custo da rede por busca exaustiva, os
valores ótimos contínuos de capacidade para cada enlace, serão calculados utilizando o método
dos multiplicadores de Lagrange (REKLAITIS; RAVINDRAN; RAGSDELL, 1983). Isto cor-
responde ao que se chama de relaxamento contínuo, e permite obter um limitante inferior para o
custo de uma rede. A idéia se resume em encontrar o gradiente (se ele existir)em uma superfície
n-dimensional. De forma geral:
Minimize : f(x) (3.13)
sujeito à:
g
l
(x) ≥ 0 l = 1,2, ··· ,L (3.14)
h
k
(x) = 0 k = 1,2, ··· ,K (3.15)
sendo x = (x
1
,x
2
,··· ,x
N
).
Observações:
1. Um ponto x ∈ R é dito factível se satisfizer todas as restrições (equações (3.14) e (3.15))
2. O conjunto das restrições presentes na equação (3.15), define uma superfície S.
3. No espaço das soluções viáveis, uma restrição de desigualdade l pode estar ativa quando
g
l
(x) = 0, ou inativa quando g
l
(x) < 0.
O método dos multiplicadores de Lagrange essencialmente impõe uma série de condições
necessárias para identificar os pontos candidatos a ponto ótimo. Isto é feito convertendo o
problema com restrições em um problema equivalente sem restrições com a ajuda dos mul-
tiplicadores de Lagrange. Devido a equação (3.14), de não-igualdade, algumas condições de
otimização conhecidas como condições de Kuhn-Tucker (REKLAITIS; RAVINDRAN; RAGS-
DELL, 1983) devem ser satisfeitas:
∇f(x) −
L
∑
l=1
υ
l
∇g
l
(x) −
K
∑
k=1
ν
k
∇h
k
(x) = 0 (3.16)
g
l
(x) ≥ 0 l = 1,2, ··· ,L (3.17)
h
k
(x) = 0 k = 1,2, ··· ,K (3.18)
υ
l
g
l
(x) = 0 l = 1,2, ··· ,L (3.19)
30
υ
l
≥ 0 l = 1,2, ··· ,L (3.20)
onde ∇ é o operador corresponente ao gradiente,
υ
l
∈ R e
ν
k
∈ R são os multiplicadores de
Lagrange.
Aplicando o método dos multiplicadores de Lagrange ao problema CA discreto dado pelas
equações (3.1)-(3.5) obtém-se:
L(
υ
ij
) =
∑
ij
d
ij
·C
ij
−
∑
ij
υ
ij
Atraso
sd
−
K
µ
∑
i, j
δ
sd
ij
C
ij
− f
ij
(3.21)
Derivando L(
υ
ij
) e igualando a zero, obtém-se o valor ótimo de capacidades
C
∗
ij
=
∑
ij
δ
sd
ij
υ
ij
d
ij
+ f
ij
(3.22)
Nota-se que as capacidades ótimas são funções dos multiplicadores de Lagrange
υ
ij
. O al-
goritmo de Chromy (CHROMY, 1987) é usado para determinar tais multiplicadores. Tal algo-
ritmo é baseado em uma atualização dosmultiplicadores do tipo quadrática, conforme mostrado
abaixo:
Algoritmo de Chromy:
1. Especificar d
ij
, f
ij
, K,
µ
e a matriz ∆
2. Para a primeira iteração (n=1) fazer
υ
(n)
ij
= 1
3. Calcular
C
(n)
ij
=
∑
ij
δ
sd
ij
υ
(n)
ij
d
ij
+ f
ij
(3.23)
4. Calcular
T
(n)
sd
=
K
µ
∑
i, j
δ
sd
ij
C
(n)
ij
− f
ij
(3.24)
e
υ
(n+1)
ij
=
υ
(n)
ij
T
(n)
sd
Atraso
sd
2
(3.25)
5. Incrementar n e repetir os passos 3 e 4 até que as condições de Kuhn-Tucker sejam satis-
feitas:
(a)
T
(n)
sd
≤ Atraso
sd
31
(b)
υ
(n+1)
ij
[Atraso
sd
−
T
(n)
sd
] ≤
ε
ou se atinja o número máximo de iterações. Observa-se que
ε
é um número pequeno.
Na prática, alguns multiplicadores poderão ser zero, identificando as restrições que não fazem
parte da solução (CHROMY, 1987).
32
4 ATRIBUIÇÃO DE BUFFER
Para que se tenha um projeto completo, além de garantir o atraso médio fim-a-fim para os
vários caminhos na rede, deve-se garantir que a probabilidade de perda de pacotes fim-a-fim
seja inferior a um valor estipulado pelo projetista (P
loss
). Tais valores, atraso médio e P
loss
,
estão intimamente relacionados ao desempenho do protocolo TCP. Na primeira seção deste
capítulo será apresentada a formulação matemática para o problema de atribuição de buffer. Na
segunda seção será mostrada uma solução existente para o problema. Na terceira seção, uma
nova proposta de solução para o problema é discutida. E por fim, na quarta seção será feita uma
análise da complexidade da solução proposta.
4.1 FORMULAÇÃO MATEMÁTICA
O problema de atribuição de buffer (BA - Buffer Assignment) é baseado no modelo de filas
M
[X]
/M/1/B tendo por objetivo dimensionar os buffers dos enlaces da rede. Estes buffers são
dimensionados com o menor tamanho possível, objetivando não ultrapassar P
loss
, já que para
o mesmo tipo de tráfego, quanto menor o buffer, maior a probabilidade de perda de pacotes.
Dados: a topologia, a requisição de tráfego, os fluxos e as capacidades para os enlaces (encon-
tradas através da solução do problema CA), o BA será formulado como o seguinte problema de
otimização:
Z
BA
= min
∑
ij
h(B
ij
) (4.1)
sujeito à
∑
ij
δ
sd
ij
p(B
ij
,C
ij
, f
ij
,[X]) ≤ P
sd
loss
∀(s,d),∀(i, j) (4.2)
B
ij
≥ 0 ∀(i, j) (4.3)
A equação (4.1) é a função objetivo que minimiza o custo total dos buffers na rede, onde B
ij
é
o tamanho do buffer (em pacotes) no enlace (i, j) e h(B
ij
) é a função custo. Por simplicidade
33
h(B
ij
) = b
ij
· B
ij
, onde b
ij
é o custo monetário em $/pacote/ano
1
. Na equação (4.2) tem-se a
restrição de perda de pacotes que é representada pela soma das probabilidades de perda em cada
enlace do caminho (s,d). p(B
ij
,C
ij
, f
ij
,[X]) é a probabilidade de perda de pacotes para a fila
M
[X]
/M/1/B. A equação (4.3) garante que nenhum buffer terá tamanho negativo. É importante
lembrar que a performance do TCP é afetada pela perda dos segmentos de dados no envio e pela
perda dos pacotes de resposta ACKs no caminho inverso, principalmente para fluxos pequenos.
Neste trabalho considerou-se que a probabilidade de perda de ACKs é desprezível.
O problema formuladopode ser classificado com um problema de otimização convexa mul-
tivariávelvinculado; a condição convexa garante a existência de uma única solução, ou seja, um
ótimo global.
4.2 SOLUÇÃO EXISTENTE
Uma proposta de solução para o problema BA foi apresentada em (WILLE, 2004). Tal
proposta utiliza um algoritmo que combina dois métodos: o método da Barreira Logarítmica e
o método das Coordenadas Cíclicas. O método da barreira logarítmica consiste em minimizar
uma função formada pela função objetivo inicial e por uma função que reflita a influência das
restrições. A idéia é transformar um problema com restrições em um problema sem restrições.
Considere o seguinte problema:
Minimize : g
o
(x) (4.4)
sujeito à:
g
i
(x) ≤ 0; i = 1,··· ,m (4.5)
x ∈ R
n
(4.6)
onde g
i
(x) é uma função convexa e contínua em R.
Os pontos em que todas as funções de restrições (equação (4.5)) são negativas é denotado
por Ψ(G) e definido como:
Ψ(G) = {x : g
i
(x) < 0;i = 1, ··· ,m} (4.7)
Um ponto x em Ψ(G) é dito (estritamente) viável. A barreira logarítma é definida como sendo
a função:
φ
(x) =
−
m
∑
i=1
log(−g
i
(x)); g
i
(x) < 0,i = 1,··· ,m
+∞; de outro modo
(4.8)
1
Neste trabalho será utilizado b
ij
= 1.00.
34
Esta função tende ao infinito quando x se aproxima de Ψ(G). O método da barreira consiste na
formulação da função
B(x,t) = g
o
(x) + (1/t)·
φ
(x). (4.9)
onde x ∈ R
n
, e t é um escalar positivo. Dado um ponto inicial (estritamente) viável, é possível
manter este ponto sendo (estritamente) viável, minimizando a função B(x,t). O peso (1/t)
no termo pertencente a barreira
φ
(x), controla a distância da função em relação a barreira.
Quando o peso aumenta, a equação (4.9) é afastada da barreira, quando diminui, é aproximada.
Ao minimizar (4.9), (1/t) diminui com as iterações até próximo de zero, fazendo com que a
equação se aproxime da barreira, sem nunca atingí-la, e convergindo para uma solução x
∗
no
limite de Ψ(G).
Para resolver o problema e minimizar a função B(x,t), o método chamado de coordenadas
ciclícas é utilizado. Este método consiste em partir de um ponto inicial x
1
e minimizar a função
B(x,t) na direção d
1
= (1,0, ··· ,0); encontrando o ponto x
2
que minimiza a função nesta
direção; partindo deste ponto na direção d
2
= (0,1, ··· ,0), minimizando a função encontrando
o ponto x
3
, e assim sucessivamente até chegar ao ponto x
n+1
, onde o ciclo se repete e volta-se
a minimizar na direção d
1
= (1, 0,··· ,0). O vetor direção d
n
, tem o componente n igual a 1 e
todos os outros iguais a 0. O processo se repete até alcançar a precisão desejada.
4.3 PROPOSTA DE SOLUÇÃO
O algoritmo de solução apresentado em (WILLE, 2004) revelou-se de baixa confiabilidade
e com instabilidade numérica, dada a grande dificuldade de integração entre os dois métodos
no qual a proposta está baseada. Desta forma este trabalho propõe uma nova abordagem de
solução.
O modelo de filas M
[X]
/M/1/B não fornece uma fórmula fechada para o cálculo da proba-
bilidade de perda de pacotes, o que dificulta o processo de otimização. A proposta é a utilização
de uma função analítica aproximada (YABCZNSKI; BENTO; WILLE, 2006) que possa ser
tratada por algum método/algoritmo de otimização.
A função aproximada está representada na equação (4.10), onde p
ij
representa a probabi-
lidade de perda de cada enlace (i, j), k é uma constante de ajuste da altura da curva e
α
ajusta
sua inclinação, B é o tamanho do buffer e
ρ
é o fator de utilização do enlace (calculado no CA).
p
ij
= k
(1−
ρ
α
ij
ij
)
ρ
α
ij
B
ij
ij
1−
ρ
α
ij
(B
ij
+1)
ij
(4.10)
35
Na nova abordagem, o primeiro passo consiste em substituir p(B
ij
,C
ij
, f
ij
,[X]) por (4.10)
na formulação do BA.
O problema agora é solucionado com base em uma simples heurística. A idéia consiste em
decompor o problema em n×(n−1) problemas simples (um para cada caminho (s, d)). Seja I
sd
um caminho individual entre origem-destino, e seja B
sd
ij
uma variável auxiliar que representa o
buffer no enlace (i, j) no caminho (s,d). Aplicando o método dos multiplicadores de Lagrange
obtém-se:
L(
ν
) = min
∑
(i, j)∈I
sd
b
ij
B
ij
+
ν
∑
(ij)∈I
sd
k
(1−
ρ
α
ij
ij
)
ρ
α
ij
B
ij
ij
1−
ρ
α
ij
(B
ij
+1)
ij
− P
sd
loss
(4.11)
sujeito à
B
sd
ij
≥ 0 ∀(i, j), ∀(s,d) (4.12)
As soluções são dadas por:
p
sd
ij
=
b
ij
(1−
ρ
α
ij
(B
sd
ij
+1)
ij
)P
sd
loss
ln
ρ
ij
∑
(kl)∈I
sd
(1−
ρ
α
kl
(B
sd
kl
+1)
kl
)b
kl
ln
ρ
kl
(4.13)
Conhecendo os valores de p
sd
ij
(para cada caminho), obtém-se valores admissíveis para as vari-
áveis p
ij
(no problema BA original) fazendo:
p
ij
= min
sd
(p
sd
ij
) ∀(s,d), ∀(i, j) (4.14)
Entretanto, uma dificuldade extra deve ser vencida. Observando-se a equação (4.13) percebe-se
a presença de três grupos de variáveis desconhecidas:
α
ij
, p
sd
ij
e B
sd
ij
. Na presente proposta os
valores de
α
ij
são determinados, uma única vez, pelo ajuste da curva dada pela equação (4.10)
e a curva obtida de M
[X]
/M/1/B (P
loss
obtido pela solução do CMTC).
Os valores de p
sd
ij
e B
sd
ij
são obtidos pelo método da Iteração Linear, partindo de valores de
buffers admissíveis, e iterando até a convergência. Posteriormente (4.14) é calculada.
4.3.1 Método para a Solução do BA
O método da Iteração Linear (BARROSO et al., 1987), também chamado de Método das
Aproximações Sucessivas, é um método computacional útil para encontrar os zeros (míni-
mos/máximos) de funções.
36
A nova proposta de solução é apresentada pelo pseudo-código a seguir:
1. Para calcular o valorde k, basta variar k até encontrar a curva de probabilidade de perda da
fila M
[X]
/M/1/B (p(B
ij
,C
ij
, f
ij
,[X])). Este teste é realizado em um ponto em que a curva
já esteja com a probabilidade de perdas estabilizada, o que geralmente ocorre quando B é
elevado.
2. Para cada enlace calcula-se o
α
ij
. Tomando a equação (4.10) e sabendo os valores de k,
C
ij
, f
ij
e
ρ
ij
:
(a) atribui-se um valor para
α
ij
,
α
∈ [0,1].
(b) varia-se B
ij
de 1 a 1000, por exemplo. Desta forma uma curva dada pela equação
(4.10) é encontrada.
(c) o erro entre as curvas da fila M
[X]
/M/1/B e da equação (4.10) é medido e ar-
mazenado. Volta ao item 2.a incrementando o valor de
α
ij
. Isto se repete até que o
valor de
α
ij
seja 1.
(d) é atribuído a
α
ij
o valor que produzir o menor erro entre as duas curvas.
3. De posse de
α
ij
, é atribuído um valor admissível (elevado) para cada B
ij
.
4. São calculadas as probabilidades de perda para cada enlace em um caminho origem-
destino (p
sd
ij
na equação (4.13)).
5. Um novo valor para B
sd
ij
é encontrado onde o ponto p
sd
ij
(item anterior) toca a curva da fila
M
[X]
/M/1/B para o enlace (i, j).
6. Enquanto o número de iterações não for atingido ou ainda houver variação nos valores de
B
ij
, volte ao item 4. Caso contrário o algoritmo avança.
7. Um novo caminho origem-destino é escolhido e o algoritmo volta ao item 3 até que todos
os caminhos origem-destino tenham sido processados.
8. Calcula-se (4.14).
4.4 COMPLEXIDADE
Sendo N
itr
o número de iterações, N
m
o número de restrições e L o número de enlaces, a
complexidadedo algoritmode solução para o problemaBA é dada por O(L.
ψ
α
+N
m
.N
itr
.L.
ψ
b
).
A operação de determinação dos valores do parâmetro
α
(etapa 2), com complexidade
ψ
α
,
37
é realizada para cada um dos L enlaces. Após esta etapa, o algoritimo de Iteração Linear é
realizado para cada uma das N
m
restricões. Sua convergência requer N
itr
iterações. A cada
iteração, a operação de determinação do valor do buffer na curva M
[X]
/M/1/B (etapa 5), com
complexidade
ψ
b
, é realizada para cada um dos L enlaces.
38
5 SIMULAÇÕES E VALIDAÇÃO DOS
RESULTADOS
Neste capítulo são dimensionadas algumas topologias utilizando os algoritmos propostos,
cuja verificação é realizada através dos dados obtidos por simulações. Na primeira seção será
feita uma breve descrição dos cenários a serem analizados. Na segunda seção serão apresenta-
dos os resultados numéricos e as análises. Na terceira seção será feita a verificação dos resulta-
dos, comparando os resultados numéricos e os resultados obtidos através de simulações usando
o programa Network Simulator 2.29 (MCCANNE; FLOYD, 1995).
5.1 CENÁRIOS
Para testar os métodos propostos para a solução dos problemas CA e BA, três topologias
de redes com tamanhos diferentes foram utilizadas (tabela 5.1). Todas as três topologias foram
geradas aletoriamente. Para as três topologias, a matriz de tráfego foi calculada pela geração de
valores aleatórios uniformemente distribuídos para cada par origem-destino.
Tabela 5.1: Topologias utilizadas nos testes.
Topologia N
◦
de nós N
◦
de enlaces N
◦
de restrições Área km
2
1 5 12 11 215 x 215
2 11 24 15 20 x 20
3 20 48 25 20 x 20
As mesmas restrições de QoS são impostas para todos os pares origem-destino. São elas:
(i) latência inferior a 0.5 s para fluxos TCP com menos de 20 pacotes, e (ii) vazão maior que
512 kbps para fluxos TCP com mais de 20 pacotes. Cada pacote possui o tamanho fixo de 1460
bytes. Fixando Ploss = 0.01 e com o auxílio da figura 2.2 é encontrado como parâmetro de
restrição RTT < 0.07.
Os algoritmos foram implementados em C++, e os experimentos foram executados em um
computador com 512 kBytes de memória RAM e com velocidade de processamento de 1GHz.
39
5.2 RESULTADOS NUMÉRICOS E ANÁLISE
O problema CA discreto foi resolvido para cada topologia utilizando o PSO, o algoritmo
de busca exaustiva (ES) e a heurística proposta. Também foram encontrados os limitantes infe-
riores usando o algoritmo de Chromy.
Após vários testes com o PSO, onde o peso de inércia w inicia em 0.9 e decrementa até 0.4 e
várias combinações entre os valores
ϕ
1
= {0.3,0.6, 0.9,1.5,2.0} e
ϕ
2
= {0.3, 0.6,0.9,1.5,2.0},
optou-se por utilizar w = 0.5+ rand()/2 e
ϕ
1
=
ϕ
2
= 1.49445 (SHI, 2004), já que nenhuma
melhora foi observada utilizando outros valores. Para o fator de penalização do fitness utilizou-
se Q = 4. Como o PSO não é determinístico, 500 experimentos foram executados para cada
combinação de número de partículas (N
p
) e número de iterações (N
itr
). Foram observados o
número de sucessos em detectar o mínimo global usando valores inteiros, os melhores valores,
os valores médios e o desvio padrão.
Primeiramente foi considerada uma rede com 12 enlaces e 11 restrições de atraso (topolo-
gia #1), onde S = (4,6, 10,20,50) [Mbps], d
ij
= 150 [km], ∀ (i, j). Os fluxos para os enlaces
(tráfego #1.a), são f = (16,11,21,21,2, 14,24,19,9,3, 8, 21) [Mbps]. A título de exemplo,
a matriz ∆ será apresentada no anexo. Usando o algoritmo de busca exaustiva foi obtido o
seguinte conjunto de capacidadesC = (20,20,50,50, 4,20,50,50,20, 6,10, 50), correspondente
ao menor custo (melhor resultado) de 52500/ano,o mesmo resultado foi encontrado pela heurís-
tica. O limitante inferior encontrado foi de 30400.02/ano. Um segundo experimento foi reali-
zado usando um outro perfil de tráfego (tráfego #x.b) que corresponde a duas vezes o tráfego
#x.a. Usando o algoritmo de busca exaustiva foi obtido o seguinte conjunto de capacidades
C = (50, 50,50,50,6,50, 50,50,50,10,20,50), correspondente ao menor custo (melhor resul-
tado) de 72900/ano. Novamente a heurística obteve o mesmo resultado da busca exaustiva. O
limitante inferior, encontrado utilizando o algoritmo de Chromy, foi de 55750.02/ano.
As Tabelas 5.2 e 5.3 sintetizam o desempenho do PSO para o primeiro teste.
Tabela 5.2: PSO para topologia #1 e tráfego #1.a.
Probl. N
p
N
itr
Taxa de Suc. Ótimo Valor médio Desv. padrão
1 5 50 345/500 52500 53890.2 2218.16
2 10 50 473/500 52500 52734 1000.12
3 30 50 500/500 52500 52500 0.0
4 5 100 354/500 52500 53731.8 2185.20
5 10 100 478/500 52500 52689 903.55
6 30 100 500/500 52500 52500 0.0
40
Tabela 5.3: PSO para topologia #1 e tráfego #1.b.
Probl. N
p
N
itr
Taxa de Suc. Ótimo Valor médio Desv. padrão
1 5 50 489/500 72900 72982.2 602.31
2 10 50 498/500 72900 72909 201.24
3 30 50 500/500 72900 72900 0.0
4 5 100 496/500 72900 72927 335.08
5 10 100 500/500 72900 72900 0.0
6 30 100 500/500 72900 72900 0.0
Note que o espaço de busca para este problema pode chegar a N
L
s
= 2.4× 10
8
soluções
candidatas. O tempo computacional para resolver o problema usando ES foi de uns poucos
segundos, enquanto o PSO levou em torno de dez segundos. A diferença entre os resultados
das tabelas 5.2 e 5.3 para um mesmo número de partículas e um mesmo número de iterações,
pode ser justificado pela restrição 3.4. Neste primeiro teste, dobrando os valores dos fluxos nos
enlaces (i, j) e mantendo o mesmo conjunto de capacidades discretas a escolher S, reduzimos o
espaço de busca, pois C
ij
sempre deverá ser maior que f
ij
. Por exemplo: para um fluxo de 16
Mbps e pela restrição 3.4 pode-se escolher 20 Mbps ou 50 Mbps como sendo a capacidade para
o respectivo enlace. Já, dobrando o valor do fluxo para 32 Mbps e pela restrição 3.4, o único
valor que se pode escolher para a capacidade do enlace é 50 Mbps.
Observa-se uma redução do desvio padrão relacionado aos valores de custo, tanto em re-
lação ao aumento do número de iterações, quanto em relação ao aumento do número de partícu-
las. Nota-se ainda que o número de partículas é um importante parâmetro associado ao desem-
penho do PSO. O aumento de N
p
faz reduzir o desvio padrão indicando que um número maior
de boas soluções se aproximam da solução ótima.
O segundo teste foi realizado com uma rede de 24 enlaces e 15 restrições de atrasos (topolo-
gia #2). Os valores dos fluxos foram distribuídos entre 5 e 55 Mbps, com média igual a 21.4
Mbps(tráfego #2.a). Utilizou-se dois conjuntos de capacidades a escolher: S= (6, 8,34,51,155),
produzindo um espaço de busca de N
L
s
= 5.9×10
16
; e S = (6,8,10, 15,20,34,40,51,100,155),
que produz um espaço de busca N
L
s
= 10× 10
24
. Para o ES e o primeiro conjunto de capaci-
dades, o tempo computacional requerido para o cálculo foi de aproximadamente cinco horas
e o resultado encontrado apresentou um custo de 9054.21/ano. O mesmo custo foi encon-
trado pela heurística. Para o segundo conjunto o resultado encontrado apresentou um custo de
6548.61/ano. Neste caso, para a heurística, o custo encontrado foi de 6595.41/ano. O limite
inferior foi de 5525.76/ano.
As Tabelas 5.4 e 5.5 resumem o desempenho do PSO para a topologia #2 e tráfego #2.a.
41
O tempo computacional para o primeiro conjunto de capacidades (tabela 5.4) gira em torno de
dez segundos, já para o segundo conjunto (tabela 5.5) gira em torno de um minuto.
Tabela 5.4: PSO para topologia #2, tráfego #2.a e conjunto com 5 capacidades.
Probl. N
p
N
itr
Taxa de Suc. Ótimo Valor médio Desv. padrão
1 10 100 62/500 9054.21 9774.55 677.95
2 30 100 252/500 9054.21 9195.75 215.24
3 50 100 333/500 9054.21 9133.09 122.50
4 10 300 69/500 9054.21 9766.46 662.27
5 30 300 280/500 9054.21 9182.24 208.75
6 50 300 350/500 9054.21 9120.71 115.25
Tabela 5.5: PSO para topologia #2, tráfego #2.a e conjunto com 10 capacidades.
Probl. N
p
N
itr
Taxa de Suc. Ótimo Valor médio Desv. padrão
1 10 100 10/500 6548.61 7071.26 518.22
2 30 100 139/500 6548.61 6661.29 201.07
3 50 100 165/500 6548.61 6615.49 105.87
4 10 300 22/500 6548.61 7041.58 505.59
5 30 300 158/500 6548.61 6652.92 195.79
6 50 300 177/500 6548.61 6607.39 101.74
Como era esperado, as taxas de sucessos apresentados na tabela 5.5 são menores do que
as apresentadas na tabela 5.4, pois o espaço de busca utilizando o conjunto S com 10 capaci-
dades é bem maior do que o espaço de busca utilizando um conjunto S com 5 capacidades.
Portanto, para um mesmo número de partículas e um mesmo número de iterações, a taxa de
sucesso diminui com o aumento do espaço de busca. Observe que apesar da taxa de sucesso ser
menor na tabela 5.5, os desvios padrões geralmente são menores do que aqueles apresentados
na tabela 5.4. Isto se dá porque as diferenças entre os valores que formam o conjunto S com
10 capacidades é menor do que as diferenças entre os valores que formam o conjunto S com 5
capacidades.
Por último foi realizado um terceiro teste com uma rede de 48 enlaces e 25 restrições
de atrasos (topologia #3). Os valores dos fluxos foram distribuídos entre 5 e 90 Mbps, com
média igual a 33.33 Mbps (tráfego #3.a). Utilizou-se dois conjuntos de capacidades a es-
colher: S = (8,34, 44,51,155), produzindo um espaço de busca de N
L
s
= 3.5 × 10
33
; e S =
(10,25,34,44,51,70,90,120,155,190), que produz um espaço de busca N
L
s
= 10× 10
48
. Para
o algoritmo ES não foi possível obter o tempo computacional por ser muito longo. No entanto o
custo mínimo para o primeiro e segundo conjuntos de capacidades a escolher é de 18908.03/ano
e 12605.89/ano respectivamente. Utilizando Chromy, o limitante inferior encontrado foi de
42
11239.95/ano enquanto que para a heurística foi encontrado um custo de 19289.9/ano para o
primeiro conjunto de capacidades e 12887.4/ano para o segundo conjunto.
As Tabelas 5.6 e 5.7 resumem o desempenho do PSO para a topologia #3 e tráfego #3.a.
O maior tempo computacional para o primeiro conjunto de capacidades (tabela 5.6) é o do
problema 5 e gira em torno de vinte segundos, já para o segundo conjunto (tabela 5.7) o tempo
computacional do problema 2 gira em torno de cinquenta segundos e do problema 3 em torno
de oito minutos.
Tabela 5.6: PSO para topologia #3, tráfego #3.a e conjunto com 5 capacidades.
Probl. N
p
N
itr
Taxa de Suc. Ótimo Valor médio Desv. padrão
1 200 500 125/500 18908.03 19185.2 162.56
2 300 500 132/500 18908.03 19179.8 164.36
3 200 800 131/500 18908.03 19180 164.61
4 300 800 148/500 18908.03 19168.9 169.84
5 800 1000 234/500 18908.03 19089 185.16
Tabela 5.7: PSO para topologia #3, tráfego #3.a e conjunto com 10 capacidades.
Probl. N
p
N
itr
Taxa de Suc. Ótimo Valor médio Desv. padrão
1 800 1000 53/500 12605.89 12702.1 149.07
2 1000 2000 75/500 12605.89 12673.1 123.35
3 3000 4000 247/500 12605.89 12612.6 13.98
Observe que os resultados obtidos com o PSO e o conjunto S com 5 capacidades (tabela
5.6), mostram-se instáveis. Além de não haver nenhuma melhora nos resultados com o aumento
do número de iterações N
itr
, e com o aumento do número de partículas N
p
, há uma piora no
desvio padrão. Este problema ocorre devido ao número pequeno de partículas e/ou iterações
em relação ao tamanho do espaço de busca, causando uma espécie de saturação do PSO.
Observe também que, apesar do número de sucessos em encontrar o valor ótimo ser maior
no problema 5 da tabela 5.6 do que no problema 1 da tabela 5.7, o desvio padrão é maior por
ser maior a diferença entre os valores que compõe o conjunto S com 5 capacidades.
Realizando mais alguns testes para a rede com 48 enlaces, observou-se que, conforme a
disposição das linhas (responsáveis pelo cálculo dos atrasos) na matriz ∆, que determina o ca-
minho, obtém-se resultados diferentes para a heurística. Isto pode ser observado na tabela 5.8.
Na coluna 3 é mostrado o resultado dos cálculos usando o algoritmo de Chromy (CR). Nas
colunas 4 e 5 são mostrados os resultados utilizando o método de busca exaustiva (ES/5) e a
heurística do Ajuste do Enlace Crítico (H/5), respectivamente, com um conjunto discreto S de 5
43
capacidades a serem escolhidas. Nas colunas 6 e 7 são mostrados os resultados dos cálculos uti-
lizando o método de busca exaustiva (ES/10) e a heurística do Ajuste do Enlace Crítico (H/10),
com um conjunto discreto S de 10 capacidades a serem escolhidas. O resultado presente na col-
una 8 (H1/10) foi obtido utilizado o mesmo conjunto S de 10 capacidades utilizado no cálculo
de H/10, porém duas das linhas da matriz ∆ foram trocadas de posição. O tempo computacional
da heurística com o conjunto S de 10 capacidades foi de um segundo aproximadamente. As
setas na tabela indicam o tipo de variação do resultado, para aquele enlace, em relação a coluna
anterior.
Observa-se que a heurística deve ser empregada com cautela pois, embora sendo fácil e
rápida, ela visa satisfazer as restrições e não minimizar o custo.
Com a obtenção das capacidades alocadas para os enlaces das três redes propostas, pode-se
agora solucionar o problema BA, já que para os cálculos dos tamanhos dos buffers, e conse-
quentemente, os cálculos das probabilidades de perdas de pacotes, é necessário que se saiba a
capacidade alocada para cada enlace.
De posse do fluxo e da capacidade de cada enlace, é possível calcular o índice de ocupação
dos enlaces
ρ
ij
,∀(i, j) e obter a curva de perdas para a fila M
[X]
/M/1/B. Então encontra-se k,
que é fixo para todos os enlaces, e um
α
ij
para cada enlace (i, j). Por fim, através do método
proposto no capítulo anterior, o tamanho dos buffers e as probabilidades de perdas de pacotes
para os enlaces são encontradas.
Na tabela 5.9 são mostrados todos os valores calculados referentes a topologia com 12
enlaces (considerou-se P
loss
= 0.01). A figura 5.1 mostra as curvas de probabilidade de perdas
de pacotes produzidas pela fila M
[X]
/M/1/B e pela equação (4.10), referentes ao enlace 4.
44
Tabela 5.8: Teste com a rede de 48 enlaces.
.
Enlace Fluxo CR ES/5 H/5 ES/10 H/10 H1/10
1 69 72.76 155 155 90 90 90
2 79 90.69 155 155 120 ⇓ 90 90
3 30 35.50 34 34 34 34 34
4 84 86.07 155 155 90 90 90
5 7 9.59 34 34 10 ⇑ 25 10
6 15 19.08 34 34 34 ⇓ 25 25
7 14 19.19 34 34 25 25 25
8 14 18.34 34 34 25 25 25
9 19 23.36 34 34 25 25 25
10 21 28.24 34 34 25 25 25
11 88 89.67 155 155 90 90 90
12 67 71.59 155 155 70 ⇑ 90 90
13 8 13.47 34 34 25 25 25
14 7 12.78 34 34 10 10 10
15 33 37.99 44 44 44 44 44
16 46 54.70 51 51 70 ⇓ 51 51
17 29 32.44 34 34 34 34 34
18 14 21.24 34 34 25 25 25
19 22 23.77 34 34 25 25 25
20 54 60.59 155 155 70 70 70
21 57 61.25 155 155 70 70 70
22 26 32.16 34 34 34 34 34
23 23 27.20 34 34 25 25 25
24 19 22.64 34 34 25 25 25
25 68 72.55 155 155 70 ⇑ 90 90
26 27 28.33 34 34 34 34 34
27 29 35.03 34 34 34 34 34
28 10 11.76 34 34 25 25 25
29 15 17.95 34 34 25 25 25
30 55 59.55 155 155 70 70 70
31 65 69.72 155 155 70 70 70
32 39 44.16 44 44 44 44 44
33 23 29.55 34 34 34 34 34
34 30 33.32 44 ↓ 34 34 34 34
35 14 15.33 34 34 25 25 25
36 38 43.79 44 44 51 ⇓ 44 44
37 26 32.72 51 ↓ 34 34 34 34
38 58 66.15 155 155 70 70 70
39 25 27.42 34 34 34 34 34
40 65 69.28 155 155 70 70 70
41 30 37.54 34 34 44 44 44
42 29 38.28 44 ↓ 34 44 44 44
43 23 26.66 34 34 25 ⇑ 34 34
44 24 27.64 34 34 34 34 34
45 48 55.30 51 ↑ 155 51 ⇑ 70 70
46 11 13.44 34 34 25 25 25
47 13 18.51 34 34 25 25 25
48 14 15.96 34 34 25 25 25
Custo 11239.95 18908.03 19289.9 12605.89 12887.4 12778.2
45
Tabela 5.9: Cálculos para topologia #1, tráfego #1.a e conjunto com 5 capacidades.
Enlace Fluxo Capacidade
ρ α
Buffer p
1 16 20 0.8 0.095 140 0.00787
2 11 20 0.55 0.09 76 0.00589
3 21 50 0.42 0.085 72 0.00233
4 21 50 0.42 0.085 73 0.00212
5 2 4 0.5 0.09 61 0.01
6 14 20 0.7 0.095 109 0.00556
7 24 50 0.48 0.09 68 0.00521
8 19 50 0.38 0.085 68 0.00209
9 9 20 0.45 0.085 66 0.00478
10 3 6 0.5 0.09 61 0.01
11 8 10 0.8 0.095 130 0.01
12 21 50 0.42 0.085 65 0.00410
Prob. de perda = 0.00212
Buffer = 73
Alfa = 0.085
0
50 100 150 200 250 300
0.0
0.2
0.4
0.6
0.8
1.0
Buffer
Probabilidade de perda
M[x]/M/1/B
Equação aproximada
Figura 5.1: Curvas M
[X]
/M/1/B e da equação (4.10) para o enlace 4.
5.3 SIMULAÇÕES
Para verificar as restrições de QoS da camada de transporte, algumas simulações foram
realizadas utilizando o programa NS-2. São escolhidos para o teste da rede, um par origem-
destino. As aberturas das conexões TCP seguem processo de Poisson. As taxas de abertura de
conexões são determinadas pelo índice de utilização do enlace
ρ
ij
. A quantidade de dados a
ser transmitida em cada conexão, é expressa em número de pacotes. Um tráfego misto TCP é
46
considerado, onde os tamanhos dos arquivos são obtidos de medidas realizadas em (MELLIA;
CARPANI; LO CIGNO, 2002). O tempo de simulação é de 2200 segundos, onde nos primeiros
200 segundos o sistema é considerado como estando no período transitório e nos 2000 segundos
restantes é considerado em regime permanente e neste últimoperíodo os dados são efetivamente
utilizados na obtenção dos resultados.
Dois casos são considerados para mostrar a eficiência do processo de dimensionamento. A
primeira simulação será sobre um caminho origem-destino com 3 enlaces, pertencente a rede
formada por 24 enlaces (topologia #2). A segunda simulação será sobre um caminho origem-
destino com 4 enlaces, pertencente a rede formada por 48 enlaces (topologia #3). Ambas as
simulações foram realizadas com os resultados obtidos para o problema CA com 5 e 10 ca-
pacidades a escolher e com os resultados obtidos com o algoritmo de Chromy (CR) (limitantes
inferiores).
Para a primeira simulação, os enlaces 6, 19, 24, foram utilizados. A tabela 5.10 mostra os
resultados obtidos dos problemas CA e BA com 5 e 10 capacidades (N
s
) a escolher e o resultado
obtido através do algoritmo de Chromy (CR). Tanto os fluxos, como as capacidades, são dados
em Mpbs. O tamanho do buffer é expresso em pacotes.
Tabela 5.10: Dados de 3 enlaces da topologia #2.
CR N
s
= 5 N
s
= 10
Enlace Fluxo
ρ
C B
ρ
C B
ρ
C B
1 5 0.53 9.37 92 0.62 8 90 0.5 10 87
2 12 0.78 15.31 149 0.35 34 64 0.8 15 156
3 10 0.80 14.64 140 0.29 34 75 0.67 15 134
As tabelas 5.11, 5.12 e 5.13, mostram os atrasos médios E[T], o número médio de pacotes
E[N] e as probabilidades de perdas p
ij
, obtidos pelas simulações no NS-2.29 e calculadas com
o modelo de filas M
[X]
/M/1/B para N
s
= 5, N
s
= 10 e CR, considerando a topologia #2.
Tabela 5.11: Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 5 e topologia #2.
NS-2 N
s
= 5
Enlace E[T] E[N] p
ij
E[T] E[N] p
ij
1 0.043 17.61 0.0039 0.029 13.08 0.0051
2 0.004 4.75 0.0037 0.004 4.31 0.0021
3 0.006 5.09 0.00015 0.003 3.33 0.0004
Inicialmente pode-se observar uma boa concordância entre os valores previstos com o mo-
delo M
[X]
/M/1/B e aqueles obtidos via simulação. Observa-se que a margem de erro das si-
mulações é de ±15% para E[T] e E[N]; e de ±20% para p
ij
. Os valores reportados nas tabelas
47
Tabela 5.12: Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 10 e topologia #2.
NS-2 N
s
= 10
Enlace E[T] E[N] p
ij
E[T] E[N] p
ij
1 0.025 10.16 0.0031 0.018 8.03 0.0016
2 0.035 34.53 0.0039 0.030 32.72 0.0051
3 0.025 20.64 0.0020 0.018 16.62 0.0012
Tabela 5.13: Resultados da simulação e do modelo M
[X]
/M/1/B para CR e topologia #2.
NS-2 CR
Enlace E[T] E[N] p
ij
E[T] E[N] p
ij
1 0.030 12.32 0.0028 0.020 9.21 0.0017
2 0.032 31.60 0.0044 0.028 29.65 0.0047
3 0.027 22.52 0.0020 0.020 17.98 0.0012
5.12 e 5.13 são bem semelhantes porque capacidades e buffers, nestes casos, são semelhantes.
Como pode-se observar na tabela 5.10 (colunas CR e N
s
=10). Isto se deve a maior granulari-
dade das capacidades que fazem com que os valores obtidos no caso discreto se aproximem do
caso contínuo.
Já no caso da granularidade baixa, o projeto é bastante diferente, como observado na tabela
5.10 (coluna N
s
=5). Entretanto, dados previstos e simulados são similares, conforme observado
na tabela 5.11.
Os gráficos 5.2, 5.3 e 5.4 mostram a latência na transmissão de arquivos de vários tamanhos
calculado usando o modelo CSA. A restrição de QoS de latência permitida L
t
= 0.5s, também
é mostrada nos gráficos. As observações devem restringir-se à latência na transferência de ar-
quivos com até 20 pacotes, pois o modelo CSA subestima os valores de latência, neste caso,
devido a utilização de uma aproximação para o cálculo do tempo necessário a transmissão re-
manescente após as fases de slow start e fast recovery (CARDWELL; SAVAGE; ANDERSON,
2000). Observa-se uma boa concordância com os valores obtidos pela simulação do sistema no
software NS-2. (A margem de erro das simulações varia entre ±15% e ±34% de acordo com o
tamanho do fluxo TCP).
Nos gráficos 5.3 e 5.4 a latência para 20 pacotes fica mais próxima do limite L
t
= 0.5 do
que no gráfico 5.2, o que faz sentido, pois o algoritmo que minimiza o custo da rede, faz com
que as capacidades sejam as mais próximas possíveis dos respectivos fluxos (tabela (5.10)). No
caso onde N
s
= 5 as capacidades em dois enlaces do caminho considerado assumiram valores
mais elevados (34 Mbps). Desta forma é natural um desempenho melhor, fazendo com que os
valores de latência se afastem do valor alvo L
t
= 0.5s, conforme observado na figura 5.2.
48
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1.1
195 19 10 6 4 2 1
Latencia [s]
Tamanho do Arquivo [pacotes]
NS-2.29
Modelo CSA
Figura 5.2: Latência para 3 enlaces, topologia #2, N
s
= 5
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
195 19 10 6 4 2 1
Latencia [s]
Tamanho do Arquivo [pacotes]
NS-2.29
Modelo CSA
Figura 5.3: Latência para 3 enlaces, topologia #2, N
s
= 10
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
195 19 10 6 4 2 1
Latencia [s]
Tamanho do Arquivo [pacotes]
NS-2.29
Modelo CSA
Figura 5.4: Latência para 3 enlaces, topologia #2, CR
Para a simulação com 4 enlaces, foram usados os enlaces 8, 7, 14 e 20 da rede com 48
enlaces (topologia #3). A tabela 5.14 mostra os resultados obtidos dos problemas CA e BA
com 5 (N
s
= 5) e 10 capacidades (N
s
= 10) a escolher e o resultado obtido através do algoritmo
de Chromy (CR).
As tabelas 5.15, 5.16 e 5.17, mostram os atrasos médios E[T], o número médio de pacotes
49
Tabela 5.14: Dados de 4 enlaces da topologia #3
CR N
s
= 5 N
s
= 10
Enlace Fluxo
ρ
C B
ρ
C B
ρ
C B
1 14 0.76 18.34 167 0.41 34 68 0.56 25 99
2 14 0.72 19.19 152 0.41 34 68 0.56 25 99
3 7 0.54 12.78 106 0.20 34 55 0.70 10 127
4 54 0.89 60.59 275 0.34 155 64 0.77 70 151
E[N] e as probabilidades de perdas p
ij
, obtidos pelas simulações no NS-2.29 e utilizando o
modelo de filas M
[X]
/M/1/B para N
s
= 5, N
s
= 10 e CR, considerando a topologia #3.
Tabela 5.15: Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 5 e topologia #3.
NS-2 N
s
= 5
Enlace E[T] E[N] p
ij
E[T] E[N] p
ij
1 0.004 5.63 0.0045 0.004 5.52 0.0026
2 0.004 6.12 0.0042 0.004 5.52 0.0026
3 0.002 2.86 0.0020 0.003 2.04 0.0014
4 0.007 2.49 0.0078 0.0008 4.22 0.0020
Tabela 5.16: Resultados da simulação e do modelo M
[X]
/M/1/B para N
s
= 10 e topologia #3.
NS-2 N
s
= 10
Enlace E[T] E[N] p
ij
E[T] E[N] p
ij
1 0.010 11.73 0.0030 0.008 10.31 0.0015
2 0.010 11.59 0.0020 0.008 10.31 0.0015
3 0.039 22.43 0.0025 0.030 19.14 0.0026
4 0.007 33.94 0.0029 0.005 27.94 0.0036
Tabela 5.17: Resultados da simulação e do modelo M
[X]
/M/1/B para CR e topologia #3.
NS-2 CR
Enlace E[T] E[N] p
ij
E[T] E[N] p
ij
1 0.025 28.65 0.0023 0.022 27.39 0.0020
2 0.019 22.40 0.0020 0.018 22.67 0.0017
3 0.018 10.26 0.0020 0.015 9.87 0.0008
4 0.016 72.03 0.0026 0.015 73.89 0.0049
Novamente, observa-se uma boa concordância entre os valores previstos com o modelo
M
[X]
/M/1/B e aqueles obtidos via simulação. A margem de erro das simulações é de ±15%
para E[T] e E[N]; e de ±20% para p
ij
. Nota-se que, na tabela 5.14, os valores de capacidades
e buffers são bem diferentes para todos os casos, ao contrário do que acontece com os testes
50
realizados com a rede de 24 enlaces. Isto ocorre devido aos valores que formam o conjunto S
de capacidades discretas. Se nos conjuntos S com 5 e 10 capacidades houvesse os valores 20,
15 e 65 para serem escolhidos para capacidades dos enlaces, provavelmente os resultados da
tabela 5.14, seriam parecidos e, consequentemente, os resultados das tabelas 5.15, 5.16 e 5.17
também.
Os gráficos 5.5, 5.6 e 5.7, mostram a latência na transmissãode arquivos de vários tamanhos
calculada usando o modelo CSA. As observações também devem restringir-se à latência na
transferência de arquivos com até 20 pacotes. A margem de erro das simulações varia entre
±15% e ±34% de acordo com o tamanho do fluxo TCP.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
195 19 10 6 4 2 1
Latencia [s]
Tamanho do Arquivo [pacotes]
NS-2.29
Modelo CSA
Figura 5.5: Latência para 4 enlaces, topologia #3, N
s
= 5
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
195 19 10 6 4 2 1
Latencia [s]
Tamanho do Arquivo [pacotes]
NS-2.29
Modelo CSA
Figura 5.6: Latência para 4 enlaces, topologia #3, N
s
= 10
Ao analisar os gráficos 5.5, 5.6 e 5.7, referentes ao caminho formado por 4 enlaces, é pos-
sível observar um melhor desempenho do sistema quando N
s
= 5 (gráfico 5.5). Este comporta-
mento já era esperado, pois em todos os enlaces do caminho as capacidades são bem superiores
as encontradas com N
s
= 10 e CR. Isto faz com que o valor da latência diminua, mas também
faz com que o custo do caminho seja maior (problema CA). Para N
s
= 10, o desempenho do sis-
tema também é superior ao desempenhodo sistema para CR, o que faz com que o custo também
51
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
2.2
195 19 10 6 4 2 1
Latencia [s]
Tamanho do Arquivo [pacotes]
NS-2.29
Modelo CSA
Figura 5.7: Latência para 4 enlaces, topologia #3, CR
seja superior ao custo encontrado para CR. Observando o gráfico 5.7 nota-se que a restrição de
latência (L
t
= 0.5 s), utilizando o modelo CSA, foi atingida, o que leva a crer que a restrição
RTT de camada de rede também foi atingida. Isto pode ser verificado somando os valores con-
tidos na coluna 5 da tabela 5.17, cujo resultado é 0.07. Analisando desta maneira, a latência
encontrada para a simulação com o NS-2 teria que ultrapassar o limite de 0.5 s, pois somando as
linhas da coluna 2 encontra-se 0.078. No entanto, a latência encontrada para a simulação com
o NS-2, é bem menor (gráfico 5.7). Sabendo que as informações recolhidas da simulação são
oriundas da camada de rede e só então são processadas para a obtenção da latência na camada
de transporte e que a simulação é realizada utilizando funções/processos aleatórios, é possível
diminuir esta aparente discordância entre os resultados da simulação com o NS-2, realizando
várias simulações longas e tirando sua média, assim a variância tende a diminuir e o resultado
a melhorar.
52
6 CONCLUSÃO E TRABALHOS FUTUROS
Nesta dissertação abordou-se a solução dos problemas CA discreto e BA, seguindo a me-
todologia de projeto de redes IP que considera a dinâmica das redes de pacotes, assim como os
efeitos dos protocolos nas diferentes camadas e na QoS experimentada pelos usuários finais.
No capítulo 3 foi apresentado o problema de atribuição de capacidades (CA) discretas,
sujeito a restrições de QoS fim-a-fim, onde os valores de capacidades de tráfego para cada
enlace são escolhidos de um conjunto discreto de valores. Neste capítulo foram apresentadas
três propostas para a solução do problema CA discreto: busca exaustiva, PSO e uma heurística.
Também foi apresentado um método para calcular um limitante inferior para o custo da rede
(utilizando valores contínuos) baseado no algoritmo Chromy (CHROMY, 1987).
No capítulo 4 foi apresentado o problema de atribuição de buffer, que tem por objetivo
dimensionar os buffers dos enlaces das redes de forma otimizada, e um método de solução
baseada em uma função aproximada para o cálculo da probabilidade de perda de pacotes no
modelo de filas M
[X]
/M/1/B.
No capítulo 5 são realizadas as simulações e verificações dos resultados de onde se pode
retirar alguns elementos para análise.
Ao utilizar a busca exaustiva para resolver o problema CA discreto, foi possível encontrar
o menor custo para o projeto. Contudo, aumentando o número de capacidades discretas a es-
colher e/ou aumentando o número de enlaces que formam a rede, o tempo gasto no processo
de otimização torna-se muito elevado, pois o algoritmo testa todas as combinações entre os va-
lores possíveis de capacidades para os enlaces. Observa-se que para redes pequenas (topologia
#1), é melhor utilizar o método de busca exaustiva para encontrar o resultado do problema CA
discreto, pois o cálculo não consome muito tempo e o resultado encontrado é o melhor exis-
tente (ótimo). No entanto, a medida que o conjunto de capacidades discretas a escolher e/ou o
número de enlaces da rede aumentam, o tempo que a busca exaustiva consome, para encontrar
o resultado para o problema CA, torna-se muito elevado, o que justifica o emprego dos outros
métodos utilizados (PSO e heurística).
53
Os testes realizados com o PSO mostram que apesar de apresentar resultados satisfatórios,
não é possível garantir que seja encontrado o resultado ótimo para o problema CA discreto.
Também foi possível ver, através dos testes, que a medida que o espaço de busca do problema
aumenta, com o aumento da rede ou com o aumento do conjunto de capacidades discretas a
escolher, é necessário aumentar o número de partículas (N
p
) e/ou o número de iterações (N
itr
)
do PSO. Observa-se também que a performace do PSO está mais relacionada ao número de
partículas do que ao número de iterações. Isto ocorre devido as adaptações empregadas no PSO
para a resolução do problema.
Ao se comparar a heurística proposta com os outros dois métodos (ES e PSO), aquela
mostrou ser extremamente rápida em encontrar uma solução viávelpara o problema CA. No en-
tanto, os resultados obtidos através desta heurística, mostraram-se dependentes do modo como
as linhas da matriz ∆ estão dispostas. Vale a pena lembrar que esta heurística não garante o
resultado ótimo, mas sim um resultado viável, já que tem por objetivo satisfazer as restrições e
não minimizar o custo da rede. O que faz com que ela deva ser empregada com cautela.
O método de Chromy, utilizado para encontrar os limitantes inferiores, baseado em capaci-
dades contínuas para o custo da rede, mostrou ser rápido e eficiente. Este método é empregado
para obter os valores ótimos (contínuos) para o problema CA e serve como base de comparação
para os métodos utilizados no cálculo do problema de CA discreto.
Ao analisar a proposta de solução para o problema de atribuição de buffer, e observar o
gráfico 5.1, é possível notar uma boa aproximação entre as curvas geradas pelo modelo de filas
M
[X]
/M/1/B e pela função de aproximação (4.10), o que mostra uma excelente escolha ao uti-
lizar esta função como função de aproximação. Com base nesta função aproximada foi possível
desenvolver um método analítico para a resolução do problema BA baseado, inicialmente, na
aplicação dos multiplicadores de Lagrange e posterior uso do método de Iteração Linear.
As simulações, utilizando o NS-2, foram realizadas com a finalidade de comprovar a eficá-
cia dos métodos utilizados nos cálculos do problema CA e BA. Tanto as simulações como o
modelo CSA, têm como entradas as capacidades e buffers encontradas através dos métodos
propostos para solução dos problema CA e BA. Os resultados das simulações no NS-2, foram
comparados com os resultados obtidos através dos cálculos realizados com o modelo CSA e
observou-se uma boa concordância entre eles, confirmando o funcionamento do método.
Para trabalhos futuros, a função custo (3.1), utilizada no problema CA, pode ser modi-
ficada de tal forma a ser não linear, representando assim uma economia de escala, ou seja,
quanto maior a capacidade do enlace, menor é o seu custo por bps. Outros fatores podem ser
considerados na elaboração da função custo para o problema CA, são eles: custo do equipa-
54
mento e instalação, custo de manutenção, custo da capacidade alocada por quilômetro. Outra
proposta para trabalhos futuros, é de implementar alguma técnica para manter a diversidade
e tentar melhorar o desempenho do PSO. Como por exemplo: explosões periódicas e/ou re-
pulsão entre partículas. Também pode ser implementado o genocídio de partículas que não
respeitarem as restrições. Outra proposta seria a comparação de desempenho do PSO com uma
outra meta-heurística conhecida, como por exemplo, os Algorítmos Genéticos (GOLDBERG,
1989). Uma proposta para a heurística de Ajuste do Enlace Crítico é a implementação de algum
algoritmo que troque as linhas da matriz ∆ de forma que a heurística consiga encontrar resul-
tados melhores. Para o problema de atribuição de buffer poder-se-ia pensar em adotar filas do
tipo RED (Random Early Detection)(FLOYD; JACOBSON, 1993),(BONALD; MAY; BOLOT,
2000),(ALAZEMI; MOKHTAR; AZIZOGLU, 2000).
55
REFERÊNCIAS BIBLIOGRÁFICAS
ALAZEMI, H. M.; MOKHTAR, A.; AZIZOGLU, M. Stochastic modeling of random early
detection gateways in tcp networks. IEEE Globecom 2000, São Francisco, USA, p. 1415 –
1424, 2000.
BARROSO, L. C.; BARROSO, M. M. de A.; FILHO, F. F. C.; CARVALHO, M. L. B. de;
MAIA, M. L. Cálculo Numérico com Aplicações. São Paulo - SP: Editora Harbra, 1987.
BONALD, T.; MAY, M.; BOLOT, J.-C. Analytic evaluation of red performance. IEEE
INFOCOM 2000, Tel Aviv, Israel, v. 3, p. 1415 – 1424, mar. 2000.
CARDWELL, N.; SAVAGE, S.; ANDERSON, T. Modeling tcp latency. IEEE Infocom 00, Tel
Aviv, Israel, 2000.
CHAO, X.; MIYAZAWA, M.; PINEDO, M. Queueing Networks - Customers, Signals and
Product Form Solutions. New York: John Wiley, 1999.
CHROMY, J.R. Design optimizationwith multipleobjectives.American StatisticalAssociation
Proceedings of Surveys Research Methods Section, p. 194–199, 1987.
EBERHART, R. C.; HU, X.; SHI, Y. Swarm intelligence for permutation optimization: a case
study of n-queens problem. IEEE Swarm Intelligence Symposium, Indianapolis - USA, p.
243–246, 2003.
ERSOY, C.; LEVI, A.; GUMRAH, O. Artificial intelligence search techniques for discrete
link capacity assignment in prioritized multiservice networks. Int. J. Compt. Syst. Sci. Eng, p.
191–197, 2000.
FLOYD, S.; JACOBSON, V. Randon early detection gateways for congestion avoidance.
IEEE/ACM Transactions on Networking, v. 1, p. 397 – 413, 1993.
FRALEIGH, C.; TOBAGI, F.; DIOT, C. Provisioning ip backbone networks to support latency
sensitive traffic. IEEE Infocom 03, São Francisco, CA, 2003.
GARETTO, M.; TOWSLEY, D. F. Modeling, simulation and measurements of queuing delay
under long-tail internet traffic. Proc. ACM Sigmetrics 2003, San Diego - USA, p. 47–57, 2003.
GERLA, M.; KLEINROCK, L. On the topological design of distributed computer networks.
IEEE Transactions on Communications, v. 25, p. 48–60, 1977.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine Learning.
Massachusetts: Addison-Wesley, 1989.
KENNEDY, J.; EBERHART, R. C. A new optimizer using particle swarm theory. Proc. 6
th
Int.
Symp. on Micro Machine and Human Science, Nagoya - Japan, p. 39–43, 1995.
56
KENNEDY, J.; EBERHART, R. C. Swarm Intelligence. San Francisco: Morgan Kauffmann,
2001.
KLEINROCK, L. Queueing Systems, Volume II: Computer Applications. New York: Wiley
Interscience, 1976.
LIU, X. ming; IGARASHI, J.; MIYAMOTO, H. A capacity assignment method with different
types of channel capacities for packet switched networks. 2nd Switching Network Systems
Division, NEC Corp., p. 194–199, 1990.
LOPES, H. S.; COELHO, L. S. Particle swarm optimization with fast local search for the
blind traveling salesman problem. Proc. of 5
th
Int. Conf. on Hybrid Intelligent Systems, Rio de
Janeiro - Brazil, p. 245–250, 2005.
LOPES, H. S.; HEMBECKER, F.; GODOY JR., W. Particle swarm optimization for the
multidimensional knapsack problem. Proc. 8
th
Int. Conf. on Adaptive and Natural Computing
Algorithms, LNCS 4431, p. 358–365, 2007.
MARUYAMA, K.; TANG, D. T. Discrete link capacity and priority assigments in
communication networks. IBM J. Res. Develop, p. 254–263, maio 1977.
MCCANNE, S.; FLOYD, S. NS Network Simulator. 1995. Disponível em:
<http://www.isi.edu/nsnam/ns>.
MELLIA, M.; CARPANI, A.; LO CIGNO, R. Measuring ip and tcp behavior on edge nodes.
IEEE Globecom 2002, Taipei, TW, 2002.
PARK, K.; WILLINGER, W. Self-Similar Network Traffic and Performance Evaluation. New
Jersey: John Wiley, 2000.
PAXSON, V.; FLOYD, S. Wide-area traffic: the failure of poisson modeling. IEEE/ACM
Transactions on Networking, v. 3, p. 226–244, 1995.
REKLAITIS, G. V.; RAVINDRAN, A.; RAGSDELL, K. M. Engineering Optimzation:
Methods and Applications. New York: Wiley Interscience, 1983.
SHI, Y. Particle swarm optimization. IEEE Neural Networks Society, 2004.
WILLE, E. C. G. Design and Planning of IP Networks Under End-to-End QoS Constraints.
Tese (Doutorado) — Politecnico di Torino, 2004.
WILLE, E. C. G.; MELLIA, M.; LEONARDI, E.; AJMONE-MARSAN, M.; GARETTO,
M. Considering end-to-end qos in ip network design. 11
th
Intern. Telecomunications Network
Strategy and Plannind Symposium (Networks 2004), p. 69–74, 2004.
WILLE, E. C. G.; MELLIA, M.; LEONARDI, E.; AJMONE-MARSAN, M. Algorithms for IP
networks design with end-to-end QoS constraints. Computer Networks, v. 50, p. 1086–1103,
2006.
YABCZNSKI, E.; BENTO, C. R. C.; WILLE, E. C. G. Algoritmos para dimensionamento de
redes de computadores. Relatório Técnico, CPGEI-UTFPR, Curitiba, 2006.
57
ANEXO
Anexo A - Matriz ∆ Referente a Topologia #1
Dada a topologia da rede e os requisitos de tráfego origem(s)-destino(d) é possível obter
a matriz ∆. Cada linha desta matriz representa um par origem-destino e cada coluna desta
linha representa um enlace. Se o valor do elemento da matriz for 1, o enlace está presente
no caminho origem-destino, caso contrário, o enlace não está presente no caminho origem-
destino. Basicamente a matriz ∆ representa as rotas origem-destino e é utilizada para o cálculo
das restrições de atrasos (Atraso
sd
).
Para a topologia #1 formada por 5 nós, 12 enlaces, a matriz ∆ foi criada de forma aleatória
para produzir 11 rotas entre os vários nós origem-destino.
∆ =
δ
sd
ij
=
1 0 0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0
0 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 1
(1)
Para facilitar, os enlaces são numerados de 1 a 12 (note que existem 12 colunas na matriz).
Considerando que a primeira linha da matirz ∆, acima, é referente a rota de transmissão entre o
nó de origem s
1
e o nó de destino d
1
, é possível dizer que o enlace 1 e o enlace 4 estão presentes
no caminho origem-destino entre os nós s
1
e d
1
. Então:
T
s
1
d
1
=
K
µ
1
C
1
− f
1
+
1
C
4
− f
4
≤ Atraso
s
1
d
1
(2)
58
Da mesma forma a segunda linha é referente a rota de transmissão entre o nó de origem s
2
e
o nó de destino d
2
. Pela linha da matriz é possível dizer que o enlace 2 e o enlace 12 estão
presentes no caminho origem-destino entre os nós s
2
e d
2
. Então:
T
s
2
d
2
=
K
µ
1
C
2
− f
2
+
1
C
12
− f
12
≤ Atraso
s
2
d
2
(3)
O conjunto completo da restrições (formada pela matriz ∆) é:
T
s
1
d
1
=
K
µ
1
C
1
− f
1
+
1
C
4
− f
4
≤ Atraso
s
1
d
1
(4)
T
s
2
d
2
=
K
µ
1
C
2
− f
2
+
1
C
12
− f
12
≤ Atraso
s
2
d
2
(5)
T
s
3
d
3
=
K
µ
1
C
4
− f
4
+
1
C
7
− f
7
≤ Atraso
s
3
d
3
(6)
T
s
4
d
4
=
K
µ
1
C
5
− f
5
≤ Atraso
s
4
d
4
(7)
T
s
5
d
5
=
K
µ
1
C
3
− f
3
+
1
C
6
− f
6
≤ Atraso
s
5
d
5
(8)
T
s
6
d
6
=
K
µ
1
C
7
− f
7
+
1
C
9
− f
9
≤ Atraso
s
6
d
6
(9)
T
s
7
d
7
=
K
µ
1
C
3
− f
3
+
1
C
6
− f
6
+
1
C
8
− f
8
≤ Atraso
s
7
d
7
(10)
T
s
8
d
8
=
K
µ
1
C
6
− f
6
+
1
C
8
− f
8
≤ Atraso
s
8
d
8
(11)
T
s
9
d
9
=
K
µ
1
C
10
− f
10
≤ Atraso
s
9
d
9
(12)
T
s
10
d
10
=
K
µ
1
C
11
− f
11
≤ Atraso
s
10
d
10
(13)
59
T
s
11
d
11
=
K
µ
1
C
8
− f
8
+
1
C
12
− f
12
≤ Atraso
s
11
d
11
(14)
O que tornaa solução do problema CA difícil, é a presença de um mesmo enlace em diversas
rotas origem-destino, como acontece com os enlaces 3, 4, 6, 7, 8, 12.
Resumo
A presente dissertação trata do dimensionamento de redes IP sujeitas ao tráfego TCP. A me-
todologia usada foi recentemente apresentada na literatura e consiste em mapear as restrições
do usuário em restrições da camada de rede, e no uso de um modelo refinado de tráfego TCP.
Os problemas considerados correspondem à Atribuição de Capacidades (Capacity Assignment)
discretas e à Atribuição de Buffer (Buffer Assignment). Na formulação destes problemas leva-se
em consideração restrições de qualidade de serviço (Quality-of-Service) vistas pelo usuário fi-
nal. No problema de Atribuição de Capacidades discretas, os valores de capacidades para cada
enlace são escolhidos de um conjunto discretos de valores. Para a solução deste problema são
propostas três técnicas: Busca Exaustiva (ES - Exaustive Search), Otimização por Enxame de
Partículas (PSO - Particle Swarm Optimization)e uma heurística baseada em restrições. Ainda,
para o problema CA, é proposto um algoritmo para calcular um limitante para o custo de rede.
O problema de Atribuição de Buffer busca atribuir o tamanho dos buffers da rede, de forma
otimizada. Para solução deste problema é proposto um método que faz uso de uma função
analítica aproximada para o cálculo de probabilidade de perda de pacotes na rede. As técni-
cas de solução propostas são verificadas pela comparação dos desempenhos teóricos calculados
com aqueles obtidos via simulação usando o software NS-2.
PALAVRAS-CHAVE
Dimensionamento de redes IP, Atribuição de Capacidades (CA) Discretas, Atribuição de
Buffer (BA).
ÁREA / SUB-ÁREA DE CONHECIMENTO
3.04.00.00-7 – Engenharia Elétrica
3.04.06.00-5 – Telecomunicações
2007
N
o
: 460
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo