AntNet Algoritmos de formigas aplicados a encaminhamento de pacotes em redes Pedro Neves nº 27836 Algoritmos Formiga Na natureza … O comportamento de recolha de alimentos de muitas sociedades de formigas baseia-se na comunicação indirecta mediada por feromonas. Enquanto caminham, do ninho para as fontes de alimento e vice-versa, as formigas deixam um rasto químico que forma um trilho de feromonas. 2 / 17 Ant Colony Optimization (ACO) 1. 2. 3. 4. Os caminhos mais curtos surgem do comportamento colectivo, através de: uma escolha local e probabilística de cada formiga sobre para onde se mover, tendo maior probabilidade os caminhos que tenham mais feromonas uma forma indirecta de comunicação (Estigmergia) 3 / 17 Feromonas e Estigmergia Quando as formigas deixam um rasto de feromonas: modificam o modo como as próximas formigas iram percepcionar o terreno local influenciam a escolha do caminho a seguir das próximas formigas Ao ler/escrever o sinal químico de feromonas de um local as formigas estão: a comunicar indirectamente através do ambiente a criar um comportamento colectivo 4 / 17 Encaminhamento em Redes Um algoritmo de encaminhamento está distribuído por toda a rede Tem de escolher o melhor caminho para levar os pacotes até ao seu destino e evitar congestionamentos A maioria dos algoritmos serve-se de estruturas de dados nos nós (Routing Tables) Estas estruturas são ao mesmo tempo bases de dados e modelos locais do estado global a informação que guardam e como a actualizam depende do algoritmo utilizado 5 / 17 Métricas e Objectivos do Encaminhamento Métricas Atraso na distribuição de pacotes (seg): Velocidade com que os pacotes são enviados (bits / seg): qualidade do serviço quantidade do serviço Recursos da rede utilizados Objectivos com muita carga: aumentar a quantidade de pacotes enviados no mesmo atraso médio com pouca carga: diminuir o atraso médio de cada pacote 6 / 17 AntNet: Estruturas de dados Routing Table: Para um qualquer destino d e para cada nó vizinho n tem a probabilidade Pnd , que representa a “tendência” de escolher o nó n como parte do caminho até ao destino d. Local Traffic Statistics: Contém informação sobre a distribuição do tráfego em toda a rede, tal como o nó o percepciona. 7 / 17 AntNet: Descrição do algoritmo 1. A cada intervalo de tempo t, em cada nó n, é criada uma formiga (Foward Ant), com um destino pseudo-aleatório (depende dos padrões de tráfego) 2. O objectivo de cada formiga é: descobrir um caminho, desde a origem até ao destino deixar, em cada nó visitado, informação útil para futuras formigas 3. Cada Foward Ant guarda, na sua memória privada, os nós que visitou e o tempo que gastou entre cada um deles. 8 / 17 AntNet: Descrição do algoritmo (cont.) 4. O próximo nó é escolhido tendo em conta: Routing Tables probabilísticas Heurística local baseadas no estado das ligações desse nó memória privada dos nós percorridos até então 5. Se for detectado um ciclo, este é eliminado tal como toda a informação sobre esse sub-caminho 9 / 17 AntNet: Descrição do algoritmo (cont.) 6. Quando chega ao seu destino a Foward Ant cria uma Backward Ant, transfere a sua memória para a nova formiga e morre. 7. A Backward Ant faz exactamente o mesmo percurso, mas no sentido inverso, até à origem. 10 / 17 AntNet: Descrição do algoritmo (cont.) 8. Em cada nó que passa a Backward Ant actualiza a Routing Table local e o Modelo de Tráfego Local usando informação memorizada e local 11 / 17 AntNet: Método de Decisão A cada nó k, a formiga, com destino d, escolhe o próximo n entre os nós vizinhos que ainda não percorreu, ou entre todos os vizinhos calculando a probabilidade P’nd de “tendência” para esse nó • Nk {conjunto de vizinhos de k} α peso da heurística local • utilizando uma Heurística Local ln que reflecte o estado actual do nó k • qn – nº de bits à espera de serem enviados de k para n 12 / 17 AntNet: Regra de actualização das tabelas Para descobrir o caminho entre K e D, as probabilidades dos arcos de saída de K são actualizadas através de um valor de reforço R O nó f, que é o vizinho de K atravessado pela Backward Ant, recebe um reforço positivo. Todos os outros vizinhos recebem um reforço negativo. 13 / 17 AntNet: Foward Vs. Backward Ants As Foward Ants têm a mesma prioridade que os restantes pacotes … Dessa forma conseguem obter informação sobre: o tempo global da viagem o tempo que levou entre os nós percorridos a velocidade com que os pacotes estão a percorrer a rede possíveis congestionamentos As Backward Ants têm prioridade sobre os outros pacotes propagam a informação, obtida pela Foward Ant, pelos nós visitados o mais depressa possível 14 / 17 AntNet: Avaliação do caminho descoberto O caminho descoberto é avaliado de forma: implícita, através do tempo decorrido entre a descoberta do caminho e a actualização das Rounting Tables implícita, através da actualização das Rounting Tables que descobrir quais os caminhos que mais frequentemente são descobertos explícita, através da avaliação do tempo que a formiga gastou em viagem T Mas T não pode ser comparado como absoluto pois é dependente do congestionamento existente na altura Associamos ao tempo T uma medida de qualidade R 15 / 17 Bibliografia “AntNet: Distributed Stigmergetic Control for Communications Networks” Gianni Di Caro, Marco Dorigo IRIDIA, Université Libre de Bruxelles – Bélgica “Ant Colony Optimization” http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html Acetatos teóricos de VA Paulo Urbano 16 / 17 Perguntas? FIM