VOLUME JI
`
`" Fifiinj I dini—
`T- ..._
`.
`
`1
`
`
`
`Google Ex. 1407, pg. 1
`
`Google Ex. 1407, pg. 1
`
`

`

`cm. Douglas.
`teammates 101th mln.
`
`Vol. 2 by Douglas 8. Sea: and M10 1.. Scams.
`Inflation Minus-apnea}. tolerances and index.
`Contents. Vol. 1. Principles, protocols, and
`ereluteeem - v. 2. Design, implement“, and
`internals.
`2. Computer network
`1. Coupon: networks.
`protoeoh.
`3. Date nonunion systems.
`1. Stevens, David L.
`It. Title.
`WIOSJJ” 1991
`00$.6
`90-7829
`1m 0-13-668505-9 (v. 1)
`IBM 0-13-472242-6 (v. 2)
`
`Editorial/production supervision: Joe Scordato
`Cover design: Karen Stephens
`Cover illustration: Jim Kinstrey
`Manufacturing buyers: Linda Behrens and David Dickey
`
`‘
`
`
`
`1
`
`The author and publisher of this book have used their best efforts in preparing this book.
`These efforts include the development. research. and testing of the theories and programs to
`determine their effectiveness. The author and publisher make no warranty of any kind.
`expressed or implied. with regard to these programs or the documentation contained in this
`book. The author and publisher shall not be liable in any event for incidental or consequential
`damages in connection with. or arising out of. the furnishing. performance. or use of these
`programs.
`
`= Q 1991 by Prentice-Hall. Inc.
`__
`A Simon & Schuster Company
`Englewood Clills. New Jersey 07632
`
`All rights reserved. No part of this hook
`may be reproduced. in any form or by any
`means. without permission in writing from
`the publisher.
`
`Printed in the United States of America
`
`l0 9
`
`8
`
`7
`
`6
`
`5
`
`4
`
`3
`
`2
`
`l
`
`ISBN U-LS-LI'FEEHE-l:
`
`UNIX is a registered trademark of AT&T Bell
`Laboratories.
`proNET-IO is a trademark of Proteon Corporation.
`VAX. Microvax. and DECstation are trademarks
`of Digital Equipment Corporation.
`
`Prentice-Hall International (UK) Limited, Landon
`Prentice-Hall of Australia Pty. Limited. Sydney
`Prentice-Hall Canada Inc.. Toronto
`Prentice-Hall His‘panoamericana. S. A.. Maxim Cily
`Prentice-Hall of India Private Limited. New Delhi
`Prentice-Hall of Japan. Inc.. Tokyo
`Simon & Schuster Asia Pte. Ltd.. Singapore
`Editortt Prentice-Hall do Brasil. Ltda.. Rio tie Jmu'im
`
`
`
`Google Ex. 1407, pg. 2
`
`Google Ex. 1407, pg. 2
`
`

`

`
`
`tisslon
`
`Chap. l4
`
`s;
`
`Sec. l4.4
`
`Retransmission Timer And Backoff
`
`265
`
`it needs to schedule another retransmission
`Once rcprexmr retransmits the data,
`timeout in the future. The call to rmser implements timer control according to Kam’s
`algorithm.
`it shifts the timeout in tcb_re.\'mt left rt'h_re.\'mtcormt bits to double the de-
`lay for each retransmission that has occurred.
`It then passes the computed delay as an
`argument to rmset, causing it to schedule a new RETRANSMIT event.
`For small values of TCP_MAXREI‘RIES. doubling the timeout on each retransmis-
`sion works well. However. if the system allows a large number of retries, doubling the
`timeout on each can result in severe delays before TCP decides to abort a connection.
`To prevent the timeout from becoming arbitrarily large, tcprexmr enforces a maximum
`timeout by choosing the minimum of
`the
`computed timeout
`and constant
`TCP__MAXRXT.
`Section 14.7.] discusses the final few statements in (cprexnrr. which handle conges-
`tion control.
`
`.ransmitting
`
`*/
`
`14.5 Window-Based Flow Control
`
`mum) ,
`
`. TCP_MAXRXT) ) i
`
`*/
`t first drop
`:cb_ssthresh) /2;
`
`ll be called by the
`sion. Because the
`
`be processed. so
`
`count and enforces
`
`.‘P__MAXRETRIES.
`'l to abort the con-
`nr has checked for
`nains in the output
`retransmission.
`
`When TCP on the receiving machine sends an acknowledgement. it includes a win-
`dow advertisement in the segment to tell the sender how much buffer space the receiver
`has available for additional data. The window advertisement always specifies the data
`the receiver can accept beyond the data being acknowledged, and TCP mandates that
`once a receiver advertises a given window. it may never advertise a subset of that win-
`dow (i.e., the window never shrinks). 01' course. as the sender fills the advertised win-
`dow. the value in the acknowledgement field increases and the value in the window
`field may become smaller until it reaches zero. However, the receiver may never de-
`crease the point in the sequence space through which it has agreed to accept data Thus.
`the window advertisement can only decrease if the sender supplies data and the aclt-
`nowledgement number increases: it cannot decrease merely because the receiver decides
`to decrease its buffer size.
`TCP uses window advertisements to control the flow of data across a connection.
`
`A receiver advertises small window sizes to limit the data a sender can generate.
`extreme case. advertising a window size of zero halts transmission altogethert.
`
`in the
`
`14.5.1 Silly Window Syndrome
`
`If a receiver advertises buffer space as soon as it becomes available, it may cause
`behavior known as the silly window syndrome. Silly window behavior is characterized
`as a situation in which the receiver's window oscillates between zero and a small posi-
`tive value, while the sender transmits small segments to fill the window as soon as it
`opens. Such behavior leads to low network utilization because each segment transmit-
`ted contains little data compared to the overhead for TCP and IP headers.
`To prevent a TCP peer from falling victim to the silly window syndrome when
`transmitting. TCP uses a technique known as receiver-side silly window avoidance.
`The silly window avoidance rule states that once a receiver advertises a zero window, it
`
`+We say that the receiver "closes“ the window.
`
`Google Ex. 1407, pg. 3
`
`

`

`It”
`
`lL'I': now control Ann AGBFIWE KemrL-smtsslon
`
`Chap. I4
`
`should delay advertising a nonzero window until it has a nontrivial amount of space in
`its buffer. A nontrivial amount of buffer space is defined to be the space sufficient for
`one maximum-sized segment or the space equivalent
`to one quarter ‘of the buffer,
`whichever is larger.
`
`14.5.2 Flecelver-Slde Silly Wlndow Avoldance
`
`Procedure {rpm-indow implements receiver-side silly window avoidance when it
`computes a window advertisement.
`
`/* tcprwindow.c - tcprwindow '/
`
`Binclude <conf.h>
`fiinclude <kernel.h>
`#include <network.h>
`
`/ t___.-_..—__-.___________..---__...___________.._..._._______ ___--_--__.-.._--_
`*
`tcprwindow — do receive window processing for a TCB
`*
`
`‘/
`
`int: tcprwindow (ptcb)
`struct
`tcb
`'ptcb;
`l
`
`int
`
`window;
`
`window = ptcb->tcb_rbsize - ptcb->tcb_rbcount;
`if (ptcb—>tcb_st;ate < TCPS_ESTABLISHED)
`return window;
`
`Receiver-Side Silly Window Syndrome Avoidance:
`Never shrink an already-advertised window, but wait for at
`least 1/4 receiver buffer and 1 max—sized segment before
`opening a zero window.
`
`*
`*I
`
`if (window’A < ptcb->tcb_rbsize II window < ptcb—>tcb_rmss)
`window = 0:
`
`window = max(window, ptcb->tcb_cwin - ptcb->tcb rnext);
`ptcb->tcb_cwin = pteb->tcb_rnext + window;
`_
`return window;
`
`
`
`Tcprwindow be
`space (i.e.. the size
`buffer).
`ll‘ TCP has
`connection (the stat
`ment size has not t
`
`silly window avoids
`tcb__wind0w of the
`blished. tcpm'indow
`ing the window to z
`The final state:
`venisement as discu
`
`14.5.3 Optlmlzlnq
`
`Once a receivc
`
`state and begins to I
`an acknowledgemel
`the acknowledgeme
`ficient space becon
`and the sender will
`
`Although the
`minor optimization
`for the receiver to 1
`size. without waitit
`plication program 6
`31 space causes the
`As the sender pror
`ment. moves back
`
`14.5.4 Adjustlns
`
`Procedure tcp
`dow advertisemen
`
`peer TCP is willin
`
`rChapler 12 disct
`
`
`
`Google Ex. 1407, pg. 4
`
`Google Ex. 1407, pg. 4
`
`

`

`
`
`ission
`
`Chap. l4
`
`aunt of space in
`.ce sufficient for
`r of the buffer.
`
`)idance when it
`
`1C6 :
`wait for at:
`int: before
`
`Sec. l4.5
`
`Window-Based Flow Control
`
`267
`
`to the available buffer
`TCpm’indow begins by computing a window size equal
`space (i.e.. the size of the receive buffer minus the current count of characters in the
`buffer).
`lf TCP has just begun a three-way handshake. but has not yet established a
`connection (the state is less than TCPS_ESTABLISHED), the receiver maximum seg-
`ment size has not been initialized. Therefore. tcptwr'ndow cannot apply receiver-side
`silly window avoidance - it merely stores the value computed for the window in field
`tt'b_window of the TCB and returns to its caller. Once a connection has been esta-
`blished, rquwindow applies the rule for receiver-side silly window avoidance. by reduc-
`ing the window to zero unless a nontrivial amount of space is available.
`The final statements of rcptwr'ndow apply congestion avoidance to‘the window ad-
`vertisement as discussed below.
`
`14.5.3 Optlmlzlng Performance After A Zero Wlndow
`
`Once a receiver advertises a zero window. the sender enters the PERSIST output
`state and begins to probe the receiver'l'. The receiver responds to each probe by sending
`an acknowledgement. As long as the window remains closed, the probes continue, and
`the acknowledgements contain a window advertisement of zero. Eventually. when suf-
`ficient space becomes available, the acknowledgements will carry a nonzero window,
`and the sender will start to transmit new data.
`Although the sender bears ultimate responsibility for probing a zero window, a
`minor optimization can improve performance. The optimization consists of arranging
`for the receiver to generate a gratuitous acknowledgement that contains the new window
`size, without waiting for the next probe. Thus, in our implementation, whenever an ap-
`plication program extracts data from a TCP input buffer. it checks to see if the addition-
`al space causes the window to open, and sends a gratuitous acknowledgement if it does.
`As the sender processes the acknowledgement. it finds the nonzero window advertise-
`ment, moves back to the TRANSMIT state. and resumes transmission of data.
`
`14.5.4 Adlustlng The Sender's Window
`
`It handles win-
`Procedure tcpswr'ndow computes the size of the sender’s window.
`dow advertisements in incoming segments. and keeps track of the amount of data the
`peer TCP is willing to receive.
`
`+Cltapter l2 discusses output processing and the output state machine.
`
`Google Ex. 1407, pg. 5
`
`Google Ex. 1407, pg. 5
`
`