Subject: Re: Next draft of ECM WG congestion manager document (fwd)

From: Hari Balakrishnan <[email-masked]>
Date: Tue, 17 Oct 2000 19:25:06 -0400

Joe,

> I've heard these arguments before. In the absence of evidence that CM
> is not a significant penalty (i.e., emperical evidence of the
> performance
> of running code), it is wise to err on the side of caution here.

There are some running code measurements in the OSDI 2000 paper. In addition 
there is now a code release. Hopefully, these should reduce the concerns of 
overhead from cm_request().

> The solution is to not provide the cm_request(id) format;
> as you point out, any provision for two interfaces is asking for
> trouble.
> The better solution is the more general interface. Applications that
> can make due with the simpler version can call it as I indicated, or
> use a macro in the code of the API.

Yep, your interface is more general. However, purely being more general does 
not necessarily make it more appropriate. The implication of this design choice 
on implementation and on future design choices must be considered. For example, 
it will always be easier to move application code from the simpler interface to 
the more general interface through:

#define cm_request(id) cm_request(id, 1, MTU) 

> > > > I am not sure at all that complicating the API
> > > > to accommodate this, in the absence of significant experience that dictates
> > > > that it's necessary, is a good idea.
> > >
> > > That experience is in abundance; per-packet overhead should be avoided,
> > > especially where not otherwise necessary.
> > 
> > ... and where you do not give up any other benefits as a result. One important
> >  aspect of the CM, is that it is supposed to effectively shape/control the
> > transmission of data. By allowing application to send bursts of data it gives
> > up much of this control. In addition, scheduling such variable sized bursts
> > may also prove to be a non-trivial problem. This seems to have much greater
> > future implications than the per-packet processing overheads.
> 
> There are two issues here:
> 
> 	1. size
> 		assuming MTU is imprecise anyway

This was chosen as the balance between making it hard on the application to 
know a priori the exact amount of information being sent and CM needing to  
control the transmission precisely. This was based on a similar choice by 
existing protocols like TCP, and by the preferred mode for ALF (as described in 
Clark's 1990 paper).  However, do note that cm_notify & cm_updates are on the 
exact number of bytes sent. Therefore, the CM is able to keep a precise account 
of what's going on, within a short time delay (the time between callback and 
transmission).

> 
> 	2. npkts
> 		making this larger does increase granularity of the API
> 		whether an implementation of the API supports this
> 		should be up to the API
> 
> 		it is overrestrictive to assume that CM must be tickled
> 		for every packet going out the door, regardless of the size
> 
> 		there are numerous cases where such bursts are desirable,
> 		and might be impeded by the current interface, e.g.,	
> 		bursts in gigabit ethernet, and the small-scale burstiness of
> 		TCP (sending multiple packets per ACK).
> 

I assume that even though the application requests npkts, the callback can 
return anywhere between 1 and npkts as sendable now (or does a callback 
indicate that all npkts are sendable?).

If so, then this would rather complicate both the CM and the application. E.g. 
how does the CM decide when it should do the callback---especially when there 
are multiple applications all with differently-sized requests? E.g., if the CM 
has 2 applications, 1 asking for 5 pkts and the other asking for 1. When a 2 
pkts become available in the congestion window, should it wait for 5 to become 
available or just satisfy the smaller request. Also, suppose an adaptive 
application wanted to send 10 pkts and got a callback for 2 pkts - what should 
its adaptation decision be? Does it need revoke its request 8 more pkts (i.e., 
is there a "revoke" call)?

Historical note:

In fact, we had npkts in the API for about 3-4 months inthe early stages of 
design, until we were convinced otherwise (my recollection is that we were 
going back and forth on it, and that Steve McCanne and Mark Handley 
persuasively convinced us to make the simpler decision).  In addition, with the 
npkts added we also found it necessary to add min_bytes (actually our original 
interface was cm_request(id, nbytes, min_bytes)).  This was in order to help 
the scheduler decide when to do callbacks.  A callback had to indicate a value 
between min_bytes to nbytes that could be transmitted.

We were convinced that this provided little gain to applications and would 
complicate the internals significantly.  We chose the path of lower 
implementation complexity.  This approach is in fact not new by any means; UNIX 
did this routinely in their system.  See, for example,
Richard P. Gabriel, Worse is better. From LISP: good news, bad news, how to win 
BIG, AI Expert 6, 6 (June, 1991) pages 33-35
for an interesting description of this in the context of UNIX and LISP.

Hari & Srini

---

From: "David G. Andersen" <[email-masked]>
Date: Tue, 17 Oct 2000 19:41:05 -0400 (EDT)

> overhead from cm_request().

  To expand upon these slightly:

Using the congestion manager from userland imposes a measurable overhead
on its clients, primarily because it's now necessary to handle ACKs in
userland.  This results in an additional read() system call and memory
copy (acks are typically too small to be handled via a zero-copy scheme
like memory mapped buffers).

Unfortunately, this is something that can't be avoided if you want
to handle your protocol entirely in userland, which is an
extremely desirable property for protocol designers - witness
the proliferation of UDP based protocols.

Once you've paid this penalty, the extra overhead of a request
system call is slight.  If you want a maximally responsive
protocol, you'll be calling cm_update() every time you receive
an ACK from your clients anyway, so as to not withhold
additional information from the CM.

Considered in this framework, the typical process for
packet transmission looks something like:

   request
   transmit
   notify
   update

Our implementation optimizes the 'notify' stage by having it called
directly by ip_output, so from userland, it looks like:

  request
  transmit
  update

The request operation is actually one of the cheapest operations
performed by our implementation of the CM.  It's not zero-cost;
we were able to get a measurable benefit by making it
completely implicit in the case of the buffered UDP sockets,
but doing so also eliminated several other sources of overhead --
additional sockets to select on and test, the need to
perform any checking before enqueuing data into the
kernel buffer, and by giving the kernel the ability
to immediately transmit the data from its buffer at
interrupt time, instead of waiting for the
process to be scheduled to call send().
The marginal benefits from JUST eliminating the
call to request were very small.

If you'd like more details on the numbers, I've
got gobs of 'em that we looked at when writing
the OSDI paper, and I'm more than happy to
share.

  -Dave Andersen

--
work: [email-masked]                          me:  [email-masked]
      MIT Laboratory for Computer Science           http://www.angio.net/

---

From: Joe Touch <[email-masked]>
Date: Wed, 18 Oct 2000 06:42:08 -0700

Hari Balakrishnan wrote:
> Clark's 1990 paper).

TCP is already being extended to handle byte counting, to be more
precise.
The difference between MTUs and bytes can range from trivial to 
a factor of around 10 (e.g., ACKs), on average, given other overheads.

Since TCP is already being extended to account for this concern, it
makes sense to consider it in the CM now.

> However, do note that cm_notify & cm_updates are on the

It's precise only if, given the grant to send X bytes, X bytes are sent.
If TCP's window allows a full MTU, it must request that, because
that much data MIGHT appear by the time the callback occurs.

However, if new data does not appear, that TCP connection will
have waited too long to receive its share of the connection. The
CM should be told this, or the utilization of the channel will
suffer significantly.

> are multiple applications all with differently-sized requests?

Good question. Some applications have no utility in sending one packet,
e.g., transaction systems. Each request needs a min (don't call me back
until there are this many bytes available to send) and a max (tell me,
up to this number, how many I can send on this callback).

If a particular implementation of the CM cannot support it, then so be
it.
But it should not be excluded from the specification.

> implementation complexity.  This approach is in fact not new by any means; UNIX

If this were a demonstration prototype, by all means. 
But this is a standarization process, and a reasonable
set of expected uses (and performance capabilities)
must be supported at the outset.

Joe

---

From: Joe Touch <[email-masked]>
Date: Wed, 18 Oct 2000 06:48:18 -0700

"David G. Andersen" wrote:
> like memory mapped buffers)
...
> the proliferation of UDP based protocols.

The CM is for operational systems,
not just as a testbed for protocol designers. 

While measurement of userland protocol performance may suffice for
an OSDI paper, it does not address the issue of performance
degradation of kernel protocols, notably TCP, which concern me.

> If you want a maximally responsive

Calling the CM per ACK isn't the issue - it's calling the
CM per send. TCP sends multiple packets per ACK.

Joe

---

From: Hari Balakrishnan <[email-masked]>
Date: Wed, 18 Oct 2000 10:40:28 -0400

Joe,

> not just as a testbed for protocol designers. 

It *is* for operational systems, including those running new protocols.  E.g., 
SCTP, storage-area network protocols, streaming media,...

> degradation of kernel protocols, notably TCP, which concern me.

Our measurements show that in fact an in-kernel protocol like TCP does not 
suffer any penalties observable ourside of experimental error.  Function calls 
not even inlined) are blazingly fast on even the standard PCs these days.

> CM per send. TCP sends multiple packets per ACK.

Yes, so it calls cm_request() for each MSS and gets a permission when deemed 
appropriate.  No big deal.

If there's anything to be concerned about, it's userland apps.  As it turns 
out, our measurements show that it isn't too awful.

Hari

---

From: Hari Balakrishnan <[email-masked]>
Date: Wed, 18 Oct 2000 10:35:35 -0400

Joe,

> makes sense to consider it in the CM now.

By saying this, you're giving the impression that the CM precludes byte 
counting or somehow makes it hard.  Neither of this is true.  In fact, our 
implementation does do a form of byte counting, where the cm_update() call from 
the TCP sender upon receiving an ACK tells the CM exactly how many bytes 
cleared the pipe (esp. with TCP/SACK).

Whether or not byte counting is done in adjusting the window size is orthogonal 
to the interface provided by cm_request(), as mentioned immediately below.

> CM should be told this, or the utilization of the channel will

It is a simple matter now for the TCP sender to now make a number of 
cm_request() calls, and receive function callbacks.  I don't agree with you 
that the performance penalty for a good in-kernel implementation in doing this 
is significant.

Furthermore, I claim that it is almost always a good idea to limit bursts to a 
reasonably small number.

You're probably going to say that that's not the case for a 1Gbps/2.5Gpbs (name 
your number) fast TCP.  Perhaps so, but I don't think the additional inlineable 
function call for the request callback will be _the_ limiting factor here.

> must be supported at the outset.

I don't know where the comment about "demonstration prototype" came from!  Are 
you arguing that UNIX is a "demonstration prototype"?!  I was in fact using 
UNIX, and the "Worse is better" paper on system architecture philosophy to 
argue that when confronted with design choices that are seemingly hard to 
resolve, it is often best to take the path of simpler implementation.  History 
seems to suggest that this is almost always the correct choice.

I don't believe that any expected use (or performance target) is precluded at 
all.  In fact, that's one of the big advantages of a simple interface and 
implementation structure.

Hari

---

From: "David G. Andersen" <[email-masked]>
Date: Wed, 18 Oct 2000 14:15:50 -0400 (EDT)

> degradation of kernel protocols, notably TCP, which concern me.
 
   Oh!  Sorry about that - I assumed that we were talking about the cases
where the performance really goes downhill, and those are all in userland.
Our current implementation is really quite unoptimized:  We do a lot of
pointer chasing to find schedulers and congestion controllers, things that
in a production system you could aggressively optimize away or specialize
for your common cases.  With that in mind, both microbenchmarks and
throughput degredation benchmarks indicate that we're currently causing a
1-2% performance hit.

Much of cm_request can be expressed as a macro;  in particular, a clever
implementation could actually treat a call to cm_request as a two-part
request:

  a)  I'd like to send a packet
  b)  While you're at it, check how many more I can send if I keep
      begging

resulting in a cm_request call that looks something like:

(Sorry if the terminology isn't quite up to that in the draft;
my brain is stuck in the code):

#define cm_request(macroflow *mflow)
  lock_mflow(mflow);
  if (mflow->extra_send == 0) {
    real_cm_request(mflow);
  } else {
    mflow->extra_send--;
    mflow->unregistered_pkts++;
  }

real_cm_request would do the cleanup job of coping with
the extra_send and unregistered packets.

This can optimize the heck out of the same case you're worried about, and
it has the same set of attendant complications in scheduling multiple
packets.  If a vendor wants to tackle these complications, they can do so
in a way that's API transparent even without taking a number-of-bytes
argument.

There's lots of room for a really clever person to get in and
reduce the API overhead.  However, consider what happens
in standard TCP during normal transmission:  Receipt of an
ACK gives permission to send 1 or 2 more packets worth.
Not 10.  Therefore, if you're trying to transmit as rapidly as
possible, cm_request(foo, 10, bar) is likely to fail and tell you
you've only got window space for two packets _anyway_.

This means that there's one additional function call --
that can perhaps be optimized if you can cope with the
agony of basing your scheduler around a multiple request
paradigm anyway -- for every two packets you transmit.

Also note that the cm_request gives you permission to transmit
up to 1 PMTU.  If you're sending tiny packets and worried
about the overhead, then:

  a)  You shouldn't be sending tiny packets, because they DO
      have higher overhead in all regards
and
  b)  You can send PMTU / packetsize  packets per request
      call already.

> CM per send. TCP sends multiple packets per ACK.

When sending bulk data, TCP sends ~2 packets per ACK.

   -Dave Andersen

---

From: Joe Touch <[email-masked]>
Date: Mon, 30 Oct 2000 15:15:03 -0800

> the extra_send and unregistered packets.

The lock is probably the most worrisome of the components,
computationally as well as in latency of the function call.

> you've only got window space for two packets _anyway_.

But if there are 4 ACKs waiting to be processed, 
the CM API must be called 8 times, rather than 4 
(or even better, 1).
 
>       have higher overhead in all regards

I might have to, e.g., to use gigabit ethernet in non-jumbogram mode.

>   b)  You can send PMTU / packetsize  packets per request

This conflicts with a). If tiny != sum of the data, then
the CM should differentiate between sending 10 packets of 50 bytes
and one of 500.

> When sending bulk data, TCP sends ~2 packets per ACK.

That too depends on the ACK. If ACKs are lost (or
compressed, as with some proposals), the receipt of
a single ACK can generate up to a windows' worth of 
new outgoing packets.

Joe

---

From: "David G. Andersen" <[email-masked]>
Date: Mon, 30 Oct 2000 21:15:09 -0500 (EST)

...
> computationally as well as in latency of the function call.

In a uniprocessor system, these operations are NOPs. 
In a multiprocessor system, these are macros that, in the uncontested
case, throw in a memory write barrier and an atomic test/set of the
lock.  I agree completely with the point you're about to make - that
in the contested case, this will slow down access to the
control structures.  Inserting a small dose of reality, however,
the time spent with these structures locked is puny compared to
the time taken to actually transmit a packet -- since you're
calling these once per packet request, the extra time wasted
in the case of a contested multiprocessor system is minimal.

... and in the common case of a uniprocessor system, or a
multiprocessor system without a multithreaded network stack,
or an uncontested multithreaded / multiprocessor machine,
the lock is a small cost, especially considering that
in the same circumstances, the act of packet transmission
requires grabbing at least as many of the same kinds of locks.

> the CM API must be called 8 times, rather than 4 

  I completely agree.  That's why I suggested that the actual
call to the CM API can be optimized up one side and down the other,
_provided_ the task of writing the "multiple request" API
can be done easily.  If it can, you can make the single
request case very fast, as I noted above.  If you can't, well,
it doesn't matter anyway.

> I might have to, e.g., to use gigabit ethernet in non-jumbogram mode.

  Um.

  I think I'm missing something in intuiting the circumstances
under which you'd want to artificially limit your MTU
for the same (sender, receiver) pair (e.g. the same macroflow)
for one application, and NOT do so with another.  Either
your jumbogram mode is better (mtu==big, and use it)
or it's not (mtu==1500).

  Which is a longwinded way of saying:  If you don't want to
use your ethernet in jumbogram mode, then your MTU is 1500.

> the CM should differentiate between sending 10 packets of 50 bytes

  I disagree.  My point in (a) was about CPU and interrupt utilization,
but this actually brings up an interesting issue of how much attention the
CM should pay to link layer costs:  With a network like ethernet,
packets really are expensive per-packet because of the back-off,
but with a full-duplex point to point link, you only pay the cost of the
extra headers.

  I think that this goes way off the deep end of what the CM should do,
however -- if you take this to the extreme, you have to then consider
every possible network technology over which you pass.  Best to
simply count bytes passed to IP, and let the other layers do
their job as they see fit.

> a single ACK can generate up to a windows' worth of 

  ... which can still be well optimized as above.

  -Dave