Análise de filas de prioridades para o Algoritmo de Dijkstra em redes de malhas sem fio. – Árvore AVL – Heap Binário
Análise de filas de prioridades para o Algoritmo de Dijkstra em redes de malhas sem fio. – Árvore AVL – Heap Binário
0 0
slides-tcc
On Github diogomg / slides-tcc
Análise de filas de prioridades para o Algoritmo de Dijkstra em redes de malhas sem fio.
Diogo Machado Gonçalves
Drª Sheila Morais de Almeida
Msc. Saulo Jorge Beltrão de Queiroz
Introdução
- Popularização de dispositivos compatíveis com o padrão IEEE 802.11;
- Crescimento do número de hotspots;
WMN vs. WLAN
Pacotes com destino à Internet são encaminhados para o roteador mais próximo com acesso à Internet. Baixo custo; Rede auto-configurável; Crescimento facilitado da redes.Protocolo OLSRD
- O protocolo proativo padrão da IETF;
- O grafo representa a topologia da rede;
- Construção de um grafo em memória através de trocas de mensagens;
- Mensagens de controle hello e TC (Topology Control);
- As rotas ótimas são calculadas a partir do grafo com o Algoritmo de Dijkstra;
- Qualidade de enlaces baseada na métrica ETX (expected Transmission count).
Algoritmo de Dijkstra
Melhor solução conhecida para resolver o problema dos caminhos mínimos de origem única assumindo arestas não negativas.Justificativa
- O crescimento da rede aumenta a complexidade do cálculo de rotas;
- Diminui a vazão da rede porque os pacotes são descartados durante esse cálculo.
Ponto a ser explorado
A complexidade do algoritmo de Dijkstra (necessário ao OLSRD) é altamente dependente da fila de prioridades e da dinâmica do grafo.
Filas de prioridade
Organizam um conjunto de dados baseadas em um critério definido.
Filas de prioridade de mínimo
- Inserção(Q, x);
- Mínimo(Q);
- ExtraiMínimo(Q)
- DecrementaChave(Q, x, k).
Objetivo Geral
Apontar a fila de prioridade, aplicada no algoritmo de Dijkstra, mais eficiente no contexto de redes de malha sem fio em um protocolo proativo.
Fibonnaci nao é eficiente no contexto de wmn; Trabalho do Saulo mostrou que o alg de RR (tambem é um algoritmo SPF) é mais eficiente (ozinho) que o Dijkstra em wmn no caso medio Análise das filas de prioridade mais adequadas à uma WMN ainda nao foi feita;Trabalhos relacionados
Queiroz (2009) propõe o uso do modelo de computação incremental para otimização da atualização da tabela de roteamento.
Oberhauser e Simha (1995) apresenta estatísticas de desempenho do algoritmo de Dijkstra a partir da utilização de diferentes filas de prioridades.
Algoritmo de Dijkstra
Estrutura de dados Extrai mínimo Decrementa chave Dijsktra Heap binário Árvore AVL Árvore Van Emde BoasÁrvore AVL
Árvore AVL
Operação Complexidade Inserção(Q, chave) Remoção(Q, chave) Busca(Q, chave) Mínimo(Q)Árvore AVL
Fila de prioridade Árvore AVL Operação Mínimo Mínimo Inserção Inserção Extrai mínimo Mínimo + Remoção Decrementa chave Busca + Remoção + InserçãoHeap Binário
Heap Binário
Operação Complexidade Inserção(Q, chave) DecrementaChave(Q, i, chave) ExtraiMínimo(Q) Mínimo(Q)Árvore Van Emde Boas
Array associativo com suporte à operações de filas de prioridade.
Permite apenas a inserção de chaves inteiras que respeitam o intervalo [0, u − 1].
Árvore Van Emde Boas
Árvore Van Emde Boas
Operação Complexidade Inserção(Q, chave) Remoção(Q, chave) Busca(Q, chave) Mínimo(Q)Árvore Van Emde Boas
Fila de prioridade VEB Operação Mínimo Mínimo Inserção Inserção Extrai mínimo Mínimo + Remoção Decrementa chave Busca + Remoção + InserçãoÁrvore Van Emde Boas
Teoricamente a vEB não suporta os valores das chaves geradas pelo algoritmo de cálculo de caminhos mínimos.
Teoricamente...
Árvore Van Emde Boas
Na prática o protocolo define um limite para o custo na qual é viável utilizar uma rota, ou seja, há um intervalo de valores válidos.
O protocolo olsrd define uma constante de 4 bytes como o limite do custo de um caminho, ou seja, na prática, nenhum vértice terá prioridade maior que (4294967295).
A princípio
O algoritmo de Dijkstra utilizando com vEB como fila de prioridade possuiria uma complexidade relativa à:
Organização do protocolo OLSRD
Organização do Algoritmo de Dijkstra
Ambiente de teste
AVL
Ambiente de teste
Heap Binário
Ambiente de teste
Van Emde Boas
Ambiente de teste
Caracteristicas de uma rede de malha sem fio
Ambiente de teste
Grafo base
Ambiente de teste
Repetição de chaves
Ambiente de teste
Altura das estruturas
Ambiente de teste
Ciclos de CPU utilizados
Ambiente de teste
Ciclos de CPU utilizados
Conclusões
AVL
Pontos fortes
- Procedimento ExtraiMínimo;
- Melhor desempenho em pequenas redes;
- Alocação estática dos nós.
Conclusões
AVL
Pontos fracos
- Procedimento DecrementaChave;
- Inserção de chaves repetidas (versão do OLSRD);
- Desempenho comprometido em grandes redes.
Conclusões
Heap Binário
Pontos fortes
- Desempenho do procedimento DecrementaChave;
- Alocação estática dos nós.
Conclusões
Heap Binário
Pontos fracos
- Desempenho do procedimento ExtraiMínimo;
- Desempenho em pequenas redes;
- Desempenho em redes com número reduzido de links.
Conclusões
Árvore Van Emde Boas
Pontos fortes
- Desempenho constante
- Dijkstra executado em tempo linear
- Bom desempenho em ambos os procedimentos;
- Melhor desempenho em grandes redes.
Conclusões
Árvore Van Emde Boas
Pontos fracos
- Espaço de memória variável para cada nó;
- Maior consumo de memória;
- Inviabilidade de alocação estática dos nós.
Conclusões
- AVL para pequenas redes;
- Van Emde Boas melhor desempenho geral;
- Heap Binário melhor custo benefício tempo/memória.
Resultados
Patch aceito pela comunidade
Atualmente em fase de testes
Resultados
Apresentação do trabalho no Fórum de Técnologia em Software Livre
Trabalhos futuros
- Alocação estática da VEB;
- Avaliação das filas de prioridades em algoritmos incrementais.
Referências
CORMEN, T. et al. Introduction to algorithms. Cambridge, Massachusetts: The MIT Press, 2009.
OBERHAUSER, G.; SIMHA, R. Fast data structures for shortest path routing: a comparative evaluation. In: . [S.l.]: IEEE, 1995. p. 1597–1601.
NORTEL. Solutions Breaf: Wireless mesh network. EUA, 2006. 8 p.