Algoritmos de encaminhamento

Dijkstra

• Link state divulga custos; cada router monta o grafo e corre Dijkstra. Exige custos não negativos.
• Fixa o não fixado de menor distância, relaxa vizinhos, repete. Próximo salto é o primeiro nó após a origem.

• De A: B=2, C=3 via B, D=4 via C. Próximo salto para D é B; predecessor de D é C.
• Empates podem dar vários mínimos; segue o desempate dado.

Distance vector

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

• Guarda o vizinho do mínimo como próximo salto. Rondas síncronas usam os vetores da ronda anterior.
• Falha Z–A em cadeia Z–A–B: A aceita o anúncio antigo de B e a distância sobe 3, 4, 5 sem caminho real.
• Split horizon corta ciclos de dois; anel de três ou mais pode dar a volta pela má notícia antiga. Infinito do RIP é 16.
• Poison reverse anuncia infinito ao vizinho de quem aprendeu a rota; triggered updates apressam a má notícia.

Protocolos

	Ideia	Âmbito
RIP	Vetor, custo em saltos, 16 é infinito	Interior, pequeno
OSPF	Estado de ligações, áreas	Interior
BGP	Vetor de caminhos com políticas	Entre sistemas autónomos

• Minimizar soma de custos não maximiza débito: custo $1/R$ escolhe o direto de 3 Mbit/s contra dois de 4.