Improving Round-Trip Time Estimates in Reliable Transport Protocols
`
`Phil Karn
`Bell Communications Research, Incorporated
`
`Craig Partridge
`Harvard University/BBN
`Laboratories
`
`Incorporated
`
`1. Abstract
`the
`transport protocol,
`As a reliable, end-to-end
`ARPA Transmission Control Protocol
`(TCP) uses
`positive
`acknowledgements
`and
`retransmission
`to
`guarantee
`delivery+
`TCP
`implementations
`are
`expected
`to measure and adapt to changing network
`propagation delays so that its retransmission behavior
`balances user
`throughput
`and network efficiency.
`However,
`TCP suffers
`from a problem we call
`retransmission ambiguity: when an acknowledgment
`that has been retransmitted,
`arrives
`for a segment
`there
`is no
`indication which
`transmission
`is being
`acknowledged. Many existing TCP
`implementations
`do not handle this problem correctly.
`to
`This paper
`reviews
`the various approaches
`retransmission
`and presents a novel and effective
`approach to the retransmission ambiguity problem.
`
`2. Introduction
`the
`time,
`the round-trip
`estimating
`Dynamically
`the
`the sending of a packet and
`interval
`between
`in
`receipt of its acknowledgement,
`is a key function
`many
`reliable
`transport protocols
`[5,15,22].
`Such
`estimates are used
`to ensure
`that data
`is reliably
`delivered.
`If a packet
`remains unacknowledged
`for
`too
`long,
`it
`is assumed
`to have been
`lost and is
`retransmitted.
`Estimated
`round-trip
`times are used to
`determine when these retransmissions will occur.
`Three developments
`in IP networking
`[19,20,21]
`led
`to
`increased
`interest
`in
`the problems of
`have
`estimating
`round-trip
`times.
`in the
`First, there has been an explosive growth
`size and complexity of IP internetworks, built by
`
`Permission to copy without fee all or part of this material is granted
`provided
`that
`the copies are not made or distributed
`for direct
`commercial advantage, the ACM copyright notice and the title of
`the publication and its date appear, and notice is given that copying
`is by permission of the Association for Computing Machinery. To
`copy otherwise, or to republish,
`requires a fee and/or specfic
`permission.
`
`0 1988 ACM O-89791-245-4/88/ &01/0002 $1.50
`
`subnetworks.
`existing
`interconnecting
`best
`The
`(The
`is
`the ARPA
`Internet.
`known
`example
`in the
`ARPANET
`is just one component subnetwork
`ARPA
`Internet.) The ARPA
`Internet has highly vari-
`able
`round-trip
`times. Because
`its paths are very
`complex,
`it also tends to lose more packets.
`Second, there has been a large increase in traffic
`on some of
`the major
`IP networks. Higher
`traffic
`loads have
`led
`to serious network
`congestion
`on
`some parts of the ARPA
`Internet
`[16,18]. Like net-
`work size, congestion
`is known
`to cause highly vari-
`able round-trip
`times and higher packet loss rates.
`Finally,
`recent research has shown that the stan-
`dard approaches
`to estimating
`round-tip
`times for the
`Transmission Control Protocol
`(TCP) are inaccurate
`if packets are lost or round-trip
`times are highly vari-
`able [9,24]. This discovery
`is distressing because it
`suggests
`that
`the mechanism
`reliable
`protocols
`depend upon
`to handle
`loss and variable
`round-trip
`times, namely
`the estimation of round-trip
`times, may
`not work well.
`Concern about the accuracy of estimated round-
`times has led to some interesting
`research
`into
`tip
`reliability mechanisms which are less dependent on
`round-trip
`estimates
`[2,24].
`The authors, however,
`take a different approach
`that
`tries
`to improve
`the
`data used to compute
`round-trip
`time estimates.
`In
`this paper we present an analysis of this work.
`
`3. The TCP Algorithm
`future
`to predict
`attempt
`TCP
`implementations
`round-trip
`times by sampling
`the behavior of packets
`sent over a connection and averaging
`those samples
`time estimate, SR7T.
`into a “smoothed”
`round-trip
`When a packet
`is sent over a TCP connection,
`the sender times how long it takes for it to be ack-
`nowledged, producing a sequence, S, of round-trip
`time samples: SI,S;?,S~....
`
`Petitioners' Exhibit 1045
`Page 0001
`
`

`

`With each new sample, Si, the new SRTT
`computed
`from the formula:
`
`is
`
`SR~i+l = (aXSRrri)+(
`
`l-ol)XSi
`
`is the current estimate of the round-trip
`where SR~i
`is the new computed value, and ~1 is a
`time, SR7Ti+l
`constant between 0 and 1 that controls how rapidly
`the SRTT adapts to change.
`the amount
`(RTO,),
`The retransmission
`time-out
`of time the sender will wait for a given packet to be
`acknowledged,
`is computed
`from SR7Tp The
`for-
`mula is:
`
`RTO, = ~xSR?T,
`
`than 1, chosen such
`where p is a constant, greater
`that there is an acceptably small probability
`that the
`round-trip
`time for the packet will exceed RTO;.
`
`3.1. General Observations
`the
`to observe about
`There are several
`things
`to
`algorithm.
`First,
`it can be viewed as an attempt
`approximate
`the next value from a function R, where
`R(i) is the actual round-trip
`time for packet
`i. Given
`the sequence of measured round-trip
`times,
`
`S = SlJ2S3,...Ji-l
`
`which correspond
`
`to the values of R:
`
`those values
`from
`we hope that the RTO computed
`will be a good upper bound on R(i),
`the round-trip
`time for the next packet. Notice
`that if the measured
`round-trip
`times, S, are inaccurate
`then the RTO
`is
`probably
`incorrect;
`this problem
`is examined
`in the
`next section.
`that the values of the
`One should also observe
`constants CL and
`/3 have
`important effects on
`the
`behavior of the algorithm.
`the SRTT
`The value of a controls how rapidly
`[ll]
`has
`adjusts to changing
`round-trip
`times. Mills
`measured network
`round-trip
`times and recommends
`that there be two values
`for a, depending on the rela-
`tive values of
`the sample, Si, and SRi’Tp Mills
`observed
`that round-trip
`times are roughly Poisson
`distributed,
`but with brief periods of high delay.
`During
`these periods, he found that the standard way
`of computing SRTT and RTO often did not adapt
`swiftly enough, and the TCP sender would unneces-
`sarily
`retransmit packets because
`the RTO was set
`too low. As a result, he suggested a nonlinear
`filter
`where a
`is smaller when SR7T,~Si, allowing
`the
`SRTT
`to adapt more swiftly
`to sudden increases
`in
`network delay.
`for p is harder because it has
`Choosing a value
`important and conflicting
`effects on individual
`user
`throughput and overall network efficiency
`[IS]. To
`
`throughput p should be only a little
`achieve optimal
`greater than 1. This keeps the RTO very close to the
`SRTT and ensures
`that packet
`loss will be quickly
`detected. Detecting
`lost packets quickly
`is important
`for good throughput, since the end-to-end
`flow con-
`trol mechanisms
`in reliable protocols
`like TCP will
`cause the sender to stop transmitting
`new packets if a
`packet
`remains unacknowledged
`for much
`longer
`than the round-trip
`time.
`is
`throughput
`for
`is good
`Unfortunately,
`what
`the
`disastrous
`for efficient network utilization.
`If
`RTO
`is nearly equal to the SR’IT
`(i.e., if p is near
`unity)
`then a
`large number of packets will
`be
`retransmitted unnecessarily because the sender times
`out
`too soon. For example, consider
`the situation
`where RTO = SRn,
`(i.e, p=l), and the SRTT
`is an
`accurate median of the round-trip
`times.
`In this case,
`roughly half of all packets will be timed out and
`retransmitted
`because
`their acknowledgement
`took
`too
`long, burdening
`the network with unnecessary
`To minimize
`retransmissions,
`p
`retransmissions.
`should be chosen such that the RTO will be a high’
`The TCP
`upper
`limit
`on
`the
`round-trip
`times.
`specification
`[21] recommends a value of p=2 as a
`reasonable balance. Another possibility
`suggested by
`Van Jacobson
`[7,8]
`is
`to vary p based on
`the
`observed
`variance
`in measured
`round-trip
`times,
`although
`this is outside
`the immediate scope of this
`paper.
`
`3.2. Back-off
`Whenever a timeout occurs, virtually every TCP
`implementation
`increases
`the RTO by some factor
`before
`retransmitting
`the unacknowledged
`data.
`Should
`the new, larger RTO expire yet again before
`the retransmission
`is acknowledged,
`it
`is increased
`still
`further.
`This
`technique
`is known as back-@.
`(Back-off
`is performed
`independently of SRTT calcu-
`lation, since without an acknowledgment
`there is no
`new
`timing
`information
`to be fed into
`the calcula-
`tion). A variety of algorithms
`are used since
`the
`TCP specification
`does not prescribe one. Some
`(e.g., Berkeley UNIX’)
`step
`through a
`table of
`arbitrary
`back-off
`factors
`for
`each
`successive
`retransmission;
`others simply double
`the RTO
`(i.e.,
`perform binary exponential
`back-off)
`for each con-
`secutive
`attempt. Whatever
`the algorithm,
`TCP
`back-off
`is essential
`in keeping
`the network stable
`when sudden overloads cause packets to be dropped.
`When
`the overload condition disappears, packet
`loss
`stops and the TCPs reduce their RTO to their normal
`SRI-T-based values.
`
`1 UNIX
`
`is a trademark of AT&T Bell Laboratories.
`
`Petitioners' Exhibit 1045
`Page 0002
`
`

`

`4. Sampling Round-Trip Times
`A key assumption of the TCP algorithm is that
`the sequence of round-trip samples is an accurate
`measurement of the true network round-trip
`times
`(i.e., that s,=R(l),s,=R(2), etc.). It has recently been
`shown
`that
`the two standard sampling methods,
`measuring from the first transmission and measuring
`from the most recent transmission, give inaccurate
`results [9,24].
`This inaccuracy is caused by packet retransmis-
`sion. The information carried in the packet headers
`of TCP and most other reliable protocols does not
`indicate if an acknowledgement is in response to the
`original transmission of a packet or a retransmission.
`As a result, a round-trip
`time measurement for a
`retransmitted packet is ambiguous. We will call this
`problem retransmission ambiguity.
`
`4.1. Measuring From the First Transmission
`Many TCP implementations measure round-trip
`times from the first transmission of a packet. When-
`ever an acknowledgement is received, the round-trip
`time is computed from the first time the packet was
`sent, regardless of how many times the acknowledged
`packet has been retransmitted,
`Sampling from the first transmission may cause
`the SRlT
`to grow without bound when there is loss
`on the network. When there is loss, the TCP sender
`must retransmit
`lost packets.
`If we look at the
`sequence of samples, SF, we discover that it contains
`samples of two types.
`If pi is a boolean function
`which is 0 if the acknowledgement for packet i is
`acknowledging a retransmission, SF can be expressed
`as:
`
`fSi if yi#O
`
`If we look at the values of XL those samples which
`are derived
`from
`the acknowledgements of
`retransmissions, we find that they are a function of
`the true round-trip time, R(i), the SR’IT, and the par-
`ticular retransmission of packet i, ri, where ri>O,
`which is being acknowledged:
`ST= R(i)+r@TOi = R(i)+-r&dRTI’i
`
`si will be used to compute the new smoothed round-
`trip time, SRTT+r, Plugging < into the SR’IT func-
`tion gives:
`SRTTi,l = (olxSRTT)+(l-a)X(R(i)+riXpxSRTTi)
`= (CWSRTTJ+( l-a)xR(i)+((pr,-QrJXSRTTi
`Since Ckcl<l
`the factor (pr,-c@ri)
`is greater than
`zero and distorts the function, causing it to inflate the
`value of the SRTT. Inflated round-trip time estimates
`may not be a problem if the original reason for the
`high loss rate was network congestion, because
`
`congestion tends to increase round-trip times anyway.
`It is also acceptable if the loss rate is very low since
`the accumulated error is so small that it will probably
`have no noticeable effect on the SRTT. However, if
`the path is lossy (e.g., a noisy packet radio channel
`operating without link level acknowledgements), the
`SRTT grows and throughput unnecessarily decreases
`to low levels.
`
`4.2. Measuring From the Most Recent Transmis-
`sion
`
`Another popular method measures round-trip
`time from the most recent transmission of a packet.
`The implicit assumption in this method is that the
`RTO is accurate; if a packet has to be retransmitted
`then previous
`transmissions have almost certainly
`been Iost.
`this assumption is often false. If
`Unfortunately,
`the RTO is smaller than the true round-trip time, ack-
`nowledgements for previous transmissions may arrive
`after a retransmission.
`If 2i is a boolean function
`which returns 0 if the acknowledgement is for a pre-
`vious transmission, the sequence of sampled values,
`S, is:
`
`if 2i~
`Si
`‘iZ = F ‘ if r.$l I
`{
`At first glance this doesn’t look too bad. q is a
`value between 0 and the RTO, which might be
`expected to distort the SRTT a bit, but doesn’t have
`the growth term caused by measuring from the first
`transmission.
`But the picture is not quite so rosy. Recall that
`the RTO is intended as an estimate of the maximum
`possible round-trip
`time.
`If an acknowledgement
`arrives after the RTO has expired, it is highly likely
`to come very shortly afterwards.
`In other words,
`instead of being randomly distributed between 0 and
`the RTO, siis likely to be very close to 0 (recall that
`the sample timer was reset when
`the RTO had
`elapsed). This will cause the SR’IT
`to decline,
`reducing the RTO, and increasing the likelihood
`that
`a packet will be acknowledged just after the RTO has
`The SRTT stabilizes at an unreasonably
`expired.
`low estimate. Unnecessary data retransmissions
`occur constantly, useful
`throughput drops sharply,
`and network bandwidth is wasted.
`Observe that the problem of a declining SRTT
`could be avoided if
`the RTO were set extremely
`high, so high that no packet could survive that long
`that
`unacknowledged. Recall however,
`for high
`throughput, the RTO cannot be much larger than the
`SRTT. An algorithm which requires an extremely
`high RTO will give unacceptable performance across
`a lossy path.
`
`Petitioners' Exhibit 1045
`Page 0003
`
`

`

`4.3. Ignoring Round-Trip Times for Packets That
`Have Been Retransmitted
`Some implementations simply ignore round-trip
`time samples tainted by retransmission.
`This method works, provided the true round-trip
`time never grows faster than the algorithm can adapt.
`If there is a sudden increase in network round-trip
`time (e.g., when the failure of a primary path causes
`packets to be sent via a slower secondary path), and
`if the new path delay becomes larger than the RTO,
`all samples will be discarded, because every packet
`will be retransmitted before the acknowledgement
`comes back. Note that if the RTO is reasonable (i.e.,
`if p is chosen well) then the chance of a dramatic
`surge is quite small. But the consequences of such a
`surge are truly disastrous -
`the sender is stuck with
`an unrealistically short RTO that it has little chance
`or no chance of correcting. Once again, there are
`numerous unnecessary retransmissions, throughput
`drops sharply and network capacity is wasted.
`
`4.4. Karn’s Algorithm
`Very recently a new sampling method has been
`suggested by one of
`the authors. This method
`addresses the problems with ignoring round-trip times
`of retransmitted packets.
`The fundamental notion of I&m’s algorithm is
`to use RTO back-off to collect accurate round-trip
`time measurements uncontaminated by retransmission
`ambiguity. The rule is as follows:
`When an acknowledgement arrives for a packet
`that has been sent more
`than once (i.e.,
`retransmitted at least once), ignore any round-
`trip measurement based on this packet, thus
`avoiding the retransmission ambiguity problem.
`In addition,
`the backed-off RTO for
`this packet
`is kept for
`the next packet. Only when it (or a
`succeeding packet)
`is acknowledged without an
`intervening
`retransmission
`will
`the RTO be
`recalculated
`from SRlT.
`The last provision ensures that new and accurate
`round trip measurements will be taken and fed into
`the SRTT estimate regardless of any sudden increase
`in round-trip delay.
`If the increase is large, the RTO
`may oscillate between the backed-off value necessary
`to avoid an unnecessary retransmission and the value
`calculated from SR’IT. However, the SR’lT will con-
`verge
`to
`the correct value, and unnecessary
`retransmission will stop.
`How quickly
`the SRTT converges to the new
`round-trip
`time depends on the back-off algorithm
`and the SRTT smoothing algorithm, but typically this
`convergence is quite fast. To prevent unnecessary
`retransmissions, the RTO must be greater than the
`new round-trip time. To achieve this new RTO value
`
`the SRTT must be at least as large as the new
`round-trip time, s, divided by p. (For simplicity
`in
`the proof, we assume that the new value for s does
`not vary). Reaching the new RTO takes n valid sam-
`ples, where n is the minimum value for which the
`following equality in terms of the new RTT, s, and
`the old SRTT, z, is true:
`
`;
`
`I
`
`(zxa”) + ~((sx(l-wa(‘-‘))
`
`”
`
`In the worst case s-z is almost s (i.e., s > z), so the
`z term may be ignored. Dividing
`the remaining terms
`by s, we find that the upper limit on n is given by the
`solution to:
`
`Using typical values of CL = 0.875 and p = 2, n is
`only 6. Since the number of required valid samples
`is small, convergence is usually swift.
`A TCP implementation using Kam’s algorithm
`and Mills’ nonlinear filter has been in heavy use on
`perhaps the worst medium ever used to pass IP
`datagrams: amateur packet radio [lo]. Despite packet
`loss rates often exceeding 50%, SRIT values remain
`quite stable, changing only
`in
`response to
`true
`changes in round-trip time. Packets lost due to noise
`leave the SRTT unaffected.
`
`4.5. Sampling RTTs in Parallel
`the best
`While Kam’s algorithm
`is currently
`available solution
`to the sampling problem, it
`is
`worth
`taking a few paragraphs to discuss another
`class of sampling algorithms which have been
`developed recently. These algorithms depend on the
`fact that most transport protocols send more than one
`packet at a time, and as a result it is possible to take
`multiple round-trip time samples in parallel.
`One such algorithm has recently been developed
`in an implementation of the Reliable Data Protocol
`(RDP), which uses the TCP algorithm to estimate
`round-trip times [4,17,22].
`It relies on the fact that
`networks almost always preserve packet ordering.
`If
`two packets are sent close together it is-likely
`that
`they will
`reach their destination in the order they
`were sent, and be acknowledged in the same order.
`So if an acknowledgement for packet i is received
`after the acknowledgement for packet j, where j>i,
`it
`is a strong hint that the acknowledgement is for a
`retransmission of packet
`i. We can check the
`retransmission count, ri, for packet i, so this observa-
`tion gives a sampling method.
`Measuring from the lirst transmission, a sample
`for packet i, Si, should be discarded if:
`
`Petitioners' Exhibit 1045
`Page 0004
`
`

`

`i.e., those samples for which -@I. The problem is
`that most sampling methods are inadequate approxi-
`mations of y, and either exclude too many good sam-
`ples or include too many bad samples.
`Kam’s algorithm solves this problem by accept-
`ing only good samples and using the retransmission
`back-off strategy to ensure that good samples will
`eventually be available even
`if
`round-trip
`times
`increase dramatically.
`
`6. Deficiencies in the TCP Algorithm
`to
`So far
`this paper has focussed on how
`improve round-trip estimates by using better sam-
`pling methods. Before con&ding we would like to
`touch briefly on some other ways that round-trip esti-
`mates can be improved.
`One improvement is to sample more frequently.
`Some protocol
`implementations sample round-trips
`only once per sending window, leading to poor esti-
`mates because the estimator does not have enough
`recent samples to detect changes in the round-trip
`time.
`Another possible improvement is to chose a new
`algorithm for estimating the RTO. The TCP algo-
`rithm assumes that a weighted average, the SRTT,
`adjusted by some estimate of variance, p, is a good
`approximation of the behavior of the network func-
`tion, R. Recently, research by Jacobson has shown
`that R is a more complex function
`than a simple
`average can accurately model [6,8]. Encouragingly,
`however, Jacobson’s work also suggests that it may
`be possible to predict the values generated by R with
`functions of roughly
`the same complexity as the
`functions presented in section 2.
`
`7. Conclusion
`Much attention has recently been paid to the
`question of whether one can accurately sample
`round-trip times over a transport protocol connection.
`The authors have shown that round-trip times can be
`accurately sampled and have presented a simple
`method that gives good round-trip time samples.
`
`8. Acknowledgements
`like to thank Will Leland
`The authors would
`and Chase Cotton for their useful comments on this
`paper.
`
`.
`
`An acknowledgement for some packet j,
`j>i, has already been received, and
`.
`r,+O
`The first test can only be applied if packets can be
`acknowledged when they are received out of order.
`Such acknowledgements are called extended or selec-
`tive acknowledgements. RDP supports extended ack-
`nowledgements. TCP does not, although considera-
`tion is being given to adding this facility
`[l].
`The performance of this sampling method is
`highly dependent on the number of parallel transmis-
`sions a protocol implementation will support. Obser-
`vations suggest that the algorithm keeps accurate
`round-trip estimates at much higher loss rates than
`sampling from the first transmission.
`Other estimation methods that use multiple sam-
`ples taken in parallel have been explored in Mills’
`work on synchronizing network clocks [12,13,14].
`Synchronizing clocks involves problems of handling
`a certain amount of bad data, caused by noisy links
`or faulty clocks. The techniques used to eliminate
`such bad values can also be applied to the problem
`of extracting good round-trip
`times from a set of
`several round-trip times collected at roughly the same
`time.
`Parallel sampling methods tend to suffer from
`two problems. First, they can be adversely affected
`by the loss of an entire group of packets; all the sam-
`ples become bad. Second, they often fail when a
`network is congested. When a network is congested,
`most protocols attempt to reduce the data they put on
`the network by limiting
`themselves to sending one
`packet at a time. Unfortunately, a network is most
`likely to drop packets when it is congested. Thus the
`ability to take parallel samples is lost at precisely the
`time we would most like to have an accurate sam-
`pling method. One could blur the notion of “paml-
`lel” and simply apply these techniques after every n
`samples, where n is chosen to equal the number
`packets that are normally in flight. But when the pro-
`tocol is in one-packet-at-a-time mode, recomputing
`the SRIT must be delayed until n samples have been
`collected, which could be a long time, at minimum it
`is roughly nxSRTT.
`
`5. The Perfect Sampling Method
`It is worth noting for a moment that most of the
`methods discussed in
`this section are attempts to
`achieve the sampling function y discussed in section
`3.2. Recall that y was a boolean function which
`returned 0 if the sample was taken from the ack-
`nowledgement of a retransmission. The sampling
`methods want to use only those samples measuring
`the time between the first transmission of a packet
`and the acknowledgement of that first transmission,
`
`Petitioners' Exhibit 1045
`Page 0005
`
`

`

`2.
`
`3.
`
`4.
`
`5.
`
`Bibliography
`1.
`Braden, Robert T., Selective Acknowledgments
`Draft ARPANET Working Group
`in TCP.
`Requests for Comments.
`Clark, David D., Lambert, Mark L., and Zhang,
`Lixia. NEI’BLT:
`A Bulk Data Transfer Proto-
`col; RFC998.
`In ARPANET Working Group
`Requests for Comments, no. 998. SRI Intema-
`tional, Menlo Park, Calif., March 1987.
`Edge, Stephen William.
`An Adaptive Timeout
`Algorithm
`for Retransmission Across a Packet
`In Proceedings
`of
`Network.
`Switching
`SIGCOMM
`‘83, Association
`for Computing
`Machinery, 1983.
`Hinden, Robert M. and Partridge, Craig. Ver-
`sion 2 of
`the Reliable Data Protocol. Draft
`ARPANET Working Group Requests for Com-
`ments.
`Infor-
`for Standards,
`International Organization
`mation processing
`systems
`- Open Systems
`- Connection oriented
`trun-
`Interconnection
`sport protocol specification.
`International Stan-
`dard, no. 8073. ISO, Switzerland. 1986.
`Internet
`Presentation
`to
`the
`Jacobson, Van.
`End-To-End
`Services Task Force. April
`16,
`1987.
`Interpacket Arrival Variance
`Jacobson, Van.
`and Mean. Letter to the TCP-IP mailing
`list, 15
`June 1987.
`Jacobson, Van. Retransmit Timers: Theory and
`Practice, working
`title of draft paper.
`for
`Jain, Raj, Divergence of Timeout Algorithms
`In Proceedings Fifth
`Packet Retransmissions.
`Annual
`International Phoenix Conference on
`Computers and Communications, Scottsdale,
`AZ, March 26-28, 1986.
`10. Kam, P. R., Price, H., Diersing, R. Packet
`In IEEE Journal
`Radio in the Amateur Service.
`on Selected Areas
`in Communications, May
`1985.
`
`6.
`
`7.
`
`8.
`
`9.
`
`Experiments;
`Internet Delay
`David.
`11. Mills,
`In ARPANET Working Group
`RFC889.
`Requests for Comments, no. 889. SRI Intema-
`tional, Menlo Park, Calif., Dec. 1983.
`12. Mills, David.
`Algorithms
`for Synchronizing
`In ARPANET Work-
`Network Clocks; RFC9.56.
`ing Group Requests for Comments, no. 956.
`SRI International, Menlo Park, Calif., Sep. 1985.
`
`13.
`
`14.
`
`15.
`
`16.
`
`17.
`
`18.
`
`19.
`
`20.
`
`21.
`
`22.
`
`23.
`
`24.
`
`in Network Clock
`Experiments
`Mills, David.
`In ARPANET Work-
`Synchronization; RFC957.
`ing Group Requests for Comments, no. 957.
`SRI International, Menlo Park, Calif., Sep. 1985.
`Mills, David. Network Time Protocol; RFC958.
`In ARPANET Working Group Requests for Com-
`ments, no. 958. SRI International, Menlo Park,
`Calif., Sep. 1985.
`for
`intervals
`timeout
`Morris, Robert J.T. Fixing
`lost packet detection
`in computer communica-
`In AFIPS Conference Proceed-
`tion networks.
`ings, 1979 National
`Computer
`Conference.
`AFIPS Press, Montvale, Jew Jersey.
`IP/TCP
`in
`Nagle,
`John. Congestion Control
`In ARPANET Working
`Networks;
`RFC896.
`Group Requests for Comments, no. 896. SRI
`International, Menlo Park, Calif., Jan. 1984.
`Implementing
`the Reliable
`Partridge, Craig.
`In Proceedings of the
`Data Protocol
`(RDP).
`I987 Summer USENIX Conference, Phoenix,
`Arizona.
`Perry, Dennis G. Congestion in the ARPANET.
`Letter
`to the TCP-IP Mailing
`List, October 1,
`1986.
`In
`Internet Protocol; RFC791.
`Pastel, J., ed.
`ARPANET Working Group Requests for Com-
`ments, no. 791. SRI International, Menlo Park,
`Calif., Sep. 1981.
`Postel, J., ed.
`Internet Control Message Proto-
`col; RFC792.
`In ARPANET Working Group
`Requests for Comments, no. 792. SRI Intema-
`tional, Menlo Park, Calif., Sep. 1981.
`Postel, Jon, ed. Transmission Control Protocol;
`In ARPANET Working Group
`RFC793.
`Requests for Comments, no. 793. SRI Intema-
`tional, Menlo Park, Calif., Sep. 1981.
`
`Velten, David, Hinden, Robert and Sax, Jack.
`In ARPANET
`Reliable Data Protocol; RFC908.
`Working Group Requests for Comments, no.
`908. SRI International, Menlo Park, Calif., July
`1984.
`Watson, Richard W. Timer-Based Mechanisms
`in Reliable Transport Protocol Connection
`Management.
`Networks
`Computer
`1981,
`North-Holland Publishing Company.
`Zhang, Lixia. Why TCP Timers Don’t Work
`In Proceedings of SIGCOMM ‘86, Asso-
`Well.
`ciation
`for Computing Machinery.
`
`Petitioners' Exhibit 1045
`Page 0006
`
`