Corporate and Professional Publishing Group

An Engineering Approach to Computer Networking

by S. Keshav

ISBN 0-201-63442-2 * Hardcover * 688 pages * 1997


Book Description Preface Glossary Bibliography Solutions Slides Simulator Exercises Errata Cover (73K) Ordering Information C&P Welcome Page.


Errata

Please report errors by sending me email at skeshav@cs.cornell.edu. When reporting an error, I would appreciate it if you could tell me your name, the page, paragraph and line number of the error, and whether the error is syntactic, grammatical, factual, or logical. This will let me locate and correct the error. I will acknowledge everyone who reports an error on this page and also in future printings of the book.

Some of these errors have been fixed in the second and third printings, so you may not find them if you purchased your copy after September 1997, and after February 1998, respectively.

Front matter

My affiliation should read: AT&T Labs - Research.

The first paragraph of the acknowledgements section got dropped out. It should read:

"My sincere thanks to my management at AT&T Bell Laboratories and AT&T Labs, in particular, Sandy Fraser, Chuck Kalmanek, Brian Kernighan, Ravi Sethi, Peter Weinberger, and Mihalis Yannakakais for allowing me to work on the book full time for over a year. I could not have undertaken this project without their generous support."

Chapter 1

Page 7: 6th paragraph: First line should read-"In Chapter 14, we study the problem of achieving end-to-end quality of serviceby managing traffic at multiple time scales." Reported by: Jose Landivar, University of Buffalo.

Chapter 4

Page 50: Figure 4.2: Typo: In the caption for the figure, 'link S1-H2' should read 'link S1-S2'. Reported by: Suresh Rai, Lousiana State University.

Page 53: Line 8: Line should read-"When a switch sees a packet on this VCI, it holds it in a special buffer, awaiting further instructions from the switch controller." Reported by: Laurent Mathy, Lancaster University.

Page 54: Line 18: Line should read-"For example, a schedule that serves three cells from H1, then one from H3 guarantees a fourth of the link bandwidth to H3." Reported by: Laurent Mathy, Lancaster University.

Page 59: Line 1: Replace "nb(p-r)" by "b(np-r)." Reported by: Hideaki Kashimura, IBM Japan.

Chapter 6

Page 99: Line 20: Replace "time is N * S, the throughput is S" by "time is N *S, the throughput is 1/S" Reported by:  Yong-Min Choi, Korea Telecom, Korea.

Chapter 7

Page 126: Example 7.1: The second part of the problem asks how many calls a system of square cells with no two adjacent cells sharing an
edge can support. The solution then states that 5 sets of channels are required. However, with those requirements, only 2 sets of cells are required, arranged in a checkerboard pattern. This also impacts the description of EAMPS (p.132, paragraph 4) which references this example to give an explanation for why there are 7 sets of channels in the EAMPS system. For such a hexagonal tiling, only three sets of channels are necessary, arranged in the obvious way.

The real answer is that, given a particular tiling of the plane, one has to take into account inteference from all the other cells in the plane in order to correctly compute the reuse factor. It turns out that for the EAMPS analog system, with a signal to noise ratio spec of 18dB, a hexagonal tiling requires 7 sets of frequencies. The number 7, however, is fortuitous, rather than arising from a simple geometric relationship, as I had mistakenly thought. Reported by:James Hewitt, University of Washington, Seattle.

Page 138: First paragraph: The reduction due to p-persistance with p=0.25 should be from 100% to 33.33%, not to 25% (because after both defer, they may collide again; summing this to infinity, we get correct reduction in collision probability) Reported by:David Sacerdote, Cornell.

Page 142: Figure 7.4: The line between nodes B and C should represent "undetectable", not "strong" Reported by: S. Keshav.

Page 142: Figure 7.5: The labels for nodes B and C should be interchanged. After relabelling, the signal strengths should be:

Chapter 8

Page 163: Figure 8.2: Logical error: The last line in the caption should read:" .. each N times slower than the input. Reported by:  Katie Guo, Cornell University.

Page 169: Equation 8.1: Logical error: This equation is true for a non-rearrangable (or strictly non-blocking) switch. For a rearrangably non-blocking switch (as described in the text) the equation should read k >= n. . Reported by:  Andy Yuen, Rutgers University.

Page 201: Example 8.12: Typo:Replace 42.9 nanoseconds by 42.6 nanoseconds . Reported by:  Sam Kwong, City University of Hong Kong.

Page 206: Exercise 8.6:Typo: Change Example 8.5 to Example 8.6, and 1500 bytes to 500 bytes. Reported by:  Chienhua Chen, Tatung Institute of Technology,Taiwan.

Page 206: Exercise 8.8:Typo: Change Example 8.5 to Example 8.6. Reported by:  Chienhua Chen, Tatung Institute of Technology,Taiwan.

Page 207: Exercise 8.10:Typo: Change Example 8.11 to Example 8.6, Part (a). (the solution also is different, please see the errata for page 629). Reported by:  Chienhua Chen, Tatung Institute of Technology,Taiwan.

Chapter 9

Page 213: Example 9.2: Spelling error: "circcuits" should be "circuits". Reported by:  Efthymios Koutsianis, Sheffield University.

Page 216: Example 9.3: Mathematical error: Replace "...giving them 2.5 + 0.66 + 0.033 = 2.7 " by "giving them 2.5 + 0.166 + 0.033 = 2.7". Reported by:  Carlos Pagani, Universidade Estadual de Campinas.

Page 234: Section 9.4.1 line 16: Syntactic error: Replace "...infinitesimal from each connection in turn,  " by "infinitesimal amount of data from each connection in turn, ". Reported by:  Bill Curry, University of Calgary, Canada.

Page 238:
Figure 9.1: Typo: Replace "300 " just above 'SECOND ROUND' by "800". Reported by:  Onur Altintas, UNCL, Japan.

Page 238: Paragraph 3: In equation for the relative fairness bound of DRR, 'r' refers to the rate of the server--this is not clear from the paragraph. Reported by:  Katie Guo, Cornell University.

Page 243: Lines 24, 26: Logical error: Replace "finish time" by "finish number". Reported by:  Alencar de Melo Junior, Universidade Estadual de Campinas.

Page 245: Line 10: Grammatical error: The start number of an packet..", should be "The start number of a packet". Reported by:  Subramaniam Vincent, ISI

Page 246: Line 9: Logical error: The delay bound is not independent of the number of schedulers along the path! Reported by:  Kui Wu, U. Alberta, Canada.

Page 246: Example 9.11:
When the given values are plugged into the equation, we get  g = 13.004 Mbps. Consequently, some other numbers change as follows:
    line 1: ...this is more than 86 times ...
    line 3: ...contributes to nearly 45.4 ms ...
    line 4: ...contributes another 14.5 ms ... contributes only 10.07 ms ...
Reported by:  Onur Altintas, UNCL, Japan.


Page 251: Last bullet on page: Logical error: The bullet should read "With properly chosen regulators, they can achieve WFQ delay bounds without the complexity of updating the round number". Reported by:  S. Keshav.
 

Chapter 10

Page 272: Example 10.4: Typos: Line 4 and first line on page 273. (I've underlined the changes, since they are hard to see.) On line 4, replace "135.104.5.0, 135.105.5.6, and 135.105.5.24" by  "135.104.5.1, 135.104.5.6, and 135.104.5.24". On the first line on page 273, replace "135.104.5.0, 135.104.5.1, and 135.104.5.2" by "135.104.5.1, 135.104.5.6, and 135.104.5.24". Reported by:  Christopher Martin, GTE Laboratories.

Page 280: Figure 10.8: The lines joining the nodes are very faint. Use a pencil to darken them. Reported by:  S. Keshav.

Chapter 11

Page299: Figure 11.4: The link cost on link CD should be 2, not 4. Reported by:  S. Keshav.

Page 301: Figure 11.5: In the fourth stage, the first line should be A 4 B instead of A A B. Reported by:  Katie Guo, Cornell University.

Page 303: Figure 11.6: The lines in the figure are incorrectly drawn. The arcs should be as follows: From 5 in 'last' to 5 in 'destn'; from 5 in 'destn' to 4 in 'last'; from 4 in 'last' to 4 in 'destn'; from 4 in 'destn' to 2 in 'last'; from 2 in 'last' to 2 in 'destn'; from 2 in 'destn' to 1 in 'last'; from 1 in 'last' to 1 in 'destn'. Reported by:  S. Keshav.

Page 317: Paragraph 1: The last line should read: "We see that for a load of 50%, as the link cost increases, the mean load on a link decreases from 0.5, when the cost is 0, to about 0.3, when the cost is 5". Reported by:  Katie Guo, Cornell University.

Page 320: Line 3: Replace "...routers 6.0.0.1 and 6.0.0.2... " by "...routers 6.0.0.0 and 6.0.0.1 ...". Reported by:  Katie Guo, Cornell University.

Page 324: Section 11.9.2 para 2: Replace "LANS" by "LANs". Reported by:  Katie Guo, Cornell University.

Page 325: Figure 11.17: In the caption, second to last line, replace "router RI" by "router R1." Reported by:  Katie Guo, Cornell University.

Page 335: Figure 11.25: The label for node B is misplaced. Reported by:  Katie Guo, Cornell University.

Chapter 12

Page 361: Example 12.2: Replace "45 * 10^6 * 10 * 10^-3" by   "45 Mb/s * 10^6 b/Mb * 10 ms * 10^-3 s/ms." Reported by: Sameer Ajmani, Cornell University.

Page 366: Paragraph 1, line 5: Replace "...nxm matrix.." by "mxn matrix .." Reported by:  Katie Guo, Cornell University.

Page 369:  Figure 12.3: (a) The arc from 00 to 01 has the arrowhead missing (b) the arc from 00 to 00 should be labelled  0/000 instead of 1/000 (c) the arc from 10 to 00 should be labelled 0/001 instead of 1/001 (d) the arc from 01 to 10 should be labelled 0/011 instead of 1/011.  Reported by: Sameer Ajmani, Cornell University.

Page 372: Paragraph 4, line 4: Replace the first occurrence of the phrase "...the receiver declares it a 0" by the phrase "...the receiver declares it a 1.". Reported by:  Katie Guo, Cornell University.

Page 375: Example 12.9: In the solution part (a), line 1, the error rate of 10^(-7) is missing. Reported by:  Sanjay Gopinatha Rao, CMU.

Page 388: Equation 12.4: In the denominator, p^w should be replaced by p*w. Reported by:  Anurup Joseph, Motorola.

Page 393: Exercise 12.14: "... T <= 1.5Mbps, R = A = 500ms, ..." should be changed to "... R <= 1.5Mbps, T = A = 500ms, ..." Reported by:  Anurup Joseph, Motorola.

Chapter 13

Page 402: Example 13.2: The packet arriving at time 0.8 will be delayed till time 1.2, not time 1.0. Reported by:  Dan Ryan, Northeastern University.

Page 417: Paragraph 1, line 1: Replace "5^6" by "5 x 10^6". Reported by:  Katie Guo, Cornell University.

Page 443: Exercise 13.6: The solution should read that the packet waits between 3 and 4 seconds, instead of between 7 and 8 seconds. Reported by:  Dan Ryan, Northeastern University.

Page 444: Exercise 13.10: The transmission rate when the source has 20 packets outstanding should be 5 packets/sec, not 0.5 packets/sec. Reported by:  Dan Ryan, Northeastern University.

Chapter 14

Page 462: Table 14.2: Error detection and correction (row 5) should point to Chapter 12 instead of Chapter 7.. Reported by:  Christopher Martin, GTE Laboratories.

Page 472: Figure 14.5: In part (e) the label for node B is missing. Reported by:  Katie Guo, Cornell University.

Page 487: Equation 14.8: The factorial sign is missing after N in the denominator. Reported by: Ioanis Nikolaidis, U. Alberta, Canada.
 
Page 488: Last line, last word: Replace 14.9.5 by 14.9.6. Reported by: Ioanis Nikolaidis, U. Alberta, Canada.

Chapter 15

Page 504: Figure 15.4: The SONET frame braces should span only the shaded area. Reported by:  Christopher Martin, GTE Laboratories.

Page 536: Paragraph 1, line 6: Replace "The reply to the inverse ARP reply..." by "The reply to the inverse ARP request...". Reported by:  Katie Guo, Cornell University.

Page 508: Figure 15.6: MTP header: The arrow to the forward indicator bit points to the wrong place. It should point to the eighth bit in the second row instead of to the sixteenth bit in that row. Reported by: S. Keshav.

Bibliography

Page 582: Reference [CLZ88]: this paper actually appeared in SIGCOMM '87; Change the reference to: D. D. Clark, M.L. Lambert, and L. Zhang, "NETBLT: A High Throughput Transport Protocol," in SIGCOMM Symposium on Communications Architectures and Protocols, (Stowe, Vermont), pp. 353-359, ACM, Aug.1987. Reported by:  Christopher Martin, GTE Laboratories.

Answers to Review Questions and Exercises

Page 629: Exercise 8.10: Change the first sentence to: In the best case, the throughput is 64 * 144.1 Mbps = 9.22 Gbps. In the second line the corresponding change is 4.9 Gbps -> 5.34 Gbps. In the third line, the change is 132 Mbps -> 144.1 Mbps. Reported by:  Chienhua Chen, Tatung Institute of Technology,Taiwan.

Page 630: Exercise 8.15: Change line 4: ... we get a 2.5 speedup ...and line 5: ... build a 5x5 switch, ..... Reported by:  Chienhua Chen, Tatung Institute of Technology,Taiwan.

Page 640: Answers to Review questions for Chapter 13: Answer 17 should not be there. Renumber answers 18-29 as answers to review questions 17-28.Reported by:  Joe Halpern, Cornell University.

Index

Page 656: Replace "RRSVP" by "RSVP". Reported by:  Onur Altintas, UNCL, Japan.


Bug spotters

My thanks to:

Sameer Ajmani Cornell University
Onur Altintas Ultra High Speed Network and Computer Technologies Lab, Japan
Chienhua Chen Tatung Institute of Technology,Taiwan
Yong-Min Choi Korea Telecom Research & Development Group, Korea
Bill Curry University of Calgary, Canada
Katie Guo Cornell University
Joe Halpern Cornell University
James Hewitt University of Washington, Seattle
Anurup Joseph Motorola
Hideaki Kashimura IBM Japan
Efthymios Koutsianis Sheffield University, UK
Sam Kwong City University of Hong Kong
Jose Landivar University of Buffalo
Christopher Martin GTE Laboratories
Laurent Mathy  Lancaster University, UK
Alencar de Melo Junior Universidade Estadual de Campinas, Brazil
Ioanis Nikolaidis University of Alberta, Canada
Carlos Pagani Universidade Estadual de Campinas, Brazil
Suresh Rai  Lousiana State University
Sanjay Gopinatha Rao    CMU
Dan Ryan Northeastern University
David Sacerdote Cornell University
Subramaniam Vincent  ISI
Andy Yuen   Rutgers University
Kui Wu University of Alberta, Canada.