COMPUTER NETWORKS

FIFTH EDITION

PROBLEM SOLUTIONS

ANDREW S. TANENBAUM
Vrije Universiteit
Amsterdam, The Netherlands

and

DAVID WETHERALL
University of Washington
Seattle, WA

PRENTICE HALL
Upper Saddle River, NJ
 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 = 200x sec,
yielding a data rate of 168 /200x 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
interfaces.
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
thousands of kilometers. In contrast, a 56-kbps modem calling a computer in
the same building has low bandwidth and low latency.
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
social issues, without really knowing the facts of the matter. Allowing poorly
reasoned opinions be to written into law may be undesirable. The potential
2 PROBLEM SOLUTIONS FOR CHAPTER 1

effects of advertising campaigns by special interest groups of one kind or an-

other 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 results.
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 410 = 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
probability 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 collision, 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 break-
ing 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 ISO protocol model, physical communication 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
example, 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.
 PROBLEM SOLUTIONS FOR CHAPTER 1 3
15. The probability, Pk , 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
∞ ∞ 1
k −1
Σ kP k = kΣ=1k (1 − p)p
k =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).
17. TCP is connection oriented, whereas UDP is a connectionless service.
18. 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 43 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. The average person may have dozens of hosts
by then.
20. If the network tends to lose packets, it is better to acknowledge each one sep-
arately, 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).
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
4 PROBLEM SOLUTIONS FOR CHAPTER 1

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
adopted, it is difficult to change,, even if new and better techniques or meth-
ods 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 inter-
national standardization include compact disc 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
VCRs and videotapes (NTSC VHS in the U.S., PAL VHS in parts of Europe,
SECAM VHS in other countries), portable telephones, lamps and lightbulbs
(different voltages in different countries), electrical sockets 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.
29. One reason is request or response messages may get corrupted or lost during
transmission. Another reason is the processing unit in the satellite may get
overloaded processing several requests from different clients.
30. Small-sized cells result in large header-to-payload overhead. Fixed-size cells
result in wastage of unused bytes in the payload.

SOLUTIONS TO CHAPTER 2 PROBLEMS

−1
1. an = , bn = 0, c = 1.
πn
 PROBLEM SOLUTIONS FOR CHAPTER 2 5
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. So, the Shannon limit is 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 log2 101 is about
6.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 channel ca-
pacity of 6 kbps.
5. To send a T1 signal we need Hlog2 (1 + S /N ) = 1.544 × 106 with H = 50,000.
This yields S /N = 230 − 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. First, it can be damaged easily by being bent too much. Second, opti-
cal communication is unidirectional, thus requiring either two fibers or two
frequency bands on one fiber for two-way communication. Finally, fiber in-
terfaces cost more than electrical interfaces.
7. Use Δ f = cΔλ / λ2 with Δλ = 10−7 meters and λ = 10−6 meters. This gives a
bandwidth (Δf) 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. From Eq. (2-3) we get Δλ = λ2 Δf /c. We
have Δf = 5.898 × 109 , so Δλ = 3.3 × 10−5 microns. The range of wave-
lengths used is very short.
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 fre-
quency of 2f 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 × 108 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.
6 PROBLEM SOLUTIONS FOR CHAPTER 2

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
vacuum 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 dis-
tance traveled is 2 × 750 + 0.5 × circumference at altitude 750 km. Cir-
cumference 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 usec. 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 requir-
ing 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. Thus, in the worst case, the
transmitted bits will have a sequence 10001, resulting in a signal transition in
4 bits.
17. The number of area codes was 8 × 2 × 10, which is 160. The number of
prefixes 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
 PROBLEM SOLUTIONS FOR CHAPTER 2 7
wait times. For example, if 5,000 (10% of 50,000) users decide to make a
long-distance 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 customers.
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 m3 . 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 × 109 kg of copper. At $6 each, the copper is worth about 8.4 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
effective 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
buffer 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 pro-
vides 5 × 1200 = 6000 bps.
24. Two, one for upstream and one for downstream. The modulation scheme it-
self just uses amplitude and phase. The frequency is not modulated.
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 somewhat less, but the cutoff is not
sharp.)
27. The end users get 7 × 24 = 168 of the 193 bits in a frame. The overhead is
therefore 25/193 = 13%. 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 −
8 PROBLEM SOLUTIONS FOR CHAPTER 2

38043.648)/39813.12 = 4.44%.
28. In both cases 8000 samples/sec are possible. With dibit encoding, 2 bits are
sent per sample. With T1, 7 bits are sent per period. The respective data
rates are 16 kbps and 56 kbps.
29. Ten frames. The probability of some random pattern being 0101010101 (on a
digital channel) is 1/1024.
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 109 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. 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.
One-way latency = 4 × (35800/300000) = 480 msec.
Total time = 1.2 + 233/220 + 0.48 = 8193.68 sec.
33. Again, the lowest-bandwidth link is the bottleneck.
Number of packets = 230/216 = 214.
One way latency = 480 + 3 × 0.001 = 480.003 msec.
Total bits transmitted = 233 + 214 * 28 = 233 + 222.
Total time = (233 + 222) / 220 + 0.48 = 8196.48 sec.
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,
 PROBLEM SOLUTIONS FOR CHAPTER 2 9
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) .
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 separa-
tion 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
10 PROBLEM SOLUTIONS FOR CHAPTER 2

assignment 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 × 108 m2 , and
divide it by the area of 1 microcell, we get 15,279 microcells. Of course, it is
impossible to tile the plane with circles (and San Francisco is decidedly
three-dimensional), 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
mismatches. Thus, two chip sequences are orthogonal if exactly half of the
corresponding 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
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.
 PROBLEM SOLUTIONS FOR CHAPTER 2 11
50. The upstream bandwidth is 37 MHz. Using QPSK with 2 bits/Hz, we get 74
Mbps upstream. 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. Usually, cable operators
specify 10-Mbps Ethernet because they do not want one user sucking up the
entire bandwidth.

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 transmissions for an entire message is then
∞ ∞
E= Σ ip (1 − p)i −1 = p Σ i(1 − p)i −1
i =1 i =1

To reduce this, use the well-known formula for the sum of an infinite
geometric series,
∞ 1
S= Σ αi =
1=1 1−α
Differentiate both sides with respect to α to get
∞ 1
S′ = Σ iαi −1 =
i =1 (1 − α)2

Now use α = 1 − p to get E = 1/p. Thus, it takes an average of 1/0.107, or

about 9.3 transmissions.
2. The solution is
(a) 00000100 01000111 11100011 11100000 01111110
(b) 01111110 01000111 11100011 11100000 11100000 11100000
01111110
12 PROBLEM SOLUTIONS FOR CHAPTER 3

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 ap-
propriate in a military situation in which the receiver does not want to dis-
close 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 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 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, so messages that do not
extend beyond bit 31 (including the parity bits) fit. Thus, 5 parity bits are suf-
ficient. The bit pattern transmitted is 011010110011001110101.
10. 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 Hamming en-
coding) was 0xA4F. The original 8-bit data value was 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.
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
 PROBLEM SOLUTIONS FOR CHAPTER 3 13
error rate is x per bit. However, a block may encounter a bit error 1000x
times. Every time an error is encountered, 1001 bits have to be retransmitted.
So, total bits transmitted per block is 1001 + 1000x × 1001 bits. For error de-
tection and retransmission to be better, 1001 + 1000x × 1001 < 1010. So, the
error rate must be less than 9 × 10−6 .
13. Describe an error pattern as a matrix of n rows by k columns. Each of the
correct bits is a 0, and each of the incorrect bits is a 1. With four errors per
block, each block will have exactly four 1s. How many such blocks are
there? There are nk ways to choose where to put the first 1 bit, nk − 1 ways
to choose the second, and so on, so the number of blocks is
nk (nk − 1)(nk − 2)(nk − 3). Undetected errors only occur when the four 1
bits are at the vertices of a rectangle. Using Cartesian coordinates, every 1 bit
is at a coordinate (x, y ), where 0 ≤ x < k and 0 ≤ y < n. Suppose that the bit
closest to the origin (the lower-left vertex) is at (p, q). The number of legal
rectangles is (k − p − 1)(n − q − 1). The total number of rectangles can be
found by summing this formula for all possible p and q. The probability of an
undetected error is then the number of such rectangles divided by the number
of ways to distribute the 4 bits:
k −2n −2
Σ Σ (k − p − 1)(n − q − 1)
p =0q =0
nk (nk − 1)(nk − 2)(nk − 3)

14. When the first 1 goes in, 11 comes out and S 1 stores the 1. Then 0 goes in
and 01 comes out, with S 2 now storing a 1 and S 1 storing the 0. The complete
output sequence, including these initial values is 11 01 00 10 10 00 11 00.
15. To obtain the checksum, we need to calculate the ones complement sum of
words, which is same as sum modulo 24 and adding any overflow of high
order bits back into low-order bits:
0011 + 1010 = 1101
1101 + 1100 = 1001 + 1 = 1010
1010 + 1001 = 0011 + 1 = 1100.
So, the Internet checksum is 1100.
16. The remainder is x 2 + x + 1.
17. The frame is 10011101. The generator is 1001. The message after appending
three zeros is 10011101000. The remainder on dividing 10011101000 by
1001 is 100. So, the actual bit string transmitted is 10011101100. The re-
ceived bit stream with an error in the third bit from the left is 10111101100.
Dividing this by 1001 produces a remainder of 100, which is different from 0.
Thus, the receiver detects the error and can ask for a retransmission. If the
14 PROBLEM SOLUTIONS FOR CHAPTER 3

transmitted bit stream is converted to any multiple of 1001, the error will not
be detected. A trivial example is if all ones in the bit stream are inverted to
zeros.
18. The CRC checksum polynomial is or degree 32, so (a) Yes. CRC catches all
single-bit errors.
(b) Yes. CRC catches all double-bit errors for any reasonably long message.
(c) No. CRC may not be able catch all even number of isolated bit errors.
(d) Yes. CRC catches all odd number of isolated bit errors.
(e) Yes. CRC catches all burst errors with burst lengths less than or equal to
32.
(f) No. CRC may not be able to catch a burst error with burst length greater
than 32.
19. Yes, it is possible. The reason is that an acknowledgement frame may arrive
correctly, but after the sender’s timer has expired. This can happen if the re-
ceiver gets delayed in sending the acknowledgement frame, because its CPU
is overloaded processing other jobs in the system.
20. Efficiency will be 50% when the time required to transmit the frame equals
the round-trip propagation delay. At a transmission rate of 4 bits/msec, 160
bits takes 40 mssec. For frame sizes above 160 bits, stop-and-wait is rea-
sonably efficient.
21. It can happen. Suppose that the sender transmits a frame and a garbled ac-
knowledgement comes back quickly. The main loop will be executed a sec-
ond time and a frame will be sent while the timer is still running.
22. To operate efficiently, the sequence space (actually, the sender’s window
size) must be large enough to allow the transmitter to keep transmitting until
the first acknowledgement has been received. The propagation time is 18 ms.
At T1 speed, which is 1.536 Mbps (excluding the 1 header bit), a 64-byte
frame takes 0.300 msec. Therefore, the first frame fully arrives 18.3 msec
after its transmission was started. The acknowledgement takes another 18
msec to get back, plus a small (negligible) time for the acknowledgement to
arrive fully. In all, this time is 36.3 msec, so the transmitter must have
enough window space to keep going for 36.3 msec. A frame takes 0.3 ms, so
it takes 121 frames to fill the pipe. Seven-bit sequence numbers are needed.
23. Let the sender’s window be (Sl , Su ) and the receiver’s be (Rl , Ru ). Let the
window size be W. The relations that must hold are:
0 ≤ Su − Sl + 1 ≤ W1
Ru − Rl + 1 = W
Sl ≤ R l ≤ Su + 1
 PROBLEM SOLUTIONS FOR CHAPTER 3 15
24. The protocol would be incorrect. Suppose that 3-bit sequence numbers are in
use. Consider the following scenario:
A just sent frame 7.
B gets the frame and sends a piggybacked ACK .
A gets the ACK and sends frames 0–6, all of which get lost.
B times out and retransmits its current frame, with the ACK 7.
Look at the situation at A when the frame with r.ack = 7 arrives. The key
variables are AckExpected = 0, r.ack = 7, and NextFrameToSend = 7. The
modified between would return true, causing A to think the lost frames were
being acknowledged.
25. Yes. It might lead to deadlock. Suppose that a batch of frames arrived cor-
rectly and was accepted. The receiver would advance its window. Now sup-
pose that all the acknowledgements were lost. The sender would eventually
time out and send the first frame again. The receiver would then send a NAK.
If this packet were lost, from that point on, the sender would keep timing out
and sending a frame that had already been accepted, but the receiver would
just ignore it. Setting the auxiliary timer results in a correct acknowledge-
ment being sent back eventually instead, which resynchronizes.
26. It would lead to deadlock because this is the only place that incoming ac-
knowledgements are processed. Without this code, the sender would keep
timing out and never make any progress.
27. Link utilization = (1/(1 + 2BD ))
BD = bandwidth-delay product / frame size
delay = (9 × 1010)/(3 × 108) = 300 sec
bandwidth-delay product = 64 ×300 = 19.2 Gb
BD = 19200000 / 256 = 75000
So, link utilization is 6.67 × 10−4 %
28. For a send window size w, link utilization is w/ (1 + 2BD ). So, for 100% link
utilization, w = 150001.
29. Consider the following scenario. A sends 0 to B. B gets it and sends an ACK,
but the ACK gets lost. A times out and repeats 0, but now B expects 1, so it
sends a NAK . If A merely resent r.ack + 1, it would be sending frame 1,
which it has not gotten yet.
30. Suppose A sent B a frame that arrived correctly, but there was no reverse traf-
fic. After a while A would time out and retransmit. B would notice that the
sequence number was incorrect, since it would be below FrameExpected .
Consequently, it would send a NAK , which carries an acknowledgement num-
ber. Each frame would be sent exactly two times.
16 PROBLEM SOLUTIONS FOR CHAPTER 3

31. No. This implementation fails. With MaxSeq = 4, we get NrBufs = 2. The
even sequence numbers use buffer 0 and the odd ones use buffer 1. This
mapping means that frames 4 and 0 both use the same buffer. Suppose that
frames 0–3 are received and acknowledged. The receiver’s window now con-
tains 4 and 0. If 4 is lost and 0 arrives, it will be put in buffer 0 and
arrived [0] will be set to true. The loop in the code for FrameArrival will be
executed once, and an out-of-order message will be delivered to the host.
This protocol requires MaxSeq to be odd to work properly. However, other
implementations of sliding window protocols do not all have this property.
32. Let t = 0 denote the start of transmission. At t = 1 msec, the first frame has
been fully transmitted. At t = 271 msec, the first frame has fully arrived. At
t = 272 msec, the frame acknowledging the first one has been fully sent. At
t = 542 msec, the acknowledgement-bearing frame has fully arrived. Thus,
the cycle is 542 msec. A total of k frames are sent in 542 msec, for an effi-
ciency of k /542. Hence, for
(a) k = 1, efficiency = 1/542 = 0.18%.
(b) k = 7, efficiency = 7/542 = 1.29%.
(c) k = 4, efficiency = 4/542 = 0.74%.
33. With a 50-kbps channel and 8-bit sequence numbers, the pipe is always full.
The number of retransmissions per frame is about 0.01. Each good frame
wastes 40 header bits, plus 1% of 4000 bits (retransmission), plus a 40-bit
NAK once every 100 frames. The total overhead is 80.4 bits per 3960 data
bits, giving 80.4 /(3960 + 80.4) = 1.99%.
34. The transmission starts at t = 0. At t = 4096/64000 sec = 64 msec, the last bit
is sent. At t = 334 msec, the last bit arrives at the satellite and the very short
ACK is sent. At t = 604 msec, the ACK arrives at the earth. The data rate
here is 4096 bits in 604 msec, or about 6781 bps. With a window size of 7
frames, transmission time is 448 msec for the full window, at which time the
sender has to stop. At 604 msec, the first ACK arrives and the cycle can start
again. Here we have 7 × 4096 = 28,672 bits in 604 msec. The data rate is
47,470.2 bps. Continuous transmission can only occur if the transmitter is
still sending when the first ACK gets back at t = 604 msec. In other words, if
the window size is greater than 604 msec worth of transmission, it can run at
full speed. For a window size of 10 or greater this condition is met, so for
any window size of 10 or greater (e.g., 15 or 127) the data rate is 64 kbps.
35. The propagation speed in the cable is 200,000 km/sec, or 200 km/msec, so a
100-km cable will be filled in 500 µsec. Each T1 frame is 193 bits sent in
125 µsec. This corresponds to four frames, or 772 bits on the cable.
 PROBLEM SOLUTIONS FOR CHAPTER 3 17
36. PPP was clearly designed to be implemented in software, not in hardware as
bit-stuffing protocols such as HDLC nearly always are. With a software im-
plementation, working entirely with bytes is much simpler than working with
individual bits. In addition, PPP was designed to be used with modems, and
modems accept and transmit data in units of 1 byte, not 1 bit.
37. At its smallest, each frame has 2 flag bytes, 1 protocol byte, and 2 checksum
bytes, for a total of 5 overhead bytes per frame. For maximum overhead, 2
flag bytes, 1 byte each for address and control, 2 bytes for protocol and 4
bytes for checksum. This totals to 10 overhead bytes.
38. The AAL5 frame will consist of 2 PPP protcol bytes, 100 PPP payload bytes,
some padding bytes, and 8 trailer bytes. To make this frame size a multiple of
48, the number of padding bytes will be 34. This will result in an AAL5
frame of size 144 bytes. This can fit in three ATM cells. The first ATM cell
will contain the 2 PPP protcol bytes and 46 bytes of the IP packet, the second
cell will contain the next 48 bytes of the IP packet, and finally, the third ATM
cell will contain the last 6 bytes of IP packet, 34 padding bytes, and 8 AAL5
trailer bytes.

SOLUTIONS TO CHAPTER 4 PROBLEMS

1. The formula is the standard formula for Markov queueing given in Sec.
4.1.1, namely, T = 1/(µC − λ). Here, C = 108 and µ = 10−4 , so
T = 1/(10000 − lambda) sec. For the three arrival rates, we get (a) 0.1 msec,
(b) 0.11 msec, and (c) 1 msec. For case (c) we are operating a queueing sys-
tem with ρ = λ/µC = 0.9, which gives the 10× delay.
2. With pure ALOHA, the usable bandwidth is 0.184 × 56 kbps = 10.3 kbps.
Each station requires 10 bps, so N = 10300 /10 = 1030 stations.
3. With pure ALOHA, transmission can start instantly. At low load, no collis-
ions are expected so the transmission is likely to be successful. With slotted
ALOHA, it has to wait for the next slot. This introduces half a slot time of
delay.
4. (a) With G = 2 Poisson’s Law gives a probability of e −2 .
(b) (1 − e −G )k e −G = 0.135 × 0.865k .
(c) The expected number of transmissions is e G = 7.4.
5. The number of transmissions is E = e G . The E events are separated by E − 1
intervals of four slots each, so the delay is 4(e G − 1). The throughput is given
by S = Ge −G . Thus, we have two parametric equations, one for delay and one
for throughput, both in terms of G. For each G value, it is possible to find the
corresponding delay and throughput, yielding one point on the curve.
18 PROBLEM SOLUTIONS FOR CHAPTER 4

6. (a) Signal propagation speed in twin lead is 2.46 × 108 m/sec. Signal propa-
gation time for 2 km is 8.13 µsec. So, the length of contention slot is 16.26
µsec. (b) Signal propagation speed in multimode fiber is 1.95 × 108 m/s. Sig-
nal propagation time for 40 km is 205.13 µsec. So, the length of contention
slot is 410.26 µsec.
7. The worst case is where all stations want to send and s is the lowest-num-
bered station. Wait time N bit contention period + (N − 1) × d bit for trans-
mission of frames. The total is N + (N − 1)d bit times.
8. If a higher-numbered station and a lower-numbered station have packets to
send at the same time, the higher-numbered station will always win the bid.
Thus, a lower-numbered station will be starved from sending its packets if
there is a continuous stream of higher-numbered stations ready to send their
packets.
9. Stations 2, 3, 5, 7, 11, and 13 want to send. Eleven slots are needed, with the
contents of each slot being as follows:
Slot 1: 2, 3, 5, 7, 11, 13
Slot 2: 2, 3, 5, 7
Slot 3: 2, 3
Slot 4: 2
Slot 5: 3
Slot 6: 5, 7
Slot 7: 5
Slot 8: 7
Slot 9: 11, 13
Slot 10: 11
Slot 11: 13

10. (a) Since all stations will see A’s packet, it will interfere with receipt of any
other packet by any other station. So, no other communication is possible in
this case.
(b) B/s packet will be seen by E, A and C, by not by D. Thus, E can send to
D, or A can send to D, or C can send to D at the same time.
(c) This scenario is same as (b).
11. Yes. Imagine that they are in a straight line and that each station can reach
only its nearest neighbors. Then A can send to B while E is sending to F.
12. (a) Number the floors 1–7. In the star configuration, the router is in the mid-
dle of floor 4. Cables are needed to each of the 7 × 15 − 1 = 104 sites. The
total length of these cables is
7 15
4Σ Σ √(i − 4)
2
+ (j − 8)2
i =1 j =1
 PROBLEM SOLUTIONS FOR CHAPTER 2 11
50. The upstream bandwidth is 37 MHz. Using QPSK with 2 bits/Hz, we get 74
Mbps upstream. 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. Usually, cable operators
specify 10-Mbps Ethernet because they do not want one user sucking up the
entire bandwidth.

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 transmissions for an entire message is then
∞ ∞
i −1 i −1
 E= Σ ip (1 − p) = p Σ i(1 − p)
i =1 i =1

To reduce this, use the well-known formula for the sum of an infinite
geometric series,
∞ 1
S= Σ
1=1
αi =
1−α
Differentiate both sides with respect to α to get
∞ 1
S′ = Σ iαi −1 =
i =1 (1 − α)2

Now use α = 1 − p to get E = 1/p. Thus, it takes an average of 1/0.107, or

about 9.3 transmissions.
2. The solution is
(a) 00000100 01000111 11100011 11100000 01111110
(b) 01111110 01000111 11100011 11100000 11100000 11100000
01111110
12 PROBLEM SOLUTIONS FOR CHAPTER 3

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 ap-
propriate in a military situation in which the receiver does not want to dis-
close 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 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 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, so messages that do not
extend beyond bit 31 (including the parity bits) fit. Thus, 5 parity bits are suf-
ficient. The bit pattern transmitted is 011010110011001110101.
10. 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 Hamming en-
coding) was 0xA4F. The original 8-bit data value was 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.
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
PROBLEM SOLUTIONS FOR CHAPTER 3 13
 error rate is x per bit. However, a block may encounter a bit error 1000x
times. Every time an error is encountered, 1001 bits have to be retransmitted.
So, total bits transmitted per block is 1001 + 1000x × 1001 bits. For error de-
tection and retransmission to be better, 1001 + 1000x × 1001 < 1010. So, the
error rate must be less than 9 × 10−6 .
13. Describe an error pattern as a matrix of n rows by k columns. Each of the
correct bits is a 0, and each of the incorrect bits is a 1. With four errors per
block, each block will have exactly four 1s. How many such blocks are
there? There are nk ways to choose where to put the first 1 bit, nk − 1 ways
to choose the second, and so on, so the number of blocks is
nk (nk − 1)(nk − 2)(nk − 3). Undetected errors only occur when the four 1
bits are at the vertices of a rectangle. Using Cartesian coordinates, every 1 bit
is at a coordinate (x, y ), where 0 ≤ x < k and 0 ≤ y < n. Suppose that the bit
closest to the origin (the lower-left vertex) is at (p, q). The number of legal
rectangles is (k − p − 1)(n − q − 1). The total number of rectangles can be
found by summing this formula for all possible p and q. The probability of an
undetected error is then the number of such rectangles divided by the number
of ways to distribute the 4 bits:
k −2n −2
Σ Σ (k − p − 1)(n − q − 1)
p =0q =0
nk (nk − 1)(nk − 2)(nk − 3)

14. When the first 1 goes in, 11 comes out and S 1 stores the 1. Then 0 goes in
and 01 comes out, with S 2 now storing a 1 and S 1 storing the 0. The complete
output sequence, including these initial values is 11 01 00 10 10 00 11 00.
15. To obtain the checksum, we need to calculate the ones complement sum of
words, which is same as sum modulo 24 and adding any overflow of high
order bits back into low-order bits:
0011 + 1010 = 1101
1101 + 1100 = 1001 + 1 = 1010
1010 + 1001 = 0011 + 1 = 1100.
So, the Internet checksum is 1100.
16. The remainder is x 2 + x + 1.
17. The frame is 10011101. The generator is 1001. The message after appending
three zeros is 10011101000. The remainder on dividing 10011101000 by
1001 is 100. So, the actual bit string transmitted is 10011101100. The re-
ceived bit stream with an error in the third bit from the left is 10111101100.
Dividing this by 1001 produces a remainder of 100, which is different from 0.
Thus, the receiver detects the error and can ask for a retransmission. If the
14 PROBLEM SOLUTIONS FOR CHAPTER 3

transmitted bit stream is converted to any multiple of 1001, the error will not
be detected. A trivial example is if all ones in the bit stream are inverted to
zeros.
18. The CRC checksum polynomial is or degree 32, so (a) Yes. CRC catches all
single-bit errors.
(b) Yes. CRC catches all double-bit errors for any reasonably long message.
(c) No. CRC may not be able catch all even number of isolated bit errors.
(d) Yes. CRC catches all odd number of isolated bit errors.
(e) Yes. CRC catches all burst errors with burst lengths less than or equal to
32.
(f) No. CRC may not be able to catch a burst error with burst length greater
than 32.
19. Yes, it is possible. The reason is that an acknowledgement frame may arrive
correctly, but after the sender’s timer has expired. This can happen if the re-
ceiver gets delayed in sending the acknowledgement frame, because its CPU
is overloaded processing other jobs in the system.
20. Efficiency will be 50% when the time required to transmit the frame equals
the round-trip propagation delay. At a transmission rate of 4 bits/msec, 160
bits takes 40 mssec. For frame sizes above 160 bits, stop-and-wait is rea-
sonably efficient.
21. It can happen. Suppose that the sender transmits a frame and a garbled ac-
knowledgement comes back quickly. The main loop will be executed a sec-
ond time and a frame will be sent while the timer is still running.
22. To operate efficiently, the sequence space (actually, the sender’s window
size) must be large enough to allow the transmitter to keep transmitting until
the first acknowledgement has been received. The propagation time is 18 ms.
At T1 speed, which is 1.536 Mbps (excluding the 1 header bit), a 64-byte
frame takes 0.300 msec. Therefore, the first frame fully arrives 18.3 msec
after its transmission was started. The acknowledgement takes another 18
msec to get back, plus a small (negligible) time for the acknowledgement to
arrive fully. In all, this time is 36.3 msec, so the transmitter must have
enough window space to keep going for 36.3 msec. A frame takes 0.3 ms, so
it takes 121 frames to fill the pipe. Seven-bit sequence numbers are needed.
23. Let the sender’s window be (Sl , Su ) and the receiver’s be (Rl , Ru ). Let the
window size be W. The relations that must hold are:
0 ≤ Su − Sl + 1 ≤ W1
Ru − Rl + 1 = W
Sl ≤ R l ≤ Su + 1
 PROBLEM SOLUTIONS FOR CHAPTER 3 15
24. The protocol would be incorrect. Suppose that 3-bit sequence numbers are in
use. Consider the following scenario:
A just sent frame 7.
B gets the frame and sends a piggybacked ACK .
A gets the ACK and sends frames 0–6, all of which get lost.
B times out and retransmits its current frame, with the ACK 7.
Look at the situation at A when the frame with r.ack = 7 arrives. The key
variables are AckExpected = 0, r.ack = 7, and NextFrameToSend = 7. The
modified between would return true, causing A to think the lost frames were
being acknowledged.
25. Yes. It might lead to deadlock. Suppose that a batch of frames arrived cor-
rectly and was accepted. The receiver would advance its window. Now sup-
pose that all the acknowledgements were lost. The sender would eventually
time out and send the first frame again. The receiver would then send a NAK.
If this packet were lost, from that point on, the sender would keep timing out
and sending a frame that had already been accepted, but the receiver would
just ignore it. Setting the auxiliary timer results in a correct acknowledge-
ment being sent back eventually instead, which resynchronizes.
26. It would lead to deadlock because this is the only place that incoming ac-
knowledgements are processed. Without this code, the sender would keep
timing out and never make any progress.
27. Link utilization = (1/(1 + 2BD ))
BD = bandwidth-delay product / frame size
delay = (9 × 1010)/(3 × 108) = 300 sec
bandwidth-delay product = 64 ×300 = 19.2 Gb
BD = 19200000 / 256 = 75000
So, link utilization is 6.67 × 10−4 %
28. For a send window size w, link utilization is w/ (1 + 2BD ). So, for 100% link
utilization, w = 150001.
29. Consider the following scenario. A sends 0 to B. B gets it and sends an ACK,
but the ACK gets lost. A times out and repeats 0, but now B expects 1, so it
sends a NAK . If A merely resent r.ack + 1, it would be sending frame 1,
 which it has not gotten yet.
30. Suppose A sent B a frame that arrived correctly, but there was no reverse traf-
fic. After a while A would time out and retransmit. B would notice that the
sequence number was incorrect, since it would be below FrameExpected .
Consequently, it would send a NAK , which carries an acknowledgement num-
ber. Each frame would be sent exactly two times.
16 PROBLEM SOLUTIONS FOR CHAPTER 3

31. No. This implementation fails. With MaxSeq = 4, we get NrBufs = 2. The
even sequence numbers use buffer 0 and the odd ones use buffer 1. This
mapping means that frames 4 and 0 both use the same buffer. Suppose that
frames 0–3 are received and acknowledged. The receiver’s window now con-
tains 4 and 0. If 4 is lost and 0 arrives, it will be put in buffer 0 and
arrived [0] will be set to true. The loop in the code for FrameArrival will be
executed once, and an out-of-order message will be delivered to the host.
This protocol requires MaxSeq to be odd to work properly. However, other
implementations of sliding window protocols do not all have this property.
32. Let t = 0 denote the start of transmission. At t = 1 msec, the first frame has
been fully transmitted. At t = 271 msec, the first frame has fully arrived. At
t = 272 msec, the frame acknowledging the first one has been fully sent. At
t = 542 msec, the acknowledgement-bearing frame has fully arrived. Thus,
the cycle is 542 msec. A total of k frames are sent in 542 msec, for an effi-
ciency of k /542. Hence, for
(a) k = 1, efficiency = 1/542 = 0.18%.
(b) k = 7, efficiency = 7/542 = 1.29%.
(c) k = 4, efficiency = 4/542 = 0.74%.
33. With a 50-kbps channel and 8-bit sequence numbers, the pipe is always full.
The number of retransmissions per frame is about 0.01. Each good frame
wastes 40 header bits, plus 1% of 4000 bits (retransmission), plus a 40-bit
NAK once every 100 frames. The total overhead is 80.4 bits per 3960 data
bits, giving 80.4 /(3960 + 80.4) = 1.99%.
34. The transmission starts at t = 0. At t = 4096/64000 sec = 64 msec, the last bit
is sent. At t = 334 msec, the last bit arrives at the satellite and the very short
ACK is sent. At t = 604 msec, the ACK arrives at the earth. The data rate
here is 4096 bits in 604 msec, or about 6781 bps. With a window size of 7
frames, transmission time is 448 msec for the full window, at which time the
sender has to stop. At 604 msec, the first ACK arrives and the cycle can start
again. Here we have 7 × 4096 = 28,672 bits in 604 msec. The data rate is
47,470.2 bps. Continuous transmission can only occur if the transmitter is
still sending when the first ACK gets back at t = 604 msec. In other words, if
the window size is greater than 604 msec worth of transmission, it can run at
full speed. For a window size of 10 or greater this condition is met, so for
any window size of 10 or greater (e.g., 15 or 127) the data rate is 64 kbps.
35. The propagation speed in the cable is 200,000 km/sec, or 200 km/msec, so a
100-km cable will be filled in 500 µsec. Each T1 frame is 193 bits sent in
125 µsec. This corresponds to four frames, or 772 bits on the cable.
 PROBLEM SOLUTIONS FOR CHAPTER 3 17
36. PPP was clearly designed to be implemented in software, not in hardware as
bit-stuffing protocols such as HDLC nearly always are. With a software im-
plementation, working entirely with bytes is much simpler than working with
individual bits. In addition, PPP was designed to be used with modems, and
modems accept and transmit data in units of 1 byte, not 1 bit.
37. At its smallest, each frame has 2 flag bytes, 1 protocol byte, and 2 checksum
bytes, for a total of 5 overhead bytes per frame. For maximum overhead, 2
flag bytes, 1 byte each for address and control, 2 bytes for protocol and 4
bytes for checksum. This totals to 10 overhead bytes.
38. The AAL5 frame will consist of 2 PPP protcol bytes, 100 PPP payload bytes,
some padding bytes, and 8 trailer bytes. To make this frame size a multiple of
48, the number of padding bytes will be 34. This will result in an AAL5
frame of size 144 bytes. This can fit in three ATM cells. The first ATM cell
will contain the 2 PPP protcol bytes and 46 bytes of the IP packet, the second
cell will contain the next 48 bytes of the IP packet, and finally, the third ATM
cell will contain the last 6 bytes of IP packet, 34 padding bytes, and 8 AAL5
trailer bytes.

SOLUTIONS TO CHAPTER 4 PROBLEMS

1. The formula is the standard formula for Markov queueing given in Sec.
4.1.1, namely, T = 1/(µC − λ). Here, C = 108 and µ = 10−4 , so
T = 1/(10000 − lambda) sec. For the three arrival rates, we get (a) 0.1 msec,
(b) 0.11 msec, and (c) 1 msec. For case (c) we are operating a queueing sys-
tem with ρ = λ/µC = 0.9, which gives the 10× delay.
2. With pure ALOHA, the usable bandwidth is 0.184 × 56 kbps = 10.3 kbps.
Each station requires 10 bps, so N = 10300 /10 = 1030 stations.
3. With pure ALOHA, transmission can start instantly. At low load, no collis-
ions are expected so the transmission is likely to be successful. With slotted
ALOHA, it has to wait for the next slot. This introduces half a slot time of
delay.
4. (a) With G = 2 Poisson’s Law gives a probability of e −2 .
(b) (1 − e −G )k e −G = 0.135 × 0.865k .
(c) The expected number of transmissions is e G = 7.4.
5. The number of transmissions is E = e G . The E events are separated by E − 1
intervals of four slots each, so the delay is 4(e G − 1). The throughput is given
by S = Ge −G . Thus, we have two parametric equations, one for delay and one
for throughput, both in terms of G. For each G value, it is possible to find the
corresponding delay and throughput, yielding one point on the curve.
18 PROBLEM SOLUTIONS FOR CHAPTER 4

6. (a) Signal propagation speed in twin lead is 2.46 × 108 m/sec. Signal propa-
gation time for 2 km is 8.13 µsec. So, the length of contention slot is 16.26
µsec. (b) Signal propagation speed in multimode fiber is 1.95 × 108 m/s. Sig-
nal propagation time for 40 km is 205.13 µsec. So, the length of contention
slot is 410.26 µsec.
7. The worst case is where all stations want to send and s is the lowest-num-
bered station. Wait time N bit contention period + (N − 1) × d bit for trans-
mission of frames. The total is N + (N − 1)d bit times.
8. If a higher-numbered station and a lower-numbered station have packets to
send at the same time, the higher-numbered station will always win the bid.
Thus, a lower-numbered station will be starved from sending its packets if
there is a continuous stream of higher-numbered stations ready to send their
packets.
9. Stations 2, 3, 5, 7, 11, and 13 want to send. Eleven slots are needed, with the
contents of each slot being as follows:
Slot 1: 2, 3, 5, 7, 11, 13
Slot 2: 2, 3, 5, 7
Slot 3: 2, 3
Slot 4: 2
Slot 5: 3
Slot 6: 5, 7
Slot 7: 5
Slot 8: 7
Slot 9: 11, 13
Slot 10: 11
Slot 11: 13
10. (a) Since all stations will see A’s packet, it will interfere with receipt of any
other packet by any other station. So, no other communication is possible in
this case.
(b) B/s packet will be seen by E, A and C, by not by D. Thus, E can send to
D, or A can send to D, or C can send to D at the same time.
(c) This scenario is same as (b).
11. Yes. Imagine that they are in a straight line and that each station can reach
only its nearest neighbors. Then A can send to B while E is sending to F.
12. (a) Number the floors 1–7. In the star configuration, the router is in the mid-
dle of floor 4. Cables are needed to each of the 7 × 15 − 1 = 104 sites. The
total length of these cables is
7 15
4Σ Σ √(i − 4)
2
+ (j − 8)2
i =1 j =1
 PROBLEM SOLUTIONS FOR CHAPTER 4 19
or about 1832 meters.
(b) For classic 802.3, 7 horizontal cables 56 m long are needed, plus one vert-
ical cable 24 m long, for a total of 416 m.
13. Classic Ethernet uses Manchester encoding, which means it has two signal
periods per bit sent. The data rate is 10 Mbps, so the baud rate is twice that,
or 20 megabaud.
14. The signal is a square wave with two values, high (H) and low (L). The pat-
tern is LHLHLHHLHLHLLHHLLHHL.
15. The round-trip propagation time of the cable is 10 µsec. A complete trans-
mission has six phases:
1. Transmitter seizes cable (10 µsec)
2. Transmit data (25.6 µsec)
3. Delay for last bit to get to the end (5.0 µsec)
4. Receiver seizes cable (10 µsec)
5. Acknowledgement sent (3.2 µsec)
6. Delay for last bit to get to the end (5.0 µsec)
The sum of these is 58.8 µsec. In this period, 224 data bits are sent, for a rate
of about 3.8 Mbps.
16. Number the acquisition attempts starting at 1. Attempt i is distributed among
2i − 1 slots. Thus, the probability of a collision on attempt i is 2−(i − 1) . The
probability that the first k − 1 attempts will fail, followed by a success on
round k is
k −1
P k = (1 − 2−(k − 1) ) Π2
−(i − 1)
i =1

which can be simplified to

Pk = (1 − 2−(k − 1) ) 2−(k − 1)(k − 2)/ 2

The expected number of rounds is then just ΣkP k .

17. The minimum Ethernet frame is 64 bytes, including both addresses in the
Ethernet frame header, the type/length field, and the checksum. Since the
header fields occupy 18 bytes and the packet is 60 bytes, the total frame size
is 78 bytes, which exceeds the 64-byte minimum. Therefore, no padding is
used.
18. The maximum wire delay in fast Ethernet is 1/10 as long as in Ethernet.
19. The payload is 1500 bytes, but when the destination address, source address,
type/length, and checksum fields are counted, plus the VLAN header, the
total is indeed 1522. Prior to VLANs, the total was 1518.
20 PROBLEM SOLUTIONS FOR CHAPTER 4

20. The smallest Ethernet frame is 512 bits, so at 1 Gbps we get 1,953,125 or al-
most 2 million frames/sec. However, this only works when frame bursting is
 operating. Without frame bursting, short frames are padded to 4096 bits, in
which case the maximum number is 244,140. For the largest frame (12,144
bits), there can be as many as 82,345 frames/sec.
21. Gigabit Ethernet has it and so does 802.16. It is useful for bandwidth effi-
ciency (one preamble, etc.) but also when there is a lower limit on frame size.
22. Station C is the closest to A since it heard the RTS and responded to it by
asserting its NAV signal. D did not respond, so it must be outside A’s radio
range.
23. RTS/CTS in 802.11 does not help with the exposed terminals problem. So,
given the scenario in Figure 4-11(b), MACA protocol will allow simultaneous
communication, B to A and C to D, but 802.11 will allow only one of these
communications to take place at a time.
24. (a) Each set of ten frames will include one frame from each station. So, all
stations will experience a data rate of 54/50 Mbps = 1.08 Mbps. (b) Each
station gets the same amount of time to transmit. So, the 6 Mbps stations will
get 0.6 Mbps, 18 Mbps stations will get 1.8 Mbps, and 54 Mbps stations will
get 5.4 Mbps.
25. A frame contains 512 bits. The bit error rate is p = 10 −7 . The probability of
all 512 of them surviving correctly is (1 − p)512 , which is about 0.9999488.
The fraction damaged is thus about 5 × 10−5 . The number of frames/sec is
11 × 106 /512 or about 21,484. Multiplying these two numbers together, we
get about 1 damaged frame per second.
26. It depends how far away the subscriber is. If the subscriber is close, QAM-64
is used for 120 Mbps. For medium distances, QAM-16 is used for 80 Mbps.
For distant stations, QPSK is used for 40 Mbps.
27. One reason is the need for real-time quality of service. If an error is discover-
ed, there is no time for a retransmission. The show must go on. Forward
error correction can be used here. Another reason is that on very low-quality
lines (e.g., wireless channels), the error rate can be so high that practically all
frames would have to be retransmitted, and the retransmissions would proba-
bly damaged as well. To avoid this, forward error correction is used to in-
crease the fraction of frames that arrive correctly.
28. Like 802.11, WiMAX wirelessly connects devices, including mobile devices
to the Internet at Mbps speeds. Also, like 802.11, WiMAX is based on
OFDM and MIMO technologies. However, unlike 802.11, WiMAX base sta-
tions are much more powerful than 802.11 access points. Also, transmissions
in WiMAX are carefully scheduled by the base station for each subscriber
 PROBLEM SOLUTIONS FOR CHAPTER 4 21
without any possibility of collisions unlike CSMA/CA used in 802.11.
29. It is impossible for a device to be master in two piconets at the same time.
Allowing this would create two problems. First, only 3 address bits are avail-
able in the header, while as many as seven slaves could be in each piconet.
Thus, there would be no way to uniquely address each slave. Second, the ac-
cess code at the start of the frame is derived from the master’s identity. This
is how slaves tell which message belongs to which piconet. If two overlap-
ping piconets used the same access code, there would be no way to tell which
frame belonged to which piconet. In effect, the two piconets would be
merged into one big piconet instead of two separate ones.
30. A Bluetooth frame has an overhead of 126 bits for access code and header,
and a settling time of 250 to 260 µsec. At the basic data rate, 1 Mbps, a set-
tling time of 250 to 260 µsec corresponds to 250 to 260 bits. A slot is 625
µsec long, which corresponds to 625 bits at 1 Mbps. So, a maximum of 1875
bits can be transmitted in a 3-slot frame. Out of this, 376 to 386 bits are over-
head bits, leaving a maximum of 1499 to 1509 bits for the data field.
31. Bluetooth uses FHSS, just as 802.11 does. The biggest difference is that
Bluetooth hops at a rate of 1600 hops/sec, far faster than 802.11.
32. In a 5 slot Bluetooth frame, a maximum of 3125 (625×5) bits can transmitted
at basic rate. Out of this, a maximum of 2744 bits are for data. In case of
repetition encoding, data is replicated thrice, so the actual data transmitted is
about 914 bits. This results in about 29% efficiency.
33. They do not. The dwell time in 802.11 is not standardized, so it has to be
announced to new stations that arrive. In Bluetooth, this is always 625 µsec.
There is no need to announce this. All Bluetooth devices have this hardwired
into the chip. Bluetooth was designed to be cheap, and fixing the hop rate and
dwell time leads to a simpler chip.
34. We want to maximize the probability that one (and only one) tag responds in
a given slot. Consulting Sec. 4.2.4, the best tag probability for 10 tags is 1/10.
This occurs when the reader sets Q equal to 10 slots. Consulting Fig. 4-0, the
probability that one tag responds is roughly 40%.
35. One key security concern is unauthorized tracking of RFID tags. An adver-
sary with an appropriate RFID reader can track the locations of the items
tagged using RFID tags. This becomes quite serious if the item is sensitive in
nature, for example, a passport, and the tag can be used to retrieve further
information, for example, the nationality and other personal information of
the person holding the passport. Another security concern is the ability of a
reader to change tag information. This can be used by an adversary to, for ex-
ample, change the price of a tagged item he plans to buy.
22 PROBLEM SOLUTIONS FOR CHAPTER 4

36. The worst case is an endless stream of 64-byte (512-bit) frames. If the back-
plane can handle 109 bps, the number of frames it can handle is 109 /512. This
is 1,953,125 frames/sec.
37. A store-and-forward switch stores each incoming frame in its entirety, then
examines it and forwards it. A cut-through switch starts to forward incoming
frames before they have arrived completely. As soon as the destination ad-
dress is in, the forwarding can begin.
38. (a) B1 will forward this packet on ports 2, 3, and 4. B2 will forward it on 1, 2
and 3.
(b) B2 will forward this packet on ports 1, 3, and 4. B1 will forward it on 1, 2
and 3.
(c) B2 will not forward this packet on any of its ports, and B1 will not see it.
(d) B2 will forward this packet on port 2. B1 will not see it.
(e) B2 will forward this packet on port 4 and B1 will forward it on port 1.
(f) B1 will forward this packet on ports 1, 3 and 4. B2 will forward it on port
2.
39. Store-and-forward switches store entire frames before forwarding them.
After a frame comes in, the checksum can be verified. If the frame is dam-
aged, it is discarded immediately. With cut-through, damaged frames cannot
be discarded by the switch because by the time the error is detected, the frame
is already gone. Trying to deal with the problem is like locking the barn door
after the horse has escaped.
40. A bridge that does not have any station directly connected to any of its ports
and is part of a loop is a candidate for not being a part of the spanning tree
bridges. This can happen if the shortest paths to the root for all bridges con-
nected to this bridge does not include this bridge.
41. No. Hubs just connect all the incoming lines together electrically. There is
nothing to configure. No routing is done in a hub. Every frame coming into
the hub goes out on all the other lines.
42. It would work. Frames entering the core domain would all be legacy frames,
so it would be up to the first core switch to tag them. It could do this by using
MAC addresses or IP addresses. Similarly, on the way out, that switch would
have to untag outgoing frames.
 PROBLEM SOLUTIONS FOR CHAPTER 7 39
44. With 50,000 customers each getting two movies per month,, the server out-
puts 150,000 movies per month or about 5000 per day. If half of these are at
9 P.M., the server must handle about 3330 movies at once. If the server has to
transmit 3330 movies at 6 Mbps each, the required bandwidth is 20 Gbps.
Using OC-12 connections, with an SPE capacity of 594 Mbps each, at least
34 connections will be needed.
45. The fraction of all references to the first r movies is given by
C / 1 + C / 2 + C / 3 + C / 4 + . . . + C /r
Thus, the ratio of the first 1000 to the first 10,000 is
1 /1 + 1 /2 + 1/ 3 + 1/ 4 + . . . + 1 /1000
1 /1 + 1 /2 + 1 /3 + 1/ 4 + . . . + 1 /10000

because the Cs cancel out. Evaluating this numerically, we get 7.486/9.788.

Thus, about 0.764 of all requests will be for movies in memory. Noteworthy
is that Zipf’s law implies that a substantial amount of the distribution is in the
tail, compared, say, to exponential decay.

SOLUTIONS TO CHAPTER 8 PROBLEMS

1. will you walk a little faster said a whiting to a snail

theres a porpoise close behind us and hes treading on my tail
see how eagerly the lobsters and the turtles all advance
they are waiting on the shingle will you come and join the dance
will you wont you will you wont you will you join the dance
will you wont you will you wont you wont you join the dance

From Alice in Wonderland (A Whiting and a Snail).

2. Assume that the most frequent plaintext letter is e and the second most fre-
quent letter is t. In the ciphertext, the most frequent letter is ’R’, and the sec-
ond most frequent letter is ’K’. Note that the numerical values are e = 4; K =
10; R = 17; and t = 19. The following equations therefore exist:
17 = (4a +b )mod26
10 = (19a+b)mod26
Thus, -7 = 15a mod 26, which is equivalent to 19=15a mod 26. By trial and
error, we solve: a = 3. Then 17 = (12 + b) mod 26. By observation, b = 5.
3. The plaintext is: a digital computer is a machine that can solve problems for
people by carrying out instructions given to it.
From Structured Computer Organization by A. S. Tanenbaum.
40 PROBLEM SOLUTIONS FOR CHAPTER 8

4. By getting hold of the encrypted key, Trudy now knows the length of the key.
She can therefore determine how many columns there were in the transposi-
tion cipher matrix, and can break the ciphertext into columns. Subsequently,
all Trudy has to do in order to decipher the message is try out all the arrange-
ments of the columns until she finds one that makes sense. Assuming that the
length of the encrypted key is k characters, finding the correct arrangement of
the columns would require at most 2k attempts.
5. It is:
1010011 0001110 1100010 1010110 1001011 0100110 1111100 0111100 1001010 1111111 1100001

6. You could use ASCII representation of the characters in Lord of the Rings to
encrypt your messages. This will give you a one-time pad which is as long as
the number of bits required to represent all the characters in Lord of the
Rings. When you are near the end of the book, and your key is almost used
up, you use the last portion of the book to send a message announcing the
name of the next book you will be using as your one-time pad, and switch to
that book for your subsequent messages. By continuing in this routine, be-
cause you have an infinite number of books, you also have an infinitely long
one-time pad.
7. At 250 Gbps, a bit takes 4 × 10−12 sec to be transmitted. With the speed of
light being 2 × 10 8 meters/sec, in 1 bit time, the light pulse achieves a length
of 0.8 mm or 800 microns. Since a photon is about 1 micron in length, the
pulse is 800 photons long. Thus, we are nowhere near one photon per bit
even at 250 Gbps. Only at 200 Tbps do we achieve 1 bit per photon.
8. Half the time Trudy will guess right. All those bits will be regenerated cor-
rectly. The other half she will guess wrong and send random bits to Bob.
Half of these will be wrong. Thus, 25% of the bits she puts on the fiber will
be wrong. Bob’s one-time pad will thus be 75% right and 25% wrong.
9. If the intruder had infinite computing power, they would be the same, but
since that is not the case, the second one is better. It forces the intruder to do
a computation to see if each key tried is correct. If this computation is expen-
sive, it will slow the intruder down.
10. Yes. A contiguous sequence of P-boxes can be replaced by a single P-box.
Similarly, for S-boxes.
11. For each possible 56-bit key, decrypt the first ciphertext block. If the re-
sulting plaintext is legal, try the next block, etc. If the plaintext is illegal, try
the next key.
12. The equation 2n = 10 16 tells us n, the number of doubling periods needed.
Solving, we get n = 16 log 2 10 or n = 53.15 doubling periods, which is 79.72
years. Just building that machine is quite a way off, and Moore’s Law may
 PROBLEM SOLUTIONS FOR CHAPTER 8 41
not continue to hold for nearly 80 more years.
13. The equation we need to solve is 2256 = 10n . Taking common logarithms, we
get n = 256 log 2, so n = 77. The number of keys is thus 1077 . The number
of stars in our galaxy is about 1012 and the number of galaxies is about 10 8 ,
so there are about 10 20 stars in the universe. The mass of the sun, a typical
star, is 2 × 1033 grams. The sun is made mostly of hydrogen and the number
of atoms in 1 gram of hydrogen is about 6 × 1023 (Avogadro’s number). So
the number of atoms in the sun is about 1.2 × 1057 . With 1020 stars, the num-
ber of atoms in all the stars in the universe is about 1077 . Thus, the number of
256-bit AES keys is equal to the number of atoms in the whole universe
(ignoring the dark matter). Conclusion: breaking AES-256 by brute force is
not likely to happen any time soon.
14. DES mixes the bits pretty thoroughly, so a single bit error in block Ci will
completely garble block P i . However, a one bit error in block Ci will not
affect any other blocks, and therefore a single bit error only affects one plain-
text block.
15. Unfortunately, every plaintext block starting at P i +1 will be wrong now, since
all the inputs to the XOR boxes will be wrong. A framing error is thus much
more serious than an inverted bit.
16. Cipher block chaining produces 8 bytes of output per encryption. Cipher
feedback mode produces 1 byte of output per encryption. Thus, cipher block
chaining is eight times more efficient (i.e., with the same number of cycles
you can encrypt eight times as much plaintext).
17. (a) For these parameters, z = 48, so we must choose d to be relatively prime
to 48. Possible values are: 5, 7, 11, 13, and 17.
(b) If e satisfies the equation 37e = 1 mod 120, then 37 e must be 121, 241,
361, 481 etc. Dividing each of these in turn by 37 to see which is divisible by
37, we find that 481/37 = 13, hence e = 13.
(c) With these parameters, e = 9. To encrypt P we use the function
C = P 9 mod 55. For P = 8, 5, 12, 12, and 15, C = 18, 20, 12, 12, and 25, re-
spectively.
18. Trudy can look up Alice’s and Bob’s public key pairs, and retrieve na and nb .
Because of the properties of the RSA algorithm, Trudy knows that each of
these numbers is a multiplication of two primes, and therefore has only two
prime factors. As stated in the question, Trudy also knows that one of the
prime factors is common to na and nb . Thus, Trudy concludes that the
Greatest Common Divisor (GCD) of na and nb is the common prime factor, q.
All Trudy needs to do in order to break Alice’s code is to use the Euclidean
algorithm to find the GCD of na and nb to obtain q, and then divide na by the
result, q, to obtain pa . Trudy can look up ea in Alice’s public key pair, and
42 PROBLEM SOLUTIONS FOR CHAPTER 8

can then find a solution to the equation da × ea = 1 mod (p −1) (q −1), thereby
determining Alice’s private key.
19. No. The security is based on having a strong crypto algorithm and a long key.
The IV is not really essential. The key is what matters.
20. If Trudy replaces both parts, when Bob applies Alice’s public key to the sig-
nature, he will get something that is not the message digest of the plaintext.
Trudy can put in a false message and she can hash it, but she cannot sign it
with Alice’s private key.
21. When a customer, say, Sam, indicates that he wants to buy some pornogra-
phy, gamble, or whatever, the Mafia order a diamond on Sam’s credit card
from a jeweler. When the jeweler sends a contract to be signed (presumably
including the credit card number and a Mafia post office box as address), the
Mafia forward the hash of the jeweler’s message to Sam, along with a con-
tract signing up Sam as a pornography or gambling customer. If Sam just
signs blindly without noticing that the contract and signature do not match,
the Mafia forward the signature to the jeweler, who then ships them the dia-
mond. If Sam later claims he did not order a diamond, the jeweler will be
able to produce a signed contract showing that he did.
22. With 20 students, there are (25 × 24) /2 = 300 pairs of students. The probabil-
ity that the students in any pair have the same birthday is 1/181, and the
probability that they have different birthdays is 180/181. The probability that
all 300 pairs have different birthdays is thus (180/181)300 . This number is
about 0.190. If the probability that all pairs are mismatches is 0.190, then the
probability that one or more pairs have the same birthday is about 0.810.
23. The secretary can pick some number (e.g., 32) spaces in the letter, and poten-
tially replace each one by space, backspace, space. When viewed on the ter-
minal, all variants will look alike, but all will have different message digests,
so the birthday attack still works. Alternatively, adding spaces at the end of
lines, and interchanging spaces and tabs can also be used.
24. It is doable. Alice encrypts a nonce with the shared key and sends it to Bob.
Bob sends back a message encrypted with the shared key containing the
nonce, his own nonce, and the public key. Trudy cannot forge this message,
and if she sends random junk, when decrypted it will not contain Alice’s
nonce. To complete the protocol, Alice sends back Bob’s nonce encrypted
with Bob’s public key.
25. Step 1 is to verify the X.509 certificate using the root CA’s public key. If it is
genuine, she now has Bob’s public key, although she should check the CRL if
there is one. But to see if it is Bob on the other end of the connection, she
needs to know if Bob has the corresponding private key. She picks a nonce
and sends it to him with his public key. If Bob can send it back in plaintext,
 PROBLEM SOLUTIONS FOR CHAPTER 8 43
she is convinced that it is Bob.
26. First Alice establishes a communication channel with X and asks X for a cer-
tificate to verify his public key. Suppose X provides a certificate signed by
another CA Y. If Alice does not know Y, she repeats the above step with Y.
Alice continues to do this, until she receives a certificate verifying the public
key of a CA Z signed by A and Alice knows A’s public key. Note that this
may continue until a root is reached, that is, A is the root. After this Alice
verifies the public keys in reverse order starting from the certificate that Z
provided. In each step during verification, she also checks the CRL to make
sure that the certificate provided have not been revoked. Finally, after verify-
ing Bob’s public key, Alice ensures that she is indeed to talking to Bob using
the same method as in the previous problem.
27. No. AH in transport mode includes the IP header in the checksum. The NAT
box changes the source address, ruining the checksum. All packets will be
perceived as having errors.
28. The recommended method would be by using HMACs, since they are compu-
tationally faster than using RSA. However, this requires establishing a shared
key with Bob prior to the transmission of the message.
29. Incoming traffic might be inspected for the presence of viruses. Outgoing
traffic might be inspected to see if company confidential information is leak-
ing out. Checking for viruses might work if a good antivirus program is used.
Checking outgoing traffic, which might be encrypted, is nearly hopeless
against a serious attempt to leak information.
30. The VPN provides security for communication over the Internet, but not with-
in the organization. Therefore, when communicating with Mary regarding
R&D purchases, or any other communication which need only be secure from
people outside the organization, Jim does not need to use additional en-
cryption or security measures. However, if Jim wants his communication
with Mary to be secure also with respect to people inside the organization,
such as when communicating with Mary about his salary and the raise he had
been promised, additional security measures should be used.
31. In message 2, put RB inside the encrypted message instead of outside it. In
this way, Trudy will not be able to discover RB and the reflection attack will
not work.
32. Bob knows that g x mod n = 82. He computes 823 mod 227 = 155. Alice
knows that g y mod n = 125. She computes 12512 mod 227 = 155. The key is
155. The simplest way to do the above calculations is to use the UNIX bc
program.
44 PROBLEM SOLUTIONS FOR CHAPTER 8

33. (a) The information transferred from Alice to Bob is not encrypted, and there-
fore, there is nothing Bob knows that Trudy does not know. Any response
Bob can give, Trudy can also give. Under these circumstances, it is impossi-
ble for Alice to tell if she is talking to Bob or to Trudy.
(b) If n or g are secret, and are not known to Trudy, she cannot pretend to be
Bob using a man-in-the-middle attack, since she would not be able to perform
the correct calculations in order to send a return message to Alice and/or to
obtain the correct key.
34. The KDC needs some way of telling who sent the message, hence which de-
cryption key to apply to it.
35. The two random numbers are used for different purposes. RA is used to con-
vince Alice she is talking to the KDC. RA 2 is used to convince Alice she is
talking to Bob later. Both are needed.
36. If AS goes down, new legitimate users will not be able to authenticate them-
selves, that is, get a TGS ticket. So, they will not be able to access any ser-
vers in the organization. Users that already have a TGS ticket (obtained from
AS before it went down) can continue to access the servers until their TGS
ticket lifetime expires. If TGS goes down, only those users that already have
a server ticket (obtained from TGS before it went down) for a server S will be
able to access S until their server ticket lifetime expires. In both cases, no se-
curity violation will occur.
37. Even if Trudy intercepted the message including RB she has no way of using
it, since this value will not be used again in the communication between Alice
and Bob. Thus, there is no need for Alice and Bob to repeat the protocol with
different values in order to ensure the security of their communication. How-
ever, Trudy can use the information she gleaned from the intercepted message
(and multiple other such messages) to try and figure out how Bob is generat-
ing his random numbers. Therefore, next time Alice should remember to en-
crypt the last message of the protocol.
38. It is not essential to send RB encrypted. Trudy has no way of knowing it, and
it will not be used again, so it is not really secret. On the other hand, doing it
this way allows a tryout of KS to make doubly sure that it is all right before
sending data. Also, why give Trudy free information about Bob’s random
number generator? In general, the less sent in plaintext, the better, and since
the cost is so low here, Alice might as well encrypt RB .
39. The bank sends a challenge (a long random number) to the merchant’s com-
puter, which then gives it to the card. The CPU on the card then transforms it
in a complex way that depends on the PIN code typed directly into the card.
The result of this transformation is given to the merchant’s computer for
transmission to the bank. If the merchant calls up the bank again to run an-
 PROBLEM SOLUTIONS FOR CHAPTER 8 45
other transaction, the bank will send a new challenge, so full knowledge of
the old one is worthless. Even if the merchant knows the algorithm used by
the smart cards, he does not know the customer’s PIN code, since it is typed
directly into the card. The on-card display is needed to prevent the merchant
from displaying: ‘‘Purchase price is 49.95’’ but telling the bank it is 499.95.
40. In order to multicast a PGP message, one would have to encrypt the IDEA
key with the public key for each of the users accessing the Internet address.
However, if all the users to whom the message is multicast have the same
public key, the message can be multicast effectively.
41. No. Suppose the address was a mailing list. Each person would have his or
her own public key. Encrypting the IDEA key with just one public key would
not work. It would have to be encrypted with multiple public keys.
42. In step 3, the ISP asks for www.trudy-the-intruder.com and it is never sup-
plied. It would be better to supply the IP address to be less conspicuous. The
result should be marked as uncacheable so the trick can be used later if neces-
sary.
43. The nonces guard against replay attacks. Since each party contributes to the
key, if an intruder tries to replay old messages, the new key generated will not
match the old one.
44. The image contains 2048 × 512 pixels. Since each pixel contains 3 low-order
bits, the number of bits which can be used for steganographic purposes is
2048 × 512 × 3, which equals 3,145,728 bits or 393,216 bytes. The fraction
of the file which could be encrypted in the image is approximately 0.16. If
the file were compressed to a quarter of its original size, the compressed ver-
sion would be of size 0.625 Mbyte. Therefore the fraction of the file which
could be hidden in the image would be approximately 0.63.
45. Easy. Music is just a file. It does not matter what is in the file. There is
room for 294,912 bytes in the low-order bits. MP3s require roughly 1 MB per
minute, so about 18 sec of music could fit.
46. The number of bits to be encrypted is 60 × 106 × 8 = 480 × 106 bits. Each
pixel of the image can hide 3 bits in it. Therefore, the number of pixels
required in order to encrypt the entire file is
480 × 106 / 3 = 160 × 106 = 160,000, 000 pixels. We want the image to be
3:2 so let the width be 3x and the height be 2x. The number of pixels is then
6x 2 which must be 160,000,000. Solving, we get x = 5164 and an image of
15492 × 10328. If the file were compressed to a third of its original size, the
number of bits to be encrypted would be 160 × 106 , and the number of pixels
needed would be a third of the uncompressed file or 53,333,333 pixels. The
image would then be 8946 × 5962.
46 PROBLEM SOLUTIONS FOR CHAPTER 8

47. Alice could hash each message and sign it with her private key. Then she
could append the signed hash and her public key to the message. People
could compare the signature and compare the public key to the one Alice
used last time. If Trudy tried to impersonate Alice and appended Alice’s pub-
lic key, she would not be able to get the hash right. If she used her own pub-
lic key, people would see it was not the same as last time.