Resumo Capítulo 4.5 Kurose

A função crítica da camada de rede é o roteamento

A tarefa do roteamento é determinar bons caminhos(ou rotas) entre remetentes e destinatários através da rede de roteadores.

Chama-se roteador default o roteador cujo hospedeiro é ligado diretamente. Também é chamado de roteador de primeiro salto. Denominamos roteador da fonte o roteador default do hospedeiro de origem e roteador de destino o roteador default do hospedeiro de destino.

A finalidade de um algorítimo de roteamento é descobrir um '‘bom’' caminho entre o roteador da fonte e o roteador de destino. Nem sempre um '‘bom’' caminho é aquele que tem o '‘menor custo’'. Às vezes, questões políticas entram em jogo para complicar algoritmos, cuja teoria fundamenta a prática de roteamento.

Um grafo é usado para formular problemas de roteamento. Um grafo G = (N,E) é um conjunto N de nós e uma coleção de E arestas, no qual cada aresta é um par de nós do conjunto N. No contexto do roteamento da camada de rede, os nós do grafo representam roteadores – os pontos nos quais são tomadas as decisões de repasse de pacotes – e as arestas que conectam esses nós representam os enlaces físicos entre esses roteadores.

O Custo de uma aresta pode refletir o tamanho físico do enlace correspondente, a velocidade do enlace, ou o custo monetário a ele associado. Denomina-se c(x,y) o custo da aresta entre os nós x e y. Se o par (x,y) não pertencer a E, estabelecemos c(x,y)=∞. Caminho de Menor Custo é o caminho entre a fonte e o destino que tenha menor custo.

Grafo não direcionados, são aqueles que a aresta (x,y) é a mesma que a aresta (y,x) e que c(x,y)=c(y,x). Diz-se também que y é um vizinho do nó x se (x,y) ϵ E.

Algorítimo de Roteamento Global(ARG) calcula o caminho de menor custo entre uma fonte e um destino. O algorítimo considera como dados de cálculo a conectividade entre todos os nós e todos os custos dos enlaces. O algorítimo então, de algum modo, busca informações, antes de realizar o cálculo. O cálculo pode ser rodado em um local centralizado ou duplicado em vários locais. Um ARG tem informação completa sobre conectividade e custo de enlaces. São também chamados de Algorítimos de Estado de Enlace(Link State-LS).

Algorítimo de Roteamento Descentralizado(ARD) o cálculo do caminho de menor custo é realizado de modo iterativo e distribuído. Nenhum nó tem informação completa sobre os custos de todos os enlaces da rede. Cada nó começa sabendo apenas os custos dos enlaces diretamente ligados a ele. Por meio de um processo iterativo de cálculo e de troca de informações com seus nós vizinhos, um nó gradualmente calcula o caminho de menor custo até um destino ou um conjunto de destinos. Ele pode ser chamado também de Algorítimo de Vetor de Distâncias(distance-vector algorithm – DV) porque cada nó mantém um vetor de estimativas de custos(distâncias) de um nó até todos os outros nós da rede.

Algorítimos de roteamento estáticos são aqueles em que as rotas mudam muito lentamente ao longo do tempo, muitas vezes como resultado de intervenção humana. Algorítimos de roteamento dinâmico mudam os caminhos de roteamento à medida que mudam as cargas de tráfego ou a topologia da rede. Podem ser rodados periodicamente ou como reação direta às mudanças de topologia ou de custo dos enlaces. São mais suscetíveis a problemas como loops de roteamento e oscilação em rotas.

Algorítimo sensível à carga, nele os custos de enlace variam dinamicamente para refletir o nível corrente de congestionamento no enlace subjacente. Se houver um alto custo associado com um enlace que está correntemente congestionado, um algorítimo de roteamento tenderá a escolher rotas que evitem esse enlace congestionado. Algorítimos insensíveis à carga são aqueles que o custo de um enlace não reflete explicitamente seu nível de congestionamento corrente(nem o de congestionamento mais recente). Exemplos destes são: RIP, OSPF e BGP.

ALGORÍTIMO DE ROTEAMENTO DE ESTADO DE ENLACE(LS)

A topologia da rede e todos os custos do enlace são conhecidos e cada nó transmite pacotes de estado de enlace a todos os outros nós da rede. Cada um desses pacotes contém as identidades e os custos dos enlaces ligados a ele. Isso é frequentemente conseguido com um algorítimo de transmissão broadcast de estado de enlace. O resultado da transmissão broadcast dos nós é que todos os nós têm uma visão idêntica e completa da rede. Cada nó pode, então, rodar o algorítmo de estado de enlace e calcular o mesmo conjunto de caminhos de menor custo como todos os outros nós.

Cada nó fala com todos os outros nós a rede (via broadcast), mas informa somente os custos dos enlaces diretamente ligados a ele.

Sempre que o custo de um enlace muda, o novo custo deve ser enviado a todos os nós.

Em caso de falha ou mau comportamento de um roteador, usando LS um roteador poderia transmitir um custo incorreto para um de seus enlaces diretos (mas não para os outros). Um nó poderia também corromper ou descartar quaisquer pacotes recebidos como parte de uma transmissão de estado de enlace. Mas um nós LS está calculado somente suas próprias tabelas de roteamento; os outros realizam cálculos semelhantes para si próprios. Isto significa que, sob o LS, os cálculos de rota são, de certa forma, isolados, fornecendo um maior grau de robustez.

ALGORÍTMO DE ROTEAMENTO DE VETOR DE DISTÂNCIAS(DV)

É distribuído, porque cada nó recebe alguma informação de um ou mais vizinhos diretamente ligados a ele e distribui os resultados de seus cálculos para seus vizinhos. É iterativo porque esse processo continua até que mais nenhuma informação seja trocada entre vizinhos. E é assíncrono porque não requer que todos os nós rodem simultaneamente.

No algorítmo distribuído, assíncrono, cada nó envia uma cópia do seu vetor de distâncias a cada um de seus vizinhos. Quando um nó x recebe um novo vetor de distâncias de qualquer de seus vizinhos v, ele armazena o vetor de distâncias de v e