Algoritmos de encaminhamento

No grafo seguinte, a ligação A–C custa 5, mas passar por B custa apenas 3; um algoritmo de encaminhamento precisa de descobrir esta alternativa e registar B como próximo salto. O custo é definido pelo problema e não representa necessariamente atraso ou capacidade.

Link state e Dijkstra

Num algoritmo link state, cada router divulga custos das suas ligações e constrói a topologia, calculando depois menores custos a partir de si. Cada router precisa de receber a descrição completa das ligações e custos, não apenas distâncias calculadas por outros: só com o grafo consegue correr Dijkstra localmente.

Dijkstra mantém distâncias provisórias e nós fixados. Começa com origem a zero e restantes a infinito. Escolhe o não fixado de menor distância, fixa-o e tenta melhorar vizinhos com atual + custo. Os custos devem ser não negativos.

Resolução a partir de A. Depois de fixar A, B tem 2 e C tem 5; fixa B, e C melhora para 3 enquanto D fica em 6; fixa C, e D melhora para 4; fixa D. Os predecessores dão A-B-C-D. Para chegar a D, o próximo salto a partir de A é B, não C nem D.

Passo	Fixado	Dist B	Dist C	Dist D
0	A	2	5	infinito
1	B	2	3	6
2	C	2	3	4
3	D	2	3	4

Em igualdade de custos pode haver vários caminhos mínimos. Usa o critério de desempate do enunciado, se existir. Uma resposta com custo correto pode ter um caminho diferente e igualmente válido.

Distance vector e Bellman-Ford

Em distance vector, o router troca distâncias com vizinhos sem conhecer o grafo completo, segundo:

$$D_x(y)=\min_v\{c(x,v)+D_v(y)\}.$$

$v$ percorre os vizinhos de $x$, cujos custos locais são conhecidos, e cada candidato soma custo até ao vizinho e a distância que esse vizinho anunciou para o destino. Guarda também o vizinho que produziu o mínimo.

Exemplo. X liga a A com custo 2 e a B com custo 5. Para Z, A anuncia 7 e B anuncia 1; via A custa 9 e via B custa 6, por isso X anuncia 6 e usa B.

Num traço por rondas síncronas, todos calculam com os vetores da ronda anterior. Atualizar imediatamente um router e usar esse resultado no seguinte modela uma execução diferente. Regista a inicialização: frequentemente distância zero a si, custos conhecidos aos vizinhos e infinito aos restantes.

Falhas, ciclos e count to infinity

Considera Z–A–B, com custo 1 por ligação e sem split horizon. Inicialmente A anuncia distância 1 a Z e B anuncia 2 via A; quando Z–A falha, A pode receber o anúncio antigo de B e escolher distância 3 via B. B recebe esse novo valor e passa a anunciar 4 via A, e as atualizações seguintes produzem 5, 6 e assim por diante, embora nenhum dos dois tenha caminho para Z.

Atualização recebida	Distância de A a Z	Distância de B a Z
Antes da falha	1, direta	2, via A
A usa anúncio antigo de B	3, via B	2, via A
B usa anúncio novo de A	3, via B	4, via A
A usa anúncio novo de B	5, via B	4, via A

Este traço é assíncrono: uma atualização já calculada pode ser usada na seguinte. A subida prossegue até ao infinito definido pelo protocolo. Num exercício com rondas síncronas, conserva os vetores anteriores durante toda a ronda.

Split horizon evita anunciar numa interface uma rota aprendida nessa interface. Poison reverse anuncia-a com distância infinita. Triggered updates divulgam alterações sem esperar pelo intervalo periódico. Estas técnicas ajudam, mas poison reverse não elimina todos os ciclos com três ou mais routers.

Porquê só dois? Numa falha entre vizinhos diretos, não anunciar de volta ao vizinho que ensinou a rota corta o ciclo de comprimento dois. Mas numa topologia em anel, a má notícia pode dar a volta pelo outro lado: um terceiro router, que ainda não soube da falha, anuncia a rota antiga a outro vizinho, e a contagem recomeça. O infinito do protocolo, 16 no RIP, limita a duração do ciclo, não o impede.

Encaminhar um pacote num ciclo não significa que o algoritmo tenha terminado: as tabelas podem estar num estado transitório. O TTL/Hop Limit limita a vida do pacote; não resolve a convergência das tabelas.

Protocolos e âmbito

Protocolo	Ideia	Âmbito habitual
RIP	Vetor de distâncias, custo em saltos	Interior de um sistema autónomo
OSPF	Estado de ligações e caminhos mínimos	Interior de um sistema autónomo, com áreas
BGP	Vetor de caminhos e políticas	Entre sistemas autónomos e distribuição interna dessas rotas

No RIP, 16 representa infinito e limita a dimensão dos caminhos. OSPF divulga estado das ligações e calcula rotas sobre a base de dados. BGP inclui o percurso de sistemas autónomos e aplica políticas; «menor número de routers» não explica a sua seleção.

Um sistema autónomo reúne redes sob uma administração e política de encaminhamento. Há rotas estáticas, introduzidas por configuração, e dinâmicas, aprendidas por protocolo. Uma rota por omissão pode evitar conhecer individualmente todos os destinos externos.

Custo e débito não são a mesma conta

Supondo custo $1/R$, duas ligações de 4 Mbit/s custam $1/4+1/4=0{,}5$, enquanto um direto de 3 Mbit/s custa $1/3\approx0{,}333$ e por isso é escolhido, embora o primeiro tenha bottleneck de 4 Mbit/s. Minimizar a soma dos inversos não equivale a maximizar o menor débito.

Para um exercício, entrega a tabela por iteração, o custo final, o caminho e o próximo salto. Se pedirem o débito, faz depois a conta independente sobre as capacidades do caminho escolhido.