Para alcançar a “rede x”, colocamos os pacotes na interface y. Este mapeamento é dado na tabela de roteamento através de algoritmos de roteamento da camada de rede.

Objetivo: determinar melhor caminho pela rede. Usaremos uma abstração de grafos para tal, no qual cada vértice é um roteador e cada aresta representa os links físicos, com w = custo do enlace.

Tipos de Algoritmos de roteamento

Podem ser classificados quanto:

  1. ao tipo de info
  2. à mudança de rotas. todos os algs são insensíveis a carga.

Tipo de informação

Informação Global: todos os nós tem info completa da topologia, distância e custos dos outros nós, e.g, link state - LS. Informação descentralizada: roteador conhece os nós vizinhos e custos até eles, e.g distance vector - DV.

Mudança de rotas

Tipo Estático: rotas mudam raramente, usado em sistemas de borda ou que possuem poucos links de entrada e saída. Tipo Dinâmico: usados para sistemas de núcleo. Usam atualização periódica automática.

Link State:

usa Dijkstra e mantém info global.

Dijkstra: conferir notas de aula de grafos.

[!tip] Usaremos a tabela para a prova

Distance Vector:

É iterativo (continua até que os nós não troquem mais info e não há sinal de parada), assíncrono e distribuído. Usa Bellman-Ford e mantém info descentralizada, i.e Algoritmo RIP.

$$ d_{x}(y) = min_{v}{ c(x, v) + d_{v}(y) } $$ O menor custo de X até um vizinho V, mais o custo desse deste tal vizinho V até Y, considerando todos os “V” vizinhos de X.

Cada nó x mantém os seguintes dados de roteamento:

  1. O custo c(x,v) até cada vizinho v, diretamente conectado.
  2. O vetor de distâncias dele (nó x), contendo a estimativa dos custos de x até todos os destinos y em N.
  3. Os vetores de distâncias de seus N vizinhos, para cada vizinho v de x:

Vetor de Distâncias

É um conjunto contendo todas as estimativas de custos de x até todos os outros nós y pertencentes ao conjunto N de vizinhos diretamente conectados.

$$D_{x} = { D_{x}(y) : y \ \text{em} \ N }$$ Esse vetor é enviado aos outros nós toda vez que um valor mínimo é atualizado

[!todo]

  • O problema de “Boas notícias viajam depressa”
  • O problema de “Mas noticias chegam devagar” (exercício)
  • Poison Reverse -> solução para o problema das más notícias

Roteamento Hierárquico

Existem ilhas com autoridade própria. +50 milhões de IPV4 disponíveis, com +500K rotas

Sistemas Autônomos

Um AS (sistema autônomo) agrega roteadores em regiões e é uma estrutura administrativa que rodam o mesmo protocolo de roteamento.

É necessário ter mais de uma ligação com o backbone da internet, operar seu próprio range (intervalo) de IP’s e o próprio registro de AS.

Roteamento Intra-AS (IGP - Interior Gateway Protocols)

RIP OSPF IGRP

Roteamento Inter-AS

BGP -> Border Gateway Protocol