Avaliação II gabarito

Prévia do material em texto

UNIVERSIDADE FEDERAL DE SANTA MARIA 
 CENTRO DE TECNOLOGIA 
 DEPARTAMENTO DE ELETRÔNICA E COMPUTAÇÃO 
 ELC1106 – REDES DE COMUNICAÇÃO DE DADOS 
 PROFESSOR: CARLOS HENRIQUE BARRIQUELLO 
 
2ª AVALIAÇÃO
Nome: ______________________________________________ Data: ______________ 
1) (Peso 1.5) Dado um grafo G, com conjunto de vértices V e arestas E, escreva em pseudocódigo 
o algoritmo de Dijkstra para cálculo do caminho mais curto em número de saltos entre dois 
vértices quaisquer (explique todas as variáveis que forem utilizadas). 
// v é um nó do grafo, d(v) é a menor distância até v, e predecessor(v) é o nó que precede v no 
caminho mais curto, s é a origem, t é o destino, u é um nó temporário, d(u,v) é a distância entre u e v 
(em número de saltos é sempre 1), visitado (v) indica se v já foi visitado, a função “extrai_min” 
retorna o nó não visitado com a menor distância, e caminho (s,t) guarda o caminho mais curto de s 
até t 
 
// inicialização 
Para todo v de V 
d(v) = infinito 
visitado(v) = falso 
predecessor(v) = nulo 
d(s)=0 // a origem é iniciada com 0 
u=s 
 visitado(u) = verdadeiro 
 
// algoritmo executa até que o nó de destino t seja marcado como visitado 
Enquanto u != t 
Para todo v de V 
Se d(u,v) != infinito && visitado(v) == falso // seleciona um vizinho ainda não visitado 
 Se d(u) + d(u,v) < d(v) 
 d(v) = d(u) + d(u,v) 
predecessor(v) = u 
 Fim se 
Fim se 
Fim para 
u=extrai_min (d não visitado) // escolhe o nó não visitado com a menor distância até agora 
visitado(u) = verdadeiro 
Fim enquanto 
 
// Cada nó do caminho já tem o predecessor calculado, então é só guardar todo o caminho 
voltando do nó t até o nó s 
 
Caminho (s,t) = t 
v=t 
Enquanto v !=s 
v= predecessor(t) 
Caminho (s,t) = [Caminho(s,t) v] 
Fim enquanto 
 
 
2) (Peso 1.0) Suponha que um roteador J recebeu os vetores de distância dos roteadores A,I,H,K e 
mediu os retardos até A,I,H,K como 8, 10, 12 e 16 ms, respectivamente. Sabendo que o roteador 
J, utilizando o algoritmo de Bellman-Ford distribuído, atualizou a distância até um roteador B 
como 20 ms indo pelo roteador A, determine a distância do roteador A até o roteador B. 
 
Resposta: distância de A até B é 20ms-8ms = 12ms. 
 
3) (Peso 1.5) Considerando o cabeçalho IP abaixo com os valores representados em numeração 
hexadecimal, responda: 
 45 20 03 c5 78 06 00 00 34 06 ca 1f d1 55 ad 71 c0 a8 01 7e 
 
a. Qual a versão do protocolo IP? IPv4 (pode ser descoberto observando o tamanho do 
cabeçalho que é 20 bytes), se fosse IPv6 o cabeçalho seria bem maior, pois os 
endereços são de 128 bits cada (16 bytes cada) 
b. Qual é o endereço IP da origem em representação decimal com pontos? 
209.85.173.113. Pode ser descoberto observando o alinhamento de 32 bits do cabeçalho 
IP. Como o cabeçalho tem 20 bytes, nenhuma opção está sendo usada e, portanto, os 
endereços estão nos dois últimos campos de 32 bits. A ordem é sempre a origem 
seguida do destino. Assim, o penúltimo valor de 32 bits é o IP da origem e o último é o 
IP do destino. 
c. Qual é o endereço IP do destino em representação decimal com pontos? 
192.168.1.126 (é o último valor de 32 bits). 
 
4) (Peso 1.5) Um determinado roteador R possui a tabela de roteamento abaixo. 
Endereço de destino Linha de saída Prefixo binário 
196.80.0.0/12 1 11000100.0101 
196.94.16.0/20 2 11000100.01011110.0001 
196.96.0.0/12 3 11000100.0110 
196.104.0.0/14 4 11000100.011010 
128.0.0.0/1 5 1 
64.0.0.0/2 6 01 
 
Com base nesta informação, determine a linha de saída a ser utilizada pelo roteador R para 
encaminhar os pacotes com os seguintes endereços IP de destino. 
As respostas são obtidas usando operação lógica AND com a máscara de rede até encontrar o 
prefixo da linha de saída. 
a. 176.94.16.0 – 5 (em binário é 10110000.01011110.00010000.00000000) 
b. 96.94.19.135 – 6 (em binário é 01100000.01011110.00010011.10000111) 
c. 196.94.32.128 – 1 (em binário é 11000100.01011110.00100000.10000000) 
 
5) (Peso 1.0) Uma máquina TCP está transmitindo janelas completas de CW bytes através de um 
canal de T bps que tem um tempo de ida e volta de RTT segundos. Qual é a taxa de 
transferência (throughput) máxima que é possível alcançar? 
 
R= CW/RTT bytes por segundo ou R = 8 x CW/RTT bits por segundo 
 
6) (Peso 1.5) Os valores “00 e6 00 bd 00 11 fe 24”, representados em numeração hexadecimal, 
estavam contidos no cabeçalho de um segmento de um determinado protocolo de transporte 
utilizado na internet. Com base nestas informações, responda: 
a. Que protocolo é este? UDP (pode ser descoberto que não é TCP, porque o TCP tem no 
mínimo 20 bytes de cabeçalho). 
b. Qual é o valor da porta de origem? 00e6 = 230 em decimal. 
Pode ser descoberto pelo alinhamento e sabendo que as portas são valores de 16 bits. 
Além disso, tanto no TCP quanto no UDP as portas sempre são os primeiros campos e a 
ordem sempre é primeiro a origem e depois o destino. 
c. Qual é o valor da porta de destino? 00bd = 189 em decimal. 
 
7) (Peso 2.0) Em um determinado instante t, uma conexão TCP tem uma janela de 
congestionamento de 4000 bytes. O tamanho máximo do segmento usado é 1000 bytes. Qual é 
o tamanho da janela de congestionamento após serem enviados 4 segmentos sem a ocorrência 
de estouro de tempo (timeout). . . 
Para ambas as alternativas (a) e (b) não ocorreu timeout, portanto a janela inicia em 4000 bytes 
e é aumentada 4 vezes. 
a. Se a conexão está no modo de inicialização lenta? 
4k, 8k, 16k, 32k, 64k => 64000 bytes (neste caso dobra 4 vezes) 
b. Se a conexão está no modo de abstenção de congestionamento (modo linear)? 
4k, 5k, 6k, 7k, 8k => 8000 bytes (neste caso, aumenta um segmento a cada vez)