Skip to content
Textbook Guides

Solution Manual For Computer Networks, 5th Edition

Prepare for success with Solution Manual For Computer Networks, 5th Edition, providing textbook solutions that help you understand the material better.

Preview 16 of 52 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    COMPUTER NETWORKS FIFTH EDITION PROBLEM SOLUTIONS ANDREW S. TANENBAUM Vrije Universiteit Amsterdam, The Netherlands and DAVID J. WETHERALL University of Washington Seattle, WA

  2. Page 2
  3. Page 3
    Read page 3 as text

    PROBLEM SOLUTIONS 1 SOLUTIONS TO CHAPTER 1 PROBLEMS 1. The dog can carry 21 gigabytes, or 168 gigabits. A speed of 18 km/hour equals 0.005 km/sec. The time to travel distance x km is x /0. 005 = 200 x sec, yielding a data rate of 168/200 x Gbps or 840/ x Mbps. For x < 5. 6 km, the dog has a higher rate than the communication line. (i) If dog’s speed is doubled, maximum value of x is also doubled. (ii) If tape capacity is doubled, value of x is also doubled. (iii) If data rate of the transmission line is doubled, value of x is halved. 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) It is probably cheaper. It provides more computing power and better interactive in- terfaces. 3. A transcontinental fiber link might have many gigabits/sec of bandwidth, but the latency will also be high due to the speed of light propagation over thou- sands of kilometers. Similarly, a satellite link may run at megabits/sec but have a high latency to send a signal into orbit and back. In contrast, a 56-kbps modem calling a computer in the same building has low bandwidth and low latency. So do low-end local and personal area wireless techologies such as Zigbee. 4. A uniform delivery time is needed for voice as well as video, so the amount of jitter in the network is important. This could be expressed as the standard deviation of the delivery time. Having short delay but large variability is ac- tually worse than a somewhat longer delay and low variability. For financial transaction traffic, reliability and security are very important. 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 km of extra cable. If the client and server are separated by 5000 km, traversing even 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 air and vacuum is 300,000 km/sec, so the propagation delay alone is 160,000/300,000 sec or about 533 msec. 7. There is obviously no single correct answer here, but the following points seem 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, and social systems from being turned upside down every time a different party comes to power. Also, many people hold strong opinions on controversial

  4. Page 4
    Read page 4 as text

    2 PROBLEM SOLUTIONS FOR CHAPTER 1 social issues, without really knowing the facts of the matter. Allowing poorly reasoned opinions be to written into law may be undesirable. The potential ef- fects of advertising campaigns by special interest groups of one kind or anoth- er also have to be considered. Another major issue is security. A lot of people might worry about some 14-year kid hacking the system and falsifying the re- sults. 8. Call the routers A , B , C , D , and E . There are ten potential lines: AB , AC , AD , AE , BC , BD , BE , CD , CE , and DE . Each of these has four possibilities (three speeds or no line), so the total number of topologies is 4 10 = 1, 048, 576. At 100 ms each, it takes 104,857.6 sec, or slightly more than 29 hours to inspect them all. 9. Distinguish n + 2 events. Events 1 through n consist of the corresponding host successfully attempting to use the channel, i.e., without a collision. The prob- ability of each of these events is p (1 − p ) n − 1 . Event n + 1 is an idle channel, with probability (1 − p ) n . Event n + 2 is a collision. Since these n + 2 events are exhaustive, their probabilities must sum to unity. The probability of a col- lision, which is equal to the fraction of slots wasted, is then just 1 − np (1 − p ) n − 1 − (1 − p ) n . 10. Among other reasons for using layered protocols, using them leads to breaking up the design problem into smaller, more manageable pieces, and layering means that protocols can be changed without affecting higher or lower ones. One possible disadvantage is the performance of a layered system is likely to be worse than the performance of a monolithic system, although it is extremely difficult to implement and manage a monolithic system. 11. In the OSI protocol model, physical communication between peers takes place only in the lowest layer, not in every layer. 12. Message and byte streams are different. In a message stream, the network keeps track of message boundaries. In a byte stream, it does not. For ex- ample, suppose a process writes 1024 bytes to a connection and then a little later writes 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 each. With a byte stream, the message boundaries do not count and the re- ceiver will get the full 2048 bytes as a single unit. The fact that there were originally two distinct messages is lost. 13. Negotiation has to do with getting both sides to agree on some parameters or values to be used during the communication. Maximum packet size is one ex- ample, but there are many others. 14. The service shown is the service offered by layer k to layer k + 1. Another service that must be present is below layer k , namely, the service offered to layer k by the underlying layer k − 1.

  5. Page 5
    Read page 5 as text

    PROBLEM SOLUTIONS FOR CHAPTER 1 3 15. The probability, P k , of a frame requiring exactly k transmissions is the probability of the first k − 1 attempts failing, p k − 1 , times the probability of the k -th transmission succeeding, (1 − p ). The mean number of transmission is then just infinity k = 1 Σ kP k = infinity k = 1 Σ k (1 − p ) p k − 1 = 1 1 − p Or, more directly, if the probability of a message getting through is 1 − p then the expected number of transmissions per successful message is 1 / ( 1 − p ). 16. With n layers and h bytes added per layer, the total number of header bytes per message is hn , so the space wasted on headers is hn . The total message size is M + nh , so the fraction of bandwidth wasted on headers is hn /( M + hn ). This estimate does not take into account fragmentation (one higher layer message is sent as multiple lower layer messages) or aggregation (multiple higher layer messages are carried as one lower layer message) that may be present. If frag- mentation is used, it will raise the overhead. If aggregation is used, it will lower the overhead. 17. TCP is connection oriented, whereas UDP is a connectionless service. Alterna- tively, TCP provides a reliable service, whereas UDP provides an unreliable service. 18. Observe that many nodes are connected to three other nodes; the others are connected to more. Three bombs are needed to disconnect one of these nodes. By a quick check there does not appear to be a group of nodes that are con- nected to the rest of the network by fewer than three other nodes, so we con- clude that three bombs are needed to partition the network. For example, the two nodes in the upper-right corner can be disconnected from the rest by three bombs knocking out the three nodes to which they are connected. The system can withstand the loss of any two nodes. 19. Doubling every 18 months means a factor of four gain in 3 years. In 9 years, the gain is then 4 3 or 64, leading to 38.4 billion hosts. That sounds like a lot, but if every television, cellphone, camera, car, and appliance in the world is online, maybe it is plausible. It would require the average person to have dozens of hosts by then given that the estimate is much greater than the expected world population. 20. If the network tends to lose packets, it is better to acknowledge each one sepa- rately, so the lost packets can be retransmitted. On the other hand, if the net- work is highly reliable, sending one acknowledgement at the end of the entire transfer saves bandwidth in the normal case (but requires the entire file to be retransmitted if even a single packet is lost).

  6. Page 6
    Read page 6 as text

    4 PROBLEM SOLUTIONS FOR CHAPTER 1 21. Having mobile phone operators know the location of users lets the operators learn much personal information about users, such as where they sleep, work, travel and shop. This information might be sold to others or stolen; it could let the government monitor citizens. On the other hand, knowing the location of the user lets the operator send help to the right place in an emergency. It might also be used to deter fraud, since a person who claims to be you will usually be near your mobile phone. 22. 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 in time, during which it propagates 20 meters. Thus, a bit is 20 meters long here. 23. The image is 1600 × 1200 × 3 bytes or 5,760,000 bytes. This is 46,080,000 bits. At 56,000 bits/sec, it takes about 822.857 sec. At 1,000,000 bits/sec, it takes 46.080 sec. At 10,000,000 bits/sec, it takes 4.608 sec. At 100,000,000 bits/sec, it takes about 0.461 sec. At 1,000,000,000 bits/sec it takes about 46 msec. 24. Think about the hidden terminal problem. Imagine a wireless network of five stations, A through E , such that each one is in range of only its immediate neighbors. Then A can talk to B at the same time D is talking to E . Wireless networks have potential parallelism, and in this way differ from Ethernet. 25. One advantage is that if everyone uses the standard, everyone can talk to everyone. Another advantage is that widespread use of any standard will give it economies of scale, as with VLSI chips. A disadvantage is that the political compromises necessary to achieve standardization frequently lead to poor standards. Another disadvantage is that once a standard has been widely adop- ted, it is difficult to change,, even if new and better techniques or methods are discovered. Also, by the time it has been accepted, it may be obsolete. 26. There are many examples, of course. Some systems for which there is interna- tional standardization include DVD players and their discs, digital cameras and their storage cards, and automated teller machines and bank cards. Areas where such international standardization is lacking include broadcast televi- sion (NTSC in the U.S., PAL in parts of Europe, SECAM in other countries), lamps and lightbulbs (different voltages in different countries), electrical sock- ets and appliance plugs (every country does it differently), photocopiers and paper (8.5 x 11 inches in the U.S., A4 everywhere else), nuts and bolts (English versus metric pitch), etc. 27. This has no impact on the operations at layers k-1 or k+1. 28. There is no impact at layer k-1, but operations in k+1 have to be reimple- mented.

  7. Page 7
    Read page 7 as text

    PROBLEM SOLUTIONS FOR CHAPTER 1 5 29. One reason is request or response messages may get corrupted or lost during transmission, which will necessitate a retransmission delay. Another reason is the processing unit in the client may get overloaded processing several re- quests at once. Yet another reason is that the request or response messages may be queued in the network along with other messages. 30. Small-sized cells result in large header-to-payload overhead. Fixed-size cells result in wastage of unused bytes in the payload.

  8. Page 8
    Read page 8 as text

    6 PROBLEM SOLUTIONS FOR CHAPTER 2 SOLUTIONS TO CHAPTER 2 PROBLEMS 1. a n = − 1 π n , b n = 0, c = 1. 2. A noiseless channel can carry an arbitrarily large amount of information, no matter how often it is sampled. Just send a lot of data per sample. For the 4-kHz channel, make 8000 samples/sec. If each sample is 16 bits, the channel can send 128 kbps. If each sample is 1024 bits, the channel can send 8.2 Mbps. The key word here is ‘‘noiseless.’’ With a normal 4 kHz channel, the Shannon limit would not allow this. A signal-to-noise ratio of 30 dB means S/N = 1000. Using Eq. (2-3) with B = 4000 we get a maximum data rate of about 39.86 kbps. 3. Using the Nyquist theorem, we can sample 12 million times/sec. Four-level signals provide 2 bits per sample, for a total data rate of 24 Mbps. 4. A signal-to-noise ratio of 20 dB means S / N = 100. Since log 2 101 is about 6.658, the Shannon limit is about 19.975 kbps. The Nyquist limit is 6 kbps for a binary signal (with 1 bit per symbol). The bottleneck is therefore the Nyquist limit, giving a maximum channel capacity of 6 kbps. 5. To send a T1 signal we need H log 2 (1 + S / N ) = 1. 544 × 10 6 with H = 50, 000. This yields S / N = 2 30.88 − 1, which is about 93 dB. 6. Fiber has many advantages over copper. It can handle much higher bandwidth than copper. It is not affected by power surges, electromagnetic interference, power failures, or corrosive chemicals in the air. It does not leak light and is quite difficult to tap. Finally, it is thin and lightweight, resulting in much lower installation costs. There are some downsides of using fiber over copper. It can be damaged easily by being bent too much. And fiber interfaces cost more than electrical interfaces. 7. Use Eq. (2-4) to convert wavelengths of 1 micron plus/minus 0.05 microns to frequency. We have f low = 3 × 10 8 / (1. 05 × 10 − 6 ) = 3/1. 05 × 10 14 . Similarly f high = 3/0. 95 × 10 14 . Thus ∆ f = (3/0. 95 − 3/1. 05) × 10 14 = 3 × 10 13 . This is a bandwidth of 30,000 GHz. 8. The data rate is 2560 × 1600 × 24 × 60 bps, which is 5898 Mbps. For simpli- city, let us assume 1 bps per Hz, so that we require roughly 6 × 10 9 MHz of bandwidth. From Eq. (2-4) we can convert wavelengths to bandwidth. Let the wavelengths range from 1.3 microns to 1. 3 + λ microns. Then with Eq. (2-4) we have: 3 × 10 8 /1. 3 × 10 − 6 − 3 × 10 8 / [ (1. 3 + λ ) × 10 − 6 ] = 6 × 10 9 . Solv- ing, λ = 3. 3 × 10 − 5 microns. The range of wavelengths used is very short, even with slightly different assumptions.

  9. Page 9
    Read page 9 as text

    PROBLEM SOLUTIONS FOR CHAPTER 2 7 9. The Nyquist theorem is a property of mathematics and has nothing to do with technology. It says that if you have a function whose Fourier spectrum does not contain any sines or cosines above f , by sampling the function at a frequen- cy of 2 f you capture all the information there is. Thus, the Nyquist theorem is true for all media. 10. Start with λ f = c . We know that c is 3 × 10 8 m/s. For λ = 1 cm, we get 30 GHz. For λ = 5 m, we get 60 MHz. Thus, the band covered is 60 MHz to 30 GHz. 11. If the beam is off by 1 mm at the end, it misses the detector. This amounts to a triangle with base 100 m and height 0.001 m. The angle is one whose tangent is thus 0.00001. This angle is about 0.00057 degrees. 12. With 66/6 or 11 satellites per necklace, every 90 minutes 11 satellites pass overhead. This means there is a transit every 491 seconds. Thus, there will be a handoff about every 8 minutes and 11 seconds. 13. Transit time = 2 × (Altitude/Speed of light). The speed of light in air or vac- uum is 300,000 km/sec. This evaluates to 239 msec for GEO, 120 msec for MEO, and 5 msec for LEO satellites. 14. The call travels from the North Pole to the satellite directly overhead, and then transits through four other satellites to reach the satellite directly above the South Pole. Down it goes down to earth to the South Pole. The total distance traveled is 2 × 750 + 0. 5 × circumference at altitude 750 km. Circumfer- ence at altitude 750 km is 2 × π × (6371 + 750) = 44, 720 km. So, the total distance traveled is 23,860 km. Time to travel this distance = 23860/300000 = 79. 5 msec. In addition, switching occurs at six satellites. So, the total switching time is 60 u sec. So, the total latency is about 79.56 msec. 15. In NRZ, the signal completes a cycle at most every 2 bits (alternating 1s and 0s). So, the minimum bandwidth need to achieve B bits/sec data rate is B/2 Hz. In MLT-3, the signal completes a cycle at most every 4 bits (a sequence of 1s), thus requiring at least B /4 Hz to achieve B bits/sec data rate. Finally, in Manchester encoding, the signal completes a cycle in every bit, thus requiring at least B Hz to achieve B bits/sec data rate. 16. Since 4B/5B encoding uses NRZI, there is a signal transition every time a 1 is sent. Furthermore, the 4B/5B mapping (see Figure 2-21) ensures that a se- quence of consecutive 0s cannot be longer than 3. To see this, note that: i) no codeword has more than 2 consecutive zeros; ii) the longest leading sequence is 1 zero; and iii) the longest trailing sequence is 2 zeros. Combining ii and iii allows 3 consecutive 0s across two symbols. In this worst case, the transmitted bits will have a sequence 10001, resulting in a signal transition in 4 bits.

  10. Page 10
    Read page 10 as text

    8 PROBLEM SOLUTIONS FOR CHAPTER 2 17. The number of area codes was 8 × 2 × 10, which is 160. The number of pre- fixes was 8 × 8 × 10, or 640. Thus, the number of end offices was limited to 102,400. This limit is not a problem. 18. Each telephone makes 0.5 calls/hour at 6 minutes each. Thus, a telephone occupies a circuit for 3 minutes/hour. Twenty telephones can share a circuit, although having the load be close to 100% ( ρ = 1 in queuing terms) implies very long wait times. Since 10% of the calls are long distance, it takes 200 telephones to occupy a long-distance circuit full time. The interoffice trunk has 1,000,000/4000 = 250 circuits multiplexed onto it. With 200 telephones per circuit, an end office can support 200 × 250 = 50, 000 telephones. Sup- porting such a large number of telephones may result in significantly long wait times. For example, if 5,000 (10% of 50,000) users decide to make a long-dis- tance telephone call at the same time and each call lasts 3 minutes, the worst- case wait time will be 57 minutes. This will clearly result in unhappy custom- ers. 19. The cross-section of each strand of a twisted pair is π /4 square mm. A 10-km length of this material, with two strands per pair has a volume of 2 π /4 × 10 − 2 m 3 . This volume is about 15,708 cm 3 . With a specific gravity of 9.0, each local loop has a mass of 141 kg. The phone company thus owns 1. 4 × 10 9 kg of copper. At $6 each, the copper is worth about 8.5 billion dol- lars. 20. Like a single railroad track, it is half duplex. Oil can flow in either direction, but not both ways at once. A river is an example of a simplex connection while a walkie-talkie is another example of a half-duplex connection. 21. Traditionally, bits have been sent over the line without any error- correcting scheme in the physical layer. The presence of a CPU in each modem makes it possible to include an error-correcting code in layer 1 to greatly reduce the ef- fective error rate seen by layer 2. The error handling by the modems can be done totally transparently to layer 2. Many modems now have built-in error correction. While this significantly reduces the effective error rate seen at layer 2, errors at layer 2 are still possible. This can happen, for example, be- cause of loss of data as it is transferred from layer 1 to layer 2 due lack of buff- er space. 22. There are four legal values per baud, so the bit rate is twice the baud rate. At 1200 baud, the data rate is 2400 bps. 23. Since there are 32 symbols, 5 bits can be encoded. At 1200 baud, this provides 5 × 1200 = 6000 bps. 24. Two, one for upstream and one for downstream. The modulation scheme itself just uses amplitude and phase. The frequency is not modulated.

  11. Page 11
    Read page 11 as text

    PROBLEM SOLUTIONS FOR CHAPTER 2 9 25. There are 10 4000 Hz signals. We need nine guard bands to avoid any inter- ference. The minimum bandwidth required is 4000 × 10 + 400 × 9 = 43, 600 Hz. 26. A sampling time of 125 μ sec corresponds to 8000 samples per second. According to the Nyquist theorem, this is the sampling frequency needed to capture all the information in a 4-kHz channel, such as a telephone channel. (Actually the nominal bandwidth is less, but the cutoff is not sharp.) 27. With a modern T1 line, the end users get 8 × 24 = 192 of the 193 bits in a frame. (With older T1s only 7 of the 8 bits per channel could be used for data.) The overhead is therefore 1 / 193 = 0.5%. From Figure 2-41, percent overhead in OC-1 is (51.84 − 49.536)/51.84 = 3.63%. In OC-768, percent overhead is (39813.12 − 38043.648)/39813.12 = 4.44%. 28. In both cases 8000 samples/sec are possible. With QPSK encoding, 2 bits are sent per sample. With modern T1, 8 bits are sent per period. (With older T1s only 7 of the 8 bits could be used for data.) The respective data rates are 16 kbps and 64 kbps. 29. Ten frames. The probability of some random 10-bit pattern being 10 bits of the framing pattern (of 0101010101) on a digital channel) is 1/2 10 or 1/1024. This is the shortest number of frames for which the probability is less than 1/1000. 30. A coder accepts an arbitrary analog signal and generates a digital signal from it. A demodulator accepts a modulated sine wave only and generates a digital signal. 31. A drift rate of 10 − 9 means 1 second in 10 9 seconds or 1 nsec per second. At OC-1 speed, say, 50 Mbps, for simplicity, a bit lasts for 20 nsec. This means it takes only 20 seconds for the clock to drift off by 1 bit, and less for faster speeds. Consequently, the clocks must be continuously synchronized to keep them from getting too far apart. Certainly every 10 sec, preferably much more often. 32. The lowest bandwidth link (1 Mbps) is the bottleneck. The transmission time to send 1 GB at 1 Mbps is 1024 × 8 seconds. The one-way latency = 4 × (35800 / 300000) = 480 msec. Thus the total time is 1. 2 + 1024 × 8 + 0. 48 = 8193. 68 seconds. 33. The lowest bandwidth link (1 Mbps) is the bottleneck. With 64 KB packets there are 16 packets in a 1 GB file. This adds 16 × 32 = 512 bytes of headers to transmit. The transmission time is thus 1024. 5 × 8 seconds. The one-way latency is the propagation delay of 4 × (35800 / 300000) = 480 msec plus three switching times of 0.01 msec. Thus the total time is 1024. 5 × 8 + 0. 48 + 3 × 0. 00001 = 8196. 48003 seconds.

  12. Page 12
    Read page 12 as text

    10 PROBLEM SOLUTIONS FOR CHAPTER 2 34. Of the 90 columns, 86 are available for user data in OC-1. Thus, the user ca- pacity is 86 × 9 = 774 bytes/frame. With 8 bits/byte, 8000 frames/sec, and 3 OC-1 carriers multiplexed together, the total user capacity is 3 × 774 × 8 × 8000, or 148.608 Mbps. For an OC-3072 line: Gross data rate = 51. 84 × 3072 = 159252. 48 Mbps. SPE data rate = 50. 112 × 3072 = 153944. 064 Mbps. User data rate = 49. 536 × 3072 = 152174. 592 Mbps. 35. 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 accommodate 8000 frames/sec × 4 columns × 9 rows × 8 bits = 2.304 Mbps. It can be used to accommodate European CEPT-1 service. VT6 can accommodate 8000 frames/sec × 12 columns × 9 rows × 8 bits = 6.912 Mbps. It can be used to accommodate DS-2 service. 36. The OC-12c frames are 12 × 90 = 1080 columns of 9 rows. Of these, 12 × 3 = 36 columns are taken up by line and section overhead. This leaves an 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 8 bits, an OC-12c frame holds 75,096 user data bits. With 8000 frames/sec, the user data rate is 600.768 Mbps. 37. The three networks have the following properties: Star: best case = 2, average case = 2, worst case = 2. Ring: best case = 1, average case = n /4, worst case = n /2. Full interconnect: best case = 1, average case = 1, worst case = 1. 38. With circuit switching, at t = s the circuit is set up, at t = s + x / b the last bit is sent, at t = s + x / b + kd the message arrives. With packet switching, the last bit is sent at t = x / b . To get to the final destination, the last packet must be retransmitted k − 1 times by intermediate routers, with each retransmission taking p / b sec, so the total delay is x / b + ( k − 1) p / b + kd . Packet switching is faster if s > ( k − 1) p / b . In addition to the faster transmission under these conditions, packet switching is preferable when fault-tolerant transmission in the presence of switch failures is desired. 39. The total number of packets needed is x / p , so the total data + header traffic is ( p + h ) x / p bits. The source requires ( p + h ) x / pb sec to transmit these bits. The retransmissions of the last packet by the intermediate routers take up a total of ( k − 1)( p + h )/ b sec. Adding up the time for the source to send all the bits, plus the time for the routers to carry the last packet to the destination, thus clearing the pipeline, we get a total time of ( p + h ) x / pb + ( p + h )( k − 1)/ b sec. Minimizing this quantity with respect to p , we find p = √  hx /( k − 1).

  13. Page 13
    Read page 13 as text

    PROBLEM SOLUTIONS FOR CHAPTER 2 11 40. Each cell has six neighbors. If the central cell uses frequency group A , its six neighbors can use B , C , B , C , B , and C , respectively. In other words, only three unique cells are needed. Consequently, each cell can have 280 frequen- cies. 41. First, initial deployment simply placed cells in regions where there was a high density of human or vehicle population. Once they were there, the operators often did not want to go to the trouble of moving them. Second, antennas are typically placed on tall buildings or mountains. Depending on the exact loca- tion of such a structure, the area covered by a cell may be irregular due to obstacles near the transmitter. Third, some communities or property owners do not allow building a tower at a location where the center of a cell falls. In such cases, directional antennas are placed at a location not at the cell center. In the case of regular shapes, there is typically a buffer two cells wide where a frequency assigned to a cell is not reused in order to provide good separation and low interference. When the shapes of cells are irregular, the number of cells separating two cells that are using the same frequency is variable, de- pending on the width of the intermediate cells. This makes frequency assign- ment much more complicated. 42. If we assume that each microcell is a circle 100 m in diameter, each cell has an area of 2500 π . If we take the area of San Francisco, 1. 2 × 10 8 m 2 , and divide it by the area of 1 microcell, we get 15,279 microcells. Of course, it is impos- sible to tile the plane with circles (and San Francisco is decidedly three-dimen- sional), but with 20,000 microcells we could probably do the job. 43. Frequencies cannot be reused in adjacent cells, so when a user moves from one cell to another, a new frequency must be allocated for the call. If a user moves into a cell, all of whose frequencies are currently in use, the user’s call must be terminated. 44. The result is obtained by negating each of A , B , and C and then adding the three chip sequences. Alternatively, the three can be added and then negated. The result is (+3 +1 +1 − 1 − 3 − 1 − 1 +1). 45. 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 as mis- matches. Thus, two chip sequences are orthogonal if exactly half of the cor- responding elements match and exactly half do not match. 46. Just compute the four normalized inner products: ( − 1 +1 − 3 +1 − 1 − 3 +1 +1) • ( − 1 − 1 − 1 +1 +1 − 1 +1 +1)/8 = 1 ( − 1 +1 − 3 +1 − 1 − 3 +1 +1) • ( − 1 − 1 +1 − 1 +1 +1 +1 − 1)/8 = − 1 ( − 1 +1 − 3 +1 − 1 − 3 +1 +1) • ( − 1 +1 − 1 +1 +1 +1 − 1 − 1)/8 = 0 ( − 1 +1 − 3 +1 − 1 − 3 +1 +1) • ( − 1 +1 − 1 − 1 − 1 − 1 +1 − 1)/8 = 1

  14. Page 14
    Read page 14 as text

    12 PROBLEM SOLUTIONS FOR CHAPTER 2 The result is that A and D sent 1 bits, B sent a 0 bit, and C was silent. 47. Here are the chip sequences: (+1 +1 +1 +1 +1 +1 +1 +1) (+1 − 1 +1 − 1 +1 − 1 +1 − 1) (+1 +1 − 1 − 1 +1, +1 − 1 − 1) (+1 − 1 − 1 +1 +1 − 1 − 1 +1) 48. Ignoring speech compression, a digital PCM telephone needs 64 kbps. If we divide 10 Gbps by 64 kbps we get 156,250 houses per cable. Current systems have hundreds of houses per cable. 49. A 2-Mbps downstream bandwidth guarantee to each house implies at most 50 houses per coaxial cable. Thus, the cable company will need to split up the existing cable into 100 coaxial cables and connect each of them directly to a fiber node. 50. The upstream bandwidth is 37 MHz. Using QPSK with 2 bits/Hz, we get 74 Mbps upstream. Using QAM-128, this is 259 Mbps. Downstream we have 200 MHz. Using QAM-64, this is 1200 Mbps. Using QAM-256, this is 1600 Mbps. 51. The downstream data rate of a cable user is the smaller of the downstream cable bandwidth and the bandwidth of the communication medium between the cable modem and the user’s PC. If the downstream cable channel works at 27 Mbps, the downstream data rate of the cable user will be (a) 10 Mbps. (b) 27 Mbps. (c) 27 Mbps. This is assuming that the communication medium between cable modem and the user’s PC is not shared with any other user.

  15. Page 15
    Read page 15 as text

    PROBLEM SOLUTIONS FOR CHAPTER 3 13 SOLUTIONS TO CHAPTER 3 PROBLEMS 1. Since each frame has a chance of 0.8 of getting through, the chance of the whole message getting through is 0. 8 10 , which is about 0.107. Call this value p . The expected number of transmission attempts before successful reception is then E = 1/ p . Thus, it takes an average of 1/0.107, or about 9.3 transmis- sions. 2. The solution is (a) 00000101 01000111 11100011 11100000 01111110 (b) 01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110 (c) 01111110 01000111 110100011 111000000 011111010 01111110 3. After stuffing, we get A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D. 4. The maximum overhead occurs when the payload consists of only ESC and FLAG bytes. In this case, there will be 100% overhead. 5. If you could always count on an endless stream of frames, one flag byte might be enough. But what if a frame ends (with a flag byte) and there are no new frames for 15 minutes? How will the receiver know that the next byte is ac- tually the start of a new frame and not just noise on the line? The protocol is much simpler with starting and ending flag bytes. 6. The output is 011110111110011111010. 7. If the propagation delay is very long, as in the case of a space probe on or near Mars or Venus, forward error correction is indicated. It is also appropriate in a military situation in which the receiver does not want to disclose its location by transmitting. If the error rate is low enough that an error-correcting code is good enough, it may also be simpler. Finally, real-time systems cannot toler- ate 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 two changes 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 for messages that do not extend beyond 31 bits (including the parity bits). Our message has 16 data bits and 5 parity bits, for a total of 21 bits. Write this message ab 1 c 101 d 0011001 e 10101, from position 1 through 21 where a through e are the even parity bits. a is the sum of all positions with a 2 0 term except itself, or odd positions except 1. Thus a is 1 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 1 + 1 = 0. b is the sum of positions with a 2 1 term except 2, or positions 3, 6, 7, 10, 11, 14, 15, 18, and 19. b is 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 = 1. c is the sum of all other positions with a 2 2 term, or positions 5 to 7, 12 to 15, 20, and 21. c is 1 + 0 + 1 + 1 + 0 + 0 + 1 + 0 + 1 = 1. d is the sum of all other positions with a

  16. Page 16
    Read page 16 as text

    14 PROBLEM SOLUTIONS FOR CHAPTER 3 2 3 term, or positions 9 to 15. d is 0 + 0 + 1 + 1 + 0 + 0 + 1 = 1. e is the sum of all other positions with a 2 4 term, or positions 17 to 21. e is 1 + 0 + 1 + 0 + 1 = 1. The bit pattern transmitted is 011110110011001110101. 10. If we number the bits from left to right starting at bit 1, the received message was 111001001111. (Note that different bit orderings will give different answers.) The parity bits are at positions 1, 2, 4 and 8. Recomputing the parity sums, we find the syndrome to be 0010. (The 2 3 term is on the left, the 2 0 term is on the right.) This means that the bit in position 2, a parity bit, is incorrect. Flipping this bit, we get the 12-bit value transmitted (after Hamming de- coding) of 0xA4F. Removing the parity bits we get the original 8-bit data value of 0xAF. 11. A single error will cause both the horizontal and vertical parity checks to be wrong. 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 parity will catch them. Three errors will also be detected. If they are in the same row or column, that row’s or column’s parity will catch them. If two errors are in the same row, the column parity of at least one of them will catch the error. If two errors are in the same column, the row parity of at least one of them will catch the error. A 4-bit error in which the four error bits lie on the four corners of a rectangle cannot be caught since there are two errors in each row and col- umn. 12. From Eq. (3-1), we know that 10 check bits are needed for each block in case of using Hamming code. Total bits transmitted per block is 1010 bits. In case of error detection mechanism, one parity bit is transmitted per block. Suppose error rate is x per bit. However, a block may encounter a bit error 1000 x times. Every time an error is encountered, 1001 bits have to be retransmitted. So, total bits transmitted per block is 1001 + 1000 x × 1001 bits. For error detec- tion and retransmission to be better, 1001 + 1000 x × 1001 < 1010. So, the error rate must be less than 9 × 10 − 6 . 13. A block consists of n rows by k columns, or nk different positions. The num- ber of 4-bit errors is the number of ways we can choose 4 of these positions, ‘‘nk choose 4’’ or nk ( nk − 1)( nk − 2)( nk − 3) / 4! Undetected errors occur when the 4 errors are at the vertices of a rectangle. To compute how many undetected errors there are we want to know the number of ways we can choose two vertices that are neither in the same row nor column; the remaining two vertices of the rectangle are then fully determined. The first vertex can be any of the nk positions. The second vertex can be at any position in a different row and column, or ( n − 1)( k − 1) positions. There are nk ( n − 1)( k − 1) / 2 positions. The probability of an undetected 4-bit error is: 12( n − 1)( k − 1) ( nk − 1)( nk − 2)( nk − 3)

36 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.