Encaminhamento
Prof V Vargas, IST
03/11/11, Pg 1/4
Encaminhamento
{Routing.doc}
1. Diga o que entende por cada um dos tipos de algoritmo seguintes, dando um exemplo de cada um:
1. 1. encaminhamento isolado;
1. 2. encaminhamento distribuído;
1. 3. encaminhamento de rota mais curta;
1. 4. encaminhamento por inundação.
2. Indique uma vantagem e uma desvantagem de se utilizar como métrica do custo, num protocolo de
encaminhamento, a quantidade de tráfego transportado em cada linha.
R: A vantagem é escolher os caminhos com menos tráfego (mais baratos). A desvantagem é que pode causar
oscilações na escolha dos caminhos – os caminhos com menos tráfego passam a ser muito utilizados, ficando os
mais utilizados com menos tráfego, alternando-se sucessivamente.
3. Porque motivo existem diferentes protocolos para fazer o encaminhamento interno e externo?
Encaminhamento Hierárquico
4. [07E2.6] Considere três redes de comunicação autónomas, A, B e C e suponha que estas redes comportam,
respectivamente, 4, 2 e 5 nós de comutação cada uma. Um dos nós de B encontra-se ligado à rede A, e o outro
nó encontra-se ligado à rede C. Suponha que não existem quaisquer outras ligações entre aquelas três redes.
Determine o número total de entradas nas tabelas de encaminhamento do conjunto de todos os nós e compare-o
com o número que obteria se todos os nós fizessem parte de uma única
rede.
R: 4*(3+2)+2*(1+2)+5*(4+2)=56 versus 11*(11-1)=110
Nota: Cada nó de A tem, no total, 5=3+2 entradas, cfr fig Routing23.a:
- 3 entradas, indicando por onde enviar pacotes aos outros 3 nós de A
- 2 entradas, indicando por onde enviar pacotes às outras 2 Redes.
O conjunto dos nós de A precisa ter, no total, 4 * 5 entradas. Etc….
Algoritmos de cálculo da Rota Mínima (Dijkstra, etc.)
5.  Considere a rede da figura routing02.a, na qual os números junto das
ligações indicam os seus comprimentos. Usando o algoritmo de Dijkstra,
determine a distância do nó F a todos os outros nós da rede. Construa uma
tabela que ilustre a evolução do algoritmo.
Resolução:
A tabela requerida encontra-se adiante. À sua esquerda, escrevem-se as
identificações de todos os nós da Rede (excepto F).
Na primeira linha, escrevem-se os comprimentos das ligações
(abreviadamente, distâncias) desses nós a F; por ex., a distância de F a G é 6…
Situações em que, como sucede com o nó A, não existe uma ligação directa a F são representadas por "∞".
Repare-se na linha: o menor valor, 1, ocorre na coluna "E". Pelo que: a distância de E a F (ou vice-versa) é 1.
A
∞
∞
∞
7/EDC
7/EDC
6/EDCB ⇐
-
B
∞
∞
11/ED
5/EDC
5/EDC ⇐
.-
C
∞
4/E
3/ED ⇐
-
D
3
2/E ⇐
-
E
1⇐
-
G
6
6
3/ED
3/ED ⇐
-
H
∞
∞
∞
∞
17/EDG
7/EDCB
7/EDCB ⇐
A linha seguinte é uma actualização da primeira linha; aliás, qualquer subsequente linha volve-se na
actualização da linha que a precede - por aplicação do algoritmo de Dijkstra.
Prof V Vargas, IST
Encaminhamento
03/11/11, Pg 2/4
A aplicação desse algoritmo à construção da segunda linha é o seguinte:
O nó que acabou de ser seleccionado é o nó E. Não contando com o nó F, ele comporta dois vizinhos, C e D. A
rota de C (até F) passando por esse nó E vem a ser: C→E + E→F - com um comprimento total de 4 (=3+1);
repare-se: este é um valor inferior àquele que a linha "C" apresenta na primeira linha (e que é ∞); pelo que, ao
construir-se a segunda linha, se substitui esse "∞" por "4/E" - em que o rótulo "E" regista: o "4" logra-se por recurso
ao nó de trânsito "E" . Analogamente, a rota de D (até F) passando por E vem a ser: D→E + E→F - com um
comprimento total de 2 (=1+1); repare-se: este é um valor inferior àquele que a coluna "D" apresenta (e que é 3);
pelo que se substitui esse "3" por "2/E". Repare-se: o menor valor, 2, ocorre na coluna "D". Pelo que: a distância de
D a F (ou vice-versa) é 2.
A construção da terceira linha procede de um modo análogo:
O nó que acabou de ser seleccionado é o nó D. Não contando com F e E - pois que é já sabida a distância
deste a F -, ele comporta três vizinhos, B, C e G. A rota de B (até F) passando por esse nó D vem a ser:
B→D→E→F - com um comprimento total de 11 (=9+2); repare-se: este é um valor inferior àquele que a linha "B"
apresenta (e que é ∞); pelo que se substitui esse "∞" por "11/ED". Analogamente, a rota de C (até F) passando por
esse nó D vem a ser: C→D→E→F - com um comprimento total de 3 (=1+2); repare-se: este é um valor inferior
àquele que a linha "C" apresenta (e que é 4); pelo que se substitui esse "4" por "3/ED". Analogamente, a rota de G
(até F) passando por esse nó D vem a ser: G→D→E→F - com um comprimento
total de 3 (=1+2); repare-se: este é um valor inferior àquele que a linha "G"
apresenta (e que é 6); pelo que se substitui esse "6" por "3/ED". Repare-se: o
menor valor, 3, ocorre na coluna "C". Pelo que: a distância de C a F (ou viceversa) é 3 (Na coluna "G", também ocorre esse valor, 3. É indiferente neste
momento seleccionar o nó C ou o nó G).
A construção das restantes linhas procede de um modo análogo. Repare-se:
o objectivo de uma iteração é estabelecer a rota (até F) de um nó ainda não
"contemplado"; por cada iteração, selecciona-se mais um nó - e apenas um!
Havendo um total de sete rotas a determinar - tantas quantas as colunas da
tabela - então o número total de linhas há-de ser exactamente 7.
Em routing02.c, apresenta-se a árvore de escoamento do nó F - construída à
medida que se completavam as várias iterações acima: a rota para E é directa; para D, faz-se através de E; para
C e G, faz-se através de ED; para B, faz-se através de EDC; para A e H, faz-se através de EDCB.
A tabela de encaminhamento do nó F será então:
Nó
Interface de saída de F
Distância mais curta de F
de destino
para atingir esse nó
a esse nó
e
6
A
e
5
B
C
e
3
e
2
D
e
1
E
e
3
G
e
7
H
6. [04E1] Considere a rede ponto a ponto indicada, formada por ligações full-duplex:
CE, CF, CL, CV, ES, EV, FL, FS, LS, LV, SV
Admita que o algoritmo de encaminhamento selecciona as rotas que minimizam o número de saltos (hops) até
cada destinatário.
6. 1. Determine o mínimo número de saltos de um nó para todos os outros;
R: C: (E,F,L,V:1; S:2); E: (C,S,V:1; F,L:2); F: (C,L,S:1; V,E:2); L: (C,F,S,V:1; E:2);
S: (E,F,L,V:1; C:2); V: (C,E,L,S:1; F:2)
6. 2. Indique as rotas que as mensagens devem seguir.
R: C: (CE, CF, CL, CV, CES); E: (EC, ES, EV, ECF, ECL); F: (FC, FL, FS, FCE, FCV);
L: (LC, LF, LS, LV, LCE); S: (SE, SF, SL, SV, SEC); V: (VC, VE, VL, VS, VCF)
Resolução (compactada) para o nó E:
C
F
L
S
V
1⇐
∞
∞
1⇐
1⇐
2/C ⇐
2/C ⇐
1
2
2
1
1
Saltos
Rota
E→C
E→C→F
E→C→L
E→S
E→V
Encaminhamento
Prof V Vargas, IST
03/11/11, Pg 3/4
7. Considere a rede de que se indicam os comprimentos das ligações entre os nós:
AB:3; AC:4; AL:3; AV:1; BC:2; BL:8; BP:1; BR:6; CP:5; LR:1; LV:1; PR:6; PV:5; RV:3
7. 1. Determine, utilizando o algoritmo de Dijkstra, o caminho mais curto entre C e R. Nota: entre duas rotas
totalizando a mesma distância, escolha aquela que envolve menos nós de trânsito
R: CAVLR
7. 2. Escreva a tabela de encaminhamento do nó C.
R: A:A; B:B; L:A; P:B; R:A; V:A
7. 3. Idem para a rede de que se indicam os comprimentos das ligações entre os
nós:
AC:2; AF:10; AG:6; BD:1; BE:3; BH:6; CD:2; CH:10; DG:1; EF:1; EG:2; FH2
e se deseja conhecer o caminho mais curto entre A e H.
R: Caminho: ACDGEFH;
Tabela de encaminhamento: B/C; C/C; D/C; E/C; F/C; G/C; H/C
7. 4. Idem para a Rede esquematizada em Routing07.a
8. Considere a rede abaixo, em que se indicam os comprimentos das ligações entre os nós,
AB:2; AD:4; BC:5; CG:4; CH:6; DE:3; EJ:4; FG:5; FK:2; HI:3; HL:3; JK:6; KL:5
Sendo dado um qualquer par de nós fonte → destino (por exemplo, D → I), determine, utilizando o algoritmo
de Dijkstra, o caminho mais curto entre eles. R:
A
A
B
C
D
E
F
G
H
I
J
K
B
2
C
7
5
D
4
6
11
E
F
16
14
9
15
12
7
9
14
3
G
11
9
4
15
17
5
H
13
11
6
17
18
10
10
I
16
14
9
20
21
13
13
3
J
11
13
17
7
4
8
13
14
17
K
17
16
11
13
10
2
7
8
11
6
L
16
14
9
18
15
7
12
3
6
11
5
9. Considere a rede esquematizada abaixo, em que se indicam os comprimentos das ligações entre um conjunto de
nós:
AB:4; AC:3; AE:5; BC:2; BD:7; CD:10; CE:4; CF:5; DF:2; EF:8
9. 1. Recorrendo ao algoritmo de Dijkstra, determine o caminho mais curto para cada par de nós.
R:
A
B
C
D
E
A
-
B
AB
-
C
AC
BC
-
D
ABD
BD
CFD
-
E
AE
BCE
CE
DFE
-
F
ACF
BCF
CF
DF
EF
9. 2. Escreva a tabela de encaminhamento do nó E. R: A:A; B:C; C:C; D:F
10. Considere a rede ponto a ponto indicada, formada por ligações full-duplex:
A:(0,0); B:(1,0); C:(2,0); D:(0,1); E:(1,1); F:(2,1)
Admita que o algoritmo de encaminhamento selecciona as rotas que minimizam os tempos de atraso até cada
destinatário. Os tempos de atraso entre cada par de nós adjacentes são os dados pela tabela seguinte:
A
B
C
D
E
F
A
2
1
1
B
6
3
4
1
C
D
3
1
1
3
E
1
2
4
2
F
2
2
3
-
Encaminhamento
Prof V Vargas, IST
03/11/11, Pg 4/4
10. 1. Determine o tempo de atraso mínimo de A para todos os outros nós; indique as rotas que as mensagens
devem seguir para terem apenas esse tempo de atraso mínimo.
R: A-E-B:5; A-E-B-C:6; A-E-D:2; A-E:1; A-E-F:4
10. 2. Escreva a tabela de encaminhamento do nó A. R: B:E; C:E; D:E; E:E; F:E
10. 3. Sem repetir a aplicação do algoritmo utilizado acima, indique a rota seguida por um pacote com origem
em F e destinado ao nó A. R: F-E-A
11. Considere a rede de comunicação de pacotes onde se indica, para cada ramo, o custo do envio, por ele, de um
pacote de comprimento médio:
AB: 3; AC:2; AD:2; BC:7; BE:8; CD:4; CG:10; DF:3; EF:6; EH:5; FG:2; GH:4
11. 1. Escreva as tabelas de encaminhamento de cada um dos nós de comutação, de modo a minimizar o custo
do envio de um pacote de comprimento médio através da rede;
R:
Nó actual
A
B
C
D
E
F
G
H
A
B
C
D
B
D
D
D
B
Nó Destino
C
D
E
F
G
A
A
E
A
A
A
D
D
D
D
D
G
G
H
F
F
F
F
F
F
H
11. 2. Explicite qual a rota seguida por um pacote passado ao nó F com destino ao nó D. R: FD
12. Considere a seguinte rede
AB:0,01; AE:0,03; BC:0,05; BE:0,01; CD:0,06; CF:0,01; CG:0,02; DG: 0,03; EF:0,04; FG: 0,03
onde o número associado a uma linha representa a probabilidade de a linha falhar durante uma conversação
estabelecida entre os nós A e G (admite-se que as falhas nas linhas acontecem independentemente umas das
outras).
Determine a rota mais robusta entre A e G, isto é, aquela para a qual é máxima a probabilidade de que todas as
linhas se mantenham intactas durante a conversação. Qual o valor dessa probabilidade?
R: ABEFG. Prob=(1-0,01)(1-0,01)(1-0,04)(1-0,03)
Encaminhamento estático
13. Qual é a diferença, se é que existe alguma, entre encaminhamento estático usando duas alternativas com igual
peso, e encaminhamento por inundação usando apenas as duas melhores rotas?
14. Considere que dois nós de uma rede estão directamente ligados por duas linhas “em paralelo”, de capacidades
Cα e Cβ; a um dos nós estão chegando γ pacotes/segundo, destinados ao outro. Utiliza-se encaminhamento
estático com duas rotas alternativas de peso diferente: p por cento dos pacotes são encaminhados pela linha α, e
os restantes são encaminhados pela outra linha, β . Qual deve ser o valor de p em ordem a minimizar o tempo
médio de atraso entre os dois nós?
R: dT/dp=0, com T/γ = p/[µ Cα -pγ]+(1-p)/[µ Cβ -(1-p)γ]