394463343-Kurose-Cap-4-solution

Prévia do material em texto

Universidade Federal do Amazonas 
Instituto de Computação Disciplina – ICC-309 
 Redes de Computadores 
Nome: Rógenis Pereira da silva, Matrícula: 21650332 
 
Lista 3 
 
 R1. Vamos rever um pouco da terminologia usada neste livro. Lembre-se de que o 
nome de um pacote na camada de transporte é segmento e que o nome de um pacote 
na camada de enlace é quadro. 
 Qual é o nome de um pacote de camada de rede? Lembre-se de que roteadores e 
comutadores da camada de enlace são denominados comutadores de pacotes. Qual 
é a diferença fundamental entre um roteador e um comutador da camada de enlace? 
Lembre-se de que usamos o termo roteadores tanto para redes de datagramas quanto 
para redes de CVs. 
 
Resposta: Nome de um pacote da camada de rede se chama datagrama. 
 A diferença entre o roteador e um comutador é que o roteador pega um IP da Internet, 
e roteia para os computadores da rede, concedendo um IP de rede interna para cada um. E o 
comutador de pacotes permiti que computadores sejam ligados a um roteador, através dos 
cabos de redes. 
 
R2. Quais são as duas funções mais importantes de camada de rede em uma rede de 
datagramas? Quais são as três funções mais importantes de camada de rede em uma 
rede com circuitos virtuais? 
 
Resposta: Roteamento e repasse são as duas funções mais importantes da camada de 
rede em uma rede de datagramas. 
 As três funções mais importantes de camada de rede em uma rede com circuitos 
virtuais são o estabelecimento de conexão, a determinação do caminho e a comutação dos 
pacotes. 
 
 
 
 
R3. Qual é a diferença entre rotear e repassar? 
 
Resposta: Repasse refere-se à ação local realizada por um roteador para transferir um 
pacote da interface de um enlace de entrada para a interface de enlace de saída apropriada. 
Roteamento refere-se ao processo de âmbito geral da rede que determina os caminhos fim a 
fim que os pacotes percorrem desde a origem até o destino 
 
 
R12. Roteadores têm endereços IP? Em caso positivo, quantos? 
 
Resposta: Roteadores possui endereço IP, e o número de endereços IP, é o mesmo que 
o número de interfaces. Nisso, o caminho entre o enlace e o hospedeiro chama-se interface, 
isso é, cada interface tem um número IP. 
 
R13. Qual é o equivalente binário de 32 bits para o endereço IP 223.1.3.27? 
 
Resposta: 223 = 11011111, pois o número 223 pode expressar-se como: 
 128 + 64 + 16 + 8 + 4 + 2 + 1 
 Por isso, o resultado é: 1101111 
 
1 = 00000001 
 3 = 00000011 
 
 27 = 11011, pois o número 27 pode expressar-se como: 
 16 + 8 + 2 + 1 
 Por isso, o resultado é: 00011011 
 
Logo, a equivalência binária para o IP 223.1.3.27 = 11011111.00000001.00000011.00011011 
 
R14. Visite um hospedeiro que usa DHCP para obter seu endereço IP, máscara de rede, 
roteador de default e endereço IP de seu servidor DNS local. Faça uma lista desses 
valores. 
Resposta: IP do Servidor DHCP: 192.168.0.1 
Endereço IPV4: 192.168.0.17/24 
 
R15. Suponha que haja três roteadores entre os hospedeiros de origem e de destino. 
Ignorando a fragmentação, um datagrama IP enviado do hospedeiro de origem até o 
hospedeiro de destino transitará por quantas interfaces? 
 Quantas tabelas de repasse serão indexadas para deslocar o datagrama desde a 
origem até o destino? 
Resposta: 8 interfaces deverão ser transitadas, para isso serão necessárias 3 
tabelas de encaminhamento 
 
R16. Suponha que uma aplicação gere blocos de 40 bytes de dados a cada 20 ms e 
que cada bloco seja encapsulado em um segmento TCP e, em seguida, em um 
datagrama IP. Que porcentagem de cada datagrama será sobrecarga e que 
porcentagem será dados de aplicação? 
Resposta: Cabeçalho IP = 20 Bytes, equivalente a 25% 
 Cabeçalho TCP = 20 Bytes, equivalente a 25% 
 Aplicação = 40 Bytes, equivalente a 50% 
 Logo, o overhead é a soma do cabeçalho IP + o cabeçalho TCP = 40 Bytes 
 
R18. Suponha que você compre um roteador sem fio e o conecte a seu modem a cabo. 
Suponha também que seu ISP designe dinamicamente um endereço IP a seu 
dispositivo conectado (isto é, seu roteador sem fio). Suponha ainda que você tenha 
cinco PCs em casa e que usa 802.11 para conectá-los sem fio ao roteador. Como são 
designados endereços IP aos cinco PCs? O roteador sem fio usa NAT? Por quê? 
 
Resposta: Os endereços IP são atribuídos através do protocolo DHCP, o DHCP permite 
que um hospedeiro seja alocado a um endereço IP de maneira automática. Um administrador 
de rede pode configurar o DHCP para que determinado hospedeiro receba o mesmo endereço 
IP toda vez que se conectar ou um hospedeiro pode receber um endereço IP temporário. 
 O roteador sem fio usa NAT, pois obtém apenas um endereço IP do provedor. 
 
R21. Compare e aponte as diferenças entre os algoritmos de roteamento de estado de 
enlace e por vetor de distâncias. 
Resposta: O algoritmo de roteamento de estado de enlace explora o caminho de “menor 
custo” entre o roteador de origem e o roteador de destino, é a parte da camada de redes 
responsável pela decisão sobre a linha de saída a ser utilizada na transmissão do pacote de 
entrada. 
 Já o algoritmo de roteamento por vetor de distâncias é iterativo, assíncrono e distribuído, 
isto é, cada nó recebe alguma informação de um ou mais vizinhos diretamente ligados a ele, 
realiza cálculos e, em seguida, distribui os resultados de seus cálculos para seus vizinhos, esse 
processo continua até que mais nenhuma informação seja trocada entre vizinhos. O algoritmo 
não requer que todos os nós rodeiem simultaneamente. Disto isto, o cálculo do caminho de 
menor custo é realizado de maneira distribuída. Um nó só conhece o vizinho para onde deve 
encaminhar um pacote a fim de alcançar o destino dado ao longo do caminho de menor custo, 
e o custo de um caminho dele mesmo para o destino. 
 
PROBLEMAS 
 
 
 P4. Considere a rede a seguir. 
 
a. Suponha que seja uma rede de datagramas. Mostre a tabela de repasse no roteador 
A, de modo que todo o tráfego destinado ao hospedeiro H3 seja encaminhado pela 
interface 3. 
 
Endereço de destino Interface de enlace 
H3 3 
 
 
b. Suponha que esta rede seja uma rede de datagramas. Você consegue compor uma 
tabela de repasse no roteador A, de modo que todo o tráfego de H1 destinado ao 
hospedeiro H3 seja encaminhado pela interface 3, enquanto todo o tráfego de H2 
destinado ao hospedeiro H3 seja encaminhado pela interface 4? (Dica: esta é uma 
pergunta capciosa.) 
 
Resposta: Não, pois a regra de encaminhamento é baseada apenas no endereço 
de destino, por isso não se consegue compor a tabela. 
 
 
 
 
c. Suponha, agora, que esta rede seja uma rede de circuitos virtuais e que haja uma 
chamada em andamento entre H1 e H3, e outra chamada em andamento entre H2 e 
H3. Elabore uma tabela de repasse no roteador A, de modo que todo o tráfego de H1 
destinado ao hospedeiro H3 seja encaminhado pela interface 3, enquanto todo o tráfego 
de H2 destinado ao hospedeiro H3 seja encaminhado pela interface 4. 
 
Resposta: Questão sobre circuitos virtuais. 
 
d.Admitindo o mesmo cenário de (c), elabore tabelas de repasse nos nós B, C e D 
 
Resposta:Questão sobre circuitos virtuais. 
 
P10. Considere uma rede de datagramas que usa endereços de hospedeiro de 32 bits. 
Suponha que um roteador tenha quatro enlaces, numerados de 0 a 3, e que os pacotes 
têm de ser repassados para as interfaces de enlaces desta forma: 
 
 Faixa do endereço de destino Interface de enlace 
11100000 00000000 00000000 00000000 
 até 0 
11100000 00111111 11111111 11111111 
 
11100000 01000000 00000000 00000000 
 até 1 
11100000 01000000 11111111 11111111 
 
11100000 01000001 00000000 00000000 
 até 2 
11100001 01111111 11111111 11111111 
 senão 3 
 
 
 
 
 
 
 
 
 
 
a. Elabore uma tabela de repasse que tenha cinco registros, use correspondência 
do prefixo mais longo e repasse pacotes para as interfaces de enlace corretas. 
 
Prefixo Interface de enlace 
11100000 00 0 
11100000 01000000 1 
1110000 2 
11100001 1 3 
Senão 3 
 
 
b. Descreva como sua tabela de repasse determina a interface de enlace apropriada 
para datagramas com os seguintes endereços: 
 
11001000 10010001 01010001 01010101 
11100001 01000000 11000011 00111100 
11100001 10000000 00010001 01110111 
 
• O prefixo que combina com o primeiro endereço é a quinta entrada da tabela de repasse, 
que corresponde a interface 3 
• O prefixo que combina com o segundo endereço é a terceira entrada da tabela de 
repasse, que corresponde a interface 2 
• O prefixo que combina com o terceiro endereço é a quarta entrada da tabela de repasse, 
que corresponde a interface 3 
 
 
 
 
 
 
 
 
 
P11. Considere uma rede de datagramas que utiliza endereços de hospedeiro de 8 bits. 
Suponha que um roteador utilize a correspondência do prefixo mais longo e tenha a 
seguinte tabela de repasse: 
Para cada uma das quatro interfaces, forneça a faixa associada de endereços de 
hospedeiro de destino e o número de endereços na faixa. 
 
Número de end. por interface Faixa de endereço de destino Interface de enlace 
26 = 64 endereços 00000000 até 00111111 0 
25 = 32 endereços 01000000 até 01011111 1 
25 + 26 = 96 endereços 01100000 até 01111111 2 
25 + 26 = 96 endereços 10000000 até 10111111 2 
26 = 64 endereços 11000000 até 11111111 3 
 
 
P12. Considere uma rede de datagramas que usa endereços de hospedeiros de 8 bits. 
Suponha que um roteador use a correspondência do prefixo mais longo e tenha a 
seguinte tabela de repasse: 
Para cada uma das quatro interfaces, forneça a faixa associada de endereços de 
hospedeiro de destino e o número de endereços na faixa. 
 
Número de end. por interface Faixa de endereço de destino Interface de enlace 
25 = 32 endereços 11000000 até 11011111 0 
26 = 64 endereços 10000000 até 10111111 1 
25 = 32 endereços 11100000 até 11111111 2 
26 + 26 = 128 endereços 00000000 até 01111111 3 
 
 
 
 
 
 
 
 
P13. Considere um roteador que interconecta três sub-redes: 1, 2 e 3. Suponha que 
todas as interfaces de cada uma dessas três sub-redes tenham de ter o prefixo 
223.1.17/24. Suponha também que a sub-rede 1 tenha de suportar até 60 interfaces, a 
sub-rede 2 tenha de suportar até 90 interfaces e a sub-rede 3, 12 interfaces. Dê três 
endereços de rede (da forma a.b.c.d/x) que satisfaçam essas limitações. 
 
 Endereço de destino 
223.1.17.0 / 26 
223.1.17.128 / 25 
223.1.17.192 / 28 
 
P14. Na Seção 4.2.2 é dado um exemplo de tabela de repasse (usando a 
correspondência de prefixo mais longo). Reescreva a tabela usando a notação a.b.c.d/x 
em vez da notação de cadeia binária. 
• Conversão Binário para decimal da interface 0 
Binário: 11001000 00010111 00010000 00000000 até 11001000 00010111 00010111 
11111111 
Decimal: 200 23 16 0 até 200 23 23 255 
• Conversão Binário para decimal da interface 1 
Binário: 11001000 00010111 00011000 00000000 até 11001000 00010111 00011000 
11111111 Decimal: 200 23 24 0 até 200 23 23 255 
• Conversão Binário para decimal da interface 2 
Binário: 11001000 00010111 00011001 00000000 até 11001000 00010111 00011111 
11111111 Decimal: 200 23 25 até 200 23 31 255 
 
Endereço de destino Interface do enlace 
200.23.16/21 0 
200.23.24/24 1 
200.23.24/21 2 
Senão 3 
P15. No Problema P10, solicitamos que você elaborasse uma tabela de repasse 
(usando a correspondência de prefixo mais longo). Reescreva a tabela usando a 
notação a.b.c.d/x em vez da notação de cadeia binária. 
 
 
• Conversão Binário para decimal da interface de enlace 0 
Binário:11100000 00 
Decimal: 224 0 
 
• Conversão Binário para decimal da interface de enlace 1 
Binário: 11100000 01000000 
Decimal: 224 64 
 
• Conversão Binário para decimal da interface de enlace 2 
Binário: 1110000 
Decimal: 224 
 
• Conversão Binário para decimal da interface de enlace 3 
Binário: 11100001 1 
Decimal: 225 
 
Endereço de destino Interface do enlace 
224.0/10 0 
224.64/16 1 
224.8 2 
225.128/9 3 
Senão 3 
 
 
 
 
 
 
 
P16. Considere uma sub-rede com prefixo 128.119.40.128/26. Dê um exemplo de um 
endereço IP (na forma xxx.xxx.xxx.xxx) que possa ser designado para essa rede. 
Suponha que um ISP possua bloco de endereços na forma 128.119.40.64/26. 
Suponha que ele queira criar quatro sub-redes a partir desse bloco, e que cada bloco 
tenha o mesmo número de endereços IP. Quais são os prefixos (na forma a.b.c.d/x) 
para as quatro sub-redes? 
 
 Resposta: Pode-se ter qualquer endereço IP na faixa de 128.119.40.128 até 
128.119.40.191, sendo 32 – 26 = 6, logo, 26 = 64. 
Cada sub-rede deverá ter 16 hosts, então serão necessários 4 bits, 24 = 16. Desta 
maneira, as quatros sub-redes serão: 128.119.40.64/28, 128.119.40.96/28, 128.119.40.112/28 
e 128.119.40.96/28 
 
P17. Considere a topologia mostrada na Figura 4.17. Denomine as três sub-redes com 
hospedeiros (começando em sentido horário, a partir da posição das 12h) como A, B e 
C. Denomine as sub-redes sem hospedeiros como D, E e F. 
 
A. Designe endereços de rede a cada uma das seis sub-redes, com as seguintes 
restrições: todos os endereços deverão ser alocados a partir de 214.97.254/23; a 
subrede A deve ter endereços suficientes para suportar 250 interfaces; a sub-rede B 
deve ter endereços suficientes para suportar 120 interfaces e a sub-rede C deve ter 
endereços suficientes para suportar 120 interfaces. É claro que cada uma das subredes 
D, E e F deve podersuportar duas interfaces. Para cada sub-rede, a designação deve 
tomar a forma a.b.c.d/x ou a.b.c.d/x – e.f.g.h/y. 
 
Resposta: Sub-rede A: 214.97.255/24 
 Sub-rede B: 214.97.254.0/25 
 Sub-rede C: 214.97.254.128/25 
 Sub-rede D: 214.97.254.0/31 
 Sub-rede E: 214.97.254.2/31 
 Sub-rede F: 214.97.254.4/30 
 
 
 
 
 
 
 b. Usando a resposta dada no item (a), elabore as tabelas de repasse (usando a 
correspondência de prefixo mais longo) para cada um dos três roteadores. 
 
Roteador 1 
Prefixo Interface de saída 
11010110 01100001 11111111 A 
11010110 01100001 11111110 00000000 D 
11010110 01100001 11111110 0000001 F 
 
Roteador 2 
Prefixo Interface de saída 
11010110 01100001 11111111 00000000 D 
11010110 01100001 11111110 0 B 
11010110 01100001 11111110 0000001 E 
 
Roteador 3 
Prefixo Interface de saída 
11010110 01100001 11111111 0000001 F 
11010110 01100001 11111110 00000001 E 
11010110 01100001 11111110 1 C 
 
 
 
P19. Considere enviar um datagrama de 2.400 bytes por um enlace que tem uma MTU 
de 700 bytes. Suponha que o datagrama original esteja marcado com o número de 
identificação 422. Quantos fragmentos são gerados? Quais são os valores em vários 
campos dos datagramas IP gerados em relação à fragmentação? 
 
 
 
 
 
 
 
 
 
 
Resposta: Seja o datagrama de 2.400 bytes (20 Bytes de cabeçalho IP + 2380 bytes de 
carga útil IP). São gerados 4 fragmentos, (680 bytes, 680 bytes, 680 bytes, 340 bytes). 
 
Fragmento Bytes ID Deslocamento Flag 
1 680 422 0 1 = significa que ainda há 
fragmentos 
2 680 422 85 = 680/8 1 = significa que ainda há 
fragmentos 
3 680 422 170 = 1360/8 1 = significa que ainda há 
fragmentos 
4 360 422 300 = 2400/8 0 = significa 
 último fragmento 
 
P20. Suponha que entre o hospedeiro de origem A e o hospedeiro destinatário B os 
datagramas estejam limitados a 1.500 bytes (incluindo cabeçalho). Admitindo um 
cabeçalho IP de 20 bytes, quantos datagramas seriam necessários para enviar um 
arquivo MP3 de 5 milhões de bytes? Explique como você obteve a resposta. 
 
Resposta: Seja o tamanho do arquivo MP3 de 5 milhões de bytes, 
 Seja o datagrama limitado a 1500 bytes, então cada datagrama pode transportar 1460 
bytes, pois 1500 – 40(cabeçalho), do arquivo MP3. 
 Logo, o número de diagramas necessários seriam 3425, pois tamanho do arquivo / 
tamanho do datagrama = 5 x 106 / 1460 = 3435 datagramas. 
 Deste modo, o último datagrama será 960+40 = 1000 bytes. 
 
P21. Considere a configuração de rede da Figura 4.22. Suponha que o ISP designe ao 
roteador o endereço 24.34.112.235 e que o endereço da rede residencial seja 
192.168.1/24. 
 
 
 
a.Designe endereços a todas as interfaces na rede residencial. 
 Resposta: 192.168.1.1, 192.168.1.2, 192.168.1.3, sendo a interface do roteador com IP 
192.168.1.4 
 
b.Suponha que haja duas conexões TCP em curso em cada hospedeiro, todas para a 
porta 80 no hospedeiro 128.119.40.86. Forneça os seis registros correspondentes na 
tabela de tradução NAT. 
 
Tabela de tradução NAT 
Lado da Wan Lado a Lan 
24.34.112.235, 400 192.168.1.1, 3345 
24.34.112.235, 401 192.168.1.1, 3346 
24.34.112.235, 402 192.168.1.2, 3345 
24.34.112.235, 403 192.168.1.2, 3346 
24.34.112.235, 404 192.168.1.3, 3345 
24.34.112.235, 405 192.168.1.3, 3346 
 
 
 
P22.Suponha que você esteja interessado em detectar o número de hospedeiros por 
trás da NAT. Você observa que a camada IP traz um número de identificação, de modo 
sequencial, em cada pacote IP. O número de identificação do primeiro pacote IP gerado 
por um hospedeiro é aleatório, e os números de identificação subsequentes são 
determinados sequencialmente. Admita que todos os pacotes IP gerados por 
hospedeiros por trás da NAT sejam enviados para o mundo exterior. 
 
a. Com base nessa observação e admitindo que você pode analisar todos os 
pacotes enviados para fora pela NAT, você pode descrever uma técnica simples que 
detecte o número de hospedeiros únicos por trás da NAT? Justifique sua resposta. 
 Resposta: Pode-se usar um sniffer de pacotes para gravar todo o pacote IP gerado pelo 
host por trás de um NAT, já que todos os IPs são enviados para fora. Deste modo, como cada 
host gera uma seqüência de pacotes IP com números sequenciais e um número de identificação 
inicial distinto, podemos agrupar pacotes IP com IDs consecutivos em um cluster, sendo o 
número de cluster o número de hosts por trás do NAT. 
b. Se os números de identificação não são determinados de maneira sequencial, e 
sim aleatória, sua técnica funcionaria? Justifique sua resposta. 
Resposta: A técnica descrita na questão a não funcionará, pois não haverá clusters em 
dados de sniffers caso esses números de identificação não forem atribuídos sequencialmente e 
não aleatoriamente. 
 
P26. Considere a seguinte rede. Com os custos de enlace indicados, use o algoritmo 
do caminho mais curto de Dijkstra para calcular o caminho mais curto de x até todos os 
nós da rede. Mostre como o algoritmo funciona calculando uma tabela semelhante à 
Tabela 4.3. 
 
Etapa N’ D(y).p(y) D(v).p(v) D(w).p(w) D(z).p(z) D(u).p(u) D(t).p(t) 
0 x 6, x 3, x 6, x 8, x ∞ ∞ 
1 xv 6, x 6, x 8, x 6, v 7, v 
2 xvy 6, x 8, x 6, v 7, v 
3 xvyw 8, x 6, v 7, v 
4 xvywu 8, x 7, v 
5 xvywut 8, x 
6 xvywutz 
 
P27. Considere a rede mostrada no Problema P26. Usando o algoritmo de Dijkstra e 
mostrando seu trabalho usando uma tabela semelhante à Tabela 4.3, faça o seguinte: 
 
a. Calcule o caminho mais curto de t até todos os nós da rede. 
b. Calcule o caminho mais curto de u até todos os nós da rede. 
c. Calcule o caminho mais curto de v até todos os nós da rede. 
d. Calcule o caminho mais curto de w até todos os nós da rede. 
e. Calcule o caminho mais curto de y até todos os nós da rede. 
f. Calcule o caminho mais curto de z até todos os nós da rede. 
 
 
 
 
 
A. Caminho mais curto de t até todos os nós da rede. 
Etapa N’ D(y).p(y) D(v).p(v) D(u).p(u) D(w).p(w) D(z).p(z) D(x).p(x) 
0 t 7, t 4, t 2, t ∞ ∞ ∞ 
1 tu 7, t 4, t 5, u ∞ ∞ 
2 tuv 7, t 5, u ∞ 7, v 
3 tuvw 7, t ∞ 7, v 
4 tuvwx 7, t 15, x 
5 tuvwxy 15, x 
6 tuvwxyz 
 
B. Caminho mais curto de u até todos os nós da rede. 
Etapa N’ D(y).p(y) D(v).p(v) D(t).p(t) D(w).p(w) D(z).p(z) D(x).p(x) 
0 u ∞ 3, u 2, u 3, u ∞ ∞ 
1 ut 9, t 3, u 3, u ∞ ∞ 
2 utv 9, t 3, u ∞ 6, v 
3 utvw 9, t ∞ 6, v 
4 utvwx 9, t 14, x 
5 utvwxy 14, x 
6 utvwxyz 
 
 
C. Caminho mais curto de v até todos os nós da rede. 
Etapa N’D(y).p(y) D(u).p(u) D(t).p(t) D(w).p(w) D(z).p(z) D(x).p(x) 
0 v 8, v 3, v 4, v 4, v ∞ 3, x 
1 vx 8, v 3, v 4, v 4, v 11, x 
2 vxu 8, v 4, v 4, v 11, x 
3 vxut 8, v 4, v 11, x 
4 vxutw 8, v 11, x 
5 vxutwv 11, x 
6 vxutwvx 
 
D.Caminho mais curto de w até todos os nós da rede. 
Etapa N’ D(y).p(y) D(u).p(u) D(t).p(t) D(v).p(v) D(z).p(z) D(x).p(x) 
0 w ∞ 3, w ∞ 4, w ∞ 6, w 
1 wu ∞ 5, u 4, w ∞ 6, w 
2 wuv 12, v 5, u ∞ 6, w 
3 wuvt 12, v ∞ 6, w 
4 wuvtx 12, v 14, x 
5 wuvtxy 14, x 
6 Wuvtxyz 
 
E.Calcule o caminho mais curto de y a 
Etapa N’ D(w).p(w) D(u).p(u) D(t).p(t) D(v).p(v) D(z).p(z) D(x).p(x) 
0 y ∞ ∞ 7, y 8, y 12, y 6, y 
1 yx 12, x ∞ 7, y 8, y 12, y 
2 yxt 12, x 9, t 8, y 12, y 
3 yxtv 12, x 9, t 12, y 
4 yxtvu 12, x 12, y 
5 yxtvuw 12, y 
6 yxtvuw 
 
 
 F. Caminho mais curto de z até todos os nós da rede. 
Etapa N’ D(w).p(w) D(u).p(u) D(t).p(t) D(v).p(v) D(y).p(y) D(x).p(x) 
0 z ∞ ∞ ∞ ∞ 12, y 8, z 
1 zx 14, x ∞ ∞ 11, x 12, y 
2 zxv 14, x 14, v 15, v 12, y 
3 zxvy 14, x 14, v 15, v 
4 zxvyu 14, x 15, v 
5 zxvyuw 15, v 
6 zxvyuwt 
P28. Considere a rede mostrada a seguir e admita que cada nó inicialmente conheça 
os custos até cada um de seus vizinhos. Considere o algoritmo de vetor de distâncias 
e mostre os registros na tabela de distâncias para o nó z. 
 
 Custo para 
 u v x y z 
v ∞ ∞ ∞ ∞ ∞ 
x ∞ ∞ ∞ ∞ ∞ 
z ∞ 6 2 ∞ 0 
 
Custo para 
 u v x y z 
v 1 0 3 ∞ 6 
x ∞ 3 0 3 2 
Z 7 5 2 5 0 
 
Custo para 
 u v x y z 
v 1 0 3 3 5 
x 4 3 0 3 2 
Z 6 5 2 5 0 
 
Custo para 
 u v x y z 
v 1 0 3 3 5 
x 4 3 0 3 2 
Z 6 5 2 5 0 
 
 
 
 
 
 
 
P30. Considere o fragmento de rede mostrado a seguir. x tem apenas dois vizinhos 
ligados a ele: w e y. w tem um caminho de custo mínimo até o destino u (não mostrado) 
de 5 e y tem um caminho de custo mínimo u de 6. Os caminhos completos de w e de y 
até u (e entre w e y) não são mostrados. Todos os valores dos custos de enlace na rede 
são números inteiros estritamente positivos. 
 
a.Dê os vetores de distâncias de x para os destinos w, y e u. 
 
 w y w 
D(X) 2 4 7 
 
b. Dê uma mudança de custo de enlace para c(x, w) ou para c(x, y) tal que x 
informará a seus vizinhos um novo caminho de custo mínimo até u como resultado da 
execução do algoritmo de vetor de distâncias. 
 
c. Dê uma mudança de custo de enlace para c(x, w) ou para c(x, y) tal que x não 
informará a seus vizinhos um novo caminho de custo mínimo até u como resultado da 
execução do algoritmo de vetor de distâncias. 
 
Resposta: Quaisquer mudança no custo do link c(x, y), não causará que x informe seus 
vizinhos de um novo caminho de custo mínimo para u. 
 
 
P33. Demonstre que, para o algoritmo de vetor de distâncias na Figura 4.30, cada valor 
no vetor de distâncias D(x) é não crescente e, consequentemente, se estabilizará em 
um número finito de etapas. 
 
 Resposta: Cada atualização de vetores de distância de nó é baseada na equação de 
Bellman-Ford, onde apenas decrementa esses valores em seu vetor de distância, e não há 
aumento nos valores. Caso não haja atualização, nenhuma mensagem será enviada. Portanto, 
D(x), não é incrementado, e como esses custos são finitos, os vetores de distância serão 
estabilizados em etapas finitas. 
 
 
P34. Considere a Figura 4.31. Suponha que haja outro roteador, w, conectado aos 
roteadores y e z. Os custos de todos os enlaces são: c(x, y) = 4, c(x, z) = 50, c(y, w) = 
1, c(z, w) = 1, c(y, z) = 3. Suponha que a reversão envenenada seja utilizada no 
algoritmo de roteamento de vetor de distâncias. 
 
a. Quando o roteamento de vetor de distâncias é estabilizado, os roteadores w, y e 
z informam uns aos outros sobre suas distâncias para x. Que valores de distância eles 
podem informar uns aos outros? 
 
Roteador z: 
W D(x) = ∞ 
Y D(X) = 6 
 
Roteador w: 
 
Y D(x) = ∞ 
Z D(X) = 5 
 
Roteador y: 
 
W D(x) = 4 
Z D(X) = 4 
 
 
b. Agora suponha que o custo do enlace entre x e y aumente para 60. Haverá um 
problema de contagem até o infinito mesmo se a reversão envenenada for utilizada? 
Por quê? Se houver um problema de contagem até o infinito, então quantas iterações 
são necessárias para o roteamento de vetor de distâncias alcançar um estágio estável 
novamente? Justifique sua resposta. 
 Resposta: Sim, haverá problema de contagem ao infinito. 
 
c. Como você modifica c(y,z) de modo que não haja qualquer problema de 
contagem até o infinito se c(y,x) mudar de 4 para 60? 
 
Resposta: Cortar o enlace entre Y e Z