Dados Nomeados em Redes Móveis Ad Hoc · neste tipo de redes, a topologia da rede e muito din^amica, devido a mobilidade dos n os, a entrada e sa da de n os na rede e as quebras

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.3 Estrategia MPRstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.3.1 Encaminhamento de mensagens hello . . . . . . . . . . . . . . . . . 43


5.3.2.1 Algoritmo MPR . . . . . . . . . . . . . . . . . . . . . . . 46


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.3 Estrategia MPRstrategy . . . . . . . . . . . . . . . . . . . . . . . . 71

6.5.3.1 Encaminhamento de mensagens hello . . . . . . . . . . . 72



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;


• 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.


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


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


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.


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


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.


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].


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.


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


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].


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.


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.


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.


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


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.


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.


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,


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.


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.


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.


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.


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


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.


LFBL NAIF E-CHANET BF PAF

Cenario deaplicacao

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


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.


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


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


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.


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.



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.



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


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


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.



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.


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.


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.


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


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.


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.


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


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.



Figura 5.9: Fluxograma da tecnica MPR


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


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.


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.


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.


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.


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


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


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].


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.


• 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


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]


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.


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


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


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


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.


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


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


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.


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.


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.


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


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.


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.


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.


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


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.


Como foi criada uma nova estrategia, foi necessario criar dois arquivos: MPRstra-

tegy.cpp e MPRstrategy.hpp.


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.


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.


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.


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.


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;




• 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.


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.


• 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).


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.


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


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


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.


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


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


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.


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


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


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


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.


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


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


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.


Apendice B


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


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.


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


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


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.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.6730

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.6730

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.

http://named-data.net/doc/ndn-tlv/tlv.html

http://named-data.net/doc/ndn-tlv/interest.html

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.

http://named-data.net/doc/ndn-tlv/data.htmll

Documents

Dados Nomeados em Redes Móveis Ad Hoc · neste tipo de redes, a topologia da rede e muito din^amica, devido a mobilidade dos n os, a entrada e sa da de n os na rede e as quebras