RESOLUÇÃO DE PROGLEMAS UNIDADE 5 JOAO VICTOR

Prévia do material em texto

1. Suponha que o conteúdo de informação de um pacote seja o padrão de bits 1110 0110 1001 1101 e que um esquema de paridade par esteja sendo usado. Qual seria o valor do campo de soma de verificação para o caso de um esquema de paridade bidimensional? Sua resposta deve ser tal que seja usado um campo de soma de verificação de comprimento mínimo.
R: 1 1 1 0 1
 0 1 1 0 0
 1 0 0 1 0
 2 0
 1 1 0 1 1
 1 1 0 0 0
2. Durante a aula, fornecemos um esboço da derivação da eficiência do slotted ALOHA. Neste problema, concluiremos a derivação. 
a. Lembre-se de que, quando há N nós ativos, a eficiência do slotted ALOHA é
 Np(1 – p)N-1. Ache o valor de p que maximize essa expressão. 
b. Usando o valor de p encontrado em (a), ache a eficiência do slotted ALOHA fazendo que N tenda ao infinito. Dica: (1 – 1/N)N tende a 1/e quando N tende ao infinito.
• Suponha N nós com muitos quadros para enviar, cada um 
transmite no slot com probabilidade p
• Prob. de o nó 1 obter sucesso num slot = p(1-p)N-1
• Prob. de qualquer nó obter um sucesso = Np(1-p)N-1
• Para máxima eficiência com N nós, encontre p* que maximiza 
Np(1-p)N-1
• Para muitos nós, o limite de Np*(1-p*)N-1 
,com N indo ao infinito, 
resulta 1/e = .37
3. Suponha que quatro nós ativos — nós A, B, C e D — estejam competindo pelo acesso a um canal usando o slotted ALOHA. Imagine que cada nó tenha um número infinito de pacotes para enviar. Cada nó tenta transmitir em cada intervalo (slot) com probabilidade p. O primeiro é numerado como 1, o segundo como 2, e assim por diante. 
a. Qual a probabilidade que o nó A tenha sucesso pela primeira vez no intervalo 5?
Levando em conta a possibilidade de falhar 4 vezes e acertar na 5, chegamos na expressão -> ((1-(1-p)^3 * p)^4) *(p(1-p)^3)
b. Qual a probabilidade que algum nó (A, B, C ou D) tenha sucesso no intervalo 4?
P(S) = 4*(p(1-p)^3), probabilidade de algum nó suceder, como temos 4 nós, multiplicamos por 4
c. Qual a probabilidade que o primeiro sucesso ocorra no intervalo 3? d. Qual a eficiência nesse sistema de quatro nós?
A probabilidade de que todos os nós irão falhar na transmissão duas vezes, e considerando que UM deles conseguirá transmitir: 
1-(4(p(1-p)^3))^2 * (4p(1-p)^3)
d. Qual a eficiência nesse sistema de quatro nós?
4p(1-p)^4-1 ou (3/4)^3
4. Considere um canal de difusão com N nós e uma taxa de transmissão de R bits/s. Suponha que o canal de difusão use o polling (com um nó de polling adicional) para acesso múltiplo. Imagine que o intervalo de tempo entre o momento em que o nó conclui a transmissão e o momento em que o nó subsequente é autorizado a transmitir (isto é, o atraso de polling) seja dpoll. Suponha ainda que, em uma rodada de polling, determinado nó seja autorizado a transmitir, no máximo, Q bits. Qual é a vazão máxima do canal de difusão?
Vazão = Transmissão de Dados em 1 round / Tempo para completar o round
Vazão = N * Q/ (N * (D + Q/R)) = Q/ (D + Q/R)
5. Considere três LANs interconectadas por dois roteadores, como mostrado na Figura a seguir
a. Atribua endereços IP a todas as interfaces. Para a Sub-rede 1, use endereços do tipo 192.168.1.xxx; para a Sub-rede 2, use endereços do tipo 192.168.2.xxx, e para a Sub-rede 3 use endereços do tipo 192.168.3.xxx.
b. Atribua endereços MAC a todos os adaptadores.
c. Considere o envio de um datagrama IP do hospedeiro A ao hospedeiro F. Suponha que todas as tabelas ARP estejam atualizadas. Enumere todas as etapas, como foi feito no exemplo de um único roteador apresentado na aula.
d. Repita (c), admitindo agora que a tabela ARP do hospedeiro remetente esteja vazia (e que as outras tabelas estejam atualizadas).
6.	Considere a Figura anterior. Agora substituímos o roteador entre as sub-redes 1 e 2 pelo comutador S1, e chamamos de R1 o roteador entre as sub-redes 2 e 3.
a. Considere o envio de um datagrama IP do hospedeiro E ao hospedeiro F. O hospedeiro E pedirá ajuda ao roteador R1 para enviar o datagrama? Por quê? No quadro Ethernet que contém o datagrama IP, quais são os endereços IP e MAC de origem e de destino?
Não. E pode verificar o prefixo sub-rede do endereço IP do host de F, e então aprender que F faz parte da mesma LAN. Assim, E não vai enviar o pacote para o roteador padrão R1.
No Quadro Ethernet de E para F: 
Endereço IP de origem: E 
Endereço IP de destino: F
 Endereço MAC de Origem: E 
Endereço MAC de destino: F
b. Suponha que E quisesse enviar um datagrama IP a B, e que o cache ARP de E não tenha o endereço MAC de B. E preparará uma consulta ARP para descobrir o endereço MAC de B? Por quê? No quadro Ethernet (que contém o datagrama IP destinado a B) entregue ao roteador R1, quais são os endereços de origem e destino IP e MAC?
Não, porque eles não estão na mesma LAN. E pode descobrir isso através da verificação IP de B. 
No Quadro Ethernet de E para R1: 
Endereço IP de origem: E 
Endereço IP de destino: B 
Endereço MAC de Origem: E 
Endereço MAC de destino: O endereço MAC da interface de R1 que liga a sub-rede 3.
c. Suponha que o hospedeiro A gostaria de enviar um datagrama IP ao hospedeiro B, e nem o cache ARP de A contém o endereço MAC de B, nem o cache ARP de B contém o endereço MAC de A. Suponha ainda que a tabela de encaminhamento do comutador S1 contenha entradas apenas para o hospedeiro B e para o roteador R1. Dessa forma, A transmitirá por difusão uma mensagem de requisição ARP. Que ações o comutador S1 tomará quando receber a mensagem de requisição ARP? O roteador R1 também receberá essa mensagem? Se sim, R1 a encaminhará para a Subrede 3? Assim que o hospedeiro B receber essa mensagem de requisição ARP, ele enviará a mensagem de resposta ARP de volta ao hospedeiro A. Mas enviará uma mensagem de consulta ARP para o endereço MAC de A? Por quê? O que o comutador S1 fará quando receber a mensagem de resposta ARP do hospedeiro B?
O comutador S1 vai transmitir o quadro de consulta ARP (broadcast) por todas as suas interfaces. Quando recebe o quadro de A, o comutador aprende o locar do emissor (descobre que A reside na sub-rede 1, que está ligado a S1 na interface de ligação com a sub-rede 1). O comutador S1 atualizará sua tabela de repasse para incluir uma entrada para o Host A. Sim, o roteador R1 também recebe a consulta ARP, mas R1 não irá encaminhara a mensagem a sub-rede 3. B não enviará uma consulta ARP pedindo o endereço MAC de A, visto que este endereço foi obtido a partir da consulta ARP enviada por A. Quando o comutador S1 receber a resposta de B, ele irá adicionar uma entrada para o host B na sua tabela de repasse, e em seguida, descartara a mensagem, devido ao seu mecanismo de filtragem.
7. Considere o problema anterior, mas suponha que o roteador entre as sub-redes 2 e 3 é substituído por um comutador. Responda às questões de (a) a (c) do exercício anterior nesse novo contexto.
a. Não. E pode verificar o prefixo sub-rede do endereço IP do host de F, e então aprender que F faz parte da mesma LAN. Assim, E não vai enviar o pacote para S2. Quadro Ethernet de E para F: Endereço IP de origem: E 
Endereço IP de destino: F
Endereço MAC de Origem: E Endereço MAC de destino: F
b. Sim, porque E gostaria de encontrar o endereço MAC de B. Neste caso, E vai enviar uma consulta ARP com endereço MAC de destino sendo o endereço de broadcast. Este pacote de consulta será retransmitido pelo comutador S1 e, eventualmente, recebido pelo Host B. 
Quadro Ethernet de E para S2: 
Endereço IP de origem do IP = E 
Endereço IP de destino do IP = B 
Endereço MAC de Origem: E Endereço MAC de destino: FF-FF-FF-FF-FF-FF.
c. O comutador S1 vai transmitir o quadro de consulta ARP (broadcast) por todas as suas interfaces. Quando recebe o quadro de A, o comutador aprende o locar do emissor (descobre que A reside na sub-rede 1, que está ligado a S1 na interface de ligação com a sub-rede 1). O comutador S1 atualizará sua tabela de repasse para incluir uma entrada para o Host A. Sim, o comutador S2 também recebe esta mensagem de solicitação ARP, e irá transmitir esta consulta para todas as suas interfaces. B não enviará umaconsulta ARP pedindo o endereço MAC de A, visto que este endereço foi obtido a partir da consulta ARP enviada por A. Quando o comutador S1 receber a resposta de B, ele irá adicionar uma entrada para o host B na sua tabela de repasse, e em seguida, envia o quadro recebido para o destino no host A eu está na mesma LAN.
8. Lembre-se de que, com o protocolo CSMA/CD, o adaptador espera K ∙ 512 tempos de bits após uma colisão, onde K é escolhido aleatoriamente. Para K = 100, quanto tempo o adaptador espera até voltar à etapa 2 para uma Ethernet de 10 Mbits/s? E para canal de difusão de 100 Mbits/s?
	Espera para 51,200 tempos de bit para 10Mbps:
	51.2 x 103 bits : 10 x 106 bps = 5.12 ms
	Para 100Mbps:
	512 µs
9. Suponha que os nós A e B estejam no mesmo segmento de uma Ethernet de 10 Mbits/s e que o atraso de propagação entre os dois nós seja de 245 tempos de bit. Imagine que A e B enviem quadros ao mesmo tempo, que estes colidam e que, então, A e B escolham valores diferentes de K no algoritmo CSMA/CD. Admitindo que nenhum outro nó esteja ativo, as retransmissões de A e B podem colidir? Para nossa finalidade, é suficiente resolver o seguinte exemplo. Suponha que A e B comecem a transmitir em t = 0 tempos de bit. Ambos detectam colisões em t = 245 tempos de bit. Suponha que KA = 0 e KB = 1. Em que tempo B programa sua retransmissão? Em que tempo A começa a transmissão? (Nota: os nós devem esperar por um canal ocioso após retornar à etapa 2 — veja o protocolo.) Em que tempo o sinal de A chega a B? B se abstém de transmitir em seu tempo programado?
Em t = 0 A transmite. Em t = 576, A terminaria de transmitir. 
Na pior das hipóteses, B começa a transmitir no instante t = 224. 
No instante t = 224 + 225 = 449 o primeiro bit de B chega ao A. 
Como 449 < 576, A aborta antes de completar a transmissão do pacote, pois é suposto a fazer isso. Assim, A não pode terminar a transmissão antes de detectar que B transmitiu. Isso implica que se A não detecta a presença de um host, então nenhum outro host começa a transmitir enquanto A está transmitindo.
10. Neste problema, exploraremos o uso de pequenos pacotes de aplicações de voz sobre IP (VoIP). Uma desvantagem de um pacote pequeno é que uma grande parte da largura de banda do enlace é consumida por bytes de cabeçalho. Portanto, suponha que o pacote é formado por P bytes e 5 bytes de cabeçalho.
a. Considere o envio direto de uma fonte de voz codificada digitalmente. Suponha que a fonte esteja codificada a uma taxa constante de 128 Kbits/s. Considere que cada pacote esteja integralmente cheio antes de a fonte enviá-lo para a rede. O tempo exigido para encher um pacote é o atraso de empacotamento. Determine, em termos de L, o atraso de empacotamento em milissegundos.
Taxa de Transmissão = 128kbps = 128 * 1000 bits
Tempo = Distancia / Taxa de Transmissao
Tempo = L*8/128*1000
Tempo = L/16ms
b. Os atrasos de empacotamento maiores do que 20 ms podem causar ecos perceptíveis e desagradáveis. Determine o atraso de empacotamento para L = 1.500 bytes (correspondente, mais ou menos, a um pacote Ethernet de tamanho máximo) e para L = 50 bytes (correspondente a um pacote ATM).
L = 1,500 bytes
Delay de empacotamento = L/16
=1500/16 
= 93.75
Quando L= 50 
Delay de empacotamento =L/16
=50/16
= 3.125
c. Calcule o atraso de armazenagem e repasse em um único comutador para uma taxa de enlace R = 622 Mbits/s para L = 1.500 bytes e L = 50 bytes.
	Taxa de Transmissão = 622*106 bps
atraso de armazenagem e repasse = (L*8+ 40) /R
= (1500*8+40) /622*106
=19.36 µs
Taxa de Transmissão = 622*106 bps
atraso de armazenagem e repasse = (L*8+ 40) /R
= (50*8+40) /622*106
= 0.7 µs
d. Comente as vantagens de usar um pacote de tamanho pequeno.
 Quando os pacotes pequenos são usados, o tempo de atraso é muito pequeno porque os pacotes não precisam esperar.
11. Considere a rede MPLS mostrada na Figura a seguir e suponha que os roteadores R5 e R6 agora são habilitados para MPLS. Imagine que queremos executar engenharia de tráfego de modo que pacotes de R6 destinados a A sejam comutados para A via R6-R4-R3-R1, e pacotes de R5 destinados a A sejam comutados via R5-R4-R2-R1. Mostre as tabelas MPLS em R5 e R6, bem como a tabela modificada em R4, que tornariam isso possível.
	Em R4:
	Entrada
	Saida
	Destino
	Int. de Saida
	21
	10
	A
	0
	 
	12
	D
	0
	22
	22
	A
	1
				
			
	
Em R5:	
	Entrada
	Saida
	Destino
	21
	A
	1
	
Em R6:
	Entrada
	Saida
	Destino
	22
	A
	1
		
	
13. Neste problema, você juntará tudo o que aprendeu sobre protocolos de Internet. Suponha que você entre em uma sala, conecte-se à Ethernet e queira fazer o download de uma página. Quais são as etapas de protocolo utilizadas, desde ligar o computador até receber a página? Suponha que não tenha nada no seu DNS ou nos caches do seu navegador quando você ligar seu computador. (Dica: as etapas incluem o uso de protocolos da Ethernet, DHCP, ARP, DNS, TCP e HTTP.) Indique explicitamente em suas etapas como obter os endereços IP e MAC de um roteador de borda.
O computador primeiro usa DHCP para obter um endereço IP. O computador cria pela primeira vez um datagrama IP especial destinado a 255.255.255.255 na etapa de descoberta do servidor DHCP, e o coloca em um quadro Ethernet e o transmiti na Ethernet. Então, seguindo os passos do protocolo DHCP, o computador é capaz de obter um endereço IP com um determinado tempo de concessão. Um servidor DHCP na Ethernet também dá ao computador o endereço IP do roteador de primeiro salto, a máscara de sub-rede da sub-rede onde o computador reside, e o endereço do servidor DNS. A tabela ARP do computador é inicialmente vazio, assim o computador usará protocolo ARP para obter os endereços MAC do roteador de primeiro salto, do servidor DNS local e assim poder realizar a consulta DNS. Primeiro computador irá obter o endereço IP da página da Web que você gostaria de fazer download. Se o servidor DNS local não tiver o endereço IP, o seu computador irá utilizar DNS protocolo para localizar o endereço IP da página da Web. Uma vez que o computador tem o endereço IP da página da Web, em seguida, ele irá enviar uma solicitação HTTP, através do roteador de primeiro salto se a página Web não reside em um servidor Web local. O Mensagem de pedido HTTP será segmentado e encapsulados em pacotes TCP e, em seguida ainda encapsuladas em pacotes IP, e finalmente encapsulados em quadros Ethernet. Seu computador envia os quadros Ethernet destinados ao roteador de primeiro salto. Uma vez que o roteador recebe os quadros, os passa na camada IP, verifica sua tabela de roteamento e, em seguida envia os pacotes para a interface fora de todas as suas interfaces. Em seguida, seus pacotes IP serão encaminhados através da Internet até chegarem ao servidor Web. O servidor que hospeda a página Web irá enviar de volta a página da Web para o seu computador via Mensagens de resposta HTTP. Essas mensagens serão encapsuladas em pacotes TCP e em seguida, em pacotes IP. Esses pacotes IP seguem as rotas IP e, finalmente, chega ao seu roteador de primeiro salto, e, em seguida, o roteador irá encaminhar estes pacotes IP para o computador encapsulando-os em quadros de Ethernet.
14. Considere a rede do datacenter com topologia hierárquica da Figura abaixo. Suponha agora que haja 80 pares de fluxos, com dez fluxos entre a primeira e a nona estante, dez entre a segunda e a décima estante, e assim por diante. Suponha ainda que todos os enlaces na rede seja de 10 Gbits/s, exceto os enlaces entre os hospedeiros e os comutadores TOR, que são de 1 Gbit/s.
a. Cada fluxo tem a mesma velocidade de dados; determine a velocidade máxima de um fluxo
T -> C2 = 10/80 = 0,125 Gbps
	C2 -> C1 = 10/4 x 80 = 31,25 Mbps
	Tmax = 31,25 Mbps
b. Para o mesmo padrão de tráfego, determine a velocidade máxima de um fluxo para a topologia altamente interconectada da Figura abaixo.
	T -> C2 Não muda
	C2 -> C1 = 4x (10/4x80) = 125Mbps
	Tmax = 125 Mbps
c. Agora, suponha que haja um padrão de tráfego semelhante, mas envolvendo 20 fluxos em cada hospedeiroe 160 pares de fluxos. Determine as velocidades de fluxo máximas para as duas topologias.
	H -> T = 1/20 = 50Mbps
	T -> C2 = 10/160 = 62,5Mbps
	Tmax = 15,6Mbps
	T -> C2 = não muda
	C2 -> C1 = 4 x 15,6 = 62,5 Mbps
	Tmax = 62,5Mbps