Redes Avançadas

Redes Avançadas

Prof. Mateus Raeder

Universidade do Vale do Rio dos Sinos- São Leopoldo -

Redes Avançadas – Prof. Mateus Raeder

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 infra-estrutura 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 Ad Hoc

• Vantagens– Flexibilidade– Conveniência

• Desvantagens– Aumento da complexidade, principalmente de

roteamento de informações


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


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


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;



• 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 (distance-vector);

– Escalonamento• Pró-ativos (table-based) • Reativos (on-demand)



• Duas classificações que veremos– Protocolos de Roteamento Pró-ativos– Protocolos de Roteamento Reativos



• 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



• 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



• 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



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



• 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



• 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



• 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



• Exemplo

TOTD



• 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



• 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


Descoberta de Rota1 2 3

4 5 6


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


Manutenção de Rota



• 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



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



• 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

Documents

Redes Avançadas