Roteamento 6

Roteamento Baseado em Fluxo(Flow-Based Routing)

Características

O algoritmo baseado em fluxo é um algoritmo estático que utiliza tanto a topologia quanto a carga para o roteamento

Algumas redes, o fluxo médio de dados entre cada par de nós é relativamente estável e previsível.

Características

Em condições em que o tráfego médio entre i e j é conhecido e é razoavelmente constante no tempo, é possível analisar o fluxo matematicamente para otimizar o roteamento.

Características

A idéia básica por trás desta análise é que para um dado enlace, se é conhecida a capacidade e o fluxo médio, é possível calcular o atraso médio por pacote pelo enlace.

A partir dos atrasos médios dos enlaces, assim obtidos, é relativamente simples o cálculo de um atraso médio, baseado em fluxo entre dois roteadores quaisquer da sub-rede.

Necessidades

1. Deve ser conhecida a topologia da sub-rede;

2. Deve ser conhecida a matriz de tráfegoFij;

3. Deve ser conhecida a matriz da capacidade dos enlaces Cij em bit/s;

4. Deve ser adotado um determinado algoritmo de roteamento;

Exemplos

Os pesos (kbit/s) dos diversos arcos na figura fornecem a matriz de capacidade, Cij,.

A matriz de tráfego, Fij, onde para cada par fonte/destino édado o caminho e o tráfego, medido em número de pacotes/seg.

Exemplo

n – tamanho médio dos pacotes que vamos assumir como 800 bits/pacoteC – capacidade do enlace em bit/s

ג – taxa de chegada ou fluxo médio de pacotes /segundo (tráfego total do enlace)

Exemplo

Exemplo

Exemplo

n - tamanho médio dos pacotes que vamos assumir como sendo: 800 bits/pacote.

A última coluna fornece os tempos para as métricas de atraso do algoritmo

Exercício

Roteamento 7

Algoritmo de FloodingInundação

Características

Cada pacote de entrada é enviado para toda linha de saída, exceto para aquela em que chegou.

Características

Gera diversos números de pacotes duplicados.Para controlar o número infinito de pacotes é ter um contador de hops contido no cabeçalho de cada pacote.

Iniciar com o comprimento do caminho da origem ao destino.Se não souber o tamanho do caminho, na pior das hipóteses com o diâmetro total da sub-rede.

Roteamento

Roteamento por Estado de Enlace

Características

O roteamento por vetor de distância, utilizada na Arpanet até 1979, foi substituído pelo Link State Routing por dois motivos principais:

Não levava em conta a largura de banda dos enlaces de saída do roteadorA convergência lenta da sub-rede quando acontece algum problema entre os roteadores.

Características

Este algoritmo está baseado em cinco blocos funcionais:

1. Descobrir seus vizinhos e apreender seus endereços de rede.

2. Medir o atraso ou custo para cada um de seus vizinhos.

3. Construir um datagrama no qual apresenta tudo o que acabou de apreender.

4. Mandar este datagrama a todos os outros roteadores.

5. Calcular o caminho mais curto a cada um dos outros roteadores.

Características

O objetivo é que cada roteador envolvido tenha um banco de dados completo de toda a topologia da rede, para conseguir traçar o caminho mais curto através de um algoritmo, como o de Dijkstra, por exemplo. Assim, para uma determinada topologia, cada roteador deve ter um banco de dados.Este banco de dados deve ser o mesmo em todos os roteadores, a fim de que todos tomem as mesmas decisões.

Como saber quem são os vizinhos

Para o roteador saber quem são seus vizinhos, pacotes Hello são enviados para as portas de tempos em tempos. Se um roteador recebe um pacote Hello ele responde com outro pacote contendo seu nome. Os nomes dos roteadores não podem ser duplicados. Os pacotes Hello também são utilizados para saber se um link está operacional.

Medir o atraso ou custo

A forma mais simples de medir o retardo éenviar pacotes de ECHO para o vizinho e esperar resposta. A média de vários tempos de resposta dividida por dois é uma estimativa do retardo. O tamanho da fila e a carga na rede também podem ser levados em consideração.

Enviar pacote a todos outros roteadores (Flooding)

Um pacote é mandado quando um roteador descobre um novo vizinho, o custo de um link muda, um link cai ou passa um determinado tempo. Como cada LSP deve ser enviado a todos os outros roteadores na rede, utiliza-se flooding (inundação), onde cada pacote recebido é mandado para todas as portas, exceto a porta em que veio.Para o flooding não se propagar ao infinito, gerando uma explosão de pacotes, pode ser usado um contador TTL com um limite de hops que é decrementado a cada roteador, e quando chega a zero, é descartado. O ideal é que o TTL seja inicializado com o comprimento do caminho da origem ao destino

Exemplo

Por exemplo, suponha que o link entre A e B tenha caído. A deve enviar essa mudança a todos os roteadores, e B deve fazer o mesmo. Supondo que o número de seqüência inicial tenha sido “1”, A vai enviar a seguinte informação para D (única porta ativa).

Exemplo

O roteador D vai enviar esta informação para todas as portas menos A, ou seja, para E, que vai enviar para B e F. B envia a informação para C (única porta que sobrou em B que não é a que o pacote chegou). F envia a informação para G e C (que recebe duas vezes a mesma informação, descartando uma). Dependendo por onde C recebe primeiro o pacote, ele envia para as outras portas. Supondo que ele receba primeiro via B, ele envia a informação para F e G. F também pode receber o pacote por portas diferentes, enviando para as outras portas da primeira vez e descartando quando receber duplicado. G envia a informação para a porta pela qual o pacote não chegou.

Calcular o caminho mais curto

Após as informações serem distribuídas por flooding, o algoritmo de Dijkstrapode ser usado para encontrar o caminho mais curto para cada um dos outros roteadores.

Exercício

Criar um diagrama para o caminho mais curto dos seguintes roteadores:

X, L, F, e J