View
220
Download
1
Category
Preview:
Citation preview
Ana Filipa Fernandes Pereira
Dados Nomeados em Redes Móveis Ad hoc
Ana
Filip
a Fe
rnan
des
Pere
ira
maio de 2016UMin
ho |
201
6Da
dos
Nom
eado
s em
Red
es M
óvei
s Ad
hoc
Universidade do MinhoEscola de Engenharia
maio de 2016
Dissertação de MestradoCiclo de Estudos Integrados Conducentes ao Grau deMestre em Engenharia deTelecomunicações e Informática
Trabalho efetuado sob a orientação deProfessora Doutora Maria João NicolauProfessor Doutor António Costa
Ana Filipa Fernandes Pereira
Dados Nomeados em Redes Móveis Ad hoc
Universidade do MinhoEscola de Engenharia
Agradecimentos
Em primeiro lugar, gostaria de agradecer a Professora Doutora Maria Joao Nicolau
e ao Professor Doutor Antonio Costa, por todo apoio e disponibilidade demonstrada,
durante toda a execucao deste projeto de dissertacao de mestrado. Foi um privilegio ter
trabalhado sob a sua orientacao.
Agradeco tambem ao meu namorado Bruno, que demonstrou sempre todo o seu
companheirismo, paciencia e incentivo.
Queria agradecer, tambem, a toda a minha famılia, em especial aos meus pais, por
todos os esforcos realizados, para que eu pudesse concluir este meu percurso academico,
que sera muito importante no meu futuro.
Por fim, quero agradecer a todos os meus amigos e colegas de curso.
iii
Resumo
As redes moveis Ad hoc sao compostas por nos moveis, que tem a capacidade de,
autonomamente, criar uma rede de comunicacoes entre eles, sem assistencia de um ponto
de acesso, contrariamente as redes de infraestrutura. A comunicacao e sem fios e ocorre
diretamente entre os nos vizinhos, localizados no mesmo raio de alcance. No entanto,
neste tipo de redes, a topologia da rede e muito dinamica, devido a mobilidade dos
nos, a entrada e saıda de nos na rede e as quebras de ligacoes constantes, que provo-
cam alteracoes inesperadas nas rotas. Alem disso, o meio de comunicacao e sem fios e
partilhado entre os nos vizinhos.
O paradigma dos dados nomeados (NDN - Named Data Networks) pode contribuir
para minimizar alguns dos problemas das redes Ad hoc. As NDNs constituem uma al-
ternativa as redes IP, apontada como uma das mais promissoras arquiteturas de rede
da Internet do futuro e baseiam-se no paradigma receiver driven. Os utilizadores (con-
sumidores de informacao) apenas tem que saber qual o conteudo (nome) pelo qual tem
interesse, nao sendo necessario conhecer a sua localizacao (endereco). Para obter a in-
formacao que deseja, o consumidor propaga um pacote de interesse atraves da rede.
Quando este atinge um no produtor ou um no intermedio, que possua o conteudo em
cache, os dados sao devolvidos pelo caminho inverso.
Nesta dissertacao propos-se uma nova estrategia de reenvio de Interesses e Dados,
designada por MPRstrategy (MultiPoint Relay), numa rede de dados nomeados Ad Hoc.
O objectivo e diminuir o envio redundante de pacotes e melhorar o desempenho da
rede. Os pacotes de interesses sao enviados apenas por um subconjunto de nos vizinhos,
escolhidos de modo a minimizar as retransmissoes. Alem disso, o reenvio e atrasado
de modo a poder reduzir as transmissoes redundantes. Os pacotes de dados seguem o
percurso inverso, se possıvel. Senao sao reenviados da mesma forma. A estrategia foi
implementada e avaliada no simulador ndnSIM, mostrando melhorias de desempenho,
quando comparada com outras alternativas.
v
Abstract
The mobile networks Ad hoc are composed by mobile nodes, which have the ability
to, autonomously, create a communications network between them, without assistance
from an access point, in contrast to the infrastructure networks. The communication
is wireless and occurs directly between the neighbor nodes, located in the same range.
However, in this type of network, the topology of the network is very dynamic due to the
mobility of the nodes, the input and output nodes in the network and to the breaks of
connections constant, which cause unexpected changes of path. In addition, the means
of wireless communications is shared among the nodes neighbor.
The paradigm of the named data (NDN - Named Data Networks) can help to mi-
nimize some of the problems of Ad hoc networks. The NDNs are an alternative to IP
networks, and are viewed as one of the most promising network architectures for the
future Internet. This new paradigm is based on the receiver driven. Users (consumers
of information) just have to know what is the content of (name) by which you have an
interest, not being necessary to know its location (address). To get the information that
it want, the consumer propagates a interest packet through the network. When this
reaches a producer or an intermediate node, which have the content cached, the data is
returned by the reverse path.
This dissertation proposed a new Interests and Data packet forwarding strategy, cal-
led MPRstrategy (Multipoint Relay), for named-data Ad Hoc networks. The aim is to
reduce packet transmission redundancy and improve network performance. The interests
packets are sent only by a subset of neighboring nodes chosen to minimize retransmis-
sions. Furthermore, forwarding is delayed in order to reduce redundant transmissions.
Data packets follow the reverse route if possible. Otherwise, they are forwarded in the
same way. The strategy was implemented and evaluated in ndnSIM simulator, showing
improved performance compared to other alternatives.
vii
Conteudo
Agradecimentos i
Resumo iii
Abstract v
Conteudo vii
Lista de Figuras xi
Lista de Tabelas xiii
Abreviaturas xv
Sımbolos xvii
1 Introducao 1
1.1 Enquadramento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Estrutura da dissertacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Redes Ad Hoc 5
2.1 Encaminhamento Ad Hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Encaminhamento Plano . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Protocolos Proativos . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Protocolos Reativos . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Encaminhamento Hierarquico . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Zone Routing Protocol (ZRP) . . . . . . . . . . . . . . . . . . . . . 12
2.4 Encaminhamento Geografico de posicao assistida . . . . . . . . . . . . . . 12
2.4.1 LAR (Location-Aided Routing) . . . . . . . . . . . . . . . . . . . . 12
3 Redes de Dados Nomeados 15
3.1 Estrutura do no NDN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Nomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Seguranca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Encaminhamento NDN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.5 Utilizacao de protocolos de encaminhamento em redes NDN . . . . . . . . 19
ix
Conteudos x
4 Ad Hoc via NDN 21
4.1 Protocolo LFBL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Protocolo NAIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Protocolo E-CHANET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Protocolo BF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.5 Protocolo PAF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.6 Comparacao dos Protocolos . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5 Estrategias de encaminhamento propostas 33
5.1 Estrategia BFstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1.1 Encaminhamento de interesses . . . . . . . . . . . . . . . . . . . . 34
5.1.2 Encaminhamento de dados . . . . . . . . . . . . . . . . . . . . . . 36
5.1.3 Desvantagens da BFstrategy . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Estrategia DSRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2.1 Encaminhamento de interesses . . . . . . . . . . . . . . . . . . . . 42
5.2.2 Encaminhamento de dados . . . . . . . . . . . . . . . . . . . . . . 42
5.3 Estrategia MPRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3.1 Encaminhamento de mensagens hello . . . . . . . . . . . . . . . . . 43
5.3.2 Encaminhamento de interesses . . . . . . . . . . . . . . . . . . . . 46
5.3.2.1 Algoritmo MPR . . . . . . . . . . . . . . . . . . . . . . . 46
5.3.3 Encaminhamento de dados . . . . . . . . . . . . . . . . . . . . . . 54
6 Implementacao 55
6.1 Simulador ndnSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Tabelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.3 Estrutura dos Pacotes interesse/dados . . . . . . . . . . . . . . . . . . . . 57
6.3.1 Pacote de interesse . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.3.2 Pacote de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.4 Processamento de pacotes pelo NFD . . . . . . . . . . . . . . . . . . . . . 60
6.4.1 Processamento de interesses . . . . . . . . . . . . . . . . . . . . . . 62
6.4.2 Processamento de dados . . . . . . . . . . . . . . . . . . . . . . . . 63
6.5 Estrategias de encaminhamento implementadas . . . . . . . . . . . . . . . 63
6.5.1 Estrategia BFstrategy . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.5.1.1 Encaminhamento de interesses . . . . . . . . . . . . . . . 65
6.5.1.2 Encaminhamento de pacotes de dados . . . . . . . . . . . 66
6.5.2 Estrategia DSRstrategy . . . . . . . . . . . . . . . . . . . . . . . . 69
6.5.2.1 Encaminhamento de interesses . . . . . . . . . . . . . . . 69
6.5.2.2 Encaminhamento de pacotes de dados . . . . . . . . . . . 69
6.5.3 Estrategia MPRstrategy . . . . . . . . . . . . . . . . . . . . . . . . 71
6.5.3.1 Encaminhamento de mensagens hello . . . . . . . . . . . 72
6.5.3.2 Encaminhamento de interesses . . . . . . . . . . . . . . . 73
6.5.3.3 Encaminhamento de pacotes de dados . . . . . . . . . . . 74
7 Testes e resultados 77
7.1 Configuracoes para a simulacao . . . . . . . . . . . . . . . . . . . . . . . . 77
7.2 Cenarios de simulacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.3 Metricas usadas na simulacao . . . . . . . . . . . . . . . . . . . . . . . . . 79
Conteudos xi
7.4 Resultados experimentais . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.4.1 Trafego de interesses . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.4.2 Trafego de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.4.3 RTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.4.4 Percentagem de interesses satisfeitos . . . . . . . . . . . . . . . . . 88
8 Conclusao e trabalho futuro 91
8.1 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.2 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
A Algoritmos da estrategia BFstrategy 95
A.1 Encaminhamento de interesses . . . . . . . . . . . . . . . . . . . . . . . . 95
A.2 Encaminhamento de dados . . . . . . . . . . . . . . . . . . . . . . . . . . 97
B Algoritmos da estrategia DSRstrategy 99
B.1 Encaminhamento de interesses . . . . . . . . . . . . . . . . . . . . . . . . 99
B.2 Encaminhamento de dados . . . . . . . . . . . . . . . . . . . . . . . . . . 99
C Algoritmos da estrategia MPRstrategy 101
C.1 Encaminhamento de interesses . . . . . . . . . . . . . . . . . . . . . . . . 101
C.2 Encaminhamento de dados . . . . . . . . . . . . . . . . . . . . . . . . . . 102
Bibliografia 105
Lista de Figuras
2.1 OLSR: ilustracao dos MPR, adaptado de [2] . . . . . . . . . . . . . . . . . 9
2.2 (a) sem OLSR; (b) com OLSR [3] . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Funcionamento do protocolo LAR: (a)Esquema 1 [2] . . . . . . . . . . . . 13
2.4 Funcionamento do protocolo LAR: (b)Esquema 2. [2] . . . . . . . . . . . . 14
3.1 Processo de Encaminhamento NDN . . . . . . . . . . . . . . . . . . . . . . 18
4.1 Procedimento do reencaminhamento de interesses dos protocolos PAF eBF [5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1 Estrutura da tabela de interesses atrasados dos nos na estrategia BFstra-teggy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Estrutura da tabela de dados atrasados dos nos na estrategia BFstrateggy 34
5.3 Cenario da simulacao usada para mostrar desvantagens da BFstrategy . . 38
5.4 Passos 1 ate 5 da experiencia realizada para mostrar desvantagens daBFsrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.5 Passos 6 ate 10 da experiencia realizada para mostrar desvantagens daBFsrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.6 Estrutura da Tabela Vizinhos dos nos na estrategia MPRstrateggy . . . . 44
5.7 Exemplo da troca de mensagens “/hello” na MPRstrategy . . . . . . . . . 45
5.8 Estrutura da Tabela provisorio dos nos na estrategia MPRstrateggy . . . 47
5.9 Fluxograma da tecnica MPR . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.10 Exemplo da Tabela Vizinhos do no N na MPRstrategy . . . . . . . . . . . 50
5.11 Exemplo de registo na Tabela provisorio do no A na MPRstrategy . . . . 51
5.12 Exemplo da Tabela Provisorio do no N na MPRstrategy . . . . . . . . . . 52
6.1 Estrutura do pacote de interesse . . . . . . . . . . . . . . . . . . . . . . . 57
6.2 Estrutura do pacote de dados . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.3 Estrutura do pacote de interesse na estrategia DSRstrategy . . . . . . . . 60
6.4 Estrutura do pacote de dados na estrategia DSRstrategy . . . . . . . . . . 60
6.5 Estrutura do pacote de interesse na estrategia MPRstrategy . . . . . . . . 61
6.6 Relacao entre pipelines e a estrategia [6] . . . . . . . . . . . . . . . . . . . 61
6.7 Estrutura da Struct de interesses atrasados na BFstrategy . . . . . . . . . 64
6.8 Estrutura da Struct de dados atrasados na BFstrategy . . . . . . . . . . . 65
6.9 Sequencia de funcoes para o encaminhamento de interesses, na estrategiaBFstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.10 Sequencia de funcoes para o encaminhamento de dados, na estrategiaBFstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
xiii
Lista de Figuras xiv
6.11 Sequencia de funcoes para o encaminhamento de interesses, na estrategiaDSRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.12 Sequencia de funcoes para o encaminhamento de dados, na estrategiaDSRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.13 Estrutura da Tabela “Vizinhos” de um no na MPRstrategy . . . . . . . . 72
6.14 Sequencia de funcoes para o encaminhamento de interesses, na estrategiaMPRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.15 Sequencia de funcoes para o encaminhamento de dados, na estrategiaMPRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.1 Numero medio de interesses recebidos por no . . . . . . . . . . . . . . . . 81
7.2 Numero medio de interesses enviados por no . . . . . . . . . . . . . . . . . 82
7.3 Percentagem media de interesses enviados por no . . . . . . . . . . . . . . 82
7.4 Percentagem media de interesses duplicados recebidos . . . . . . . . . . . 83
7.5 Numero medio de dados recebidos por no . . . . . . . . . . . . . . . . . . 84
7.6 Numero medio de dados enviados por no . . . . . . . . . . . . . . . . . . . 85
7.7 Percentagem media de dados enviados por no . . . . . . . . . . . . . . . . 86
7.8 Percentagem media de dados duplicados recebidos . . . . . . . . . . . . . 86
7.9 RTT medio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.10 Percentagem media de interesses satisfeitos . . . . . . . . . . . . . . . . . 88
Lista de Tabelas
4.1 Tabela comparativa dos protocolos LFBL, NAIF, E-CHANET, BF e PAF 32
5.1 Debug da simulacao exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.1 Parametros do cenario de simulacao . . . . . . . . . . . . . . . . . . . . . 78
xv
Abreviaturas
AODV Ad hoc On demand Distance Vector
BF Blind Forwarding
CBR Constant Bit Rate
CGSR Clusterhead- Gateway Switch Routing
CID Content IDentifier
CPT Content Provider Table
CS Content Store
DW Defer Window
DDoS Distributed Denial of Service
DoS Denial of Service
DREAM Distance Routing Effect Algorithm for Mobility
DSR Dynamic Source Routing
DT Distance Table
DV Distance-Vector
E-CHANET Enhanced-Content-centric multiHop wireless NETwork
FIB Forwarding Information Base
FSLS Fuzzy Sighted Link State
FSR Fisheye State Routing
GeoCast Geographic Addressing and Routing
GPS Global Position System
GPSR Greedy Perimeter Stateless Routing
HSR Hierarchical State Routing
IGP Interior Gateway Protocol
LANMAR LANdMark Ad Hoc Routing
LAR Location-Aided Routing
LFBL Listen First, Broadcast Later
xvii
Acronimos xviii
LS Link-State
MANET Mobile Ad Hoc NETwork
MPR MultiPoint Relay
NAIF Neighborhood-Aware Interest Forwarding
NDN Named Data Network
NFD Ndn Forwarding Daemon
OLSR Optimized Link State Routing
OSPF Open Shortest Path First
PAF Provide-Aware Forwarding
PID content Packet IDentifier
PIT Pending Interest Table
QMRS QoS Multipath Routing with Route Stability
QoS Quality of Service
RREP Route REPly
RIP Routing Information Protocol
RREQ Route REQuest
RTT Round-Trip Time
TBRPF Topology Broadcast based on Reverse-Path Forwarding
TLV Type-Lenght-Value
ZRP Zone Routing Protocol
Sımbolos
t tempo s
v velocidade m/s
xix
Capıtulo 1
Introducao
1.1 Enquadramento
As redes Mobile Ad hoc Network (MANET) [2] sao compostas por nos moveis, que
tem a capacidade de, autonomamente, criar uma rede de comunicacoes entre eles sem
assistencia de um ponto de acesso, contrariamente as redes de infraestrutura. A co-
municacao e sem fios e ocorre diretamente entre os nos vizinhos localizados no mesmo
raio de alcance. Os nos da rede sao, simultaneamente, sistemas terminais e encami-
nhadores, ja que participam no processo de encaminhamento (multi-hop), para que os
pacotes possam ser transmitidos desde a fonte ate ao destino, passando por varios nos
intermedios. No entanto, a topologia da rede e muito dinamica, devido a mobilidade dos
nos, a entrada e saıda de nos na rede e as quebras de ligacoes constantes, que provocam
alteracoes inesperadas das rotas. Assim, o principal problema deste tipo de redes e lidar
com essa dinamica, pois existe a necessidade do conhecimento da topologia da rede, total
ou parcial, para o calculo das melhores rotas. Como tal, frequentes mudancas na topo-
logia tem um impacto direto sobre o desempenho dos protocolos de encaminhamento.
Alem disso, o meio de comunicacoes sem fios e partilhado entre os nos vizinhos, o que
pode originar colisoes se dois ou mais nos transmitirem simultaneamente.
O paradigma dos dados nomeados (NDN - Named Data Networks) [7] pode contri-
buir para minimizar alguns dos problemas das redes Ad hoc. As NDNs constituem uma
alternativa as redes IP, apontada como uma das mais promissoras arquiteturas de rede
da Internet do futuro. Este novo paradigma baseia-se na subscricao e publicacao de
conteudos. Os utilizadores (consumidores de informacao) apenas tem que saber qual o
conteudo (nome) pelo qual tem interesse, nao sendo necessario conhecer a sua localizacao
1
Capıtulo 1. Introducao 2
(endereco). Para obter a informacao que deseja, o consumidor propaga um pacote de
interesse, atraves da rede. Quando este atinge um no produtor ou um no intermedio, que
possua o conteudo em cache, os dados sao devolvidos pelo caminho inverso. Apesar do
encaminhamento de trafego, tal como e utilizado nas redes IP tradicionais, perder algum
do seu protagonismo, ele continua a ser necessario, pelo menos na propagacao pela rede
dos pacotes de interesse, que nao interessa que seja feita de forma indiscriminada.
A abordagem NDN pode ser particularmente benefica num ambiente de rede Ad
hoc. Os nos passam a comunicar com base nos dados que precisam, em vez de calcu-
larem um caminho especıfico para chegarem a um no especıfico. Isto pode simplificar
muito a implementacao, por varias razoes. Em primeiro lugar, nao e necessario atribuir
enderecos IP a cada no; em vez disso, os nos podem usar os nomes dos dados, direta-
mente, para transmitirem pacotes de interesses e de dados entre si. Em segundo lugar,
os pacotes de interesse podem ser encaminhados atraves de multiplas rotas para poten-
ciais produtores de dados [1]. Esta abordagem multipath e particularmente benefica em
redes Ad hoc, porque remove a dependencia crıtica sobre caminhos unicos calculados e,
por isso, diminuiu as exigencias rigorosas sobre as atualizacoes de rotas e a coerencia do
estado de encaminhamento entre todos os nos. Outro benefıcio das NDNs para redes
moveis e a capacidade de lidar com a fragmentacao dos dados. As NDNs permitem o
armazenamento em cache, mesmo quando os caminhos nao sao estaveis, nem previsıveis.
Dado que qualquer fragmento de informacao tem uma identificacao unica, este pode ser
armazenado em cache, em qualquer no que o encaminhe, e pode ser reutilizado se outros
nos o solicitarem [1].
Fundamentalmente, uma rede Ad hoc pode ser tao dinamica, que gastar recursos
limitados para possuir informacoes de rotas, necessarias a toda a hora, pode nao ser
viavel, e as redes NDN podem diminuir este impacto negativo.
1.2 Objetivos
O principal objetivo deste trabalho e estudar a viabilidade de aplicar o paradigma
das NDNs num contexto de uma rede Ad hoc. Para que este objetivo seja conseguido,
sera necessario dar resposta a um conjunto de desafios, entre os quais se incluem:
• Estudar as redes NDN e as redes Ad hoc;
Capıtulo 1. Introducao 3
• Estudar/adaptar os protocolos de encaminhamento e reenvio de trafego, utilizados
nas redes NDN no contexto de uma rede Ad hoc;
• Construir um cenario, que permita aplicar o paradigma dos dados nomeados numa
rede Ad hoc, utilizando o simulador ndnSIM [8];
• Construir uma estrategia de encaminhamento adequada ao cenario;
• Testar e avaliar os resultados das simulacoes efetuadas no cenario implementado;
• Verificar a viabilidade das redes NDN no contexto de uma rede Ad hoc, usando as
estrategias de encaminhamento propostas.
1.3 Estrutura da dissertacao
Esta dissertacao encontra-se organizada em oito capıtulos. No Capıtulo 1 e feita
uma introducao ao tema desta dissertacao, apresentando-se o enquadramento deste,
bem como os principais objetivos a alcancar.
O estado da arte encontra-se dividido em tres capıtulos: o Capıtulo 2, Capıtulo 3 e
Capıtulo 4.
O Capıtulo 2 aborda o conceito das redes Ad Hoc, o seu funcionamento e os varios
tipos de encaminhamento (encaminhamento plano, que ainda sao classificados em duas
classes: proativas e reativas (on-demand); encaminhamento hierarquico e encaminha-
mento geografico de posicao assistida). Por fim, sao apresentados alguns exemplos dos
varios tipos de protocolos de encaminhamento.
O Capıtulo 3 descreve o conceito das redes NDN, assim como o seu funcionamento
e a descricao das principais estrategias utilizadas neste tipo de redes.
O Capıtulo 4 explica as vantagens das redes NDN num ambiente de rede Ad hoc
e descreve cinco protocolos de encaminhamento, que podem ser usados em redes de
dados nomeados em ambientes wireless Ad Hoc: Listen First, Broadcast Later (LFBL),
Neighborhood-Aware Interest Forwarding (NAIF), Enhanced-Content-centric multiHop
wirelessNETwork (E-CHANET), Blind Forwarding (BF) e Provide-Aware Forwarding
(PAF). Por fim, e apresentada uma comparacao dos cinco protocolos de encaminhamento
abordados.
O Capıtulo 5 apresenta e explica as tres estrategias de encaminhamento, que vao ser
avaliadas no contexto deste trabalho: BFstrategy, DSRstrategy e, por fim, MPRstrategy.
Capıtulo 1. Introducao 4
O Capıtulo 6 apresenta o trabalho desenvolvido para tornar possıvel a construcao
do cenario de uma rede NDN num ambiente Ad Hoc. Em primeiro lugar, e apresen-
tada uma descricao do simulador usado, ndnSIM, pois e necessario compreender todo o
seu funcionamento ao nıvel do encaminhamento. De seguida, e explicado como foram
implementados os varios protocolos de encaminhamento no simulador ndnSIM.
No Capıtulo 7 sao descritos os testes experimentais realizados e os respetivos re-
sultados obtidos das simulacoes efetuadas no cenario implementado. Alem disso, sao
discutidos os benefıcios e os malefıcios da utilizacao de dados nomeados nas redes Ad
hoc.
Por ultimo, no Capıtulo 8, sao apresentas as conclusoes desta dissertacao, resumindo
os objetivos cumpridos e sugestoes de trabalho futuro.
Capıtulo 2
Redes Ad Hoc
As redes moveis Ad Hoc (MANET - Mobile Ad Hoc Network)[9] sao redes sem
fios, que possuem uma configuracao que nao depende de uma infraestrutura fixa, ou
seja, nao ha um no central para o qual convergem todas as informacoes. Assim, todos os
dispositivos da rede funcionam como se fossem um router, encaminhando as informacoes
vindas de dispositivos vizinhos. Os nos numa rede Ad Hoc comunicam sem conexao
pre-determinada e esta comunicacao e independente das outras existentes na rede, de
maneira que, se uma ligacao falhar, seja por perda de conexao ou falha do proprio
dispositivo, as outras ligacoes continuam a funcionar.
A topologia de rede e dinamica e imprevisıvel, devido a mobilidade dos nos. Como
o alcance de transmissao dos nos e limitado, muitas vezes e necessario recorrer a nos
intermedios para reencaminharem os pacotes, para que estes cheguem ao seu destino.
Uma rede Ad Hoc permite que dispositivos moveis possam formar uma rede, em
cenarios onde haja uma necessidade de se instalar rapidamente uma rede de comu-
nicacoes. Normalmente, sao situacoes onde nao ha uma infraestrutura de rede pre-
viamente instalada, ou numa situacao posterior a uma catastrofe natural, em que a
infraestrutura tenha sido destruıda. Algumas das suas aplicacoes possıveis sao: coor-
denacao de resgates em situacoes de desastre, troca de informacoes taticas em campos
de batalha e partilha de informacoes em reunioes e aulas.
2.1 Encaminhamento Ad Hoc
O encaminhamento em redes Ad Hoc enfrenta os problemas da mobilidade dos nos,
principalmente em redes com um grande numero de nos, e com recursos de comunicacao
5
Capıtulo 2. Redes Ad Hoc 6
limitados (por exemplo, largura de banda e energia). Assim, os protocolos de encami-
nhamento para redes sem fios Ad Hoc tem de se adaptar rapidamente as mudancas da
topologia, frequentes e imprevisıveis, e terem em atencao os recurso que utilizam.
Devido ao facto de a largura de banda ser escassa e da populacao numa MANET ser
pequena em comparacao com a Internet de rede fixa, o problema de escalabilidade para
protocolos de encaminhamento de multiplos saltos sem fios deve-se, principalmente, ao
overhead excessivo das mensagens de encaminhamento. Os protocolos de encaminha-
mento usam, geralmente, os algoritmos vetor distancia (DV - distance-vector) ou estado
de ligacao (LS - link-state) [2], que tentam encontrar os caminhos mais curtos para os
destinos.
Os algoritmos DV sao conhecidos, geralmente, por sofrerem de lenta convergencia
de rotas e uma tendencia a criarem loops em ambientes moveis. Os algoritmos LS supe-
ram este problema, mantendo a informacao global da topologia da rede em cada router,
atraves da difusao, periodica, de informacoes de ligacoes entre os seus vizinhos. No
entanto, como em redes moveis existe uma mobilidade frequente dos nos, isto exigiria
uma troca de mensagens de encaminhamento constante, o que levaria a uma sobrecarga
significativa na rede. Numa rede com uma populacao de N nos, a atualizacao do algo-
ritmo LS gera uma sobrecarga na ordem de N2 [2]. Como a largura de banda e limitada,
em grandes redes, as mensagens de encaminhamento iriam acabar por consumir a maior
parte da largura de banda existente e, consequentemente, as aplicacoes iriam ficar blo-
queadas. Assim, reduzir o overhead das mensagens de controlo de encaminhamento
torna-se uma questao fundamental para alcancar a escalabilidade.
Os protocolos de encaminhamento em redes Ad Hoc sao divididos em tres grandes
categorias [2]:
• Encaminhamento plano, que ainda se divide em duas classes: proativas e reativas
(on-demand) [10] [11] [12];
• Encaminhamento hierarquico;
• Encaminhamento geografico de posicao assistida.
Os protocolos de encaminhamento plano adotam um esquema de enderecamento
plano, em que todos os nos, que participam nesta tarefa, tem um papel igual entre
si. Em contraste, o encaminhamento hierarquico atribui, geralmente, diferentes papeis
aos nos da rede [2]. Por fim, o encaminhamento geografico exige que cada no esteja
Capıtulo 2. Redes Ad Hoc 7
equipado com o Sistema de Posicionamento Global (GPS - Global Position System)[2].
Este requisito e muito realista hoje em dia, uma vez que tais dispositivos sao baratos e
podem fornecer uma precisao razoavel.
2.2 Encaminhamento Plano
O encaminhamento plano e dividido em dois grupos: protocolos proativos e proto-
colos reativos.
2.2.1 Protocolos Proativos
Neste tipo de protocolos, as tabelas de encaminhamento estao sempre atualizadas,
atraves do envio periodico de informacoes e atualizacoes entre cada par de nos da rede
[13]. Assim, quando um no fonte tem algo para enviar, pode faze-lo imediatamente, pois
ja tem a tabela de encaminhamento atualizada, fazendo com que nao hajam atrasos na
descoberta de rotas.
No entanto, como nas redes sem fios existe uma constante mobilidade dos nos,
a topologia iria mudar constantemente e, como consequencia, manter as tabelas de
encaminhamento atualizadas torna-se uma tarefa difıcil, havendo a necessidade de um
envio constante de pacotes de controlo para a rede [13].
Devido ao facto de os nos, que constituem as redes Ad Hoc, serem, normalmente,
dispositivos que possuem caracterısticas limitadas, como por exemplo, serem alimentados
a bateria e com limitacoes a nıvel computacional, a exigencia imposta neste tipo de
protocolos pode ser um problema [13].
Exemplos de protocolos proativos sao FSR (Fisheye State Routing), FSLS (Fuzzy
Sighted Link State), OLSR (Optimized Link State Routing) e TBRPF (Topology Broad-
cast based on Reverse-Path Forwarding) [2].
• Fisheye State Routing (FSR)
Fisheye State Routing, descrito em [2] e [14], e um protocolo de encaminhamento
simples, eficiente e do tipo LS, que mantem um mapa da topologia em cada no e pro-
paga as atualizacoes de estado das ligacoes. As principais diferencas entre FSR e o
protocolo LS convencional sao a maneira pela qual as informacoes de encaminhamento
Capıtulo 2. Redes Ad Hoc 8
sao difundidas. Em primeiro lugar, FSR troca toda a informacao de estado das ligacoes
somente com os vizinhos, em vez de difundi-la na rede. No entanto, essa informacao diz
respeito a todos os nos da topologia. Em segundo lugar, a troca do estado das ligacoes
e periodica, em vez de acionada por eventos, o que evita atualizacoes de estado das
ligacoes frequentes, causadas por quebras de ligacoes e mobilidade dos nos. Alem disso,
as transmissoes periodicas de informacoes sobre o estado de ligacao sao conduzidas com
diferentes periodicidades: o estado das ligacoes relativas a nos mais proximos (em termos
de numero de saltos) e difundido mais frequentemente que o estado das ligacoes de nos
mais distantes.
Como resultado, FSR obtem uma distancia e informacoes de rota exatas sobre a
vizinhanca mais proxima de um no, e um conhecimento impreciso do melhor caminho
para um destino distante. No entanto, esta imprecisao e compensada pelo facto de a
rota, em que se desloca o pacote, se tornar progressivamente mais precisa a medida de
que o pacote se aproxima do seu destino.
• Optimized Link State Routing Protocol (OLSR)
O OLSR [15] e um protocolo baseado em LS, que limita a quantidade de nos da
rede que encaminha os estados das ligacoes, a fim de se poder eliminar mensagens
redundantes. Para isso, e utilizada uma tecnica chamada MPR (MultiPoint Relay)
[16]. Numa rede Ad Hoc sem o uso do protocolo OLSR, quando um no recebe um
pacote de controlo, normalmente retransmite esses dados aos nos vizinhos. Desse modo,
ha uma difusao desse pacote na rede, pois todos os nos receberao. Porem, cada um deles
recebera o mesmo pacote diversas vezes de diferentes vizinhos, gerando uma sobrecarga
na rede de informacoes redundantes. O protocolo OLSR tenta eliminar este problema.
No uso do OLSR, o numero de nos que retransmite os pacotes e limitado. Este
protocolo seleciona um subconjunto de nos da rede, chamados Multipoint relay (MPR),
para disseminar mensagens por toda a rede. A escolha do conjunto de MPRs e feita
de modo a que todos os nos a dois saltos de distancia recebam os pacotes [2], com
menor redundancia possıvel, como se pode verificar na Figura 2.1. Entao, quando uma
informacao deve ser atualizada na rede, os pacotes enviados por um no chegarao a
todos os seus vizinhos, mas somente aqueles denominados MPR poderao retransmitir a
informacao. Esse processo repete-se com os proximos nos a receberem os pacotes. Dessa
maneira, cada no recebera apenas uma vez os pacotes de informacao.
Capıtulo 2. Redes Ad Hoc 9
Figura 2.1: OLSR: ilustracao dos MPR, adaptado de [2]
Para calcularem os conjuntos MPR, todos os nos enviam mensagens Hello para os
seus vizinhos, que contem informacao acerca dos seus vizinhos e o estado da ligacao
com eles. O estado da ligacao pode ser unidirecional, bidirecional ou MPR [15]. Estas
mensagens de controlo sao transmitidas em broadcast e sao recebidas pelos vizinhos a
um salto de distancia. Os vizinhos nao retransmitem a mensagem. Cada Hello contem:
• a lista de enderecos para os quais existe uma ligacao bidirecional valida;
• a lista de enderecos dos nos que foram ouvidos pelo no, ou seja, foi recebido um
Hello, mas a ligacao ainda nao esta validada como bidirecional: se um no encontra
o seu proprio endereco numa mensagem Hello, considera que a ligacao para o no
remetente e bidirecional [15].
E esta mensagem Hello que permite que cada no conheca os seus vizinhos a um e
dois saltos de distancia. Com base nesta informacao, cada no executa a selecao dos seus
nos multipoint relays. Estes multipoint relays sao indicados nas mensagens Hello. Com
a rececao das mensagens Hello, cada no pode construir a sua tabela MPR selector, com
os nos que ja foram selecionados como MPRs.
Como se pode verificar na Figura 2.2 (a), sem a utilizacao desta tecnica, quando
um no (no central, cor laranja) quer transmitir uma informacao em broadcast, todos os
nos que receberem o pacote irao retransmiti-lo, formando uma rede semelhante a da
Figura 2.2 (a). Assim, os nos receberao pacotes iguais diversas vezes, vindos de vizinhos
Capıtulo 2. Redes Ad Hoc 10
Figura 2.2: (a) sem OLSR; (b) com OLSR [3]
diferentes, fazendo com que haja sobrecarga na rede, como ja tinha sido referido. Na
Figura 2.2 (b), pode-se observar a rede semelhante a que resultaria se fosse usado o
protocolo OLSR, que contem muito menos retransmissoes de pacotes. Os nos MPR
estao representados a azul e so eles e que retransmitem os pacotes. Assim, todos os nos
receberao a informacao uma unica vez.
O protocolo OLSR e particularmente apropriado para redes de grandes dimensoes.
Quando a rede e pequena, cada vizinho de um no se torna um MPR.
2.2.2 Protocolos Reativos
Ao contrario dos proativos, estes protocolos estabelecem uma rota para o destino
apenas quando o no fonte pretende transmitir pacotes, nao fazendo qualquer tipo de
atualizacoes periodicas [13]. Exemplos de protocolos reativos sao AODV (Ad Hoc On
Demand Distance Vector Routing) [3] e DSR (Dynamic Source Routing)[17] [2].
Estes protocolos tem, normalmente, uma fase de descoberta de rota. O no fonte
envia, em broadcast, um pacote de pedido de rota, que e difundido na rede, ate chegar
ao destino ou a um no que conheca a rota para o destino. A fase e concluıda quando
uma rota e encontrada ou todos os possıveis caminhos de saıda da fonte sao pesquisados.
Existem diferentes abordagens para descobrir rotas nos algoritmos reativos. No pro-
tocolo AODV, ao receber um pedido de rota, os nos intermedios “aprendem” o caminho
para a fonte e inserem-no na tabela de encaminhamento. O destino recebe, eventual-
mente, o pedido de rota e pode, assim, responder, usando o caminho inserido no pedido
de rota. Isto permite a criacao de um caminho full duplex [2].
Um esquema alternativo para tracar caminhos reativos e o protocolo Dynamic Source
Routing. O DSR usa source routing, isto e, uma fonte regista, no cabecalho do pacote,
a sequencia de nos intermedios que o pacote tem de percorrer para chegar ao destino.
Capıtulo 2. Redes Ad Hoc 11
O destino, em seguida, recupera todo a rota do pacote e usa-a, inversamente, para
responder a fonte.
O source routing permite que nos DSR mantenham multiplas rotas para um destino.
Quando uma falha de ligacao e detetada, a reconstrucao da rota pode ser adiada, caso
a fonte possa usar uma outra rota valida. Se nao existirem tais rotas alternativas, deve
ser invocada uma pesquisa para uma nova rota. O facto de o caminho estar incluıdo no
cabecalho do pacote, permite fazer a detecao de loops.
Para reduzir a sobrecarga de pesquisa de rotas, ambos os protocolos fornecem oti-
mizacoes, aproveitando as informacoes de rotas existentes nos nos intermedios.
2.3 Encaminhamento Hierarquico
Normalmente, quando uma rede sem fios aumenta de tamanho (para alem de certos
limites), os esquemas de encaminhamento proativos e reativos tornam-se inviaveis, de-
vido ao overhead da descoberta de rotas e de processamento. Uma maneira de resolver
este problema e a producao de solucoes escalaveis e eficientes, atraves da utilizacao de
um protocolo de encaminhamento hierarquico.
Os protocolos de encaminhamento hierarquicos sem fios baseiam-se na ideia de or-
ganizar os nos em grupos e, em seguida, atribuir diferentes funcionalidades aos nos,
dependendo se este esta dentro ou fora de um grupo. Tanto o tamanho das tabelas de
encaminhamento, como o tamanho dos pacotes de atualizacoes sao reduzidos, incluindo
neles apenas uma parte da rede.
A forma mais popular de construcao da hierarquia e a de grupos de nos geogra-
ficamente proximos uns dos outros em clusters explıcitos. Cada cluster tem um no
principal (clusterhead), que comunica com os nos de outros grupos, em nome do cluster.
Uma forma alternativa e ter uma hierarquia implıcita. Deste modo, cada no tem um
alcance local. Diferentes estrategias de encaminhamento sao usadas dentro e fora do
alcance da aplicacao. Atraves desta flexibilidade, pode ser alcancado um desempenho
de encaminhamento global mais eficiente.
Exemplos de protocolos hierarquicos sao HSR (Hierarchical State Routing) [18],
CGSR (Clusterhead-Gateway Switch Routing)[19], ZRP (Zone Routing Protocol) e LAN-
MAR (Landmark Ad Hoc Routing Protocol) [12] [2].
Capıtulo 2. Redes Ad Hoc 12
2.3.1 Zone Routing Protocol (ZRP)
ZRP [11] e um protocolo de encaminhamento hıbrido, que combina os protocolos
proativos e reativos, com o objetivo de tirar o benefıcio das vantagens no encaminha-
mento de ambos os tipos. A ideia basica e que cada no tem uma zona predefinida
centrada em si mesmo, em termos de numero de saltos. Para enviar pacotes para nos
dentro da zona, usa protocolos de encaminhamento proativos, mantendo as informacoes
de encaminhamento atualizadas. Para os nos fora da sua zona, usa protocolos de enca-
minhamento reativos, que nao mantem a informacao de encaminhamento.
Para nos fora da sua zona, este protocolo faz a pesquisa de rota atraves dos pacotes
RREQ (Route Request) e a respetiva resposta RREP (Route Reply), de uma forma
similar aos protocolos de encaminhamento reativos tıpicos.
2.4 Encaminhamento Geografico de posicao assistida
Os avancos no desenvolvimento do GPS tornaram possıvel o fornecimento de in-
formacoes de localizacao com uma precisao de poucos metros. [2] Alem disso, tambem
fornece uma sincronizacao temporal universal. Embora as informacoes de localizacao
possam ser usadas para o encaminhamento direcional em sistemas distribuıdos Ad Hoc,
o relogio universal (fornecido, tambem, pelo GPS) pode fornecer sincronizacao global
entre nos equipados com GPS.
A pesquisa feita pelos autores de [2] mostrou que as informacoes de localizacao
geografica podem melhorar o desempenho de encaminhamento em redes Ad Hoc.
Exemplos de protocolos geograficos de posicao assistida sao GeoCast (Geographic
Addressing and Routing) [20], LAR (Location-Aided Routing) [21], DREAM (Distance
Routing Effect Algorithm for Mobility) e GPSR (Greedy Perimeter Stateless Routing)
[22].
2.4.1 LAR (Location-Aided Routing)
O protocolo LAR, apresentado em [21], e um protocolo on-demand baseado em
source routing [2]. O protocolo utiliza informacoes de localizacao, a fim de limitar a area
da zona de descoberta de uma nova rota. Como consequencia, o numero de mensagens
de pedido de rota e reduzido.
Capıtulo 2. Redes Ad Hoc 13
O funcionamento do protocolo LAR e semelhante ao DSR [17]. Usando informacoes
de localizacao, o protocolo LAR executa a descoberta de rota atraves de flooding limitado
(isto e, inunda os pedidos para uma Request zone). Somente nos da Request zone irao
encaminhar os pedidos de rota. O protocolo LAR fornece dois esquemas para determinar
a Request zone.
Esquema 1: A fonte estima uma area circular (Expected zone), na qual se espera
que o destino seja encontrado naquele momento. A posicao e o tamanho do cırculo e
calculado com base no conhecimento da localizacao anterior do destino, o instante de
tempo associado ao registo de localizacao anterior e a velocidade media do destino. A
menor regiao retangular que inclui a Expected zone e a fonte e a Request zone, como se
pode verificar na Figura 2.3. As coordenadas dos quatro cantos da Request zone estao
ligados a um pedido de rota pela fonte. Durante a difusao do pedido de rota, so nos
dentro da Request zone reencaminham a mensagem de pedido.[2]
Figura 2.3: Funcionamento do protocolo LAR: (a)Esquema 1 [2]
Esquema 2: A fonte calcula a distancia para o destino, com base na distancia entre
esta e a localizacao conhecida do destino. Esta distancia, juntamente com a posicao do
destino, e incluıda na mensagem de pedido de rota e enviada para os vizinhos. Quando
um no recebe o pedido, calcula a sua distancia ate ao destino. Se a sua distancia ate ao
destino for inferior ou igual a distancia incluıda na mensagem de pedido, reencaminha a
mensagem de pedido. Caso contrario, nao reencaminha. Como exemplo, na Figura 2.4
Capıtulo 2. Redes Ad Hoc 14
os nos I e J irao retransmitir o pedido de S. Antes de retransmitir o pedido, o no
atualiza o campo de distancia, na mensagem de pedido, com a sua propria distancia
para o destino.[2]
Figura 2.4: Funcionamento do protocolo LAR: (b)Esquema 2. [2]
Capıtulo 3
Redes de Dados Nomeados
Com a evolucao e crescente utilizacao da Internet, surgiram alguns problemas com
o aumento do trafego, como a seguranca, escalabilidade, qualidade de servico e de-
pendencia da localizacao. Para se tentar resolver estes problemas, surgiu uma nova
arquitetura: as redes de Dados Nomeados.
O projeto de Redes de Dados Nomeados (NDN – Named Data Network) [7] propos
uma evolucao da arquitetura IP, inovando o paradigma de difusao de mensagens na
rede. Atribui nomes aos dados, fazendo com que a entrega passe a ser efetuada com
base na informacao que transportam, e nao na sua localizacao, como acontece utilizando
o paradigma normal de entrega entre uma origem e um destino.
A comunicacao em NDN e feita atraves de consumidores e produtores de dados,
atraves da troca de dois tipos de pacotes: Interesses e Dados. Ambos os tipos de
pacotes transportam, no seu cabecalho, um nome (prefixo), que identifica os dados ou
apenas uma parte. O consumidor coloca o nome dos dados desejados no pacote de
interesse e propaga-o na rede. Os nos intermedios usam este nome para encaminharem
o interesse para o(s) produtor(es) de dados. Quando o interesse atingir um no que
possua os dados solicitados, o no ira retornar um pacote de dados, que contem o nome
e o conteudo, juntamente com a assinatura do produtor. Este pacote de dados segue o
caminho inverso tomado pelo interesse, a fim de voltar para o consumidor que o solicitou.
15
Capıtulo 3. Redes de Dados Nomeados 16
3.1 Estrutura do no NDN
Para exercer as funcoes de encaminhamento dos pacotes de dados e de interesse, cada
no NDN possui tres estruturas de dados: uma tabela de interesses pendentes (PIT - Pen-
ding Interest Table), uma tabela com informacoes de encaminhamento (FIB - Forwarding
Information Base) e, por fim, uma tabela com o armazenamento de conteudos (CS –
Content Store), descritas em detalhe em [23].
A FIB e usada para encaminhar pacotes de interesse em direcao a potenciais fontes
dos dados correspondentes. E quase identica a uma tabela de encaminhamento IP, com
a diferenca que a FIB permite ter uma lista de interfaces de saıda, em vez de uma unica.
A CS e uma cache temporaria de dados recebidos pelo no. Depois de encaminhar
os pacotes de dados, um router NDN armazena os mesmos, a fim de poder responder
a futuros interesses. O armazenamento e um dos mecanismos mais atrativos que foi
proposto pelas redes NDN, pois este significa a reducao da latencia e a reducao do
custo da largura de banda. Os routers atuais da Internet nao armazenam os conteudos
que passam por eles, pois nao estao habilitados para a reutilizacao dos dados. Esta
caraterıstica traz benefıcios essencialmente para as redes sem fios [24].
A tabela PIT armazena todos os pacotes de interesse que um no tenha encaminhado
(tanto tenha sido o produtor do pacote de interesse ou apenas um no intermedio), e que
ainda nao tenha recebido o respetivo pacote de dados. Em cada entrada PIT e registado
o nome dos dados, juntamente com as suas interfaces de entrada e saıda [24]. Desta
forma, e registada a rota do interesse, para quando os nos receberem o pacote de dados
correspondente, enviarem-no pela interface por onde o interesse chegou.
3.2 Nomes
As NDNs apresentam uma estrutura de nomes organizada hierarquicamente, que e
composta por um determinado numero de componentes relacionados entre si. O nome
dos dados nao corresponde ao nome do ficheiro ou ao nome de parte dele. A sua notacao
e semelhante as URLs, em que o caractere “/” delimita os componentes [24].
No exemplo “uminho.pt/di/vıdeos/frame.mpg/1/2”, “uminho.pt/di/vıdeos/frame.mpg”
corresponde ao nome gerado pela aplicacao e “1/2” corresponde ao segmento 2 da versao
1 do ficheiro [4].
Capıtulo 3. Redes de Dados Nomeados 17
As convencoes de nomenclatura e os mecanismos de descoberta dos nomes sao geri-
dos pelas proprias aplicacoes [4]. Sao utilizados algoritmos determinısticos para chegar
ao nome, com base em informacoes que estao disponıveis, tanto para produtores como
para consumidores [24].
3.3 Seguranca
Em contraste com a arquitetura TCP/IP, que deixa a responsabilidade pela segu-
ranca (ou falta dela) para os terminais, as redes NDN protegem os dados em si, obrigando
os produtores de dados a assinarem, criptograficamente, cada pacote de dados [25]. A
assinatura do autor garante a integridade e permite ao consumidor determinar de onde
vem os dados.
A seguranca centrada nos dados do NDN tem aplicacoes no controle de acesso aos
dados e seguranca da infraestrutura. As aplicacoes podem controlar o acesso aos dados,
por meio de cifragem (encriptacao de dados) e distribuicao das chaves encriptadas dos
dados, limitando o perımetro de seguranca por onde os dados podem circular.
O encaminhamento de multiplos caminhos do NDN, em conjunto com o modulo de
estrategia de encaminhamento adaptativo, diminui os ataques por hijacking, que consiste
em interceptar uma sessao TCP iniciada entre duas maquina a fim de a desviar, porque
os nos podem detectar anomalias causadas por estes ataques e recuperarem os dados,
atraves de caminhos alternativos [23].
Devido ao facto de os pacotes NDN referenciarem o conteudo em vez dos dispositivos
de onde provem, e mais complicado para um no malicioso atacar um dispositivo em
particular [26].
O estado de uma tabela PIT tambem pode ajudar a mitigar ataques DDoS - Distri-
buted Denial Of Service, porque o numero de entradas PIT e um indicador explıcito da
carga do no. Colocando um limite superior para este numero, define o limite maximo
para o efeito de um ataque DDoS.[27].
No entanto, as redes NDN ainda nao sao totalmente seguras, e ainda existem al-
guns problemas de seguranca [28]. Um exemplo disso sao as consequencias da utilizacao
do armazenamento em cache, que, apesar de melhorarem o desempenho, guardam in-
formacoes da comunicacao, que podem vir a ser utilizadas por atacantes.
Capıtulo 3. Redes de Dados Nomeados 18
3.4 Encaminhamento NDN
O processo de encaminhamento de pacotes de interesse e dados nas redes NDN esta
representado na Figura 3.1.
Figura 3.1: Processo de Encaminhamento NDN
Quando um no recebe um pacote de interesse, este verifica na sua CS se contem
os dados correspondentes ao interesse e, caso possua, retorna o pacote de dados para a
interface a partir da qual o interesse chegou. Caso contrario, o no procura o nome dos
dados na sua PIT e, caso exista uma entrada correspondente, regista, simplesmente, a
interface de entrada do interesse, nessa entrada. Caso contrario, cria uma nova entrada
com o nome e interface de entrada e saıda do pacote de interesse e encaminha-o para
o produtor, com base nas informacoes da FIB. Quando um no recebe interesses com
o mesmo nome de varios nos, encaminha, apenas, o primeiro pacote recebido, para o
produtor de dados.
Capıtulo 3. Redes de Dados Nomeados 19
A estrategia de encaminhamento pode decidir abandonar um interesse em certas
situacoes, como por exemplo, se todas as ligacoes estiverem congestionadas ou o interesse
e suspeito de fazer parte de um ataque DoS (Denial of Service – ataque de negacao de
servico). Para cada interesse, a estrategia de encaminhamento decide quando e para
onde o encaminhar.
Quando um no recebe um pacote de dados, procura a entrada PIT correspondente,
armazena os dados na CS e encaminha para todas as interfaces listadas nessa entrada
PIT. De seguida, remove a entrada PIT. Caso nao encontre nenhuma entrada PIT
correspondente, descarta o pacote de dados. No entanto, existe a possibilidade de um
no nunca receber o pacote de dados correspondente ao interesse de uma entrada PIT,
por diversas razoes e, por isso, e definido um temporizador e, caso o pacote nao seja
recebido durante esse perıodo, a entrada PIT e removida.
Como os pacotes de dados percorrem sempre o caminho inverso dos pacotes de
interesse e, caso nao hajam pacotes perdidos, um pacote de interesse resulta, apenas,
num pacote de dados em cada ligacao, proporcionando um equilıbrio de fluxo.
Para o encaminhamento de dados de elevadas dimensoes, em vez de ser enviado um
pacote com um payload muito grande, a mensagem e fragmentada em varios pacotes.
Neste caso, o pacote de interesse fornece um papel similar aos ACKs TCP no controlo de
fluxo de trafego na Internet de hoje: um ciclo de feedback, controlado pelo consumidor,
em que o envio do interesse do segundo fragmento, significa que o consumidor recebeu,
com sucesso, o primeiro fragmento [24].
3.5 Utilizacao de protocolos de encaminhamento em redes
NDN
A troca de interesses e dados simetrica e o estado de encaminhamento na rede,
permitem uma caracterıstica unica de NDN - o encaminhamento adaptativo [23] [29].
Um no espera que um pacote de dados chegue, pela mesma interface pela qual transmitiu
o interesse correspondente, dentro de um perıodo razoavel de tempo (por exemplo, o
tempo de ida e volta). Caso contrario, deve esperar um tempo limite ou receber um
pacote NACK, como proposto pelos autores de [23], o que sinaliza uma falha dessa
tentativa. Apos a deteccao de uma falha, o no pode, entao, enviar o interesse para
outras interfaces, a fim de explorar caminhos alternativos.
Capıtulo 3. Redes de Dados Nomeados 20
Assim, o plano de encaminhamento de uma rede NDN e capaz de detetar e recuperar-
se de falhas na rede por conta propria, permitindo que cada router NDN lide com falhas
da rede local, sem depender da convergencia do encaminhamento global [30]. Este novo
recurso levou aos autores de [30] a reexaminarem o papel dos protocolos de encaminha-
mento numa rede NDN: sera que ainda precisa de um protocolo de encaminhamento?
Atraves de analises e simulacoes extensivas, os autores mostraram que os protocolos
de encaminhamento continuam a ser altamente beneficos numa rede NDN.
O protocolo de encaminhamento divulga a topologia inicial e informacoes de polıticas,
bem como as alteracoes de longo prazo e, por fim, calcula a tabela de encaminhamento,
para orientar o processo de encaminhamento. No entanto, devido ao facto de o plano
de encaminhamento ser capaz de detetar e recuperar de falhas rapidamente, o protocolo
de encaminhamento ja nao precisa de lidar com taxas de sobrecarga de atualizacoes a
curto prazo na rede [30]. E isto pode melhorar, significativamente, a sua escalabilidade
e estabilidade.
Capıtulo 4
Ad Hoc via NDN
As redes Ad Hoc tem a vantagem de permitir que dispositivos moveis estabelecam,
rapidamente e sem assistencia de um ponto de acesso, uma rede de comunicacao entre
eles, que potencie a utilizacao de diversos servicos. Normalmente, sao situacoes onde
nao ha uma infraestrutura de rede previamente instalada, ou numa situacao posterior
a uma catastrofe natural, em que a infraestrutura tenha sido destruıda. Algumas das
suas aplicacoes possıveis sao: coordenacao de resgates em situacoes de desastre, troca
de informacoes taticas em campos de batalha e partilha de informacoes em reunioes e
aulas.
No entanto, este tipo de redes tem uma topologia de rede muito dinamica, devido a
mobilidade dos nos, a entrada e saıda de nos na rede e as quebras de ligacoes constantes,
que provocam alteracoes inesperadas das rotas. Alem disso, o meio de comunicacoes
sem fios e partilhado entre os nos vizinhos. Assim, os protocolos de encaminhamento
necessitam de conhecer a topologia da rede, total ou parcial, para o calculo das melhores
rotas. Como tal, frequentes mudancas na topologia tem um impacto direto sobre o de-
sempenho destes protocolos. Como este tipo de redes tem varias vantagens, foi pensado
em conciliar as abordagens das redes de dados nomeados e das redes Ad Hoc, a fim de
se tentar contornar os seus problemas.
A abordagem NDN pode ser particularmente benefica num ambiente de rede Ad
Hoc. Os nos moveis podem comunicar com base nos dados que precisam, em vez de
determinarem um caminho especıfico para chegarem a um no especıfico. Isto pode sim-
plificar muito a implementacao, por varias razoes. Em primeiro lugar, nao e necessario
atribuir enderecos IP a cada no; em vez disso, os nos podem usar os nomes dos dados,
diretamente, para transmitirem pacotes de interesses e de dados entre si. Quando um
21
Capıtulo 4. Ad Hoc via NDN 22
no A tem algo para enviar, determinado por uma aplicacao especıfica, anuncia os da-
dos usando o nome dos dados nomeados. Quando um no R precisa de alguns dados,
simplesmente envia um pacote de interesse, usando o nome dos dados da aplicacao cor-
respondente. Outros nos, que recebam o pacote de interesse, tem de decidir se o enviam
no sentido de A (produtor), ou se transmitem o pacote em broadcast [1]. Esta decisao e
regida pelas configuracoes e polıticas de controlo local [1].
Em segundo lugar, os pacotes de interesse podem ser encaminhados atraves de
multiplas rotas para potenciais produtores de dados [1]. No caso de os dados solicitados
serem recebidos atraves de multiplos caminhos, um no pode avaliar qual o caminho que
apresenta o melhor desempenho e enviar um pacote de interesse futuro, para a mesma
fonte de dados, apenas atraves desse caminho [1]. Esta abordagem multipath e particu-
larmente benefica em redes Ad Hoc, porque remove a dependencia crıtica sobre caminhos
unicos pre-calculados e, por isso, diminuiu as exigencias rigorosas das atualizacoes de
rotas e a coerencia do estado de encaminhamento entre todos os nos.
Fundamentalmente, uma rede Ad Hoc pode ser tao dinamica, que gastar recursos
limitados para possuir informacoes de rotas, necessarias a toda a hora, pode nao ser
viavel, e as redes NDN podem diminuir este impacto negativo.
Outro benefıcio das NDNs para redes moveis e a capacidade de lidar com a frag-
mentacao dos dados. As tecnicas de transparent caching, em redes moveis, sao ineficazes,
porque funcionam apenas em redes fixas, assumindo que as rotas permanecem estaveis
[1]. Outras tecnicas de cache, tal como byte caching, que sao executadas na camada de
rede, em vez de na camada de transporte, sofrem das mesmas limitacoes. Estas podem
ser executadas somente quando as rotas sao estaveis e os nos sabem o caminho exato
que o pacote vai seguir, uma exigencia que nao pode ser satisfeita em ambientes moveis
[1].
Em contraste, as NDNs permitem o armazenamento em cache, mesmo quando os
caminhos nao sao estaveis nem previsıveis. Dado que qualquer fragmento de informacao
tem uma identificacao unica, este pode ser armazenado em cache, em qualquer no que
o encaminhe, e pode ser reutilizado se outros nos o solicitarem. Por exemplo, se houver
uma transferencia de um ficheiro MPEG demorada, sobre HTTP dentro de uma rede
movel, nenhum dos nos intermedios na rede movel sera capaz de armazenar em cache
todo o arquivo, assumindo que os pacotes vao seguir caminhos diferentes. Nas redes
NDN, os diferentes fragmentos de dados do mesmo ficheiro MPEG possuem um nome
Capıtulo 4. Ad Hoc via NDN 23
exclusivo e, portanto, quando um no solicita o arquivo, os nos intermedios podem arma-
zenar todas as partes do ficheiro MPEG que passar por eles. Os pedidos subsequentes
para o mesmo ficheiro MPEG, ou pedidos de retransmissao de algumas partes do fi-
cheiro, podem, entao, ser servidos pelas copias das varias partes do ficheiro que foram,
oportunisticamente, armazenadas nos nos intermedios.
Finalmente, as NDNs sao perfeitamente adequadas, para permitirem a comunicacao
em cima de qualquer tipo de rede, uma exigencia tao crucial nas redes moveis, onde
o estado de conectividade de rede pode variar de “quase sempre ligado” a “conectados
intermitentemente” [1]. Alem disso, as NDNs permitem a implementacao de uma grande
gama de protocolos, que vao desde o tempo real, a protocolos tolerantes a atrasos, dentro
da mesma estrutura [1]. Nas redes NDN, os nos moveis nao precisam de detetar o seu
estado de conectividade e, consequentemente, ajustar a sua modalidade de comunicacao
com base nas condicoes atuais da rede. Por exemplo, um no movel, que foi originalmente
ligado atraves de uma rede celular 3G, pode transitar para uma rede peer-to-peer, quando
se move para fora do alcance da rede 3G, sem a necessidade de alterar a sua modalidade
de comunicacao [1].
De seguida, sao descritos cinco protocolos de encaminhamento (LFBL, NAIF, E-
CHANET, BF e PAF), que podem ser usados em redes de dados nomeados em ambientes
wireless Ad Hoc.
4.1 Protocolo LFBL
Listen First, Broadcast Later (LFBL) e um protocolo de encaminhamento para redes
sem fios, proposto em [31], capaz de lidar com a alta dinamica das redes Ad Hoc e que nao
exige rotas pre-determinadas, enderecamento IP, ou uma camada MAC com capacidade
para transmitir em unicast. Este protocolo usa o conceito de dados nomeados. Esta
combinacao permite que o LFBL lide, perfeitamente, com duas situacoes existentes em
redes dinamicas: mobilidade fısica dos nos e mobilidade logica dos dados.
A facilidade que este protocolo tem em lidar com a mobilidade fısica dos nos sig-
nifica que o seu desempenho nao e dependente do tipo ou da frequencia de alteracoes
topologicas da rede. Quanto a mobilidade logica, significa que os pedidos de dados nao
precisam de ser direcionados a um no especıfico, pois e possıvel obter uma resposta
atraves de qualquer outro no, que possua os dados solicitados.
Capıtulo 4. Ad Hoc via NDN 24
A comunicacao no LFBL e composta por duas fases: uma fase de pedido e uma fase
de dados.
• Fase de pedido
A fase de pedido e semelhante as fases de pedido de rota dos protocolos on-demand.
O LFBL usa uma abordagem centrada nos dados. Os consumidores solicitam os dados
que estao interessados, pelo seu nome, atraves de um pacote REQ. O LFBL utiliza,
exclusivamente, a comunicacao em broadcast para todos os pacotes [31], tornando-se
uma opcao mais natural para um meio sem fios, permitindo uma maior flexibilidade na
selecao de protocolos da camada MAC.
Caso o consumidor tenha conhecimento previo de quem e o produtor, o pacote de
solicitacao e enderecado para ele. Caso contrario, o pacote e difundido pela rede, de
forma a garantir que qualquer produtor disponıvel seja encontrado, e que seja feita uma
distribuicao de informacoes de distancia, para que outros nos na rede possam aprender
a sua distancia ate ao consumidor.
Cada no que receber o pacote REQ decide se pode responder ao pedido, verificando
se contem os dados desejados. Caso nao possua os dados, o recetor tem duas decisoes
importantes a fazer: se a sua retransmissao beneficiara o encaminhamento do pacote e,
nesse caso, qual o perıodo de tempo que e necessario esperar, antes de o encaminhar.
O recetor tenta perceber se esta mais perto do destino do que o no que lhe enviou
o pacote. Para isso, verifica o cabecalho do pacote, que possui um campo designado
por srcDist, que contem a distancia entre o no origem do pacote e o encaminhador mais
recente, modificado em cada salto. Em cada salto, os recetores inserem a sua propria
distancia ate ao consumidor nesse campo, antes de reencaminharem o pacote. Os nos
usam esse campo, tambem, para descobrirem e atualizarem a sua distancia ate aos nos
ativos na rede.
Antes do encaminhamento, cada no escolhe um certo perıodo de tempo para esperar
e ver se os outros nos encaminham o mesmo pacote. Este perıodo, que serve para o no
escutar o meio, tem duas finalidades importantes: priorizacao e evitar colisoes entre nos
intermedios.
Priorizacao e atribuir perıodos de escuta mais curtos para nos que acreditam que
estao numa rota melhor, em relacao aos seus vizinhos, entre o consumidor e o produtor.
Capıtulo 4. Ad Hoc via NDN 25
Prevencao de colisoes significa, simplesmente, reduzir a possibilidade de dois nos
escolherem a mesma duracao para o seu perıodo de escuta, e transmitirem simultane-
amente, causando uma colisao. Adicionar um fator aleatorio para o perıodo de escuta
consegue ser altamente eficaz para este fim, de acordo com as simulacoes feitas pelos
autores. Outra tecnica usada pelos autores foi corresponder este tempo a um perıodo
de tempo relacionado com a sua distancia ate ao vizinho que enviou o pacote.
Quando um produtor recebe o REQ, produz um pacote de resposta (REP). Para
alem dos dados, o REP contem a distancia ate ao consumidor, calculada a partir do
cabecalho do REQ. Esta distancia e usada pelos nos intermedios, para tomarem decisoes
de encaminhamento.
Existe a possibilidade de o consumidor receber mais do que uma resposta ao seu
pedido, mas, nesse caso, pode escolher qual prefere, escolhendo qual o produtor a quem
deseja enviar um aviso de rececao. O produtor que deixar de receber avisos de rececao,
acabara por desistir.
• Fase de dados
A fase de dados comeca quando uma resposta chega ao consumidor e continua ate
que o consumidor termine o envio de pedidos ou nao esteja a receber as respostas aos
seus pedidos. Neste ultimo caso, o consumidor retorna para a fase de pedido.
Numa rede altamente dinamica, a topologia muda constantemente e, por isso, qual-
quer estado, mantido num no, ficaria desatualizado rapidamente. A atualizacao dos
estados iria implicar uma grande sobrecarga na rede. Em contraste, o LFBL acaba
completamente com a nocao de selecao de rota. Para cada fluxo fim-a-fim, os potenciais
encaminhadores LFBL tomam decisoes, com base na sua distancia ate ao destino.
4.2 Protocolo NAIF
Conscientes da sobrecarga excessiva do reenvio de trafego nas NDNs em ambientes
Ad Hoc, os autores de [32] propuseram um mecanismo de propagacao de interesses
adaptativo, designado por NAIF (Neighborhood-Aware Interest Forwarding), que visa
reduzir a sobrecarga da difusao, mantendo a robustez. Em ambos, as transmissoes de
interesses sao efetuadas em broadcast. A logica de NAIF e, em vez de selecionar um no
para transmitir o interesse, nos intermedios propagam os interesses, cooperativamente,
Capıtulo 4. Ad Hoc via NDN 26
entre o consumidor e os potenciais produtores de dados. O algoritmo NAIF e aplicado
apenas para o encaminhamento de interesses em nos intermedios.
O NAIF reduz o encaminhamento de pacotes duplicados, controlando o reenvio de
pacotes de interesse, com base nas estatısticas de transmissao dos nos, que sao usadas,
posteriormente, para ajustar a taxa de transmissao. O controlo de encaminhamento
NAIF baseia-se em dois parametros obtidos nos nos intermedios: a taxa de recuperacao
de dados, que e a razao entre o numero de pacotes de dados, obtidos com sucesso, e o
numero de interesses enviados; e a taxa de transmissao [32]. Estes dois parametros sao
ajustados periodicamente, com base nas estatısticas de encaminhamento.
Um no decide transmitir ou descartar os interesses recebidos, com base na taxa de
transmissao: quantos mais pacotes de dados, com o mesmo prefixo, um no “ouvir” dos
seus vizinhos, mais interesses desse prefixo pode descartar, pois julga-os serem superfluos
[32]. Por outro lado, quando um no deteta que descartou demasiados interesses, aumenta
a sua taxa de transmissao para compensar. Desta forma, os nos intermedios transmitem
os interesses, cooperativamente, reduzindo as situacoes de congestionamento.
Alem disso, sao filtrados os encaminhadores inelegıveis, que sao os nos que possuem
uma taxa de recuperacao de dados baixa e estao muito longe do consumidor. Assim, se
um no considerado inelegıvel receber um interesse, este e descartado.
4.3 Protocolo E-CHANET
E-CHANET (Enhanced-Content-centric multiHop wirelessNETwork) e uma arqui-
tetura centrada em informacoes, proposta em [33], para redes Ad Hoc, que executa
funcoes de routing, reenvio de pacotes e transporte confiavel, especificamente adaptada
para lidar com as limitacoes e exigencias de ambientes sem fios distribuıdos.
O encaminhamento E-CHANET tem dois objetivos: por um lado, visa reduzir o
numero de nos que participam no processo de encaminhamento (e, portanto, o numero
de copias de pacotes), limitando assim o consumo de energia, acelerando a entrega
e economizando os recursos da rede; por outro lado, o objetivo e tirar vantagens da
partilha de conteudo em varios nos, e em lidar com nos moveis.
No E-CHANET, semelhante ao protocolo LFBL, cada pacote e transmitido, consi-
derando o mecanismo de supressao baseado em contagem, para reduzir a probabilidade
de colisoes e limitar as transmissoes em rajada. Tanto as transmissoes de dados, como
de interesses sao adiadas por um perıodo de tempo TData e TInterest, respetivamente.
Capıtulo 4. Ad Hoc via NDN 27
Estes tempos sao escolhidos aleatoriamente, mas de forma a que TData seja menor do que
TInterest, a fim de dar maior prioridade aos pacotes de dados, sobre os interesses. Se um
no “ouvir” que o mesmo pacote esta a ser transmitido por outro no, para um potencial
destino, durante o seu tempo de espera, em seguida, aborta a sua propria transmissao.
Cada no E-CHANET possui as mesmas estruturas de dados que as NDNs: FIB,
PIT e CS. Alem destas, possui tambem uma nova estrutura de dados, chamada CPT
(Content Provider Table), que armazena informacoes sobre o produtor descoberto (ou
seja, o ID do produtor, a distancia ate ele e o RTT medido), com o objetivo de que esta
informacao possa ajudar na decisao do encaminhamento dos interesses.
O encaminhamento E-CHANET e dividido em tres fases: (i) difusao controlada de
interesses, (ii) encaminhamento de dados impulsionado por entradas PIT, e (iii) enca-
minhamento de interesses impulsionado por entradas CPT.
(i) Difusao controlada de interesses:
Um consumidor inicia o processo, transmitindo um interesse. Cada no que receber
o pacote, verifica a sua CS. Se forem encontrados os dados correspondentes, agenda a
transmissao destes, para depois de TData. Caso contrario, procura por uma entrada
correspondente na PIT.
Se nao for encontrada uma entrada correspondente do interesse, o no insere uma
nova entrada na PIT, que inclui, temporariamente, o nome do pacote requisitado e a
distancia para o consumidor. Antes de reencaminhar o pacote, o no verifica a CPT. Se
forem encontradas informacoes sobre um produtor acessıvel para os dados solicitados,
preenche os campos do interesse com essa informacao.
Pelo contrario, se for encontrada uma correspondencia do interesse na PIT, o no
descarta o interesse, pois considera o pacote duplicado, e verifica se a PIT precisa de ser
atualizada.
(ii) Encaminhamento de dados impulsionado por entradas PIT:
Eventualmente, o interesse vai chegar a um (ou mais) produtor(es). E possıvel que
cheguem pedidos redundantes ao produtor e, neste caso, o produtor apenas responde ao
primeiro interesse, enviando os dados correspondentes. O pacote de dados contem o seu
identificador e a sua distancia (numero de saltos) ate ao consumidor, calculada a partir
do campo contagem de saltos do interesse recebido.
Capıtulo 4. Ad Hoc via NDN 28
Cada no que receber o pacote de dados averigua, em primeiro lugar, se possui uma
entrada PIT correspondente. Caso possua, verifica se esta mais proximo do consumidor,
do que o no que lhe enviou o pacote. Se sim, atualiza o campo de distancia no pacote
de dados, com a sua distancia ate ao consumidor. Por fim, adiciona uma nova entrada
(ou atualiza a entrada, se existir) na CPT, com o identificador do pacote de dados e a
sua distancia para o produtor, calculada atraves do campo contagem de saltos, contida
no pacote de dados. Finalmente, o no agenda a transmissao dos dados, para depois de
TData.
Se o no nao estiver mais proximo do consumidor, do que o no que lhe enviou o
pacote, ou nao contiver a entrada PIT correspondente, os dados sao descartados.
(iii)Encaminhamento de interesses impulsionado por entradas CPT:
Ao receber os dados, o consumidor pede os pacotes subsequentes, transmitindo
interesses que anunciam um produtor. Para isso, preenche o cabecalho do interesse com
o ID do produtor descoberto e o numero de saltos ate ele, que vinha no cabecalho do
pacote de dados recebido.
Cada no intermedio que receber o interesse, procura uma correspondencia na sua
Content Store. Se for encontrada e o no for o produtor registado no pacote, envia
imediatamente os dados.
A identificacao do produtor, contida nos pacotes de dados, e utilizada para limitar
os pacotes de dados redundantes na rede. Devido ao meio ser partilhado, varios nos, que
mantem os dados na sua CS, podem responder simultaneamente ao mesmo interesse.
Caso o no intermedio nao possua os dados, procura uma entrada CPT, correspon-
dente ao ID do produtor e ao nome do conteudo registados no pacote. Se o no estiver
mais perto do produtor do que o no que lhe enviou o pacote, atualiza o cabecalho do
interesse com a sua distancia ate ao produtor, e, finalmente, agenda a transmissao do
interesse, para depois de TInterest.
4.4 Protocolo BF
O protocolo Blind Forwarding (BF) e um esquema broadcasting baseado em con-
tadores, que adia a transmissao de interesses e dados, a fim de limitar a probabilidade
de colisoes [5], semelhante aos protocolos LFBL e E-CHANET. Alem disso, aproveita a
escuta de pacotes, para o controlo da redundancia dos mesmos.
Capıtulo 4. Ad Hoc via NDN 29
Em redes Ad Hoc, um consumidor tem, normalmente, muitos vizinhos, que podem
enviar dados ou encaminhar interesses. A retransmissao de interesses e dados e adiada
por um tempo TInterest e TData, respetivamente. Estes valores sao calculados aleatori-
amente e com TInterest > TData, a fim de dar maior prioridade aos pacotes de dados.
TData serve como um temporizador que evita colisoes entre pacotes de dados, enquanto
TInterest serve como um temporizador que evita colisoes entre interesses.
Um no N, que receber um interesse e nao possuir os dados correspondentes, torna-se
num potencial encaminhador. Durante o TInterest, o interesse permanece numa fila de
pacotes atrasados, enquanto o no N escuta o canal: se ouvir os dados solicitados ou
o mesmo interesse varias vezes, γInterest , cancela a transmissao do interesse e apaga
a respetiva entrada PIT. Caso contrario, encaminha o interesse ao fim de TInterest. O
parametro γInterest atua como um threshold, que controla a redundancia de interesses
(para um no que tenha mais do que 3 vizinhos, o valor de γInterest = 1 e suficiente para
permitir a disseminacao do pedido na rede) [5].
O procedimento de envio dos dados, pelo produtor ou qualquer no intermedio, passa-
se de forma semelhante. Quando um no recebe um pacote de dados, verifica, em primeiro
lugar, se tem uma entrada PIT correspondente. Se tiver, escuta o canal: se ouvir os
dados solicitados, cancela a transmissao dos dados. Caso contrario, encaminha-os ao fim
de TData. Se o no nao encontrar nenhuma entrada PIT, significa que os dados nao sao
solicitados e, por isso, o pacote e descartado.
4.5 Protocolo PAF
O protocolo Provide-Aware Forwarding (PAF) e baseado nos protocolos LFBL e
E-CHANET, abordados nas Seccoes 4.1 e 4.3, respetivamente. Assim, os autores de [5]
aproveitaram os princıpios essenciais destes protocolos e implementaram-nos por cima
do esquema BF, abordado na Seccao 4.4.
No protocolo PAF cada no possui uma tabela DT (Distance Table), em adicao as
tabelas NDN convencionais, que inclui, para todos os nomes de conteudos processados,
o identificador do produtor (provider identifier - ID) e a distancia ate ele.
O primeiro interesse e transmitido pelo consumidor C e disseminado na rede, de
acordo com a estrategia BF. Quando o produtor P o receber, responde com um pacote
de dados, que inclui dois campos adicionais: o seu ID unico e a distancia de salto
inicializada a 1.
Capıtulo 4. Ad Hoc via NDN 30
Na rececao dos dados, cada no N que possuir uma entrada PIT do interesse corres-
pondente, armazena na sua DT o nome dos dados, o identificador de P e a distancia
ate ele. De seguida, N incrementa o campo da distancia de salto pacote e programa o
reencaminhamento deste, atraves de TData. A Figura 4.1 esquematiza o procedimento
do reencaminhamento de interesses dos protocolos PAF e BF.
Figura 4.1: Procedimento do reencaminhamento de interesses dos protocolos PAF eBF [5]
Depois de receber os dados, o consumidor inclui a informacao do produtor na sua
DT e envia o proximo interesse, incluindo o ID do produtor e a distancia ate ele.
Gracas a natureza multi-path nativa das redes NDN, pode ser descoberto mais do
que um produtor e, neste caso, C pode selecionar o que se encontrar mais proximo
Capıtulo 4. Ad Hoc via NDN 31
dele [5]. Ao receber um interesse, cada no verifica a DT para descobrir se esta mais
perto do produtor do que o consumidor. Se estiver, atualiza o campo distancia e adia a
transmissao para depois de TInterest [5].
4.6 Comparacao dos Protocolos
Para uma melhor compreensao, na Tabela ?? sao apresentadas as comparacoes dos
cinco protocolos abordados.
Todos os protocolos propostos foram projetados, especificamente, para redes sem
fios com multiplos saltos. O protocolo NAIF tem a particularidade de ser aplicado,
apenas, no encaminhamento de interesses em nos intermedios.
No encaminhamento de pacotes de interesse ou REQ, os protocolos LFBL, E-
CHANET, BF e PAF utilizam uma tecnica, em que, antes de encaminhar o pacote, cada
no espera um determinado tempo aleatorio, para verificar se outros nos encaminham o
mesmo pacote. Os protocolos LFBL e E-CHANET utilizam uma tecnica adicional, que
consiste em fazer com que a escolha do caminho seja efetuada implicitamente, utilizando
o encaminhamento oportunista, baseado nas distancias de destino, estimadas a partir
das retransmissoes. Por fim, o protocolo NAIF utiliza uma estrategia diferente. Aqui,
um no decide transmitir ou descartar os interesses recebidos, com base na taxa de trans-
missao: quantos mais pacotes de dados um no “ouvir” dos seus vizinhos, mais interesses
com o mesmo prefixo ele pode descartar, pois julga-os desnecessarios para que o interesse
seja satisfeito.
No encaminhamento de pacotes de dados, o LFBL e o E-CHANET sao semelhantes,
pois ambos fazem uma escolha criteriosa dos nos vizinhos para expedicao dos dados. Os
protocolos BF e PAF sao, tambem, semelhantes, sendo que o segundo tem um aper-
feicoamento. No protocolo NAIF nao e feito o encaminhamento de dados.
Na supressao de pacotes, os protocolos LFBL, E-CHANET, BF e PAF adiam a trans-
missao de interesses e aproveitam a escuta de pacotes, para o controlo da redundancia
e colisao de pacotes. Alem disso, tanto no LFBL, como no E-CHANET, apenas os nos
que se encontram mais perto do destino de um pacote do que o remetente anterior,
reencaminham o pacote. O E-CHANET ainda utiliza uma outra tecnica, em que se o
interesse especificar um produtor, apenas esse pode enviar os dados. Por fim, o NAIF
faz a supressao de pacotes atraves do ajuste da taxa de transmissao.
Capıtulo 4. Ad Hoc via NDN 32
LFBL NAIF E-CHANET BF PAF
Cenario deaplicacao
Redes sem fioscom multiplossaltos.
Redes sem fioscom multiplossaltos.
Redes sem fioscom multiplossaltos.
Redes sem fioscom multiplossaltos.
Redes sem fioscom multiplossaltos.
Tipos depacotes
REQ, REP Interesse Interesse, Da-dos
Interesse, Da-dos
Interesse, Da-dos
Tabelasdos nos
CS, FIB PIT CS, PIT, FIB,CPT
CS, FIB, PIT CS, FIB, PIT,DT
Encaminh.dos interes-ses/REQ
Faz escutasao meio,para preve-nir colisoes,combinadacom temposde esperaaleatoriose faz umaescolha crite-riosa dos nosvizinhos paraexpedicao dosinteresses.
Baseia-sena taxa detransmissaodos pacotesde dados cor-respondentes.
Faz escutasao meio,para preve-nir colisoes,combinadacom temposde esperaaleatoriose faz umaescolha crite-riosa dos nosvizinhos paraexpedicao dosinteresses.
Faz escutasao meio,para preve-nir colisoes,combinadacom temposde esperaaleatorios.
Semelhanteao encami-nhamento deinteresses BF.
Encaminh.dos da-dos/REP
Faz uma es-colha criteri-osa dos nosvizinhos paraexpedicao dosdados.
- Semelhanteao encami-nhamentode interessesE-CHANET.
Faz escutasao meio,para preve-nir colisoes,combinadacom temposde esperaaleatorios.
Igual a BF,com um aper-feicoamento:faz uma esco-lha criteriosados nos vi-zinhos paraexpedicao dosdados.
Supressaode pacotes
Controlode retrans-missoes combase nadistancia ateao destino eredundanciade pacotes.
Ajusta a taxade trans-missao dosinteressescom base emestatısticas detransmissaodos nos.
Controlode retrans-missoes combase nadistancia ateao destino,redundanciade pacotes eespecificacaode um pro-dutor pararetransmissaodos dados.
Controlode retrans-missoes combase na re-dundancia depacotes.
Controlode retrans-missoes combase na re-dundancia depacotes.
Simulador QualNet QualNet NS-2 ndnSIM ndnSIM
Tabela 4.1: Tabela comparativa dos protocolos LFBL, NAIF, E-CHANET, BF e PAF
Capıtulo 5
Estrategias de encaminhamento
propostas
Neste capıtulo sao apresentadas e descritas as tres propostas de estrategias de enca-
minhamento, que foram implementadas e avaliadas no ambito deste trabalho: BFstra-
tegy, DSRstrategy e MPRstrategy.
Estas estrategias de encaminhamento foram concebidas para redes Ad hoc de da-
dos nomeados, ou seja, tem em conta todos os problemas destes tipos de redes, onde
se destaca as frequentes mudancas na topologia, que tem um impacto direto sobre o
desempenho dos protocolos de encaminhamento.
5.1 Estrategia BFstrategy
A primeira estrategia de encaminhamento proposta, designada por BFstrategy, baseia-
se no protocolo Blind Forwarding (BF), descrito em [5] e ja abordado, anteriormente, na
Seccao 4.4. Esta estrategia tem como objetivo principal adiar a transmissao de interesses
e dados, por um intervalo de tempo determinado. Ao longo desse intervalo de tempo,
o pacote e descartado, caso o no o “oica” na rede, a fim de diminuir a probabilidade
de colisoes. O pacote e descartado, pois considera-se que outro no ja reencaminhou o
pacote e, por isso, o reencaminhamento deste e desnecessario.
Cada no possui uma tabela de interesses atrasados e uma tabela de dados atrasados,
que tem diferentes campos. A estrutura da tabela de interesses atrasados esta repre-
sentada na Figura 5.1 e a estrutura da tabela de dados atrasados esta representada na
Figura 5.2.
33
Capıtulo 5. Estrategias de encaminhamento propostas 34
Figura 5.1: Estrutura da tabela de interesses atrasados dos nos na estrategia BFstra-teggy
Figura 5.2: Estrutura da tabela de dados atrasados dos nos na estrategia BFstrateggy
O campo “ID” e o identificador do interesse na tabela de interesses atrasados, o
campo “prefixo” corresponde ao nome do prefixo do interesse, o campo “validade” indica
a validade do reencaminhamento do interesse (true - valido; false - invalido) e, por fim, o
campo “dados” indica se o no ja recebeu (true) ou nao (false) os dados correspondentes
ao interesse em causa. A estrutura da tabela de dados atrasados e igual a estrutura da
tabela de interesses atrasados, com excecao do ultimo campo “dados”, que nao existe
nesta ultima tabela.
5.1.1 Encaminhamento de interesses
No inıcio, o consumidor envia um interesse Y, sem qualquer tempo de espera.
Quando um no N recebe Y e nao possui os dados correspondentes, este torna-se num
Capıtulo 5. Estrategias de encaminhamento propostas 35
potencial encaminhador. Caso N seja o produtor dos dados correspondentes ou os conte-
nha na sua Content Store, N devolve o pacote de dados, sem qualquer tempo de espera.
Caso contrario, o no N verifica se o interesse corresponde a alguma entrada que ja existe
na PIT. Se corresponder, atualiza a entrada, acrescentando a interface por onde o inte-
resse chegou e descarta-o. Se nao existir na PIT nenhuma entrada para este interesse,
entao o interesse e acrescentado a PIT. De seguida, N insere o interesse Y na tabela de
interesses atrasados: o campo “ID” e igual ao ID mais alto da tabela + 1 (caso a tabela
esteja vazia, e 0); o campo “prefixo” e igual ao nome do prefixo do interesse Y acabado
de chegar; o campo “validade” e igual true; o campo “dados” e igual a false.
Depois disto, e inicializado um temporizador, que estabelece um tempo de espera
para o encaminhamento do interesse, e e calculado atraves da Equacao 5.1.
TInterest = (DW + rand[0, DW ]) ∗DeferSlotT ime (5.1)
DW (Defer Window) e um valor inteiro, que indica o comprimento do intervalo de
tempo. Os autores de [5] concluıram que existe um valor otimo para a DW, ou seja, o
valor de DW influencia o desempenho da estrategia de encaminhamento. No geral, se o
valor de DW for muito pequeno, o RTT (Round-trip Time) e grande, porque os nos sao
forcados a fazerem varias retransmissoes de interesses, para obterem os dados desejados,
devido, essencialmente, ao elevado numero de colisoes. Aumentando o valor da DW, o
RTT e menor, devido a diminuicao das colisoes dos pacotes, mas so ate um certo ponto:
se o tempo de espera for demasiado elevado antes das transmissoes, o RTT aumenta de
novo. Assim, tendo em conta as varias simulacoes feitas pelos autores, foi verificado que
um dos melhores valores para a DW, em varios cenarios, seria o 127 e, por isso, foi esse
o valor utilizado. Quanto ao DeferSlotTime, este e um valor fixo, e e um intervalo de
tempo pequeno. O seu valor, segundo os autores de [5], e 28µs.
Durante o perıodo de TInterest, o interesse Y permanece numa fila de pacotes atra-
sados, enquanto o no N escuta o canal: para todos os interesses X que receber, e feita
uma pesquisa na tabela de interesses atrasados, para averiguar se existem interesses em
espera com o mesmo prefixo. Caso existam, sera mudado o estado de validade destes
para false, para que o encaminhamento destes interesses seja abortado quando TInterest
expirar e o interesse acabado de chegar e descartado. O cancelamento do reencaminha-
mento poderia ser efetuado neste momento, no entanto, se o no recebesse outro interesse
igual, de seguida, nao seria possıvel detetar que se tratava de um interesse duplicado.
Capıtulo 5. Estrategias de encaminhamento propostas 36
Assim, foi decidido que um no espera sempre ate TInterest expirar para efetuar o seu can-
celamento, a fim de poder detetar todos os interesses duplicados, que chegaram nesse
intervalo de tempo.
Caso nao existam interesses em espera com o mesmo prefixo, sera registado o inte-
resse X, acabado de chegar, na tabela de interesses atrasados e, de seguida, e inicializado
o respetivo temporizador com o valor TInterest.
No caso de o no N receber um pacote de dados, e feita uma pesquisa na tabela de
interesses atrasados, para averiguar se existem interesses em espera com o mesmo prefixo
do pacote de dados acabado de chegar. Caso existam, sera mudado o valor do campo
“dados” destes para true, para que estes interesses nao sejam reencaminhados ao fim de
TInterest, pois o no ja possui os dados correspondentes. Caso nao existam interesses em
espera com o mesmo prefixo do pacote de dados acabado de chegar, continua o processo
de rececao de um pacote de dados, que sera explicado mais a frente.
No final de TInterest, o no N verifica, em primeiro lugar, o campo “dados” do inte-
resse Y na tabela de interesses atrasados. Caso esteja a true, significa que o no N ja
recebeu os dados correspondestes durante TInterest e, por isso, nao ha necessidade de
reencaminhar o interesse, pois este ja chegou ao produtor (por outra rota), que, por
sua vez, ja reencaminhou os dados. Assim, o interesse e descartado e o processo de
reencaminhamento de interesses termina.
Caso o campo “dados” do interesse Y esteja a false, o no N verifica o campo “va-
lidade” do interesse Y na tabela de dados. Caso seja true, significa que nao recebeu
nenhum interesse com o mesmo prefixo durante TInterest e, por isso, o no N reencaminha
o interesse Y. Caso o campo “validade” esteja a false, significa que o no N recebeu um ou
varios interesses com o mesmo prefixo durante TInterest, ou seja, o interesse foi, tambem,
reencaminhado por outro no, no raio de alcance de N. Logo, o no N descarta o interesse
Y e apaga a respetiva entrada na PIT.
5.1.2 Encaminhamento de dados
No caso de um no N receber um pacote de dados D, este verifica se tem uma entrada
PIT correspondente. Caso nao tenha, descarta o pacote. Caso tenha, verifica se tem
uma entrada correspondente na Tabela de interesses atrasados, a fim de colocar a true
o campo “dados” desses interesses. De seguida, insere o pacote de dados D na tabela
de dados atrasados: o campo “ID” e igual ao ID mais alto da tabela + 1 (caso a tabela
Capıtulo 5. Estrategias de encaminhamento propostas 37
esteja vazia, e 0); o campo “prefixo” e igual ao nome do prefixo do pacote D acabado
de chegar; o campo “validade” e igual a true.
De seguida, e inicializado um temporizador, que estabelece um tempo de espera
para o encaminhamento dos pacotes de dados, e e calculado a partir da Equacao 5.2.
TData = rand[0, DW − 1] ∗DeferSlotT ime (5.2)
Este tempo de atraso TData e inferior ao tempo de atraso TInterest, para dar uma
maior prioridade ao envio de pacotes de dados.
O passo seguinte e parecido com o encaminhamento de um pacote de interesse.
Durante o perıodo de TData, o pacote D permanece numa fila de pacotes de dados
atrasados, enquanto o no N escuta o canal: para todos os pacotes de dados que receber,
e feita uma pesquisa na tabela de dados atrasados, para averiguar se existem pacotes de
dados em espera, com o mesmo prefixo. Caso existam, sera mudado o estado de validade
destes para false e o pacote acabado de chegar e descartado.
No final de TData, o no N verifica o campo “validade” do pacote D na tabela de
dados. Caso seja true, significa que nao recebeu nenhum pacote de dados com o mesmo
prefixo durante TData e, por isso, o reencaminhamento de D tem de ser efetuado. Assim,
o no N reencaminha o pacote D. Caso seja false, significa que o no N recebeu um ou
varios pacotes de dados com o mesmo prefixo durante TData e, por isso, o no N descarta
o pacote D e apaga a respetiva entrada na PIT.
5.1.3 Desvantagens da BFstrategy
Esta estrategia de encaminhamento foi implementada com o objetivo de combater
os efeitos negativos do fenomeno de broadcast storm. No entanto, como e baseado num
encaminhamento em blind forwarding, nao evita completamente as colisoes de pacotes.
De facto, os pacotes podem colidir se, por exemplo, os potenciais encaminhadores usarem
o mesmo tempo de atraso TInterest e TData, ou se estes tempos forem muito pequenos.
Uma outra desvantagem desta estrategia de encaminhamento e o facto de a pro-
pagacao de pacotes na rede nao poder ser completamente controlada, devido a existencia
de terminais ocultos [5]. Como existe uma elevada quantidade de trafego na rede, exis-
tem nos que nao recebem os pacotes, devido a inibicao do reencaminhamento de pacotes.
Por exemplo, se o no W, que deveria ter reencaminhado para o no Z, receber um pacote
Capıtulo 5. Estrategias de encaminhamento propostas 38
igual, durante os perıodos de TInterest e/ou TData, e se W for o unico possuidor do pa-
cote, que tenha na sua area de cobertura o no Z, Z nao ira receber o pacote. De forma
a tornar esta afirmacao mais clara, foi elaborado um exemplo ilustrativo. Na Figura 5.3
esta representado o cenario da simulacao.
Figura 5.3: Cenario da simulacao usada para mostrar desvantagens da BFstrategy
O cenario e composto por seis nos e, entre eles, existe um produtor e um consumidor.
O produtor e representado pelo no 5 e o consumidor pelo no 0. O modelo de mobilidade
usado foi o Constant Position, ou seja, os nos nao se mexem. Os nos 1, 2, 3 e 4 estao
ao alcance do consumidor. O produtor esta, apenas, ao alcance do no 4.
O tipo de trafego e Constant Bit Rate (CBR), com uma frequencia de envio de
1 interesse por segundo e o primeiro interesse e enviado aos 0 segundos. O tamanho
dos pacotes de dados e de 64 Bytes. Por fim, foi usado um tempo de simulacao de 10
segundos.
A Tabela 5.1 representa tudo o que acontece, passo a passo, na simulacao abordada,
durante o segundo 5.
No passo 1, e enviado o interesse 5, pelo consumidor 0. De seguida, os nos 2, 1, 3 e 4
recebem o interesse, passo 2, 3, 4 e 5, respetivamente. A Figura 5.4 ilustra estes passos.
Capıtulo 5. Estrategias de encaminhamento propostas 39
Passo Tempo[s]
No Debug
1 5 0 Consumidor envia o interesse 5.
2 5.00024 2 Recebe interesse 5. Regista interesse na tabela de interes-ses. Inicia temporizador com um perıodo TInterest, calculadoaleatoriamente, para reencaminhar o interesse 5 posterior-mente.
3 5.00024 1 Recebe interesse 5. Regista interesse na tabela de interesses.Inicia temporizador com um perıodo TInterest, para reenca-minhar o interesse 5 posteriormente.
4 5.00024 3 Recebe interesse 5. Regista interesse na tabela de interesses.Inicia temporizador com um perıodo TInterest, para reenca-minhar o interesse 5 posteriormente.
5 5.00024 4 Recebe interesse 5. Regista interesse na tabela de interesses.Inicia temporizador com um perıodo TInterest, para reenca-minhar o interesse 5 posteriormente.
6 5.07574 3 Temporizador chega ao fim. Verifica a tabela de interesses,para averiguar se o reencaminhamento do interesse e, ainda,valido. Como e valido, reencaminha o interesse 5.
7 5.07598 2 Recebe interesse 5. Verifica a tabela de interesses, para ave-riguar se existe algum interesse em espera com o mesmoprefixo. Como existe, deteta que esta em Loop. Descarta opacote acabado de receber.
8 5.07598 0 Recebe interesse 5. Como e o consumidor do pacote, detetaque esta em Loop. Descarta o pacote acabado de receber.
9 5.07598 4 Recebe interesse 5. Verifica a tabela de interesses, para ave-riguar se existe algum interesse em espera com o mesmoprefixo. Como existe, deteta que esta em Loop. Descarta opacote acabado de receber.
10 5.07598 1 Recebe interesse 5. Verifica a tabela de interesses, para ave-riguar se existe algum interesse em espera com o mesmoprefixo. Como existe, deteta que esta em Loop. Descarta opacote acabado de receber.
11 5.08484 4 Temporizador chega ao fim. Verifica a tabela para averiguarse o reencaminhamento do interesse e, ainda, valido. Comoja nao e, devido ao facto de ter recebido o mesmo interessedurante o perıodo TInterest, descarta o pacote.
12 5.0871 1 Temporizador chega ao fim. Verifica a tabela para averiguarse o reencaminhamento do interesse e, ainda, valido. Comoja nao e, descarta o pacote.
13 5.10325 2 Temporizador chega ao fim. Verifica a tabela para averiguarse o reencaminhamento do interesse e, ainda, valido. Comoja nao e, descarta o pacote.
14 5.25 - Timeout do interesse 5.
Tabela 5.1: Debug da simulacao exemplo
Capıtulo 5. Estrategias de encaminhamento propostas 40
Figura 5.4: Passos 1 ate 5 da experiencia realizada para mostrar desvantagens daBFsrategy
No passo 6, o TInterest do no 3 chega ao fim e este reencaminha o interesse. Os nos 2,
0, 4 e 1 recebem e percebem que este interesse e duplicado e, por isso, alteram o campo
“validade” do interesse 5 para false. A Figura 5.5 ilustra estes passos.
No passo 11, o TInterest do no 4, que era o unico que podia reencaminhar o interesse
para o produtor, chega ao fim. O no verifica a tabela de interesses atrasados, para
averiguar se o reencaminhamento do interesse e, ainda, valido. Como ja nao e, devido
ao facto de ter recebido o mesmo interesse durante o perıodo TInterest, descarta o pacote.
O mesmo acontece para os nos 1 e 2, nos passos 12 e 13, respetivamente. Desta forma,
o produtor nao recebe o interesse 5 e, como consequencia, nao pode enviar os dados
correspondentes.
Como e possıvel verificar neste exemplo, existe a possibilidade de alguns nos nao
receberem os pacotes. Alem disso, quanto maior for o trafego, maior e possibilidade de
esta situacao acontecer, pois ha uma maior probabilidade de um no receber o mesmo
interesse, no perıodo de TInterest, ou ate receber o mesmo pacote de dados, no perıodo
de TData, e, consequentemente, abortar o reencaminhamento. Na situacao em que um
Capıtulo 5. Estrategias de encaminhamento propostas 41
Figura 5.5: Passos 6 ate 10 da experiencia realizada para mostrar desvantagens daBFsrategy
no tem apenas um vizinho, e muito provavel que aconteca algo parecido com o exemplo
que foi dado e isto e uma desvantagem desta estrategia.
Por todas estas desvantagens apresentadas, foram acrescentadas outras funcoes ao
protocolo implementado, de forma a melhorar o seu desempenho.
5.2 Estrategia DSRstrategy
A nova estrategia foi baseada no protocolo de encaminhamento reativo DSR (Dyna-
mic Source Routing)[17] [2], abordado anteriormente na Seccao 2.2.2 e foi implementada
tendo como base a estrategia BFstrategy.
Nesta nova estrategia, designada por DSRstrategy, foi introduzido um novo campo
no cabecalho do pacote de interesse e do pacote de dados, designado por “Path”. A
descricao dos campos dos pacotes de interesse e dados e feita mais a frente, na Seccao
6.3.
Capıtulo 5. Estrategias de encaminhamento propostas 42
5.2.1 Encaminhamento de interesses
Em primeiro lugar, quando o consumidor gera um pacote de interesse, tera de colocar
o seu ID no campo “Path” do cabecalho e enviar o pacote, sem qualquer tempo de espera.
De seguida, todos os nos que receberem o interesse, e nao possuırem os dados cor-
respondentes, terao de colocar, da mesma forma, o seu proprio ID no campo “Path” do
cabecalho do pacote de interesse. Desta forma, sera registado todo o percurso percorrido
pelo interesse, ate chegar ao produtor ou a um no que possua os dados corresponden-
tes na sua CS. Posteriormente, e inicializado um temporizador, com um atraso igual
a TInterest. Durante esse perıodo, o interesse permanece numa fila de pacotes atrasa-
dos, enquanto o no escuta o canal. Esta fase nao foi alterada, sendo semelhante a da
estrategia anterior.
5.2.2 Encaminhamento de dados
Quando o interesse chegar a um produtor ou a um no que possua os dados corres-
pondentes na sua Content Store, este tera de copiar a rota percorrida pelo interesse,
que estara no campo “Path” do cabecalho do interesse, e coloca-la no campo “Path”
do cabecalho do pacote de dados, antes de o enviar. Todos os nos que receberem o
pacote de dados, terao de verificar se pertencem a rota. Caso pertencam, reencaminham
o pacote, sem esperar qualquer tempo de atraso. Caso contrario, e inicializado um tem-
porizador, com um tempo de atraso igual a TData. Neste caso, o procedimento e igual
ao procedimento usado na estrategia anterior.
O objetivo principal desta nova funcionalidade na estrategia de encaminhamento e
fazer com que o pacote de dados percorra o mesmo percurso que o interesse percorreu, a
fim de estabelecer uma rota para os dados. No entanto, devido a mobilidade dos nos, e
possıvel que a rota tenha sido quebrada e foi esta a razao pela qual foi decidido que um
no que recebesse um pacote de dados, e nao pertencesse a rota, pudesse reencaminha-lo.
Neste caso, o no tera de esperar um perıodo igual a TData e o encaminhamento so e feito
se, durante esse tempo, nao receber um pacote de dados igual. Assim, ira permitir que,
mesmo que uma rota tenha ficado invalida, os dados possam ser entregues ao consumi-
dor, mesmo que implique que o RTT seja maior e que a rota, por eles percorrida, seja
diferente.
Capıtulo 5. Estrategias de encaminhamento propostas 43
O facto de esta estrategia forcar os dados a seguirem o mesmo trajeto dos res-
petivos interesses, faz com que os dados tenham uma rota para seguirem, em vez de
serem difundidos na rede, fazendo com que haja uma diminuicao significativa do RTT,
melhorando o seu desempenho. No entanto, esta melhoria nao resolve todos os seus
problemas. A desvantagem de existir a possibilidade de alguns nos nao receberem os
pacotes, abordada na Seccao 5.1.3, permanece, pois este ultimo aperfeicoamento so mo-
difica o encaminhamento dos pacotes de dados. O encaminhamento de interesses nao foi
alterado.
5.3 Estrategia MPRstrategy
Visto que as duas estrategias anteriores tinham varios problemas, tais como grande
probabilidade de colisoes e falta de controlo no encaminhamento de interesses, pensou-
se propor uma estrategia diferente, principalmente no encaminhamento de interesses.
Ainda assim, a estrategia proposta foi concebida, tendo por base as estrategias BFstra-
tegy e DSRstrategy, melhorando-as.
A nova estrategia, designada por MPRstrateggy, foi baseada na tecnica MultiPoint
Relay, que e usada pelo protocolo OLSR, abordada na Seccao 2.2.1. Esta tecnica tem
o objetivo de limitar os nos da rede que reencaminham os interesses, a fim de se poder
eliminar mensagens redundantes e, consequentemente, diminuir o trafego. Assim, a sua
funcao e selecionar um subconjunto de nos da rede, chamados Multipoint relay (MPR),
atraves dos quais seja possıvel disseminar mensagens por toda a rede, ate encontrar um
produtor. A escolha dos MPRs e feita de modo a que cubram todos os nos a dois saltos
de distancia.
5.3.1 Encaminhamento de mensagens hello
Para conhecer todos os nos a dois saltos de distancia, a estrategia utiliza um pro-
tocolo de hello. Todos os nos terao de enviar, periodicamente, mensagens hello para os
seus vizinhos, que conterao o seu ID e os IDs dos seus proprios vizinhos. Naturalmente,
na primeira vez que os nos enviam a mensagem hello, enviarao apenas o seu ID, por-
que ainda nao tem conhecimento dos vizinhos. Assim, este algoritmo necessita de duas
iteracoes para convergir.
Capıtulo 5. Estrategias de encaminhamento propostas 44
Todos os nos terao uma Tabela Vizinhos, que contera todos os seus vizinhos, os res-
petivos vizinhos destes e o numero de vizinhos. A estrutura da tabela esta representada
na Figura 5.6.
Figura 5.6: Estrutura da Tabela Vizinhos dos nos na estrategia MPRstrateggy
Como o contexto em que se enquadra e o das redes de dados nomeados, foi decidido
que as mensagens de hello serao retransmitidas atraves de interesses e dados. Para isso,
todos os nos serao consumidores e, simultaneamente, produtores do prefixo “/hello”.
Todos os consumidores enviarao interesses hello de 5 em 5 segundos. O protocolo OLSR
recomenda o envio de pacotes de hello de 2 em 2 segundos [34], mas como as simulacoes
feitas sao para cenarios em que os dispositivos moveis sao transportados por pedestres,
foi decidido que o intervalo de tempo de 5 segundos era suficiente.
Assim, quando um no N envia um interesse com o prefixo “/hello”, todos os nos
que receberem esse interesse serao, obviamente, os vizinhos de N. Como todos os nos sao
produtores do prefixo “/hello”, os vizinhos de N nao reencaminharao o interesse e, em
vez disso, devolverao os dados correspondentes. Para isso, irao a sua Tabela Vizinhos,
verificar quais sao os seus vizinhos e, de seguida, registarao, no conteudo do pacote de
dados, o seu proprio ID e o ID dos seus vizinhos. O no N, ao receber o pacote de dados,
ira registar na sua Tabela Vizinhos o seu vizinho e os respetivos vizinhos do vizinho.
A Figura 5.7 ilustra um exemplo deste procedimento.
E de notar que os nos adiam a transmissao dos pacotes de dados hello por um tempo
THello, calculado aleatoriamente, a fim de evitar colisoes. Quando o no N enviava o in-
teresse hello, todos os seus vizinhos recebiam-no ao mesmo tempo e, consequentemente,
iriam enviar o respetivo pacote de dados hello, tambem, ao mesmo tempo, o que provo-
cava varias colisoes entre pacotes. Como resultado, N nao recebia a informacao de todos
os vizinhos e ficava com um conhecimento incompleto da topologia, o que resultava num
mau desempenho do protocolo de encaminhamento. Ao contrario dos outros tempos
de atraso criados (TInterest, TData e, como sera visto mais a frente, TInterestMPR), que
servem, tambem, para evitar loops de encaminhamento, neste caso serve apenas para
Capıtulo 5. Estrategias de encaminhamento propostas 45
Figura 5.7: Exemplo da troca de mensagens “/hello” na MPRstrategy
os pacotes nao serem enviados todos ao mesmo tempo. Na troca de pacotes hello nao
existem loops de encaminhamento, pois os nos nunca os reencaminham.
Visto que o RTT e cerca de 5ms, foi decidido que o valor maximo para este tempo-
rizador seria 5ms. Assim, THello estara entre os 0 e 5ms.
Quando um no N recebe um pacote de dados “/hello”, com a informacao de um
vizinho, e verificado se ja possui informacao sobre aquele vizinho na Tabela Vizinhos.
Se sim, elimina a informacao obsoleta e insere a nova. Se nao, simplesmente acrescenta
a nova informacao na tabela.
Alem disso, e estabelecido um tempo de vida para a informacao de um vizinho na
tabela, atraves da utilizacao de um temporizador TNeighbor, que e calculado atraves da
Equacao 5.3.
Capıtulo 5. Estrategias de encaminhamento propostas 46
TNeighbor = Hellointerval + THello +RTT (5.3)
O valor Hellointerval e o intervalo de envio de interesses hello, que e 5 segundos.
THello e o tempo esperado para a retransmissao dos pacotes de dados hello e, nesta
equacao, tem o valor de 5 ms, que e o seu valor maximo. E escolhido o valor maximo,
para nao ocorrer a situacao de um no apagar a informacao do vizinho, simplesmente
por este estar no tempo de espera antes da retransmissao dos dados. Por fim, RTT
e o tempo necessario, aproximadamente, desde que o no N envia o interesse hello, ate
receber o pacote de dados correspondente, que tem o valor de 5ms.
Este temporizador e iniciado quando e criada a informacao desse vizinho na Tabela
Vizinhos. Sempre que essa informacao e atualizada, o temporizador e reiniciado. Caso
o temporizador chegue ao fim, significa que aquele no deixou de ser vizinho (pois o no
N nao recebeu mais atualizacoes deste) e, por isso, a informacao e apagada da Tabela
Vizinhos.
5.3.2 Encaminhamento de interesses
Quando um no tiver um interesse para enviar (com a excecao do interesse com
prefixo /hello), quer seja o consumidor ou um no intermedio, tera de descobrir quais
os seus vizinhos terao de reencaminhar o pacote, ou seja, quais sao os MPRs, para que
todos os vizinhos desses vizinhos recebam o interesse, mas com a menor redundancia
possıvel. O conjunto de nos MPRs serao colocados num novo campo do cabecalho do
interesse, designado por campo “MPR”.
5.3.2.1 Algoritmo MPR
O algoritmo MPR, utilizado para calcular o conjunto de vizinhos MPRs de cada no,
utiliza uma tabela adicional, designada por Tabela provisorio, que esta representada na
Figura 5.8.
O primeiro campo da Tabela provisorio, de um no N, contem o ID do vizinho de
N. O segundo campo contem a quantidade de vizinhos, do vizinho de N, que ainda nao
estao na area de cobertura dos nos ja considerados MPRs. O terceiro campo contem os
IDs desses vizinhos e, por fim, o ultimo campo contem uma variavel inteira, que indica
se o vizinho de N e MPR (1), se ja foi considerado nao-MPR (0) ou se essa decisao
Capıtulo 5. Estrategias de encaminhamento propostas 47
Figura 5.8: Estrutura da Tabela provisorio dos nos na estrategia MPRstrateggy
ainda nao foi feita (-1). Esta tabela serve como tabela auxiliar, para averiguar quais dos
vizinhos de N (com a mesma quantidade de vizinhos) irao pertencer ao conjunto MPR.
Supondo que N tem 5 vizinhos, que contem todos eles 4 vizinhos cada um, o no N ira
registar na Tabela provisorio todas as informacoes desses nos, de forma a perceber quais
tera de escolher como MPR, para uma menor redundancia possıvel de pacotes na rede.
Na Figura 5.9 esta representado o fluxograma da tecnica dos MultiPoint Relays. E
de notar que o vetor com cobertura contem os IDs dos vizinhos dos vizinhos, que ja estao
na area de cobertura dos nos ja considerados MPRs. Ja o vetor sem cobertura contem
os IDs dos vizinhos do vizinho, que ainda nao estao na area de cobertura dos nos ja
considerados MPRs e servira para colocar no terceiro campo da Tabela provisorio de
cada vizinho de N.
Capıtulo 5. Estrategias de encaminhamento propostas 48
Capıtulo 5. Estrategias de encaminhamento propostas 49
Figura 5.9: Fluxograma da tecnica MPR
Capıtulo 5. Estrategias de encaminhamento propostas 50
De seguida, e mostrado um exemplo, para ilustrar a ideia do algoritmo MPR. A
Figura 5.10 representa um exemplo da tabela Vizinhos de um no N.
Figura 5.10: Exemplo da Tabela Vizinhos do no N na MPRstrategy
Em primeiro lugar, o no N tera de ir a tabela Vizinhos e construir uma lista ordenada,
por ordem decrescente, com os seus os vizinhos, que contem mais vizinhos. Neste caso,
a lista ficaria: B-A-C-E-F-G-H-D. De seguida, tera de descobrir quais os vizinhos serao
MPRs.
O primeiro no da lista ordenada e o B. Como a lista com cobertura ainda esta vazia
e nao existe nenhum outro vizinho de N com a mesma quantidade de vizinhos do que B,
significa que B e o primeiro da lista ordenada e e, tambem, o vizinho com mais vizinhos.
Por isto, o no B e considerado MPR. De seguida, os vizinhos de B sao registados na lista
com cobertura, para que N consiga perceber quais os vizinhos dos seus vizinhos ja tem
cobertura, pelos ja considerados MPRs.
O proximo no da lista ordenada e o no A, que tem como primeiro vizinho o no 5.
Como este ja pertence a lista com cobertura, ja recebera o pacote atraves de outro MPR.
A pesquisa dos vizinhos de A continua, ate haver algum vizinho que nao conste na lista
com cobertura ou que acabem os vizinhos de A. O proximo e o no 2. Este ainda nao
consta na lista com cobertura. Contudo, como o no A tem o mesmo numero de vizinhos
em relacao ao proximo no da lista ordenada, o no C, a decisao de se o A e ou nao um
MPR nao e feita neste momento, pois antes e necessario averiguar os vizinhos de todos
Capıtulo 5. Estrategias de encaminhamento propostas 51
os nos, que contem a mesma quantidade de vizinhos do que A, a fim de nao considerar
nos MPRs desnecessariamente e contribuir para a redundancia de pacotes na rede.
De seguida, o no 2 e registado no vetor sem cobertura do no A e a pesquisa dos
vizinhos do no A continuaria, mas, neste caso acabou, porque acabaram os vizinhos de
A. No entanto, se A tivesse mais algum vizinho, o procedimento seria o mesmo, ou seja,
se A tivesse um no que ainda nao pertencesse a lista com cobertura, registaria esse no
no vetor sem cobertura. Caso ja pertencesse, descartava esse no e continuava a pesquisa
de vizinhos de A. Quando a pesquisa termina, e feito um registo na Tabela provisorio.
Neste caso, o registo teria os valores (A; 1; 2; -1). A sua explicacao esta representada
na Figura 5.11.
Figura 5.11: Exemplo de registo na Tabela provisorio do no A na MPRstrategy
O proximo e o no C. Os seus vizinhos sao os nos 5 e 1. O no 5 ja consta na lista
com cobertura, mas o no 1 ainda nao. O procedimento e o mesmo que foi utilizado no
no A. Neste caso, o registo na Tabela provisorio teria os valores (C; 1; 1; -1).
O proximo e no E. Os seus vizinhos sao os nos 1 e 2, que nao constam na lista
com cobertura. Neste caso, o registo na Tabela provisorio teria os valores (E; 2; 1,2; -1).
O no F tem os mesmos vizinhos de E. O registo na Tabela provisorio teria os valores
(F; 2; 1,2; -1).
O no G contem os vizinhos 4 e 8, que nao constam na lista com cobertura. Neste
caso, o registo na Tabela provisorio teria os valores (G; 2; 4,8; -1).
O ultimo no, que contem dois vizinhos, e no H. Os seus vizinhos sao os nos 1 e 6,
que nao constam na lista com cobertura. O registo na Tabela provisorio teria os valores
(H; 2; 1,6; -1).
Posto isto, chegou o momento de decidir quais os nos com 2 vizinhos serao MPRs.
Para isso, e percorrida a Tabela provisorio, que esta representada na Figura 5.12.
Capıtulo 5. Estrategias de encaminhamento propostas 52
Figura 5.12: Exemplo da Tabela Provisorio do no N na MPRstrategy
Em primeiro lugar, e analisado o no A. E percorrida a Tabela Provisorio, de forma
a procurar se o no 2 aparece mais vezes. E encontrado no no E. Como ainda nao esta
decidido se E sera ou nao um MPR, e verificado se este tem na sua area de cobertura
todos os vizinhos de A e ainda um outro no que A nao tenha. Como tem todos e ainda
mais o no 1, o no A e considerado nao-MPR. A mesma situacao acontece para o no C.
De seguida, e analisado o no E. O seu primeiro vizinho e encontrado no grupo de
vizinhos do no C, mas como este ja foi considerado nao-MPR, o procedimento continua.
O proximo no que faz match com o no 1 e o no F. Como ainda nao esta decidido se F
sera ou nao um MPR, e verificado se este tem na sua cobertura todos os vizinhos de E e,
ainda, um outro no que E nao tenha. O no F tem todos os vizinhos de E, mas nao tem
um outro diferente e, por isso, o procedimento continua. De seguida, e encontrado no
no H, e este nao possui todos os vizinhos de E, por isso o procedimento continua. Como
nao existe outro no que faca match com o vizinho 1, e feita a verificacao final: como
ainda nao esta decidido se E e ou nao MPR, E e considerado oficialmente MPR e sao
registados os vizinhos de E, que estavam na lista sem cobertura, na lista com cobertura.
O proximo e o no F. O seu vizinho 1 e encontrado no no C, que ja foi considerado
nao-MPR e, por isso, continua a pesquisa. E encontrado, tambem, no no E, que ja
foi considerado MPR. De seguida, e verificado se o no F possui algum outro no que
E nao possua. Como nao possui, o no F e considerado nao-MPR. Por fim, e tambem
encontrado no no H, mas aqui nada acontece (porque H nao possui todos os vizinhos de
F) e, assim, o no F fica considerado nao-MPR.
Capıtulo 5. Estrategias de encaminhamento propostas 53
E analisado, agora, o no G. O seu primeiro vizinho e o no 4, que nao faz match com
nenhum no da Tabela Provisorio. Entao, o no G e logo considerado MPR, sem haver
necessidade de analisar os seus restantes vizinhos. Por fim, sao registados os vizinhos de
G, que estavam na lista sem cobertura, na lista com cobertura.
Finalmente, e analisado o no H. O seu vizinho 1 e encontrado no no C, que ja
foi considerado nao-MPR e, por isso, continua a pesquisa. E encontrado, tambem, no
no E, que ja foi considerado MPR. Como H possui outro no que F nao possui, H e
considerado temporariamente MPR. Como o seu proximo vizinho, o no 6, e unico na
Tabela Provisorio, H e considerado MPR.
Esta estrategia, de marcar os nos como temporariamente MPRs, serve para nao
serem tomadas decisoes precipitadas, testando todas as relacoes entre os nos, para uma
melhor decisao final da escolha dos MPRs.
No final deste processo, a Tabela Provisorio e apagada.
O ultimo no da lista ordenada e o no D, que possui apenas um vizinho. Como este
ja pertence a lista com cobertura, o no D e considerado nao-MPR.
Neste momento, o no N ja decidiu quais os seus vizinhos serao MPRs: B, E, G e H.
Conclusao: neste caso, o no N possui 8 vizinhos, mas apenas 4 deles sao considerados
MPRs. Serao feitos metade dos reencaminhamentos, o que levara a que o trafego seja
diminuıdo em grande medida e a estrategia de encaminhamento tenha um desempenho
muito melhor, com o reencaminhamento de interesses controlado.
O proximo passo e colocar esta lista de nos no campo “MPR” do interesse. Quando
os vizinhos de N receberem o pacote, atraves de N, terao de verificar se pertencem a lista
de MPRs. Caso nao pertencam, nao reencaminham. Caso pertencam e nao possuam
os dados correspondentes, utilizam o algoritmo MPR para os seus proprios vizinhos,
a fim de descobrirem quais deles serao considerados MPRs, alteram o campo “MPR”
do interesse com o resultado obtido e, por fim, reencaminham o interesse. O processo
repete-se ate que o interesse chegue a um produtor ou a um no que possua os dados
correspondentes na sua Content Store.
E de notar que, sempre que um no intermedio tenha um interesse para encaminhar,
este adia a sua transmissao por um tempo TInterestMPR, calculado aleatoriamente, a
fim de evitar colisoes. O valor deste temporizador estara entre os 0 e 5ms, tal como o
THello. Se durante o perıodo de TInterestMPR, o no receber os dados correspondentes, o
encaminhamento do interesse e abortado.
Capıtulo 5. Estrategias de encaminhamento propostas 54
Outro aspeto importante e o facto de que o algoritmo MPR tem em conta a rota do
interesse, ou seja, se o interesse recebido por N tem a rota “X-A-N”, quando e executado
o algoritmo MPR no no N, este ira descartar, caso possua, os vizinhos A e X e os vizinhos
dos vizinhos A e X nos seus calculos. Assim, diminuira a probabilidade de loops.
5.3.3 Encaminhamento de dados
Quanto ao encaminhamento de pacotes de dados, este nao foi alterado, ou seja,
continua a seguir o percurso inverso do interesse e, caso nao pertenca a rota do interesse,
espera um perıodo de TData. Se durante esse perıodo nao receber outro pacote de dados
igual, reencaminha o pacote ao fim de perıodo de TData. Caso contrario, descarta o
pacote.
E de notar que no reencaminhamento de interesses, os nos continuam a colocar os
seus IDs no campo “Path” do cabecalho do pacote.
Poderia ter sido proposta uma outra variante desta estrategia de encaminhamento,
que alterasse o encaminhamento dos dados, a semelhanca do que foi feito para os in-
teresses. Em vez de os dados seguirem a rota do interesse, seria utilizado o algoritmo
MPR. No entanto, existe uma limitacao, que e uma regra das NDNs, que poe em causa
este protocolo. Quando um no recebe um pacote de dados, verifica se tem uma entrada
PIT correspondente. Caso nao tenha, descarta o pacote nao solicitado. Desta forma,
como o algoritmo MPR define um conjunto reduzido de nos para reencaminharem o
pacote, se esses nos nao tiverem recebido o interesse correspondente, irao descartar o
pacote e o encaminhamento termina, nao conseguindo fazer com que os dados cheguem
ao consumidor. Por esta razao, foi decidido que esta estrategia nao seria proposta.
Capıtulo 6
Implementacao
Neste capıtulo sera descrita a implementacao da rede de dados nomeados no contexto
de uma rede Ad Hoc, bem como as tres estrategias de encaminhamento implementadas.
Alem disso, sera explicado o funcionamento do simulador utilizado.
Para a implementacao da rede, foi usado o simulador ndnSIM 2.0 [8], que e uma
versao estendida do NS-3, que incorpora o paradigma dos dados nomeados.
6.1 Simulador ndnSIM
A ferramenta ndnSIM implementa todas as caracterısticas basicas da arquitetura
NDN, incluindo:
• A utilizacao de um esquema de nomes hierarquico e o formato de pacotes de
interesses/dados;
• O uso de tabelas para o processamento de pacotes, tais como CS, PIT e FIB;
• A abstracao de estrategias de encaminhamento;
• A abstracao de interfaces, a fim de suportar a interface entre a arquitetura NDN
e as camadas superiores (aplicacoes) e inferiores (rede, ligacao).
No ndnSIM 2.0, todo o encaminhamento e gestao NDN e implementado direta-
mente, usando o codigo fonte do NDN Forwarding Daemon (NFD) [8]. O NDN Forwar-
ding Daemon (NFD) e um encaminhador de rede e foi projetado para permitir simular
experiencias diversificadas, tendo em conta as caracterısticas, algoritmos e aplicacoes
das redes NDN. Assim, o NFD implementa e evolui com o protocolo NDN.
55
Capıtulo 6. Implementacao 56
Nesta seccao sera explicada a estrutura do NFD: em primeiro lugar serao apresenta-
das as tabelas usadas pelo NFD, depois a estrutura dos pacotes e, por fim, sera explicado
o processo de encaminhamento de interesses e dados.
6.2 Tabelas
O NFD implementa a PIT, FIB e CS, alem de outras tabelas de suporte, como a
tabela Strategy Choice e a tabela Measurements.
A tabela Forwarding Information Base (FIB) e usada para encaminhar pacotes de
interesse em direcao a potenciais fontes dos dados. E quase identica a uma tabela de
encaminhamento IP, com a diferenca de que a FIB permite ter uma lista de interfaces
de saıda, em vez de uma unica. Uma entrada FIB contem o nome do prefixo e um
conjunto de NextHops. Quando existe uma entrada FIB para um determinado prefixo
significa que pode ser alcancada uma potencial fonte de dados correspondente, atraves
das interfaces contidas no registo de NextHops, nessa entrada FIB. Cada registo de
NextHop contem uma interface de saıda, para uma potencial fonte de dados, e o seu
custo de encaminhamento.
A tabela Content Store (CS) e uma cache de pacotes de dados. Os pacotes de
dados, recebidos por um no, sao colocados nesta cache por um perıodo de tempo, a
fim de satisfazer os interesses futuros que solicitem os mesmos dados. Cada entrada da
Tabela CS contem o pacote de dados, a indicacao se o pacote de dados nao e solicitado
e a hora em que os dados em cache se irao tornar obsoletos.
A tabela Pending Interest Table (PIT) tem como objetivo controlar os interesses en-
caminhados em direcao a produtores de dados, para que os dados possam ser enviados
para o respetivo consumidor [35]. Alem disso, contem interesses satisfeitos recentemente,
para que possam ser detetados ciclos. Uma entrada PIT representa um interesse pen-
dente ou um interesse que foi recentemente satisfeito e e constituıda por um conjunto
de registos de entrada, um conjunto de registos de saıda, dois temporizadores (o tem-
porizador insatisfeito, que expira quando todos os registos da entrada PIT expirarem; e
o temporizador straggler, que expira quando a entrada PIT pode ser removida por ter
sido satisfeita ou rejeitada, e ja nao ser necessaria para detetar ciclos) e, por fim, uma
lista Nonce.
Cada interesse possui um valor Nonce, que pode ser considerado como o seu identi-
ficador e serve, principalmente, para verificar se o interesse recebido por um dado no e
Capıtulo 6. Implementacao 57
duplicado. Supondo que um consumidor envia um interesse com um valor Nonce = x.
Caso o mesmo consumidor deseje enviar outro pacote, mesmo sendo igual ao primeiro
interesse, esse interesse ja vai ter um valor Nonce 6= x. A lista Nonce e formada por um
conjunto de Nonces de pacotes de interesse recebidos, que correspondam a uma entrada
PIT. Assim, caso um no receba dois pacotes de interesse com o mesmo nome, mas o
primeiro com Nonce = x e o segundo com Nonce 6= x, vai perceber que sao diferentes,
nao detetando um loop falso.
A tabela Strategy Choice contem a estrategia de encaminhamento escolhida.
A tabela Measurements e usada pelas estrategias de encaminhamento, para arma-
zenar informacoes de medicoes por prefixos de dados.
6.3 Estrutura dos Pacotes interesse/dados
Cada pacote NDN e codificado com o formato Type-Length-Value (TLV) [36]. Este
formato nao tem um cabecalho fixo, o que torna o envio de pacotes de tamanhos muito
pequenos mais eficiente, pois nao implica tanta sobrecarga na rede.
6.3.1 Pacote de interesse
Um pacote de interesse, que esta representado na Figura 6.1, e constituıdo por
quatro campos: Name, Selectors, Nonce e InsterestLifeTime. Os campos Name e Nonce
sao os unicos obrigatorios, todos os outros sao facultativos [37].
Figura 6.1: Estrutura do pacote de interesse
• Name: e o nome do prefixo.
• Selectors: sao usados para ajudar na selecao dos dados a enviar, quando existem
varios pacotes que correspondem ao interesse. O campo Selector contem cinco
Capıtulo 6. Implementacao 58
sub-campos: MinSuffixComponents e MaxSuffixComponents, PublisherPublicKey-
Locator, Exclude, ChildSelector e MustBeFresh [37].
– MinSuffixComponents e MaxSuffixComponents: permite que um consumidor
de dados possa indicar se o nome do interesse e o nome completo. O valor
por defeito de MinSuffixComponents e 0 e de MaxSuffixComponents e efeti-
vamente infinito. Quando sao estes os valores usados, significa que qualquer
pacote de dados, cujo nome comece com o prefixo, corresponde ao interesse
do consumidor [37].
– PublisherPublicKeyLocator : especifica a chave publica, que corresponde a
chave privada que devera ser usada para assinar o pacote de dados, que o
consumidor solicitou. Esta e uma maneira de o interesse selecionar respostas
de um determinado produtor [37].
– Exclude: permite especificar uma lista de nomes, que nao devem aparecer
como uma continuacao do nome do prefixo, no pacote de dados [37].
– ChildSelector : muitas vezes um determinado interesse ira corresponder a mais
do que um pacote de dados contido na Content Store dos nos. O ChildSelec-
tor serve para especificar qual dos pacotes o consumidor deseja receber [37]
(especificar versoes dos pacotes, por exemplo).
– MustBeFresh: quando MustBeFresh nao existe no pacote de interesse, um no
pode responder com um pacote de dados a partir de sua CS, com o Fresh-
nessPeriod valido ou ja expirado. Quando este campo existe num pacote de
interesse, o no nao deve retornar o pacote de dados a partir da sua CS, caso
o valor de FreshnessPeriod esteja expirado. Cada pacote de dados contem
um valor de FreshnessPeriod, que e definido pelo seu produtor inicial. A sua
contagem regressiva comeca quando o pacote de dados chega a um no [37].
• Nonce: e um identificador de um pacote de interesse e serve, principalmente, para
verificar se o interesse e duplicado.
• Guiders: contem um sub-campo, designado por InterestLifetime, que indica o
tempo de vida de um interesse [37].
Capıtulo 6. Implementacao 59
6.3.2 Pacote de dados
Um pacote de dados, que esta representado na Figura 6.2, e constituıdo por qua-
tro campos: Name, MetaInfo, Content e Signature. O pacote de dados contem o seu
conteudo (armazenado no campo Content), o seu nome (Name), alguns bits adicionais
de informacao (MetaInfo) e uma assinatura digital dos outros tres elementos (Signa-
ture)[38].
Figura 6.2: Estrutura do pacote de dados
• Name: e o nome do prefixo.
• MetaInfo: e um campo opcional, que contem informacao adicional e e dividida em
3 sub-campos: ContentType, FreshnessPeriod e FinalBlockId.
– ContentType: corresponde ao tipo de dados que o pacote transporta. Existem
tres tipos: default (=0), Link (=1) e Key (=2). Quando esta ativado o tipo
default, significa que o conteudo (campo Content) e identificado pelo campo
Name. No caso do tipo Link, o conteudo corresponde a outro nome que
identifica o pacote de dados. O tipo Key indica que o conteudo do pacote
transporta uma chave publica [38].
– FreshnessPeriod : indica o tempo de vida do pacote de dados, ate este ser
marcado como expirado. A expiracao do FreshnessPeriod significa, apenas,
que o produtor pode ter produzido dados mais recentes. Quando Freshnes-
sPeriod e omitido, o pacote de dados nao pode ser marcado como obsoleto
[38].
– FinalBlockId : indica o identificador do ultimo pacote de dados de uma sequencia
de fragmentos. Este campo deve estar presente no pacote final, e pode
tambem estar presente noutros fragmentos, a fim de proporcionar um aviso
antecipado ao consumidor. O valor do FinalBlockId deve ser igual ao campo
Name do ultimo pacote da sequencia de fragmentos [38].
• Content : contem o conteudo (dados) do pacote de dados.
Capıtulo 6. Implementacao 60
• Signature: e uma assinatura digital dos outros tres campos do pacote de dados
[38].
Na estrategia DSRstrategy, foi introduzido um novo campo no cabecalho do pa-
cote de interesse e do pacote de dados, designado por “Path” e, por isso, a estrutura
dos pacotes e diferente nesta estrategia. A nova estrutura do pacote de interesse esta
representada na Figura 6.3 e a do pacote de dados esta representada na Figura 6.4.
Figura 6.3: Estrutura do pacote de interesse na estrategia DSRstrategy
Figura 6.4: Estrutura do pacote de dados na estrategia DSRstrategy
Na estrategia MPRstrategy, foi, tambem, introduzido um novo campo ao cabecalho
do interesse, designado por campo “MPR”. Assim, a estrutura do pacote de interesse
foi, novamente, alterada e pode ser vista na Figura 6.5. Nesta estrategia, o pacote de
dados e igual a estrategia DSRstrategy.
6.4 Processamento de pacotes pelo NFD
Os pacotes chegam ao NFD atraves de interfaces. Uma interface pode ser tanto uma
interface fısica (caso a NDN opere diretamente pela Ethernet), como um tunel overlay
(caso a NDN opere como um overlay acima do TCP ou UDP) [6].
O processamento de pacotes no NFD e desempenhado atraves de pipelines de en-
caminhamento e estrategias de encaminhamento [6]. Um pipeline e um conjunto de
Capıtulo 6. Implementacao 61
Figura 6.5: Estrutura do pacote de interesse na estrategia MPRstrategy
etapas, levadas a cabo sobre um pacote ou numa entrada PIT, e e acionado por um
evento especıfico: rececao de interesses, detecao de interesses recebidos em loop, detecao
de quando o interesse esta pronto para ser enviado para outro no, etc.
A estrategia e um tomador de decisoes sobre o encaminhamento de interesses, que e
anexado no final ou inıcio dos pipelines. Por outras palavras, a estrategia toma decisoes
se, quando e para onde encaminhar um interesse, enquanto os pipelines fornecem a
estrategia informacoes de apoio para tomar essas decisoes [6].
A Figura 6.6 mostra a relacao das tarefas dos pipelines e das estrategias, onde as
caixas azuis representam pipelines e as caixas brancas representam pontos de decisao da
estrategia.
Figura 6.6: Relacao entre pipelines e a estrategia [6]
Capıtulo 6. Implementacao 62
O processamento de pacotes de interesses e dados pelo NDN e diferente (o primeiro
serve como um pedido, enquanto o segundo satisfaz pedidos pendentes) e, por isso, os
pipelines de encaminhamento sao separados em dois grupos: processamento de interesses
e processamento de dados [6], que serao descritos de seguida.
6.4.1 Processamento de interesses
O processamento dos interesses e constituıdo por varios pipelines:
• Incoming interest : processamento de interesses recebidos por um no.
• Interest loop: processamento de interesses recebidos em loop.
• Outgoing interest : preparacao e envio de interesses.
• Interest reject : processamento de entradas PIT, que sao rejeitadas pela estrategia.
• Interest unsatisfied : processamento de entradas PIT, que se tornam insatisfeitas.
Quando um no recebe um interesse, e iniciado o pipeline Incoming interest. Em
primeiro lugar, e inserida uma entrada na tabela Pending Interest Table (PIT). A cada
entrada PIT sao associados dois temporizadores: o temporizador insatisfeito, que expira
quando a entrada PIT expira; e o temporizador straggler, que expira quando a entrada
PIT pode ser removida, pois foi satisfeita ou rejeitada, e ja nao e necessaria para fins de
detecao e verificacao de loops.
Caso seja detetado que o interesse e duplicado, e iniciado o pipeline Interest loop,
onde o pacote e descartado. Se o interesse nao for duplicado, e realizada uma pesquisa
na tabela Content Store (CS). Se existirem os dados correspondentes na CS, e enviado
o pacote de dados; caso contrario, o interesse deve ser encaminhado.
A estrategia de encaminhamento decide como encaminhar um interesse. Para deci-
dir qual estrategia e responsavel por encaminhar um interesse, e realizada uma pesquisa
de correspondencia mais longa de prefixo na tabela de Strategy Choice, que contem a
configuracao da estrategia. A estrategia responsavel por um interesse (ou, mais precisa-
mente, pela entrada PIT) decide se, quando e para onde encaminhar o interesse. Caso
a estrategia decida que nao pode enviar o interesse, e iniciado o pipeline Interest reject,
onde o pacote e descartado.
Apos a estrategia decidir encaminhar um interesse para uma interface especıfica, o
interesse e enviado atraves do pipeline Outgoing interest, onde e passado para a interface.
Capıtulo 6. Implementacao 63
A interface, dependendo do protocolo subjacente, acrescenta o cabecalho da camada de
ligacao, os fragmentos, se necessario, e envia os pacotes da camada de ligacao, como
fluxo de saıda ou datagramas, atraves da API do sistema operativo.
Caso uma entrada PIT nao seja satisfeita, depois de o temporizador insatisfeito
expirar, e iniciado o pipeline Interest unsatisfied, onde a entrada PIT e eliminada.
6.4.2 Processamento de dados
O processamento de dados pelo NFD e dividido nos seguintes pipelines:
• Incoming data: processamento de pacotes de dados recebidos.
• Data unsolicited : processamento de pacotes de dados recebidos nao solicitados.
• Outgoing data: Preparacao e envio de pacotes de dados.
Quando um no recebe um pacote de dados, e iniciado o pipeline Incoming data.
O primeiro passo deste pipeline e verificar se existem entradas PIT que possam ser
satisfeitas com este pacote de dados. Todas as entradas correspondentes sao, entao, se-
lecionadas para posterior processamento e sao cancelados os temporizadores insatisfeito
e straggler, para cada entrada PIT encontrada, pois o interesse pendente ficou, agora,
satisfeito. Se esses dados nao satisfizerem nenhuma das entradas PIT, significa que o
pacote de dados nao foi solicitado e, por isso, e iniciado o pipeline Data unsolicited,
onde o pacote e descartado. No entanto, em casos especiais, dados nao solicitados, a
partir de uma aplicacao local, sao armazenados em cache na CS. Finalmente, os dados
sao enviados para todos os consumidores. O processo de envio de dados atraves de uma
interface e semelhante ao envio de um interesse e realiza-se atraves do pipeline Outgoing
data.
6.5 Estrategias de encaminhamento implementadas
Ate ao momento, a maioria dos trabalhos que usaram a ferramenta ndnSIM [39]
tem-se focado em redes com fios, e nao em redes wireless Ad Hoc [5]. Talvez por esta
razao, a comunicacao wireless multihop ainda nao seja suportada pela versao atual oficial
do ndnSIM [8]. Nesta ferramenta, um no pode encaminhar um pacote de interesse/dados
recebido atraves de todas as interfaces de rede, exceto atraves da interface pela qual o
pacote chegou. Como consequencia, o pacote recebido pela interface 802.11 nao seria
Capıtulo 6. Implementacao 64
enviado diretamente atraves da mesma interface, a fim de permitir uma comunicacao
wireless multihop. Assim, a ferramenta teve de ser reformulada, para contornar este
problema e suportar o reencaminhamento em interfaces radio 802.11.
A restricao para os interesses estava mencionada no arquivo pit-entry.cpp, na funcao
canForwarTo. Todas as estrategias acediam a essa funcao, para averiguar se podiam, ou
nao, reencaminhar o interesse. Assim, todas as novas estrategias implementadas, em vez
de utilizarem a funcao canForwarTo da pit-entry.cpp, utilizam uma nova funcao, que
faz exatamente o mesmo do que a funcao original, eliminado a restricao nao desejada.
Ja a restricao para os pacotes de dados era aplicada no arquivo forwarder.cpp, mais
propriamente na funcao onIncomingData. Esta funcao verificava quais os downstreams
pendentes e enviava o pacote por esses, caso nao fossem iguais a interface de entrada.
Assim, neste caso bastou eliminar essa restricao. Desta forma, ja e possıvel simular uma
rede com uma comunicacao wireless multihop.
6.5.1 Estrategia BFstrategy
Como ja tinha sido referido, a estrategia BFstrategy, abordada anteriormente na
Seccao 5.1, tem como objetivo principal adiar a transmissao de interesses e dados, por
um intervalo de tempo, calculado aleatoriamente, a fim de diminuir a probabilidade de
colisoes.
As tabelas de interesses atrasados e de dados atrasados, que todos os nos possuem,
sao representadas por duas estruturas de dados (struct). A estrutura de interesses atra-
sados esta representada na Figura 6.7 e a estrutura de dados atrasados esta representada
na Figura 6.8.
Figura 6.7: Estrutura da Struct de interesses atrasados na BFstrategy
Capıtulo 6. Implementacao 65
Figura 6.8: Estrutura da Struct de dados atrasados na BFstrategy
O campo “ID” e do tipo int, o campo “prefixo” e do tipo ndn::Name, o campo
“validade” e o campo “dados” sao do tipo bool. A estrutura da struct de dados atrasados
e igual a estrutura da struct de interesses atrasados, com a excecao da ultima ter um
campo adicional, o campo “dados”.
6.5.1.1 Encaminhamento de interesses
Como foi criada uma nova estrategia, foi necessario criar dois arquivos: BFstra-
tegy.cpp e BFstrategy.hpp. Todas as estrategias de encaminhamento no simulador ndn-
SIM tem de ter a funcao afterReceiveInterest, que e chamada pela funcao onIncomin-
gInterest do forwarder.cpp. A funcao afterReceiveInterest tem o objetivo principal de
verificar se e possıvel reencaminhar o interesse, para si proprio ou para a rede, e, caso
seja possıvel, enviar o interesse pela interface de saıda. No entanto, dependendo da
estrategia, pode ter, ou nao, mais funcionalidades. Aos parametros desta funcao, foram
acrescentados a struct de interesses atrasados e um valor inteiro loop, que indica se foi
detetado que o interesse esta em loop (=1) ou nao (=0). Este valor inteiro serve para
fazer o registo do interesse recebido na struct de interesses atrasados, a fim de ser ve-
rificado se existe outro interesse com o mesmo prefixo na struct. Caso exista, este sera
marcado como invalido.
Nesta estrategia, a funcao afterReceiveInterest foi alterada: e verificado se e o con-
sumidor a enviar o interesse, criado por si. Se sim, envia de imediato o pacote para a
rede, senao invoca a funcao wait interest.
Nos arquivos BFstrategy.cpp e BFstrategy.hpp, foram acrescentadas, entao, duas
novas funcoes: wait interest e sendInterest. A funcao wait interest tem uma primeira
tarefa de verificar se e o produtor a receber o interesse. Caso seja, envia de imediato o
interesse por uma interface local (enviar ou receber um pacote, atraves de uma interface
Capıtulo 6. Implementacao 66
local, significa que o no envia o pacote para ele proprio ou recebe atraves dele proprio,
respetivamente, ou seja, processa o pacote). Caso contrario, e averiguado se existem
interesses pendentes iguais ao pacote acabado de receber e, nesse caso, estes sao marcados
como invalidos. Caso nao exista nenhum pacote igual na Tabela de interesses atrasados
e o interesse nao esteja em loop, e calculado um tempo aleatorio para programar o seu
envio.
A funcao sendInterest e chamada no final do tempo de espera do interesse, e tem o
objetivo de verificar se se deve enviar o interesse. Se o no recebeu um interesse igual ou
os dados correspondentes durante o perıodo de espera, o interesse e invalido e, por isso,
e rejeitado. Caso o interesse seja valido, e enviado.
Por fim, foi alterada a funcao onIncomingInterest do forwarder.cpp. Esta funcao
e utilizada para receber interesses. A mudanca implementada foi a seguinte: quando
e detetado que um interesse esta em loop, em vez de, apenas, o enviar para a funcao
onInterestLoop e descarta-lo, envia, tambem, para a estrategia de encaminhamento, a
fim de invalidar o envio de outros interesses iguais, que possam estar pendentes.
Na Figura 6.9 esta representada a sequencia de funcoes que foram alteradas e criadas,
no encaminhamento de interesses, para implementar esta estrategia de encaminhamento.
E de notar que a funcao onOutgoingInterest nao foi alterada, estando na imagem apenas
para mostrar o seguimento do codigo.
Todos os algoritmos podem ser consultados em anexo, no Apendice A: o algoritmo
da funcao onIncomingInterest esta representado na Listagem 1, o algoritmo da funcao
afterReceiveInterest esta na Listagem 2, o algoritmo da funcao wait interest esta na
Listagem 3 e, por fim, o algoritmo da funcao sendInterest esta na Listagem 4.
6.5.1.2 Encaminhamento de pacotes de dados
O encaminhamento dos pacotes de dados e feito no arquivo forwarder.cpp, onde sao
implementados os pipelines de encaminhamento. Como esta estrategia controla nao so o
encaminhamento de interesses, mas tambem o encaminhamento dos dados, foi necessario
alterar o arquivo forwarder.cpp, mais propriamente a funcao onIncomingData, que e a
funcao chamada quando um pacote de dados e recebido. A alteracao feita foi a seguinte:
antes de enviar o pacote de dados, e verificado se a estrategia de encaminhamento a
ser utilizada e a BFstrategy. Se sim, em vez de enviar o pacote para a rede, vai para a
funcao wait data, que sera explicada de seguida.
Capıtulo 6. Implementacao 67
Figura 6.9: Sequencia de funcoes para o encaminhamento de interesses, na estrategiaBFstrategy
Alem disso, foram acrescentadas duas novas funcoes: wait data e sendData. A
funcao wait data executa varias tarefas: em primeiro lugar, e verificado se e o consumidor
a receber os dados ou o produtor a enviar os dados. Caso uma destas hipoteses seja
valida, o pacote de dados e enviado de imediato. De seguida, e verificado se a Tabela de
interesses atrasados possui algum interesse com o mesmo prefixo que o pacote de dados
acabado de receber e, nesse caso, o campo “Dados” e alterado para true. Depois, e
verificada a Tabela de dados atrasados, para averiguar se existe algum pacote de dados
igual ao pacote acabado de receber. Se sim, este e marcado como invalido e o pacote e
Capıtulo 6. Implementacao 68
descartado. Senao, e calculado um tempo aleatorio para o envio do pacote.
Ja a funcao sendData tem o mesmo objetivo do que a funcao sendInterest, mas para
o caso do encaminhamento dos dados.
Na Figura 6.10 esta representada a sequencia de funcoes que foram alteradas e
criadas, no encaminhamento de dados, para implementar esta estrategia de encaminha-
mento. E de notar que a funcao onOutgoingData nao foi alterada, estando na imagem
apenas para mostrar o seguimento do codigo.
Todos os algoritmos podem ser consultados em anexo, no Apendice A: o algoritmo
da funcao onIncomingData esta representado na Listagem 5, o algoritmo da funcao
wait data esta representado na Listagem 6 e, por fim, o algoritmo da funcao sendData
esta representado na Listagem 7.
Figura 6.10: Sequencia de funcoes para o encaminhamento de dados, na estrategiaBFstrategy
Capıtulo 6. Implementacao 69
6.5.2 Estrategia DSRstrategy
A estrategia DSRstrategy, abordada anteriormente na Seccao 5.2, foi baseada, tal
como a estrategia anterior, no protocolo Blind Forwarding (BF) e, adicionalmente, no
protocolo de encaminhamento reativo DSR (Dynamic Source Routing)[17] [2].
Nesta nova estrategia, foram alterados os ficheiros onde estao definidos os pacotes
de interesse e dados interest.cpp e data.cpp, respetivamente, porque foi definido um novo
campo, no cabecalho do pacote de interesse e do pacote de dados, designado por “Path”,
que e uma variavel do tipo string.
6.5.2.1 Encaminhamento de interesses
O encaminhamento de interesses e igual ao da estrategia BFstrategy e, por isso, os
arquivos DSRstrategy.cpp e DSRstrategy.hpp sao iguais aos arquivos BFstrategy.cpp e
BFstrategy.hpp, respetivamente.
A alteracao feita na funcao onIncomingInterest do forwarder.cpp e, tambem, igual
a estrategia anterior.
Por outro lado, a funcao onOutgoingInterest do forwarder.cpp, que e chamada para
enviar um interesse foi alterada, a fim de introduzir o ID do no no campo “Path” do
cabecalho do interesse. Alem disso, caso o no seja o produtor dos dados correspondentes
do interesse, a rota do interesse e processada para, posteriormente, ser colocada no
pacote de dados. Este algoritmo pode ser consultado em anexo, no Apendice B e esta
representado na Listagem 8.
Na Figura 6.11 esta representada a sequencia de funcoes que foram alteradas e
criadas, no encaminhamento de interesses, para implementar esta estrategia de encami-
nhamento. Os algoritmos das funcoes afterReceiveInterest, wait interest e sendInterest
nao estao descritos nesta estrategia, pois sao iguais aos da estrategia BFstrategy, ja
abordada.
6.5.2.2 Encaminhamento de pacotes de dados
Ja para o encaminhamento de dados, foi alterada a funcao onIncomingData do
forwarder.cpp: antes de enviar os dados, e verificado se e o produtor a enviar o pacote.
Caso seja, envia-o de imediato. Caso contrario, se for um no intermedio a reencaminhar
o pacote, e necessario ir buscar o valor do campo “Path”, a fim de averiguar se o no
Capıtulo 6. Implementacao 70
Figura 6.11: Sequencia de funcoes para o encaminhamento de interesses, na estrategiaDSRstrategy
pertence a rota percorrida pelo interesse. Caso pertenca, envia o pacote, caso contrario,
vai para a funcao wait data, ja usada na estrategia anterior.
As funcoes wait data e sendData, ja abordadas na estrategia anterior, sao usadas,
tambem, nesta estrategia.
Na Figura 6.12 esta representada a sequencia de funcoes que foram alteradas e
criadas, no encaminhamento de dados, para implementar esta estrategia de encami-
nhamento. Os algoritmos das funcoes wait data e sendData nao estao descritos nesta
estrategia, pois sao iguais aos da estrategia BFstrategy, ja abordada.
Capıtulo 6. Implementacao 71
O algoritmo da funcao onIncomingData pode ser consultado em anexo, no Apendice
B, e esta representado na Listagem 9. A funcao onOutgoingData nao foi alterada.
Figura 6.12: Sequencia de funcoes para o encaminhamento de dados, na estrategiaDSRstrategy
6.5.3 Estrategia MPRstrategy
Esta estrategia, abordada anteriormente na Seccao 5.3, e baseada na tecnica Multi-
Point Relay, que e usada pelo protocolo OLSR. Esta tecnica tem o objetivo de limitar
os nos da rede que reencaminham os pacotes, a fim de se poder eliminar mensagens re-
dundantes. Assim, a sua funcao e selecionar um subconjunto de nos da rede, chamados
Multipoint relay (MPR), para disseminar mensagens por toda a rede. A escolha de cada
MPR e feita de modo a que cubra todos os nos a dois saltos de distancia.
Capıtulo 6. Implementacao 72
Todos os nos terao uma Tabela “Vizinhos”, cuja estrutura esta ilustrada na Fi-
gura 6.13. Esta tabela e representada por uma struct.
Figura 6.13: Estrutura da Tabela “Vizinhos” de um no na MPRstrategy
Por fim, a estrutura do pacote de interesse foi, novamente, alterada no arquivo
interest.cpp, a fim de acrescentar o campo “MPR”. Neste campo sera colocado o conjunto
de nos MPRs calculado.
6.5.3.1 Encaminhamento de mensagens hello
Foi decidido que os nos iriam iniciar as sua funcoes em tempos diferentes, de modo
a implementar um cenario mais real. Assim, o primeiro interesse hello a ser enviado por
cada no sera feito em tempos diferentes, o que faz com que a troca de interesses hello
nao esteja sincronizada.
O protocolo de troca de hellos foi implementado com base em interesses e dados, o
que levantou uma serie de problemas, nomeadamente:
• Em primeiro lugar, como um no N era, simultaneamente, consumidor e produtor do
mesmo prefixo, “/hello”, quando N enviava um interesse com esse prefixo, em vez
de enviar para uma interface nao local, ou seja, enviar para outro no em broadcast,
enviava internamente (para si proprio), atraves de uma interface local. Isto porque
ja tinha encontrado o produtor do interesse que estava a enviar, que era o proprio
N. Todos os nos tinham este comportamento e, por isso, nao havia interesses com
o prefixo “/hello” a serem enviados para a rede. Para contornar este problema, foi
imposta a restricao de que, quando um no desejava enviar um interesse “/hello”,
nao poderia envia-lo por uma interface local, mas sim para a rede.
• Em segundo lugar, quando um no N recebia, pela primeira vez, um interesse
“/hello”, deveria envia-lo internamente, por uma interface local, a fim de pro-
duzir um pacote de dados. Em vez disso, o no descartava o interesse, pois, como
tinha enviado um interesse “/hello” num curto espaco de tempo, os registos de
Capıtulo 6. Implementacao 73
saıda da entrada PIT do interesse enviado ainda nao tinham expirado. Para eli-
minar este problema, foi imposta a restricao de que, mesmo que os registos de
saıda, da entrada PIT do interesse enviado, ainda nao estivessem expirados, o no
N podia enviar o interesse recebido internamente.
• Aparentemente, o problema estaria resolvido, mas aconteceram mais imprevistos.
Quando um no N recebia um interesse “/hello”, na segunda troca de interesses,
em vez de produzir um pacote de dados novo, enviava o pacote que continha na
sua Content Store. Isto nao podia acontecer, pois os seus vizinhos poderiam ter-se
alterado e o pacote de dados “/hello” tem de estar sempre atualizado. Para isso,
foi imposta uma restricao que obriga um produtor a produzir sempre um novo
pacote de dados “/hello” e nunca reutilizar o pacote armazenado na CS.
• Em quarto lugar, quando um produtor enviava um pacote de dados, em vez de en-
viar, unicamente, para os seus vizinhos, enviava, tambem, para si proprio, atraves
de uma interface local. Isto porque, como tinha um interesse pendente com o
mesmo prefixo, iria satisfazer esse interesse com os seus dados. Como o objetivo
nao era esse, foi imposta uma restricao para que um produtor nao pudesse enviar
o seu pacote de dados “/hello” para si proprio.
• Em quinto lugar, um no N reencaminhava os pacotes de dados recebidos, atraves
de um vizinho X, o que nao poderia acontecer, pois os vizinhos de N iam achar
que X era seu vizinho, o que poderia nao ser verdade. Para isso, foi imposta a
restricao de impedir o reencaminhamento de pacotes de dados “/hello”.
• Por ultimo, um consumidor so aceitava o primeiro pacote de dados que recebesse,
aceitando so os dados de um unico vizinho. Isto acontecia porque o no verificava
que ja tinha aquele pacote de dados, com o prefixo “/hello”, e, por isso, descartava
novos pacotes de dados. Para contornar este problema, foi imposta a restricao para
que um consumidor aceitasse todos os pacotes de dados “/hello” recebidos.
Com todas estas solucoes, o problema foi resolvido e foi conseguido o resultado
esperado.
6.5.3.2 Encaminhamento de interesses
Como foi criada uma nova estrategia, foi necessario criar dois arquivos: MPRstra-
tegy.cpp e MPRstrategy.hpp.
Capıtulo 6. Implementacao 74
A funcao afterReceiveInterest do MPRstrategy.cpp tem a tarefa de verificar se o no
pertence ao grupo de MPRs do interesse. Caso pertenca, adiciona o interesse a Tabela
de interesses atrasados, calcula o valor de TInterestMPR e programa a ida para a funcao
sendInterest, depois desse tempo. Caso nao pertenca, descarta o interesse.
A funcao sendInterest verifica se o no recebeu os dados correspondentes, durante
TInterestMPR. Se sim, descarta o interesse. Senao, envia-o pela interface de saıda.
A funcao onOutgoingInterest foi tambem, alterada: tal como na estrategia DSRs-
trategy, e introduzido o ID do no no campo “Path” do cabecalho do interesse e, caso
o no seja o produtor dos dados correspondentes do interesse, a rota e guardada para,
posteriormente, coloca-la no cabecalho do pacote de dados. Alem disso, antes de enviar
o pacote, e calculado o conjunto de MPRs, atraves do algoritmo MPR, que foi explicado
na Seccao 5.3.2.1, e o resultado e colocado no campo “MPR” do cabecalho do interesse.
Por outro lado, se o interesse for um hello, e construıda uma string com o seu ID e o ID
de todos os seus vizinhos e, por fim, e enviado o resultado para o produtor.
Na Figura 6.14 esta representada a sequencia de funcoes que foram alteradas e
criadas, no encaminhamento de interesses, para implementar esta estrategia de encami-
nhamento.
Todos os algoritmos podem ser consultados em anexo, no Apendice C: o algoritmo da
funcao afterReceiveInterest esta representado na Listagem 10, o da funcao sendInterest
esta representado na Listagem 11 e o da funcao onOutgoingInterest esta representado
na Listagem 12. E de notar que a funcao onIncomingInterest nao foi alterada.
6.5.3.3 Encaminhamento de pacotes de dados
Para o encaminhamento dos pacotes de dados foram alteradas as funcoes onInco-
mingData e onOutgoingData do forwarder.cpp, que sao usadas para receber um pacote
de dados e enviar um pacote de dados, respetivamente. Alem disso, sao usadas as funcoes
wait data e sendData, ja abordadas nas estrategias anteriores.
As alteracoes feitas na funcao onIncomingData sao as mesmas abordadas na es-
trategia DSRstrategy e foi acrescentado um codigo extra, para a situacao em que e
recebido um pacote de dados hello por uma interface local, ou seja, quando o no e o pro-
dutor do pacote. Neste caso, o pacote e adicionado a Tabela de dados Hello atrasados,
e calculado o valor de THello e programada a ida para a funcao sendHello, depois desse
tempo.
Capıtulo 6. Implementacao 75
Figura 6.14: Sequencia de funcoes para o encaminhamento de interesses, na estrategiaMPRstrategy
A Tabela de dados Hello atrasados serve para armazenar os pacotes, durante o
tempo de espera antes do reencaminhamentos. E representada por uma estrutura de
dados e tem, apenas, dois campos: o campo “ID”, que identifica o pacote e o campo
“data”, que e o pacote de dados.
A funcao sendHello envia os pacotes de dados hello.
Por fim, a funcao onOutgoingData foi alterada, para permitir a troca de hellos:
se for o produtor a enviar o hello, produzido por si, para si proprio ou o produtor a
reencaminhar o hello, recebido da rede, para outro no, a operacao e terminada.
Todos os algoritmos podem ser consultados em anexo, no Apendice C: o algoritmo
da funcao onIncomingData esta representado na Listagem 13, o da funcao sendHello
esta representado na Listagem 14 e o da funcao onOutgoingData esta representado na
Listagem 15.
A Figura 6.14 ilustra a sequencia de funcoes que foram alteradas e criadas, no
encaminhamento de dados, para implementar esta estrategia de encaminhamento. Os
algoritmos das funcoes wait data e sendData nao estao descritos nesta estrategia, pois
sao iguais aos da estrategia BFstrategy, ja abordada.
Capıtulo 6. Implementacao 76
Figura 6.15: Sequencia de funcoes para o encaminhamento de dados, na estrategiaMPRstrategy
Capıtulo 7
Testes e resultados
Depois de implementado o cenario da rede de dados nomeados numa rede Ad Hoc
e as varias estrategias de encaminhamento, procedeu-se a execucao de testes. Para isso,
foram feitas varias simulacoes, de forma a verificar e certificar o comportamento do
cenario e das varias estrategias de encaminhamento implementadas.
Neste capıtulo, serao apresentados todos os testes e simulacoes realizadas, assim
como a analise e discussao dos resultados obtidos.
7.1 Configuracoes para a simulacao
As simulacoes foram realizadas utilizando o simulador ndnSIM, como ja tinha sido
referido anteriormente.
Em todas as simulacoes feitas, para averiguar o desempenho dos protocolos de en-
caminhamento implementados, sao utilizados os mesmos parametros de configuracao.
Estes estao de acordo com a Tabela 7.1. O cenario tem, entao, uma dimensao de 600
metros por 1500 metros, com 80 nos. O modelo de mobilidade usado foi o Random
Waypoint e a posicao inicial dos nos e feita de um modo aleatorio. O alcance de trans-
missao dos nos e de 160 metros. O tipo de trafego e Constant Bit Rate (CBR), com uma
frequencia de envio de 1 interesse por segundo. (A taxa de transmissao e de 2Kbps) e o
tamanho dos pacotes de dados e de 64 Bytes. Por fim, foi usado um tempo de simulacao
de 204 segundos.
77
Capıtulo 7. Testes e Resultados 78
Parametros Valor
Dimensao 600m x 1500m
Numero de nos 80
Modelo de Mobilidade Random Waypoint
Alcance de transmissao 160m
Tipo de trafego Constant Bit Rate (CBR)
Tamanho dos pacotes 64 Bytes
Taxa de transmissao 2Kbps
Especificacoes Wifi IEEE 802.11b, freq. 2.4GHz. Taxa de tranf. ate 2Mbps
Tempo de simulacao (s) 204
Tabela 7.1: Parametros do cenario de simulacao
7.2 Cenarios de simulacao
Para avaliar o comportamento dos varios protocolos de encaminhamento, foram
implementados varios cenarios de simulacao diferentes.
Os cenarios diferem no numero de produtores de conteudos diferentes e no numero
de consumidores. O numero de produtores e consumidores varia, simultaneamente, en-
tre 2, 7, 12, 17 e 22. Os consumidores geram trafego do tipo Constant Bit Rate (CBR),
com uma frequencia de 1 interesse por segundo. Visto que a aplicacao dos consumido-
res e iniciada aos 6 segundos (para dar tempo de os nos conhecerem a vizinhanca, na
MPRstrategy) e terminada aos 204 segundos, da um total de 198 interesses gerados por
consumidor, por simulacao. Entao, por simulacao:
• 2 consumidores geram 396 interesses;
• 7 consumidores geram 1386 interesses;
• 12 consumidores geram 2376 interesses;
• 17 consumidores geram 3366 interesses;
• 22 consumidores geram 4356 interesses.
Como se pode verificar, quantos mais consumidores houver, maior sera o numero de
interesses gerados, fazendo com que o trafego seja mais elevado. Assim, estes diferentes
cenarios servem para testar o desempenho dos varios protocolos de encaminhamento
implementados com a variacao do volume de trafego.
Capıtulo 7. Testes e Resultados 79
Alem disso, os cenarios tambem diferem, naturalmente, nas varias estrategias de en-
caminhamento implementadas: BFstrategy, DSRstrategy e MPRstrategy. Sao, tambem,
mostrados os resultados da estrategia Broadcast, que envia todos os interesses e dados
recebidos, nao efetuando qualquer controlo sobre o trafego na rede. Esta estrategia e
usada para verificar o comportamento da rede num cenario em que nao existe uma es-
trategia de encaminhamento, e torna-se um termo de comparacao para o comportamento
da rede usando as tres estrategias implementadas.
7.3 Metricas usadas na simulacao
Para avaliar o desempenho/eficiencia das estrategias implementadas, foram utiliza-
das as seguintes metricas:
• Numero de interesses gerados: numero total de pacotes de interesse gerados, por
todos os nos presentes na rede.
• Interesses recebidos por no: numero medio de interesses recebidos, por no.
• Interesses enviados por no: numero medio de interesses enviados, por no.
• Percentagem de interesses enviados por no (PIntEnv): percentagem de interesses
que foram enviados, em relacao aos interesses que poderiam ter sido enviados, ou
seja, os interesses que nao sao duplicados. Um no pode sempre reencaminhar um
interesse recebido, desde que este nao seja duplicado. E, entao, o resultado da
fracao do numero de interesses enviados (IntEnv) pelo numero de interesses que
poderiam ser enviados, que sao os interesses recebidos (IntRec) menos os interesses
duplicados (IntLoop). A formula usada esta representada na Equacao 7.1.
PIntEnv =IntEnv
IntRec − IntLoop∗ 100 (7.1)
• Percentagem de interesses duplicados recebidos por no (PIntLoop): resultado da
fracao do numero de pacotes de interesse duplicados (IntLoop) pelo numero de
interesses recebidos (IntRec). A formula usada esta representada na Equacao 7.2.
PIntLoop =IntLoopIntRec
∗ 100 (7.2)
• Dados recebidos por no: numero medio de pacotes de dados recebidos, por no.
Capıtulo 7. Testes e Resultados 80
• Dados enviados por no: numero medio de pacotes de dados enviados, por no.
• Percentagem de dados enviados por no (PDataEnv): percentagem de dados que
foram enviados, em relacao aos dados que poderiam ter sido enviados, ou seja,
os dados que nao sao nem duplicados, nem nao solicitados. Um no pode sempre
reencaminhar um pacote de dados recebido, desde que nao seja nem duplicado,
nem nao solicitado (nao contem a entrada PIT do interesse correspondente). E,
entao, o resultado da fracao do numero de pacotes de dados enviados (DataEnv),
pelo numero de pacotes de dados que poderiam ter sido enviados, que sao os dados
recebidos (DataRec), menos os dados nao solicitados (DataNaoSolicitado), menos os
dados duplicados (DataLoop). A formula usada para o calculo da percentagem de
dados enviados esta representada na Equacao 7.3.
PDataEnv =DataEnv
DataRec −DataNaoSolicitado −DataLoop∗ 100 (7.3)
• Percentagem de dados duplicados recebidos por no (PDataLoop): resultado da fracao
do numero de pacotes de dados duplicados recebidos, pelo numero de pacotes de
dados que poderiam ser enviados, que sao os dados recebidos, menos os dados nao
solicitados. A formula usada esta representada na Equacao 7.4, por no.
PDataLoop =DataLoop
DataRec −DataNaoSolicitado∗ 100 (7.4)
• Percentagem de interesses satisfeitos (PIntSatisf ): resultado da fracao do numero
de interesses satisfeitos (IntSatisf ) pelo numero de interesses gerados (IntGerados).
PIntSatisf =IntSatisfIntGerados
∗ 100 (7.5)
• RTT: tempo medio medido no consumidor, desde que envia o pacote de interesse,
ate que recupera o pacote de dados desejado.
Em todos os calculos efetuados para chegar aos valores das metricas, foi feita uma
media por no, e depois por simulacao, com a excecao da primeira metrica (numero de
interesses gerados).
Capıtulo 7. Testes e Resultados 81
7.4 Resultados experimentais
Nesta seccao serao mostrados os resultados obtidos nas simulacoes realizadas, para
verificar o desempenho dos protocolos implementados, atraves da utilizacao das metricas,
explicadas na seccao anterior.
E de notar que foram realizadas vinte repeticoes para cada cenario de simulacao.
O resultado das simulacoes, efetuadas para as tres estrategias implementadas e para
a estrategia de Broadcast, variando o numero de consumidores e produtores, sao descritas
de seguida. Todos os graficos apresentados nesta seccao contem o desvio padrao para
cada medida do grafico.
7.4.1 Trafego de interesses
No grafico da Figura 7.1 esta representado o numero medio de interesses recebidos
por no, por simulacao.
Figura 7.1: Numero medio de interesses recebidos por no
No grafico da Figura 7.2 esta representado o numero medio de interesses enviados
por no, por simulacao.
No grafico da Figura 7.3 esta representada a percentagem media de interesses envi-
ados por no, por simulacao.
No grafico da Figura 7.4 esta representada a percentagem media de interesses du-
plicados recebidos.
Capıtulo 7. Testes e Resultados 82
Figura 7.2: Numero medio de interesses enviados por no
Figura 7.3: Percentagem media de interesses enviados por no
Como se pode verificar, os protocolos BFstrategy e DSRstrategy tem resultados pare-
cidos nos quatro graficos da Figura 7.1, Figura 7.2, Figura 7.3 e Figura 7.4, apresentado
linhas sobrepostas nos quatro graficos, uma vez que utilizam a mesma estrategia no
encaminhamento dos interesses.
Na estrategia Broadcast, a percentagem de interesses enviados por no (grafico da
Figura 7.3) e muito maior em relacao as outras estrategias, sendo de quase 100%, pois
nao tem qualquer restricao nos interesses que reencaminha, acabando por reencaminhar
Capıtulo 7. Testes e Resultados 83
Figura 7.4: Percentagem media de interesses duplicados recebidos
todos. O valor desta percentagem nao e exatamente 100%, devido aos interesses recen-
temente satisfeitos recebidos, ou seja, interesses que ja receberam os dados correspon-
dentes, recentemente. Quando um no recebe um interesse e este e igual a um interesse
recentemente satisfeito, o pacote e descartado. Quanto maior e o trafego, maior e a
probabilidade de isto acontecer e, por isto, a percentagem de interesses enviados por no,
na estrategia Broadcast, diminui, ainda que ligeiramente, com o aumento do trafego.
Apesar de as estrategias BFstrategy, DSRstrategy e Broadcast terem, aproxima-
damente, o mesmo numero de interesses recebidos, o numero de interesses enviados
(grafico da Figura 7.2) e bastante diferente. A estrategia Broadcast envia muitıssimos
mais. Como esta estrategia nao faz qualquer controlo de trafego, o numero de colisoes e
elevado, o que faz com que os nos recebam menos interesses do que os que deveriam re-
ceber, o que diminui, tambem, a percentagem de interesses duplicados recebidos. Entao,
como envia muitos mais pacotes e acaba por receber os mesmos, significa que existe um
maior numero de colisoes na estrategia Broadcast.
Por outro lado, a estrategia MPRstrategy tem um numero muito superior de inte-
resses recebidos (mesmo sem contar com os interesses Hello), em relacao as restantes
estrategias, pois o numero de colisoes de pacotes na rede e muito menor, devido a esta
ser a unica, das quatro, que controla, de facto, o trafego dos interesses na rede.
A percentagem de interesses enviados por no da estrategia MPRstrategy e inferior
as estrategias BFstrategy e DSRstrategy, estando entre os 25 e 30%, enquanto as ultimas
Capıtulo 7. Testes e Resultados 84
estrategias tem percentagens entre os 36 e 43%. Isto acontece devido a utilizacao da
tecnica dos MPRs na estrategia MPRstrategy, que diminui os encaminhamentos de in-
teresses.
A percentagem de interesses duplicados recebidos e, tambem, inferior na estrategia
MPRstrategy, pelas mesmas razoes. Enquanto a estrategia MPRstrategy tem percen-
tagens entre os 45 e 48%, as estrategias BFstrategy e DSRstrategy tem entre os 53 e
58%. Mesmo sendo um valor inferior em relacao as outras estrategias, continua a ser
um valor elevado. Isto acontece devido ao cenario usado, em que os nos tem muitos
vizinhos, devido ao elevado numero de nos, a pequena dimensao do cenario e ao elevado
alcance de transmissao, que faz com que quando um no transmite um pacote, muitos
nos o recebam.
7.4.2 Trafego de dados
No grafico da Figura 7.5 esta representado o numero medio de pacotes de dados
recebidos por no, por simulacao.
Figura 7.5: Numero medio de dados recebidos por no
No grafico da Figura 7.5, e possıvel verificar que a estrategia com menos pacotes
de dados recebidos e a Broadcast, porque e a que tem piores percentagens de interesses
satisfeitos (como se vai verificar na Seccao 7.4.4) e, por isso, os interesses muitas vezes
nao chegam aos produtores, (por colisoes, loops de encaminhamento, congestionamento
das interfaces de saıda, entre outras razoes) e existem menos pacotes de dados na rede.
Capıtulo 7. Testes e Resultados 85
De seguida e a estrategia BFstrategy que tem menos dados recebidos, seguida da
DSRstrategy, e a explicacao e a mesma, ou seja, e devido ao valor da percentagem de
interesses satisfeitos. Por fim, a MPRstrategy tem uma grande diferenca em relacao as
outras estrategias. Mais uma vez deve-se a percentagem de interesses satisfeitos e ao
numero inferior de colisoes, em relacao as outras estrategias.
No grafico da Figura 7.6 esta representado o numero medio de pacotes de dados
enviados por no, por simulacao. Todas as estrategias mantem semelhante a linha de
dados enviados e recebidos, excepto a Broadcast. Nesta estrategia, a linha de dados
enviados sobe, em relacao as outras estrategias. Apesar de enviar muitos mais pacotes,
acaba por receber menos, devido as colisoes.
Figura 7.6: Numero medio de dados enviados por no
No grafico da Figura 7.7 esta representada a percentagem media de pacotes de dados
enviados por no, por simulacao. Neste grafico confirma-se a percentagem de 100% de
pacotes de dados enviados por no, da estrategia Broadcast, com valores nulos de desvio
padrao. Neste caso, como nao existem pacotes de dados recentemente satisfeitos, todos
os pacotes de dados recebidos sao enviados.
As estrategias MPRstrategy e DSRstrategy tem valores muito semelhantes na per-
centagem de pacotes de dados enviados, tendo as suas linhas sobrepostas em quase todas
as amostras, pois utilizam a mesma estrategia, que obriga os dados a seguirem o mesmo
percurso dos interesses correspondentes. Ja a BFstrategy tem um valor ligeiramente in-
ferior. Isto acontece, porque nas estrategias MPRstrategy e DSRstrategy, apenas os nos
Capıtulo 7. Testes e Resultados 86
Figura 7.7: Percentagem media de dados enviados por no
que nao pertencem a rota do interesse e que tem de esperar o perıodo de TData, antes do
reencaminhamento do pacote. Ja na BFstrategy, todos os pacotes tem esse perıodo de
espera e, por isso, a possibilidade de a estrategia abortar o encaminhamento e superior.
No grafico da Figura 7.8 esta representada a percentagem media de pacotes de dados
duplicados recebidos.
Figura 7.8: Percentagem media de dados duplicados recebidos
E possıvel verificar que as estrategias MPRstrategy e DSRstrategy tem, novamente,
valores muito semelhantes, pelas mesmas razoes. Ainda assim, a MPRstrategy tem um
Capıtulo 7. Testes e Resultados 87
valor ligeiramente superior, devido ao facto de haverem mais pacotes de dados na rede,
que aumenta a probabilidade de dados duplicados.
A estrategia BFstrategy tem um valor inferior, em relacao as estrategias MPRstrategy
e DSRstrategy, devido a menor quantidade de pacotes de dados na rede, maior numero
de colisoes e menor numero de interesses satisfeitos.
Por fim, a estrategia Broadcast tem, inicialmente, o valor mais baixo, mas a medida
que o trafego aumenta, a sua percentagem de dados duplicados aumenta acentuada-
mente. Isto deve-se ao nao controlo de pacotes da rede.
7.4.3 RTT
No grafico da Figura 7.9 esta representado o tempo medio usado pelo consumidor,
desde que envia o pacote de interesse, ate que recupera o pacote de dados desejado, por
simulacao.
Figura 7.9: RTT medio
Naturalmente, a estrategia Broadcast e a que apresenta tempos mais baixos, porque
e a unica que nao utiliza tempos de atraso nem nos encaminhamentos de interesses, nem
nos de dados.
A estrategia seguinte com o valor mais baixo e a MPRstrategy. Apesar de, tal como
as estrategias BFstrategy e DSRstrategy, tambem esperarem um determinado tempo
antes de enviarem um interesse, a MPRstrategy apresenta um RTT inferior, pois tem
controlo no trafego.
Capıtulo 7. Testes e Resultados 88
As estrategias BFstrategy e DSRstrategy tem valores semelhantes, pois utilizam os
mesmos tempos de atraso. A BFstrategy tem valores ligeiramente superiores, em relacao
a DSRstrategy, devido ao encaminhamento diferente dos dados.
7.4.4 Percentagem de interesses satisfeitos
No grafico da Figura 7.10 esta representada a percentagem media de interesses
satisfeitos, por simulacao.
Figura 7.10: Percentagem media de interesses satisfeitos
Quando e aumentado o numero de consumidores, o comportamento dos protocolos
degrada-se. Isto acontece, pois quantos mais consumidores houverem, maior e o trafego,
devido ao aumento da quantidade de interesses gerados, o que implica mais pacotes de
interesses e dados duplicados, atraso na recuperacao dos dados e mais colisoes.
No caso dos protocolos BFstrategy e DSRstrategy, um outro fator que pode levar a
que os pacotes colidam e se os potenciais encaminhadores usarem o mesmo tempo de
atraso TInterest e TData. Outro problema e a possibilidade de alguns nos nao receberem
os pacotes, como foi explicado na Seccao 5.1.3. De facto, como estes dois protocolos se
baseiam num encaminhamento blind forwarding no encaminhamento de interesses, nao
tem controlo no trafego da rede, o que degrada o seu desempenho.
No entanto, o protocolo da DSRstrategy tem resultados melhores do que a BFstra-
tegy, devido ao comportamento diferente dos dois protocolos no encaminhamento dos
dados. Enquanto a BFstrategy inunda a rede com o pacote de dados, para este chegar
Capıtulo 7. Testes e Resultados 89
ao seu consumidor, a DSRstrategy forca os dados a seguirem o percurso do interesse.
Assim, na estrategia DSRstrategy os dados tem uma rota que tentam seguir, o que se
reflete numa melhoria no protocolo da DSRstrategy em relacao ao da BFstrategy.
Por outro lado, o comportamento do protocolo da MPRstrategy e o que apresenta
melhores resultados. Como esta estrategia limita o numero de nos que encaminham os
interesses, escolhendo apenas os necessarios para que todos os nos recebam, o numero
de colisoes e menor, em relacao as estrategias BFstrategy e DSRstrategy.
No entanto, esta estrategia tem uma descida mais acentuada. Como e escolhido
um numero muito reduzido de nos para retransmitirem os interesses, se esses nos nao
receberem o pacote (por colisoes, por exemplo), o encaminhamento do interesse termina
e este nao chega ao produtor. Quanto maior for o trafego, maior e a probabilidade de
colisoes e maior e a probabilidade de este problema acontecer.
Ja a estrategia Broadcast tem sempre pessimos resultados, o que prova que o controlo
do trafego da rede e extremamente importante e, por isso, os protocolos de encaminha-
mento continuam a ser necessarios neste tipo de redes, o que vem a concordar com a
teoria dos autores de [30], abordada na Seccao 3.5.
Com estes resultados, e possıvel afirmar que, usando o protocolo MPRstrategy, e
viavel a utilizacao de redes NDN num ambiente de redes Ad hoc. As redes Ad hoc
tem varias vantagens, desde a sua facil instalacao, uma vez que este tipo de rede pode
ser estabelecida em locais onde nao haja uma estrutura de rede previamente instalada;
e tolerante a falhas, pois as perdas de conectividade entre nos podem ser facilmente
resolvidas, desde que possa ser estabelecida uma nova rota; dois nos podem comunicar
diretamente, desde que estejam no raio de alcance um do outro, ao contrario das redes
baseadas numa infraestrutura, em que a comunicacao tem de ser feita por meio de um
no central; por fim, a sua mobilidade e uma grande vantagem em relacao as redes fixas.
No entanto, tem tambem desvantagens: a topologia de uma rede Ad hoc muda cons-
tantemente, o que dificulta muito a construcao de protocolos de encaminhamento com
bom desempenho, o que faz com que as taxas de erros sejam muito mais elevadas em
relacao a uma rede fixa. Alem disso, e difıcil localizar um no, pois o endereco da maquina
nao tem qualquer relacao com a sua localizacao. Assim, se a troca de mensagens nas
redes Ad Hoc for baseada na arquitetura IP, onde se utiliza o paradigma normal de en-
trega de mensagens entre uma origem e um destino, os protocolos de encaminhamento
terao dificuldades em localizar os destinos e, consequentemente, calcularem rotas ate
eles. Teriam de usar mensagens de controlo para os encontrar, e, como a rede e muito
Capıtulo 7. Testes e Resultados 90
dinamica, teriam de enviar essas mensagens muito frequentemente, para terem a topo-
logia atualizada. Isto faria com que se gerasse um grande overhead na rede e uma taxa
de erros elevada.
Assim, uma rede de dados nomeados, baseada na subscricao e publicacao de conteudos,
so traz vantagens para as redes Ad Hoc, desde que seja usado um bom protocolo de en-
caminhamento.
Capıtulo 8
Conclusao e trabalho futuro
8.1 Conclusao
O principal objetivo deste trabalho era estudar a viabilidade de usar o paradigma
dos dados nomeados no contexto de uma rede Ad hoc. Nas redes Ad hoc, a topologia
da rede e muito dinamica, devido a mobilidade dos nos, a entrada e saıda de nos na
rede e as quebras de ligacoes constantes, que provocam alteracoes inesperadas das ro-
tas. Alem disso, o meio de comunicacoes sem fios e partilhado entre os nos vizinhos.
Assim, o principal problema deste tipo de redes e lidar com essa dinamica, pois existe a
necessidade do conhecimento da topologia da rede, total ou parcial, para o calculo das
melhores rotas.
Neste contexto, a abordagem NDN podera ser particularmente benefica. Nas NDNs,
os nos moveis podem comunicar com base nos dados que precisam, em vez de calcularem
um caminho especıfico para chegarem a um no especıfico. Numa rede Ad Hoc, isto
poderia simplificar muito a implementacao, por varias razoes. Em primeiro lugar, nao
era necessario atribuir enderecos IP a cada no; em vez disso, os nos podiam usar os
nomes dos dados, diretamente, para transmitirem pacotes de interesses e de dados entre
si. Outro benefıcio das NDN nas redes moveis e a capacidade de lidar com a fragmentacao
dos dados. As NDN permitem o armazenamento em cache, mesmo quando os caminhos
nao sao estaveis, nem previsıveis. Dado que qualquer fragmento de informacao tem
uma identificacao unica, este pode ser armazenado em cache, em qualquer no que o
encaminhe, e pode ser reutilizado se outros nos o solicitarem [1].
De forma a tentar perceber os benefıcios e os malefıcios da utilizacao de dados
nomeados nas redes Ad hoc, foi implementado um cenario de teste e tres protocolos de
91
Capıtulo 8. Conclusao 92
encaminhamento: BFstrategy, DSRstrategy e MPRstrategy.
A BFstrategy baseia-se no protocolo Blind Forwarding (BF) e tem como objetivo
principal adiar a transmissao de interesses e dados, por um intervalo de tempo, calculado
aleatoriamente, a fim de diminuir a probabilidade de colisoes. Se durante esse tempo
de espera, o no receber um interesse ou pacote de dados com o mesmo prefixo (no caso
de estar a adiar a transmissao de um interesse), ou um pacote de dados com o mesmo
prefixo (no caso de estar a adiar a transmissao de um pacote de dados), a transmissao
do pacote e abortada, pois considera-se que outro no ja reencaminhou o pacote, e um
novo encaminhamento deste e desnecessario.
Na DSRstrategy, o encaminhamento dos interesses e semelhante a estrategia BFs-
trategy, ou seja, adia a transmissao dos interesses, por um intervalo de tempo calculado
aleatoriamente, e descarta-o caso “oica” um pacote igual na rede. Por outro lado, os da-
dos seguem a rota percorrida pelo interesse. Quando um no recebe um pacote de dados,
verifica se pertence a rota do interesse, que esta armazenada no cabecalho do pacote
de dados. Caso pertenca, reencaminha o pacote; caso contrario, adia a transmissao do
pacote, por um intervalo de tempo calculado aleatoriamente, e descarta-o caso “oica” o
mesmo pacote na rede.
A MPRstrateggy foi baseada na tecnica MultiPoint Relay, que e usada pelo protocolo
OLSR, e tem o objetivo de limitar os nos da rede que reencaminham os interesses,
a fim de se eliminarem pacotes redundantes. Assim, a sua funcao e selecionar um
subconjunto de nos da rede, chamados Multipoint relay (MPR), atraves dos quais seja
possıvel disseminar os interesses por toda a rede, ate se encontrar um produtor. A
escolha dos MPRs e feita de modo a que cubram todos os nos a dois saltos de distancia.
Quanto ao encaminhamento de pacotes de dados, este e semelhante ao comportamento
da estrategia DSRstrategy, ou seja, os dados seguem o percurso inverso do interesse.
Foram feitas varias simulacoes, de forma a verificar o comportamento do cenario e
avaliar as varias estrategias de encaminhamento implementadas. Os resultados obtidos
demonstraram que a utilizacao de escutas ao meio para prevenir colisoes, combinada com
tempos de espera aleatorios e uma escolha criteriosa dos nos vizinhos, para expedicao
de interesses e dados, permite melhorar substancialmente o desempenho dos protocolos
de encaminhamento.
Foi possıvel verificar, tambem, que o comportamento das estrategias BFstrategy
e DSRstrategy e semelhante, principalmente no trafego de interesses, pois utilizam a
Capıtulo 8. Conclusao 93
mesma tecnica. Como estas estrategias sao baseadas no encaminhamento Blind Forwar-
ding, nao tem o controlo na propagacao de pacotes na rede e nao evitam completamente
as colisoes de pacotes. De facto, os pacotes podem colidir se, por exemplo, os potenciais
encaminhadores usarem o mesmo tempo de atraso TInterest e TData, ou se estes tempos
forem muito pequenos.
No entanto, o comportamento da DSRstrategy e ligeiramente melhor em relacao a
BFstrategy, devido as diferencas no encaminhamento dos pacotes de dados. Enquanto a
estrategia DSRstrategy forca os dados a seguirem o percurso do interesse, a BFstrategy
inunda a rede com o pacote de dados, para este chegar ao consumidor. Assim, na
estrategia DSRstrategy os dados tem uma rota que tentam seguir, fazendo com que haja
uma diminuicao significativa do RTT, o que se reflete numa melhoria da DSRstrategy
em relacao a BFstrategy.
Por outro lado, o protocolo MPRstrategy mostrou ter um bom desempenho. O nıvel
de satisfacao dos interesses esta entre os 60 e 88%, o que e um valor muito animador
neste tipo de redes.
De facto, usando o protocolo MPRstrategy, e possıvel afirmar que e viavel a utilizacao
do paradigma dos dados nomeados no contexto de uma rede Ad hoc.
Uma rede Ad Hoc nao depende de uma infraestrutura fixa e trabalha num meio sem
fios, o que permite que dispositivos moveis possam formar uma rede, em cenarios onde
exista uma necessidade de se instalar rapidamente uma rede de comunicacao. Normal-
mente, sao situacoes onde nao ha uma infraestrutura de rede previamente instalada, ou
numa situacao posterior a uma catastrofe natural, em que a infraestrutura tenha sido
destruıda. Num cenario de coordenacao de resgates, em situacoes de desastre ou troca
de informacoes taticas em campos de batalha, uma rede Ad Hoc pode ser muito util.
Por isto, e extremamente importante melhorar este tipo de redes e tentar contornar as
suas desvantagens.
8.2 Trabalho Futuro
Os resultados obtidos da abordagem NDN no contexto de rede moveis Ad hoc foram
animadores. No entanto, estes resultados poderiam ter sido comparados com uma rede
Ad hoc pura, sem a abordagem NDN, e com as mesmas estrategias de encaminhamento
nos dois cenarios, de forma a verificar todos os problemas das redes Ad Hoc.
Capıtulo 8. Conclusao 94
Alem disso, seria interessante fazer mais testes aos protocolos propostos e imple-
mentados, noutros cenarios e com diferentes modelos de mobilidade, para representar
diferentes situacoes possıveis da utilizacao deste tipo de redes. Um cenario de um campo
de batalha e bem diferente de uma sala de aulas. Devido ao tempo necessario para a
realizacao dos testes aos protocolos propostos, ficaram alguns testes interessantes por
realizar.
Outra tarefa interessante seria tentar implementar um encaminhamento com garan-
tias de QoS no trafego fim a fim, para proporcionar aos utilizadores uma boa experiencia
de utilizacao da rede com aplicacoes exigentes, nomeadamente aplicacoes sensıveis ao
atraso. Nas redes Ad hoc, a capacidade de garantir o encaminhamento de trafego, com
garantias de qualidade de servico (QoS), de forma a cumprir certas exigencias pretendi-
das pelo cliente ao utilizar certo servico, constitui um desafio ainda maior do que faze-lo
nas redes fixas, devido a topologia dinamica e imprevisıvel [13].
Por fim, uma outra tarefa a ser realizada seria melhorar o encaminhamento dos dados
no protocolo MPRstrategy. Neste momento, este protocolo nao controla exatamente o
encaminhamento dos dados. Apesar de forcar os dados a seguirem o mesmo percurso
dos interesses, existem, certamente, muitas ocasioes em que a rota e destruıda, devido a
dinamica da topologia. Nestes casos, os dados apenas esperam um determinado tempo
antes do reencaminhamento, para “ouvirem” a rede. Se receberem um pacote igual
durante o tempo de espera, abortam o encaminhamento. E so este o controlo dos
pacotes de dados, que podera nao ser suficiente na presenca de uma rede densa, por
exemplo. De facto, se o encaminhamento dos dados fosse melhorado, o desempenho das
redes de dados nomeados num contexto Ad Hoc poderia ser ainda mais satisfatorio.
Apendice A
Algoritmos da estrategia
BFstrategy
A.1 Encaminhamento de interesses
Listagem 1 Algoritmo onIncomingInterest - BFstrategy, forwarder.cpp
1: Funcao onIncomingInterest2: ...3: se o interesse estiver em loop e a estrategia de encaminhamento utilizada for a
BFstrategy ou DSRstrategy entao4: variavel loop = 15: se a estrategia de encaminhamento utilizada for a BFstrategy entao6: Ir para a funcao afterReceiveInterest do BFstrategy.cpp.7: senao8: Ir para a funcao afterReceiveInterest do DSRstrategy.cpp.9: fim se
10: fim se11: ...12: fim Funcao
95
Anexo A. Algoritmos da estrategia BFstrategy 96
Listagem 2 Algoritmo afterReceiveInterest - BFstrategy, BFstrategy.cpp
1: Funcao afterReceiveInterest2: ...3: se for possıvel reencaminhar o interesse entao4: se a interface de entrada for local (significa que e o consumidor a enviar o
interesse, criado por si) entao5: Enviar o interesse pela interface de saıda.6: senao7: Ir para funcao wait interest.8: fim se9: fim se
10: ...11: fim Funcao
Listagem 3 Algoritmo wait interest - BFstrategy, BFstrategy.cpp
1: Funcao wait interest2: se a interface de saıda for local (significa que e o produtor a receber o interesse,
e contem os dados correspondentes) e nao esta em loop entao3: Enviar o interesse pela interface de saıda.4: fim se5: para cada elemento da Tabela de interesses atrasados fazer6: se existir algum elemento da Tabela, cujo campo “prefixo” seja igual ao
prefixo do interesse recebido entao7: Marcar campo “validade” desse elemento a false.8: fim se9: fim para
10: se o interesse recebido e unico na Tabela de interesses atrasados e nao esta emloop e nao e o produtor entao
11: Adicionar o interesse a Tabela de interesses atrasados, com: (ID do interesse,prefixo do interesse, true, false).
12: Calcular o valor aleatorio de TInterest antes do envio do interesse.13: Programar ida para a funcao sendInterest, depois de um perıodo igual a
TInterest.14: senao15: Rejeitar o interesse recebido.16: fim se17: fim Funcao
Anexo A. Algoritmos da estrategia BFstrategy 97
Listagem 4 Algoritmo sendInterest - BFstrategy, BFstrategy.cpp
1: Funcao sendInterest2: para cada elemento da Tabela de interesses atrasados fazer3: se o campo “prefixo” do elemento for igual ao prefixo do interesse a ser
enviado entao4: se o campo “dados” do elemento e igual a false e o campo “validade” do
elemento e igual a true entao5: Enviar o interesse pela interface de saıda.6: senao7: Rejeitar o interesse.8: fim se9: Apagar o elemento da Tabela de interesses atrasados.
10: fim se11: fim para12: fim Funcao
A.2 Encaminhamento de dados
Listagem 5 Algoritmo onIncomingData - BFstrategy, forwarder.cpp
1: Funcao onIncomingData2: ...3: se a estrategia de encaminhamento utilizada for a BFstrategy entao4: Ir para a funcao wait data.5: senao6: Enviar o pacote de dados pela interface de saıda.7: fim se8: fim Funcao
Anexo A. Algoritmos da estrategia BFstrategy 98
Listagem 6 Algoritmo wait data - BFstrategy, forwarder.cpp
1: Funcao wait data2: se a interface de saıda for local (significa que e o consumidor a receber o pacote
de dados) ou se a interface de entrada for local (significa que e o produtor a enviaros seus dados) entao
3: Enviar o pacote de dados.4: fim se5: para cada elemento da Tabela de dados atrasados fazer6: se o campo “prefixo” do elemento for igual ao prefixo do pacote de dados
acabado de receber entao7: Alterar o campo “validade” do elemento da Tabela para false.8: fim se9: fim para
10: para cada elemento da Tabela de interesses atrasados fazer11: se o campo “prefixo” do elemento for igual ao prefixo do pacote de dados
acabado de receber entao12: Alterar o campo “dados” do elemento da Tabela para true.13: fim se14: fim para15: se nao existe nenhum elemento da Tabela de dados atrasados com o campo
“prefixo” igual ao prefixo do pacote de dados recebido entao16: Adicionar o pacote de dados a Tabela de dados atrasados, com: (ID dos
dados, prefixo dos dados, true).17: Calcular o valor aleatorio para TData antes do envio do pacote de dados.18: Programar ida para a funcao sendData, depois de um perıodo igual a TData.19: senao20: Rejeitar o pacote de dados recebido.21: fim se22: fim Funcao
Listagem 7 Algoritmo sendData - BFstrategy, forwarder.cpp
1: Funcao sendData2: para cada elemento da Tabela de dados atrasados fazer3: se o campo “prefixo” do elemento for igual ao prefixo do pacote de dados a
ser enviado entao4: se o campo “validade” do elemento da Tabela e igual a true entao5: Enviar pacote de dados.6: senao7: Rejeitar pacote de dados.8: fim se9: Apagar o elemento da Tabela de dados atrasados.
10: fim se11: fim para12: fim Funcao
Apendice B
Algoritmos da estrategia
DSRstrategy
B.1 Encaminhamento de interesses
Listagem 8 Algoritmo onOutgoingInterest - DSRstrategy, forwarder.cpp
1: Funcao onOutgoingInterest2: ...3: se a estrategia de encaminhamento utilizada for a DSRstrategy entao4: Adicionar o ID do proprio no ao campo “Rota” do cabecalho do interesse.5: se a interface de saıda for local (significa que e o produtor a receber o interesse
e possui os dados correspondentes) entao6: Guardar a rota do interesse, para, posteriormente, coloca-la no cabecalho
do pacote de dados.7: fim se8: fim se9: ...
10: fim Funcao
B.2 Encaminhamento de dados
99
Anexo B. Algoritmos da estrategia DSRstrategy 100
Listagem 9 Algoritmo onIncomingData - DSRstrategy, forwarder.cpp
1: Funcao onIncomingData2: ...3: se a estrategia de encaminhamento utilizada for a DSRstrategy ou MPRstrategy
entao4: se a interface de entrada for local (significa que e o produtor a enviar os dados
e, por isso, nao precisa de verificar se pertence a rota) entao5: Enviar pacote de dados pela interface de saıda.6: senao7: Ir buscar campo “Rota” do cabecalho do pacote de dados.8: se o no pertencer a rota do pacote de dados entao9: Enviar pacote de dados pela interface de saıda.
10: senao11: Ir para a funcao wait data.12: fim se13: fim se14: senao15: Enviar pacote de dados pela interface de saıda.16: fim se17: fim Funcao
Apendice C
Algoritmos da estrategia
MPRstrategy
C.1 Encaminhamento de interesses
Listagem 10 Algoritmo afterReceiveInterest - MPRstrategy, MPRstrategy.cpp
1: Funcao afterReceiveInterest2: para cada nexthop da FibEntry fazer3: se o interesse nao tem prefixo “/hello” e se nao e o produtor a receber o
interesse, nem o consumidor a enviar o interesse entao4: Ir buscar valor do campo “MPR” ao cabecalho do interesse.5: se o no pertencer ao conjunto de nos MPRs definidos no cabecalho do
interesse e for possıvel enviar o interesse entao6: Adicionar o interesse a Tabela de interesses atrasados, com: (ID do
interesse, prefixo do interesse, true, false).7: Calcular o valor aleatorio de TInterestMPR antes do envio do interesse.8: Programar ida para a funcao sendInterest, depois de um perıodo igual
a TInterestMPR.9: senao
10: Rejeitar o interesse.11: fim se12: senao13: se for possıvel enviar o interesse entao14: Enviar o interesse.15: senao16: Rejeitar o interesse.17: fim se18: fim se19: fim para20: fim Funcao
101
Anexo C. Algoritmos da estrategia MPRstrategy 102
Listagem 11 Algoritmo sendInterest - MPRstrategy, MPRstrategy.cpp
1: Funcao sendInterest2: para cada elemento da Tabela de interesses atrasados fazer3: se o campo “prefixo” do elemento for igual ao prefixo do interesse entao4: se o campo “dados” do elemento e igual a false entao5: Enviar o interesse pela interface de saıda.6: senao7: Rejeitar o interesse.8: fim se9: Apagar o elemento da Tabela de interesses atrasados.
10: fim se11: fim para12: fim Funcao
Listagem 12 Algoritmo onOutgoingInterest - MPRstrategy, forwarder.cpp
1: Funcao onOutgoingInterest2: ...3: se a estrategia de encaminhamento utilizada for a MPRstrategy entao4: Adicionar o ID do proprio no ao campo “Rota” do cabecalho do interesse.5: se a interface de saıda for local (significa que e o produtor a receber o interesse
e possui os dados correspondentes) entao6: Guardar a rota do interesse, para, posteriormente, coloca-la no cabecalho
do pacote de dados.7: fim se8: fim se9: se a estrategia de encaminhamento utilizada e a MPRstrategy, se o prefixo do
interesse nao e “/hello” e a interface saıda nao e local (significa que vai enviar opacote para a rede) entao
10: Calcular conjunto de MPRs.11: se o conjunto de MPRs for vazio entao12: Nao enviar interesse.13: senao14: Alterar campo “MPR” do cabecalho do interesse com o valor obtido.15: fim se16: fim se17: se o prefixo do interesse for “/hello” e a interface de saıda for local (significa que
e o produtor a receber o interesse e, por isso, ira enviar o pacote de dados com osseus vizinhos) entao
18: Enviar interesse “/hello” pela interface local.19: senao20: Enviar interesse pela interface de saıda.21: fim se22: fim Funcao
C.2 Encaminhamento de dados
Anexo C. Algoritmos da estrategia MPRstrategy 103
Listagem 13 Algoritmo onIncomingData - MPRstrategy, forwarder.cpp
1: Funcao onIncomingData2: ...3: se a estrategia de encaminhamento utilizada for a MPRstrategy entao4: se a interface de entrada for local (significa que e o produtor a enviar os
dados) e o prefixo do pacote e “/hello” entao5: Adicionar o pacote a Tabela de dados Hello atrasados, com: (ID dos
dados, pacote).6: Calcular o valor aleatorio para de THello antes do envio do pacote.7: Programar ida para a funcao sendHello, depois de um perıodo igual aTHello.
8: fim se9: fim se
10: fim Funcao
Listagem 14 Algoritmo sendHello - MPRstrategy, forwarder.cpp
1: Funcao sendHello2: para cada elemento da Tabela de dados “/hello” atrasados fazer3: se o campo “ID” do elemento for igual ao prefixo do pacote de dados entao4: Construir string com o seu ID.5: para cada elemento da Tabela Vizinhos fazer6: Acrescentar a string o campo “ID do vizinho” de todos os elementos
da Tabela Vizinhos.7: fim para8: Copiar string para o conteudo do pacote de dados “/hello”.9: Enviar o pacote de dados pela interface de saıda.
10: Apagar o elemento da Tabela de dados “/hello” atrasados.11: fim se12: fim para13: fim Funcao
Anexo C. Algoritmos da estrategia MPRstrategy 104
Listagem 15 Algoritmo onOutgoingData - MPRstrategy, forwarder.cpp
1: Funcao onOutgoingData2: se o prefixo do pacote de dados e “/hello” e a interface de entrada e de saıda sao
locais (significa que e o produtor a enviar o pacote de dados, produzido por si, parasi proprio) entao
3: Return.4: senao5: se o prefixo do pacote de dados e “/hello” e a interface de entrada e de saıda
sao nao locais (significa que e o produtor a reencaminhar o pacote de dados, recebidoda rede, para outro no) entao
6: Return.7: fim se8: se o prefixo do pacote de dados nao e “/hello” e a interface de saıda for local
(significa que e o produtor a enviar os dados) entao9: Copiar a rota do interesse para o cabecalho do pacote de dados.
10: fim se11: fim se12: ...13: fim Funcao
Bibliografia
[1] Michael Meisel, Vasileios Pappas, and Lixia Zhang. Ad hoc networking via named
data. In Proceedings of the fifth ACM international workshop on Mobility in the
evolving internet architecture, pages 3–8. ACM, 2010.
[2] Xiaoyan Hong, Kaixin Xu, and Mario Gerla. Scalable routing protocols for mobile
ad hoc networks. Network, IEEE, 16(4):11–21, 2002.
[3] Charles Perkins, Elizabeth Belding-Royer, and Samir Das. Ad hoc on-demand
distance vector (aodv) routing. Technical report, 2003.
[4] Paulo Alexandre Gomes Duarte. Dados nomeados para redes tolerantes a atrasos.
2014.
[5] Marica Amadeo, Claudia Campolo, and Antonella Molinaro. Forwarding strategies
in named data wireless ad hoc networks: Design and evaluation. Journal of Network
and Computer Applications, 50:148–158, 2015.
[6] Alexander Afanasyev, Junxiao Shi, Beichuan Zhang, Lixia Zhang, Ilya Moi-seenko,
Yingdi Yu, Wentao Shang, Yi Huang, Jerald Paul Abraham, Steve DiBenedetto,
et al. Nfd developers guide. Technical report, Technical Report NDN-0021, NDN
Project, 2014.
[7] Lixia Zhang, Deborah Estrin, Jeffrey Burke, Van Jacobson, James D Thornton,
Diana K Smetters, Beichuan Zhang, Gene Tsudik, Dan Massey, Christos Papado-
poulos, et al. Named data networking (ndn) project. Relatorio Tecnico NDN-0001,
Xerox Palo Alto Research Center-PARC, 2010.
[8] Spyridon Mastorakis, Alexander Afanasyev, Ilya Moiseenko, and Lixia Zhang. ndn-
sim 2.0: A new version of the ndn simulator for ns-3. Technical report, Tech. Report
NDN-0028, 2015.
105
Bibliografia 106
[9] Joseph Macker. Mobile ad hoc networking (manet): Routing protocol performance
issues and evaluation considerations. 1999.
[10] Samir R Das, Robert Castaneda, and Jiangtao Yan. Simulation-based performance
evaluation of routing protocols for mobile ad hoc networks. Mobile networks and
applications, 5(3):179–189, 2000.
[11] Zygmunt J Haas and Marc R Pearlman. The performance of query control schemes
for the zone routing protocol. IEEE/ACM Transactions on Networking (TON), 9
(4):427–438, 2001.
[12] Guangyu Pei, Mario Gerla, and Xiaoyan Hong. Lanmar: landmark routing for large
scale wireless ad hoc networks with group mobility. In Proceedings of the 1st ACM
international symposium on Mobile ad hoc networking & computing, pages 11–18.
IEEE Press, 2000.
[13] Tiago Filipe Meneses Magalhaes Coelho. Encaminhamento com qos em redes moveis
ad hoc. 2013.
[14] Guangyu Pei, Mario Gerla, and Tsu-Wei Chen. Fisheye state routing in mobile ad
hoc networks. In In ICDCS Workshop on Wireless Networks and Mobile Computing,
page 71–78, 2000. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
10.1.1.43.6730.
[15] Philippe Jacquet, Paul Muhlethaler, Thomas Clausen, Anis Laouiti, Amir Qayyum,
and Laurent Viennot. Optimized link state routing protocol for ad hoc networks. In
Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century.
Proceedings. IEEE International, pages 62–68. IEEE, 2001.
[16] Amir Qayyum, Laurent Viennot, and Anis Laouiti. Multipoint relaying: An efficient
technique for flooding in mobile wireless networks. 2000.
[17] David B Johnson and David A Maltz. Dynamic source routing in ad hoc wireless
networks. In Mobile computing, pages 153–181. Springer, 1996.
[18] Guangyu Pei, Mario Gerla, Xiaoyan Hong, and Ching-Chuan Chiang. A wireless
hierarchical routing protocol with group mobility. In Wireless Communications and
Networking Conference, 1999. WCNC. 1999 IEEE, pages 1538–1542. IEEE, 1999.
Bibliografia 107
[19] Ching-Chuan Chiang and Mario Gerla. Routing and multicast in multihop, mobile
wireless networks. In Universal Personal Communications Record, 1997. Conference
Record., 1997 IEEE 6th International Conference on, volume 2, pages 546–551.
IEEE, 1997.
[20] Julio C Navas and Tomasz Imielinski. Geocast—geographic addressing and routing.
In Proceedings of the 3rd annual ACM/IEEE international conference on Mobile
computing and networking, pages 66–76. ACM, 1997.
[21] Young-Bae Ko and Nitin H Vaidya. Location-aided routing (lar) in mobile ad hoc
networks. Wireless Networks, 6(4):307–321, 2000.
[22] Brad Karp and Hsiang-Tsung Kung. Gpsr: Greedy perimeter stateless routing for
wireless networks. In Proceedings of the 6th annual international conference on
Mobile computing and networking, pages 243–254. ACM, 2000.
[23] Cheng Yi, Alexander Afanasyev, Ilya Moiseenko, Lan Wang, Beichuan Zhang, and
Lixia Zhang. A case for stateful forwarding plane. Computer Communications, 36
(7):779–791, 2013.
[24] Lixia Zhang, Alexander Afanasyev, Jeffrey Burke, Van Jacobson, Patrick Crowley,
Christos Papadopoulos, Lan Wang, Beichuan Zhang, et al. Named data networking.
ACM SIGCOMM Computer Communication Review, 44(3):66–73, 2014.
[25] Van Jacobson, Diana K Smetters, James D Thornton, Michael F Plass, Nicholas H
Briggs, and Rebecca L Braynard. Networking named content. In Proceedings of the
5th international conference on Emerging networking experiments and technologies,
pages 1–12. ACM, 2009.
[26] Alexander Afanasyev, Priya Mahadevan, Ilya Moiseenko, Ersin Uzun, and Lixia
Zhang. Interest flooding attack and countermeasures in named data networking. In
IFIP Networking Conference, 2013, pages 1–9. IEEE, 2013.
[27] Van Jacobson, Jeffrey Burke, Deborah Estrin, Lixia Zhang, Beichuan Zhang, Gene
Tsudik, Kim Claffy, Dmitri Krioukov, Dan Massey, Christos Papadopoulos, et al.
Named data networking (ndn) project 2012-2013 annual report, 2014.
[28] Tobias Lauinger, Nikolaos Laoutaris, Pablo Rodriguez, Thorsten Strufe, Ernst Bi-
ersack, and Engin Kirda. Privacy risks in named data networking: what is the cost
Bibliografia 108
of performance? ACM SIGCOMM Computer Communication Review, 42(5):54–57,
2012.
[29] Cheng Yi, Alexander Afanasyev, Lan Wang, Beichuan Zhang, and Lixia Zhang.
Adaptive forwarding in named data networking. ACM SIGCOMM computer com-
munication review, 42(3):62–67, 2012.
[30] Cheng Yi, Jerald Abraham, Alexander Afanasyev, Lan Wang, Beichuan Zhang, and
Lixia Zhang. On the role of routing in named data networking. In Proceedings of
the 1st international conference on Information-centric networking, pages 27–36.
ACM, 2014.
[31] Michael Meisel, Vasileios Pappas, and Lixia Zhang. Listen first, broadcast later:
Topology-agnostic forwarding under high dynamics. In Annual conference of inter-
national technology alliance in network and information science, page 8, 2010.
[32] Yu-Ting Yu, Raheleh B Dilmaghani, Seraphin Calo, MY Sanadidi, and Mario Gerla.
Interest propagation in named data manets. In Computing, Networking and Com-
munications (ICNC), 2013 International Conference on, pages 1118–1122. IEEE,
2013.
[33] Marica Amadeo, Antonella Molinaro, and Giuseppe Ruggeri. E-chanet: Routing,
forwarding and transport in information-centric multihop wireless networks. Com-
puter Communications, 36(7):792–803, 2013.
[34] Thomas Clausen and Philippe Jacquet. Optimized link state routing protocol (olsr).
Technical report, 2003.
[35] Van Jacobson, Diana K Smetters, James D Thornton, Michael F Plass, Nicholas H
Briggs, and Rebecca L Braynard. Networking named content. In Proceedings of the
5th international conference on Emerging networking experiments and technologies,
pages 1–12. ACM, 2009.
[36] Ndn packet format specification 0.2-alpha-3 documentation - tlv @ONLINE, Octo-
ber 2015. URL http://named-data.net/doc/ndn-tlv/tlv.html.
[37] Ndn packet format specification 0.2-alpha-3 documentation - interest packet @ON-
LINE, October 2015. URL http://named-data.net/doc/ndn-tlv/interest.
html.
Bibliografia 109
[38] Ndn packet format specification 0.2-alpha-3 documentation - data packet @ON-
LINE, October 2015. URL http://named-data.net/doc/ndn-tlv/data.htmll.
[39] Alexander Afanasyev, Ilya Moiseenko, Lixia Zhang, et al. ndnsim: Ndn simulator
for ns-3. University of California, Los Angeles, Tech. Rep, 2012.
Recommended