Subject: Re: ECM last call for draft-balakrishnan-cm-02.txt to Proposed Standard

From: Hari Balakrishnan <[email-masked]>
Date: Wed, 12 Jul 2000 20:27:14 -0400

Joe,

Thanks for these detailed comments---appreciate it!

On Tue, 11 Jul 2000 11:48:53 PDT, you wrote:

> Some brief comments before last call closes:
>
> Sec 4.2
>    ALF != dynamic content
>    although ALF can be dynamic and can affect content,
>    there are other application dynamic content responses
>    that aren't ALF-based

Yes, that's true; we certainly didn't mean to imply that.  I've modified the 
text to make this clear.

>    Is it absolutely necessary that each MTU require a separate
>    CM call or callback? This could severely affect performance.
>
>    cm_request should be able to pass a requested number of bytes,
>    either an upper bound or an estimate, e.g., for cases where
>    the application is NOT sending an MTU. E.g - for realtime apps,
>    it would prevent waiting for permission to send a full MTU
>    when only a few bytes are being sent. (preferably, this could be
>    cm_request(K,size) where K is the number of packets to be sent
>    and size is the max size of each packets, again to allow amortization.

This has been a topic of several debates.  In fact, the original design had K 
as a parameter, but various people suggested a simpler interface.  In fact, the 
original proposal was of the form:
	cm_request(max_want, min_usable)

There are a few tradeoffs here that need to be weighed.  Perhaps these will 
convince you about the choice we made, or at least see where we're coming from!

     1) If the concern is purely overhead, then the addition of K to the core 
CM API may not be the best way to go.  (This document describes the API that 
the CM MUST implement to do the job of congestion control, and at the same time 
enabling application adaptation.)  If a particular OS has high user/kernel 
crossing cost, it may provide the facility that enqueues multiple cm_request() 
calls in sequence and issues them to the CM (within the kernel) one at a time.

	The primary reason that the older design had a byte count was not overhead but 
application-related.  The fear was that an application could not make a 
decision with cmapp_send() callback for a single MTU. For example, it may have 
needed information that it could send e.g., 4 packets during this RTT to make 
an application adaptation decision.  In the end, it was felt (based on comments 
received from people who've built such apps and our own experience) that this 
longer-time-scale adaptation was better handled through the query and 
rate-based callback API.

     2) Not having an explicit (potentially large) size to schedule makes the 
implementation of CM internals simpler.  A lot simpler, in fact.

     3) Notice that the cmapp_send() callback still occurs individually for 
each packet transmission, to avoid burst transmissions.  Because of this, the 
number of user/kernel crossings or overhead is not reduced by more than a 
factor of 2 (not K).  On the other hand, doing a callback with a passed 
parameter (of the number of packets to send) results in CM giving up any 
possibility of shaping the output traffic (i.e., the app may burst packets into 
the network).

>    the downcall (cm_data?) appears to be referred to but not defined in
>    the discusion of synchronous calls

This paragraph in the draft may be misleading.  The CM is not on the data path 
of such transmissions; there's no cm_data() or equivalent call.  Transmissions 
occur using udp_output(), for example.  I've added a note to this effect in the 
draft.

> As suggested at the BOF earlier, all reasonable parameters should
> include variances.
> This includes cmapp_update's rate value. Just as RTT includes a
> deviation, rate should be an
> upper bound or average with some variance as well.

All reports from the CM are instantaneous values.  (I've added a note 
clarifying this.)  Any calculation of averages or variances should be done by 
applications themselves.  The reason for this is that it is hard to know a 
priori what the averaging mechanism should be that makes sense for each 
application.  For example, rate-averaging can be done in several ways, with 
different applications preferring different ones.  It is therefore better, a la 
the end-to-end argument, to simply report raw instantaneous values, empowering 
applications (e.g., TCP) to treat these samples any way they choose.

> All variance information should have a way to control and read the
> averaging interval,
> (and possibly to get a token indicating the averaging algorithm). Some
> parameters of
> the algorithms (decay rate, averaging window) may need to be in the
> interface in the future.

Joe, this seems somewhat more complicated than desirable, and it is unclear 
that we'll get it all correct.  The interface we've chosen allows any 
application to do all of this quite trivially.  Do you agree?  (I do agree that 
specific apps might want to do all this, and they should if it makes sense for 
them.)

> 4.3 - application notification
>
>    the use of CM_PERSISTENT and CM_TRANSIENT requires the application to
> infer,
>    rather than report.
>
>    it would be safer to report explicit issues:
>
>         timeout_loss
>
>         sequence_loss
>
>         reported_loss
>
>    these should be a bit-vector, because there could be combinations of
> some kinds
>    of loss (e.g., reported sequence loss from the other end, etc.)

Terms such as reported, sequence and timeout seem to be TCP-specific. We have 
used PERSISTENT and TRANSIENT to merely represent the concept of persistent 
heavy congestion loss/loss of ack clock/timer driven event/etc. vs. transient 
data loss etc.  In addition, CM really requires applications to provide 
feedback on time periods of a RTT.

We do agree that it may make sense to report a bit-vector, and I will change 
the document to reflect that.

>    cm_notify should have a MUST to call cm_notify(stream,0) if the app has
> no immediate
>    data to send. that would make it consistent with the subsequent claim
> that the controller
>    be robust and fix apps that don't report it correctly (i.e., when the
> app has an error).
>    I.e., if it's just a should, why is the CM doing cleanup? should the
CM
> do cleanup at all?
>    (It doesn't matter which - but the two appear inconsistent)

Absolutely.  There are a couple of other reasons to do a "MUST," having to do 
with how long a cmapp_send() grant is valid for.  This has been fixed now.

However, the CM MUST still have support for cleanup to support applications 
that crash before cm_notify or are written incorrectly and do not do 
cm_notify(0).

> 4.5 get/set macroflow
>    these routines lack an interface to set sharing policy. the entire
> mechanism underspecifies
>    this property, and currently assumes that streams are shared 1/N. that
> is only one choice

The objective of this interface was only to set up sharing of groups not 
sharing policy. The scheduler must provide the interface to set sharing policy 
within a macroflow. Because we want to support many different schedulers (each 
of which may need different information to set policy), we chose not to specify 
an API to the scheduler. In a later guideline document, we plan to describe a 
few simple schedulers (at least a hierarchical scheduler and a weigted round 
robin) and the API they export to provide relative prioritization.

>    in the second paragraph, destination = destination IP address

Yes, fixed now.

> Security considerations
>
>    there are quite a few issues to consider, many of which were discussed
> in Touch97.
>    in particular, the CM opens attacks to siblings of a vulnerable stream
> on a single machine,
>    or (if macroflows span sets of hosts) across machines.

Agreed; added to the section.

> I would very much like to see some of these issues addressed
> before this protocol goes to proposed standard.
>
> Joe

Hari & Srini

---

From: Joe Touch <[email-masked]>
Date: Thu, 13 Jul 2000 10:14:36 -0700

> calls in sequence and issues them to the CM (within the kernel) one at a time.

That still requires procedure calls per write/read, even if inside the
OS. If the application has permission to send at line rate or can pace
them out automatically (via control of a DMA), the CM should get out of
the way.

> longer-time-scale adaptation was better handled through the query and

Rate-based callbacks don't work well with DMA engines. The DMA setup can
be prohibitive if done on a per packet basis, esp. if the packets are
small and the data rate is high.

> implementation of CM internals simpler.  A lot simpler, in fact.

Agreed. But the CM should (MUST?:-) not prohibit, by its design
requirements, high-performance networking.
 
> possibility of shaping the output traffic (i.e., the app may burst packets into

The app can do this anyway. The CM trusts the application to send only
one packet per cmapp_send() callback, it can equivalently trust it to
pace, if
the application asserts that it both can and will. 

Perhaps this is a MAY:
	the CM MUST support cm_request(K,size); sizes of K=1 MUST be supported,
sizes of K>1 MAY be supported.

	cmapp_send(K, size) MUST be supported;
		the application MUST NOT send more than K packets of size
		if K>1, the application MUST have a pre-negotiated rate with the CM, 	
			and the application MUST pace the K packets via that rate

(this allows simple applications to set K=1 and be done with it, but
doesn't prohibit high-performance variants).

Having the CM spec assert a callback-per-MTU is unduly imposing an
implementation detail which has substantial performance implications.

> All reports from the CM are instantaneous values.

RTT already has an average and STDDEV. This indicates that the CM
is already doing averaging. The reported rate is no different -
and it's important because the application may want to know the
rate of the aggregate.

> application to do all of this quite trivially.  Do you agree?  

Applications would need to poll the CM interface, increasing load. The
same
way RTT is averaged and reported back, rate should be as well.

It's not complicated - it's orthogonal. The CM should just report the
information it already has.
I agree that if the application doesn't like the averaging algorithm or
interval it may want to change them;
the CM MAY implement an interface to provide that facility :-)

> the document to reflect that.

The problem is that there is the possibility of different flows (TCP,
UDP, etc.) being aggregated. The meaning of these terms must be
unambiguous and absolute, not relative to the protocol.

The bit-vector should indicate:

	timeout (without loss)
	timeout (inferred as loss)
	loss inferred from the receive stream (e.g., sequence numbers)
	loss explicitly reported by third parties (ECN)
	loss explicitly reported by the endsystem (SACK?)

Sequence numbers and reported errors (NACKS) are not TCP specific.

> that crash before cm_notify or are written incorrectly and do not do

I was wondering whether this was the CM's responsibility, or the wording
of the APP requires it (or the sandbox in which it runs, e.g., the OS)
to notice the failure and cleaup after itself. If it is a MUST, then the
app MUST find a way to do it and the CM need not deal with cleanup; if
it is a SHOULD, then you MUST implement a cleanup in the CM. The
difference is which sides have MUSTs and SHOULDs.
 
> robin) and the API they export to provide relative prioritization.

AOK - there should be a description of that, i.e., 'what's NOT in this
document,
but still needs to be deterimined'.

Joe

---

From: Joe Touch <[email-masked]>
Date: Thu, 13 Jul 2000 10:19:33 -0700

On a separate note, I've been suggesting that RFCs include a section,
akin to security considerations, called something like "Impact on
Internet Standards". Sort of like the EPA's 'Environmental Impact", this
would list any way in which:

	- the RFC violates any existing protocol (proposed or standard, not
experimental or informational)

	- the RFC relies in a new way or very strongly on an existing protocol

	- the RFC makes additional requirements on an existing protocol

(these are not precise; just placeholders for the idea 'how do you
affect standards or would their change affect you').

In this document, e.g., there is an assumption in the definition of
flows that a pair of IP addresses share flow properties on all
connections between them. I.e., that IP addresses NOT be shared on
different hosts with different path properties. (that's a looser version
of an existing requirement, but still might be useful to flag).

Joe

---

From: Hari Balakrishnan <[email-masked]>
Date: Fri, 14 Jul 2000 09:02:33 -0400

Joe,

Many of the other points you made make sense to me.  But I have a problem with 
this one:

> and it's important because the application may want to know the

Mea culpa.  srtt and rttdev are obviously not instantaneous values.  The rate 
reported is instantaneous, though, in the sense that it is an instantaneous 
rate calculated, for example, by taking the ratio of cwnd and srtt, and 
dividing by the fraction of that ratio allocated to the stream.

> the CM MAY implement an interface to provide that facility :-)

The issue is that the CM is in fact reporting all the information it has.  It 
needs the srtt and rttdev because of the way it mimics TCP-style window-based 
congestion avoidance and control.  It doesn't implement any rate averaging and 
therefore can't report it in any reasonable way.  Like I said before, an 
application can average these instantaneous things in any manner it chooses.

Hari

---

From: Hari Balakrishnan <[email-masked]>
Date: Fri, 14 Jul 2000 09:11:54 -0400

Joe,

> Sequence numbers and reported errors (NACKS) are not TCP specific.

No, they aren't TCP-specific.  But many UDP-based streams don't have a notion 
of a timeout, which is usually related to reliability.  I believe that there 
are three fundamental types of congestion events that a feedback- and 
window-based protocol can pick up.

	- The loss of the feedback self-clock, e.g., when many packets are lost in 
quick succession, or when many feedback packets are lost, or if a 
retransmission is lost (e.g., in TCP).  This signifies "persistent" congestion, 
which essentially means that the feedback clock is lost, so go back into slow 
start.  This is generally not dependent on whether SACK is used or not.

	- The loss of some packets, but not the feedback clock.  This signifies 
"transient" congestion, one that requires some decrease in window (rate) but 
doesn't necessitate slow start.

	- ECN.

That was the intention of the three orthogonal modes of notification.  The 
bit-vector is a good idea, especially if ECN and one of the other two modes 
occur at the same time.

Do you agree?

Hari

---

From: Hari Balakrishnan <[email-masked]>
Date: Fri, 14 Jul 2000 09:18:27 -0400

Joe,

I think it should be the CM's responsibility, as it is the best defensive behavior and is pretty straightforward to implement.  Furthermore, note that there may not be an OS sandbox conveniently available, e.g., if a stream runs over vanilla UDP.  Unless you're willing to make modifications to vanilla UDP to make it CM-aware and also maintain more stream state, which I don't think is a good idea.

Hari

---

From: Joe Touch <[email-masked]>
Date: Fri, 14 Jul 2000 12:38:13 -0700

> dividing by the fraction of that ratio allocated to the stream.

Putting a windowed value (RTT) into a calculation makes the result of
that calculation implicitly windowed. The rate is thus "over the window
of the RTT". It is probably sufficient to point that out, in that case.
(rather than requiring some of the extra interface I mentioned earlier).

Joe

---

From: Joe Touch <[email-masked]>
Date: Fri, 14 Jul 2000 12:44:57 -0700

Hari Balakrishnan wrote:
>         - The loss of the feedback self-clock,

Then say this.

> e.g., when many packets are lost in

Persistent means different things; it could mean 'large losses over a
RTT', 'many losses in a row', etc. 

Losing a retransmission is not 'persistent' in any case, unless it
occurs many times.

> bit-vector is a good idea, especially if ECN and one of the other two modes

Basically, except that I would like to see

	a) the names be well-defined, e.g.,
		persistent = more than X% packets lost over 1 RTT,
		or more than Y% lost over 2 RTTs..

		transient = all other loss patterns

	b) these are orthogonal to whether the loss is generated by a timeout,
	noticing gaps in a sequence, or explicit feedback, so it would be 
	useful to say: TYPE_OF_LOSS as one of these three

	I agree that some protocols will never generate some patterns,
	but the point is to get away from TCP-specifics and express
	the underlying reasons, IMO...:-)

Joe

---

From: Joe Touch <[email-masked]>
Date: Fri, 14 Jul 2000 12:46:06 -0700

Hari Balakrishnan wrote:
> I think it should be the CM's responsibility, as it is the best 
> defensive behavior and is pretty straightforward to implement.  
> Furthermore, note that there may not be an OS sandbox conveniently 
> available, e.g., if a stream runs over vanilla UDP.  Unless you're 
> willing to make modifications to vanilla UDP to make it CM-aware 
> and also maintain more stream state, which I don't think is a good idea.

Agreed - the above wasn't proposing a different solution, it was
requesting
a clarification of the wording of MUST/SHOULD/MAY to indicate what you
just said :-)

Joe