VOLUME ]I
`
`" Fififfliubu
`
`."'
`
`
`
`Google Ex. 1007, pg. 1
`
`Google Ex. 1007, pg. 1
`
`

`

`‘
`-;—-
`hummus with Ice/n.
`
`Vol. 2 by We 8. Cost: and David 1.. Stevens.
`Includes Damon-apnea. Mame-e and index.
`Contents. Vol. 1. Principles, protocols, and
`enumerate - v. 2. neatly, implementation, and
`intends-
`2. Computer network
`t. Coeputer networks.
`protoeoh.
`3. Due: cremains“ systems.
`1. Stevens, David L.
`H. ext)...
`mtos.s.css 1991
`006.6
`90-7829
`1m 0-13-666505-9 (v. 1)
`ISBN 0-13-472262-6 (v. 2)
`
`Editorial/production supervision: Joe Scordato
`Cover deslgn: Karen Stephens
`Cover illustration: Jim Kinstrey
`Manufacturing buyers: Linda Behrens and David Dickey
`
`‘
`
`
`
`;
`.4
`
`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.
`
`1:
`_.
`
`O 1991 by Prentice-Hall. Inc.
`A Simon & Schuster Company
`Englawood Cliffs. New Jersey 07632
`
`All rights reserved. No prtrt of this book
`may be reproduced. in any form or by any
`means. without permission in writing from
`the publisher.
`
`Printed in the United States of America
`I098765432|
`
`ISBN U-lfl-H'EEHE-l:
`
`UNIX is a registered trademark of AT&T Bell
`Laboratories.
`proNET-IO is a trademark of Protcon Comoration.
`VAX. Microvax. and DECstation are trademarks
`of Digital Equipment Corporation.
`
`.
`
`Prentice-Hall lntemational (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited. Syrlmfiv
`Prentice-Hall Canada lnc.. Toronto
`Prentice-Hall His‘panoamericanu. S. A.. Mexico City
`Prentice-Hall of India Private Limited. New Delhi
`Prentice-Hall of Japan. lnc., Tokyo
`Simon & Schuster Asia Pte. Ltd.. Singapore
`Editoru Prentice-Hall do Brasil. Ltdu.. Rio de .lonc'ir'o
`
`'Wu-E-srrornrmmrr-t'me-arwr.v.7. 7:
`
`.;
`
`. G
`
`,
`
`oogle Ex. 1007, pg. 2
`
`Google Ex. 1007, pg. 2
`
`

`

`
`
`tission
`
`Chap. l4
`
`Sec. 14.4
`
`Retransmission Timer And Backofl'
`
`265
`
`nsmitting
`-______..—___—_-
`
`it needs to schedule another retransmission
`Once tcprexmr retransmits the data,
`timeout in the future. The call to tmset implements timer control according to Kam’s
`algorithm.
`It shifts the timeout in lcb_re.\'mt left ch_re.\'mtconnr bits to double the de-
`lay for each retransmission that has occurred.
`It then passes the computed delay as an
`argument to Imser, 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 retrics, 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, rcprexmt 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 u‘prexmr, which handle conges-
`tion control.
`
`.ransmitting
`
`*/
`
`14.5 Window-Based Flow Control
`
`mum) I
`
`. TCP_MAXRXT) ) .-
`
`*/
`* first drop
`:cb_ssthresh) l2;
`
`ll be called by the
`sion. Because the
`
`be processed. so
`
`count and enforces
`
`.‘P_MAXRETRIES.
`'! to abort the con-
`n! 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). Of 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 ack-
`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
`iWe say that the receiver "closes“ the window.
`
`Google Ex. 1007, pg. 3
`
`

`

`
`
`a... - H.
`
`.. .....- u _ .‘
`
`Tcprwt’ndow be
`space (i.e.. the size
`buffer).
`if TCP has
`connection (the stat
`ment size has not t
`
`silly window avoids
`tcb_window of the
`blished. tcpm'indow
`ing the window to z
`The final statel
`venisemcnt as discu
`
`14.5.3 Optlmlzlng
`
`Once a recein
`
`state and begins to 1
`an acknowledgemei
`the acknowledgeme
`ficient space becon
`and the sender will
`Although the
`minor optimization
`for the receiver to 1
`size. without waitii
`plication program t
`3! space causes the
`As the sender proi
`ment. moves back
`
`14.5.4 Adlustlns
`
`Procedure rcp
`dow advertisemen
`
`peer TCP is willin
`
`fChspler 12 discr
`
`£00
`
`llJl’: I‘IDW Control And Adaptive Retransmission
`
`Chap. [4
`
`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-SIde Sllly Wlndow Avoldanco
`
`Procedure tcprwindow implements receiver-side silly window avoidance when it
`computes a window advertisement.
`
`/* tcprwindow.c - tcprwindow */
`
`Ginclude <conf .h)
`#include <kernel.h>
`#include <network.h>
`
`/ a___._---—._--__________——-__.._....._-_..____...._.._.__________-_-—__..-----_
`
`tcprwindow - do receive window processing for a TCB
`*
`it __—__..__....-______———____-..--___-_____._-.._-___________-___-..__._________
`‘/
`
`tcprwindow (ptcb)
`int:
`struct
`tcb
`'ptcb;
`l
`
`int:
`
`window;
`
`window = ptcb->tcb_rbsize - ptcb->tcb_rbcount;
`if (ptcb->tcb_st:at:e < 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.
`
`/~k
`
`*
`‘
`
`* i
`
`*
`*/
`
`if (windowtt < ptcb—>tcb_rbsize || window < ptcb->ccb rmss)
`window = 0:
`_
`
`window = max(window, ptcb->tcb_cwin - ptcb—>tcb_rnext:);
`ptcb->t:cb_cwin = ptqb—>tcb_rnext: + window;
`return window;
`
`
`
`Google Ex. 1007, pg. 4
`
`Google Ex. 1007, pg. 4
`
`

`

`
`
`Sec. [4.5
`
`Window-Based Flow Control
`
`267
`
`to the available buffer
`Tcpm'r‘ndow 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).
`if 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. rcprwindow cannot apply receiver-side
`silly window avoidance - it merely stores the value computed for the window in field
`tt'b_wind0w of the TCB and tetums to its caller. Once a connection has been esta-
`blished. (cprwr'ndow 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 tcpm'r'ndow apply congestion avoidance tothe window ad-
`vertisement as discussed below.
`
`14.5.3 Optimizing Pertormance After A Zero Window
`
`Once a receiver advertises a zero window. the sender enters the PERSIST output
`state and begins to probe the receiverl'. 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 beats 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 Adjusting The Sender’s Window
`
`It handles win-
`Procedure tcpswindow 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.
`
`ission
`
`Chap. l4
`
`aunt of space in
`.ce sufficient for
`r of the buffer.
`
`)idance when it
`
`ice :
`wait for at
`ant: before
`
`:cb_rmss i
`
`axt) .-
`
`fChaptcr [2 discusses output processing and the output state machine.
`
`Google Ex. 1007, pg. 5
`
`Google Ex. 1007, pg. 5
`
`