Encaminhamento “Vector de Caminhos”
Prof V Vargas, IST
03/11/11, Pg 1/2
Encaminhamento “Vector de Caminhos”
{PathVector.doc}
1. [07E1] Considere a rede da figura Routing22.a em que os números junto das ligações representam o seu
comprimento. O protocolo de encaminhamento usado é por vector
de caminhos (Path Vector). Todos os nós encaminhadores arrancam
no instante t=0 e a troca de mensagens de encaminhamento procede
de forma síncrona nos instantes t=1, 2, 3,..... Admita que, quando os
encaminhadores são ligados em t=0, estes já têm conhecimento da
identidade dos seus vizinhos e dos respectivos custos directos.
1. 1. Apresente a evolução dos vectores de caminhos anunciados
pelo nó F, desde t=0 até à estabilização do algoritmo.
1. 2. Explique como, neste protocolo, é resolvido o problema da
contagem para infinito (que é um problema comum, por
exemplo, nos algoritmos do tipo vector de distâncias).
R1:
A
B
C
D
E
Vector enviado em t=1:
FD/2
FE/1
∞
∞
∞
Vector enviado em t=2:
FDB/4
FEC/2
FD/2
FE/1
∞
Vector enviado em t=3:
FECA/3
FDB/4
FEC/2
FD/2
FE/1
(A coluna D é irrelevante em vectores enviados a D; a coluna E é irrelevante em vectores enviados a E)
R2: Admita-se, por ex., que a linha DF quebra; D passaria a divulgar a seguinte rota para F: DEF. E admitase que, depois disso, EF também quebra. Este cenário, com o algoritmo vector-de-distâncias, conduziria a
contagem para infinito: o nó E não perceberia que já não há maneira de alcançar F. Com o protocolo vector-decaminhos, isso fica resolvido: E recebe de C e D os caminhos CEF e DEF - e descarta-se deles, pois repara que
ele, E, está incluído nesses caminhos; após o que divulga, como rota para chegar a F, ∞ - que vai ser utilizado por
C e D para também actualizairem os vector-de-caminhos que estão divulgando aos demais nós.
2. [08E2.13] Considere a rede da figura Routing27.d, em que os números junto das ligações representam o seu
comprimento. Todos os nós encaminhadores
arrancam no instante t=0 e a troca de mensagens
de encaminhamento procede de forma síncrona
nos instantes t=1, 2, 3,..... Admita que, quando os
encaminhadores são ligados em t=0, estes já têm
conhecimento da identidade dos seus vizinhos e
dos respectivos custos directos.
2. 1. Suponha que o protocolo de encaminhamento usado é por vector de distâncias (Distance Vector) com a
variante poisoned reverse. Qual a tabela de
distâncias final presente em B, após a
estabilização do algoritmo?
2. 2. Suponha agora que o protocolo de
encaminhamento usado é por vector de
caminhos (Path Vector). Quais os primeiros 3
vectores de caminhos anunciados por F?
R1: A tabela é a seguinte, obtém-se das Árvores
de escoamento, cfr figs Routing27.a, Routing27.b e
Routing27.c
Para:
A
C
D
E
F
De B
Via A
via C
1
4
3
2
∞
∞
5
4
5
∞
via D
∞
∞
1
4
3
R2:Path vectors enviados por F a ambos os vizinhos, D e E
Encaminhamento “Vector de Caminhos”
Prof V Vargas, IST
v1
v2
v3
03/11/11, Pg 2/2
D:2/FD; E:1/FE
B:3/FDB; C:3/FEC; D:2/FD; E:1/FE
A:4/FDBA; B:3/FDB; C:3/FEC; D:2/FD; E:1/FE
BGP
3. [09E2.6] Uma das características do protocolo BGP (Border Gateway Protocol) é o facto de não exibir o
designado problema da contagem para infinito. Explique, de forma clara, quais os procedimentos deste
protocolo que evitam que este problema se manifeste.
R: BGP usa um protocolo de “vectores de caminhos” (Path Vectors): Sejam F1 e F2 nós fronteira de dois
Sistemas Autónomos: AS1 e AS2. F1 envia a F2 o caminho que conhece de AS1 para uma rede Z; esse caminho
será uma lista de AS’s: AS1, ASi , ASj , ASk ,…, Z. F2 pode descartá-lo se reparar que nele já se encontra o AS2: se
o aceitasse, iria dar azo a um caminho fechado (loop) – e a uma distância a Z ilimitadamente crescente…