Redes
Avançadas
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Redes Ad Hoc
• Relembrando... O que são?
– “Ad Hoc” vem do latim “para este fim”
– Situações nas quais os problemas são resolvidos de uma
maneira improvisada
– Em redes:
• Dispositivos que podem criar uma rede sem uma infraestrutura prévia de comunicação
• Não há a idéia de um nó central, eliminando a necessidade
do roteador
• Ligações entre os nós são independentes
– Se uma ligação falhar, as outras continuam ativadas
Redes Avançadas – Prof. Mateus Raeder
Redes Ad Hoc
• Vantagens
– Flexibilidade
– Conveniência
• Desvantagens
– Aumento da complexidade, principalmente de
roteamento de informações
Redes Avançadas – Prof. Mateus Raeder
Roteamento
• O que fazem os algoritmos de roteamento?
• Procuram estabelecer uma rota entre dois hosts de uma
rede
• Para entrega de pacotes
• Mapeiam a topologia da rede
• Em redes cabeadas, existem dois principais tipos de
algoritmos de roteamento
• Link-state
• Distance vector
Redes Avançadas – Prof. Mateus Raeder
Roteamento
• Em MANETs (Mobile Ad hoc Networks)
– Grande grau de mobilidade dos seus componentes
– O caminho entre dois participantes da rede pode ser
alterado
• Protocolos de redes cabeadas mostraram-se
ineficientes para este tipo dinâmico de rede
• Para suprir os problemas dos protocolos de
roteamento para redes cabeadas, surgiram os
protocolos de roteamento para redes ad hoc
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Qualidades desejáveis nos protocolos de roteamento
– Livre de loops: evitar rotas circulares que não atingem o destino;
– Operações baseadas em demanda de trafego: deve ter a
capacidade de se adaptar a diferentes condições de tráfego;
– Segurança: o protocolo de roteamento deve poder evitar as
mais variadas formas de ataque;
– Períodos de sonolência: capacidade de adaptar-se a períodos
de inatividade dos hosts móveis (avisados com antecedência ou
não);
– Suporte a links unidirecionais: tipicamente algoritmos de
roteamento para redes ad hoc assumem links bidirecionais,
sendo que muitas propostas não funcionam sobre links
unidirecionais;
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Taxonomia
– Modelo de Comunicação:
• Canais Múltiplos: muitos mecanismos de multiplexação;
• Canais Simples: um único mecanismo de multiplexação;
– Estrutura
• Uniformes: todos os terminais possuem o mesmo papel;
• Não-Uniformes (hierárquicos): terminal com papel especial;
– Estado da Informação
• Baseado em Topologia: utiliza o estado do enlace (link-state);
• Baseado em destino: utiliza a distância até o destino (distancevector);
– Escalonamento
• Pró-ativos (table-based)
• Reativos (on-demand)
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Duas classificações que veremos
– Protocolos de Roteamento Pró-ativos
– Protocolos de Roteamento Reativos
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Protocolos de Roteamento Pró-Ativos
– Cada host (nodo) mantém informações de roteamento
para todos os outros nodos da rede
– Utilizando diversas tabelas para controle
– Estas tabelas são atualizadas de acordo com as
mudanças da rede
– As diferenças entre os protocolos são basicamente
• Como a informação é atualizada e detectada
• Como lidam com as tabelas de roteamento
• Quantidade de tabelas de roteamento
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Protocolos de Roteamento Pró-Ativos
– Neste tipo de protocolo, busca-se que sempre haja uma
rota entre todos os hosts
– Assim sendo, as rotas são continuamente atualizadas
– As informações de mudanças são propagadas por toda a
rede para manter a consistência
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Vantagem dos algoritmos pró-ativos:
– Disponibilidade imediata de uma rota para entrega dos
pacotes de comunicação
– Redução no atraso na transmissão inicial dos pacotes de
comunicação
• Desvantagens:
– Mobilidade provoca intervalos consideráveis de perda de
conectividade, dispara descoberta de novas rotas
– Carga elevada de mensagens de roteamento entre os
nodos comunicantes
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
Protocolos de roteamento pró-ativos
Ano
Distributed Bellman-Ford (DBF)
1987
Highly Dynamic Destination-Sequenced Distance Vector (DSDV)
1994
Wireless Routing Protocol (WRP)
1996
Clusterhead Gateway Switch Routing (CGSR)
1997
Hierarchical State Routing (HSR)
1999
Mobile Mesh Routing Protocol (MMRP)
2000
Intrazone Routing Protocol (OLSR)
2002
Optimized Link State Routing Protocol (OLSR)
2003
Topology Dissemination based on Reverse-Path Forwarding (TBRPF)
2004
Guesswork
2005
“Direction” Forward Routing (DFR)
2006
BABEL
2008
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Protocolos de Roteamento Reativos
– Não armazena informação sobre rota até o destino
– Somente quando realmente quer transmitir dados faz a
descoberta da rota
– Tenta reduzir o overhead dos protocolos pró-ativos
– Assim, a rota é determinada e mantida pelos hosts que
querem enviar dados para outro
– Descoberta de rota geralmente através de flooding na
rede
– Quando um host no caminho é encontrado, responde
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Protocolos de Roteamento Reativos
– Podem ser classificados em dois tipos:
• Source routing
• Hop-by-hop
• Source routing
– Cada pacote carrega toda a informação do roteamento
– Os nodos intermediários encaminham os pacotes de
acordo com o que está no pacote
– Nodos intermediários não precisam guardar informações
atualizadas para cada rota para enviar ao destino
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Source routing: funcionamento básico
– Cada terminal de origem (TO) possui uma tabela de rotas para os
terminais de destino (TD)
– Quando o TO vai transmitir verifica sua tabela de rotas
• TD está na tabela: emite a mensagem para o TD (com a rota para
alcançar o TD no cabeçalho)
• TD não está na tabela: deve iniciar fase de descoberta de rota
– Quando terminal recebe um pacote ele verifica se ele é o TD:
• É o TD: envia a resposta de confirmação
• Não é TD: propaga o pacote para o próximo terminal de acordo com a
rota contida no cabeçalho da mensagem
– Se escutar o próximo terminal: assume envio correto
– Se não escutar o próximo terminal: mensagem de erro é respondida para o TO,
que começará uma fase de manutenção de rota
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Exemplo
TO
TD
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Protocolos de Roteamento Reativos
– Podem ser classificados em dois tipos:
• Source routing
• Hop-by-hop
• Hop-by-hop
– Também conhecida como point-to-point
– O pacote enviado carrega apenas o endereço de
destino e o next hop
– Os nodos intermediários usam suas tabelas de roteamento
para encaminhar os pacotes
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Hop-by-hop: funcionamento básico
– Cada TO possui uma tabela de rotas para os terminais destino
– Quando o TO quer transmitir, verifica a sua tabela de rotas
• TD está na tabela: emite o pacote para o próximo terminal
• TD não está na tabela: deve iniciar uma fase de descoberta de rota
– Quando um terminal recebe um pacote ele verifica se ele é o TD:
• É o TD: envia a resposta de confirmação
• Não é o TD: consulta a sua tabela de rotas
– TD está na tabela de rotas: encaminha o pacote para o próximo terminal (de
acordo com a sua tabela de roteamento)
– TD não está na tabela: pacote de erro é respondido para o TO, que começará
uma fase de manutenção de rota
Redes Avançadas – Prof. Mateus Raeder
Descoberta de Rota
1
4
2
3
5
6
Redes Avançadas – Prof. Mateus Raeder
Manutenção de Rota
• Monitoramento da rota por parte dos nós
• Ao repassar o pacote, nós aguardam por algum tipo de
reconhecimento por parte do próximo nó
• Se o terminal que está roteando o pacote não receber nenhum
reconhecimento vindo do próximo salto, envia um pacote de erro
de rota de volta para o TO
• Esse pacote contém (principalmente):
– O nó que detectou o erro
– O nó que não foi alcançado
• O TO deve atualizar sua tabela
– Todas as rotas que utilizam esse enlace devem ser apagadas
Redes Avançadas – Prof. Mateus Raeder
Manutenção de Rota
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Vantagens dos Protocolos Reativos
– Otimização da utilização da rede
– Rotas mais dinâmicas nas mudanças na rede
– Cada nodo terá a melhor rota (no momento) para o
destino
• Desvantagens
– Retardo inicial quando a rota precisa ser encontrada
– Os nodos intermediários devem armazenar e manter
informações sobre o roteamento para todas as rotas
ativas
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
Protocolos de roteamento reativos
Ano
Dynamic Source Routing (DSR)
1996
Ad Hoc On-demand Distance Vector (AODV)
1997
Routing On-Demand Acyclic Multi-path (ROAM)
1999
Light-weight Mobile Routing (LMR)
1995
Temporally Ordered Routing Algorithm (TORA)
1997
Associativity-Based Routing (ABR)
1996
Signal Stability Adaptive (SSA)
1996
Relative Distance Micro-discovery Ad Hoc Routing (RDMAR)
1999
Dynamic MANET On-demand (DYMO)
2006
Redes Avançadas – Prof. Mateus Raeder
Protocolos de Roteamento
• Ainda podem ocorrer situações híbridas
– Geralmente para redes maiores
– Grupos podem ser organizados (clusters)
– Diferentes algoritmos podem ser utilizados para o
roteamento dentro e entre os grupos
– Um nodo (geralmente chamado clusterhead) controlam
os dados que chegam e saem de cada grupo
Redes Avançadas – Prof. Mateus Raeder