Solution Manual For Computer Networks, 4th Edition

Page 1 of 15

Solution Manual For Computer Networks, 4th Edition - Page 1 preview image

COMPUTER NETWORKSFOURTH EDITIONPROBLEM SOLUTIONSANDREW S. TANENBAUMVrije UniversiteitAmsterdam, The Netherlands

Page 2 of 15

Solution Manual For Computer Networks, 4th Edition - Page 2 preview image

Page 3 of 15

Solution Manual For Computer Networks, 4th Edition - Page 3 preview image

PROBLEM SOLUTIONS1SOLUTIONS TO CHAPTER 1 PROBLEMS1.The dog can carry 21 gigabytes, or 168 gigabits.A speed of 18 km/hourequals 0.005 km/sec. The time to travel distancexkm isx /0.005=200xsec,yielding a data rate of 168/200xGbps or 840/xMbps.Forx <5.6 km, thedog has a higher rate than the communication line.2.The LAN model can be grown incrementally. If the LAN is just a long cable.it cannot be brought down by a single failure (if the servers are replicated) Itis probably cheaper. It provides more computing power and better interactiveinterfaces.3.A transcontinental fiber link might have many gigabits/sec of bandwidth, butthe latency will also be high due to the speed of light propagation overthousands of kilometers. In contrast, a 56-kbps modem calling a computer inthe same building has low bandwidth and low latency.4.A uniform delivery time is needed for voice, so the amount of jitter in the net-work is important.This could be expressed as the standard deviation of thedelivery time. Having short delay but large variability is actually worse thana somewhat longer delay and low variability.5.No. The speed of propagation is 200,000 km/sec or 200 meters/μsec.In 10μsec the signal travels 2 km. Thus, each switch adds the equivalent of 2 kmof extra cable.If the client and server are separated by 5000 km, traversingeven 50 switches adds only 100 km to the total path, which is only 2%. Thus,switching delay is not a major factor under these circumstances.6.The request has to go up and down, and the response has to go up and down.The total path length traversed is thus 160,000 km. The speed of light in airandvacuumis300,000km/sec,sothepropagationdelayaloneis160,000/300,000 sec or about 533 msec.7.There is obviously no single correct answer here, but the following pointsseem relevant. The present system has a great deal of inertia (checks and bal-ances) built into it.This inertia may serve to keep the legal, economic, andsocial systems from being turned upside down every time a different partycomes to power.Also, many people hold strong opinions on controversialsocial issues, without really knowing the facts of the matter. Allowing poorlyreasoned opinions be to written into law may be undesirable.The potentialeffects of advertising campaigns by special interest groups of one kind oranother also have to be considered. Another major issue is security. A lot ofpeople might worry about some 14-year kid hacking the system and falsifyingthe results.

Page 4 of 15

Solution Manual For Computer Networks, 4th Edition - Page 4 preview image

2PROBLEM SOLUTIONS FOR CHAPTER 18.Call the routersA,B,C,D, andE.There are ten potential lines:AB,AC,AD,AE,BC,BD,BE,CD,CE, andDE. Each of these has four possibilities(three speeds or no line), so the total number of topologies is 410=1,048,576.At 100 ms each, it takes 104,857.6 sec, or slightly more than 29 hours toinspect them all.9.The mean router-router path is twice the mean router-root path.Number thelevels of the tree with the root as 1 and the deepest level asn.The path fromthe root to levelnrequiresn−1 hops, and 0.50 of the routers are at this level.The path from the root to leveln−1 has 0.25 of the routers and a length ofn−2 hops. Hence, the mean path length,l, is given byl=0.5×(n−1)+0.25×(n−2)+0.125×(n−3)+. . .orl=i=1Σ∞n(0.5)i−i=1Σ∞i(0.5)iThis expression reduces tol=n−2.The mean router-router path is thus2n−4.10.Distinguishn+2 events.Events 1 throughnconsist of the correspondinghost successfully attempting to use the channel, i.e., without a collision. Theprobability of each of these events isp(1−p)n−1.Eventn+1 is an idlechannel, with probability (1−p)n.Eventn+2 is a collision.Since thesen+2 events are exhaustive, their probabilities must sum to unity. The proba-bility of a collision, which is equal to the fraction of slots wasted, is then just1−np(1−p)n−1−(1−p)n.11.Among other reasons for using layered protocols, using them leads to break-ing up the design problem into smaller, more manageable pieces, and layeringmeans that protocols can be changed without affecting higher or lower ones,12.No. In the ISO protocol model, physical communication takes place only inthe lowest layer, not in every layer.13.Connection-oriented communication has three phases.In the establishmentphase a request is made to set up a connection. Only after this phase has beensuccessfully completed can the data transfer phase be started and data trans-ported. Then comes the release phase.Connectionless communication doesnot have these phases. It just sends the data.14.Message and byte streams are different.In a message stream, the networkkeeps track of message boundaries. In a byte stream, it does not. For exam-ple, suppose a process writes 1024 bytes to a connection and then a little laterwrites another 1024 bytes.The receiver then does a read for 2048 bytes.With a message stream, the receiver will get two messages, of 1024 bytes

Page 5 of 15

Solution Manual For Computer Networks, 4th Edition - Page 5 preview image

PROBLEM SOLUTIONS FOR CHAPTER 13each.With a byte stream, the message boundaries do not count and thereceiver will get the full 2048 bytes as a single unit. The fact that there wereoriginally two distinct messages is lost.15.Negotiation has to do with getting both sides to agree on some parameters orvalues to be used during the communication.Maximum packet size is oneexample, but there are many others.16.The service shown is the service offered by layerkto layerk+1.Anotherservice that must be present is below layerk, namely, the service offered tolayerkby the underlying layerk−1.17.The probability,Pk, of a frame requiring exactlyktransmissions is the proba-bility of the firstk−1 attempts failing,pk−1, times the probability of thek-thtransmission succeeding, (1−p).The mean number of transmission is thenjustk=1Σ∞kPk=k=1Σ∞k(1−p)pk−1=1−p13333318.(a) Data link layer. (b) Network layer.19.Frames encapsulate packets. When a packet arrives at the data link layer, theentire thing, header, data, and all, is used as the data field of a frame. Theentire packet is put in an envelope (the frame), so to speak (assuming it fits).20.Withnlayers andhbytes added per layer, the total number of header bytesper message ishn, so the space wasted on headers ishn. The total messagesizeisM+nh,sothefractionofbandwidthwastedonheadersishn /(M+hn).21.Both models are based on layered protocols. Both have a network, transport,and application layer.In both models, the transport service can provide areliable end-to-end byte stream.On the other hand, they differ in severalways. The number of layers is different, the TCP/IP does not have session orpresentation layers, OSI does not support internetworking, and OSI has bothconnection-oriented and connectionless service in the network layer.22.TCP is connection oriented, whereas UDP is a connectionless service.23.The two nodes in the upper-right corner can be disconnected from the rest bythree bombs knocking out the three nodes to which they are connected. Thesystem can withstand the loss of any two nodes.24.Doubling every 18 months means a factor of four gain in 3 years. In 9 years,the gain is then 43or 64, leading to 6.4 billion hosts. My intuition says that ismuch too conservative, since by then probably every television in the worldand possibly billions of other appliances will be on home LANs connected to

Page 6 of 15

Solution Manual For Computer Networks, 4th Edition - Page 6 preview image

4PROBLEM SOLUTIONS FOR CHAPTER 1the Internet. The average person in the developed world may have dozens ofInternet hosts by then.25.If the network tends to lose packets, it is better to acknowledge each oneseparately, so the lost packets can be retransmitted. On the other hand, if thenetwork is highly reliable, sending one acknowledgement at the end of theentire transfer saves bandwidth in the normal case (but requires the entire fileto be retransmitted if even a single packet is lost).26.Small, fixed-length cells can be routed through switches quickly, and com-pletely in hardware.Small, fixed-size cells also make it easier to buildhardwarethat handlesmany cellsin parallel.Also, they do not blocktransmission lines for very long, making it easier to provide quality-of-serviceguarantees.27.The speed of light in coax is about 200,000 km/sec, which is 200 meters/μsec.At 10 Mbps, it takes 0.1μsec to transmit a bit. Thus, the bit lasts 0.1μsec intime, during which it propagates 20 meters.Thus, a bit is 20 meters longhere.28.The image is 1024×768×3 bytes or 2,359,296 bytes.This is 18,874,368bits. At 56,000 bits/sec, it takes about 337.042 sec. At 1,000,000 bits/sec, ittakes about 18.874 sec.At 10,000,000 bits/sec, it takes about 1.887 sec.At100,000,000 bits/sec, it takes about 0.189 sec.29.Think about the hidden terminal problem. Imagine a wireless network of fivestations,AthroughE, such that each one is in range of only its immediateneighbors. ThenAcan talk toBat the same timeDis talking toE. Wirelessnetworks have potential parallelism, and in this way differ from Ethernet.30.One disadvantage is security. Every random delivery man who happens to bein the building can listen in on the network. Another disadvantage is reliabil-ity. Wireless networks make lots of errors. A third potential problem is bat-tery life, since most wireless devices tend to be mobile.31.One advantage is that if everyone uses the standard, everyone can talk toeveryone. Another advantage is that widespread use of any standard will giveit economies of scale, as with VLSI chips. A disadvantage is that the politicalcompromises necessary to achieve standardization frequently lead to poorstandards.Another disadvantage is that once a standard has been widelyadopted, it is difficult to change,, even if new and better techniques ormethods are discovered.Also, by the time it has been accepted, it may beobsolete.32.There are many examples, of course.Some systems for which there is inter-national standardization include compact disc players and their discs, Walk-man tape players and audio cassettes, cameras and 35mm film, and automated

Page 7 of 15

Solution Manual For Computer Networks, 4th Edition - Page 7 preview image

PROBLEM SOLUTIONS FOR CHAPTER 15teller machines and bank cards.Areas where such international standardiza-tion is lacking include VCRs and videotapes (NTSC VHS in the U.S., PALVHS in parts of Europe, SECAM VHS in other countries), portable tele-phones, lamps and lightbulbs (different voltages in different countries), electr-ical sockets and appliance plugs (every country does it differently), photo-copiers and paper (8.5 x 11 inches in the U.S., A4 everywhere else), nuts andbolts (English versus metric pitch), etc.SOLUTIONS TO CHAPTER 2 PROBLEMS1.an= πn−1333,bn=0,c=1.2.A noiseless channel can carry an arbitrarily large amount of information, nomatter how often it is sampled.Just send a lot of data per sample.For the 4kHz channel, make 8000 samples/sec.If each sample is 16 bits, the channelcan send 128 kbps.If each sample is 1024 bits, the channel can send 8.2Mbps. The key word here is ‘‘noiseless.’’ With a normal 4 kHz channel, theShannon limit would not allow this.3.Using the Nyquist theorem, we can sample 12 million times/sec.Four-levelsignals provide 2 bits per sample, for a total data rate of 24 Mbps.4.A signal-to-noise ratio of 20 dB meansS/N=100.Since log2101 is about6.658, the Shannon limit is about 19.975 kbps. The Nyquist limit is 6 kbps.The bottleneck is therefore the Nyquist limit, giving a maximum channelcapacity of 6 kbps.5.To send a T1 signal we needHlog2(1+S /N)=1.544×106withH=50, 000.This yieldsS /N=230−1, which is about 93 dB.6.A passive star has no electronics.The light from one fiber illuminates anumber of others. An active repeater converts the optical signal to an electri-cal one for further processing.7.Use∆f=c∆λ/λ2with∆λ =10−7meters andλ =10−6meters.This gives abandwidth (∆f) of 30,000 GHz.8.The data rate is 480×640×24×60 bps, which is 442 Mbps. For simplicity,let us assume 1 bps per Hz.From Eq. (2-3) we get∆λ = λ2∆f /c.We have∆f=4.42×108, so∆λ =2.5×10−6microns. The range of wavelengths usedis very short.9.The Nyquist theorem is a property of mathematics and has nothing to do withtechnology. It says that if you have a function whose Fourier spectrum doesnot contain any sines or cosines abovef, then by sampling the function at a

Page 8 of 15

Solution Manual For Computer Networks, 4th Edition - Page 8 preview image

6PROBLEM SOLUTIONS FOR CHAPTER 2frequency of 2fyou capture all the information there is.Thus, the Nyquisttheorem is true for all media.10.In the text it was stated that the bandwidths (i.e., the frequency ranges) of thethree bands were approximately equal. From the formula∆f=c∆λ/λ2, it isclear that to get a constant∆f, the higher the frequency, the larger∆λhas tobe.The x-axis in the figure isλ, so the higher the frequency, the more∆λyou need.In fact,∆λis quadratic inλ. The fact that the bands are approxi-mately equal is an accidental property of the kind of silicon used.11.Start withλf=c. We know thatcis 3×108m/s.Forλ =1 cm, we get 30GHz. Forλ =5 m, we get 60 MHz. Thus, the band covered is 60 MHz to 30GHz.12.At 1 GHz, the waves are 30 cm long. If one wave travels 15 cm more thanthe other, they will arrive out of phase. The fact that the link is 50 km long isirrelevant.13.If the beam is off by 1 mm at the end, it misses the detector. This amounts toa triangle with base 100 m and height 0.001 m.The angle is one whosetangent is thus 0.00001. This angle is about 0.00057 degrees.14.With 66/6 or 11 satellites per necklace, every 90 minutes 11 satellites passoverhead.This means there is a transit every 491 seconds. Thus, there willbe a handoff about every 8 minutes and 11 seconds.15.The satellite moves from being directly overhead toward the southern hor-izon, with a maximum excursion from the vertical of 2φ. It takes 24 hours togo from directly overhead to maximum excursion and then back.16.The number of area codes was 8×2×10, which is 160.The number ofprefixes was 8×8×10, or 640. Thus, the number of end offices was limitedto 102,400. This limit is not a problem.17.With a 10-digit telephone number, there could be 1010numbers, althoughmany of the area codes are illegal, such as 000.However, a much tighterlimit is given by the number of end offices.There are 22,000 end offices,each with a maximum of 10,000 lines. This gives a maximum of 220 milliontelephones.There is simply no place to connect more of them.This couldnever be achieved in practice because some end offices are not full.An endoffice in a small town in Wyoming may not have 10,000 customers near it, sothose lines are wasted.18.Each telephone makes 0.5 calls/hour at 6 minutes each.Thus, a telephoneoccupies a circuit for 3 minutes/hour. Twenty telephones can share a circuit,although having the load be close to 100% (ρ =1 in queueing terms) impliesvery long wait times).Since 10% of the calls are long distance, it takes 200telephones to occupy a long-distance circuit full time.The interoffice trunk

Page 9 of 15

Solution Manual For Computer Networks, 4th Edition - Page 9 preview image

PROBLEM SOLUTIONS FOR CHAPTER 27has 1,000,000/4000 = 250 circuits multiplexed onto it.With 200 telephonesper circuit, an end office can support 200×250=50,000 telephones.19.The cross-section of each strand of a twisted pair isπ/4 square mm. A 10-kmlengthofthismaterial,withtwostrandsperpairhasavolumeof2π/4×10−2m3.This volume is about 15,708 cm3.With a specific gravityof 9.0, each local loop has a mass of 141 kg. The phone company thus owns1.4×109kg of copper. At 3 dollars each, the copper is worth about 4.2 bil-lion dollars.20.Like a single railroad track, it is half duplex. Oil can flow in either direction,but not both ways at once.21.Traditionally, bits have been sent over the line without any error correctingscheme in the physical layer. The presence of a CPU in each modem makesit possible to include an error correcting code in layer 1 to greatly reduce theeffective error rate seen by layer 2. The error handling by the modems can bedone totally transparently to layer 2.Many modems now have built in errorcorrection.22.There are four legal values per baud, so the bit rate is twice the baud rate. At1200 baud, the data rate is 2400 bps.23.The phase shift is always 0, but two amplitudes are used, so this is straightamplitude modulation.24.If all the points are equidistant from the origin, they all have the same ampli-tude, so amplitude modulation is not being used.Frequency modulation isnever used in constellation diagrams, so the encoding is pure phase shift key-ing.25.Two, one for upstream and one for downstream.The modulation schemeitself just uses amplitude and phase. The frequency is not modulated.26.There are 256 channels in all, minus 6 for POTS and 2 for control, leaving248 for data. If 3/4 of these are for downstream, that gives 186 channels fordownstream.ADSLmodulationis at4000baud,sowithQAM-64(6bits/baud) we have 24,000 bps in each of the 186 channels.The totalbandwidth is then 4.464 Mbps downstream.27.A 5-KB Web page has 40,000 bits. The download time over a 36 Mbps chan-nel is 1.1 msec.If the queueing delay is also 1.1 msec, the total time is 2.2msec.Over ADSL there is no queueing delay, so the download time at 1Mbps is 40 msec. At 56 kbps it is 714 msec.28.There are ten 4000 Hz signals. We need nine guard bands to avoid anyinterference.The minimum bandwidth required is 4000×10+400×9 =43,600 Hz.

Page 10 of 15

Solution Manual For Computer Networks, 4th Edition - Page 10 preview image

8PROBLEM SOLUTIONS FOR CHAPTER 229.A sampling time of 125μsec corresponds to 8000 samples per second.According to the Nyquist theorem, this is the sampling frequency needed tocapture all the information in a 4 kHz channel, such as a telephone channel.(Actually the nominal bandwidth is somewhat less, but the cutoff is notsharp.)30.The end users get 7×24=168 of the 193 bits in a frame.The overhead istherefore 25/193 = 13%.31.In both cases 8000 samples/sec are possible.With dibit encoding, two bitsare sent per sample. With T1, 7 bits are sent per period. The respective datarates are 16 kbps and 56 kbps.32.Ten frames. The probability of some random pattern being 0101010101 (on adigital channel) is 1/1024.33.A coder accepts an arbitrary analog signal and generates a digital signal fromit. A demodulator accepts a modulated sine wave only and generates a digitalsignal.34.(a) 64 kbps. (b) 32 kbps. (c) 8 kbps.35.The signal must go from 0 toAin one quarter of a wave—that is, in a timeT /4.In order to track the signal, 8 steps must fit into the quarter wave, or 32samples per full wave. The time per sample is 1/xso the full period must belong enough to contain 32 samples—that is,T >32/xorfmax=x /32.36.A drift rate of 10−9means 1 second in 109seconds or 1 nsec per second. AtOC-1 speed, say, 50 Mbps, for simplicity, a bit lasts for 20 nsec. This meansit takes only 20 seconds for the clock to drift off by one bit.Consequently,the clocks must be continuously synchronized to keep them from getting toofar apart. Certainly every 10 sec, preferably much more often.37.Of the 90 columns, 86 are available for user data in OC-1.Thus, the usercapacity is 86×9=774 bytes/frame.With 8 bits/byte, 8000 frames/sec, and3OC-1carriersmultiplexedtogether,thetotalusercapacityis3×774×8×8000, or 148.608 Mbps.38.VT1.5 can accommodate 8000 frames/sec×3 columns×9 rows×8 bits =1.728 Mbps. It can be used to accommodate DS-1. VT2 can accommodate8000 frames/sec×4 columns×9 rows×8 bits = 2.304 Mbps. It can be usedto accommodate European CEPT-1 service.VT6 can accommodate 8000frames/sec×12 columns×9 rows×8 bits = 6.912 Mbps. It can be used toaccommodate DS-2 service.39.Message switching sends data units that can be arbitrarily long.Packetswitching has a maximum packet size. Any message longer than that is splitup into multiple packets.

Page 11 of 15

Solution Manual For Computer Networks, 4th Edition - Page 11 preview image

PROBLEM SOLUTIONS FOR CHAPTER 2940.TheOC-12cframesare12×90=1080columnsof9rows.Ofthese,12×3=36 columns are taken up by line and section overhead.This leavesan SPE of 1044 columns.One SPE column is taken up by path overhead,leaving 1043 columns for user data.Since each column holds 9 bytes of 8bits, an OC-12c frame holds 75,096 user data bits. With 8000 frames/sec, theuser data rate is 600.768 Mbps.41.The three networks have the following properties:star: best case = 2, average case = 2, worst case = 2ring: best case = 1, average case =n/4, worst case =n/2full interconnect: best case = 1, average case = 1, worst case = 142.With circuit switching, att=sthe circuit is set up; att=s+x /bthe last bitis sent; att=s+x /b+kdthe message arrives.With packet switching, thelast bit is sent att=x /b.To get to the final destination, the last packet mustbe retransmittedk−1 times by intermediate routers, each retransmission tak-ingp /bsec, so the total delay isx /b+(k−1)p /b+kd.Packet switching isfaster ifs >(k−1)p /b.43.The total number of packets needed isx /p, so the total data + header traffic is(p+h)x /pbits.The source requires (p+h)x /pbsec to transmit these bits.The retransmissions of the last packet by the intermediate routers take up atotal of (k−1)(p+h)/bsec. Adding up the time for the source to send all thebits, plus the time for the routers to carry the last packet to the destination,thusclearingthepipeline,wegetatotaltimeof(p+h)x /pb+(p+h)(k−1)/bsec.Minimizing this quantity with respect top, we findp=√77777777hx /(k−1).44.Each cell has six neighbors. If the central cell uses frequency groupA, its sixneighbors can useB,C,B,C,B, andCrespectively.In other words, only 3unique cells are needed. Consequently, each cell can have 280 frequencies.45.First, initial deployment simply placed cells in regions where there was highdensity of human or vehicle population.Once they were there, the operatoroften did not want to go to the trouble of moving them. Second, antennas aretypically placed on tall buildings or mountains. Depending on the exact loca-tion of such structures, the area covered by a cell may be irregular due to obs-tacles near the transmitter.Third, some communities or property owners donot allow building a tower at a location where the center of a cell falls. Insuch cases, directional antennas are placed at a location not at the cell center.46.If we assume that each microcell is a circle 100 m in diameter, then each cellhas an area of 2500π. If we take the area of San Francisco, 1.2×108m2anddivide it by the area of 1 microcell, we get 15,279 microcells.Of course, it isimpossible to tile the plane with circles (and San Francisco is decidedlythree-dimensional), but with 20,000 microcells we could probably do the job.

Page 12 of 15

Solution Manual For Computer Networks, 4th Edition - Page 12 preview image

10PROBLEM SOLUTIONS FOR CHAPTER 247.Frequencies cannot be reused in adjacent cells, so when a user moves fromone cell to another, a new frequency must be allocated for the call. If a usermoves into a cell, all of whose frequencies are currently in use, the user’s callmust be terminated.48.It is not caused directly by the need for backward compatibility. The 30 kHzchannel was indeed a requirement, but the designers of D-AMPS did not haveto stuff three users into it.They could have put two users in each channel,increasing the payload before error correction from 260×50=13 kbps to260×75=19.5 kbps.Thus, the quality loss was an intentional trade-off toput more users per cell and thus get away with bigger cells.49.D-AMPS uses 832 channels (in each direction) with three users sharing a sin-gle channel.This allows D-AMPS to support up to 2496 users simultane-ously per cell.GSM uses 124 channels with eight users sharing a singlechannel.This allows GSM to support up to 992 users simultaneously.Bothsystems use about the same amount of spectrum (25 MHz in each direction).D-AMPS uses 30 KHz×892 = 26.76 MHz.GSM uses 200 KHz×124 =24.80 MHz.The difference can be mainly attributed to the better speechquality provided by GSM (13 Kbps per user) over D-AMPS (8 Kbps peruser).50.The result is obtained by negating each ofA,B, andCand then adding thethree chip sequences.Alternatively the three can be added and then negated.The result is (+3 +1 +1−1−3−1−1 +1).51.By definitionSdT≡m1333i=1ΣmSiTiIfTsends a 0 bit instead of 1 bit, its chip sequence is negated, with thei-thelement becoming−Ti. Thus,SdT≡m1333i=1ΣmSi(−Ti)= −m1333i=1ΣmSiTi=052.When two elements match, their product is +1.When they do not match,their product is−1.To make the sum 0, there must be as many matches asmismatches.Thus, two chip sequences are orthogonal if exactly half of thecorresponding elements match and exactly half do not match.53.Just compute the four normalized inner products:(−1 +1−3 +1−1−3 +1 +1)d(−1−1−1 +1 +1−1 +1 +1)/8 = 1(−1 +1−3 +1−1−3 +1 +1)d(−1−1 +1−1 +1 +1 +1−1)/8 =−1

Page 13 of 15

Solution Manual For Computer Networks, 4th Edition - Page 13 preview image

PROBLEM SOLUTIONS FOR CHAPTER 211(−1 +1−3 +1−1−3 +1 +1)d(−1 +1−1 +1 +1 +1−1−1)/8 = 0(−1 +1−3 +1−1−3 +1 +1)d(−1 +1−1−1−1−1 +1−1)/8 = 1The result is thatAandDsent 1 bits,Bsent a 0 bit, andCwas silent.54.Ignoring speech compression, a digital PCM telephone needs 64 kbps. If wedivide 10 Gbps by 64 kbps we get 156,250 houses per cable. Current systemshave hundreds of houses per cable.55.It is both.Each of the 100 channels is assigned its own frequency band(FDM), and on each channel the two logical streams are intermixed by TDM.This example is the same as the AM radio example given in the text, but nei-ther is a fantastic example of TDM because the alternation is irregular.56.A 2-Mbps downstream bandwidth guarantee to each house implies at most 50houses per coaxial cable.Thus, the cable company will need to split up theexisting cable into 100 coaxial cables and connect each of them directly to afiber node.57.The upstream bandwidth is 37 MHz. Using QPSK with 2 bits/Hz, we get 74Mbps upstream.Downstream we have 200 MHz.Using QAM-64, this is1200 Mbps. Using QAM-256, this is 1600 Mbps.58.Even if the downstream channel works at 27 Mbps, the user interface isnearly always 10-Mbps Ethernet. There is no way to get bits to the computeranyfasterthan10-Mbpsunderthesecircumstances.Iftheconnectionbetween the PC and cable modem is fast Ethernet, then the full 27 Mbps maybe available. Usually, cable operators specify 10 Mbps Ethernet because theydo not want one user sucking up the entire bandwidth.SOLUTIONS TO CHAPTER 3 PROBLEMS1.Since each frame has a chance of 0.8 of getting through, the chance of thewhole message getting through is 0.810, which is about 0.107. Call this valuep. The expected number of transmissions for an entire message is thenE=i=1Σ∞ip(1−p)i−1=pi=1Σ∞i(1−p)i−1To reducethis, use the well-known formula for the sum of an infinitegeometric series,S=1=1Σ∞αi=1− α133333Differentiate both sides with respect toαto getS′ =i=1Σ∞iαi−1=(1− α)2133333333

Page 14 of 15

Solution Manual For Computer Networks, 4th Edition - Page 14 preview image

12PROBLEM SOLUTIONS FOR CHAPTER 3Now useα =1−pto getE=1/p.Thus, it takes an average of 1/0.107, orabout 9.3 transmissions.2.The solution is(a) 00000100 01000111 11100011 11100000 01111110(b) 01111110 01000111 11100011 11100000 11100000 11100000 0111111001111110(c) 01111110 01000111 110100011 111000000 011111010 011111103.After stuffing, we get A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D.4.If you could always count on an endless stream of frames, one flag byte mightbe enough. But what if a frame ends (with a flag byte) and there are no newframes for 15 minutes. How will the receiver know that the next byte is actu-ally the start of a new frame and not just noise on the line?The protocol ismuch simpler with starting and ending flag bytes.5.The output is 011110111110011111010.6.It is possible.Suppose that the original text containsthebit sequence01111110 as data.After bit stuffing, this sequence will be rendered as011111010.If the second 0 is lost due to a transmission error, what isreceived is 01111110, which the receiver sees as end of frame.It then looksjust before the end of the frame for the checksum and verifies it. If the check-sum is 16 bits, there is 1 chance in 216that it will accidentally be correct,leading to an incorrect frame being accepted.The longer the checksum, thelower the probability of an error getting through undetected, but the probabil-ity is never zero.7.If the propagation delay is very long, as in the case of a space probe on ornear Mars or Venus, forward error correction is indicated. It is also appropri-ate, in a military situation in which the receiver does not want to disclose hislocation by transmitting.If the error rate is low enough that an error-correcting code is good enough, it may also be simpler.Finally, real-timesystems cannot tolerate waiting for retransmissions.8.Making one change to any valid character cannot generate another valid char-acter due to the nature of parity bits. Making two changes to even bits or twochanges to odd bits will give another valid character, so the distance is 2.9.Parity bits are needed at positions 1, 2, 4, 8, and 16, so messages that do notextend beyond bit 31 (including the parity bits) fit. Thus, five parity bits aresufficient. The bit pattern transmitted is 01101011001100111010110.The encoded value is 101001001111.

Page 15 of 15

Solution Manual For Computer Networks, 4th Edition - Page 15 preview image

PROBLEM SOLUTIONS FOR CHAPTER 31311.If we number the bits from left to right starting at bit 1, in this example, bit 2(a parity bit) is incorrect.The 12-bit value transmitted (after Hammingencoding) was 0xA4F. The original 8-bit data value was 0xAF.12.A single error will cause both the horizontal and vertical parity checks to bewrong. Two errors will also be easily detected.If they are in different rows,the row parity will catch them. If they are in the same row, the column paritywill catch them. Three errors might slip by undetected, for example, if somebit is inverted along with its row and column parity bits. Even the corner bitwill not catch this.13.Describe an error pattern as a matrix ofnrows bykcolumns.Each of thecorrect bits is a 0, and each of the incorrect bits is a 1.With four errors perblock, each block will have exactly four 1s.How many such blocks arethere?There arenkways to choose where to put the first 1 bit,nk−1 waystochoosethesecond,andsoon,sothenumberofblocksisnk(nk−1)(nk−2)(nk−3).Undetected errors only occur when the four 1 bitsare at the vertices of a rectangle.Using Cartesian coordinates, every 1 bit isat a coordinate (x,y), where 0≤x < kand 0≤y < n.Suppose that the bitclosest to the origin (the lower-left vertex) is at (p,q). The number of legalrectangles is (k−p−1)(n−q−1). Then the total number of rectangles canbe found by summing this formula for all possiblepandq. The probability ofan undetected error is then the number of such rectangles divided by thenumber of ways to distribute the four bits:nk(nk−1)(nk−2)(nk−3)p=0Σk−2q=0Σn−2(k−p−1)(n−q−1)33333333333333333333333314.The remainder isx2+x+1.15.The frame is 10011101. The generator is 1001. The message after appendingthree zeros is 10011101000.The remainder on dividing 10011101000 by1001 is 100.So, the actualbit string transmitted is 10011101100. Thereceived bit stream with an error in the third bit from the left is 10111101100.Dividing this by 1001 produces a remainder 100, which is different from zero.Thus, the receiver detects the error and can ask for a retransmission.16.The CRC is computed during transmission and appended to the output streamas soon as the last bit goes out onto the wire. If the CRC were in the header,it would be necessary to make a pass over the frame to compute the CRCbefore transmitting. This would require each byte to be handled twice—oncefor checksumming and once for transmitting. Using the trailer cuts the workin half.

Preview Mode

This document has 47 pages. Sign in to access the full document!

Report

Learning Tools

Writing Tools

Browse Resources

Solution Manual For Computer Networks, 4th Edition - Page 1

Study Now!

Document Details

Related Documents

Solution Manual for Computer Networks, 6th Edition

Solution Manual For Computer Networks, 5th Edition

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Company

Explore

Study Tools