30410344 Manual Solucoes Redes Tanenbaum

8/4/2019 30410344 Manual Solucoes Redes Tanenbaum

1/57

REDES DE COMPUTADORESANDREW S. TANENBAUM

SOLUES DOS PROBLEMAS

TRADUO DA QUARTA EDIO TRADUO VANDENBERG D. DE SOUZAANALISTA DE SISTEMAS E TRADUTOR

REVISO TCNICA EDGAR JAMHOURPROFESSOR DE REDES DE COMPUTADORES PUC-PR PONTIFCIA UNIVERSIDADE CATLICA DO PARAN


2/57

Todos os direitos reservados. Nenhuma parte deste livro pode ser reproduzida, emqualquer forma ou por quaisquer meios, sem permisso por escrito da editora.


3/57

SOLUES DOS PROBLEMAS DO CAPTULO 1

3

SOLUES DOS PROBLEMAS DO CAPTULO 11. O co pode transportar 21 gigabytes, ou 168 gigabits. A velocidade de 18 km/h igual a 0,005 km/s. O tempo para percorrer a distncia x km x/0,005 = 200x segundos

, o que significa uma taxa de dados de 168/200x Gbps ou 840/x Mbps. Para x < 5,6km, o co tem uma taxa mais alta que a linha de comunicao. O modelo de LAN pode serampliado de forma incremental. Se a LAN apenas um longo cabo, ela no pode ser desativada por uma falha isolada (se os servidores forem replicados). Provavelmente ela ter um custo mais baixo. Esse modelo oferece maior capacidade de computao e melhores interfaces interativas. Um link de fibra transcontinental pode ter muitos gigabits/s de largura de banda, mas a latncia tambm ser alta devido velocidade depropagao da luz por milhares de quilmetros. Em contraste, um modem de 56 kbps quechamar um computador no mesmo edifcio ter baixa largura de banda e baixa latncia. necessrio um tempo de entrega uniforme para voz, e assim a quantidade de flutuao narede importante. Isso poderia ser expresso como o desvio padro do tempo de entrega. A existncia de um pequeno retardo mas com grande variabilidade na realidade pi

or que um retardo um pouco mais longo com baixa variabilidade. No. A velocidade de propagao 200.000 km/s ou 200 metros/ms. Em 10 ms, o sinal percorre 2 km. Desse modo, cada switch adiciona o equivalente a 2 km de cabo extra. Se o cliente e o servidor estiverem separados por 5000 km, o percurso de at mesmo 50 switches s adicionar 100 km ao caminho total, o que corresponde a apenas 2%. Portanto, o retardode comutao no um fator importante sob essas circunstncias. A solicitao tem de subdescer, e a resposta tambm tem de subir e descer. O comprimento total do caminhopercorrido portanto 160.000 km. A velocidade da luz no ar e no vcuo 300.000 km/s, e assim o retardo de propagao sozinho 160.000/300.000 s ou cerca de 533 ms. bvioque no existe apenas uma resposta correta nesse caso, mas os pontos a seguir parecem relevantes. O sistema atual tem muita inrcia (cheques e saldos) incorporada aele. Essa inrcia pode servir para impedir que os sistemas legal, econmico e social sejam virados de cabea para baixo toda vez que um partido diferente chegar ao p

oder. Alm disso, muitas pessoas guardam opinies fortes sobre questes sociais controvertidas, sem realmente conhecerem os fatos relevantes para o assunto. Permitirque opi-

2.

3.

4.

5.

6.

7.


4/57

4


nies mal debatidas sejam transformadas em lei pode ser algo indesejvel. Os efeitospotenciais de campanhas de publicidade realizadas por grupos de interesses especiais de um tipo ou de outro tambm tm de ser considerados. Outra questo importante

a segurana. Muitas pessoas poderiam se preocupar com o fato de algum garoto de 14anos invadir o sistema e falsificar os resultados. 8. Chame os roteadores de A,B, C, D e E. Existem dez linhas potenciais: AB, AC, AD, AE, BC, BD, BE, CD, CEe DE. Cada uma dessas linhas tem quatro possibilidades (trs velocidades ou nenhuma linha). E assim, o nmero total de topologias 410 = 1.048.576. A 100 ms cada, ser necessrio o tempo de 104.857,6 segundos, ou pouco mais de 29 horas para inspecionar todas elas. O caminho mdio de roteador para roteador duas vezes o caminho mdiode roteador para a raiz. Numere os nveis da rvore com a raiz tendo o nmero 1 e o nvel mais profundo como n. O caminho desde a raiz at o nvel n exige n 1 hops (saltos), e 0,50 dos roteadores est nesse nvel. O caminho desde a raiz at o nvel n 1 tem 0,25 dos roteadores e um comprimento igual a n 2 hops. Conseqentemente, o comprimentodo caminho mdio, l, dado por: l = 0,5 (n 1) + 0,25 (n 2) + 0,125 (n 3) + .

l9.

n (0,5) i

i =1

i =1

n (0,5)

i

Essa expresso se reduz a l = n 2. Portanto, o caminho mdio de roteador a roteador 2n 4. 10. Faa a distino entre n + 2 eventos. Os eventos de 1 a n consistem na tentativa bem-sucedida do host correspondente de usar o canal, isto , sem uma coliso. Aprobabilidade de cada um desses eventos p(1 p)n-1. O evento n + 1 um canal inativo, com probabilidade (1 p)n. O evento n + 2 uma coliso. Tendo em vista que esses n + 2 eventos so exaustivos, a soma de suas probabilidades tem de ser a unidade. A probabilidade de uma coliso, que igual frao de slots desperdiados, ento simnte: 1 np(1 p)n-1 (1 p)n. Entre outras razes para a utilizao de protocolos em cas, seu emprego conduz quebra do problema de projeto em fragmentos menores e mais manejveis; alm disso, a diviso em camadas significa que os protocolos podem ser alterados sem afetar protocolos de nveis mais altos ou mais baixos.

11.


5/57


5

12. 13.

No. No modelo de protocolos da ISO, a comunicao fsica s tem lugar na camada mais baix

a, no em todas as camadas. A comunicao orientada a conexes tem trs fases. Na fase deestabelecimento, feita uma solicitao para configurar uma conexo. Somente aps essa fase ter sido concluda com sucesso, a fase de transferncia de dados pode ser iniciada e os dados podem ser transportados. Em seguida, vem a fase de liberao. A comunicao sem conexes no tem essas fases. Ela simplesmente envia os dados. Os fluxos de mensagens e bytes so diferentes. Em um fluxo de mensagens, a rede mantm o controle dos limites das mensagens. Em um fluxo de bytes, isso no acontece. Por exemplo, suponha que um processo grave 1.024 bytes para uma conexo, e que um pouco mais tardegrave outros 1.024 bytes. Em seguida, o receptor faz a leitura de 2.048 bytes.Com um fluxo de mensagens, o receptor obter duas mensagens de 1.024 bytes cada. No caso de um fluxo de bytes, os limites de mensagens no so levados em considerao, eassim o receptor ir receber os 2.048 bytes como uma nica unidade. O fato de terem

existido originalmente duas mensagens distintas perdido. A negociao significa fazer ambos os lados concordarem sobre alguns parmetros ou valores a serem usados durante a comunicao. O tamanho mximo do pacote um exemplo, mas existem muitos outros.O servio mostrado o servio oferecido pela camada k camada k + 1. Outro servio que deve estar presente se encontra abaixo da camada k, ou seja, o servio oferecido camada k pela camada subjacente k 1. A probabilidade, Pk, de um quadro exigir exatamente k transmisses a probabilidade das primeiras k 1 tentativas falharem, pk-1,vezes a probabilidade da k-sima transmisso ser bem-sucedida, (1 p). O nmero mdio detransmisses ento:

14.

15.

16.

17.

k =1

kP = k(1 p)p k k =1

k1

=

1 1p

18. 19.

(a) Camada de enlace de dados. (b) Camada de rede. Quadros encapsulam pacotes. Quando um pacote chega camada de enlace de dados, todo o conjunto, cabealho, dadose tudo mais, usado como campo de dados de um quadro. O pacote inteiro inseridoem um envelope (o quadro), por assim dizer (supondo-se que ele caiba no quadro).Com n camadas e h bytes adicionados por camada, o nmero total de bytes de cabealho por mensagem hn, e assim o espao desperdiado em cabealhos hn. O tamanho total da

mensagem M + nh; portanto, a frao da largura de banda desperdiada em cabealhos hn/+ hn).


6/57

20.


7/57

6


21.

Ambos os modelos so baseados em protocolos colocados em camadas. Ambos tm camadas

de rede, transporte e aplicao. Nos dois modelos, o servio de transporte pode fornecer um fluxo de bytes fim a fim confivel. Por outro lado, eles diferem em diversosaspectos. O nmero de camadas diferente, o TCP/IP no tem camadas de sesso ou de apresentao, o OSI no admite interligao de redes, e o OSI tem servio orientado a conexesem conexes na camada de rede. O TCP orientado a conexes, enquanto o UDP um serviosem conexes. Os dois ns do canto superior direito podem ser desconectados do restante por trs bombas que derrubam os trs ns aos quais eles esto conectados. O sistemapode resistir perda de dois ns quaisquer. A duplicao a cada 18 meses significa um ganho de quatro vezes em 3 anos. Em 9 anos, o ganho ento 43, ou 64, levando a 6,4bilhes de hosts. Minha opinio pessoal que esse nmero muito conservador, pois provavelmente nessa poca todo televisor do mundo e talvez bilhes de outros aparelhos eletrodomsticos estaro em LANs domsticas conectadas Internet. O usurio mdio no mundo d

envolvido talvez tenha ento dezenas de hosts da Internet. Se a rede tende a perder pacotes, melhor confirmar cada um separadamente, de modo que os pacotes perdidos possam ser retransmitidos. Por outro lado, se a rede altamente confivel, o envio de uma nica confirmao no fim da transferncia inteira poupa largura de banda no caso normal (mas exige que o arquivo inteiro seja retransmitido at mesmo se um nicopacote se perder). Clulas pequenas de tamanho fixo podem ser roteadas por switches com rapidez e completamente em hardware. Clulas de tamanho fixo e pequeno tambmtornam mais fcil a criao de hardware capaz de tratar muitas clulas em paralelo. Alm disso, elas no bloqueiam as linhas de transmisso por um tempo muito longo, facilitando o oferecimento de garantias de qualidade de servio. A velocidade da luz no cabo coaxial cerca de 200.000 km/s, que corresponde a 200 metros/ms. A 10 Mbps, necessrio 0,1 ms para transmitir um bit. Portanto, o bit dura 0,1 ms e, durante esse tempo, ele se propaga por 20 metros. Desse modo, um bit tem 20 metros de compr

imento. A imagem tem 1.024 768 3 bytes ou 2.359.296 bytes. Isso corresponde a 18.874.368 bits. A 56.000 bits/s, ela demora cerca de 337,042 segundos. A 1.000.000 bits/s, ela leva cerca de 18,874 s. A 10.000.000 bits/s, ela demora aproximadamente 1,887 segundos. A 100.000.000 bits/s, ela demora cerca de 0,189 segundo.

22. 23.

24.

25.

26.

27.

28.


8/57


7

29.

Pense no problema do terminal oculto. Imagine uma rede sem fios de cinco estaes, d

e A at E, tal que cada estao esteja no alcance apenas de seus vizinhos imediatos. Ento, A pode se comunicar com B ao mesmo tempo que D est se comunicando com E. Redes sem fios tm paralelismo potencial e, nesse aspecto, so diferentes da Ethernet. Uma desvantagem a segurana. Todo entregador que por acaso esteja no edifcio pode ouvir a rede. Outra desvantagem a confiabilidade. As redes sem fios cometem muitoserros. Um terceiro problema potencial o tempo de durao da bateria, pois a maioriados dispositivos sem fios tende a ser mvel. Uma vantagem que, se todos usarem opadro, cada um poder se comunicar com todos os outros. Outra vantagem que o uso disseminado de qualquer padro proporcionar economias de escala, como ocorre com os chips VLSI. Uma desvantagem o fato de os compromissos polticos necessrios para se alcanar a padronizao freqentemente levarem a padres pobres. Outra desvantagem que, dois que um padro amplamente adotado, torna-se muito difcil alter-lo, mesmo que seja

m descobertas novas tcnicas ou melhores mtodos. Alm disso, na poca em que ele for aceito, talvez esteja obsoleto. claro que existem muitos exemplos. Alguns sistemaspara os quais existe padronizao internacional incluem os aparelhos reprodutores de CDs e seus discos, os reprodutores de fita do tipo walkman e as fitas cassetesde udio, as cmeras e os filmes de 35 mm, e ainda os caixas eletrnicos e os cartes de bancos. As reas em que tal padronizao internacional carente incluem aparelhos devideocassete e fitas de vdeo (NTSC VHS nos Estados Unidos, PAL VHS em partes da Europa, SECAM VHS em outros pases), telefones portteis, luminrias e lmpadas (voltagens diferentes em pases diferentes), tomadas eltricas e plugues de aparelhos eletrodomsticos (cada pas tem padres diferentes), fotocopiadoras e papel (8,5 11 polegadasnos Estados Unidos, A4 em todos os outros pases), porcas e parafusos (medidas inglesas versus mtricas) etc.

30.

31.

32.

1. 2.

1 , bn = 0, c = 1. pn Um canal sem rudo pode transportar uma quantidade arbitrariamente grande de informaes, no importando com que freqncia feita a amostragem. Bastanviar uma grande quantidade de dados por amostra. No caso do canal de 4 kHz, crie 8.000 amostras/s. Se cada amostra tem 16 bits, o canal pode enviar 128 kbps. Se cada amostra tem 1.024 bits, o canal an =



9/57

8


pode enviar 8,2 Mbps. A expresso-chave aqui sem rudo. Com um canal normal de 4 kHz,o limite de Shannon no permitiria isso. 3. Usando o teorema de Nyquist, podemos fazer a amostragem 12 milhes de vezes/s. Sinais do nvel quatro fornecem 2 bits por

amostra, resultando em uma taxa de dados total de 24 Mbps. Uma relao sinal/rudo igual a 20 dB significa S/N = 100. Tendo em vista que log2 101 aproximadamente igual a 6,658, o limite de Shannon cerca de 19.975 kbps. O limite de Nyquist de 6 Kbps. Portanto, o gargalo o limite de Nyquist, que resulta em uma capacidade mximade canal de 6 kbps. Para enviar um sinal T1, precisamos de Hlog2(1 + S/N) = 1,544 106 com H = 50.000. Isso resulta em S/N = 230 1, que corresponde a cerca de 93dB. Uma estrela passiva no tem nenhum componente eletrnico. A luz de uma fibra ilumina uma srie de outras. Um repetidor ativo converte o sinal ptico em um sinal eltrico para processamento posterior. Use D = cDl/l2 com Dl = 107 metros e l = 106 metros. Isso d uma largura de banda (D) = 30.000 GHz. A taxa de dados 480 640 24 60ps, que igual a 442 Mbps. Por simplicidade, vamos supor 1 bps por Hz. Da equao (2-3), obtemos Dl = l2 D /c. Temos D = 4,42 108, e assim Dl = 2,5 106 micra. O interva

lo de comprimentos de onda utilizados muito curto. O teorema de Nyquist uma propriedade matemtica e no tem nenhuma relao com a tecnologia. Ele afirma que, se voc temuma funo cujo espectro de Fourier no contm nenhum seno ou co-seno acima de , ento,r amostragem da funo freqncia de 2, voc ir captar todas as informaes que existeodo, o teorema de Nyquist verdadeiro para todos os tipos de meios de transmisso.No texto, foi declarado que as larguras de banda (isto , os intervalos de freqncia)das trs bandas eram aproximadamente iguais. A partir da frmula D = cDl/l2 fica claro que, para se obter uma constante Dl, quanto maior a freqncia maior tem de ser Dl. O eixo x na figura l; assim, quanto maior a freqncia, maior o valor Dl necessrio. De fato, Dl quadrtico em l. O fato das bandas serem aproximadamente iguais umapropriedade acidental do tipo de silcio usado. Comece com l = c. Sabemos que c 3 108 m/s. Para l = 1 cm, obtemos 30 GHz. Para l = 5 m, obtemos 60 MHz. Desse modo,a banda coberta de 60 MHz a 30 GHz.

4.

5.

6.

7. 8.

9.

10.

11.8


10/57


9

12.

A 1 GHz, as ondas tm o comprimento de 30 cm. Se uma onda percorrer 15 cm mais que

a outra, elas chegaro fora de fase. O fato do link ter o comprimento de 50 km irrelevante. Se o feixe estiver desviado 1 mm no fim do percurso, ele perder o detector. Isso significa um tringulo com base 100 m e altura 0,001 m. Portanto, o ngulo aquele cuja tangente 0,00001. Esse ngulo mede cerca de 0,00057 grau. Com 66/6 ou 11 satlites por colar, a cada 90 minutos, 11 satlites passam por uma posio diretamente vertical. Isso significa que existe um trnsito a cada 491 segundos. Desse modo, haver um handoff a cada 8 minutos e 11 segundos, aproximadamente. O satlite semovimenta de uma posio diretamente vertical em direo ao horizonte meridional, com uma excurso mxima a partir da posio vertical igual a 2f. Ele leva 24 horas para ir daposio diretamente vertical at a excurso mxima e voltar. O nmero de cdigos de rea2 10, que igual a 160. O nmero de prefixos era 8 8 10, ou 640. Desse modo, o nmede centrais finais (end offices) se limitou a 102.400. Esse limite no problema.

Com um nmero telefnico de 10 dgitos, poderia haver 1010 nmeros, embora muitos cdigosde rea sejam invlidos, como 000. Porm, um limite muito mais restrito dado pelo nmerode centrais finais. Existem 22.000 centrais finais, cada uma com um mximo de 10.000 linhas. Isso nos d no mximo 220 milhes de telefones. Simplesmente no h lugar paraconectar mais telefones. Isso nunca poderia ser conseguido na prtica, porque algumas centrais finais no esto cheias. Uma central final em uma pequena cidade do Wyoming talvez no tenha 10.000 clientes perto dela, e portanto essas linhas so desperdiadas. Cada telefone faz 0,5 chamada/hora, de 6 minutos cada. Desse modo, um telefone ocupa um circuito por 3 minutos/hora. Vinte telefones podem compartilharum circuito, embora a necessidade de manter a carga prxima a 100% (r = 1 em termos de enfileiramento) implique tempos de espera muito longos. Tendo em vista que10% das chamadas so interurbanas, so necessrios 200 telefones para ocupar em tempointegral um circuito interurbano. O tronco da estao tem 1.000.000/4.000 = 250 circ

uitos multiplexados sobre ele. Com 200 telefones por circuito, uma estao pode admitir 200 250 = 50.000 telefones. A seo transversal de cada fio de um par tranado mede p/4 mm2. Uma extenso de 10 km desse material, com dois fios por par, tem um volume igual a 2p/4 102 m3. Esse volume cerca de 15.708 cm3. Com uma mas-

13.

14.

15.

16.

17.

18.

19.


11/57

10


sa especfica igual a 9,0, cada loop local tem massa igual a 141 kg. Portanto, a companhia telefnica possui 1,4 109 kg de cobre. A 3 dlares por quilograma, o cobrevale aproximadamente 4,2 bilhes de dlares. 20. Como uma nica linha de estrada de fe

rro, ele half-duplex. O leo pode fluir em qualquer sentido, mas no em ambos os sentidos ao mesmo tempo. Normalmente, os bits so enviados pela linha sem qualquer esquema de correo de erros na camada fsica. A presena de uma CPU em cada modem torna possvel incluir um cdigo de correo de erros na camada 1 para reduzir bastante a taxade erros efetiva vista pela camada 2. O tratamento de erros pelos modems pode ser totalmente transparente para a camada 2. Muitos modems atuais incluem correo deerros. Existem quatro valores vlidos por baud, e assim a taxa de bits duas vezesa taxa em bauds. A 1.200 bauds, a taxa de dados 2.400 bps. O deslocamento de fase sempre 0, mas so usadas duas amplitudes; portanto, ele utiliza modulao por amplitude direta. Se todos os pontos estiverem eqidistantes da origem, todos eles tero amesma amplitude, e assim a modulao de amplitude no est sendo usada. A modulao de fria nunca utilizada em diagramas de constelao; portanto, a codificao de chaveamento

or deslocamento de fase puro. Dois, um para upstream e um para downstream. O esquema de modulao propriamente dito utiliza apenas amplitude e fase. A freqncia no molada. H 256 canais ao todo, menos 6 para POTS e 2 para controle, restando 248 para dados. Se desses canais forem para downstream, isso dar 186 canais para downstream. A modulao ADSL feita em 4.000 bauds; assim, com QAM-64 (6 bits/baud), teremos24.000 bps em cada um dos 186 canais. A largura de banda total ser ento 4,464 Mbps downstream. Uma pgina da Web de 5 KB tem 40.000 bits. O tempo de download sobreo canal de 36 Mbps 1,1 ms. Se o retardo de enfileiramento tambm for de 1,1 ms, otempo total ser 2,2 ms. Sobre a ADSL no existe nenhum retardo de enfileiramento,e assim o tempo de download a 1 Mbps 40 ms. A 56 kbps, ele igual a 714 ms. Existem dez sinais de 4.000 Hz. Precisamos de nove bandas de proteo para evitar qualquer interferncia. A largura de banda mnima exigida 4.000 10 + 400 9 = 43.600 Hz.

21.

22. 23. 24.

25.

26.

27.

28.


12/57


11

29.

Um tempo de amostragem de 125 ms corresponde a 8.000 amostras por segundo. De ac

ordo com o teorema de Nyquist, essa a freqncia de amostragem necessria para captartodas as informaes em um canal de 4 kHz, como o de um canal telefnico. (Na realidade, a largura de banda nominal um pouco menor, mas o corte no ntido.) Os usurios finais obtm 7 24 = 168 dos 193 bits em um quadro. O overhead portanto de 25/193 = 13%. Em ambos os casos, so possveis 8.000 amostras/s. Com a codificao dibit, so enviados dois bits por amostra. Com T1, so enviados 7 bits por perodo. As respectivas taxas de dados so 16 kbps e 56 kbps. Dez quadros. A probabilidade de algum padro aleatrio ser 0101010101 (em um canal digital) 1/1.024. Um codificador aceita um sinalanalgico arbitrrio e gera um sinal digital a partir dele. Um demodulador aceita apenas uma onda senoidal modulada e gera um sinal digital. (a) 64 kbps. (b) 32 kbps. (c) 8 kbps. O sinal deve ir de 0 at A em um quarto de onda isto , em um tempoigual a T/4. Para controlar o sinal, devemos ter 8 etapas no quarto de onda, ou

32 amostras por onda completa. O tempo por amostra 1/x, e assim o perodo total deve ser longo o suficiente para conter 32 amostras isto , T > 32/x ou max = x/32. Uma taxa de flutuao de 10-9 significa 1 segundo em 109 segundos, ou 1 nanossegundopor segundo. velocidade OC-1, digamos 50 Mbps para simplificar, um bit perdura por 20 nanossegundos. Isso significa que demora apenas 20 segundos para a flutuao do clock alcanar um bit. Em conseqncia disso, os clocks devem ser continuamente sincronizados para impedir que eles fiquem afastados demais. Com certeza a cada 10 segundos, de preferncia com freqncia muito maior. Das 90 colunas, 86 esto disponveis para dados do usurio em OC-1. Desse modo, a capacidade de usurio 86 9 = 774 bytes/quadro. Com 8 bits/byte, 8.000 quadros/s e 3 portadoras OC-1 multiplexadas em conjunto, a capacidade total de usurio 3 774 8 8.000, ou 148.608 Mbps. O VT1.5 podeacomodar 8.000 quadros/s 3 colunas 9 linhas 8 bits = 1,728 Mbps. Ele pode ser usado para acomodar DS-1. O VT2 pode acomodar 8.000 quadros/s 4 colunas 9 linhas 8

bits = 2,304 Mbps. Ele pode ser usado para acomodar o servio europeu CEPT-1. O VT6 pode acomodar 8.000 quadros/s 12 colunas 9 linhas 8 bits = 6,912 Mbps. possvelutiliz-lo para acomodar o servio DS-2.

30. 31.

32. 33.

34. 35.

36.

37.

38.


13/57

12


39.

A comutao de mensagens envia unidades de dados que podem ser arbitrariamente longa

s. A comutao de pacotes tem um tamanho mximo de pacote. Qualquer mensagem mais longa que esse tamanho mximo dividida em vrios pacotes. Os quadros OC-12c tm 12 90 = 1.080 colunas de 9 linhas. Dessas, 12 3 = 36 colunas so ocupadas pelo overhead de linha e seo. Isso deixa uma SPE de 1.044 colunas. Uma coluna SPE ocupada por overhead de caminho, restando 1.043 colunas para dados do usurio. Tendo em vista que cada coluna contm 9 bytes de 8 bits, um quadro de OC-12c contm 75.096 bits de dadosdo usurio. Com 8.000 quadros/s, a taxa de dados do usurio 600,768 Mbps. As trs redes tm as seguintes propriedades: Estrela: Melhor caso = 2, caso mdio = 2, pior caso= 2 Anel: Melhor caso = 1, caso mdio = n/4, pior caso = n/2 Interconexo total: Melhor caso = 1, caso mdio = 1, pior caso = 1

40.

41.

42.

Com a comutao de circuitos, em t = s, o circuito configurado; em t = s + x/b, o ltimo bit enviado; em t = s + x/b + kd, a mensagem chega. Com a comutao de pacotes, oltimo bit enviado em t = x/b. Para obter o destino final, o ltimo pacote deve serretransmitido k 1 vezes pelos roteadores intermedirios, cada retransmisso demorando p/b segundos; assim, o retardo total x/b + (k 1)p/b + kd. A comutao de pacotes mais rpida se s > (k 1)p/b. O nmero total de pacotes necessrios x/p, e assim o trfo total de dados + cabealho (p + h)x/p bits. A origem exige (p + h)x/pb segundospara transmitir esses bits. As retransmisses do ltimo pacote pelos roteadores inte

rmedirios demora um tempo total de (k 1)(p + h)/b segundos. Acrescentando o tempopara a origem enviar todos os bits, mais o tempo para os roteadores transportarem o ltimo pacote at o destino, limpando assim o pipeline, obtemos um tempo totalde (p + h)x/pb + (p + h)(k 1)/b segundos. Minimizando essa quantidade em relao a p, encontramos p = hx / (k 1). Cada clula tem seis vizinhas. Se a clula central utilizar o grupo de freqncias A, suas seis vizinhas podero usar B, C, B, C, B e C, respectivamente. Em outras palavras, so necessrias apenas trs clulas exclusivas. Conseqentemente, cada clula pode ter 280 freqncias. Primeiro, o desenvolvimento inicial simplesmente colocava clulas em regies em que havia alta densidade de populao humana ou de veculos. Uma vez posicionadas, o operador com freqncia no queria ter o traba-

43.

44.

45.


14/57


13

lho de mov-las. Em segundo lugar, em geral as antenas so colocadas em edifcios ou montanhas. Dependendo da posio exata de tais estruturas, a rea coberta por uma clulapode ser irregular devido a obstculos prximos ao transmissor. Em terceiro, algumas

comunidades ou donos de propriedades no permitem a montagem de uma torre no local em que est o centro de uma clula. Em tais casos, antenas direcionais so colocadasem uma posio que no corresponde ao centro da clula. 46. Se considerarmos que cada microclula um crculo com 100 m de dimetro, ento cada clula ter uma rea de 2.500p.armos a rea de San Francisco, 1,2 108 m2, e a dividirmos pela rea de uma microclula, obteremos 15.279 microclulas. claro que impossvel preencher o plano com crculos lado a lado (e San Francisco decididamente tridimensional), mas com 20.000 microclulas talvez pudssemos fazer o trabalho. As freqncias no podem ser reutilizadas em clulas adjacentes; assim, quando um usurio se desloca de uma clula para outra, uma nova freqncia deve ser alocada para a chamada. Se um usurio se mover para uma clula cujas freqncias esto todas em uso atualmente, a chamada do usurio ter de ser encerrada.Ele no causado diretamente pela necessidade de compatibilidade com verses anterio

res. O canal de 30 kHz era de fato um requisito, mas os projetistas do D-AMPS noeram obrigados a colocar trs usurios nele. Eles podiam ter colocado dois usurios emcada canal, aumentando a carga til antes da correo de erros de 260 50 = 13 kbps para 260 75 = 19,5 kbps. Desse modo, a perda de qualidade foi um compromisso intencional para colocar mais usurios por clula e, portanto, perde o sentido com clulasmaiores. O D-AMPS utiliza 832 canais (em cada sentido) com trs usurios compartilhando um nico canal. Isso permite ao D-AMPS admitir at 2.496 usurios por clula simultaneamente. O GSM utiliza 124 canais com oito usurios compartilhando um nico canal.Isso permite que ao GSM dar suporte a at 992 usurios ao mesmo tempo. Ambos os sistemas utilizam quase a mesma poro do espectro (25 MHz em cada sentido). O D-AMPS utiliza 30 kHz 892 = 26,76 MHz. O GSM usa 200 kHz 124 = 24,80 MHz. A diferena podeser atribuda principalmente melhor qualidade de voz oferecida pelo GSM (13 Kbps por usurio) em relao ao D-AMPS (8 Kbps por usurio). O resultado obtido pela negao d

da um dos valores A, B e C, e depois somando-se as trs seqncias de chips. Como outra alternativa, as trs seqncias podem ser somadas e depois negadas. O resultado (+3+1 +1 1 3 1 1 +1).

47.

48.

49.

50.


15/57

14


51.

Por definio: S T

1 m S i Ti m i =1

Se T tende a 0 bit em vez de 1 bit, sua seqncia de chip negada, com o i-simo elemento transformando-se em Ti. Desse modo: S T

52. 1 m 1 m S i ( Ti ) = S i Ti = 0 m i=1 m i =1

Quando dois elementos coincidem, seu produto + 1. Quando eles no coincidem, seu p

roduto 1. Para obter a soma 0, deve haver uma quantidade de coincidncias igual aonmero de no coincidncias. Desse modo, duas seqncias de chips so ortogonais se exatamte metade dos elementos correspondentes coincide e exatamente metade no coincide.Basta calcular os quatro produtos internos normalizados: (1 +1 3 +1 1 1 +3 +1) (1+1 +1 1 +1 +1)/8 = 1 (1 +1 3 +1 1 1 +3 +1) (1 1 +1 1 +1 +1 +1 1)/8 = 1 (1 +1+1 1 +1 +1 +1 1 1)/8 = 0 (1 +1 3 +1 1 1 +3 +1) (1 +1 1 1 1 1 +1 1)/8 = 1 OD enviaram bits 1, B enviou um bit 0 e C se manteve em silncio.

53.

54.

Ignorando-se a compactao de voz, um telefone digital PCM precisa de 64 kbps. Se di

vidirmos 10 Gbps por 64 kbps, obtermos 156.250 casas por cabo. Os sistemas atuais tm centenas das casas por cabo. Ambos. Cada um dos 100 canais recebe a atribuio de sua prpria faixa de freqncia (FDM) e, em cada canal, os dois fluxos lgicos so entremeados pelo TDM. Esse exemplo igual ao exemplo de rdio AM dado no texto, mas nenhum deles um exemplo fantstico de TDM, porque a alternncia irregular. Uma garantiade largura de banda downstream de 2 Mbps para cada casa implica no mximo 50 casaspor cabo coaxial. Desse modo, a empresa de transmisso por cabo precisar dividir ocabo existente em 100 cabos coaxiais e conectar cada um deles diretamente a umn de fibra. A largura de banda upstream 37 MHz. Usando QPSK com 2 bits/Hz, obtemos 74 Mbps upstream. Temos 200 MHz downstream. Usando-se QAM-64, isso equivale a1.200 Mbps. Utilizando-se QAM-256, isso igual a 1.600 Mbps.

55.

56.

57.


16/57


15

58.

Ainda que o canal downstream funcione a 27 Mbps, a interface do usurio quase semp

re Ethernet de 10 Mbps. No existe nenhum meio de enviar bits ao computador com velocidade maior que 10 Mbps sob essas circunstncias. Se a conexo entre o PC e o modem a cabo for Ethernet rpida, o total de 27 Mbps poder estar disponvel. Em geral, as operadoras de cabo especificam Ethernet de 10 Mbps, porque no querem que um nicousurio fique com toda a largura de banda.

SOLUES DOS PROBLEMAS DO CAPTULO 31. Tendo em vista que cada quadro tem uma chance de 0,8 de chegar, a chance da mensagem inteira chegar 0,810, que cerca de 0,107. Chame esse valor de p. O nmeroesperado de transmisses para uma mensagem inteira ento: E=

ip (1 p)

i =1

i 1

=p

i =1

i (1 p)

i 1

Para reduzir isso, use a conhecida frmula da soma de uma srie geomtrica infinita: S=

1= 1

a

i

=

1 1a

Diferencie ambos o lados em relao a a para obter: S =

iai =1

i 1

=

1 (1 a )2

Agora use a = 1 p para obter E = 1/p. Desse modo, isso ocupa em mdia 1/0,107, ou


17/57

cerca de 9,3 transmisses. 2. A soluo : (a) 00000100 01000111 11100011 11100000 01111110 (b) 01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110(c) 01111110 01000111 110100011 111000000 011111010 01111110 3. 4. Aps a insero, obtemos: A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D. Se voc sempre pudesse contar com uma srie infinita de quadros, um byte de flag poderia ser suficiente. Porm, o que aconteceria se um quadro terminasse (com um byte de flag) e no houvesse nenhumnovo quadro du-


18/57

16


rante 15 minutos? Como o receptor saber que o prximo byte na realidade o incio de um novo quadro e no apenas rudo na linha? O protocolo muito mais simples com bytesde flag iniciais e finais. 5. 6. A sada 011110111110011111010. possvel. Suponha qu

e o texto original contenha a seqncia de bits 01111110 como dados. Depois da inserode bits, essa seqncia ser representada por 011111010. Se o segundo 0 se perder devido a um erro de transmisso, a seqncia recebida ser 01111110, que o receptor v como umfim de quadro. Em seguida, ele observa imediatamente antes do fim do quadro a soma de verificao e a confirma. Se a soma de verificao 16 bits, existe uma chance em216 de que ela esteja acidentalmente correta, levando aceitao de um quadro incorreto. Quanto mais longa a soma de verificao, menor a probabilidade de um erro no serdetectado, mas a probabilidade nunca zero. Se o retardo de propagao muito longo, como no caso de uma sonda para Marte ou Vnus, a correo antecipada de erros indicada.Alm disso, ela tambm apropriada em uma instalao militar na qual o receptor no querevelar sua posio transmitindo. Se a taxa de erros for baixa o suficiente para queum cdigo de correo de erros seja bom o bastante, ele tambm poder ser mais simples. Po

r fim, os sistemas de tempo real no podem tolerar a espera por retransmisses. Umamudana em qualquer caractere vlido no pode gerar outro caractere vlido, devido natureza dos bits de paridade. Efetuar duas mudanas em bits pares ou duas mudanas em bits mpares resultar em outro caractere vlido, e assim a distncia 2. Os bits de paridade so necessrios nas posies 1, 2, 4, 8 e 16, de forma que as mensagens que no se estendem alm do bit 31 (incluindo os bits de paridade) se adaptam. Desse modo, cincobits de paridade so suficientes. O padro de bits transmitido 011010110011001110101. O valor codificado 101001001111. Se numerarmos os bits da esquerda para a direita comeando no bit 1, o bit 2 desse exemplo (um bit de paridade) ser incorreto. Ovalor de 12 bits transmitido (aps a codificao de Hamming) foi 0xA4F. O valor de dados de 8 bits original foi 0xAF. Um nico erro tornar erradas ambas as verificaes deparidade, horizontal e vertical. Dois erros tambm sero detectados com facilidade.Se eles estiverem em linhas diferentes, a paridade de linha os detectar. Se estiv

erem na mesma linha, a paridade de coluna ir capt-los. Trs erros podero

7.

8.

9.

10. 11.

12.


19/57


17

passar despercebidos, por exemplo, se algum bit for invertido juntamente com seus bits de paridade de linha e coluna. Nem mesmo o bit do canto ir captar isso. 13. Descreva um padro de erro como uma matriz de n linhas por k colunas. Cada um do

s bits corretos 0 e cada um dos bits incorretos 1. Com quatro erros por bloco, cada bloco ter exatamente quatro valores 1. Quantos desses blocos existem? H nk maneiras de escolher onde colocar o primeiro bit 1, nk 1 modos de escolher o segundo e assim por diante, at o nmero de blocos ser nk(nk-1)(nk-2)(nk-3). Erros no detectados s ocorrem quando os quatro bits 1 esto nos vrtices de um retngulo. Usando-se coordenadas cartesianas, todo bit 1 est em uma coordenada (x, y), onde 0 x < k e 0 y < n. Suponha que o bit mais prximo origem (o vrtice inferior esquerdo) esteja em (p, q). O nmero de retngulos vlidos (k p 1)(n q 1). Ento, o nmero total dpode ser encontrado fazendo-se o somatrio dessa frmula para todos os valores p eq possveis. A probabilidade de um erro no detectado ento o nmero de tais retngulosvidido pelo nmero de maneiras de distribuir os quatro bits:k 2 n 2

p =0q =0

(k p 1)(n 1 1)

nk(nk 1)(nk 2)(nk 3) 14. 15. O resto x2 + x + 1. O quadro 10011101. O gerador 01. A mensagem depois de acrescentar trs zeros 10011101000. O resto da diviso de 10011101000 por 1001 100. Assim, o string de bits real transmitido 10011101100. Ofluxo de bits recebido com um erro no terceiro bit a partir da esquerda 10111101100. A diviso desse valor por 1001 produz o resto 100, que diferente de zero. Desse modo, o receptor detecta o erro e pode solicitar uma retransmisso. O CRC calculado durante a transmisso e acrescentado ao fluxo de sada to logo o ltimo bit sai para o fio. Se o CRC estivesse no cabealho, seria necessrio fazer uma passagem sobr

e o quadro para calcular o CRC antes da transmisso. Isso exigiria que cada byte fosse tratado duas vezes uma vez para o clculo da soma de verificao e uma para transmisso. O uso do final (trailer) reduz o trabalho metade. A eficincia ser 50% quandoo tempo para transmitir o quadro for igual ao retardo de propagao de ida e volta.A uma taxa de transmisso de 4 bits/ms, a transmisso de 160 bits demora 40 ms. Para tamanhos de quadros 17 acima de 160 bits, o mtodo de parar e esperar tem uma eficincia razovel.

16.

17.


20/57

18


18.

Para operar de modo eficiente, o espao da seqncia (na realidade, o tamanho da janel

a de envio) deve ser grande o bastante para permitir ao transmissor continuar transmitindo at receber a primeira confirmao. O tempo de propagao 18 ms. velocidadeque equivale a 1,536 Mbps (excluindo-se o bit 1 do cabealho), um quadro de 64 bytes demora 0,300 ms. Portanto, o primeiro quadro chega totalmente 18,3 ms depoisde sua transmisso ter se iniciado. A confirmao demora outros 18 ms para voltar, mais um pequeno tempo (desprezvel) para a confirmao chegar por completo. No total, esse tempo de 36,3 ms. O transmissor dever ter espao de janela suficiente para continuar por 36,3 ms. Um quadro demora 0,3 ms, e assim sero necessrios 121 quadros para preencher o canal. Ser preciso usar sete nmeros de seqncias de bits. Pode acontecer. Suponha que o transmissor envie um quadro e que uma confirmao adulterada volterapidamente. O loop principal ser executado uma segunda vez e um quadro ser enviado enquanto o timer ainda estiver executando. Seja a janela do transmissor (Sl, S

u) e a do receptor (Rl, Ru). Seja W o tamanho da janela. As relaes que devem ser vlidas so: 0 Su Sl + 1 W1 Ru Rl + 1 = W S l Rl Su + 1

19.

20.

21.

O protocolo seria incorreto. Suponha que estejam em uso nmeros de seqncia de 3 bits. Considere o seguinte cenrio: A acaba de enviar o quadro 7. B recebe o quadro eenvia um ACK de piggyback. A recebe o ACK e envia os quadros de 0 a 6, e todos eles so perdidos. B chega ao tempo limite (timeout) e retransmite seu quadro atual

, com o ACK 7. Observe a situao em A quando chega o quadro com r.ack = 7. As variveis-chave so AckExpected = 0, r.ack = 7 e NextFrameToSend = 7. O between modificado retornaria true, fazendo A imaginar que os quadros perdidos estavam sendo confirmados.

22.

Sim. Ela poderia levar a um impasse. Suponha que um lote de quadros chegasse corretamente e fosse aceito. Ento, o receptor avanaria sua janela. Agora, suponha quetodas as confirmaes se perdessem. O transmissor eventualmente chegaria ao tempo limite e enviaria o primeiro quadro de novo. O receptor enviaria um NAK. Suponhaque ele se perdesse. Desse ponto em diante, o transmissor continuaria a entrar no tempo limite e a enviar um quadro que j havia sido aceito, mas o receptor simplesmente o ig-


21/57


19

noraria. A definio do timer auxiliar resulta, em vez disso, no envio de uma confirmao correta, o que resultaria na ressincronizao. 23. Ele levaria ao impasse (deadlock), porque esse o nico lugar em que so processadas as confirmaes que chegam. Sem ess

e cdigo, o transmissor continuaria em timeout e nunca faria nenhum progresso. Anularia o propsito de se ter NAKs, de forma que teramos de recorrer a timeouts. Embora o desempenho se degradasse, a correo no seria afetada. Os NAKs no so essenciais. Considere o seguinte cenrio. A envia 0 a B. B o recebe e envia um ACK, mas o ACK perdido. A chega ao tempo limite e repete 0, mas agora B espera 1, e assim enviaum NAK. Se A simplesmente reenviasse r.ack+1, ele estaria enviando o quadro 1, que ainda no recebeu. No. O tamanho mximo da janela de recepo 1. Suponha que fosse 2Inicialmente, o transmissor envia quadros de 0 a 6. Todos os valores so recebidose confirmados, mas a confirmao perdida. O receptor agora est preparado para aceitar 7 e 0. Quando a retransmisso de 0 chegar ao receptor, ela ser bufferizada e 6 ser confirmado. Quando 7 chegar, 7 e 0 sero repassados ao host, levando a uma falhade protocolo. Suponha que A enviasse a B um quadro e este chegasse corretamente,

mas que no houvesse nenhum trfego no sentido inverso. Depois de algum tempo, A chegaria ao tempo limite e retransmitiria. B notaria que o nmero de seqncia estava incorreto, pois o nmero de seqncia est abaixo de FrameExpected. Conseqentemente, ele enviaria um NAK, que transportaria um nmero de confirmao. Cada quadro seria ento enviado exatamente duas vezes. No. Essa implementao falha. Com MaxSeq = 4, obtemos NrBufs = 2. Os nmeros de seqncia pares usam o buffer 0 e os nmeros de seqncia mpares usabuffer 1. Esse mapeamento significa que os quadros 4 e 0 utilizam ambos o mesmobuffer. Suponha que os quadros 0 a 3 fossem recebidos e confirmados. Agora, a janela do receptor contm 4 e 0. Se 4 for perdido e 0 chegar, ele ser inserido no buffer 0 e arrived[0] ser definido como true. O loop no cdigo de FrameArrival ser executado uma vez, e uma mensagem fora de ordem ser entregue ao host. Esse protocoloexige que MaxSeq seja mpar para funcionar corretamente. Porm, outras implementaes deprotocolos de janelas deslizantes no tm todas essa propriedade. Seja t = 0 o incio

da transmisso. Em t = 1 ms, o primeiro quadro totalmente transmitido. Em t = 271ms, o primeiro quadro chega por completo. Em t = 272 ms, o quadro que confirmao primeiro completamente enviado. Em t = 542 ms, o quadro que conduz a confirmao chega por intei-

24.

25.

26.

27.

28.

29.


22/57

20


ro. Desse modo, o ciclo tem 542 ms. Ao todo, k quadros so enviados em 542 ms, o que d uma eficincia de k/542. Conseqentemente: (a) k = 1, eficincia = 1/542 = 0,18%.(b) k = 7, eficincia = 7/542 = 1,29%. (c) k = 4, eficincia = 4/542 = 0,74%. 30. Co

m um canal de 50 kbps e oito nmeros de seqncia de bits, o canal est sempre cheio. Onmero de retransmisses por quadro cerca de 0,01. Cada quadro de boa qualidade desperdia 40 bits de cabealho, mais 1% de 4.000 bits (retransmisso), mais um NAK de 40bits uma vez a cada 100 quadros. O overhead total 80,4 bits por 3.960 bits de dados, o que corresponde a uma frao 80,4/(3.960 + 80,4) = 1,99%. A transmisso comea emt = 0. Em t = 4.096/64.000 s = 64 ms, o ltimo bit enviado. Em t = 334 ms, o ltimobit chega ao satlite e o ACK muito breve enviado. Em t = 604 ms, o ACK chega aosolo. Aqui, a taxa de dados 4.096 bits em 604 ms, ou cerca de 6.781 bps. Com umtamanho de janela de 7 quadros, o tempo de transmisso 448 ms para a janela completa, e nesse tempo o transmissor tem de parar. Em 604 ms, o primeiro ACK chega eo ciclo pode recomear. Nesse caso, temos 7 4.096 = 28.672 bits em 604 ms. A taxade dados 47.470,2 bps. A transmisso contnua s pode ocorrer se o transmissor ainda e

stiver enviando quando o primeiro ACK voltar, no tempo t = 604 ms. Em outras palavras, se o tamanho da janela for maior que 604 ms de transmisso, ele poder funcionar a toda velocidade. Para um tamanho de janela igual a 10 ou maior, essa condio satisfeita; assim, para qualquer janela de tamanho 10 ou maior (por exemplo, 15ou 127), a taxa de dados 64 kbps. A velocidade de propagao no cabo 200.000 km/s, ou 200 km/ms, e assim um cabo de 100 km ser preenchido em 500 ms. Cada quadro T1 equivale a 193 bits enviados em 125 ms. Isso corresponde a quatro quadros, ou 772bits no cabo. Cada mquina tem duas variveis importantes: next_frame_to_send e frame_expected, cada uma das quais pode assumir os valores 0 ou 1. Desse modo, cadamquina pode estar em um entre quatro estados possveis. Uma mensagem no canal contmo nmero de seqncia do quadro que est sendo enviado e o nmero de seqncia do quadroest sendo confirmado por ACK. Desse modo, existem quatro tipos de mensagens. O canal pode conter a mensagem 0 ou 1 em qualquer sentido. Portanto, o nmero de estad

os em que o canal pode estar 1 com zero mensagens, 8 com uma mensagem e 16 com duas mensagens (uma mensagem em cada sentido). No total existem 1 + 8 + 16 = 25 estados possveis do canal. Isso implica 4 4 25 = 400 estados possveis para o sistema completo.

31.

32.

33.


23/57


21

34.

A seqncia de disparo 10, 6, 2, 8. Ela corresponde aceitao de um quadro par, perd

confirmao, ao timeout pelo transmissor e regenerao da confirmao pelo receptor. Ade Petri e grafo do estado so:

35.

A

D

1 C

3

BD

ACD BE

AE

2

4

O sistema modelado de excluso mtua. B e E so sees crticas que no podem estar ativ

mesmo tempo, isto , o estado BE no permitido. A posio C representa um semforo que pe ser ocupado por qualquer A ou D, mas no por ambos ao mesmo tempo. 36. O PPP foiclaramente projetado para ser implementado em software e no em hardware, como oHDLC quase sempre . Com uma implementao de software, funcionar inteiramente com bytes muito mais simples que trabalhar com bits individuais. Alm disso, o PPP foi criado para ser usado com modems, e os modems aceitam e transmitem dados em unidades mltiplas de 1 byte, e no de 1 bit. No mnimo, cada quadro tem dois bytes de flag(sinalizao), um byte de protocolo e dois bytes de total de verificao, dando um totalde cinco bytes de overhead por quadro.

37.


24/57

22


SOLUES DOS PROBLEMAS DO CAPTULO 41. A frmula a frmula padro para o enfileiramento de Markov, dada na Seo 4.1.1, ou sa, T = 1(mC l). Nesse caso, C = 108 e m = 10-4, e portanto T = 1/(1.000 lambda)

s. Para as trs taxas de chegada, obtemos (a) 0,1 ms, (b) 0,11 ms, (c) 1 ms. No caso (c), estamos operando um sistema de enfileiramento com r = l/mC = 0,9, que corresponde ao retardo de 10. Com o ALOHA puro, a largura de banda utilizvel 0,184 56 kbps = 10,3 kbps. Cada estao requer 10 bps; assim, N = 10.300/10 = 1.030 estaes. Com o ALOHA puro, a transmisso pode comear instantaneamente. Com baixa carga, no esperada nenhuma coliso, e assim a transmisso provavelmente ser bem-sucedida. Com o slotted ALOHA, ela tem de esperar pelo prximo slot. Isso introduz um tempo de retardo igual metade de um slot. Cada terminal faz uma solicitao a cada 200 segundos, oque corresponde a uma carga total de 50 solicitaes/s. Conseqentemente, G = 50/8.000 = 1/160. (a) Com G = 2, a lei de Poisson fornece uma probabilidade igual a e-2. (b)(1 e-G)ke-G = 0,135 0,865k. (c) O nmero esperado de transmisses eG = 7,4. (a)Mais uma vez a partir da lei de Poisson, P0 = e-G, e assim G = lnP0 = ln 0,1 = 2,

3. (b) Usando S = Ge-G com G = 2,3 e e-G = 0,1, S = 0,23. (c) Sempre que G > 1,o canal fica sobrecarregado; portanto, ele est sobrecarregado. O nmero de transmisses E = eG. Os E eventos esto separados por E 1 intervalos de quatro slots cada; assim, o retardo 4(eG 1). O throughput dado por S = GeG. Desse modo, temos duas equaes paramtricas, uma para retardo e uma para throughput, ambas em termos de G. Para cada valor de G, possvel encontrar o retardo e o throughput correspondentes, gerando um nico ponto na curva. (a) O pior caso : Todas as estaes querem enviar e s aestao de nmero mais baixo. O tempo de espera N perodos de disputa de bits + (N 1)bit para transmisso de quadros. O total N + (N 1)d tempos de bits. (b) O pior caso : Todas as estaes tm quadros a transmitir e s tem o nmero de estao virtual mais b. Conseqentemente, s ter sua vez de transmitir depois que as outras N 1 estaes tiverem transmitido um quadro cada uma, e depois de N perodos de disputa de tamanho log2 N cada. O tempo de espera portanto (N 1) d + N log2 bits.

2. 3.

4.

5.

6.

7.

8.


25/57


23

9.

Quando a estao 4 envia, ela se torna 0, e 1, 2 e 3 so aumentados em 1. Quando a est

ao 3 envia, ela se torna 0, e 0, 1 e 2 so aumentados em 1. Finalmente, quando a estao 9 envia, ela se torna 0 e todas as outras estaes so incrementadas em 1. O resultado 9, 1, 2, 6, 4, 8, 5, 7, 0 e 3. As estaes 2, 3, 5, 7, 11 e 13 querem enviar. So necessrios onze slots, sendo o contedo de cada slot: slot 1: 2, 3, 5, 7, 11, 13 slot2: 2, 3, 5, 7 slot 3: 2, 3 slot 4: 2 slot 5: 3 slot 6: 5, 7 slot 7: 5 slot 8: 7slot 9: 11, 13 slot 10: 11 slot 11: 13

10.

11.

O nmero de slots necessrios depende da distncia que se deve percorrer de volta na rv

ore at encontrar um ancestral comum das duas estaes. Se eles tm o mesmo pai (isto , um nvel de volta), o que acontece com probabilidade 2n, a demora de 2n + 1 slots para percorrer a rvore. Se as estaes tm um av comum, o que acontece com probabilidade 2+ 1, o percurso na rvore demora 2n 1 slots etc. O pior caso 2n + 1 (pai comum),e o melhor caso o de trs slots (estaes em metades diferentes da rvore). A mdia m por: m=n 1 i =0

2

( n i )

( 2n + 1 2i )

Essa expresso pode ser simplificada para: m = (1 2n)(2n + 1) 2(n 1) 12.

n 1 i =0

i2

i

Os rdios no podem receber e transmitir na mesma freqncia ao mesmo tempo, e assim o CSMA/CD no pode ser usado. Se esse problema pudesse ser resolvido (por exemplo, equipando-se cada estao com dois rdios), ainda haveria o problema de nem todas as estaes estarem dentro do alcance de rdio de cada uma das outras. Somente se ambos os problemas puderem ser resolvidos, o CSMA/CD ser um candidato. Ambos utilizam uma combinao de FDM e TDM. Nos dois casos, esto disponveis bandas de freqncias dedicadassto , comprimentos de onda), e nos dois casos essas bandas so dotadas de slots para TDM.

13.


26/57

24


14.

Sim. Imagine que elas estejam em linha reta e que cada estao possa acessar apenas

suas vizinhas mais prximas. Ento A pode transmitir para B enquanto E est transmitindo para F. (a) Numere os andares de 1 a 7. Na configurao de estrela, o roteador est no quarto andar. So necessrios cabos para cada um dos 7 15 1 = 104 locais. O comprimento total desses cabos : 4

15.

7 15

i =1 j =1

(i 4)2 + ( j 8)2O comprimento total aproximadamente 1.832 metros. (b) Para 802.3, so necessrios 7cabos horizontais de 56 metros, mais um cabo vertical de 24 metros de comprimento, correspondendo ao total de 416 m. 16. A Ethernet utiliza a codificao Manchester, o que significa que ela tem dois perodos de sinal por bit enviado. A taxa de dados do padro Ethernet 10 Mbps, e assim a taxa de bauds duas vezes esse valor, ou20 megabauds. O sinal uma onda quadrada com dois valores, alto (H) e baixo (L).O padro LHLHLHHLHLHLLHHLLHHL. Dessa vez, o padro HLHLHLLHHLLHLHHLHLLH. O tempo depropagao de ida e volta do cabo 10 ms. Uma transmisso completa tem seis fases: O transmissor ocupa o cabo (10 ms). Transmisso de dados (25,6 ms). Retardo para o ltimo bit chegar ao fim (5,0 ms). O receptor ocupa o cabo (10 ms). Confirmao enviada (3,2 ms). Retardo para o ltimo bit chegar ao fim (5,0 ms). A soma desses valores 5

8,8 ms. Nesse perodo, so enviados 224 bits de dados, o que corresponde taxa de 3,8Mbps. 20. Numere as tentativas de aquisio a partir de 1. A tentativa i distribudaentre 2i-1 slots. Desse modo, a probabilidade de uma coliso na tentativa i 2-(i-1). A probabilidade de as primeiras k 1 tentativas falharem, seguidas por um sucesso na rodada k, : p k = (1 2( k 1) )

17. 18. 19.

2k i =1

( i 1)


27/57


25

Que pode ser simplificada para: Pk = (1 2(k 1)) 2(k 1)(k 2) O nmero esperado deadas ento apenas kPk. 21. Para um cabo de 1 km, o tempo de propagao em um sentido ms, e assim 2t = 10 ms. Para fazer CSMA/CD funcionar, tem de ser impossvel transm

itir um quadro inteiro nesse intervalo. A 1 Gbps, todos os quadros menores que 10.000 bits podem ser completamente transmitidos em um tempo abaixo de 10 ms, e portanto o quadro mnimo de 10.000 bits ou 1.250 bytes. O quadro Ethernet mnimo tem64 bytes, incluindo ambos os endereos no cabealho de quadro Ethernet, o campo de tipo/comprimento e o total de verificao. Tendo em vista que os campos de cabealho ocupam 18 bytes e o pacote tem 60 bytes, o tamanho total do quadro 78 bytes, que excede o mnimo de 64 bytes. Portanto, no utilizada nenhuma insero. O comprimento mxide cabo no Fast Ethernet 1/10 do comprimento na Ethernet. A carga til de 1.500 bytes mas, quando os campos de endereo de destino, endereo de origem, tipo/comprimento e total de verificao tambm so considerados, o total na verdade 1.518. A codificatem apenas 80% de eficincia. Ela utiliza 10 bits de dados transmitidos para representar 8 bits de dados reais. Em um segundo, so transmitidos 1.250 megabits, o qu

e significa 125 milhes de palavras de cdigo. Cada palavra de cdigo representa 8 bits de dados, e ento a taxa de dados verdadeira de fato 1.000 megabits/s. O menor quadro Ethernet tem 512 bits; assim, a 1 Gbps, obtemos 1.953.125 ou quase 2 milhesde quadros/s. Porm, isso s funciona quando a rajada de quadros est operando. Sem arajada de quadros, os quadros curtos so preenchidos por insero at 4.096 bits e, nesse caso, o nmero mximo 244.140. Para o maior quadro (12.144 bits), pode haver at 82.345 quadros/s. A Ethernet de gigabit tem esse recurso, bem como o 802.16. Ele til para aumentar a eficincia de largura de banda (um nico prembulo etc.), mas tambm quando existe um limite mais baixo sobre o tamanho dos quadros. A estao C a mais prxima de A, pois ouviu o RTS e respondeu a ele afirmando seu sinal NAV. D no respondeu, e portanto deve estar fora do alcance de rdio de A.

22.

23. 24.

25.

26.

27.

28.


28/57

26


29.

Um quadro contm 512 bits. A taxa de erros de bits p = 10-7. A probabilidade de to

dos os 512 bits sobreviverem corretamente (1 p)512, que equivale a cerca de 0,9999488. A frao danificada ento cerca de 5 10-5. O nmero de quadros/s 11 106/512roximadamente 21.484. Multiplicando esses dois nmeros, obtemos quase um quadro danificado por segundo. Depende da distncia em que se encontra o assinante. Se o assinante estiver perto, o QAM-64 ser usado para 120 Mbps. Em distncias mdias, o QAM-16 usado para 80 Mbps. No caso de estaes distantes, o QPSK ser usado para 40 Mbps.O vdeo no-compactado tem uma taxa de bits constante. Cada quadro tem o mesmo nmerode pixels que o quadro anterior. Desse modo, possvel calcular com muita preciso aquantidade de largura de banda que ser necessria e quando. Conseqentemente, o serviode taxa de bits constante a melhor opo. Uma razo a necessidade de qualidade de servio em tempo real. Se for descoberto um erro, no haver tempo para uma retransmisso.O espetculo tem de continuar. A correo de erros direta pode ser usada nesse caso. O

utra razo que, em linhas de qualidade muito baixa (por exemplo, canais sem fios),a taxa de erros pode ser to alta que praticamente todos os quadros teriam de serretransmitidos, e seria bem provvel que a retransmisso tambm estivesse danificada.Para evitar isso, usada a correo antecipada de erros, a fim de aumentar a frao de quadros que chegam corretamente. impossvel um dispositivo ser mestre em duas piconets ao mesmo tempo. H dois problemas. Primeiro, s esto disponveis 3 bits de endereo no cabealho, enquanto at sete escravos poderiam estar em cada piconet. Desse modo,no haveria nenhum meio de enderear de forma exclusiva cada escravo. Em segundo lugar, o cdigo de acesso no comeo do quadro derivado da identidade do mestre. Essa amaneira como os escravos sabem que mensagem pertence a cada piconet. Se duas piconets superpostas usassem o mesmo cdigo de acesso, no haveria como saber qual quadro pertenceria a cada piconet. Na realidade, as duas piconets estariam fundidasem uma nica piconet grande, e no em duas piconets separadas. O Bluetooth utiliza F

HSS, da mesma forma que o 802.11. A maior diferena que o Bluetooth salta a uma taxa de 1.600 hops/s, bem mais rpido que o 802.11. Um canal ACL assncrono, com os quadros chegando irregularmente medida que os dados so produzidos. Um canal SCO sncrono, com quadros chegando periodicamente a uma taxa bem definida.

30.

31.

32.

33.

34.

35.


29/57


27

36.

No. O tempo de parada no 802.11 no padronizado, e assim ele tem de ser anunciado s

novas estaes que chegam. No Bluetooth, esse tempo sempre 625 ms. No h necessidade deanunci-lo. Todos os dispositivos Bluetooth tm esse valor codificado no chip. O Bluetooth foi projetado para ser econmico, e a fixao da taxa de hops e do tempo de parada leva a um chip mais simples. O primeiro quadro ser encaminhado por cada ponte. Aps essa transmisso, cada ponte ter uma entrada para o destino a com a porta apropriada em sua tabela de hash. Por exemplo, a tabela de hash de D ter agora uma entrada para quadros diretos destinados a a na LAN 2. A segunda mensagem ser vistapelas pontes B, D e A. Essas pontes acrescentaro uma nova entrada em suas tabelas de hash para quadros destinados a c. Por exemplo, a tabela de hash da ponte Dter agora outra entrada para quadros diretos destinados a c na LAN 2. A terceiramensagem ser vista pelas pontes H, D, A e B. Essas pontes acrescentaro uma nova entrada em suas tabelas de hash para quadros destinados a d. A quinta mensagem ser

vista pelas pontes E, C, B, D e A. As pontes E e C acrescentaro uma nova entradaem suas tabelas de hash para quadros destinados a d, enquanto as pontes D, B e Aatualizaro as entradas de suas tabelas de hash para o destino d. A pontes G, I eJ no so usadas para encaminhar quaisquer quadros. A principal razo para termos loops em uma LAN estendida o aumento da confiabilidade. Se qualquer ponte na rvore atual falhar, o algoritmo (dinmico) de rvore de amplitude ir reconfigurar a rvore, formando uma nova rvore que poder incluir uma ou mais dessas pontes que no faziam parte da rvore anterior. A opo mais simples no fazer nada de especial. Todo quadro de entrada colocado no painel traseiro (backplane) e enviado placa de destino, que poderia ser a placa de origem. Nesse caso, o trfego entre placas passar pelo paineltraseiro do switch. A outra opo reconhecer esse caso e trat-lo de modo especial, enviando o quadro diretamente sem passar pelo painel traseiro. O pior caso um fluxo infinito de quadros de 64 bytes (512 bits). Se o painel traseiro puder tratar

109 bps, o nmero de quadros que ele poder manipular ser 109/512. Isso correspondea 1.953.125 quadros/s. A porta em B1 para a LAN 3 precisaria ser rotulada novamente como GW. Um switch de armazenar e encaminhar (store-and-forward) armazena cada quadro de entrada em sua totalidade, depois o examina e o encaminha. Um switch de corte (cut-through) comea a encaminhar os quadros de entrada antes que elescheguem completamente. Assim que chega o endereo de destino, o encaminhamento pode comear.

37.

38.

39.

40.

41. 42.


30/57

28


43.

Os switches de armazenar e encaminhar armazenam quadros inteiros antes de transm

iti-los. Depois que um quadro chega, o total de verificao pode ser verificado. Seo quadro estiver danificado, ele ser imediatamente descartado. No caso do corte,quadros danificados no podem ser descartados pelo switch porque, no momento em que o erro for detectado, o quadro j ter ido. Tentar lidar com o problema como trancar a porta da cocheira depois que o cavalo escapou. No. Os hubs simplesmente estabelecem conexes eltricas entre todas as linhas de entrada. No existe nada para configurar. Nenhum roteamento feito em um hub. Todo quadro que entra no hub sai delepor todas as outras linhas. Funcionaria. Todos os quadros que entrassem no domnio do ncleo seriam quadros antigos; assim, caberia ao primeiro switch do ncleo a tarefa de identific-los. Isso poderia ser feito com a utilizao de endereos MAC ou endereos IP. De modo semelhante, no caminho de sada, esse switch teria de desmarcar osquadros de sada.

44.

45.

SOLUES DOS PROBLEMAS DO CAPTULO 51. Transferncia de arquivos, login remoto e vdeo por demanda necessitam de um servio orientado a conexes. Por outro lado, a verificao de cartes de crdito e outros ternais de pontos de venda, transferncia eletrnica de fundos e muitas formas de acesso a bancos de dados remotos so inerentemente sem conexes, com uma consulta indo emum sentido e a resposta voltando no outro sentido. Sim. Sinais de interrupo devemsaltar frente dos dados e serem entregues fora de seqncia. Um exemplo tpico ocorrequando um usurio de terminal acessa a tecla de encerramento (eliminao). O pacote g

erado a partir do sinal de encerramento deve ser enviado de imediato e deve saltar frente de quaisquer dados enfileirados atualmente para o programa; isto , dados j digitados mas ainda no lidos. As redes de circuitos virtuais quase certamentetm necessidade desse recurso para rotear pacotes de configurao de conexo de uma origem arbitrria at um destino arbitrrio. A negociao poderia definir o tamanho da janela,o tamanho mximo de pacote, a taxa de dados e os valores de timers. A existncia dequatro hops significa que cinco roteadores esto envolvidos. A implementao do circuito virtual exige a alocao de 5 8 = 40 bytes de memria por 1.000 segundos. A implementao de datagrama requer a

2.

3.

4. 5.


31/57


29

transmisso de 12 4 200 = 9.600 bytes de cabealho alm das necessidades de implementado circuito virtual. Portanto, a questo se reduz ao custo relativo de 40.000 bytes-segundo de memria versus 9.600 bytes-hops de capacidade do circuito. Se a memria

depreciada ao longo de 2 52 40 3.600 = 1,5 107 segundos, um byte-segundo custa6,7 10-8 centavos, e 40.000 deles custam pouco mais de 2 milsimos de centavos. Seum byte-hop custa 10-6 centavos, 9.600 deles custam 9,6 milsimos de centavos. Oscircuitos virtuais so mais econmicos para esse conjunto de parmetros. 6. Sim. Umagrande rajada de rudo poderia adulterar terrivelmente um pacote. Com um total deverificao de k bits, existe uma probabilidade de 2-k de que o erro no seja detectado. Se o campo de destino ou, de modo equivalente, o nmero do circuito virtual foralterado, o pacote ser entregue ao destino errado e aceito como genuno. Em outraspalavras, uma rajada de rudo ocasional poderia transformar um pacote perfeitamente vlido para um destino em um pacote perfeitamente vlido para outro destino. Eleseguir todas estas rotas: ABCD, ABCF, ABEF, ABEG, AGHD, AGHF, AGEB e AGEF. O nmerode hops usados 24. Escolha uma rota que use o caminho mais curto. Agora, remova

todos os arcos usados no caminho recm-encontrado e execute novamente o algoritmodo caminho mais curto. O segundo caminho ser capaz de sobreviver falha de qualquer linha no primeiro caminho e vice-versa. Contudo, concebvel que essa heurstica possa falhar ainda que existam dois caminhos disjuntos. Para resolver o problemacorretamente, deve ser usado um algoritmo de fluxo mximo. A ida por B fornece (11, 6, 14, 18, 12, 8). A ida por D fornece (19, 15, 9, 3, 9, 10). A ida por E fornece (12, 11, 8, 14, 5, 9). Tomando-se o mnimo para cada destino com exceo de C, tem-se (11, 6, 0, 3, 5, 8). As linhas de sada so (B, B, , D, E, B). 10. A tabela de roteamento tem 400 bits. Duas vezes por segundo essa tabela gravada em cada linha,e assim so necessrios 800 bps em cada linha, em cada sentido. Ele sempre mantido.Se um pacote chegou em uma linha, ele deve ser confirmado. Se nenhum pacote chegou em uma linha, ele deve ser enviado para l. Os casos 00 (no chegou e no ser enviado) e 11 (chegou e ser devolvido) so logicamente incorretos, e portanto no existem.

O mnimo ocorre em 15 agrupamentos, cada um com 16 regies e cada regio tendo 20 roteadores, ou em uma das formas equivalentes; por exem-

7. 8.

9.

11.

12.


32/57

30


plo, 20 agrupamentos com 16 regies de 15 roteadores. Em todos os casos, o tamanhoda tabela 15 + 16 + 20 = 51. 13. concebvel que ele possa entrar em modo promscuo,lendo todos os quadros colocados na LAN, mas isso muito ineficiente. Em vez dis

so, normal o agente local levar o roteador a consider-lo o host mvel, respondendoa solicitaes ARP. Quando o roteador recebe um pacote IP destinado ao host mvel, eletransmite uma consulta ARP solicitando o endereo de nvel MAC 802.3 da mquina com esse endereo IP. Quando o host mvel no est em atividade, o agente local responde ao ARP, e assim o roteador associa o endereo IP do usurio mvel ao endereo de nvel MAC 802.3 do agente local. (a) O algoritmo de encaminhamento pelo caminho inverso levacinco rodadas para terminar. Os destinatrios de pacotes nessas rodadas so AC, DFIJ, DEGHIJKN, GHKN e LMO, respectivamente. So gerados ao todo 21 pacotes. (b) A rvore de escoamento necessita de quatro rodadas e 14 pacotes. O n F tem no momento dois descendentes, A e D. Agora, ele adquire um terceiro descendente G no circulado, porque o pacote que segue IFG no est na rvore de escoamento. O n G adquire um segundo descendente, alm de D, identificado por F. Esse descendente tambm no est circula

do, pois no entra na rvore de escoamento. Existem vrias rvores de amplitude possveis.Uma delas :C B F A E K J D

14.

15.

16.

I

17. 18. 19.

Quando obtm o pacote, H o transmite. Porm, I sabe como chegar at I, e portanto no efetua a transmisso por difuso. O n H est a trs hops de B, e assim leva trs rodadas paencontrar a rota. Ele pode faz-lo de forma aproximada, mas no de forma exata. Suponha que existam 1.024 identificadores de ns. Se o n 300 estiver procurando


33/57


31

pelo n 800, talvez seja melhor percorrer o sentido horrio, mas poderia acontecer de haver 20 ns reais entre 300 e 800 no sentido horrio e apenas 16 ns reais entre eles no sentido anti-horrio. O propsito da funo de hash criptogrfico SHA-1 produzir u

distribuio muito suave, de forma que a densidade de ns seja aproximadamente a mesma ao longo de todo o crculo. Porm, sempre haver flutuaes estatsticas, e assim a escoa direta pode ser errada. 20. 21. O n na entrada 3 passa de 12 para 10. O protocolo terrvel. Seja o tempo dividido em unidades de T segundos. No slot 1, o roteador de origem envia o primeiro pacote. No incio do slot 2, o segundo roteador recebeu o pacote, mas ainda no pode confirm-lo. No comeo do slot 3, o terceiro roteadorrecebeu o pacote, mas tambm no pode confirm-lo, e assim todos os roteadores atrs dele ainda esto suspensos. A primeira confirmao s pode ser enviada quando o host de destino receber o pacote do roteador de destino. Agora, a confirmao comea a se propagar de volta. So necessrios dois perodos completos de trnsito da sub-rede, 2(n 1)T segundos, antes do roteador de origem poder enviar o segundo pacote. Desse modo, othroughput de um pacote a cada 2(n 1)T segundos. Cada pacote emitido pelo host d

e origem efetua 1, 2 ou 3 hops. A probabilidade de que o pacote efetue um hop p.A probabilidade de ele efetuar dois hops p(1 p). A probabilidade de ele efetuar3 hops (1 p)2. O comprimento do caminho mdio que um pacote pode esperar percorrer ento a soma ponderada dessas trs probabilidades, ou p2 3p + 3. Note que, para p= 0 a mdia 3 hops e, para p = 1, a mdia de 1 hop. Com 0 < p < 1, podem ser necessrias diversas transmisses. O nmero mdio de transmisses pode ser encontrado observando-se que a probabilidade de uma transmisso bem-sucedida por toda a distncia (1 p)2,que chamaremos a. O nmero esperado de transmisses :

22.

a + 2a (1 a ) + 3a (1 a )2 + ... =

1

a

=

1 (1 p)2

Finalmente, o total de hops usados (p2 3p + 3)/(1 p)2. 23. Primeiro, o mtodo de bit de advertncia envia explicitamente uma notificao de congestionamento origem peladefinio de um bit, enquanto RED notifica implicitamente a origem, apenas descartando um de seus pacotes. Em segundo lugar, o mtodo do bit de advertncia s descarta um pacote quando no existe nenhum espao restante no buffer, enquanto RED descarta pacotes antes que todo buffer esteja esgotado.


34/57

32


24.

O roteador tem de fazer aproximadamente o mesmo trabalho para enfileirar um paco

te, no importando o quanto ele seja grande. Existe pouca dvida de que processar dez pacotes de 100 bytes cada um signifique muito mais trabalho que processar um pacote de 1.000 bytes. No possvel enviar nenhum pacote maior que 1.024 bytes, de qualquer modo. Com um smbolo a cada 5 ms, podem ser enviadas 200.000 clulas/s. Cadaclula contm 48 bytes de dados ou 384 bits. A taxa de dados lquida ento 76,8 Mbps. Aresposta ingnua que, a 6 Mbps, ele leva 4/3 segundo para drenar um balde de 8 megabits. Porm, essa resposta est errada porque, durante esse intervalo, chegam maissmbolos. A resposta correta pode ser obtida usando-se a frmula S = C/(M r). Por substituio, obtemos S = 8/(6 1) ou 1,6 s. Chame o comprimento do intervalo mximo de rajada Dt. No caso extremo, o balde est cheio no incio do intervalo (1 Mbyte) e outros 10Dt Mbytes chegam durante o intervalo. A sada durante a rajada de transmissocontm 50Dt Mbytes. Igualando essas duas quantidades, temos 1 + 10Dt = 50Dt. Resol

vendo essa equao, conclumos que Dt 25 ms. As larguras de banda em MB/s so: A: 2, B:0, C: 1, E: 3, H: 3, J: 3, K: 2 e L: 1. Aqui, m 2 milhes e l 1,5 milho; assim, r =l/m igual a 0,75 e, a partir da teoria de enfileiramento, cada pacote experimenta um retardo quatro vezes maior do que teria em um sistema ocioso. O tempo em um sistema ocioso 500 ns; aqui, ele igual a 2 ms. Com 10 roteadores ao longo de um caminho, o tempo de enfileiramento somado ao tempo de servio 20 ms. No existe nenhuma garantia. Se muitos pacotes forem expedidos, seu canal talvez tenha desempenho pior que o do canal normal. Ela necessria em ambos. Mesmo em uma rede de circuitos virtuais concatenados, algumas redes ao longo do caminho poderiam aceitarpacotes de 1.024 bytes, enquanto outras s poderiam aceitar pacotes de 48 bytes.A fragmentao ainda necessria. Nenhum problema. Basta encapsular o pacote no campo de carga til de um datagrama pertencente sub-rede que est sendo percorrida e envi-lo. O datagrama IP inicial estar fragmentado em dois datagramas IP em I1. No ocorrer

nenhuma outra fragmentao. Enlace A-R1: Comprimento = 940; ID = x; DF = 0; MF = 0;Deslocamento = 0

25. 26.

27.

28.

29. 30.

31. 32.

33. 34.


35/57


33

Enlace R1-R2: (1)Comprimento = 500; ID = x; DF = 0; MF = 1; Deslocamento = 0 (2)Comprimento = 460; ID = x; DF = 0; MF = 0; Deslocamento = 60 Enlace R2-B: (1)Comprimento = 500; ID = x; DF = 0; MF = 1; Deslocamento = 0 (2) Comprimento = 460;

ID = x; DF = 0; MF = 0; Deslocamento = 60 35. Se a taxa de bits da linha b, o nmero de pacotes/s que o roteador pode emitir b/8192; assim, o nmero de segundos que ele leva para emitir um pacote 8192/b. Para transmitir 65.536 pacotes, ele demora 229/b segundos. Igualando essa expresso durao mxima de pacotes, obtemos 229/b =10. Ento, b cerca de 53.687.091 bps. Tendo em vista que a informao necessria para rear cada fragmento, a opo deve aparecer em todo fragmento. Com um prefixo de 2 bits, restariam 18 bits para indicar a rede. Conseqentemente, o nmero de redes seria218, ou 262.144. Porm, todos os valores 0 e todos os valores 1 so especiais, e assim apenas 262.142 esto disponveis. O endereo 194.47.21.130. A mscara tem 20 bits decomprimento, e assim a parte de rede tem 20 bits. Os 12 bits restantes so para ohost, e portanto existem 4.096 endereos de hosts. Para comear, todas as solicitaes soarredondadas at uma potncia de dois. O endereo inicial, o endereo final e a mscara s

dados a seguir: A: 198.16.0.0 198.16.15.255 escrito como 198.16.0.0/20 B: 198.16.16.0 198.23.15.255 escrito como 198.16.16.0/21 C: 198.16.32.0 198.47.15.255 escrito como 198.16.32.0/20 D: 198.16.64.0 198.95.15.255 escrito como 198.16.64.0/19 41. 42. Eles podem ser agregados a 57.6.96/19. suficiente adicionar uma novaentrada de tabela: 29.18.0.0/22 para o novo bloco. Se um pacote de entrada corresponder a 29.18.0.0/17 e tambm a 29.18.0.0/22, o mais longo vencer. Essa regra torna possvel atribuir um grande bloco a uma nica linha de sada, mas fazer uma exceo para um ou mais blocos pequenos dentro de seu intervalo. Os pacotes so roteados como: (a) Interface 1 (b) Interface 0 (c) Roteador 2

36. 37.

38. 39.

40.

43.


36/57

34


(d) Roteador 1 (e) Roteador 2 44. Depois que o NAT instalado, crucial que todosos pacotes pertencentes a uma nica conexo entrem e saiam da empresa pelo mesmo roteador, pois nele que o mapeamento mantido. Se cada roteador tiver seu prprio ende

reo IP e todo o trfego pertencente a uma dada conexo puder ser enviado ao mesmo roteador, o mapeamento poder ser feito de modo correto, e o multihoming com o NAT poder funcionar. Voc dir que o ARP no fornece um servio camada da rede; ele faz partea camada de rede e ajuda a fornecer um servio camada de transporte. A questo de endereamento IP no ocorre na camada de enlace de dados. Os protocolos da camada de enlace de dados so semelhantes aos protocolos 1 a 6 do Captulo 3, HDLC, PPP etc. Eles movem bits de uma extremidade de uma linha at a outra. O RARP tem um servidorRARP que responde a solicitaes. O ARP no tem esse recurso. Os prprios hosts respondem a consultas ARP. No caso geral, o problema no trivial. Os fragmentos podem chegar fora de ordem e alguns podem estar faltando. Em uma retransmisso, o datagramapode estar fragmentado em blocos de diferentes tamanhos. Alm disso, o tamanho total no conhecido at chegar o ltimo fragmento. Talvez o nico modo de realizar a remont

agem seja inserir no buffer todos os fragmentos, at chegar o ltimo e o tamanho serconhecido. Depois, crie um buffer com o tamanho correto e insira os fragmentosno buffer, mantendo um mapa de bits com 1 bit por 8 bytes para controlar os bytes que esto presentes no buffer. Quando todos os bits no mapa de bits forem iguaisa 1, o datagrama estar completo. No que se refere ao receptor, isso faz parte deum novo datagrama, pois nenhuma outra parte dele conhecida. Portanto, ele ser enfileirado at aparecer o restante. Se as outras partes no forem recebidas, essa tambm chegar ao tempo limite. Um erro no cabealho muito mais srio que um erro nos dados. Por exemplo, um endereo incorreto poderia resultar na entrega de um pacote ao host errado. Muitos hosts no verificam se um pacote que lhes foi entregue de fatodestinado a eles, supondo que a rede nunca lhes dar pacotes destinados a outro host. Algumas vezes, os dados no so verificados porque isso dispendioso, e as camadas superiores com freqncia fazem essa verificao de qualquer modo, tornando-a redundan

te aqui. Sim. O fato de a LAN Minneapolis ser sem fio no faz os pacotes que chegam para ela em Boston saltarem repentinamente para Minneapolis. O

45.

46. 47.

48.

49.

50.


37/57


35

agente local (home-agent) em Boston deve canaliz-los para o agente externo (foreign-agent) na LAN sem fios em Minneapolis. A melhor maneira de imaginar essa situao considerar que o usurio se conectou LAN de Minneapolis, da mesma forma que todos

os outros usurios de Minneapolis. O fato da conexo usar rdio em vez de cabos irrelevante. 51. Com 16 bytes, existem 2128 ou 3,4 1038 endereos. Se os alocarmos velocidade de 1018 por segundo, eles iro durar por 1013 anos. Esse nmero 1.000 vezes aidade do universo. claro que o espao de endereos no plano, de modo que eles no socados linearmente, mas esse clculo mostra que at mesmo um esquema de alocao que tenha uma eficincia de 1/1.000 (0,1%), nunca se esgotar. O campo Protocol informa aohost de destino a que tratador de protocolos deve ser dado o pacote IP. Roteadores intermedirios no precisam dessa informao, e assim ela no necessria no cabealhoipal. Na realidade, ela est l, mas disfarada. O campo Next header do ltimo cabealho (de extenso) usado para esse propsito. Conceitualmente, no h mudanas. Tecnicamente,endereos IP solicitados agora so maiores, e assim so necessrios campos maiores.

52.53.

SOLUES DOS PROBLEMAS DO CAPTULO 61. A chamada LISTEN poderia indicar a vontade de estabelecer novas conexes, mas node bloquear. Quando fosse feita uma tentativa de conexo, o chamador poderia receber um sinal. Ento ele executaria, digamos, OK ou REJECT para aceitar ou rejeitara conexo. Em nosso esquema original, essa flexibilidade est ausente. A linha tracejada de PASSIVE ESTABLISHMENT PENDING at ESTABLISHED no depende mais da chegada de uma confirmao. A transio pode acontecer imediatamente. Em essncia, o estado PASSIVEESTABLISHMENT PENDING desaparece, pois ele nunca visvel em qualquer nvel. Se o cliente envia um pacote a SERVER_PORT e o servidor no est escutando essa porta, o pa

cote no ser entregue ao servidor. (a) O clock leva 32.768 pulsos ou 3.276,8 segundos para completar o ciclo. taxa de gerao zero, o transmissor entraria na zona proibida em 3.276,8 60 = 3.216,8 segundos. (b) A 240 nmeros de seqncia/min, o nmero de seqncia real 4t, onde t medido em segundos. A margem esquerda da regio proibida 10 3.216,8). Igualando essas duas frmulas, descobrimos que a interseo entre elas ocorre em t = 5.361,3 segundos.

2.

3. 4.


38/57

36


5.

Observe o segundo pacote duplicado na Figura 6.11(b). Quando esse pacote chegass

e, seria um desastre se as confirmaes para y ainda estivessem presentes. Os impasses so possveis. Por exemplo, um pacote chega inesperadamente a A, e A o confirma.A confirmao se perde, mas agora A est aberto, enquanto B nada sabe sobre o que aconteceu. Em seguida, o mesmo acontece a B, e ento ambos ficam abertos, mas esperando nmeros de seqncia diferentes. Os tempos limite tm de ser introduzidos para evitaros impasses. No. O problema essencialmente o mesmo com mais de dois exrcitos. Se otempo AW ou WA pequeno, os eventos AC(W) e WC(A) so eventos improvveis. O transmissor deve retransmitir no estado S1; a ordem do receptor no importa. Sim. Ambos os lados poderiam executar RECEIVE simultaneamente. Sim, n2 + n3 + n6 + n7 = 1. Os estados listening, waiting, sending e receiving implicam todos que o usurio estbloqueado e portanto no pode estar tambm em outro estado. Uma mensagem de comprimento zero recebida pelo outro lado. Ela poderia ser usada para assinalar o fim do

arquivo. Nenhuma das primitivas pode ser executada, porque o usurio est bloqueado. Desse modo, somente so possveis eventos de chegada de pacotes, e no todos eles. CallReq, ClearReq, DataPkt e Credit so os nicos vlidos. A janela deslizante mais simples, tendo apenas um conjunto de parmetros (as arestas da janela) para administrar. Alm disso, o problema de uma janela ser aumentada e depois diminuda, com as TPDUs chegando na ordem errada, no ocorre. Porm, o esquema de crdito mais flexvel, permitindo um gerenciamento dinmico da bufferizao, separada das confirmaes. No. Os pacos IP contm endereos IP que especificam uma mquina de destino. Uma vez que tal pacote chegasse, como o tratador de rede saberia a que processo entreg-lo? Os pacotesUDP contm uma porta de destino. Essa informao essencial para que eles possam ser entregues ao processo correto. possvel que um cliente possa obter o arquivo errado.Suponha que o cliente A envie uma solicitao para o arquivo 1 e depois sofra uma pane. Ento, outro cliente B usa o mesmo protocolo para solicitar outro arquivo 2. Su

ponha que o cliente B, funcionando na mesma mquina que A (com

6.

7. 8.

9. 10.

11. 12.

13.

14.

15.


39/57


37

o mesmo endereo IP), vincule seu soquete UDP mesma porta que A esteve usando antes. Alm disso, suponha que a solicitao de B se perca. Quando a resposta do servidorchegar (para a solicitao de A), o cliente B a receber e presumir que ela uma respost

a sua prpria solicitao. 16. O envio de 1.000 bits sobre uma linha de 1 Gbps demoraum 1 ms. A velocidade da luz na fibra ptica 200 km/ms; assim, demora 0,5 ms paraa solicitao chegar e outro 0,5 ms para a resposta voltar. Ao todo, 1.000 bits so transmitidos em 1 ms. Isso equivalente a 1 megabit/s, ou 0,1% de eficincia. A 1 Gbps, o tempo de resposta determinado pela velocidade da luz. O melhor que pode seralcanado 1 ms. A 1 Mbps, a linha demora cerca de 1 ms para bombear os 1.024 bits, 0,5 ms para o ltimo chegar ao servidor e 0,5 ms para a resposta voltar, no melhor caso. O melhor tempo de RPC possvel ento 2 ms. A concluso que melhorar a velocidade da linha por um fator de 1.000 s rende um fator de dois em desempenho. A menos que a linha de gigabits seja incrivelmente econmica, provvel que no compense teressa aplicao. Aqui esto trs razes. Primeiro, as IDs de processos so especficas do Suso de IDs de processos tornaria esses protocolos dependentes do SO. Em segundo

lugar, um nico processo pode estabelecer vrios canais de comunicaes. Uma nica ID deprocesso (por processo) no pode ser usada como identificador de destino para fazer distino entre esses canais. Em terceiro lugar, fazer os processos escutarem em portas conhecidas fcil, mas so impossveis IDs de processos conhecidas. O segmento padro tem 536 bytes. O TCP acrescenta 20 bytes, da mesma forma que o IP, o que resulta no padro de 576 bytes ao todo. Embora cada datagrama chegue intacto, possvel que os datagramas cheguem na ordem errada; assim, o TCP tem de estar preparado para montar novamente as peas de uma mensagem de maneira apropriada. Cada amostra ocupa 4 bytes. Isso d um total de 256 amostras por pacote. Existem 44.100 amostras/s; assim, com 256 amostras/pacote, ele levar 44.100/256 ou 172 pacotes para transmitir o equivalente a um segundo de msica. Sem dvida. O chamador teria de fornecer todas as informaes necessrias, mas no h razo para que o RTP no possa estar no nca mesma maneira que o UDP. No. Uma conexo identificada apenas por seus soquetes. D

esse modo, (1, p) (2, q) a nica conexo possvel entre essas duas portas.

17.

18.

19. 20.

21.

22.

23.


40/57

38


24.

O bit ACK usado para informar se o campo de 32 bits usado. Porm, se ele no existis

se, o campo de 32 bits sempre teria de ser usado, se necessrio confirmando um byte que j tivesse sido confirmado. Em resumo, ele no absolutamente essencial para otrfego de dados normal. No entanto, ele desempenha um papel crucial durante o estabelecimento de conexes, onde usado na segunda e na terceira mensagem do handshake de trs vias. O segmento de TCP inteiro deve caber no campo de carga til de 65.515 bytes de um pacote IP. Tendo em vista que o cabealho de TCP tem no mnimo 20 bytes, restam somente 65.495 bytes para dados de TCP. Uma alternativa comear com um LISTEN. Se for recebido um SYN, o protocolo entrar no estado SYN RECD. O outro modo ocorre quando um processo tenta fazer uma abertura ativa e enviar um SYN. Se ooutro lado tambm estivesse se abrindo e fosse recebido um SYN, ele tambm entrariano estado SYN RECD. Embora o usurio esteja digitando a uma velocidade uniforme,os caracteres sero ecoados em rajadas. O usurio pode pressionar vrias teclas sem qu

e nada aparea na tela e depois, repentinamente, o contedo da tela alcanar a digitao.possvel que as pessoas considerem esse efeito incmodo. As primeiras rajadas contm respectivamente 2K, 4K, 8K e 16K bytes. A rajada seguinte de 24 KB e ocorre depois de 40 ms. A prxima transmisso ser um segmento de tamanho mximo 1. Depois, teremos2, 4 e 8. Assim, aps quatro sucessos, ele ter 8 KB. As estimativas sucessivas so 29,6, 29,84, 29,256. Uma janela pode ser enviada a cada 20 ms. Isso d 50 janelas/s,correspondendo a uma taxa de dados mxima de cerca de 3,3 milhes de bytes/s. A eficincia da linha ento 26,4 Mbps/1.000 Mbps, ou 2,6%. A meta enviar 232 bytes em 120segundos ou a carga til de 35.791.394 bytes/s. Isso equivale a 23.860 quadros de1.500 bytes por segundo. O overhead do TCP de 20 bytes. O overhead do IP de 20bytes. O overhead da Ethernet de 26 bytes. Isso significa que, para 1.500 bytesde carga til, devem ser enviados 1.566 bytes. Se fssemos enviar 23.860 quadros de1.566 bytes a cada segundo, precisaramos de uma linha de 299 Mbps. Com qualquer v

elocidade maior que essa, correremos o risco de encontrar dois segmentos TCP diferentes com o mesmo nmero de seqncia ao mesmo tempo. Um transmissor pode no enviar mais de 255 TPDUs, isto , 255 128 8 bits em 30 segundos. Portanto, a taxa de dadosno maior que 8,704 kbps.

25.

26.

27.

28. 29. 30. 31.

32.

33.


41/57


39

34. 35.

Calcule a mdia: (270.000 0 + 730.000 1 ms)/1.000.000. A demora de 730 ms. Ela lev

a 4 10 = 40 instrues para copiar 8 bytes. Quarenta instrues demoram 40 ns. Desse modo, cada byte exige 5 ns de tempo da CPU para cpia. Assim, o sistema capaz de manipular 200 MB/s ou 1.600 Mbps. Ele pode tratar uma linha de 1 Gbps, se no houver nenhum outro gargalo. O tamanho do espao de seqncias 264 bytes, o que equivale a cerca de 2 1019 bytes. Um transmissor de 75 Tbps consome um espao de seqncias taxa de9,375 1012 nmeros de seqncias por segundo. Ele demora 2 milhes de segundos para recomear. Tendo em vista que h 86.400 segundos em um dia, ele ir demorar mais de trs semanas para recomear, mesmo a 75 Tbps. Um tempo mximo de durao de pacote menor que trssemanas evitar o problema. Em resumo, a mudana para 64 bits provavelmente funcionar por um bom tempo. O RPC sobre o UDP leva apenas dois pacotes em vez de trs. Entretanto, o RPC ter problemas se a resposta no couber em um nico pacote. Sim. O pacote 6 confirma tanto a solicitao quanto o FIN. Se cada um fosse confirmado separadam

ente, teramos 10 pacotes na seqncia. Como outra alternativa, o pacote 9 que confirma a resposta e o FIN tambm poderiam ser divididos em dois pacotes separados. Desse modo, o fato de haver nove pacotes se deve simplesmente boa sorte. Com um pacote 11,72 vezes menor, voc obtm 11,72 vezes mais pacotes por segundo, e assim cadapacote s recebe 6.250/11,72, ou 533 instrues. A velocidade da luz na fibra e no cobre aproxi

Documents

30410344 Manual Solucoes Redes Tanenbaum