Dynamic Source Routing
Instituto Superior Técnico
Segurança em Redes Móveis
Elaborado por:
Luís Ricardo Fonseca
18 de Janeiro de 2010
Indice
A. Protocolos de rotas
B. Reactivos vs Proactivos
C. DSR
C.1. Detalhe
C.2. Mecanismos
C.3. Características
C.4. Optimizações
C.5. Ataques
D. Bibliografia
Dynamic Source Routing
2 / 17
A. Protocolos de rotas
Um protocolo de rotas (routing protocol) especifica como um
conjunto (rede) de sensores comunicam entre si. Recorrendo a
algoritmos que permitem seleccionar rotas entre dois nós.
Os protocolos podem ser classificados consoante o modo como
efectuam a selecção das rotas em:
Reactivos ou On-demand;
Proactivos.
Dynamic Source Routing
3 / 17
B. Reactivos vs Proactivos
Reactivos ou On-demand: rotas entre nós são determinadas
apenas quando surge a necessidade de enviar pacotes de dados.
Os protocolos reactivos funcionam por inundação da rede com
mensagens de route request.
Proactivos: rotas entre nós são determinadas antes de surgir a
necessidade de enviar pacotes de dados. Normalmente, é feita a
actualização periódica das rotas entre nós, bem como, sempre
que há alterações na topologia de rede.
Dynamic Source Routing
4 / 17
B. Reactivos vs Proactivos
Topologia
Reactivos
Proactivos
Vantagens
Desvantagens
Utilização dos recursos (largura
de banda, memória, energia, etc.)
Possível atraso no início da
apenas quando necessário,
transmissão, pela necessidade de
determinando as rotas apenas na
determinar a rota.
altura de transmissão de informação.
Minimizam o atraso inicial no
envio de mensagens porque
determinam as rotas previamente.
Dynamic Source Routing
Consumo elevado de recursos,
devido à actividade de actualização
periódica de rotas, especialmente
quando ocorrem alterações
frequentes de topologia.
5 / 17
C.1. DSR – Detalhe (Descrição)
O DSR (Dynamic Source Routing) é um protocolo de rotas reactivo
desenhado para gestão de MANETs (Mobile Ad-hoc NETworks) sendo a
rota estabelecida a partir do nó inicializador (Source Routing), com o envio
de mensagem de route request.
Os padrões do protocolo são descritos no RFC 4728.
São gerados 3 tipos distintos de mensagens:
Route Request;
Route Reply;
Route Error.
Em termos de requisitos de memória, cada nó armazena em cache as
rotas determinadas a partir dele próprio, a lista de pares (nó inicializador,
request id) dos route requests que recebe, e a sequência de request ids
gerados.
Dynamic Source Routing
6 / 17
C.1. DSR – Detalhe (Definições)
Route Request: mensagem enviada pelo nó inicializador para todos os nós vizinhos que
por sua vez procedem ao seu reencaminhamento até chegar ao nó de destino. Tem o
seguinte formato: <Nó Inicializador, Nó Destino, Request ID, Route Record> constituído
pelos nós de origem e destino, um request id (identificador único) definido pelo inicializador
de acordo com uma sequência, e a sequência de todos os nós que a mensagem de Route
Request percorreu até ao momento (Route Record).
Route Reply: mensagem enviada pelo nó destino para o nó inicializador. Tem o seguinte
formato: <Nó Destino, Nó Inicializador, Request ID, Route Record>.
Route Error: mensagem enviada pelo nó que identificou a falha na rota, com informação da
ligação que falhou, com o seguinte formato: <Nó que identificou a falha na rota, Nó que
não confirmou o reconhecimento>.
Route Source: sequência de nós (rota) desde o nó inicializador até ao nó destino.
Route Cache (de um nó): armazena todas as Route Sources desse nó que foram
determinadas até ao momento. Cada elemento (Route Source) da Route Cache tem
associado um período de validade, ao fim do qual é eliminado da Route Cache.
Dynamic Source Routing
7 / 17
C.2. DSR – Mecanismos
O DSR é composto por 2 mecanismos “Route Discovery" e "Route Maintenance", que
funcionam em conjunto para descobrir e manter rotas em redes. Estes 2 mecanismos são
desencadeados “on-demand”, de forma reactiva, quando é necessário determinar uma rota
ou surgem alterações a uma determinada rota.
Route Discovery: mecanismo que permite a um nó I (inicializador), que pretende enviar
uma mensagem para um nó D (destino), obter uma rota de I para D.
Route Maintenance: detecta se a topologia da rede sofreu alterações e permite ao nó
inicializador decidir se deverá ser utilizada uma rota alternativa ou se deverá ser executado
o Route Discovery para encontrar uma nova rota.
O DSR utiliza "soft states“, isto é, as rotas são determinadas de acordo com as
necessidades, permitindo que o protocolo seja robusto face a problemas como falha de
nós. Por exemplo, um nó que falhe e reinicie pode juntar-se de novo à rede, após reiniciar,
sem qualquer interferência na execução do protocolo.
Dynamic Source Routing
8 / 17
C.2. DSR – Mecanismos (Route Discovery)
Route Discovery (de I para D)
Cada nó mantém uma lista de pares (nó inicializador, request id), permitindo detectar a
recepção de requests duplicados. Se o nó I (inicializador) tem na Route Cache uma rota
para o nó D (destino), então utiliza essa rota, caso contrário é executado o algoritmo:
1.O nó I envia uma mensagem de Route Request para os nós vizinhos, inundando a rede.
2.Executa-se o seguinte ciclo até encontrar o nó destino D. Para cada nó N que recebe o Route Request:
1.
Se o par (nó inicializador, request id) para esta requisição já estiver na lista de pares do nó N,
então o nó N ignora a mensagem e não faz nada. (Assim, o nó N não processará o mesmo
Route Request mais do que uma vez).
2.
Caso não se verifique 1, se o nó N já estiver no Route Record, então o nó N ignora o Route
Request. (Garantia de não ocorrência de loops).
3.
Caso não se verifique 1 e 2, se o nó N for o nó destino, ou N tiver em cache uma rota para o
nó destino (que não inclui nenhum nó do Route Record, para evitar loops), então devolve um
Route Reply para o nó I, contendo todo o caminho (Route Record). Para tal, ele verifica se tem
alguma rota em cache para o nó I. Se tiver, utiliza-a, caso contrário, utiliza a mesma rota no
sentido inverso. O nó I recebe o Route Reply, guardando o caminho na Route Cache de modo
a utilizá-lo no envio de pacotes de dados para D.
4.
Caso não se verifique 1, 2 e 3, N faz o forward do Route Request para todos os nós vizinhos
(com excepção do nó que o precedeu).
Dynamic Source Routing
9 / 17
C.2. DSR – Mecanismos (Route Discovery)
Route Request:
O nó 1 envia o Route Request, com a identificação do nó de início (1) e de destino (5) ao seu nó vizinho
(2). O nó 2 reencaminha para os nós 3 e 4. Como o nó 3 tem em cache um caminho para o nó destino,
não reencaminha o Route Request. O nó 4 reencaminha o Route Request para o 5, que é o nó destino.
Route Reply:
O nó 5 envia um Route Reply para o nó 1 (inicializador) com a rota determinada;
O nó 3 envia um Route Reply para o nó 1 com a concatenação da rota determinada de 1 para 3 e a rota
que tem em cache de 3 para o nó 5 (destino).
Dynamic Source Routing
10 / 17
C.2. DSR – Mecanismos (Route Maintenance)
Route Maintenace:
O procedimento de manutenção de rotas monitoriza todas as rotas a partir dos nós que
fazem parte da rede. Portanto, quando um nó envia uma mensagem, o mesmo é
responsável pela confirmação de que a mensagem foi recebida pelo nó seguinte.
1.Quando um nó não recebe a confirmação de recepção (de um pacote de dados) do nó
para o qual efectuou o envio, após tentar enviar um número máximo de vezes (definido),
envia uma mensagem de Route Error para o nó inicializador.
2.O nó inicializador recebe a mensagem de Route Error e remove da route cache as Route
Sources que contêm a ligação que falhou.
1. Se o nó inicializador tiver uma Route Source alternativa na Route Cache, então
utiliza-a;
2. Caso não se verifique 1 então o nó inicializador inicia a fase de Route Discovery,
para encontrar caminhos de I para D, enviando uma mensagem de Route Request
a todos os nós vizinhos.
Dynamic Source Routing
11 / 17
C.2. DSR – Mecanismos (Route Maintenance)
Route Error:
O nó C após um determinado número de tentativas falhadas de envio de um pacote de
dados para D, envia uma mensagem de Route Error para o nó inicializador A, indicando
que houve uma falha na ligação C->D.
Dynamic Source Routing
12 / 17
C.3. DSR – Características
Rotas múltiplas para qualquer nó destino, sendo o nó inicializador a escolher as rotas
a utilizar. Permite assim uma reacção rápida a alterações de rota, podendo utilizar rotas
alternativas em cache, bem como o balanceamento de cargas (load balancing);
Inexistência de loops garantida;
Aplicável em redes com ligações unidireccionais (adaptável);
Utilização de soft states;
Menor consumo de recursos, uma vez que não é necessário proceder à actualização
periódica de tabelas de rotas;
Menor consumo de recursos, pela utilização de informação de rotas em cache:
pelos nós intermédios, permite reduzir o número de níveis a incluir na pesquisa;
pelo nó inicializador, que só tenta encontrar um caminho para um nó destino, se não
tiver em cache nenhuma rota para o mesmo;
Menor consumo de largura de banda porque não são utilizadas “hello messages”;
O procedimento de manutenção (Route Maintenance) não permite reparar uma
ligação que tenha falhado entre 2 nós. Apenas é feita a comunicação da ocorrência ao nó
inicializador, que posteriormente toma uma decisão sobre a solução a adoptar.
Dynamic Source Routing
13 / 17
C.4. DSR – Optimizações
 Aproveitamento da Cache:
 Cada nó (no percurso do Route Request) guarda em cache o Route Record da
mensagem encaminhada, permitindo posteriormente utilizar essa rota (entre nó
inicializador e ele mesmo);
 Limitar o número de níveis percorridos pelo Route Request a partir da origem (que
poderá ser incrementado sucessivamente caso não seja obtida resposta após um
determinado período de tempo), permitindo evitar difusão de mensagens por toda
a rede, para além dos nós estritamente necessários.
 Escolha do melhor caminho:
 Quando o nó de destino não tem uma rota em cache para o nó inicializador,
executa o processo de Route Discovery para o nó inicializador, adicionando a nova
rota à rota recebida na mensagem de Route Request (permitindo, em alguns
casos, obter uma rota melhor do que a determinada anteriormente, e que poderá
ser guardada e utilizada pelo nó inicializador).
Dynamic Source Routing
14 / 17
C.5. DSR – Ataques
O DSR funciona com um modelo de confiança “cega” nos vizinhos. Adicionalmente, não
existe autenticação entre as partes que comunicam, nem encriptação das mensagens
trocadas, não sendo garantida a confidencialidade e integridade da informação trocada,
estando por isso o protocolo vulnerável a vários ataques:
Topologia
Externos
Nós
-
Nós que
falham
Meio
-
Ataque
Nós sem autorização e não confiáveis.
Utilizar
mecanismos
autenticação.
Ataques de Physical layer (Jamming e
Tampering).
Detectar zona de jamming e
contorná-la; esconder sensores.
Vírus.
Utilizar antí-virus.
Route Discovery
Falha no envio de Route Requests
e/ou Route Replys.
Route Maintenance
Falha no envio de Route Errors.
-
Falha no envio de pacotes de dados.
-
Mesmo comportamento que nós que
falham (não enviam mensagens).
Internos
Nós egoístas Mantêm as rotas
para si mesmos
(motivo: poupança
de energia)
Solução
Ignoram Route Requests e/ou Route
Replys e/ou Route Errors.
Utilizar rota alternativa.
Utilizar rota alternativa.
Ignoram pacotes de dados.
Dynamic Source Routing
15 / 17
de
C.5. DSR – Ataques
Continuação…
Topologia
Nós
Meio
Ataque
Solução
Route Requests errados:
» Criação e envio de Route Requests
para esgotamento de recursos;
» Não enviar Route Requests, para
impedir determinação de rotas.
Internos
Nós
maliciosos
Ameaça à
integridade da rede
Route Replys errados:
» Envio de Route Replys errados (rotas
erradas);
» Circular informação de Route Records
por nós maliciosos;
» Não enviar Route Replys, para impedir
determinação de rotas.
Utilizar mecanismos de
autenticação e de encriptação de
mensagens.
Route Errors errados:
» Envio de Route Errors errados para
inviabilizar rotas;
» Não enviar Route Errors, para impedir
determinação de rotas alternativas.
Dynamic Source Routing
16 / 17
D. Bibliografia
DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks, David B.
Johnson David A. Maltz Josh Broch. Computer Science Department, Carnegie Mellon University
Pittsburgh, PA 15213-3891.
Arithmetic Encoding Based Dynamic Source Routing for Ad-Hoc Networks. Ajay Koul, R.B. Patel and
V.K. Bhat. Journal of Computer Science 4 (5): 353-359, 2008, ISSN 1549-3636.
Efficient, Secure, Dynamic Source Routing for Ad-hoc Networks. Michael Weeks1,2 and Gulsah Altun1,
Journal of Network and Systems Management, Vol. 14, No. 4, December 2006 (c 2006) DOI:
10.1007/s10922-006-9043-8.
Nodes Bearing Grudges:Towards Routing Security, Fairness, and Robustness in Mobile Ad Hoc
Networks. Sonja Buchegger. IBM Zurich Research Laboratory, Jean-Yves Le Boudec EPFL-DSC CH1015 Lausanne, Switzerland.
Analysis of the Dynamic Source Routing Protocol for Ad Hoc Networks. Rajendra V. Boppana Anket
Mathur CS Department, UT San Antonio, San Antonio, TX 78249. USA.
Lecture notes Wireless Sensor Networks security da cadeira: http://comp.ist.utl.pt/pdis-srm/.
RFC 4728: http://tools.ietf.org/html/rfc4728.
Dynamic Source Routing
17 / 17