Subject: Conservative behaviours
From: Luigi Rizzo <[email-masked]>
To: [email-masked]
Date: Tue, 6 Feb 1996 14:22:19 +0100 (MET)

Many comments on my previous messages (thanks to those who responded,
BTW) insist on the need of being conservative in the estimation of
RTTs (and in general, in the generation of traffic, which is the
ultimate reason for being conservative).

I completely agree, and actually I would like to have a more strict
control on this. It is the sender which might constitute a danger
for the network, so we should force this one, not the receiver, to
have a strictly controlled and conservative behaviour. The other
party should only have the minimum possible trust.

In the case of RTT estimates: we trust the other party for not
acknowledging data which have not been received yet, so we know
that the RTT measure reflects at least the propagation delays plus
the effect of queueing at intermediate nodes.

But how do we know what is their ack generation policy ? Some might
send immediate ACKs, e.g. in the case of short packets, or when
there are pending data in the other direction. Some might implement
RFC122 and ack every other segment, so the RTT is the propagation
delay plus the interarrival time.  Some might use delayed ack, so
the RTT might be up to .5 sec larger than the real one. Etcetera.

We cannot prohibit any of the above behaviours, they are all legal and
in many cases there are good reasons to use them. And we cannot tell
which one is being used. The conclusion is that even if we ask the
other party to have a conservative behaviour, then we cannot trust
it and we have to apply additional safety factors.

This leads to a general lack of clarity of the mechanisms, some
loss of control on the actual safety factors that are being used,
and possibly leads to exceedingly large estimates.

In my opinion, it would be cleaner (and possibly easier and more
efficient) to just ask the receiver to help us in determining the
real propagation delay. Don't ask it to be conservative, as we
cannot trust it anyways. Conservative behaviour can (and must)
be enforced by the sender.

	Thanks
	Luigi
====================================================================
Luigi Rizzo                     Dip. di Ingegneria dell'Informazione
email: [email-masked]       Universita' di Pisa
tel: +39-50-568533              via Diotisalvi 2, 56126 PISA (Italy)
fax: +39-50-568522              http://www.iet.unipi.it/~luigi/
====================================================================

From: Luigi Rizzo <[email-masked]>
Subject: Re: Thoughts about RFC1323 timestamps
To: [email-masked]
Date: Tue, 6 Feb 1996 14:31:23 +0100 (MET)
Content-Length: 2770

Thanks to the people who sent comments on the message and allowed me to
find a mistake in my proposal.

Following suggestions from David Borman and Matt Mathis, I have changed
slightly my proposal on which timestamp to echo: now it should read as
follows:

    keep rule #1 (don't update TSrecent with out-of-sequence
    segments) and #2 (don't use dup acks for RTT estimates) but
    use the timestamp echo reply field in dup acks to carry the
    timestamp of the last received segment, if this is more recent
    than ts_recent.

What was wrong in my original email was the word "_always_" instead
of "in dup acks" here.

In BSD 4.4, it can be implemented by the following code

    tcp_out(struct tcpcb *tp, struct tcpopt* to)
    {               
	u_long  tmp=tp->ts_recent;
	if ((to->to_flag & TOF_TS) &&
		!(tp->t_flags & TF_DELACK) &&
		TSTMP_LT(tmp, to->to_tsval)) 
		    tp->ts_recent=to->to_tsval;
	(void) tcp_output(tp);
	tp->ts_recent=tmp;
    }       

and by replacing calls to tcp_output(tp) with tcp_out(tp, &to)
from within tcp_input().
[Actually, some calls to tcp_output() can remain untouched because
you know that the test would fail.]

The only scenario where my code produces different RTT measurements
from the current one is when:

    * incoming packets are lost or reordered, and
    * the last valid ack (say for packet #1) gets lost or reordered;

As an example:

    incoming packets:		#0	#1	#3	#2
    ACK/TSecr, current code	#0,TS#0	#1,TS#1	#1,TS#1	#3,TS#2
    ACK/TSecr, new code		#0,TS#0	#1,TS#1	#1,TS#3	#3,TS#2
					(lost)     ^^^^

The sender interprets the dup ack for #3 as a non dup ack, and uses
the timestamp to update the RTT estimate.  With the new code, the
TSecr contains TS#3 instead of TS#1.

To me, this seems acceptable because:

* it is only triggered by the combination of two hopefully unlikely
  events;
* the new sample for the RTT that comes out is not shorter than the real
  round trip time for the segment, so it is not an underestimate of the
  RTT, just a value which is close to the real one;
* a shorter-than-usual sample does not necessarily reduce the RTO,
  because it might increase RTTVAR which has a large weight in the
  computation of the RTO;
* current practice already considers dup acks to carry unreliable
  (exceedingly large) TSecr, and discards them.

Does this look reasonable now ?

	Thanks
	Luigi
====================================================================
Luigi Rizzo                     Dip. di Ingegneria dell'Informazione
email: [email-masked]       Universita' di Pisa
tel: +39-50-568533              via Diotisalvi 2, 56126 PISA (Italy)
fax: +39-50-568522              http://www.iet.unipi.it/~luigi/
====================================================================

Date: Tue, 6 Feb 96 01:19:00 PST
From: [email-masked] (Biswanath Mukherjee)
To: [email-masked]
Subject: Infocom96 Conference Program

(We apologize if you are receiving multiple copies of this message since
our mailing list is constructed from multiple different sources.)
=========================================================================

Announcing...

IEEE Infocom '96 ---- Networking the Next Generation
====================================================

Information about Infocom96, the Fifteenth Annual Joint Conference
of the IEEE Computer and Communications Societies, is now available
through the World Wide Web at

http://www.research.att.com/~hgs/infocom96

Here are a few highlights:

* Abstracts of all 176 accepted papers are now available on the web.

* Conference Location: HOTEL NIKKO.  SAN FRANCISCO, California, USA

* Conference Dates: Tutorials:  March 24-25, 1996
                    Conference: March 26-28, 1996

* Early (Discounted) Registration Deadline: February 23, 1996.

* 44 Technical Sessions (in 4 parallel tracks), where 176 papers will
  be presented on the most recent advances in all aspects of networking,
  including multimedia, wireless, optical, multicasting, ATM, network
  management, queueing networks, network security, and system software.

* Six tutorials by leading experts on the following topics:
  -- Wireless Communication Networks by Don Cox, Stanford University
  -- Image and Video Compression by Avideh Zakhor, UC Berkeley
  -- Optical Networking by Rajiv Ramaswami, IBM
  -- High-Speed Networks: From Ethernet to ATM by Pravin Varaiya, UC Berkeley
  -- Broadband Networking: Models and Techniques for Control, Design and
     Management by Debasis Mitra, AT&T Bell Laboratories
  -- Multimedia Conferencing over the Internet by Van Jacobson, LBL

* Six panels on the challenges and promises of future networks:
  -- Wireless Multimedia Networks: Issues, Challenges and Directions
  -- Inter-operability in Multi-vendor ATM Networks
  -- How Much Synchronization is Needed for Multimedia Communication?
  -- Can High-Speed Wide-Area Networks be Effectively Controlled?  
  -- Simulation Modeling of High Speed Networks: State of the Art
     and Challenges
  -- The Economics of the Internet

* Keynote Speaker: Arno Penzias, AT&T Bell Laboratories

* Plenary Session--Hamid Ahmadi, IBM,
  "Wireless and Mobile Networking - the Enterprise Perspective"

* Hard copies of the Advance Program have been mailed to all IEEE
  Computer and Communications Society Members, as well as to all
  corresponding authors of Infocom96 submissions.

For further information, please write to "[email-masked]".

Biswanath Mukherjee
Technical Program Chair, IEEE INFOCOM '96
University of California
Department of Computer Science
Davis, California 95616, USA
Email:     [email-masked] (for all correspondence re: Infocom '96)
Telephone: +1-916-752-4826
Fax:       +1-916-752-4767

From: David Borman <[email-masked]>
Date: Mon, 5 Feb 1996 14:38:33 -0600
To: [email-masked]
Subject: Re: Thoughts about RFC1323 timestamps
Cc: [email-masked], [email-masked]

> From: Luigi Rizzo <[email-masked]>
> Subject: Re: Thoughts about RFC1323 timestamps
> Date: Mon, 5 Feb 1996 19:20:50 +0100 (MET)
> 
> > The problem is that you don't know whether the out-of-sequence segment
> > is due to a lost packet, or just packet reordering.  If you receive
> > packet #1 and delay the ack, and then get #3 & #2, you want the TSecr
> > in the dup-ack sent in response to #3 arriving out of order to be the TS
> > from #1, and then when you get #2, you want the TSecr to be from #2,
> > even though it acks #2-#3.  With your change, the ack in response to
> 
> Exactly what I meant to do. I am sure I did not explain it clearly, but
> the following should work:
...

Ok, it's a bad example.  Let me fix that.  On an idle connection, two
packets are received out of sequence, #2, #1.  When the ack is sent
for #2, currently TSrecent is not updated, it stays at TS#0 (the
previous packet).  Then when #1 is acked, TSrecent is updated with
TS#1, and when the other side computes the RTT it includes the
reordering of the packets.  With your change, when #2 arrives on the
quiet connection, TSrecent is updated with TS#2 and sent in the
ack.  Then when #1 arrives, its TSecr is older than TSrecent, so the
ack for #1-#2 that gets sent has TSecr#2, not TSecr#1, and the
RTT estimate does *not* include the reordering of the packets.

Look at the example in RFC1323, pages 16-17.  This is the one that
your proposed change breaks.  I just can't agree with something
when it is so easy to come up with a scenario where it produces
the wrong RTT measurement.

		-David Borman, [email-masked]

From: Luigi Rizzo <[email-masked]>
Subject: Re: Thoughts about RFC1323 timestamps
To: [email-masked] (David Borman)
Date: Mon, 5 Feb 1996 19:20:50 +0100 (MET)
Cc: [email-masked], [email-masked]
Content-Length: 3403

> The problem is that you don't know whether the out-of-sequence segment
> is due to a lost packet, or just packet reordering.  If you receive
> packet #1 and delay the ack, and then get #3 & #2, you want the TSecr
> in the dup-ack sent in response to #3 arriving out of order to be the TS
> from #1, and then when you get #2, you want the TSecr to be from #2,
> even though it acks #2-#3.  With your change, the ack in response to

Exactly what I meant to do. I am sure I did not explain it clearly, but
the following should work:

When you get #3, even if it is out-of-sequence, there is a DELACK
pending: so you know that you are not sending a dup ack, and use
the timestamp from #1 (in TSrecent). TSrecent is not changed because
#3 is not in sequence.  When you get #2, it advances the ack pointer,
so you also advance TSrecent, and use this as the TSecr.

> #3 would have the TS from #3, and the ack in response to #2 would have
> the TS from #3.  In this scenario, the computed RTT from both ACKs
> will be underestimated.

see above.

> > One can object that the last valid ack is lost, and one subsequent
> > dup ack is not recognized as a dup thus causing the RTT to be
> > updated.
> 
> The whole point of doing RTT measurement is to have an accurate
> RTT value so you can avoid spurious retransmissions.  With that
> in mind, if there is the possibility of error, it is better to
> err on the side of a value that is too large than a value that
> is too small.

agreed.
But note that a smaller RTT does not necessarily mean a smaller
RTO: the smaller RTT might actually cause an increase
in RTTVAR, and since

	RTO = SRTT + 4RTTVAR,

this might even be more conservative than current code.

> > But as shown in Braden's message of April 93, the RTT
> > derived from these dups can have very large errors, and this is
> > the reason why he recommends not to use them to update the RTT.
> 
> In examples where the last valid ack is lost, the subsequent
> dup ack will not be wildly inaccurate, just slightly inflated.
> The cases of very large errors have to do with packets arriving
> after the connection has been idle for some period of time.

In general, if T is the interval between subsequent segments,
delayed acks are delayed by DT=min(T, tcp_fasttimo).  Subsequent
dup acks just reflect the time since the last in-sequence segment,
plus, possibly, a DT.  The nth dup ack has an error of about nT+DT.
Which one you get depends on how many segments have been lost, etc.

Now, I believe that the error (and its sign) will be irrelevant
until it is comparable with the actual RTT, the granularity of
timers, and the minimum RTO (2 seconds now).

It might become important as these values becomes much smaller,
but my feeling is that the minimum RTO will always be forced
to be much larger than any reasonable error in the estimate of RTT
for sufficiently fast networks.

For slow networks, where you get less than a few packets per second,
the overestimate might really become too large.

	Luigi
====================================================================
Luigi Rizzo                     Dip. di Ingegneria dell'Informazione
email: [email-masked]       Universita' di Pisa
tel: +39-50-568533              via Diotisalvi 2, 56126 PISA (Italy)
fax: +39-50-568522              http://www.iet.unipi.it/~luigi/
====================================================================

From: David Borman <[email-masked]>
Date: Mon, 5 Feb 1996 11:17:20 -0600
To: [email-masked]
Subject: Re: Thoughts about RFC1323 timestamps
Cc: [email-masked], [email-masked]

> From [email-masked] Sun Feb  4 17:04 CST 1996
> From: Luigi Rizzo <[email-masked]>
> Subject: Re: Thoughts about RFC1323 timestamps
> To: [email-masked] (Matt Mathis)
> Date: Sun, 4 Feb 1996 23:56:51 +0100 (MET)
> Cc: [email-masked], [email-masked]
> X-Mailer: ELM [version 2.4 PL23]
> Content-Length: 1836
> 
> > You are forgetting the most important constraint on the timers.  It is
> > absolutely critical that the timers are sufficiently conservative where the
> > probability of of spurious retransmissions is infinitesimal.  Otherwise there
> 
> Probably I was not completely clear: I did not mean to modify the
> TSecr sent for in-sequence segments, but only the value for
> out-of-sequence segments which cause dup acks to be sent immediately.
> The RFC specifies that these values should not be used to update
> the RTT estimates (and personally I have no interest in this,
> although note that after a lost segment you might have a long period
> of time where you cannot update the RTT).

The problem is that you don't know whether the out-of-sequence segment
is due to a lost packet, or just packet reordering.  If you receive
packet #1 and delay the ack, and then get #3 & #2, you want the TSecr
in the dup-ack sent in response to #3 arriving out of order to be the TS
from #1, and then when you get #2, you want the TSecr to be from #2,
even though it acks #2-#3.  With your change, the ack in response to
#3 would have the TS from #3, and the ack in response to #2 would have
the TS from #3.  In this scenario, the computed RTT from both ACKs
will be underestimated.

> One can object that the last valid ack is lost, and one subsequent
> dup ack is not recognized as a dup thus causing the RTT to be
> updated.

The whole point of doing RTT measurement is to have an accurate
RTT value so you can avoid spurious retransmissions.  With that
in mind, if there is the possibility of error, it is better to
err on the side of a value that is too large than a value that
is too small.

> But as shown in Braden's message of April 93, the RTT
> derived from these dups can have very large errors, and this is
> the reason why he recommends not to use them to update the RTT.

In examples where the last valid ack is lost, the subsequent
dup ack will not be wildly inaccurate, just slightly inflated.
The cases of very large errors have to do with packets arriving
after the connection has been idle for some period of time.
 
			-David Borman, [email-masked]

From: Luigi Rizzo <[email-masked]>
Subject: Re: Thoughts about RFC1323 timestamps
To: [email-masked] (Matt Mathis)
Date: Sun, 4 Feb 1996 23:56:51 +0100 (MET)
Cc: [email-masked], [email-masked]
Content-Length: 1836

> You are forgetting the most important constraint on the timers.  It is
> absolutely critical that the timers are sufficiently conservative where the
> probability of of spurious retransmissions is infinitesimal.  Otherwise there

Probably I was not completely clear: I did not mean to modify the
TSecr sent for in-sequence segments, but only the value for
out-of-sequence segments which cause dup acks to be sent immediately.
The RFC specifies that these values should not be used to update
the RTT estimates (and personally I have no interest in this,
although note that after a lost segment you might have a long period
of time where you cannot update the RTT).

One can object that the last valid ack is lost, and one subsequent
dup ack is not recognized as a dup thus causing the RTT to be
updated. But as shown in Braden's message of April 93, the RTT
derived from these dups can have very large errors, and this is
the reason why he recommends not to use them to update the RTT.

Current code is more conservative than what I propose, but it is also
less representative of the actual RTT. Moreover, one must
weight the difference with the effects of smoothed means, the frequency
of such events (hopefully low) and, especially, the unavoidable
roundings in the computation which give a minimum retransmit time
which is usually quite large. I cannot imagine that my proposal
could increase spurios retransmissions significantly.

	Luigi
====================================================================
Luigi Rizzo                     Dip. di Ingegneria dell'Informazione
email: [email-masked]       Universita' di Pisa
tel: +39-50-568533              via Diotisalvi 2, 56126 PISA (Italy)
fax: +39-50-568522              http://www.iet.unipi.it/~luigi/
====================================================================

To: Luigi Rizzo <[email-masked]>
Cc: [email-masked], [email-masked]
Subject: Re: Thoughts about RFC1323 timestamps 
Date: Sun, 04 Feb 1996 11:26:29 -0500
From: "Matt Mathis" <[email-masked]>

You are forgetting the most important constraint on the timers.  It is
absolutely critical that the timers are sufficiently conservative where the
probability of of spurious retransmissions is infinitesimal.  Otherwise there
is a danger of massive wasted BW, due to timers triggering needless
retransmissions.  This was part of the congestive collapse that clobbered the
entire Internet in 1987-1988 and lead Van Jacobson to explore congestion
issues in his landmark paper.

The problem  is that the receivers delayed ACK algorithm MUST never trigger the
senders retransmit timer.  Thus when the receiver is doing delayed ACK, the
receiver must use the timestamp from the OLDEST ``omitted'' ACK, such that the
senders RTT estimate includes the receiver's delayed ACK timer.
(BTW, this wording suggests a simpler algorithm than specified by the RFC.)

But note that even this is not good enough.  Here is a pathological situation
that we have been mulling over.  Consider the following topology where "-"
is an ethernet and "=" is T3.   The letters refer to ``hubs'' which include
routers, fast metropolitan connectivity and hosts.  The hub detail is not
shown:

H1----H2====H3==========WC=============EC============EU
   1ms   1ms    40mS           30ms        30ms		(one way delay)

(this is 3 sites in Hawaii, and a path across the US to Europe)

Assume that there is a TCP connection ``A'' carrying traffic from a host at H1
to a host at H3, which is not bottlenecked by the network.  e.g. it is limited
by a disk drive, etc.  Also that it is using the existing timer algorithm
but with 1mS granularity.  I believe that this means that it's retransmit
timer (mean+4 dev) would be at most about 50 mS.

Also assume that the queues at all hubs are correctly provisioned
for the 200 mS worst case roundtrip time.

Now suppose a new, network limited connection ``B'' starts between H2 and EU.
At the end of its slowstart it will create a 200mS queue on the link from H2
to H3.  This queue will cause the RTT for connection ``A'' to change from 4 mS
to 204mS.  Since connection A's retransmit timer is 50 mS, it will do at least
two spurious retransmissions.  Not a serious in this case, but suppose you
replace connection ``A'' with 500 telnets.....

This is not easy to fix because the essential problem is that the small
connections have no way to observe the huge nominally unused queue at H2 until
some other connection fills it.  I believe that the only ``fix'' is to
mandate a floor on the retransmit timer - say 1 second.  (1 second is a small
integer times the correct queue time for the vast majority of todays Internet.
This would allow H2 to have internal hops.)

Note that this eliminates the usefulness using accurate RTTM to implement the
retransmit timer.

Note that the old code, with 500mS ticks and RTT rounding effectively had
a floor of 2 seconds.

--MM--

From: Luigi Rizzo <[email-masked]>
Subject: Thoughts about RFC1323 timestamps
To: [email-masked]
Date: Sun, 4 Feb 1996 10:14:25 +0100 (MET)
Content-Length: 2408

I was recently thinking about TCP timestamps.  RFC1323, and,
especially, subsequents updates by R.Braden [1] specify that:  

#1   (2)  If: SEG.TSval >= TSrecent and SEG.SEQ <= Last.ACK.sent
         then SEG.TSval is copied to TS.Recent; otherwise, it is
ignored. 

(TS.Recent is the value sent as the timestamp echo reply in the
next ack. It is also used to discard old segments. In BSD4.4 it is
the ts_recent field in the tcpcb).

Also:

#2     "A TSecr value received in a segment is used to update the
       averaged RTT measurement only if the segment acknowledges  
       some new data, i.e., only if it advances the left edge of the
       send window." 

(this rule is necessary to avoid possibly large errors on the
estimate of the RTT when segments are lost, see [1]).

As a consequence, the timestamp echo reply value (TSecr) in acks to
out-of-sequence segments is completely ignored.

I'd like to keep rule #1 and #2, but use the timestamp echo reply
field to carry _always_ the timestamp of the last received segment,
if this is more recent than ts_recent.

For in-sequence segments, this is exactly what already happens;
for out-of-sequence segments, rule #2 specifies that the field
should be ignored so it should not matter what is really sent. Note
that the value to put in TSecr is readily available from the incoming
segment, and does not need to be stored in the tcp control block
as it is going out in an immediate ACK.

The change I suggest has two advantages: the sender has a more
accurate value for the RTT, which can possibly be used to update
the estimates (thus overriding rule #2; but I have not investigated
on this).  Also, the sender can use this info to determine which
segments have been received at the remote side.

Anything wrong in my reasoning ? I have been running a FreeBSD
kernel with this modification for a few days and have not seen
difficulties in TCP connections with other systems.

        Luigi

[1] R.Braden, email message to the tcplw mailing list, april 1993

====================================================================
Luigi Rizzo                     Dip. di Ingegneria dell'Informazione
email: [email-masked]       Universita' di Pisa
tel: +39-50-568533              via Diotisalvi 2, 56126 PISA (Italy)
fax: +39-50-568522              http://www.iet.unipi.it/~luigi/
====================================================================