33
Roteamento 6 Roteamento Baseado em Fluxo (Flow-Based Routing)

Roteament

Embed Size (px)

Citation preview

Page 1: Roteament

Roteamento 6

Roteamento Baseado em Fluxo(Flow-Based Routing)

Page 2: Roteament

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.

Page 3: Roteament

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.

Page 4: Roteament

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.

Page 5: Roteament

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;

Page 6: Roteament

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.

Page 7: Roteament

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)

Page 8: Roteament

Exemplo

Page 9: Roteament

Exemplo

Page 10: Roteament

Exemplo

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

Page 11: Roteament
Page 12: Roteament
Page 13: Roteament
Page 14: Roteament
Page 15: Roteament
Page 16: Roteament

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

Page 17: Roteament

Exercício

Page 18: Roteament

Roteamento 7

Algoritmo de FloodingInundação

Page 19: Roteament

Características

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

Page 20: Roteament
Page 21: Roteament

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.

Page 22: Roteament

Roteamento

Roteamento por Estado de Enlace

Page 23: Roteament

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.

Page 24: Roteament

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.

Page 25: Roteament

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.

Page 26: Roteament
Page 27: Roteament

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.

Page 28: Roteament

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.

Page 29: Roteament

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

Page 30: Roteament

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

Page 31: Roteament

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.

Page 32: Roteament

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.

Page 33: Roteament

Exercício

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

X, L, F, e J