Ana Sofia Bernardo Gonçalves
Licenciada em Engenharia Informática
Monitorização de Sistemas Distribuídos em
Redes WiFi
Dissertação para obtenção do Grau de
Mestre em Engenharia Informática
Orientador: Prof. Doutor Vitor Manuel Alves Duarte,
Prof. Auxiliar, Universidade Nova de Lisboa
Presidente:
Arguente:
Vogal:
Júri:
Prof. Doutor Fernando Pedro Reino da Silva Birra
Prof. Doutor Rodolfo Alexandre Duarte Oliveira
Prof. Doutor Vitor Manuel Alves Duarte
Junho, 2015
Monitorização de Sistemas Distribuídos em Redes WiFi
c Ana Sofia Bernardo Gonçalves, Faculdade de Ciências e Tecnologia, UniverCopyright sidade Nova de Lisboa
A Faculdade de Ciências e Tecnologia e a Universidade Nova de Lisboa têm o direito,
perpétuo e sem limites geográficos, de arquivar e publicar esta dissertação através de
exemplares impressos reproduzidos em papel ou de forma digital, ou por qualquer outro
meio conhecido ou que venha a ser inventado, e de a divulgar através de repositórios
científicos e de admitir a sua cópia e distribuição com objectivos educacionais ou de
investigação, não comerciais, desde que seja dado crédito ao autor e editor.
Aos meus pais
A GRADECIMENTOS
Gostaria desde já apresentar os meus agradecimentos aos que me apoiaram durante a
elaboração desta dissertação.
Em primeiro lugar, gostaria de agradecer ao meu orientador, Prof. Doutor Vitor Manuel
Alves Duarte, pela disponibilidade e paciência demonstradas ao longo deste tempo. O seu
apoio foi crucial para a conclusão deste trabalho.
À Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa, em particular
ao Departamento de Informática, por me ter fornecido as bases essenciais para a minha
formação, pelas pessoas que aqui conheci e onde passei a grande parte do meu tempo
nestes últimos anos.
À minha família, principalmente aos meus pais, pelo tempo, dedicação e esforço que
despenderam para me proporcionar melhores oportunidades de vida.
Aos meus amigos, pelas trocas de ideias, apoio e diversão nos bons e maus momentos.
Em especial ao Alexandre, pelo apoio e pela paciência necessária nestes últimos meses.
vii
R ESUMO
As aplicações distribuídas são particularmente difíceis de depurar pelo facto da sua
execução necessitar de interações, de redes de computadores, assíncronas. Acresce ainda o
facto de o seu desempenho depender, não só de fatores internos a cada um dos processos,
mas também a problemas de comunicação da rede, como congestionamento, fraca ou
elevada latência ou perda de pacotes. Esta dificuldade agrava-se quando uma aplicação
distribuída executa através de uma rede WiFi, acrescentando desafios à gestão da qualidade da rede por serem mais instáveis e lentas que as redes cabladas. Esta problemática
pode ser ultrapassada através de ferramentas que, através da monitorização das interações
da rede, e sem as perturbar, possibilitem a depuração e avaliação do desempenho da
aplicação distribuída que está em execução.
Existem já diversas ferramentas de monitorização e análise de tráfego, porém estas
ferramentas não possibilitam a fácil análise das interações geradas apenas pela aplicação e
não têm em consideração os desafios inerentes à compreensão da comunicação através de
redes sem fios, mais concretamente a norma IEEE 802.11
O objetivo desta dissertação consiste em apresentar um conjunto de metodologias
para avaliação de um algoritmo distribuído, através da monitorização de pacotes 802.11
gerados pela aplicação distribuída.
Palavras-chave: Monitorização, redes Wifi, depuração, avaliação, aplicações distribuídas
ix
A BSTRACT
Distributed applications are particularly difficult to debug because their implementation requires asynchronous computer network interactions, and their performance
depends not only on internal factors to each of the processes, but also depends on the
network problems, such as traffic congestion, low or high latency or packet loss. This
difficulty is aggravated when a distributed application is running over a wireless network, given to the fact that WiFi networks are more unstable and slower than wired
networks, adding challenges to the management of network quality. This problem can be
overcome through tools that, by monitoring network interactions and without disturbing
them, enable debugging and performance evaluation of the distributed application that is
executing.
There are already several tools for traffic monitoring and analysis, but these existing
tools do not allow an easy analysis of network interactions generated by the application
and do not help to undertand wireless communication patterns.
The goal of this thesis is to present a set of methods to evaluate a distributed algorithm,
by monitoring 802.11 packets generated by the interactions of a distributed application.
Keywords: Monitoring, wifi networks, debugging, evaluation, distributed applications
xi
C ONTEÚDO
Conteúdo
xiii
Lista de Figuras
xv
Lista de Tabelas
xvii
1
Introdução
1
1.1
Contexto e motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2.1
Implementação de um sistema de análise . . . . . . . . . . . . . . .
5
1.2.2
Estudo de um algoritmo . . . . . . . . . . . . . . . . . . . . . . . . .
5
Estrutura do documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
2
Monitorização de Redes
7
2.1
Redes WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.1
Serviços de Sistema de Distribuição . . . . . . . . . . . . . . . . . .
8
2.1.2
Serviços de Estação . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.3
Controlo de Acesso ao Meio . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.4
Gestão de Energia . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.1.5
Tipos de Pacotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Monitorização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.1
Biblioteca PCap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Ferramentas de Captura . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3.1
TCPDump . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3.2
Wireshark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3.3
Wireshark para Sistemas Distribuídos . . . . . . . . . . . . . . . . .
22
2.3.4
Monitorização de tráfego de rede de um processo com base no PCap 22
2.3.5
Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
2.3
3
23
Algoritmos de Consenso
25
3.1
Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.2
Paxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.3
Turquois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.4
Consenso Multi-Valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
xiii
CONTEÚDO
3.5
4
6
30
Sistema de Análise
33
4.1
Requisitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2
Captura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.3
Análise de Tráfego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.3.1
Classificação de Tráfego . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.3.2
Informação sumária . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
Visualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.4.1
Versão Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.4.2
Versão Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.4
5
Análise do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Análises Efetuadas
43
5.1
Ambiente de testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
5.2
Análise de capturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.3
Análise de tempos de execução . . . . . . . . . . . . . . . . . . . . . . . . .
49
5.4
Análise de tráfego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5.5
Análise de tráfego extra . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
Conclusões
57
6.1
Objetivos e metas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.2
Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.3
Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Bibliografia
63
xiv
L ISTA DE F IGURAS
2.1
Exemplificação de um conjunto de serviços estendido . . . . . . . . . . . . . .
8
2.2
Exemplificação de um conjunto de serviços independente . . . . . . . . . . . .
9
2.3
Representação do protocolo CSMA/CA1 . . . . . . . . . . . . . . . . . . . . .
12
2.4
2.5
Exemplificação do protocolo
RTS/CTS2
. . . . . . . . . . . . . . . . . . . . . .
DCF com implementação dos protocolos CSMA/CA e
superframe4
RTS/CTS3
13
. . . . . . .
14
2.6
Estrutura de uma
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.7
Estrutura de um pacote ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.8
Elementos envolvidos na captura de pacotes5 . . . . . . . . . . . . . . . . . . .
19
3.1
Execução correta do algoritmo Paxos . . . . . . . . . . . . . . . . . . . . . . . .
28
4.1
Arquitetura da rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2
Exemplo de tráfego de rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.3
Versão Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.4
Versão Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.5
Gráfico da versão web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.6
Informação agregada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.7
Diagrama do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.8
Gráfico temporal da execução do algoritmo para cada tipo de pacote . . . . .
41
4.9
Gráfico temporal da execução do algoritmo para cada nó interveniente . . . .
41
4.10 Gráficos de tráfego acumulado . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
5.1
Falha na receção do pacote INIT no nó 192.168.1.101 . . . . . . . . . . . . . . .
45
5.2
Falha na receção do pacote INIT no nó 192.168.1.101, com inclusão da porta 12347 45
5.3
Falha na receção do pacote VALUE nos nós 192.168.1.101 e 192.168.1.107 . . .
45
5.4
Caso de erro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
5.5
Caso de retransmissão de pacote . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.6
Gráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.7
Gráfico com inclusão da porta 12345 . . . . . . . . . . . . . . . . . . . . . . . .
47
5.8
Gráfico com zoom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
5.9
Gráfico com perda de pacotes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
5.10 Gráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
5.11 Evolução dos tempos médios de execução, sem broadcast adicional . . . . . . .
50
xv
L ISTA DE F IGURAS
5.12 Evolução dos tempos médios de execução, com broadcast adicional . . . . . .
50
5.13 Evolução dos tempos mínimos de execução, sem broadcast adicional . . . . . .
51
5.14 Evolução dos tempos mínimos de execução, com broadcast adicional . . . . . .
51
5.15 Execução do algoritmo com 6 nós e 10ms de intervalo, sem broadcast adicional
54
5.16 Execução do algoritmo com 6 nós e 40ms de intervalo, sem broadcast adicional
54
xvi
L ISTA DE TABELAS
2.1
Tipo de informação apresentada sobre cada pacote . . . . . . . . . . . . . . . .
21
5.1
Melhores tempos entre envio de mensagens . . . . . . . . . . . . . . . . . . . .
51
5.2
5.3
Tráfego total para cada tempo entre envio de mensagens e respetivo
no
de nós
Tráfego da aplicação para cada tempo entre envio de mensagens e respetivo
52
no
de nós . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5.4
Tráfego de uma execução com 5ms, com broadcast adicional . . . . . . . . . . .
53
5.5
Tráfego da aplicação, com injeção de tráfego extra, sem broadcast adicional . .
53
6.1
Tráfego da aplicação, sem broadcast adicional . . . . . . . . . . . . . . . . . . .
59
6.2
Tráfego da aplicação com injeção de tráfego extra, sem broadcast adicional . .
60
xvii
CAPÍTULO
1
I NTRODUÇÃO
1.1
Contexto e motivação
Com o aparecimento e crescimento das redes de computadores e da Internet, existe
uma crescente necessidade de modelos de cooperação e de mecanismos que permitam
o acesso e a partilha de recursos, independentemente da sua localização. Os sistemas
distribuídos surgem com a intenção de tirar partido dessa partilha. Permite-se assim
que utilizadores e aplicações acedam e partilhem recursos remotos de forma eficiente e
controlada, beneficiando também de maior capacidade computacional e armazenamento
disponibilizado.
Por definição, um sistema distribuído é uma coleção de computadores independentes
que o utilizador, idealmente, perceciona como um sistema único e coerente [33]. Isto é,
apesar da heterogeneidade e variedade de computadores, um sistema distribuído tem
que ser capaz de executar de modo determinístico e fiável, e a ser percecionado como
um só. Para tal, é necessário que os computadores intervenientes colaborem entre si.
Esta colaboração poderá ser feita, por exemplo, através de modelos de programação ou
middlewares que permitam a troca de informação.
Um sistema distribuído visa cumprir diversos objetivos. Contudo, apesar de apresentarem vantagens, comparativamente aos sistemas centralizados, estes objetivos aumentam a
complexidade dos sistemas distribuídos. Desta forma, existem novos desafios e problemas
que necessitam ser resolvidos. Neste contexto, surgem então os algoritmos distribuídos,
para resolver as problemáticas inerentes à computação e sistemas distribuídos. Um algoritmo distribuído consiste num algoritmo que executa em computadores independentes
que colaboram entre si. Estes computadores poderão executar considerando a possibilidade de falhas de alguns dos intervenientes. Alguns dos problemas que são resolvidos
com algoritmos distribuídos são, por exemplo, a eleição de líder, pesquisa distribuída,
geração de spanning-tree, exclusão mútua e alocação de recursos [21].
1
CAPÍTULO 1. INTRODUÇÃO
Um dos maiores problemas de computação distribuída é o estabelecimento de consenso. O problema de consenso requer que um conjunto de processos concorde com um
determinado valor. Para tal, é necessário que exista um quórum de processos a decidir um
dado valor v. Um algoritmo de consenso terá assim que funcionar por várias fases, garantindo que à medida que o algoritmo avança, exista um quórum de processos em sintonia.
Para tal é necessário que cada processo comunique o seu estado aos restantes, tendo que
comunicar periodicamente e/ou à medida que avança para cada fase do algoritmo. Este
facto leva a que haja um número significativo de interações na rede.
O comportamento de um algoritmo distribuído é, por norma, difícil de prever e verificar. Isto porque, mesmo que a sua implementação seja simples, o facto da sua execução
correr paralelamente em diversos processos, com fases intercaladas de forma indeterminada, implica que possam haver diferentes comportamentos do algoritmo para os mesmos
valores de entrada. Além disso, estes algoritmos enfrentam algumas incertezas que envolvem as condições da rede, como por exemplo a) falhas de comunicação; b) ordem de
mensagens desconhecida; c) incerteza no tempo de entrega de mensagens; e d) vários nós
a executar em simultâneo, começando em tempos diferentes e a trabalhar em velocidades
diferentes [21]. Devido a estas incertezas, ao não-determinismo, e às inúmeras interações
que passam pela rede, torna-se difícil verificar o funcionamento, correto ou incorreto,
de um algoritmo. Isto é, torna-se difícil avaliar o desempenho ou a causa de erros de
um algoritmo. Entre estas situações encontram-se problemas provocados por fenómenos
de saturação, ou interferências entre diversos sistemas que partilham a rede. Este facto
dificulta o processo de desenvolvimento e monitorização das aplicações.
Considere-se o exemplo do trabalho de Almeida[1]. Este trabalho consistiu no desenho
de um protocolo de encaminhamento, tolerante a intrusões, com consenso de dados numa
rede de sensores sem fios. Este trabalho recorreu a um protocolo de encaminhamento,
MINSENS++ [34], que introduz tolerância a intrusões através da existência de múltiplos
caminhos disjuntos, para que, em caso de um nó corrompido, esse nó não prejudique a
restante rede. As redes de sensores são constituídas por diferentes tipos de nós, existindo
um tipo de nós, denominado estações de base, que contém maior capacidade computacional que os restantes. No âmbito deste trabalho, são estes os nós responsáveis por calcular
as árvores de encaminhamento. O protocolo MINSENS++ pressupõe que estes nós podem
ficar comprometidos, pelo que é necessário recorrer a resoluções por consenso para casos
de divergência de valores entre estações de base da mesma rede de sensores.
Parte do desenvolvimento deste trabalho foi dedicado a um estudo do desempenho
do algoritmo de consenso utilizado. Neste estudo foram apontadas diversas dificuldades
em avaliar a solução e o impacto que esta tem na rede. Nas conclusões deste estudo são
apresentados problemas de performance e de escalabilidade que se mantêm inexplicáveis.
Isto porque não existem métodos que permitam analisar as interações, via rede, à medida
que o algoritmo é desenvolvido. Nota-se então a necessidade de depurar as comunicações
de rede, de forma a perceber o impacto que esta poderá ter no algoritmo, ou vice-versa. A
mesma necessidade é notada nas mais variadas situações e já foi alvo de alguns trabalhos
2
1.1. CONTEXTO E MOTIVAÇÃO
no Departamento de Informática [7], [23].
A par com a evolução dos sistemas e algoritmos distribuídos, o uso das redes sem fios
também tem vindo a aumentar. Com o aparecimento de dispositivos móveis, como computadores portáteis, sensores, telemóveis e tablets, existe a necessidade destes dispositivos
se ligarem a uma rede independentemente da sua localização. Com velocidades cada vez
maiores, o uso de redes WiFi, é de importância cada vez maior. No entanto, ao satisfazer
esta necessidade, existe um acréscimo na complexidade da rede e a importância de lidar
com os problemas antes apontados aos sistemas distribuídos.
Uma rede WiFi funciona através do uso de ondas rádio, pelo que este meio de comunicação tem a particularidade de ser partilhado. Como tal, é possível que vários dispositivos
tentem aceder ao mesmo meio. Devido a este facto, uma rede WiFi é suscetível de sofrer
interferências internas, assim como externas à rede e que prejudicam o desempenho da
mesma. Estas interferências podem ser provocadas por outros dispositivos rádio (telefones sem fios ou micro-ondas1 , por exemplo) ou outras redes que comuniquem através
do mesmo canal de rádio. Numa rede WiFi podem também ocorrer colisões de pacotes,
provocadas pelos nós da mesma. Estas colisões ocorrem quando mais do que um nó tenta
aceder ao meio em simultâneo. Apesar de não ser possível controlar as interferências
externas, existem mecanismos de controlo de acesso ao meio, de modo a evitar que dois
dispositivos, da mesma rede, acedam em simultâneo. Estes mecanismos têm como objetivo
minimizar as colisões, sendo responsáveis por decidir que estação pode aceder ao meio.
No entanto, este processo cria um certo overhead na rede. Este overhead e as interferências
externas, tornam uma rede 802.11 mais lenta do que seria expectável, degradando-se com
a utilização.
Uma rede WiFi pode também ser alvo de um ou mais clientes maliciosos. Estes clientes
podem alterar as suas definições de modo a consumirem grande parte da largura de
banda da rede, prejudicando os restantes clientes e o desempenho total da rede. Há que
considerar também o facto de uma rede 802.11 ser mais volátil, devido à movimentação
das estações, existe uma alteração constante do grafo da rede. Estes fatores tornam as
redes 802.11 mais imprevisíveis e instáveis, podendo ter períodos de inúmeras perdas de
pacotes, devido a colisões ou congestionamento da rede.
Considere-se assim um algoritmo de consenso executado num sistema distribuído
numa rede WiFi. As incertezas que este enfrenta são agravadas pela instabilidade e
imprevisibilidade da rede.
Este acréscimo na complexidade da rede dificulta ainda mais a verificação e avaliação
da execução real de um algoritmo distribuído. Em muitos casos, estes fatores não podem
ser resolvidos com técnicas já conhecidas de verificação do código. Isto deve-se ao facto
do desempenho observado pode ser degradado por fenómenos externos aos próprios
algoritmos que se pretendem avaliar. Uma abordagem passa por monitorizar as próprias
interações e o tráfego nessas redes. Esta monitorização não deverá, idealmente, interferir
1 Os
telefones sem fios e micro-ondas funcionam no mesmo intervalo de frequências que algumas redes
WiFi
3
CAPÍTULO 1. INTRODUÇÃO
na rede ou nos programas em execução. Desta forma, será possível compreender melhor e
avaliar o que realmente ocorre durante o funcionamento desses algoritmos, e despistar
situações que de outro modo se não seriam detetadas.
Existem trabalhos feitos com o intuito de controlar e melhorar a utilização e qualidade
das redes WiFi que mostram a necessidade que existe de gerir a instabilidade deste tipo de
redes. WiFox [9], por exemplo, conclui que os pontos de acesso constituem um bottleneck na
rede, por não terem vazão para tratar dos pedidos de todas as estações. Com esta conclusão
os autores propuseram a priorização dos pacotes do ponto de acesso. Naturalmente, após
completar a solução proposta, os autores necessitaram de voltar a estudar o rendimento
da rede, utilizando novamente a monitorização de tráfego.
Nota-se assim, uma vez mais, a necessidade de um ambiente e regime controlado que
permita a análise do impacto que um algoritmo distribuído tem na rede, principalmente
no contexto das redes 802.11 pela sua instabilidade e imprevisibilidade. Um elemento
importante deste regime, será uma ferramenta capaz de monitorizar e distinguir o tráfego
gerado pelo algoritmo do restante, assim como o tráfego gerado pelo protocolo 802.11. Para
tal, terá que se considerar todo o tráfego gerado numa rede WiFi para controlo do meio,
filtrando este tráfego que se torna desnecessário para a compreensão do comportamento
da rede, mas que poderá ser útil, a nível da aplicação, para obter alguns dados sobre o
estado da rede. Através desta ferramenta será então possível angariar um conjunto de
dados que possam dar uma visão generalizada do impacto que o algoritmo poderá ter
na rede, ou vice-versa, e o seu desempenho, assim como das influências externas ou de
outros nós da rede.
1.2
Objetivos
Através das necessidades e dificuldades passadas em alguns dos trabalhos anteriormente
referidos, justifica-se a existência de um conjunto de metodologias que ajude na depuração,
e avaliação de um algoritmo e do seu impacto na rede. Devido ao uso recorrente de redes
WiFi e das complicações que lhes são inerentes, esta dissertação propõe focar-se, como caso
de estudo, em algoritmos distribuídos que usufruem de uma rede sem fios, recorrendo a
técnicas de monitorização de tráfego WiFi. No entanto, qualquer sistema que gere tráfego
na rede poderá beneficiar deste trabalho.
O objetivo desta dissertação passa por auxiliar a implementação de algoritmos distribuídos com um conjunto de métodos que permitam avaliar e melhorar os tempos de
execução do mesmo, recorrendo a técnicas de monitorização sem perturbar o sistema avaliado. Para tal, pretende-se focar na captura de pacotes 802.11, proporcionando um meio
de avaliação das condições do algoritmo e da rede. Como complemento a este conjunto de
métodos, pretende-se desenvolver um sistema de análise do tráfego da rede. Desta forma,
existem duas fases de elaboração desta dissertação. Estas fases são explicadas de seguida.
4
1.2. OBJETIVOS
1.2.1
Implementação de um sistema de análise
Pretende-se criar um sistema de análise que permita avaliar as condições da rede. Isto
é, através da monitorização das execuções do algoritmo, pretende-se que seja possível
analisar o estado da rede e, consequentemente, tirar conclusões em relação aos tempos
de execução vs condições da rede. Com este objetivo em mente, este sistema requer a
existência de três componentes:
Captura de Tráfego.
Este componente deverá ser responsável pela captura de pacotes, por nós independentes do sistema em análise. Mais especificamente, este componente deverá
ser capaz de capturar a informação do tráfego relevante, possivelmente baseado
em ferramentas já existentes, como o TCPDump e/ou a biblioteca PCap [36], sem
interferir e perturbar a rede e aplicação.
Análise de Tráfego.
O componente de análise de tráfego deverá ser responsável pela classificação e
análise da informação recolhida. Esta análise terá como vista a identificação dos
vários tipos de mensagens, seu número, volume e latência, ao longo do tempo.
Visualização.
Este componente deverá ser responsável pela apresentação da análise efetuada
e correlação com a aplicação. Esta correlação, ao longo da execução do algoritmo
distribuído e suas mensagens, tem como vista a explicação do desempenho e latência
observada pela aplicação. Deverá ainda ser possível detetar as perturbações sofridas
devido a outro tráfego, interferências ou fenómenos de saturação.
1.2.2
Estudo de um algoritmo
O trabalho de Almeida refere como trabalho futuro a elaboração de testes mais exaustivos
ao algoritmo de consenso. Deste modo, e aproveitando esta necessidade, pretende-se
estudar a implementação de um algoritmo base deste trabalho [25]. Este algoritmo será
utilizado para avaliação do sistema de análise implementado, mas também como base de
estudo para o conjunto de metodologias futuramente apresentados.
Tem-se como objetivo apresentar um conjunto de métodos que, podendo recorrer ao
sistema de análise, consigam avaliar o funcionamento do algoritmo de consenso. Pretendese estudar o comportamento e desempenho do algoritmo em várias das configurações
que antes foram deficientemente avaliadas. Através deste conjunto de metodologias
tenciona-se completar os seguintes estudos:
1. Estudo do comportamento do algoritmo com recurso ao sistema de análise. Este
estudo tenciona mostrar como é que o comportamento do algoritmo varia, dependendo do tempo de execução.
5
CAPÍTULO 1. INTRODUÇÃO
2. Estudo do desempenho do algoritmo com recurso à execução do algoritmo com diferentes parametrizações. Através destas execuções pretende-se comparar o impacto
que as diferentes configurações do algoritmo podem ter.
3. Estudo do impacto do algoritmo na rede. Perante diferentes condições de rede,
pretende-se determinar se o algoritmo prejudica outro tráfego que esteja a decorrer,
ou se o tráfego extra prejudica a execução do algoritmo.
1.3
Estrutura do documento
Este documento divide-se em seis capítulos. No capítulo 1 fez-se uma introdução ao
problema que esta dissertação pretende resolver, mostrando o contexto e a motivação,
descrevendo-se também os objetivos para este trabalhos.
No capítulo 2 serão apresentados e introduzidos conceitos importantes para a compreensão dos desafios que esta dissertação encontra. Primeiro são introduzidos alguns
detalhes do funcionamento das redes de computadores, com foco nas redes da norma IEEE
802.11 e os desafios que existem neste tipo de redes. No fim deste capítulo são referidos
conceitos de monitorização de tráfego, mais uma vez, com foco na captura de tráfego WiFi
e, de seguida, são apresentadas algumas ferramentas existentes para monitorização de
redes de computadores. No fim deste capítulo são apresentadas as conclusões tiradas após
este estudo.
No capítulo 3 são introduzidos conceitos e a noção de algoritmos de consenso, devido
ao uso de um algoritmo de consenso para avaliação da solução proposta. Este capítulo
exemplifica os algoritmos de consenso através da explicação dos algoritmos Turquois [25]
e Multi-Valued Consensus [34], explicados nas secções 3.3 e 3.4.
No capítulo 4 é apresentado o sistema de análise desenvolvido. Primeiro são explicados
os requisitos necessários, passando ao detalhe dos componentes que constituem o sistema.
No capítulo 5 é então exposto o conjunto de métodos de estudo. Começando por
explicar a implementação do algoritmo Turquois usada e o ambiente de testes utilizado.
De seguida são apresentadas as análises efetuadas ao algoritmo e os respetivos resultados.
Por fim, no capítulo 6 são apresentadas as conclusões retiradas da elaboração desta
dissertação e trabalho futuro.
6
CAPÍTULO
2
M ONITORIZAÇÃO DE R EDES
Este capítulo abordará alguns conceitos do escopo desta dissertação que serão importantes
para a sua compreensão. Serão também abordados e referenciados alguns trabalhos já
existentes de monitorização de tráfego.
Na secção 2.1 serão introduzidos conceitos referentes ao funcionamento das redes
sem fios, mais concretamente à norma IEEE 802.11 e aos problemas que estão inerentes
a este tipo de redes. Na secção 2.2 serão introduzidos conceitos relacionados com a
monitorização e captura de tráfego de rede, assim como referências às especificações
necessárias para a captura de tráfego numa rede sem fios. Por fim, na secção 2.3 serão
apresentadas algumas ferramentas de captura de tráfego, e alguns casos de estudo onde se
recorre à monitorização de tráfego específico de uma aplicação distribuída ou de somente
um processo, para compreender ou melhorar o funcionamento de determinado sistema.
Na secção 2.3.5 serão apresentadas as conclusões do estudo feito às ferramentas de captura
apresentadas.
2.1
Redes WiFi
Uma rede local sem fios, Wireless Local Area Network (WLAN), consiste num conjunto
de computadores, fixos ou portáteis, que comunicam entre si através de ondas rádio. No
contexto das WLAN, cada computador ligado em rede é denominado de estação e várias
estações ligadas entre si constituem um conjunto de serviços básico.
Uma rede WiFi poderá conter vários conjuntos de serviços básicos de forma a aumentar
a cobertura de rede. Para tal, este tipo de redes mantém dois ou mais conjuntos de serviços
básicos ligados entre si, através de um sistema de distribuição. A comunicação entre
o conjunto de serviços básico e o sistema de distribuição estabelece-se através de um
ponto de acesso. O ponto de acesso é o dispositivo responsável por passar a informação
do conjunto de serviços básicos para o respetivo sistema de distribuição, tal como é
7
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
responsável por estabelecer a comunicação entre estações. Quando uma rede funciona
através desta arquitetura, a rede executa em modo infraestrutura. Desta forma, à medida
que se movimenta, uma estação estará ligada ao ponto de acesso mais próximo, sem
perder acesso à rede. A norma 802.11 determina que o sistema de distribuição forneça
um conjunto de serviços que podem ser divididos em serviços de estação e serviços de
sistema de distribuição.
Em suma, para dois conjuntos de serviços básicos existem dois pontos de acesso, um
para cada, e ambos os pontos de acesso comunicam entre si através de um sistema de
distribuição. Este sistema de distribuição poderá ser, por exemplo, uma rede ethernet.
A este conjunto, no seu todo, denomina-se conjunto de serviços estendido. A figura 2.1
ilustra um exemplo de uma estrutura de um conjunto de serviços estendido.
Sistema de Distribuição
Ponto de Acesso
Estação
Ponto de Acesso
Estação
Estação
Estação
Estação
Estação
Conjunto de Serviços Básico
Conjunto de Serviços Básico
Figura 2.1: Exemplificação de um conjunto de serviços estendido
No entanto, uma rede WiFi não requer sempre a existência de um ponto de acesso. Uma
WLAN é considerada uma rede ad-hoc, ou um conjunto de serviços básicos independente,
quando o conjunto de serviços básico não tem acesso a redes exteriores e as estações
comunicam entre si ponto-a-ponto. A figura 2.2 ilusta uma rede ad-hoc.
2.1.1
Serviços de Sistema de Distribuição
Os cinco serviços de sistema fornecidos pelo sistema de distribuição são:
Associação. Quando uma estação pretende ligar-se a uma WLAN necessita juntar-se
à infra-estrutura de um conjunto de serviços básico. Para tal, existe o serviço de
associação que permite que uma estação se associe a um dado ponto de acesso.
Reassociação. Um dos requisitos de uma rede WiFi é que permita a transição das estações
entre conjuntos de serviços básicos da mesma rede. Este serviço permite que a
estação se associe a outro ponto de acesso da mesma rede, sem perder conectividade.
8
2.1. REDES WIFI
Estação
Rede ad-hoc
Estação
Estação
Figura 2.2: Exemplificação de um conjunto de serviços independente
Dissociação. Este serviço consiste na terminação da associação entre uma estação e um
ponto de acesso, deixando de ser possível a comunicação entre a estação e o ponto
de acesso.
Distribuição. Este serviço consiste na distribuição da informação. Quando uma estação
A pretende enviar um pacote à estação B é enviado um pedido para o ponto de
acesso do conjunto de serviços básico. De seguida, o pedido é transmitido através
do sistema de distribuição até ao ponto de acesso a que a estação B se encontra
associada.
Integração. Este serviço é utilizado para permitir a comunicação com outro tipo de redes.
Este serviço executa as alterações necessárias para que o pacote esteja de acordo com
o protocolo da rede destino, e vice-versa. [3]
2.1.2
Serviços de Estação
Uma rede WiFi tem a particularidade de não se encontrar fisicamente limitada como no
caso de uma rede ethernet. As redes IEEE 802.11 utilizam ondas rádio para estabelecer
a comunicação e como tal existe o problema de vários dispositivos utilizarem a mesma
frequência de rádio quer tenham, ou não, o objetivo de enviar informação. Esta particularidade leva então à necessidade de identificar, autorizar e proteger a transmissão entre
duas estações ou entre uma estação e um ponto de acesso. Para tal existem os seguintes
serviços de estação:
Autenticação. Este serviço consiste na verificação de que a estação é reconhecida e autorizada a comunicar com outra estação ou um ponto de acesso. Assim que a estação se
encontra autenticada, esta pode prosseguir com o serviço de associação descrito anteriormente. Existem dois tipos de serviço de autenticação: Autenticação de Sistema
Aberto, em que qualquer estação que se tenta autenticar pode comunicar na rede, e
Autenticação de Chave Partilhada, em que as estações que se pretendem associar
necessitam de ter uma chave secreta partilhada.
9
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
Revogação de Autenticação. Consiste na terminação do serviço de autenticação, deixando a estação de estar autenticada perante um ponto de acesso, a associação entre
ambos deixa de existir.
Privacidade. Este serviço consiste na garantia de privacidade da comunicação entre
estação e ponto de acesso. Este serviço é garantido através da cifra do conteúdo
dos pedidos, através de Wired Equivalent Privary (WEP) [12] ou Wireless Application
Protocol (WAP) [26]. Este serviço poderá não ser utilizado, deixando a comunicação
ser transmitida em claro e passível de sofrer ataques de eavesdropping1 .
Serviço de entrega de unidade de dados MAC. Este serviço é responsável por garantir
que os dados chegam ao seu destino. [8]
2.1.3
Controlo de Acesso ao Meio
Genericamente, a comunicação dos protocolos de rede pode ser feita através de dois tipos
de ligação: 1) ligação ponto a ponto e 2) ligação por difusão. A ligação ponto a ponto
permite conectar dois nós diretamente, havendo somente dois intervenientes na comunicação. A ligação por difusão permite que vários nós recebam e enviem pacotes através
de um canal de comunicação partilhado. Neste caso, quando um pacote é transmitido,
todos os nós recebem. As redes WiFi e Ethernet são exemplos de redes que utilizam ligação
por difusão. No entanto, neste tipo de ligação ocorre o problema de múltiplo acesso. Este
problema ocorre quando mais que um nó tenta aceder ao meio de comunicação. Nesta
situação, existindo vários pacotes a ser transmitidos na rede, ocorre uma colisão e nenhum
dos pacotes envolvidos chega corretamente ao destino.
Considerando o exemplo da norma IEEE 802.11, esta recorre a ondas rádio para
comunicar informação, utilizando o ar como meio de transmissão. Este facto possibilita
que qualquer dispositivo rádio possa, potencialmente, emitir para este meio de difusão.
O problema de múltiplo acesso encontra-se mais uma vez presente, estendendo-se até
aos nós externos à rede. Isto porque, existindo duas redes 802.11 a transmitir no mesmo
canal rádio, as estações de ambas as redes competem pelo acesso ao mesmo meio de
comunicação.
De modo a combater o problema de múltiplo acesso foram criados protocolos de
controlo de acesso ao meio. Estes protocolos visam controlar e coordenar os nós que
acedem à rede, na tentativa de minimizar a ocorrência de colisões.
De seguida são apresentados os mecanismos de controlo de acesso ao meio, tanto das
redes Ethernet como das redes WiFi.
1 Eavesdropping consiste num ataque de redes de computadores em a informação que passa entre dois principais é
"ouvida"por terceiros não autorizados
10
2.1. REDES WIFI
2.1.3.1
CSMA/CD
Como é sabido, as estações de uma rede 802.3 comunicam através de uma ligação de
difusão. Como tal, este protocolo recorre a um mecanismo de controlo de acesso ao meio.
As redes ethernet executam um protocolo de deteção de colisões, denominado Carrier Sense
Multiple Access with Collision Detection, vulgarmente conhecido como CSMA/CD [11]. Este
protocolo pretende prevenir a ocorrência de colisões recorrendo a duas características
das estações: a) percecionar quando outra estação se encontra a transmitir e b) detetar a
colisão enquanto está a transmitir [16]. O protocolo CSMA/CD define que:
1. Uma estação nunca começa a transmissão de um pacote caso detete que existe outro
nó da rede a transmitir.
2. Durante a transmissão de um pacote, se a estação detetar que existe mais atividade
no meio, interrompe a sua transmissão.
3. Antes de retransmitir, é necessário esperar um tempo adicional para garantir que o
meio não está a ser usado.
2.1.3.2
CSMA/CA
Como referido anteriormente, o protocolo CSMA/CD requer que uma estação seja capaz
de ouvir e transmitir para a rede em simultâneo, sendo capaz de interromper a transmissão
em caso de colisão. Contudo, os dispositivos rádio de uma rede WiFi não possuem esta
capacidade, pois se escutarem durante uma transmissão o seu próprio sinal será tão forte
que só ouvem a sua própria emissão, impossibilitando a deteção de colisões. Para colmatar
este problema, as redes 802.11 utilizam uma versão modificada do protocolo CSMA/CD,
o protocolo Carrier Sense Multiple Access with Collision Avoidance, vulgarmente conhecido
como (CSMA/CA) [12].
A base da filosofia deste protocolo é semelhante à utilizada no protocolo CSMA/CD.
Este novo protocolo utiliza a capacidade das estações analisarem o estado de utilização do
canal. Contudo, como não é possível detetar a utilização do canal durante a transmissão,
este protocolo foca-se em evitar a ocorrência de colisões, ao invés de as detetar. Desta
forma, o protocolo CSMA/CA define que:
1. Quando a estação pressente que o canal está inativo, transmite o pacote após esperar
um tempo adicional conhecido como DIFS (Distributed Inter-frame Space).
2. Caso o canal se encontre ativo, a estação espera um tempo aleatório para repetir a
tentativa de envio.
3. Ao fim do tempo aleatório, quando o canal se encontra inativo, a estação transmite o
pacote e espera pela chegada de um pacote ACK.
11
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
4. Ao receber o pacote ACK, a estação reconhece que o seu pacote foi recebido no
nó destino. Se a estação tiver mais pacotes para transmitir, recomeça o processo
no passo 2. Caso o pacote ACK não seja recebido, é estabelecido mais um tempo
aleatório para recomeçar a fase 2, desta vez com um intervalo de tempo maior.
No caso do nó destino, quando este recebe um pacote de dados, e após verificar a
integridade do pacote, espera um intervalo de tempo conhecido como SIFS (Short Interframe Space), para depois enviar o respetivo ACK. Este processo é descrito na figura
2.3.
A
DIFS
{
B
Dados
ACK
} SIFS
Figura 2.3: Representação do protocolo CSMA/CA2
2.1.3.3
RTS/CTS e O Problema do Nó Escondido
Ao contrário das redes ethernet em que todas as estações se ouvem entre si, as redes WiFi,
devido ao uso de ondas de rádio, não garante que todas as estações da rede sejam capazes
de ouvir as restantes. Apesar de implementação do protocolo CSMA/CA, este facto
leva a que este protocolo não seja capaz de evitar ou detetar todas as colisões possíveis.
Reconhece-se assim um problema adicional, conhecido como o Problema do Nó Escondido.
Este problema ocorre, por exemplo, quando numa rede existem três estações A, B e C e,
sendo B o ponto de acesso, por exemplo. Devido à distância entre as estações A e C, a
estação B consegue alcançar ambas A e C mas A não alcança C nem C alcança A. Esta
situação está predisposta à ocorrência de colisões, visto que quando A quiser transmitir
não conseguirá detetar se C está ou não a transmitir, e vice-versa.
De modo a resolver este problema foi criado o protocolo Request To Send/Clear to Send
(RTS/CTS) [12] na camada MAC. Este protocolo define que, quando uma estação quer
transmitir, seja enviado um pacote de pedido de envio, conhecido como Request to Send
(RTS), ao ponto de acesso. A estação emissora terá assim que esperar pela receção de um
2 Figura
baseada em [16]
12
2.1. REDES WIFI
pacote de autorização de envio, Clear to Send (CTS). Só após a receção de um pacote CTS é
que a estação estará autorizada a enviar o seu pacote. Como todas as estações conseguem
ouvir a atividade do ponto de acesso, quando um CTS é enviado todas as estações ficam
cientes de que o meio está ocupado. Este processo garante que o meio fica reservado,
deixando as restantes estações em espera durante a transmissão do pacote. Deste modo
existem garantias de que, mesmo que a estação C não consiga ouvir a estação A, a estação
C é notificada por B e não corre o risco de transmitir ao mesmo tempo que a estação A.
Este processo é exemplificado na figura 2.4.
RTS
Área notificada
após RTS
A
B
CTS
C
Área notificada
após CTS
Figura 2.4: Exemplificação do protocolo RTS/CTS3
2.1.3.4
Funções de Coordenação
As redes WiFi utilizam vários protocolos para partilha do meio de comunicação. Estes protocolos são denominados funções de coordenação. Existem duas funções de coordenação,
sendo estas a função de coordenação distribuída, Distributed Coordination Function (DCF),
e a função de coordenação central, Point Coordination Function (PCF).
DCF
A função DCF, sendo um algoritmo distribuído executado por todas as estações, pode
ser utilizado tanto por redes ad-hoc como por redes em modo infra-estrutura. Esta função
executa os protocolos CSMA/CA e RTS/CTS apresentados nas secções 2.1.3.2 e 2.1.3.3,
respetivamente. A figura 2.5 ilustra o funcionamento da função DCF.
PCF
A função PCF é somente utilizada em redes em modo infra-estrutura, devido à sua
necessidade de uma estação central executar o algoritmo de coordenação. Nesta função
de coordenação o tempo é dividido em superframes. Cada superframe é dividida entre um
periodo de contenção, Contention Period (CP), em que é utilizada a função DCF, e um
período livre de contenção, Contention Free Period (CFP), em que é utilizada a função PCF.
3 Figura
4 Figura
baseada em [6]
baseada em [16]
13
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
A
DIFS
{
RTS
} SIFS
CTS
SIFS
Restantes nós
da rede
B
{
Dados
Acesso
diferido
} SIFS
ACK
Figura 2.5: DCF com implementação dos protocolos CSMA/CA e RTS/CTS4
Como o nome indica, o período livre de contenção elimina a necessidade das estações
competirem pelo meio, sendo o ponto de acesso responsável por coordenar as estações.
O ponto de acesso elege, à vez, a estação autorizada a transmitir. Através de uma lista
ordenada por prioridade, o ponto de acesso envia um pacote do tipo CF-Poll à estação
eleita. Após a receção deste pacote, se a estação eleita tiver dados para transmitir, prossegue
com a transmissão do pacote e ACK respetivo ao pacote CF-Poll. Este processo repete-se
para todas as estações da lista.
Para garantir que as estações a transmitir através da função DCF não interfiram com a
função PCF, antes de se dar início a este período, existe um tempo de espera denominado
PCF Inter-frame Space (PIFS). Após este tempo de espera, a função PCF dá início ao período
CFP quando o ponto de acesso envia um pacote beacon. O período livre de contenção
terminado quando o ponto de acesso envia um pacote do tipo CF-End. A estrutura de
uma superframe é ilustrada pela figura 2.6.
Superframe
Período livre de contenção - CFP
Dados +
CF-Poll
Beacon
PA
Dados + CF-Ack
+ CF-Poll
Período de
contenção - CP
Dados + CF-Ack
+ CF-Poll
Dados +
CF-Poll
CF-End
Dados +
CF-Ack
EST 1
Dados +
CF-Ack
EST 2
DCF
EST 3
Dados +
CF-Ack
EST 4
PIFS
SIFS
SIFS
SIFS
SIFS
SIFS
PIFS
SIFS
PA não obteve resposta de EST 3
Figura 2.6: Estrutura de uma superframe5
14
SIFS
2.1. REDES WIFI
2.1.4
Gestão de Energia
Uma rede sem fios pode ser constituída por vários dispositivos móveis, podendo estes ser
portáteis, telemóveis, tablets, etc. Para estes dispositivos a gestão de energia é importante
para aumentar o tempo útil de bateria. Como tal, o protocolo 802.11 possibilita que as
estações alternem entre os estados ativo e inativo, de modo a pouparem energia durante
os períodos inativos.
O modo de poupança de energia começa quando a estação A notifica o ponto de acesso
que irá alterar o seu estado para inativo. Com esta notificação, o ponto de acesso sabe
quais são as estações que se encontram no período de poupança de energia. Durante este
período, se o ponto de acesso receber um pacote que seja destinado à estação A, sabendo
que esta se encontra em modo inativo, em vez de transmitir o pacote, este é mantido em
espera num buffer.
O ponto de acesso envia periodicamente pacotes beacon (tipicamente a cada 100ms
[16]). Estes pacotes contêm a lista de estações com pacotes em espera para serem enviados.
Quando a estação A retorna ao estado ativo, ao receber um beacon verifica se existem
pacotes para receber. Caso verifique que não, retorna ao estado inativo. Caso verifique que
sim, envia um pacote ao ponto de acesso a pedir que lhe sejam transmitidos os pacotes em
espera. Deste modo, uma estação não necessita estar em modo ativo durante períodos em
que não hajam pacotes que lhe sejam destinados.
Este método de gestão de energia é utilizado em redes em modo infraestrutura. Considerando redes ad-hoc, o método anterior não poderá ser aplicado pela inexistência de
um nó centralizado. Por este motivo, o método de gestão de energia em redes ad-hoc
é diferente. No caso destas redes, todas as estações emitem pacotes beacon. O tempo é
dividido em intervalos de beacon, e cada intervalo de beacon é dividido em dois intervalos,
a janela ATIM (Announcement Traffic Indication Message Window) e a janela de dados. Se
uma estação pretender transmitir dados, é necessário emitir um pacote ATIM durante o
período de uma janela ATIM, para então estar autorizada a competir pela transmissão do
pacote durante o período da janela de dados. Caso contrário, se a estação não emitir um
pacote ATIM, durante o período de uma janela ATIM, entra em estado inativo durante o
período da janela de dados [32]. No caso de estações que se encontrem em modo inativo, é
necessário que a estação passa para modo ativo ao receber um pacote beacon, mantendo-se
em estado ativo durante o período da janela ATIM. Caso esta estação receba um pacote
ATIM, terá que se manter ativa, durante o período da janela de dados, para receber o
pacote que lhe é destinado.
2.1.5
Tipos de Pacotes
Face ao exposto anteriormente, o tráfego 802.11 consiste em três tipos de pacotes: pacotes
de dados, pacotes de gestão e pacotes de controlo. De seguida serão listados os sub-tipos
de pacotes presentes no tráfego de uma rede WiFi.
5 Figura
baseada em [41]
15
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
2.1.5.1
Pacotes de Dados
Estes pacotes transportam os dados da rede. Tipicamente, estes pacotes são provenientes
de outros protocolos (por exemplo IP, TCP, UDP, etc) e são encapsulados para que as
estações e pontos de acesso possam interpretar os pedidos que provêm destes pacotes. Os
pacotes de dados podem também ser aproveitados para fazer piggyback6 de outro tipo de
informação, como por exemplo, pacotes ACK.
Dados: pacote utilizado para enviar dados
CF-ACK: pacote de reconhecimento utilizado durante o período livre de contenção
CF-Poll: pacote de eleição utilizado durante o período livre de contenção
Dados+CF-ACK: pacote de dados com piggyback do pacote CF-ACK
Dados+CF-Poll: pacote de dados com piggyback do pacote CF-ACK
Dados+CF-ACK+CF-Poll: pacote de dados com piggyback dos pacotes CF-ACK e CF-Poll
CF-ACK+CF-Poll: pacote CF-ACK com piggyback do pacote CF-Poll
Função nula: pacote enviado pela estação para anunciar que entrará em modo de poupança de energia
2.1.5.2
Pacotes de Gestão
Os pacotes de gestão estão associados aos serviços de sistema de distribuição e de estação.
Estes pacotes são enviados quando uma estação se pretende associar, autenticar, dissociar,
reassociar ou terminar a autenticação. Dentro desta classificação encontram-se também os
pacotes que as estações e os pontos de acesso enviam para determinar a acessibilidade dos
nós e da rede (os pacotes beacon, por exemplo, são enviados esporadicamente pelos pontos
de acesso para anunciar às estações que se encontram ativos e acessíveis). Os subtipos dos
pacotes de gestão são:
Beacon: pacote enviado pelo ponto de acesso para anunciar a sua presença
Pedido de sondagem: pacote é enviado pelas estações que procuram os pontos de acesso
disponíveis
Resposta de sondagem: pacote é enviado pelos pontos de acesso após a receção de um
pedido de sondagem
Autenticação: pacote enviado quando uma estação pretende autenticar-se perante um
ponto de acesso
6 Mecanismo que tenta minimizar os pacotes enviados, acrescentando informação dos pacotes de reconhecimento, por exemplo, a pacotes de dados
16
2.2. MONITORIZAÇÃO
Revogação de Autenticação: pacote enviado para anunciar a terminação de autenticação
Pedido e Resposta de Associação: pacotes enviados durante o serviço de associação de
uma estação a um ponto de acesso
Pedido e Resposta de Reassociação: pacotes enviados durante o serviço de reassociação
de uma estação a um ponto de acesso
Dissociação: pacote enviado para anunciar a terminação da associação entre estações
Mensagem de anúncio da indicação de tráfego: pacote enviado durante o período da
janela ATIM, para indicar que a estação pretende enviar um pacote de dados.
2.1.5.3
Pacotes de Controlo
Estes pacotes são responsáveis pelo controlo de acesso ao meio, informando as estações e
os pontos de acesso quando é que podem, ou não, enviar informação. Os pacotes Request
to Send e Clear to Send, por exemplo, fazem parte do mecanismo de controlo de acesso ao
meio, RTS/CTS, já referido anteriormente na secção 2.1.3.3. Os subtipos dos pacotes de
controlo são:
RTS: pacote de pedido de envio
CTS: pacote de autorização de envio
ACK: pacote de reconhecimento
CF-End: pacote de terminação do período livre de contenção
CF-End+ACK: pacote CF-End com piggyback do pacote ACK
Power Save Poll: pacote enviado pela estação para pedir que lhe sejam transmitidos os
pacotes que ficaram em espera durante o período de poupança de energia
2.2
Monitorização
A monitorização da rede é baseada na escuta ou captura do tráfego de rede que circula no
meio de comunicação. Este método consiste em capturar os pacotes que são recebidos e
enviados pelo dispositivo que se pretende monitorizar, ou por outro que tenha acesso ao
meio e possa obter essa informação. Para explicar o processo de monitorização é preciso
explicar antes o que acontece no dispositivo quando este recebe um pacote. Quando
um dispositivo recebe um pacote ethernet, por exemplo, a placa de rede verifica se o
endereço MAC corresponde ao dispositivo, em caso positivo o pacote é encaminhado para
o controlador de rede.
A este ponto é preciso identificar os protocolos do pacote para este ser encaminhado
à camada de protocolos suportados pelo SO e suas aplicações. Para tal é preciso ter em
17
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
consideração que um pacote contém informação sobre os diversos protocolos a que se
rege. A figura 2.7 mostra o exemplo de um pacote TCP, assim para concluir que este é um
pacote TCP é necessário interpretar os diferentes cabeçalhos. Esta tarefa está encarregue
ao controlador de rede e pilha de protocolos. A partir do momento em que um pacote é
recebido pelo controlador de rede, os cabeçalhos são vistos um a um para identificar o
protocolo e encaminhar o pacote ao devido handler da pilha de protocolos. Este processo
acaba quando se consegue obter os dados do pacote e encaminhá-los à camada de aplicação
para que sejam devidamente processados ao nível do processo utilizador.
Cabeçalho
Ethernet
Cabeçalho
IP
Cabeçalho
TCP
Dados
Ethernet
Checksum
Figura 2.7: Estrutura de um pacote ethernet
Quando um programa de monitorização da rede se encontra a correr num dispositivo,
o controlador de rede, para além do processo antes descrito, transfere uma cópia dos
pacotes para um mecanismo de captura de pacotes. Em sistemas Unix, por exemplo, existe
um módulo no núcleo do sistema, chamado Packet Filter que aplica filtros na captura, como
exemplifica a figura 2.8. A biblioteca PCap [36], referida na secção 2.2.1, permite aceder
a estes mecanismos, em particular os mecanismos baseados no Berkeley Packet Filtering
(BPF) [24] ou suas variantes. Este mecanismo é o componente que permite controlar os
tipos de pacotes que são recolhidos durante a monitorização. Este componente torna-se
bastante importante em casos em que o administrador da rede não queira ver todos os
pacotes que estão a passar na rede e quer limitar-se, por exemplo, a visualizar pacotes
UDP, ou só os que envolvem determinado protocolo/porto. O Packet Filter permite assim
especificar filtros de captura, minimizando a quantidade de dados que passam do núcleo
para o nível de utilizador, que depois fará o processamento que acha necessário.
2.2.1
Biblioteca PCap
Os sistemas operativos oferecem um mecanismo de monitorização de tráfego, não sendo
necessário o uso de ferramentas externas para o mesmo. A biblioteca, de código aberto,
PCap [36] oferece uma interface de alto nível que permite aceder a este mecanismo
independentemente do sistema operativo usado.
Esta biblioteca foi criada com o intuito de haver uma abstração de alto nível que
permita ao programador aceder ao mecanismo de captura de pacotes, sem se preocupar
com as particularidades do sistema operativo. Existindo em diferentes versões para
Windows e Unix, WinPCap [38] e LibPCap [36], respetivamente. Esta ferramenta permite
assim a elaboração de um programa, numa linguagem de alto nível (C/C++), com o intuito
de capturar o tráfego da rede permitindo também a escolha de uma interface de rede,
7 Figura
baseada em [22]
18
2.3. FERRAMENTAS DE CAPTURA
Sniffer
Pacote
Recebido / Transmitido
Packet Filter
Monitor de Rede
Placa de Rede
Pacotes
Driver de Rede
Navegador
Pilha de Protocolo
Servidor FTP
Hardware
Núcleo de SO
Utilizador
Figura 2.8: Elementos envolvidos na captura de pacotes7
filtros de pacotes e modos de captura (os modos promíscuo e monitor são suportados pela
biblioteca).
Como mencionado anteriormente, o mecanismo de captura suporta diferentes filtros
para minimizar, logo à partida, a quantidade de dados que é passada do núcleo para o
nível de utilizador. Os filtros são definidos a alto nível e convertidos para filtros reconhecidos pelo núcleo do sistema. No caso do sistema Unix, como referido anteriormente, o
filtro reconhecido é o Berkeley Packet Filtering [24], existindo uma implementação para os
sistema Linux denominado Linux Socket Filtering (LSF). Contudo, caso seja definido um
filtro que não seja suportado diretamente pelo núcleo, a biblioteca PCap implementa o
filtro internamente, em nível utilizador, oferecendo ao utilizador/programador a mesma
interface, independentemente do sistema operativo.
Esta biblioteca permite também guardar as capturas em ficheiros, no formato pcap, de
modo a poderem ser consultadas a partir de programas de análise ou visualização gráfica,
como por exemplo Wireshark.
2.3
Ferramentas de Captura
As ferramentas baseadas na captura de tráfego podem operar de diferentes formas, consoante os seus objetivos, assim como as relações entre desempenho, uso de memória
e perturbação do sistema monitorizado. Para além do processo da captura de pacotes
anteriormente explicado, a monitorização de tráfego pode ser classificada como online,
offline, ativa e passiva.
Online. A visualização dos pacotes capturados é feita em tempo real, durante a monitorização.
Offline. A visualização e análise dos pacotes só é possível após a terminação da captura.
19
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
Activa. Permite que o utilizador altere os parâmetros e os filtros da monitorização enquanto esta se encontra a decorrer.
Passiva. A monitorização é levada a cabo sem qualquer intervenção no sistema, só sendo
possível visualizar os dados.
Independentemente do modo de funcionamento destas ferramentas, existem diferentes
modos de captura. Os modos de captura disponíveis dependem das interfaces de rede,
e respetivos controladores no núcleo do sistema. Estes modos definem o tipo e quais os
pacotes que a ferramenta consegue capturar. Considerando o foco desta dissertação em
redes 802.11, é necessário considerar a particularidade dos pacotes deste protocolo terem
cabeçalhos específicos. Dependendo do modo de captura, poderá ser possível visualizar e
analisar, ou não, os cabeçalhos do protocolo 802.11. Para estes pacotes existem dois modos
de processamento, ou são processados e traduzidos para falsos pacotes ethernet, ignorando
a informação do protocolo 802.11, ou podem conter os cabeçalhos específicos do protocolo.
Estes cabeçalhos contêm, por exemplo, informação referente ao tipo de pacote 802.11
(gestão, controlo ou dados), tal como informação de nível rádio, como a força do sinal da
rede ou o canal em que está a decorrer a transmissão.
Modo Promíscuo. O modo promíscuo permite que o programa capture todos os pacotes
que chegam ao controlador do dispositivo, mesmo que os pacotes não sejam destinados ao mesmo. Este modo permite assim apanhar todos os pacotes que estão a passar
na rede. No contexto de redes sem fios, este modo de captura só permite capturar os
pacotes a partir do momento em que o dispositivo se encontra autenticado perante
um ponto de acesso. Os pacotes 802.11 capturados neste modo serão traduzidos
para falsos pacotes ethernet.
Modo Monitor. Este modo de captura permite que o dispositivo apanhe o tráfego de
todos os pontos de acesso que estiverem a transmitir no canal. A particularidade do
modo monitor é que o dispositivo não necessita estar associado e autenticado a um
ponto de acesso ou rede ad-hoc. Quando este modo se encontra ativo, o dispositivo é
dissociado do ponto de acesso. Se o dispositivo só possuir um adaptador de rede,
este modo impossibilita o dispositivo de comunicar em rede e só permite a receção
de pacotes para que estes sejam passados ao programa de monitorização. Caso o
dispositivo possua mais que um adaptador de rede, consegue comunicar com os
restantes nós através do adaptador de rede adicional. O modo monitor só pode
ser ativado em redes sem fios e permite a captura de cabeçalhos rádio. Este modo
é assim o mais indicado no contexto desta dissertação, sendo a única maneira de
capturar dados do protocolo 802.11.
Existem inúmeras ferramentas de monitorização de tráfego de rede, na sua maioria
baseadas na biblioteca PCap, contudo, existem duas que merecem algum destaque sendo
20
2.3. FERRAMENTAS DE CAPTURA
elas Wireshark e TCPDump [36], a seguir descritas. Serão também referidos alguns trabalhos antes realizados no Departamento de Informática com base nestas ferramentas e
biblioteca.
2.3.1
TCPDump
TCPDump [36] é uma ferramenta de monitorização de rede executada através da linha
de comandos do sistema Unix, ou Windows. No caso do sistema Windows, a versão da
ferramenta chama-se WinDump [37]. Esta ferramenta utiliza a biblioteca LibPCap para
captura de tráfego e permite a aplicação de diversos tipos de filtros. É possível visualizar
os resultados no terminal ou guardá-los em ficheiro.
O TCPDump serve como base e referência para muitos outros sistemas de monitorização e análise de tráfego [35], como por exemplo: capinfo, tcpstat, tcptrace, etc. A ferramenta
Wireshark, explicada na secção 2.3.2, permite a obtenção de estatísticas do tráfego e tem
como base o TCPDump.
2.3.2
Wireshark
Wireshark [39] é uma ferramenta de monitorização passiva de tráfego que permite capturar,
visualizar e analisar os pacotes de que passam por uma dada interface de rede. Sendo
uma ferramenta de código aberto, permite expandir as suas funcionalidades através do
desenvolvimento de plug-ins e extensões.
Para a monitorização da rede, o programa apresenta as diversas interfaces de rede
existentes no dispositivo, para que o utilizador possa indicar qual usar. Após a escolha
da interface de rede, o utilizador tem diversas opções ao seu dispor, como, por exemplo,
filtros de captura, modos de captura e tipos de cabeçalhos que pretende visualizar. Durante
a monitorização é apresentada uma lista, que mostra a captura de pacotes em tempo real
(modo online), e que para pacote mostra a informação da Tabela 2.1.
No Sequência
Tempo
Origem
Destino
Protocolo
Tamanho
Informação
Tabela 2.1: Tipo de informação apresentada sobre cada pacote
Ao aceder à informação de cada pacote é possível aceder aos campos que estão nos
vários cabeçalhos do pacote (por exemplo, IP - IPv4 - TCP - HTTP). A ferramenta faz a
interpretação dos pacotes de modo a, à medida que são apresentados, indicar o protocolo a
que estes correspondem e fornece vários tipos de visualização de estatísticas e informações
sumárias da captura num todo. Através desta ferramenta é possível fazer capturas tanto
em modo promíscuo como em modo monitor, com o pormenor de que esta capacidade
estará dependente do adaptador de rede do dispositivo.
21
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
2.3.3
Wireshark para Sistemas Distribuídos
O trabalho de Farruca [7] focou-se na monitorização de sistemas distribuídos, isto é,
na monitorização dos processos que se encontram a executar nos computadores que
constituem o sistema distribuído. Considerando o Wireshark, esta ferramenta atualmente
não permite filtrar o tráfego de rede por aplicação, nem de capturar o tráfego a partir de
diversos computadores. Assim, a principal motivação deste trabalho foi contribuir com
uma ferramenta que permita monitorizar uma aplicação distribuída em concreto.
Para tal, este trabalho recorreu à biblioteca PCap, igualmente utilizada pelo Wireshark,
para captura do tráfego. De modo a monitorizar o tráfego do processo, o mesmo é identificado para que o seu descritivo seja usado para obter os sockets em uso. É assim possível
criar um filtro para a ferramenta PCap, com base nas portas usadas pelo processo. De
modo a que a captura não necessite de ser iniciada manualmente em cada computador, um
a um, o processo de monitorização é iniciado num computador que, ao detetar o processo
a ser monitorizado, consegue detetar os computadores que se encontram a comunicar
com este, e propagar o processo de monitorização por todos os intervenientes do sistema
distribuído.
Após a monitorização de todos os processos estar concluída, existe um elemento
central que recolhe os resultados de cada monitorização para elaborar o relatório final. Este
relatório apresenta os pacotes que passaram na rede durante a monitorização, devidamente
ordenados, dando a possibilidade de filtrá-los e ainda de mostrar o grafo do sistema
distribuído.
2.3.4
Monitorização de tráfego de rede de um processo com base no PCap
O trabalho de Farruca [7] recorre à monitorização de processos de modo a garantir a
captura do tráfego gerado por uma aplicação distribuída. Contudo, o resultado produzido
faz uso de filtros a nível do utilizador para identificar e filtrar o tráfego da aplicação,
aumentando a carga do programa de captura. O trabalho de Martins [23] focou-se na
otimização da monitorização do tráfego de rede de somente um processo.
Tendo em conta os objetivos deste trabalho, pretende-se assim em utilizar mecanismos
internos ao núcleo do sistema para monitorizar e filtrar o tráfego gerado por um processo
sem causar perturbações no sistema. Ao focar a monitorização para o tráfego gerado por
um programa e ao centrar a análise desse tráfego no núcleo do sistema, este trabalho
pretende simplificar o processo de filtragem do tráfego e minimizar o conhecimento
necessário sobre a aplicação para levar a cabo a mesma.
A implementação deste trabalho focou-se no desenvolvimento de um módulo do
núcleo que fosse uma extensão do Linux Socket Filtering, uma implementação do Berkeley
Socket Filter referido anteriormente. O módulo desenvolvido acrescenta a opção de monitorizar o tráfego gerado por um processo e, o facto deste módulo ter sido implementado a
nível do núcleo, permite que qualquer aplicação possa ser monitorizada sem alterações
ao seu código. O facto deste módulo ser uma extensão do LSF permite também que as
22
2.3. FERRAMENTAS DE CAPTURA
ferramentas de monitorização baseadas no LipPcap possam beneficiar deste módulo.
Deste modo, foi possível desenvolver uma solução que permitisse a captura do tráfego
gerado por um processo e, pelo facto desta monitorização ser levada a cabo a nível do
núcleo, não se observam perturbações no sistema nem na aplicação a ser analisada.
2.3.5
Conclusões
Face aos objetivos expostos na secção 1.2, as ferramentas anteriormente apresentadas
foram alvo de estudo.
Na secção 2.3.2 é apresentado o Wireshark, uma ferramenta de monitorização de rede
que possibilita a captura de pacotes 802.11 e a visualização de pacotes de dados, gestão e
de controlo. Esta ferramenta permite assim distinguir os diferentes tipos de pacotes, desencapsular os pacotes de dados e apresentar os diferentes protocolos que destes fazem parte.
No entanto, não possibilita a distinção do tráfego gerado pelo algoritmo, impossibilitando
a análise do tráfego útil para a avaliação do funcionamento e desempenho do algoritmo
distribuído. Esta ferramenta também não permite uma clara análise da utilização da rede
pelo algoritmo ou pelos vários tipos de pacotes WiFi. Tal como não permite identificar
fenómenos de congestionamento ou interferências que estejam a reduzir o desempenho
da rede.
O trabalho de Farruca, “Wireshark para Sistemas Distribuídos”, [7] é apresentado na
secção 2.3.3. Esta ferramenta, baseada no Wireshark para colmatar as suas limitações,
permite monitorizar um sistema distribuído. Isto é, esta ferramenta é capaz de distinguir e filtrar o tráfego gerado por uma aplicação distribuída e, correndo instâncias das
ferramentas em todos os nós, capturar as interações que ocorrem durante a execução
da mesma. No entanto, a solução implementada causa perturbações no sistema onde
decorre a monitorização e, no contexto desta dissertação, não captura pacotes específicos
do protocolo 802.11, sendo incapaz de distinguir, perante o tráfego de uma rede WiFi, os
tipos de pacotes que estão a ser transmitidos na rede.
Na secção 2.3.4 é apresentado o trabalho de Martins, “Monitorização de tráfego de
rede de um processo com base no PCap” [23] que por sua vez foca-se em colmatar as
limitações do trabalho de Farruca, mitigando as perturbações que a monitorização de
um processo pode causar no sistema. Este trabalho foca-se somente nesta problemática,
como tal não oferece meios automatizados de monitorizar todos os nós que executam a
aplicação distribuída, e assim obter as interações que ocorrem durante a execução desta.
Esta ferramenta limita-se a identificar o tráfego de um processo, não ajudando na captura
de outro tráfego (WiFi ou outro) nem na identificação dos problemas já apresentados que
ocorram durante o funcionamento de uma aplicação distribuída.
Nota-se, mais uma vez, uma lacuna nas ferramentas desta índole e no modo como
lidam com o tráfego 802.11, que, como referido por Schulman et al. [31], tem problemáticas
inexistentes na monitorização de tráfego 802.3 (por exemplo). A acrescentar a estes desafios,
não existem ferramentas que possibilitem a monitorização e distinção de tráfego de uma
23
CAPÍTULO 2. MONITORIZAÇÃO DE REDES
aplicação distribuída da do restante tráfego da rede. Este facto dificulta a avaliação e
depuração do funcionamento e desempenho de um algoritmo distribuído, aliado à falta
de um regime de estudo controlado, não existem métodos a que o programador possa
recorrer durante o desenho, ou avaliação do funcionamento, de um algoritmo ou aplicação
distribuídos.
24
CAPÍTULO
3
A LGORITMOS DE C ONSENSO
Este capítulo abordará conceitos para a compreensão de algoritmos de consenso, seguidos
de alguns algoritmos de exemplo. A secção 3.1 apresenta os conceitos necessários para a
compreensão de algoritmos de consenso. De seguida a secção 3.2 apresenta o algoritmo
de referência Paxos. As secções 3.4 e 3.3 apresentam os algoritmos utilizados no trabalho
de motivação a esta dissertação.
3.1
Definição
“Algoritmos distribuídos são algoritmos desenhados para correr em vários processadores ligados entre si. Partes de um algoritmo distribuído correm concorrente
e independentemente, cada uma com uma quantidade de dados limitada. Os algoritmos são supostos correr corretamente, mesmo que um dos processadores ou canais de
comunicação operem em velocidade diferentes e até em caso de falha.” [21]
Um algoritmo de consenso é um algoritmo distribuído que visa resolver o problema
de consenso. Esta classe de algoritmos serve de base à resolução de muitos dos problemas
específicos dos ambientes distribuídos, como, por exemplo, a eleição de processos líder,
coordenação entre os processos, sincronização, etc. O problema de consenso requer que
processos distribuídos cheguem a acordo quanto a um determinado valor. Para tal, este
problema requer que sejam cumpridas as seguintes propriedades:
Validade. Se todos os processos propõem um valor v, então v será o valor acordado.
Acordo. Dois processos corretos não podem decidir valores diferentes.
Terminação. Todos os processos corretos decidem eventualmente1 um valor.
1 Do
inglês eventually, que implica que irá acontecer algures no tempo
25
CAPÍTULO 3. ALGORITMOS DE CONSENSO
Integridade. Se um processo correto decide v, então v foi a proposta inicial de algum
processo.
O algoritmo de consenso começa com a proposta de valores dos processos, sendo, no
final, acordado um desses valores propostos. Considera-se que se chegou a um consenso
quando um quórum de processos decide o mesmo valor, sendo o quórum (n/2) + 1, em n
processos. Durante este processo é necessário tolerar a falha de processos, podendo estes
falhar por paragem ou por serem corrompidos. Existindo assim dois tipos de falhas:
Falhas por Paragem. Denominam-se falhas por paragem, os casos em que um processo
deixa de executar, cessando todas as suas operações.
Falhas Bizantinas. Consideram-se falhas bizantinas quando um processo toma um comportamento inesperado. Este comportamento pode passar por enviar mensagens
erradas, incompletas, a enviar informação diferente a processos diferentes ou processos a deixar de responder temporariamente (simulando uma falha por paragem).
Este tipo de falhas são mais difíceis de detetar. Neste contexto, só é possível chegar a
um consenso quando se limitam a f falhas bizantinas, com f < n3 .
O funcionamento do algoritmo altera também consoante o modelo temporal que
assume. Os tipos de sincronismo que se podem considerar em algoritmos de consenso são:
Síncrono. Assume-se um modelo síncrono quando a interação ocorre num intervalo de
tempo limitado, sendo o envio e a receção bloqueantes.
Assíncrono. Assume-se um modelo assíncrono quando não se conseguem assumir limites
de tempo na interação, não podendo o envio e a receção bloquear o processo, sob
pena de nunca se conseguir desbloquear.
O tipo de falhas que o algoritmo tolera terá impacto no funcionamento do mesmo [27]
[19], alterando as especificações necessárias para calcular o quórum do consenso.
Existem diversos algoritmos de consenso consoante os modelos de falhas e sincronismo. Existem protocolos deterministas (Paxos [17], por exemplo) que são os protocolos
considerados previsíveis, em que valores de entrada iguais geram sempre os mesmos
valores de saída, e que permitem assumir um tempo limite para a sua terminação. Existem
também protocolos probabilísticos, que recorrem a processos estocásticos, tornando-se
em algoritmos imprevisíveis. Neste caso os valores de saída nem sempre são os mesmos
para valores de entrada iguais e, em oposição aos algoritmos deterministas, não permitem
assumir tempo limite para a sua terminação.
O algoritmo Turquois [25], explicado na secção 3.3 é considerado um algoritmo probabilístico.
26
3.2. PAXOS
3.2
Paxos
Paxos [17] é um algoritmo de consenso assíncrono com modelo de falhas por paragem.
Neste algoritmo os processos são classificados em três agentes a) proposers b) acceptors e
c) learners , podendo um processo assumir o papel dos três agentes. O algoritmo executa
em vários rondas em que cada ronda é dividida por duas fases. A figura 3.1 ilustra a
execução correta do algoritmo Paxos.
Fase 1a: Preparação O proposer, cria uma proposta identificada por um número n. Este
valor n terá que ser maior do que qualquer outro número de proposta por este
proposer. De seguida, o proposer envia uma mensagem do tipo prepare, contendo o
valor proposto, para um quórum de acceptors. O proposer é quem decide que acceptors
constituem o quórum.
Fase 1b: Promessa O acceptor, ao receber uma mensagem do tipo prepare, verifica se o
valor n é o maior valor que já recebeu de qualquer proposer. Se o valor for o mais
elevado até à data recebido, o acceptor envia uma promessa de que irá ignorar
propostas futuras que sejam menores que o valor n recebido. Se o acceptor já tiver
aceite um valor anteriormente, terá que enviar o valor da proposta e o número
correspondente à proposta na mensagem de promessa. Caso o valor n não seja o
mais elevado recebido até à data, a mensagem de prepare é ignorada.
Fase 2a: Aceitação Pedido Após o proposer receber um quórum de mensagens de promessa, necessita definir um valor de proposta. Se, até à data, qualquer acceptor tiver
aceite uma proposta, o proposer terá recebido os valor aceites anteriormente pelos
acceptors, tendo que definir o valor da sua proposta como o maior valor aceite pelos
acceptors. Se nenhum dos acceptors tiver aceite um valor anteriormente, o proposer
pode definir qualquer valor de proposta. Após definir o valor de proposta, o proposer
envia uma mensagem to tipo accept request para um quórum de acceptor, que contém
o valor da sua proposta.
Fase 2b: Aceitação Se um acceptor receber uma mensagem to tipo accept request para uma
proposta n, o acceptor aceita a proposta somente se não tiver prometido considerar
apenas propostas de número maior que n. Neste caso, o acceptor regista o valor v da
proposta e envia uma mensagem to tipo accept ao proposer e a todos os learners. Caso
contrário ignora a mensagem accept request.
Este algoritmo original de Paxos serve como base para diversas variantes, como por
exemplo a versão Byzantine Paxos [18] que assume um modelo de falhas bizantinas.
3.3
Turquois
Turquois [25] é um protocolo de consenso binário e probabilístico desenhado para redes
ad-hoc sem fios com modelo de falhas bizantinas. Este protocolo permite que k, de n
27
CAPÍTULO 3. ALGORITMOS DE CONSENSO
Proposer
Acceptor
Acceptor
Acceptor
prepare(n)
promise(n, v1)
accept
request(n, v2)
accept(n)
Figura 3.1: Execução correta do algoritmo Paxos
processos, sendo k ⊆ n, decidam um valor v, sendo v ∈ {0, 1} ou ⊥, caso não cheguem a
um consenso. O estado inicial de um processo é composto por três variáveis internas:
1. Fase φi ≥ 1.
2. Valor proposto vi ∈ {0, 1}.
3. Estado da decisão statusi ∈ {decided, undecided}.
No início do protocolo, as variáveis internas encontram-se com os seguintes valores:
φi = 1, statusi = undecided e vi = proposali . O algoritmo encontra-se dividido em duas
tarefas que são executadas em paralelo por cada processo, sendo elas:
Receção. Esta tarefa recebe as mensagens, do formato hi, φi , vi , statusi i de todos os restantes processos. É esta tarefa que está encarregue de validar e processar a mensagem
consoante a fase em que o ciclo se encontra.
Emissão. Esta tarefa envia as mensagens broadcast com o formato hi, φi , vi , statusi i aos
restantes processos. Estas mensagens são enviadas periodicamente, sendo a tarefa
ativa por um relógio interno.
Como referido, a tarefa de receção dos pacotes é responsável por processar a mensagem
consoante a fase em que o ciclo se encontra. Isto deve-se ao facto deste protocolo de
consenso funcionar em ciclos, em que cada ciclo está dividido em três fases:
CONVERGE. Fase em que os processos tentam convergir para o valor mais observado
entre todos os processos, (φi mod 3 = 1).
28
3.4. CONSENSO MULTI-VALOR
LOCK. Fase em que os processos tentam bloquear um valor vi ∈ {0, 1} ou ⊥, se não
conseguirem decidir, (φi mod 3 = 2).
DECIDE. Fase em que os processos tentam decidem o valor que foi bloqueado na fase
anterior, (φi mod 3 = 0).
Caso os processos não consigam decidir um valor, começa um novo ciclo em que cada
processo propõe valores aleatórios.
Devido ao modelo de falhas bizantinas, este protocolo necessita validar as mensagens
que são recebidas. Esta validação de mensagens é feita através da validação de autenticidade e de semântica das mensagens. Para a validação de autenticidade, é necessária a
troca de chaves entre os intervenientes do algoritmo, para que, na receção de uma mensagem, esta possa ser devidamente autenticada de modo a validar a origem da mensagem.
A validação da semântica das mensagens é levada a cabo para garantir que os dados
recebidos estão congruentes com o estado do algoritmo.
3.4
Consenso Multi-Valor
O trabalho de motivação desta dissertação [1], baseou-se num protocolo de consenso multi
valor, com modelo de falhas bizantino e assíncrono, denominado Multi-Valued Consensus
[34]. Este algoritmo, por sua vez, necessita de recorrer a um algoritmo de consenso binário,
tendo sido, neste âmbito, escolhido o algoritmo Turquois [25].
O protocolo executa em três fases distintas: proposta de um valor, deteção do valor
mais votado e decisão do valor.
O protocolo começa com todos os processos a proporem um valor v através de mensagens com o formato hINIT, i, vi i, sendo i o identificador do processo e vi o seu valor
proposto. Cada processo guarda as mensagens INIT recebidas num vetor V, na posição
i e espera até receber (n − f ) mensagens, sendo n o total de processos e f o número de
falhas admissíveis. Quando um processo recebe (n − 2 f ) mensagens com o mesmo valor
v, envia uma mensagem do formato hVECT, i, vi a todos os restantes processos. Caso o
processo não consiga decidir um valor v, envia um valor ⊥.
A dada altura todos os processos terão difundido mensagens do tipo hVECT, i, vi,
assim, um processo espera até receber (n − f ) mensagens VECT. Quando são recebidas
(n − 2 f ) mensagens VECT com o mesmo valor v proposto, o processo inicia o consenso
binário propondo o valor 1, para que todos os processos se possam decidir pelo valor v. O
valor v só é aceite quando o protocolo de consenso binário decidir 1, caso contrário o valor
decidido, pelo consenso multi-valor, é ⊥.
29
CAPÍTULO 3. ALGORITMOS DE CONSENSO
3.5
Análise do sistema
O trabalho de Almeida [1] atravessou algumas dificuldades no estudo da solução implementada. No processo de avaliação da solução, foram feitos diversos testes, nomeadamente à latência da rede. Estes testes tiveram em consideração diferentes números
de nós da rede (4, 7, 10 e 13), protocolos de comunicação (TCP, TCP persistente, UDP e
UDP multicast), presença de falhas e algumas parametrizações adicionais. Os testes de
latência foram feitos com temporizadores em cada nó que no fim da execução do protocolo
retornam o tempo total calculado.
No contexto das parametrizações adicionais, foram considerados vários intervalos
e tempos de espera. Um dos parâmetros considerados, por exemplo, foi o intervalo de
tempo entre o envio de mensagens. Este intervalo pode ser malicioso se assumir um
valor demasiado baixo, podendo congestionar a rede e levar à perda de pacotes e ao
aumento da latência da rede. O aumento da latência da rede poderá levar ao aumento de
falhas, dificultando o consenso entre os processos. Por outro lado, caso o valor assumido
seja muito alto, este pode atrasar a execução do protocolo. Os ajustes a estes parâmetros
foram feitos por experimentação, não havendo um controlo e conhecimento total do
comportamento do protocolo de modo a se conseguir calcular parâmetros favoráveis.
Este pormenor leva a uma das questões levantadas na avaliação deste trabalho, será
que os intervalos e tempos de espera utilizados podem ser relaxados e mesmo assim obter
bons tempos de latência? Esta será uma questão que só poderá ser respondida através
da monitorização detalhada e controlada da rede durante a execução do protocolo, ao
contrário do método por tentativa e erro.
A avaliação feita com diferentes números de nós começou com uma rede mais pequena,
de 4 nós, até chegar a uma rede de 13 nós. No caso de uma rede de 13 nós o protocolo
de consenso mostrou ser bastante instável. A execução do mesmo tornava-se demorada,
causando até a falha de todo o sistema. Foi colocada em questão a combinação de hardware
e rede usados. No entanto, não é percetível se o problema se prende com o facto do
protocolo não ser escalável ou se está presente no tipo de dispositivos utilizados. Uma
possível causa deste problema é o intervalo de tempo já referido anteriormente. O mesmo
intervalo de tempo terá um impacto diferente à medida que se aumenta o tamanho da rede.
Isto porque, proporcionalmente ao tamanho da rede, o número de mensagens trocadas
aumenta. Assim, um tempo favorável para uma rede de 4 nós poderá ser demasiado baixo
para uma rede de 13 nós, estando a congestionar o tráfego da rede. No entanto, a dúvida
mantém-se sem resposta. Não havendo metodologias e ferramentas destinadas a perceber
o que está a acontecer na rede para causar esta instabilidade.
As metodologias de avaliação usadas mostram que existe uma lacuna, não só, nas ferramentas de depuração e gestão de aplicações distribuídas, mas como na falta de métodos
controlados de análise da rede. Pelos problemas indicados, nota-se a necessidade de haver
um sistema que favoreça a monitorização do tráfego gerado por um sistema distribuído,
sem perturbar o mesmo, de modo a compreender melhor o seu comportamento, e perceber
30
3.5. ANÁLISE DO SISTEMA
se o protocolo a ser desenvolvido tem impacto positivo ou negativo no desempenho da
rede.
31
CAPÍTULO
4
S ISTEMA DE A NÁLISE
Este capítulo abordará o sistema implementado no contexto desta dissertação. Na secção
4.1 serão apresentados os requisitos necessários para a implementação do sistema. Nas
secções 4.2, 4.3 e 4.4 serão explicados os diferentes componentes que cumprem os requisitos
do sistema.
4.1
Requisitos
Para prosseguir com a implementação de um sistema de monitorização, de um algoritmo
distribuído a executar numa rede WiFi, é necessário fazer o levantamento dos requisitos
deste mesmo sistema. Após a análise dos objetivos pretendidos e as particularidades da
norma 802.11, foram definidos os seguintes requisitos:
Captura sem interferências. Com o objetivo de obter resultados reais e fidedignos é
necessário que a captura de tráfego não interfira na rede e/ou nos dispositivos
intervenientes.
Classificação de tráfego. De modo a ser possível analisar o tráfego de um algoritmo
específico é essencial fazer a classificação do tráfego, distinguindo a origem do
tráfego e o seu impacto na rede. Este sistema precisa assim de ser capaz de identificar
os diferentes tipos de tráfego:
• Pacotes de Gestão, secção 2.1.5.2
• Pacotes de Controlo, secção 2.1.5.3
• Pacotes de Dados, secção 2.1.5.1
• Pacotes desconhecidos
33
CAPÍTULO 4. SISTEMA DE ANÁLISE
Considerando os pacotes de dados, é ainda possível separar em duas sub-categorias:
tráfego da aplicação e tráfego extra. Os pacotes desconhecidos constituem pacotes
mal formados que não permitem identificar a sua origem.
Modo monitor. Para que o requisito anterior seja possível, é necessário que a captura de
tráfego seja efetuada em modo monitor. Só neste modo é que será possível obter
todo o tráfego da rede, incluindo pacotes do protocolo 802.11.
Análise da evolução. Para uma melhor compreensão do algoritmo, é necessário ter uma
visualização da sua evolução ao longo do tempo. Deste modo, poderá ser possível
identificar períodos de maior congestionamento ou falhas do sistema.
Agregação de informação. Considerando que o meio WiFi não é estável, é de esperar que
a execução de um algoritmo distribuído neste meio não seja estável e previsível.
Como tal, é necessário processar a informação de várias capturas de modo a agregar
a informação e obter dados estatísticos.
De modo a cumprir estes requisitos, o sistema terá que contar com três componentes distintos. O sistema será assim dividido por captura, análise e visualização. Estes
componentes serão explicados de seguida.
4.2
Captura
Este componente é responsável por cumprir dois dos requisitos enumerados: captura
sem interferências e captura com modo monitor. Como existem programas de captura
de tráfego simples e eficientes, não existe a necessidade de implementar de raiz este
componente. Tendo como objetivo agregar diversas capturas, pretende-se utilizar um
programa de captura já existente. A título de experimentação, a primeira opção foi o uso
da ferramenta Wireshark [39].
Primeiramente, o processo de captura passou por executar a ferramenta Wireshark em
simultâneo com o tráfego em estudo. No entanto, após alguma análise dos resultados obtidos, concluiu-se que desta forma se perturba e altera os resultados obtidos. Considerando
que esta ferramenta necessita processar cada pacote que captura, este processamento
introduz um atraso no atendimento dos pacotes que chegam ao Packet Filter. Caso a ferramenta não consiga processar pacotes ao mesmo ritmo com que estes passam na rede, os
resultados apresentados na captura não serão representativos do que realmente se passa
na rede. Esta situação observou-se em execuções mais rápidas do algoritmo, em que, no
ficheiro resultante da captura, não eram apresentados pacotes gerados pelo algoritmo.
Assim sendo, como substituto da ferramenta Wireshark, passou-se a utilizar TCPDump
[36], com a particularidade de colocar o processo a executar em segundo plano e sem
geração de output em tempo real. Deste modo minimiza-se o processamento de pacotes,
limitando a ferramenta a capturar e guardar a informação dos mesmos.
34
4.3. ANÁLISE DE TRÁFEGO
Uma das particularidades do modo monitor é que o dispositivo dissocia-se do ponto
de acesso no momento da captura. Assim, este modo não permite comunicações com a
rede, caso o dispositivo não tenha adaptadores de rede adicionais.
Mesmo que o dispositivo de captura seja capaz de monitorizar e produzir tráfego
em simultâneo, é importante considerar que tal poderá prejudicar as condições tanto
da captura, como da execução do algoritmo. Isto porque o overhead introduzido pelo
processamento de pacotes para o algoritmo pode prejudicar o processamento de pacotes
da captura, e vice-versa. Estes factos levam à escolha de manter um nó monitor externo à
execução do algoritmo. Considerando o exemplo da figura 4.1, com um algoritmo a correr
entre os nós A, B e C, a captura do tráfego é efetuada num quarto nó D.
Ponto de Acesso
Estação A
Estação C
Estação
Monitora D
Estação B
Figura 4.1: Arquitetura da rede
Em suma, este componente limita-se à utilização da ferramenta TCPDump e da produção de um ficheiro pcap. A captura de tráfego executa-se, em modo monitor, através de
um computador externo, que não intervém no algoritmo a estudar.
4.3
Análise de Tráfego
Este componente é responsável por processar os resultados da captura de tráfego e produzir os dados que são consumidos pelo componente de visualização. Este componente é
assim responsável por cumprir o requisito de classificação de tráfego e parte dos requisitos
análise da evolução e agregação de informação.
A implementação deste componente recorre à utilização da biblioteca Pcap [36], mais
concretamente a versão LibPcap [36], com uso da linguagem de programação C. Na
prática este componente divide-se em dois programas que, consumindo a mesma captura,
originam tipos de dados diferentes.
4.3.1
Classificação de Tráfego
Este programa é o que permite fazer a distinção dos tipos de pacotes que ocorrem na
rede sem fios. A nível da classificação dos tipos de pacotes (gestão, controlo e dados), esta
informação encontra-se disponível no cabeçalho 802.11. De modo a poder caracterizar
35
CAPÍTULO 4. SISTEMA DE ANÁLISE
o tráfego da aplicação é necessário introduzir quais os endereços IP intervenientes no
algoritmo. E, caso sejam conhecidas, é possível limitar mais os resultados, indicando as
portas utilizadas pelo algoritmo. Assim, se o utilizador definir que pretende analisar o
tráfego entre as máquinas 192.168.1.100, 192.168.1.101 e 192.168.1.102, é considerado pacote
da aplicação qualquer pacote que tenha como origem e destino dois destes endereços
IP. Considerando que estas três máquinas poderão comunicar entre si, fora da execução
do algoritmo, o tráfego útil da aplicação pode ser filtrado através das portas utilizadas.
Utilizando o exemplo da figura 4.2, limitar a classificação de tráfego aos endereços IP
levaria a que os pacotes do protocolo ICMP fossem classificados como tráfego útil. Existe
assim a possibilidade de introduzir um conjunto de portas para restringir o filtro de
pacotes. Os restantes pacotes de dados são classificados como tráfego extra.
mp
te ic
2345
paco
rta 1
, po
p
d
te u
paco
34
rta
p,
pa
12
co
rta
te
po
ud
p,
pa
ud
po
te
co
te
co
pa
icm
p
12
34
5
192.168.1.100
192.168.1.101
5
192.168.1.102
Figura 4.2: Exemplo de tráfego de rede
De modo a cumprir o requisito de análise da evolução, é guardado o estado da rede de
tempos a tempos. Numa captura de dez segundos, por exemplo, se o utilizador pedir uma
análise de 200 em 200 milissegundos, é guardado o número de pacotes e o total de bytes
das mensagens para cada intervalo de tempo. Após o processamento, é produzido um
ficheiro no formato csv que contém a evolução dos tipos de tráfego ao longo do tempo.
4.3.2
Informação sumária
Este programa é em parte responsável pelo requisito de agregação de informação. O
processamento dos pacotes é semelhante ao do programa anterior. Neste caso a classificação de tráfego é simplificada, limitando a distinguir tráfego da aplicação e tráfego extra.
No entanto, ao contrário da implementação anterior, este programa acumula os dados,
apresentando no final um sumário das condições da rede. Os resultados são, mais uma
vez, disponibilizados em formato csv. Neste caso, são produzidos dois ficheiros, separando
a informação do tráfego da aplicação e do tráfego extra. A informação apresentada em
ambos é a seguinte:
• Tempo de execução
36
4.4. VISUALIZAÇÃO
• Número de pacotes
• Número de bytes
• Número de pacotes/segundo
• Número de bytes/segundo
4.4
Visualização
Este componente é responsável por parte dos requisitos de análise da evolução do algoritmo e agregação de informação. Como já referido, este componente consome os
resultados produzidos pelo componente anterior. Para o utilizador gerir as capturas que
pretende analisar e visualizar, é necessário que o sistema disponibilize uma interface
gráfica. De seguida são apresentadas as duas versões da interface gráfica que foram
implementadas.
4.4.1
Versão Java
Inicialmente, foi escolhida a linguagem de programação Java [13] para a implementação
desta interface gráfica. Esta implementação foi feita com recurso ao pacote Java Swing [14]
e à biblioteca XChart [40]. A base desta implementação passa por receber um ficheiro pcap
ou csv e os devidos parâmetros: endereços IP, portas (opcional) e intervalo de tempo (em
milissegundos). Caso o ficheiro introduzido tenha sido em formato pcap, os parâmetros são
usados para executar o programa de classificação de tráfego. Este programa de classificação
produz um ficheiro csv que é processado posteriormente para gerar um gráfico. Caso seja
introduzido um ficheiro csv, não é necessário executar o programa de classificação de
tráfego, sendo possível passar diretamente à produção do gráfico. O utilizador pode então
escolher que informação que pretende visualizar, assim como o tipo de gráfico que prefere
usar. A figura 4.3 mostra a primeira versão da interface gráfica, implementada em Java.
4.4.2
Versão Web
Durante a implementação da versão Java, houve algumas dificuldades em acrescentar
interatividade aos gráficos. Chegando à conclusão que, para acrescentar funcionalidades
aos gráficos, teria que ser despendido muito tempo, optou-se por procurar uma alternativa.
Considerando a familiaridade com as tecnologias, e a vasta oferta de bibliotecas de geração
de gráficos, optou-se por procurar uma alternativa web em Javascript [15]. Tomou-se assim
conhecimento da biblioteca CanvasJS [4] que oferece uma API com as funcionalidades
pretendidas. Alterando a interface gráfica para uma implementação web, é necessária
a implementação de um servidor, sendo escolhida a linguagem Ruby [29], com uso da
framework Ruby on Rails [30]. De modo a agilizar a criação da interface gráfica, foi usada a
framework Bootstrap [2]. Em suma, a versão web é constituída por uma parte de servidor,
37
CAPÍTULO 4. SISTEMA DE ANÁLISE
(a) Ecrã inicial
(b) Opções do gráfico
(c) Gráfico
Figura 4.3: Versão Java
implementada em Ruby on Rails, e por uma parte de cliente, implementada em HTML5
[10], CSS [5] e Javascript com recurso à framework Bootstrap e à biblioteca CanvasJS.
Esta alteração permitiu assim criar uma alternativa à versão Java, em menos tempo de
implementação, acrescentando algumas características interessantes aos gráficos:
• Zoom
• Interatividade com o gráfico, obtendo os valores dos pontos
• Exportação para imagem JPG/PNG
• Ativação/desativação de conjuntos de dados
Considerando a versão anterior, o mesmo ficheiro (pcap ou csv) era processado de todas
as vezes que era submetido. Com recurso a uma base de dados, a versão web guarda os
resultados da captura, aquando da primeira submissão do ficheiro. Deste modo é mantido
um histórico de ficheiros, facilitando o acesso a gráficos anteriormente observados. As
figuras 4.4 e 4.5 mostram a interface gráfica que possibilita a visualização de gráficos.
Para além da visualização de gráficos, esta versão permite, com o uso do programa de
informação sumária, agregar a informação de várias capturas. Neste caso, com a submissão
38
4.4. VISUALIZAÇÃO
(a) Página inicial
(b) Opções do gráfico
Figura 4.4: Versão Web
Figura 4.5: Gráfico da versão web
de várias capturas, e respetivos parâmetros, a aplicação processa a informação sumária
resultante de todas as capturas e produz o seguinte resultado:
• Média do tempo de execução
• Média do número de pacotes
• Média do número de pacotes/segundo
• Média de bytes
• Média de bytes/segundo
39
CAPÍTULO 4. SISTEMA DE ANÁLISE
Figura 4.6: Informação agregada
• Menor tempo de execução
• No de pacotes, correspondente à captura de menor tempo de execução
• No de pacotes/segundo, correspondente à captura de menor tempo de execução
• No de bytes, correspondente à captura de menor tempo de execução
• No de bytes/segundo, correspondente à captura de menor execução
Esta informação é apresentada tanto para o tráfego de aplicação como para o tráfego
extra, podendo destes dados calcular os valores do tráfego total. A figura 4.6 mostra o
resultado da agregação de informação das capturas.
Através deste conjunto de ferramentas, é possível obter um sistema que fornece vários
tipos de informação que podem ser posteriormente utilizados para análise. A figura 4.7
mostra o diagrama de funcionamento deste sistema.
O componente de captura é responsável por fazer a monitorização do algoritmo e
produzir um ficheiro pcap, que contém os dados da captura. O ficheiro pcap, e respetivos
parâmetros, é passado ao componente de análise, através do uso da interface gráfica, de
modo a processar os dados. O componente de análise por sua vez produz dois ficheiros
csv, com a classificação do tráfego e informação sumária, respetivamente, do ficheiro pcap
inserido. Estes ficheiros csv são então utilizados pelo componente de visualização para
produção de gráficos e obtenção da informação agregada. Os gráficos e a informação
agregada são por fim apresentados ao utilizador através da interface gráfica.
Interface Gráfica
csv
Análise
Captura
Visualização
pcap
csv
Figura 4.7: Diagrama do sistema
Os gráficos produzidos pelo sistema podem ser obtidos por um utilizador que, ao
estudar um algoritmo, se depara com uma execução mais demorada. Visualizando os
gráficos, o utilizador pode assim perceber se há problemas com a comunicação dos nós,
40
4.4. VISUALIZAÇÃO
como se poderá ver na secção 5.2. Pode ainda tentar perceber se, no momento daquela
execução, houve tráfego extra acima do normal. A título de exemplo, os gráficos 4.8 e 4.9
representam a mesma execução do algoritmo Turquois. O gráfico 4.10 ilustra a evolução,
ao longo do tempo, do número de pacotes para pacotes de gestão, controlo e dados, sendo
feita a distinção entre os pacotes da aplicação e os pacotes de tráfego adicional. O gráfico
4.9 ilustra a evolução, ao longo do tempo, do número de pacotes para cada nó que executa
o algoritmo.
Figura 4.8: Gráfico temporal da execução do algoritmo para cada tipo de pacote
Figura 4.9: Gráfico temporal da execução do algoritmo para cada nó interveniente
É também possível estudar várias capturas, comparando a informação sumária obtida
em cada uma. Por exemplo, o cenário da figura 4.10, em que foram feitas várias execuções
com 4 e 7 nós. Através das capturas destas execuções, pôde-se obter uma média do
tráfego da aplicação e tráfego extra, indicando o tráfego da rede. Esta informação permite
a formação de gráficos, com uso de Excel, por exemplo. É possível observar que, com
o aumento do número de nós da rede, não só aumenta o tráfego da aplicação como
aumenta o tráfego extra. Assim, num caso de estudo, em que seja necessário testar o
41
CAPÍTULO 4. SISTEMA DE ANÁLISE
(a) Tráfego médio acumulado, com 4 nós
(b) Tráfego médio acumulado, com 7 nós
Figura 4.10: Gráficos de tráfego acumulado
comportamento do algoritmo em diferentes cenários, é interessante poder obter o tráfego
da rede, observando o rácio de tráfego de aplicação e tráfego extra.
A ferramenta implementada servirá assim como auxílio às análises que serão apresentadas no capítulo 5.
42
CAPÍTULO
5
A NÁLISES E FETUADAS
Este capítulo abordará a análise efetuada ao algoritmo em estudo no âmbito desta dissertação. Na secção 5.1 é apresentado o ambiente de testes. De seguida, a secção 5.2 apresenta
a análise feita a capturas, através da visualização de gráficos gerados pelo sistema de
análise. Na secção 5.3 é apresentada a análise aos tempos entre envio de mensagens, feita
com o propósito de encontrar os tempos favoráveis à execução do algoritmo. A secção
5.4 representa a análise ao tráfego da rede, sendo feita a comparação entre os valores
obtidos na secção anterior, de modo a perceber quais os níveis de tráfego desejáveis. Por
fim, a secção 5.5 apresenta a análise do tráfego extra. Nesta análise, o comportamento do
algoritmo é testado com a injeção de tráfego adicional na rede, de modo a perceber as
influência que o tráfego extra poderá ter na execução do algoritmo, ou vice-versa.
5.1
Ambiente de testes
No contexto da avaliação, utilizou-se uma implementação do algoritmo Turquois [25].
Esta implementação foi utilizada no contexto da avaliação de um algoritmo de consenso,
tolerante a falhas bizantinas, em redes ad-hoc. [20]
Esta versão recorre à existência de um nó que controla a experiência e como tal
coordena os intervenientes do consenso. Este nó começa por enviar uma mensagem (INIT),
com a parametrização do algoritmo, dando início à troca de chaves entre os restantes
nós. Após a troca de chaves estar concluída, o nó coordenador envia outra mensagem
(VALUE) a indicar o valor a decidir, dando sinal aos restantes nós para iniciar o consenso.
O nó coordenador mantém-se a par do desenvolvimento do processo de consenso, sendo
responsável por detetar quando é que um quórum de processos chega a consenso.
No âmbito dos testes, este algoritmo foi executado sem falhas, por paragem ou bizantinas, sendo necessário um quórum de k, em n, processos, sendo k = n −
43
n −1
3 .
CAPÍTULO 5. ANÁLISES EFETUADAS
Os dispositivos usados para correr o algoritmo foram Raspberry Pi [28], modelo B,
com sistema Unix, tendo sido usados para redes com 5 a 9 nós. Sendo o principal objetivo
perceber o impacto do algoritmo com diferentes tempos entre envio de mensagens, foram
feitas várias execuções com cada tempo de espera e com diferentes números de nós. Os
tempos entre envio de mensagens usados foram 5, 10, 20, 40 60, 80, 100, 120, 160 e 200
milissegundos. Esta implementação define que de cada vez que um nó muda de fase é
enviada uma mensagem broadcast. Assim, para avaliar se este broadcast terá algum impacto,
optou-se por testar execuções com e sem este broadcast adicional.
Em primeira instância, a rede sem fios consistiu numa rede aberta com um ponto
de acesso. De modo a minimizar a possibilidade de colisões, a rede em uso foi mantida
num canal inutilizado por redes vizinhas. Além disso há que considerar a inexistência de
pacotes do protocolo RTS/CTS [12], pelo facto de todos os nós serem capazes de ouvir os
restantes nós da rede.
5.2
Análise de capturas
Para a análise dos resultados obtidos é necessário considerar algumas particularidades
do algoritmo. No caso da implementação do algoritmo Turquois em questão, é sabido
que a troca de chaves e o consenso executam através do envio de mensagens em portas
diferentes. Mais concretamente, a troca de chaves é feita através de pacotes recebidos pela
porta 12347 e a fase de consenso recebe pacotes pela porta 12345. Para além destas duas
portas, os pacotes de pedido de retransmissão, enviados ao nó coordenador, são recebidos
pela porta 12346. Tendo este conhecimento, é possível identificar as diferentes fases do
algoritmo através da visualização dos gráficos gerados pela ferramenta.
As capturas iniciais, feitas a este algoritmo, serviram como meio de avaliação à ferramenta de análise. Através das capturas, e da sua análise através da ferramenta Wireshark
[39], foi possível verificar a autenticidade dos resultados produzidos pela ferramenta
implementada. Estas capturas permitiram também detetar que a implementação do algoritmo Turquois continha alguns problemas que não garantiam que os nós atingissem o
consenso.
Considere-se o gráfico 5.1, que ilustra a evolução do número de pacotes de cada
nó, ao longo do tempo. Neste caso, existem quatro nós com endereços 192.168.1.101,
192.168.1.103, 192.168.1.105 e 192.168.1.107, a executar o algoritmo, sendo 192.168.1.109 o
nó coordenador, e o tráfego das portas 12345 e 12347. Pode-se observar na figura 5.2 que
os nós não entram na fase de consenso pelo facto que não existir tráfego na porta 12345.
É também possível observar que, a determinada altura, somente os nós 192.168.1.103,
192.168.1.105 e 192.168.1.107 continuam a enviar pacotes. Sendo estes pacotes enviados
para a porta 12347, concluiu-se que estes nós ainda se encontram na fase de troca de
chaves. Este cenário repete-se em várias execuções do algoritmo, dando indicação de que
existem problemas na implementação do algoritmo.
44
5.2. ANÁLISE DE CAPTURAS
Figura 5.1: Falha na receção do pacote INIT no nó 192.168.1.101
Figura 5.2: Falha na receção do pacote INIT no nó 192.168.1.101, com inclusão da porta
12347
Figura 5.3: Falha na receção do pacote VALUE nos nós 192.168.1.101 e 192.168.1.107
45
CAPÍTULO 5. ANÁLISES EFETUADAS
Após identificar as fases problemáticas, foi possível identificar as partes da implementação que deviam ser corrigidas. Devido à não fiabilidade do protocolo UDP e do envio de
mensagens por difusão, caso a mensagem INIT se perdesse e o nó B não o recebesse, este
nó não seria capaz de iniciar o algoritmo, figura 5.4. O mesmo caso acontecia no início do
consenso, caso a mensagem VALUE não chegasse a todos os nós, estes não seriam capazes
de participar no consenso. As capturas permitiram observar que, por vezes, numa rede de
quatro nós, por exemplo, enquanto três comunicavam entre si, um dos nós não participava
na troca de chaves. Não sendo possível efetuar a troca de chaves entre os quatro nós, o
processo de decisão nem sequer era iniciado. O mesmo acontecia no envio da mensagem
VALUE, em caso de falha do envio da mensagem para dois nós, era possível observar
que somente dois nós tentavam chegar a consenso, sem sucesso. Este tipo de falha pode
ser observado na figura 5.3, em que a fase de consenso é identificada pelo acréscimo de
tráfego dos nós 192.168.1.103 e 192.168.1.105.
A
B
C
…
Figura 5.4: Caso de erro
Para a resolução deste problema, foi necessário implementar um mecanismo de retransmissão destes dois pacotes. No caso da mensagem INIT, o nó B ao detetar que os
restantes nós iniciaram a troca de chaves, pede ao nó coordenador para retransmitir a
mensagem, figura 5.5. Na situação da mensagem VALUE, é necessário um valor de timeout.
Completando a troca de chaves, os nós têm um tempo limitado para esperar pela mensagem VALUE. Ultrapassando esse valor, o nó pede ao nó coordenador para reenviar a
mensagem.
Utilizando como exemplo uma execução com quatro nós 192.168.1.108, 192.168.1.109,
192.168.1.151 e 192.168.1.152 e o nó coordenador 192.168.1.100. Ao observar o gráfico da
figura 5.6, pode-se ter a perceção do tráfego gerado por cada nó, em número de pacotes.
Nota-se, por exemplo, que o nó coordenador (192.168.1.100) gera muito menos tráfego que
os restantes, sendo um elemento passivo que não está envolvido na troca de mensagens
por difusão.
Se, ao gráfico anterior, se juntar a informação referente ao tráfego recebido na porta
12345, correspondente ao processo de decisão, pode-se identificar o momento em que o
consenso começa, como se pode observar na figura 5.7. De modo a facilitar a análise do
tráfego do consenso, é ainda possível ampliar o gráfico na zona pretendida e desativar os
46
5.2. ANÁLISE DE CAPTURAS
A
B
C
são
transmis
pedido re
…
Figura 5.5: Caso de retransmissão de pacote
Figura 5.6: Gráfico
Figura 5.7: Gráfico com inclusão da porta 12345
dados da porta 12345, como é possível ver na figura 5.8.
47
CAPÍTULO 5. ANÁLISES EFETUADAS
Figura 5.8: Gráfico com zoom
Figura 5.9: Gráfico com perda de pacotes
O exemplo do gráfico da figura 5.8 mostra também o caso de uma execução que
correu sem percalços. Pode-se observar que assim que a fase de consenso começa, os
quatro nós enviam mensagens a um ritmo semelhante. O gráfico da figura 5.9, por outro
lado, mostra que os nós não iniciaram o consenso na mesma altura. Neste gráfico pode
observar-se com clareza que os nós 192.168.1.108 e 192.168.1.151 começam imediatamente
o consenso, enquanto que os nós 192.168.1.109 e 192.168.1.152 estão inicialmente sem
atividade. Este gráfico permite ainda identificar o momento em que a mensagem VALUE
foi retransmitida. É possível ver, após o período de inatividade dos dois nós, que o nó
coordenador estabelece comunicação e que, de seguida, ambos os nós começam a sua
participação no consenso.
Através da visualização de gráficos é ainda possível relacionar a evolução dos diferentes tipos de pacotes. Na figura 5.10 pode-se observar a evolução do número de pacotes
de gestão, controlo, da aplicação e extra. Neste exemplo e possível ver que o tráfego dos
48
5.3. ANÁLISE DE TEMPOS DE EXECUÇÃO
Figura 5.10: Gráfico
pacotes de dados é acompanhado pelo tráfego dos pacotes de controlo, sendo este constituído, maioritariamente, por pacotes de reconhecimento. O tráfego de gestão mantém-se
mínimo por ser constituído, na sua maioria, por pacotes beacon enviados pelo ponto de
acesso. O tráfego de dados extra constitui pacotes mal formados e pacotes de função nula.
5.3
Análise de tempos de execução
Considerando a instabilidade e imprevisibilidade do meio das redes sem fios, de modo
a avaliar os diversos tempos entre envio de mensagens, foi necessário obter uma amostragem de capturas das execuções do algoritmo. Mais concretamente, foi extraída uma
amostragem de 15 execuções do algoritmo. Devido à grande variação dos tempos de
execução dos 15 valores observados, foi retirado o valor de maior duração de forma a
descartar valores demasiado dispares. Para fins de análise, foram observados os tempos
de execução da fase de consenso, extraindo o tempo de troca de chaves.
Os gráficos, das figuras 5.11 e 5.12, mostram uma evolução imprevisível dos tempos de
execução médios da fase de consenso. Mais uma vez, considerando o meio de comunicação
instável, os tempos de execução do algoritmo variam bastante, mesmo em execuções do
mesmo caso de estudo.
No entanto, se se observar os melhores tempos de execução de cada caso de estudo, os
valores encontrados são mais expectáveis. Pode-se observar nos gráficos das figuras 5.13
e 5.14 a evolução do algoritmo à medida que o intervalo de tempo entre mensagens aumenta. Os valores apresentados nos gráficos correspondem à execução de menor duração,
para cada caso de estudo. Pela observação destes gráficos pode-se concluir três aspetos
interessantes:
1. Como seria de esperar, tempos de espera baixos levam a tempos de execução elevados. Este facto leva a que se pretenda aumentar este valor. No entanto, após
49
CAPÍTULO 5. ANÁLISES EFETUADAS
Figura 5.11: Evolução dos tempos médios de execução, sem broadcast adicional
Figura 5.12: Evolução dos tempos médios de execução, com broadcast adicional
atingir uma fase favorável, o aumento do tempo entre mensagens enviadas, torna a
execução do algoritmo mais lenta.
2. O aspeto anterior torna-se mais visível na figura 5.13, mostrando que a existência
de um broadcast adicional acaba por beneficiar o algoritmo, nos casos com maiores
tempos entre envio de mensagens. Este broadcast acelera a execução do algoritmo
quando o intervalo de tempo é mais elevado. Há que notar, porém, que baixos
tempos entre envio de mensagens, tornam as execuções mais demoradas, aquando
do uso deste broadcast.
3. Para cada número de nós existe um conjunto de intervalos de tempo favoráveis. No
gráfico figura 5.13, por exemplo, pode-se reparar que o melhor tempo de execução
para 4 nós encontra-se com um tempo entre envio de mensagens a 20 ms. Ao observar
os valores dos tempos de execução para 8 nós, pode-se reparar que o melhor caso
encontra-se com um tempo entre envio de mensagens a 80 ms. Estes dados são
expectáveis, considerando que com o aumento do tamanho da rede, é de esperar que
o número de mensagens aumente e seja necessário aumentar o tempo entre envio de
50
5.3. ANÁLISE DE TEMPOS DE EXECUÇÃO
Figura 5.13: Evolução dos tempos mínimos de execução, sem broadcast adicional
Figura 5.14: Evolução dos tempos mínimos de execução, com broadcast adicional
mensagens, para não congestionar a rede.
O objetivo deste caso de estudo prende-se em encontrar um, ou mais, intervalos de
tempo entre envio de mensagens que otimizem a execução do algoritmo em estudo.
Através dos tempos de execução obtidos pôde-se extrair as conclusões da tabela 5.1.
No de nós
Tempos
4
20 - 40
5
20 - 40
6
20 - 40
7
40 - 80
8
80 - 100
Tabela 5.1: Melhores tempos entre envio de mensagens
É importante referir mais uma vez que os tempos de execução do algoritmo não são
valores previsíveis, podendo variar os melhores tempos de execução, fazendo oscilar os
melhores tempos entre envio de mensagens.
51
CAPÍTULO 5. ANÁLISES EFETUADAS
No
nós
4
5
6
7
8
C/ broadcast adicional
Tempo KBytes/seg Pacotes/seg
40
80
400
20
200
900
40
120
600
80
80
500
100
80
500
S/ broadcast adiconal
Tempo KBytes/seg Pacotes/seg
20
130
600
20
200
900
20
210
1000
80
90
500
800
110
700
Tabela 5.2: Tráfego total para cada tempo entre envio de mensagens e respetivo no de nós
No
nós
4
5
6
7
8
C/ broadcast adicional
Tempo KBytes/seg Pacotes/seg
40
60
180
20
180
500
40
90
300
80
60
160
100
60
160
S/ broadcast adicional
Tempo KBytes/seg Pacotes/seg
20
100
300
20
180
500
20
180
500
80
70
190
100
70
190
Tabela 5.3: Tráfego da aplicação para cada tempo entre envio de mensagens e respetivo no
de nós
5.4
Análise de tráfego
Resumindo o processo que levou aos valores apresentados anteriormente. Através de
várias execuções do algoritmo, foi possível extrair os melhores tempos entre envio de
mensagens. Com a informação da tabela 5.1, e as capturas de todas as execuções efetuadas,
recorreu-se assim ao sistema de análise. Com uso deste sistema foi possível avaliar o
tráfego das capturas, fazendo a agregação dos dados por casos de estudo. Desta forma,
para cada número de nós e vários tempos entre envio de mensagens, obteve-se o tráfego
médio e os valores correspondentes à execução de menor duração. Com a obtenção destes
valores, fez-se a relação entre os melhores tempos entre envio de mensagens e o tráfego
da rede. Os tempos, utilizados para fazer esta relação, foram os melhores tempos de
execução de todas as capturas para o respetivo número de nós. Foi assim possível obter
os dados representados pelas tabelas 5.2 e 5.3. Em termos de comparação, a tabela 5.4
mostra execuções com durações consideradas longas, comparativamente às restantes.
Comparando as tabelas 5.2, 5.3 com a tabela 5.4 pode-se notar na diferença de tráfego
entre uma execução considerada favorável e uma execução mais longa.
Através destes dados, pretendeu-se extrair um intervalo que seja representativo dos
melhores tempos entre envio de mensagens. Considere-se o caso da implementação sem
broadcast adicional. Pela observação dos dados da tabela 5.3, pode-se depreender que,
um bom tempo de execução deverá encontrar-se quando o tráfego da aplicação está
compreendido entre [70; 180] KBytes/segundo e [190; 500] pacotes/segundo.
Após esta observação, pretende-se continuar com testes de modo a determinar se é
possível deduzir quais os valores desejáveis para os tempos entre envio de mensagens.
0 Tempo
entre envio de mensagens, em milissegundos
52
5.5. ANÁLISE DE TRÁFEGO EXTRA
No
Aplicação
KBytes/seg Pacotes/seg
220
600
250
700
260
700
230
650
330
900
nós
4
5
6
7
8
Total
KBytes/seg Pacotes/seg
280
1200
300
1300
310
1350
295
1250
400
1800
Tabela 5.4: Tráfego de uma execução com 5ms, com broadcast adicional
5.5
Análise de tráfego extra
No contexto dos resultados obtidos anteriormente, pretende-se modificar o ambiente de
testes em uso. Neste caso, pretende-se executar o algoritmo num ambiente com tráfego
extra. Para tal, as capturas serão feitas durante execução do algoritmo em paralelo com a
transferência de um ficheiro de cerca de 300Mb. Pela observação da tabela 5.3, notou-se
que existe uma quebra brusca no tráfego, ao passar de 6 para 7 nós. Considerando ainda
que o tempo entre envio de mensagens para 6 nós é [20; 40], e para 7 nós é [40; 80], optouse por acrescentar um tempo intermédio de 60 ms. Foram feitos os testes e respetivas
capturas, obtendo os seguintes valores representados na tabela 6.2.
Com recurso aos valores deduzidos anteriormente, conclui-se que as zonas sombreadas
da tabela 6.2 representam os tempos entre envio de mensagens com melhores tempos de
execução.
5 nós
6 nós
7 nós
Tempo
KBytes/seg
Pacotes/seg
KBytes/seg
Pacotes/seg
KBytes/seg
Pacotes/seg
10
20
40
60
80
230
170
90
-
650
450
250
-
280
170
105
75
50
760
470
290
200
140
260
220
115
85
63
720
600
320
230
170
Tabela 5.5: Tráfego da aplicação, com injeção de tráfego extra, sem broadcast adicional
Comparando os tempos de execução obtidos com os intervalos de tempo calculados,
pode-se confirmar que os menores tempos de execução observados se encontram nos
intervalos definidos. Mais concretamente, os melhores tempos observados foram 20 ms
para 5 nós, 40 ms para 6 nós e 40 ms para 7 nós.
Recorrendo à visualização de gráficos produzidos pelo sistema de análise, é possível
observar a relação do tráfego da aplicação com o tráfego extra. Os gráficos das figuras 5.15
e 5.16 mostram dois cenários diferentes:
1. O gráfico da figura 5.15 mostra que, com o uso de um tempo entre envio de mensagens baixo, o tráfego de aplicação é capaz de sobrepor o tráfego da transferência de
ficheiro. Pode-se observar que o tráfego da transferência de ficheiro piora assim que
53
CAPÍTULO 5. ANÁLISES EFETUADAS
Figura 5.15: Execução do algoritmo com 6 nós e 10ms de intervalo, sem broadcast adicional
Figura 5.16: Execução do algoritmo com 6 nós e 40ms de intervalo, sem broadcast adicional
o algoritmo começa. Provavelmente, neste caso, o tráfego da aplicação é a causa do
congestionamento da rede, prejudicando a execução tanto para o algoritmo como
para a transferência.
2. O gráfico da figura 5.16 ilustra o melhor tempo de execução observado. Neste caso,
nota-se que existe uma diferença grande entre o tráfego da aplicação e o tráfego da
transferência. Contudo, sabendo à partida que esta é uma execução ótima, concluiuse que ambos os tráfegos chegam a um equilíbrio que se torna benéfico para a
execução que ambos.
Através desta experiência é possível reparar que, apesar de a injeção de tráfego extra
ter influência no tráfego da aplicação, os tempos de execução ótimos não variam muito
dos tempos observados numa rede sem perturbações. Nota-se também que, os valores
de tráfego, anteriormente definidos, aplicam-se para a identificação de execuções ótimas.
54
5.5. ANÁLISE DE TRÁFEGO EXTRA
Estes resultados mostram ainda que não existe um tempo entre envio de mensagens ideal,
pois os tempos de execução são imprevisíveis. No entanto, permitem detetar um intervalo
de valores favorável, comparativamente a outros que podem provocar o congestionamento
da rede.
55
CAPÍTULO
6
C ONCLUSÕES
Este capítulo apresentará as conclusões desta dissertação. A secção 6.1 começa por apresentar os objetivos iniciais desta dissertação, finalizando com os objetivos que foram
cumpridos. De seguida, a secção 6.2 disponibiliza os resultados obtidos durante o estudo
feito a uma implementação do algoritmo Turquois [20][25]. Por fim, a secção 6.3 apresenta
medidas em que o trabalho desta dissertação poderá ser continuado e melhorado.
6.1
Objetivos e metas
Esta dissertação pretende apresentar um conjunto de metodologias que sejam capazes de
ajudar a observar o funcionamento e compreender um algoritmo distribuído, em meio
WiFi. Para tal, definiram-se como objetivos a implementação de um sistema de análise
de tráfego e a sua aplicação a um caso de estudo de um algoritmo de consenso. Com o
propósito da implementação de um sistema de análise, definiu-se que este deveria ser
capaz de capturar tráfego 802.11 de modo a este poder ser classificado. Na componente de
análise de um algoritmo, definiu-se que o sistema de análise deveria possibilitar o estudo
da execução do algoritmo ao longo do tempo, sendo possível observar o comportamento
e a latência do mesmo.
As metodologias apresentadas pretendem facilitar o estudo do desempenho de um
algoritmo. Para este meio, tenciona-se avaliar várias parametrizações do mesmo, de modo
a apontar as suas condições ideais. Em paralelo, pretende-se estudar o impacto que o
algoritmo pode ter na rede, podendo avaliar se o algoritmo prejudica o tráfego, ou viceversa. O impacto do algoritmo deve ser estudado através da observação do tráfego por
este gerado. Pretende-se que estes estudos sejam levados a cabo com recurso ao sistema
de análise implementado, sendo este sistema uma ferramenta importante para alcançar
uma melhor compreensão do algoritmo.
57
CAPÍTULO 6. CONCLUSÕES
Face aos objetivos apresentados, no decorrer desta dissertação foi possível atingir as
seguintes metas:
1. Visualização da evolução do algoritmo com recurso a gráficos temporais, produzidos
pelo sistema de análise de tráfego. Os gráficos permitem observar a evolução, e respetivo rácio, de cada tipo de tráfego da rede. O tipo de tráfego da rede é classificado
consoante os tipos de pacotes, endereço de origem, endereço de destino e porta.
Para cada tipo de tráfego é possível observar a evolução tanto de número de pacotes
como o número de bytes enviados. O sistema possibilita a análise de capturas, de
modo a compreender o comportamento que o algoritmo toma em cada execução.
2. Captura sistemática de execuções do algoritmo com diferentes parametrizações,
permitindo ter uma amostragem de valores, e de capturas, representativa do desempenho do algoritmo. Através da amostragem de valores, é possível iniciar um
estudo às várias execuções do algoritmo, permitindo comparar os resultados das
diferentes parametrizações e identificar padrões.
3. Através da amostragem de valores, e capturas, é possível, com recurso ao sistema de
análise, obter a informação agregada das execuções para cada caso de estudo. Esta
informação permite estudar as condições da rede, em termos do valor do número
de pacotes ou de bytes a decorrer na rede. Com estes valores é possível comparar o
desempenho do algoritmo em diferentes condições da rede. Com experiências que
introduzam tráfego extra na rede, é possível determinar o impacto que o algoritmo
tem na rede, ou vice-versa, assim como o overhead devido ao protocolo da própria
rede WiFi.
Através do cumprimento destes objetivos, foi possível realizar um estudo a uma
implementação do algoritmo Turquois [20]. Os resultados deste estudo serão apresentados
de seguida.
6.2
Resultados
No âmbito desta dissertação foi levado a cabo um estudo a uma implementação do
algoritmo Turquois. Este estudo seguiu uma estratégia de análise com objetivo a detetar
os melhores parâmetros de execução. Conseguindo obter estes dados, pretendeu-se que
fosse possível, através do estudo do tráfego da rede, depreender se se estava perante uma
parametrização favorável.
Antes de iniciar a estratégia de análise foram realizadas capturas à execução do algoritmo de modo a validar os resultados produzidos pela ferramenta de análise. Por
consequência, destas capturas, foi possível concluir que a ferramenta auxilia na compreensão de um algoritmo, podendo identificar falhas na execução do mesmo. As capturas
da implementação do algoritmo Turquois ajudou a identificar falhas no envio e receção
58
6.2. RESULTADOS
de mensagens essenciais para o funcionamento do algoritmo, como foi apresentado na
secção 5.2.
Dando início à estratégia de análise, começou-se por definir os possíveis parâmetros
de execução do algoritmo. Tendo conhecimento da problemática da definição do melhor
tempo entre envio de mensagens, secção 3.5, optou-se por estudar este valor. Concretamente, utilizaram-se os tempos 5, 10, 20, 40, 80, 100 e 120 milissegundos. Além disto,
optou-se também por estudar o impacto do algoritmo com diferentes números de nós,
para avaliar a escalabilidade do mesmo. Foram feitos testes com 4, 5, 6, 7 e 8 nós.
De seguida, iniciou-se a execução o algoritmo. O algoritmo foi executado num ambiente
sem tráfego extra e com diferentes valores de tempo e números de nós. Em simultâneo
à execução do algoritmo, deu-se inicio à monitorização da rede. Esta monitorização foi
levada a cabo por um nó externo à execução do algoritmo, com recurso ao modo monitor
para obter todo o tráfego 802.11. Desta forma, obteve-se amostra de 15 capturas para
cada parametrização do algoritmo. Através destas capturas, observou-se que tempos
entre envio de mensagens produziam os tempos de execução ótimos. Mais concretamente,
concluiu-se que existe um conjunto de tempos favoráveis, tabela 5.1 da secção 5.3, ao
invés de um valor único, e que os valores observados alteram consoante o número de nós,
como seria de esperar. Foi assim possível perceber o desempenho do algoritmo e a sua
evolução. No entanto, é importante referir que, devido ao ambiente imprevisível e instável
das redes WiFi, os tempos de execução observados variam bastante, mesmo em execuções
com os mesmos parâmetros, como se pode ver nos gráficos 5.11 e 5.12 da secção 5.3. Desta
forma, os valores, daqui para a frente apresentados, são referentes aos melhores casos de
execução.
Utilizando os tempos obtidos, deu-se início ao estudo do tráfego da rede. Com recurso
ao sistema de análise, obteve-se a informação agregada para cada possível parametrização
do algoritmo, podendo ter a perceção do tráfego (em número de mensagens/segundo
e KBytes/segundo) da aplicação e da rede, no total, para cada caso de estudo, tabela 6.1.
Tendo conhecimento dos tempos entre envio de mensagens favoráveis e o tráfego da rede,
foi feita a relação entre estes valores de modo a tentar depreender os valores de tráfego
favoráveis.
No nós
4
5
6
7
8
Tempo
20
20
20
80
100
KBytes/seg
100
180
180
70
70
Pacotes/seg
300
500
500
190
190
Tabela 6.1: Tráfego da aplicação, sem broadcast adicional
Nesta fase do estudo, definiram-se dois intervalos de valores como sendo os possíveis
valores de tráfego favoráveis. Os intervalos definidos correspondem ao tráfego em número
de mensagens/segundo e KBytes/segundo. Estes intervalos são [70; 180] KBytes/segundo
59
CAPÍTULO 6. CONCLUSÕES
No nós
5
6
7
Tempo
20
40
40
KBytes/seg
170
105
115
Pacotes/seg
450
290
320
Tabela 6.2: Tráfego da aplicação com injeção de tráfego extra, sem broadcast adicional
e [190; 500] pacotes/segundo. Existe agora a necessidade de comprovar estes valores,
partindo assim para outra análise de tráfego. Desta vez optou-se por injetar tráfego na
rede, de modo a observar o impacto do algoritmo na rede (ou vice-versa) e testar os
intervalos de tráfego obtidos.
Este estudo consistiu em capturar a execução do algoritmo enquanto decorria a transferência de um ficheiro de 300Mb. Mais uma vez, estudou-se diferentes parâmetros do
algoritmo, fazendo variar os tempos entre envio de mensagens e o número de nós. Após a
conclusão das capturas, recorreu-se novamente ao sistema de análise para obter os valores
de tráfego da aplicação, e do tráfego extra. Após a obtenção destes valores, procurou-se
definir quais os tempos entre envio de mensagens, para cada número de nós, através
da análise dos valores de tráfego da aplicação. Relembrando os intervalos de tráfego
obtidos anteriormente ([70; 180] KBytes/segundo e [190; 500] pacotes/segundo), a tabela
6.2 identifica as execuções que poderão ser consideradas favoráveis. Comparando os
tempos calculados com os valores reais, obtidos da execução do algoritmo, observou-se
que as execuções ótimas do algoritmo decorriam dentro dos valores de tráfego calculados.
Pôde-se então concluir que é possível identificar execuções favoráveis através dos valores
do tráfego da aplicação.
Para além destas conclusões, a injeção de tráfego extra na rede pode demonstrar o
impacto que o algoritmo tem. Concretamente, observou-se que tempos entre envio de mensagens demasiado baixos causam congestionamento na rede, prejudicando o desempenho
da transferência de ficheiro. No caso de tempos entre envio de mensagens favoráveis,
observou-se que o tráfego da rede adapta-se, sendo distribuído equilibradamente entre a
transferência de ficheiro e a execução do algoritmo. Concluiu-se que esta observação se
deve ao facto do protocolo TCP, usado na transferência, se adaptar para usar a banda que
fica disponível. Esta distribuição permite que ambas as execuções decorram em níveis de
tráfego favoráveis a ambos, sem que a transferência prejudique o algoritmo ou vice-versa.
Em suma, através desta estratégia de estudo, pode-se assim concluir que, com a análise
do tráfego da aplicação e da rede, é possível melhorar a perceção do comportamento do
algoritmo que se pretende estudar. Define-se, assim, um possível conjunto de métodos
que levem à compreensão do impacto do algoritmo, e que medidas se devem tomar para
melhorar a execução do mesmo.
60
6.3. TRABALHO FUTURO
6.3
Trabalho Futuro
As conclusões levadas a cabo por esta dissertação levantam algumas questões que poderão
ser respondidas com algum trabalho futuro. O estudo do algoritmo Turquois, mostra que
é possível, através da utilização das metodologias de estudo, encontrar um intervalo de
tráfego favorável para a execução do algoritmo. Através deste intervalo, deve ser possível,
somente com a observação do tráfego gerado pelo algoritmo, identificar se a presente
execução está a decorrer dentro dos níveis desejados.
Perante esta observação, propõe-se que seja possível implementar um sistema autonómico, que dinamicamente otimize as parametrizações do algoritmo. Este novo sistema
deverá analisar a execução do algoritmo, em tempo real, de modo a observar os níveis
de tráfego gerado. Através desta observação, deverá ser possível deduzir se a execução
se encontra dentro dos níveis desejados. Em caso negativo, o sistema, deverá alterar as
parametrizações do algoritmo de modo a orientá-lo para valores de tráfego favoráveis. Isto
é, o sistema autonómico, ao observar valores de tráfego elevados deverá baixar o tempo
entre envio de mensagens, para aliviar o congestionamento da rede. Ou ainda, caso os
valores de tráfego sejam baixos, elevar o tempo entre envio de mensagens para atingir um
tempo de execução mais desejado. Realizando este tipo de análise dinâmica, propõe-se que
o sistema seja capaz de encontrar e definir a parametrização ideal do algoritmo, somente
através da observação dos níveis de tráfego gerado pelo algoritmo, ou já presente na rede.
Dentro da mesma linha de raciocínio, propõe-se, como trabalho de futuro, realizar
testes com maior número de nós. O objetivo desta proposta é que seja possível extrapolar os
intervalos de tempo entre envio de mensagens, consoante o número de nós interveniente
no algoritmo. Caso seja possível criar uma relação lógica entre o número de nós e o
tempo entre envio de mensagens, propõe-se também que o sistema autonómico possa ser
estendido para alterar a parametrização do algoritmo consoante o número de nós que
forem sendo detetados como participantes do algoritmo.
Propõe-se ainda que, através da utilização da ferramenta de análise implementada,
no contexto desta dissertação, seja possível levar a cabo estudos mais elaborados. A
ferramenta de análise auxilia o estudo da execução de algoritmos através da visualização
de gráficos que representam o comportamento do mesmo. Através destes gráficos, propõese que seja possível identificar outros problemas da rede, para além das observações
feitas na secção 5.5. Estes problemas poderão ser identificados por congestionamento da
rede, ou padrões que indiquem a presença clientes maliciosos que possam estar a atacar a
segurança da rede, ou a consumir grande parte da banda da rede.
61
B IBLIOGRAFIA
[1] Almeida, João. “Intrusion Tolerant Routing with Data Consensus in Wireless Sensor
Networks”. Tese de mestrado. Faculdade de Ciências e Tecnologia da Universidade
Nova de Lisboa, 2013.
[2]
Bootstrap. URL: http://getbootstrap.com.
[3] Calhoun, P. and Montemurro, M. and Stanley, D. Control and Provisioning of Wireless
Access Points (CAPWAP) Protocol Binding for IEEE 802.11. RFC 5416. 2009.
[4]
CanvasJS. URL: http://canvasjs.com.
[5] Cascading Style Sheets. URL: http://www.w3.org/Style/CSS/Overview.en.
html.
[6]
Ergen, Mustafa. IEEE 802.11 Tutorial. Rel. téc. 2002, p. 90.
[7] Farruca, Nuno. “Wireshark para Sistemas Distribuídos”. Tese de mestrado. Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa, 2009.
[8] Gast, Matthew. 802.11 Wireless Networks: The Definitive Guide. O’Reilly Media, Inc,
2005.
[9] Gupta, Arpit and Min, Jeongki and Rhee, Injong. “WiFox: Scaling WiFi Performance
for Large Audience Environments”. Em: Proceedings of the 8th International Conference
on Emerging Networking Experiments and Technologies. CoNEXT ’12. Nice, France:
ACM, 2012, pp. 217–228. ISBN: 978-1-4503-1775-7.
[10]
HTML5. URL: http://www.w3.org/TR/html5/.
[11] IEEE Computer Society. IEEE Standards for Local Area Networks: Carrier Sense Multiple Access With Collision Detection (CSMA/CD) Access Method and Physical Layer
Specifications. 1985.
[12] IEEE Computer Society. Wireless LAN Medium Access Control and Physical Layer
Specifications. 2012.
[13]
Java. URL: https://www.java.net.
[14] Java SE 7 Swing APIs and Developer Guides. URL: http://docs.oracle.com/
javase/7/docs/technotes/guides/swing/.
[15]
Javascript. URL: http://www.ecmascript.org.
63
BIBLIOGRAFIA
[16]
Kurose, James F. and Ross, Keith W. Computer Networking A Top-Down Approach.
2008.
[17]
Lamport, Leslie. “Paxos Made Simple”. Em: ACM SIGACT News 32 (2001), pp. 18–25.
[18]
Lamport, Leslie. “Byzantizing Paxos by Refinement”. Em: (2010).
[19]
Lamport, Leslie, Shostak, Robert and Pease, Marshall. “The Byzantine Generals
Problem”. Em: ACM 4 (1982), pp. 382–401.
[20]
Libório, João. Design, implementation and evaluation of a Byzantine Fault Tolerant Consensus Protocol, in an Ad-Hoc 802.11 Wireless Environment. Rel. téc. 2014.
[21]
Lynch, Nancy. Distributed Algorithms. San Francisco: CA: Morgan Kaufmann Publishers, 1996. ISBN: 978-1-55860-348-6.
[22]
Martin Garcia, Luis. “Programming with Libpcap - Sniffing the Network From Our
Own Application”. Em: In Hacking (2008), pp. 38–46.
[23]
Martins, Nuno. “Captura de tráfego de rede de um processo com base no PCAP”.
Tese de mestrado. Faculdade de Ciências e Tecnologia da Universidade Nova de
Lisboa, 2011.
[24]
McCanne, Steven and Jacobson, Van. “The BSD Packet Filter: A new architecture for
user-level packet capture”. Em: USENIX Winter 1993 Conference Proceedings (1993).
[25]
Moniz, Henrique and Neves, Nuno Ferreira and Correia, Miguel. Turquois: Byzantine
consensus in wireless ad hoc networks. IEEE, 2010, pp. 537–546. ISBN: 978-1-4244-7501-8.
[26]
Open Mobile Alliance. Wireless Application Protocol Architecture Specification. Rel. téc.
2001, p. 20.
[27]
Peaser, Marshall and Shostak, Robert and Lamport, Leslie. “Reaching agreement in
the presence of faults”. Em: J. ACM 27 (1980), pp. 228–134.
[28]
Raspberry Pi. URL: http://www.raspberrypi.org.
[29]
Ruby. URL: http://www.ruby-lang.org/en.
[30]
Ruby on Rails. URL: http://rubyonrails.org.
[31]
Schulman, Aaron and Levin, Dave and Spring, Neil. “On the Fidelity of 802.11
Packet Traces”. Em: PAM (2008).
[32]
Swain, Pravati and Chakraborty, Sandip and Nandi, Sukumar and Bhaduri, Purandar. “Performance Modeling and Evaluation of IEEE 802.11 IBSS Power Save Mode”.
Em: (2013).
[33]
Tanenbaum, Andrew S. and van Steen, Maarten. Distributed Systems, Principles and
Paradigms. 2007.
[34]
Tavares, João. “Encaminhamento e disseminação de dados tolerantes a instruses para
redes de sensores sem fios”. Tese de mestrado. Faculdade de Ciências e Tecnologia
da Universidade Nova de Lisboa, 2012.
64
BIBLIOGRAFIA
[35] TCPDump & LibPCap Related Work. URL: http://www.tcpdump.org/related.
html.
[36]
TCPDump & LipPcap. URL: "http://www.tcpdump.org".
[37]
WinDump. URL: http://www.winpcap.org/windump/.
[38]
WinPcap. URL: "http://www.winpcap.org".
[39]
Wireshark. URL: "http://www.wireshark.org".
[40]
XChart. URL: http://xeiam.com/xchart/.
[41] Youssef, Moustafa A. and Vasan, Arunchandar and Miller, Raymond E. “Specification and Analysis of the DCF and PCF Protocols in the 802.11 Standard Using
Systems of Communicating Machines”. Em: ().
65
2015
Ana Gonçalves
Monitorização de Sistemas Distribuídos em Redes WiFi