ADEE – EST - UAlgarve
Redes de Alto Débito
Routing com meta-heuristicas
Pedro Cardoso, Ph.D.
[email protected]
w3.ualg.pt/~pcardoso
• Sabia que em média uma árvore produz apenas 20 resmas de papel. Antes de imprimir este
documento pense bem se tem mesmo que o fazer. Poupe papel. Lembre-se que há cada vez menos
árvores.
• A compra de papel 100% reciclado pós-consumo diminui sua emissão de carbono em 2,2 kg por
resma.
• Cada tonelada de papel reciclado economiza electricidade suficiente para iluminar uma casa de 3
quartos durante um ano.
Fontes: http://www.openland.pt, http://www.diadaarvore.org.br
O que é uma heurística?
Heurística:
Arte de inventar ou descobrir;
Método de ensino que procura que o aluno atinja
os conhecimentos ou a solução para os
problemas por esforço próprio;
HISTÓRIA procura de documentos;
INFORMÁTICA: regra (ou conjunto de regras)
que pretende obter uma aproximação à solução
de um problema;
www.infopedia.pt
12­04­08
Redes de Alto Débito
2
O que é uma heurística?
●
Exemplo:
Algoritmo para dar
troco
–
Enquanto não tiver o
troco
●
12­04­08
Dá a moeda do valor
mais elevado, menor ou
igual do que o troco em
dívida
Redes de Alto Débito
3
O que é uma metaheurística?
Metaelemento de formação de palavras, de origem
grega, que exprime a ideia de mudança, união,
transformação no vocabulário científico, e a
ideia de nível superior, maior generalidade no
vocabulário filosófico;
www.infopedia.pt
Na Informática: Uma meta-heurística é
um método heurístico para resolver de
forma genérica problemas de
optimização.
12­04­08
Redes de Alto Débito
4
O que é uma metaheurística?
Algoritmo aplicável
a qualquer
problema
onde seja possível
definir uma
“vizinhança”
12­04­08
Redes de Alto Débito
5
O que é uma metaheurística?
Exemplos:
Algoritmos genéticos
Simulated annealing
Tabu search
Swarm Intelligence
Ant Colony Optimization
Particle swarm optimization
...
12­04­08
Redes de Alto Débito
6
SI
Swarm Intelligence
12­04­08
Redes de Alto Débito
7
Princípios da SI
Swarm Intelligence (SI)
Baseada na interacção de muito agentes simples
que tentam atingir um mesmo objectivo
Emergente
Comportamento global que surge da interacção de muitos
agentes
Stigmergia
Comunicação indirecta (geralmente através do ambiente)
12­04­08
Redes de Alto Débito
8
Princípios da SI
Propriedades dos algoritmos de Swarm
Intelligence:
Os agentes são considerados como simples
Stigmergia: Comunicação indirecta entre agentes
O comportamento global pode ser emergente
Os comportamentos são robustos
Necessário em ambientes não previsíveis e/ou dinâmicos
Os indivíduos não são importantes !?
12­04­08
Redes de Alto Débito
9
Princípios da SI
O que faz um sistema Swarm Intelligence
funcionar?
Feedback Positivo
Feedback Negativo
Aleatoriedade
Múltiplas interacções
12­04­08
Redes de Alto Débito
10
Princípios da SI
O que faz um sistema Swarm Intelligence
funcionar?
Feedback Positivo
Reforça boas soluções
Formigas são capazes de atrair mais ajuda quando fonte de
alimento é encontrado
Mais formigas sobre um trilho aumenta o rasto de
feromonas e atrai ainda mais formigas
Feedback Negativo
Aleatoriedade
Múltiplas interacções
12­04­08
Redes de Alto Débito
11
Princípios da SI
O que faz um sistema Swarm Intelligence
funcionar?
Feedback Positivo
Feedback Negativo
Elimina as soluções más ou velhas da memória colectiva
Diminuição dos rastos de feromonas
Soluções mais afastadas são exploradas por último
O rasto de feromonas tem menos tempo para se evaporar
nas soluções mais próximas
Aleatoriedade
Múltiplas interacções
12­04­08
Redes de Alto Débito
12
Princípios da SI
O que faz um sistema Swarm Intelligence
funcionar?
Feedback Positivo
Feedback Negativo
Aleatoriedade
Permite que surjam novas soluções e dirige a construção
das actuais
As decisões dos agentes são aleatórias
Probabilidade de exploração (evita convergências
prematuras)
Múltiplas interacções
12­04­08
Redes de Alto Débito
13
Princípios da SI
O que faz um sistema Swarm Intelligence
funcionar?
Feedback Positivo
Feedback Negativo
Aleatoriedade
Múltiplas interacções
Nenhum indivíduo pode resolver um determinado problema.
Só através da interacção de muitos pode ser encontrada
uma solução
Um agente não pode sozinho resolver o problema. O rasto
de feromonas rapidamente se evaporava
São necessários muitos agentes para sustentar o rasto de
feromonas
Mais soluções podem ser encontrados mais rapidamente
12­04­08
Redes de Alto Débito
14
Princípios da SI
SI é adequada para
Encontrar soluções que não exigem controle preciso
sobre a forma como a meta é alcançada
Necessita de um grande número de agentes
Os agentes podem ser simples
Comportamentos robustos
12­04­08
Redes de Alto Débito
15
De um modo geral
Vantagens
Optimização global
Versatilidade
Robustez
Optimização de situações dinâmicas
SI + heurística especifica = algoritmo eficiente
Desvantagens
Refinamento local difícil
Pode ser superado por algoritmos mais específicos
Necessário alguma capacidade computacional
(memória, processador)
12­04­08
Redes de Alto Débito
16
Exemplos de métodos
Ant Colony Optimization
Colónias de formigas
Particle Swarm Optimization
Cardumes de peixes
Bandos de pássaros
Bee Colony Alg.
Colmeias de abelhas
...
movies/Catfish_School.flv
12­04­08
Redes de Alto Débito
17
As formigas na natureza
12­04­08
Redes de Alto Débito
18
Dumb parts,
properly connected
into a swarm, yield
smart results.
The constant
creeping of ants
will wear away the
stone
Kevin Kelly
The ants said:
together we will be
able to transport an
elephant
Proverbio do USA
6
Proverbio do TOGO
12­04­08
Redes de Alto Débito
19
Formigas individuais
Comportamentais
Muito pouco “sofisticados”
Memória muito limitada
Comportamento individual com uma grande
componente aleatório.
12­04­08
Redes de Alto Débito
20
As formigas como um
colectivo
Executam tarefas complexas com grande
fiabilidade e consistência.
Regulação da temperatura do ninho (~1 ºC);
Formação de pontes;
Raids massivos sobre áreas de alimentos;
Construção e protecção do formigueiro;
12­04­08
Redes de Alto Débito
21
As formigas como um
colectivo
Executam tarefas complexas com grande
fiabilidade e consistência.
Cooperação na carga de “grandes objectos”;
emigração maciças de colónias
Cuidam dos ovos
Encontram as rotas mais curtas do ninho até uma fonte de
alimento
Exploram preferencialmente as melhores fontes alimentares
12­04­08
Redes de Alto Débito
22
Experiência com formigas
ants_on_bridge.avi
Colónia de formigas
naturais
Comportamento baseado em
Populações com elevado número de formigas
Interacção através de rastos de feromonas (e
outros)
Processo de busca de comida
Passo 1) Busca aleatória de comida
Passo 2) Transporte de comida
Passo 3) Deixar rasto de feromona
Passo 4) Procura orientada pelas feromonas → Passos
2 → Passo 3
12­04­08
Redes de Alto Débito
24
Simulação
Simulação do comportamento das colónias
de formigas usando o starlogo
12­04­08
Redes de Alto Débito
25
simulacaoStarLogo.wmv
Os enxames são...
Flexíveis
Podem responde a perturbações internas e a
desafios externo
Robustos
As tarefas são completadas mesmo que alguns
membros falhem
Descentralizados
Não existe um controlo central na colónia
Auto-organizados
As soluções para os desafios são emergentes e não
predefinidas
12­04­08
Redes de Alto Débito
26
ACO
Ant Colony
Optimization
12­04­08
Redes de Alto Débito
27
Aplicações...
Os métodos ACO foram usados com
sucesso em vários problemas bastante
complexos:
Travelling Salesman Problem
Job-shop scheduling
...
12­04­08
Redes de Alto Débito
28
Exemplo...
Um caixeiro viajante deve partir de sua
cidade, visitar “n” cidades diferentes, e
voltar a sua origem.
Mas, qual a sequência de de cidades que devo percorrer
de modo que eu percorra a menor distância (gaste o
menor tempo) possível?
12­04­08
Redes de Alto Débito
29
Exemplo...
Trivial
12­04­08
Redes de Alto Débito
30
Exemplo...
Não tão trivial
8 cidades = 7! = 5040 ciclos distintos
151 cidades de Portugal → 5,7 * 10^262 ciclos
PC a 10THz → 10^12 combinações por ciclo → 5,7*10^250
segundos → 1.8 *10^243 anos!!!(universo ~ 13,7x10^9anos.
?
12­04­08
Redes de Alto Débito
31
Exemplo...
Ant Colony Optimization
1. Espalha um conjunto de
formigas pelos nós
2. Cada formiga escolhe o
próximo nó, de entre os que
ainda não está no seu ciclo
de acordo com uma fórmula
probabilística
k
pi , j =
12­04­08
{
τ iα, j⋅d −β
i,j
∑
α
j∈J k
τ i , j⋅d i , j
0
−β
se j∈J
k
c.c .
Redes de Alto Débito
32
Exemplo...
A fórmula
k
pij =
{
τ αij⋅d−β
ij
∑
α
j∈J k
τ ij⋅d ij
0
−β
se j ∈J
k
c .c .
J
J^K - é a lista de vértices não visitados;
●τ_{i,j} - é a quantidade de feromonas na aresta (i,j);
●d_{i,j } - é a distância entre os nós i e j
●α e β são parâmetros que definem o grau de
importância de τ e d respectivamente.
●
12­04­08
Redes de Alto Débito
33
Exemplo...
Actualização das
feromonas
Após cada formiga ter
calculado uma solução, S_n
J
τij = 1−ρ ⋅τ ijΔτ ij
onde
{
1
Δτ ij =
12­04­08
D S n 
0
se i , j ∈S n
c.c.
Redes de Alto Débito
34
Exemplo...
Melhor solução após ciclo...
Ciclo 1
Ciclo 7
Ciclo 54
Ciclo 33
12­04­08
Redes de Alto Débito
35
Algoritmo
Ant Colony Optimization
•
Inicia o rasto de feromonas
•
Enquanto ¬ (critério de paragem) faz
•
Para todos formigas faz
•
•
•
•
Construir uma solução nova utilizando o
rasto de feromonas actual e heurísticas
Estimar a solução construída
Fim para
Actualiza o rasto de feromonas usando as
soluções obtidas considerando uma dada
evaporação
•
Fim enquanto
•
Devolve Solução(ões)
12­04­08
Redes de Alto Débito
36
Aplicação ao routing
12­04­08
Redes de Alto Débito
37
AVISO!

Qualquer semelhança entre o apresentado daqui para a
frente (terminologia de redes e precisão) e uma
apresentação de um técnico de redes (competente) são
mera coincidência!!!
12­04­08
Redes de Alto Débito
38
Network Routing
Importante
Influencia a performance global da rede
Difícil
Variações estocásticas
Carga de tráfego
Topologia da rede
Tipos gerais
Circuit-switched (telefones)
Packet-switched (local network, Internet)
12­04­08
Redes de Alto Débito
39
Network Routing
Routing
Actividade de construção e uso de tabelas de
routing
Tabelas de routing
Informação para fazer o forwarding dos pacotes
Uma por nó da rede
12­04­08
Redes de Alto Débito
40
Network Routing
Algoritmos classificados em
Centralizados
Controlador central → actualiza todas as tabelas de routing
Redes pequenas
Mau: atrasos na recolha da informação + envio para nós
Controlador em baixo → rede em baixo
Distribuidos
Calculo dos caminhos partilhado pelos nós
Troca de informação entre nós
Usado na maioria das redes
12­04­08
Redes de Alto Débito
41
Network Routing
Routing estático
Calculo do caminho baseado nos nós
origem/destino
Não tem em conta o tráfego
Caminho = caminho mais “barato”
Routing dinâmico (adaptativo)
Adapta as políticas de routing a variações
temporais/espaciais do tráfego
12­04­08
Redes de Alto Débito
42
Network Routing
Optimização
Routing óptimo
Vê a rede como um todo
Optimizar o funcionamento global da rede → função de
custo global
Caminho mais curto
Não há função de custo global
Caminho mais curto de acordo com o custo das ligações
Classificados
Vector distância
Tab. Routing: (destino, distância estimada, next hop)
Estado do link
Mapa dinâmico de toda a rede
12­04­08
Redes de Alto Débito
43
Formulação
do Problema
de routing
12­04­08
Redes de Alto Débito
44
Qual é o problema?
Rede de comunicações
N ,L , d
N - Nós da rede
L - Conjunto de ligações/arestas entre os nós
d - Função que a cada aresta faz corresponder um
(vector de) custos
 M
d : L ℜ 
12­04­08
Redes de Alto Débito
45
Qual é o problema?
Uma rede...
●
(distancia,custo,banda usada, ...)
Nós
Arestas
12­04­08
Redes de Alto Débito
46
Qual é o problema?
Objectivo
Encontrar os custos mínimos entre
cada par de nós
(equilíbrio da rede)
12­04­08
Redes de Alto Débito
47
Qual é o problema?
 M
d : L ℜ 
não depende do tempo
M=1
“Fácil” de resolver
Dijkstra algorithm -
O n²
M>1
Optimização com múltiplos objectivos
Ex: geralmente são problemas intratáveis, i.e., não
existem algoritmos polinomiais para os resolver
Possível resolução recorrendo a heurísticas
12­04­08
Redes de Alto Débito
48
Qual é o problema?
Exemplo de Optimização com múltiplos
objectivos
Congestionamento
Custo
90 42 52 52 12 12 23 23 23 35 15 23 34 56 10 96 76 43
1 2 23 23 23 23 34 44 3 34 100 34 34 33 44 34 4 66
valores para ir do nó i para o nó j
120
Congestionamento
100
80
60
40
20
0
0
12­04­08
20
40
60
Custo
Redes de Alto Débito
80
100
120
49
Qual é o problema?
 M
d : L ℜ 
depende do tempo
Porquê?
A rede é dinâmica e os custos variam ao longo do tempo
Congestionamentos,
Arestas/nós indisponíveis ou condicionadas
Situação muito mais complexa...
12­04­08
Redes de Alto Débito
50
Resumindo a “coisa”
12­04­08
Redes de Alto Débito
51
Redes, Routers e Routing









As redes actuais (por exemplo, a Internet)
transportam os dados em pequenos pacotes
O grande problema é como é que esses pacotes
encontram o caminho até ao seu destino
Redes, Routers e Routing
Router
A

B


B
B

B
Para os dados (por exemplo, um email)
“encontrarem o seu caminho” desde quem envia
até ao destinatário, o pacote tem de ter um
endereço...
… e os routers da rede têm de saber o que fazer
com ele.
B
Redes, Routers e Routing
E agora por onde?
?

?
?
?
?
Cada router tem de decidir para onde enviar cada
um dos pacotes…
… logo cada router tem de saber um pouco acerca
do resto rede…
… e fazer a decisão baseada nos seus
conhecimentos: ‘routing protocol’
Protocolos de Routing
“Diz-me um pouco acerca de ti …”
?
?
??
?
?
Cada router troca informação com os seus
vizinhos…
… para construir uma imagem completa da rede…
… então define o “melhor” caminho para cada
destino
Protocolo de Routing
“É por aqui para ir para B”
B
B
O problema é que cada um destes caminhos é
calculado independentemente
Routers só pensam acerca dos seus caminhos em
cada instante…
… e não têm ideia do que os outros routers iram
fazer
‘Joined-up Routing’
“E para C?”
B
C
B
C
Vista geral…
… podia ser melhor…
‘Joined-up Routing’
B
C
B
C
Vista geral…
… podia ser melhor…
… do que escolher diferentes rotas individualmente?
‘Joined-up Routing’
B
C
B
C
Vista geral…
… podia ser melhor…
… do que escolher diferentes rotas individualmente?
Parece simples!
Problemas!
!
Duas dificuldades:
Considerar todas as rotas em conjunto requer muito mais
tempo e capacidade do que separadamente
Como podem os routers cooperar deste modo…
… quando cada um define as suas rotas
independentemente?
Requerido...
?
Do que é que precisamos?
Sistema distribuido
Altamente adaptável às variações de tráfego
Adaptável à heterogeneidade das redes
Métodos eficientes para calcular rotas e …
Um método de partilhar as rotas pretendidas
… A solução podem ser as …
A Solução?
Formigas!
Principios Swarm intelligence.
..
12­04­08
Redes de Alto Débito
63
Princípios da SI
Uma rede ad hoc é composto por muitos
agentes simples (cooperantes?) com um
conjunto de problemas que precisam ser
resolvidos de forma robusta e com tão
pouca comunicação directa quanto
possível
12­04­08
Redes de Alto Débito
64
Princípios da SI
Routing é uma extensão da busca por
fontes de comida das formigas!
Formigas à procura de comida…
Pacotes à procura de destinos…
Routing pode ser resolvido com SI?
Routing pode ser um comportamento
emergente da interacção de pacotes?
12­04­08
Redes de Alto Débito
65
Ant colony behaviour
Deixar um rasto
de feromona
Lê feromonas
As formigas movem-se
… cada uma deixa um rasto de feromona
uma mensagem para a próxima formiga
Quanto mais formigas mais feromonas
As formigas seguintes detectam as feromonas
Colectivamente a colónia encontra a melhor
“estratégia”...
Ant colony routing? (ACR)
‘Ant’ packets




Será que ACO pode melhorar o routing?
Enviar formigas-pacote para a rede…
… deixando feromonas-electrónicas
… de modo a partilhar a informação de routing
… melhora a estratégia de routing para a rede?
AntNet
12­04­08
Redes de Alto Débito
68
AntNet
AntNet aplicado a uma rede packetswitched
AntNet semelhante ao algoritmo Ant
Colony Optimization (ACO) algorithm para
a resolução de problemas do tipo Traveling
Salesman
12­04­08
Redes de Alto Débito
69
AntNet
Formigas-forward, F, são lançadas regularmente
para destinos aleatórios na rede
F mantém uma lista dos nós que visitou e o tempo
decorrido para chegar lá
A formiga-pacote cresce ao atravessar a rede
Loops são removidos do caminho
F é transmitida em função da probabilidade do
próximo hop
Mantida em cada nó de roteamento na tabela
AntNet
Quando F chega no seu destino, uma formigabackward, B, é devolvida à origem
B segue o caminho inverso de F até à origem
Em cada nó, B actualiza a tabela de roteamento
Probabilidade do próximo hop para o destino
Estatísticas de tempo de envio para o destino
Média
Variância
AntNet
Os pacotes de dados são roteados usando as
probabilidades do próximo hop
As formigas-forward têm a mesma prioridade que
os pacotes de dados
As formigas-forward sofrem os mesmos
congestionamento e atrasos que os pacotes de
dados.
As formiga-backward são encaminhadas com
prioridade mais elevada do que os outros pacotes
AntNet
AntNet é um algoritmo de roteamento para redes
datagrama
2 datagramas consecutivos enviados para o mesmo
endereço podem chegar na ordem inversa
Testes explicitos de feedback são estabelecidos com
formigas-forward e formiga-backward
As tabelas de probabilidades são actualizadas de
acordo com as estatísticas
AntNet
Livro:
Ant Colony Optimization, Marco Dorigo, Thomas Stützle
Por outras palavras...
12­04­08
Redes de Alto Débito
75
Destino
?
Início
Destino
?
Início
p33.mpeg
Destino
Início
?
Início
Destino
?
Destino
Início
p50.mpeg
?
Início
Destino
Destino
Início
Destino
?
Início
Destino
?
Início
p3difa.mpeg
Destino
Início
Destino
?
Início
Destino
?
Início
p3difb.mpeg
Destino
Início
Rastos de feromonas...
Destino
Rastos de feromonas...
Destino
Rastos de feromonas...
Destino
Outros algoritmos
Ant-Based Control (ABC)
R. Schoonderwoerd, O. Holland, J. Bruten, Ant-based load
balancing in telecommunications networks, 1996.
AntNet
G. Di Caro, M. Dorigo, Mobile Agents for Adaptive Routing,
Technical Report, Univ. Libre de Bruxelles, Beligium, 1997.
Mobile Ants Based Routing
Ant Colony Based Routing Algorithm
M. Gunes, U. Sorges, I. Bouaziz, ARA – The Ant-Colony
Based Routing Algorithm for MANETs, 2003.
Termite
M. Roth, S. Wicker, Termite: Emergent Ad-Hoc Networking,
2003.
Bibliografia
Ant Colony Optimization. M. Dorigo, T. Stützle. MIT Press.
Ants for load balancing in telecommunications networks. R.
Schoonderwoerd, O. Holland, J. Bruten, Leon Rothkrantz
Adaptive Routing in Wireless Communication Networks using Swarm
Intelligence. P. Arabshahi, A. Gray, I. Kassabalidis, A. Das
Adaptive-SDR: Adaptive Swarm-based Distributed Routing. I. Kassabalidis,
M. El-Sharkawi, R. Marks II, P. Arabshahi, A. Gray
Swarm Intelligence for Routing in Communication Networks. I.
Kassabalidis, M. El-Sharkawi, R.Marks II, P. Arabshahi, A. Gray
The Genetic Adaptive Routing Algorithm. Munetomo et. Al, 1997
...
...
12­04­08
Redes de Alto Débito
93
Projectos de Mestrado em
Ant colony routing?
Pacotes de formigas




Your mission ______, should you choose to
accept it, … (preencher os espaços)
Projectos de Mestrado
Estudo de algoritmos na área do routing
ACR-video, ACR-QoS,...