net-AIO and real-time TCP (blue sky research)

net-AIO and real-time TCP (blue sky research)

[Werner Almesberger]

Hi Suparna,

I'm copying this to netdev, because people there may get a good
chuckle out of this outlandish idea as well :-)

At OLS we were chatting about using AIO also for networking.
While this concept didn't seem to rank particularly high on the
lunacy scale, it didn't appear overly useful either. About the
only possibly interesting new functionality, besides the
possibility to connect this with some eccentric TCP offloading
and zero-copy scheme, would be - when applied to TCP - to make
unACKed data in the out-of-order buffer available to user
space.

Now, it occurred to me that this may lead to something a lot
more exciting: a step towards making TCP real-time capable.
I'm using the term "real-time" loosely here, as in "there's a
deadline, but we're flexible".

I haven't followed what's going on at IETF in that area for a
while, and I'm sure plenty of other people must have thought
of similar schemes before, but since this seems nicer and
maybe even simpler than some, let me describe it anyway.

First of all, one of the main complaints of the real-time
networking people is that TCP stubbornly insists on
retransmitting every single segment until it is absolutely
certain that the segment has been received, even if the
real-time application has long since moved on.

Now, with net-AIO, the application could already get all the
data that has arrived after a lost segment. That's a good
start, but TCP will still try to retransmit. So the next step
would be to have a means to indicate that we've lost interest
in the outcome of a pending AIO operation, and - as a side
effect - communicate this also to TCP, so that TCP can stop
trying, and do something more useful instead.

Let's call this operation aio_forget(). For disk IO, this
may work just like aio_cancel().

Now, aio_forget() would be a great tool for making TCP
blissfully ignorant of any losses, actually making it very
TCP-unfriendly. So the next step would be to record the fact
that we've just forgotten some segments, but still need to
make the peer aware of the fact that there (may) have been
losses, and to slow down accordingly. Obviously, if we have
reason to believe that the peer already knows of a loss in
the general vicinity, no action is needed.

Reliably communicating a loss isn't trivial, but there should
be good background material in the context of ECN. Of course,
if ECN is available, we may just use that. Otherwise, we may
have to force a retransmission, to be sure that the peer has
noticed. (And, if the forgotten segment(s) should arrive while
TCP is trying to indicate a loss, it should stop doing so.)

Now, assuming we have a solution for indicating losses that is
satisfying both in terms of congestion control and in terms of
efficiency, there are still a few things that would be nice to
have, that this approach doesn't solve:

 - message boundaries and segment-message alignment. Not being
   able to use messages just because a few of their bytes
   ended up in a lost (and then aio_forgotten) segment would
   be just too bad. In some cases, it may be possible to just
   set the MSS to a suitable value. Also, recovering message
   boundaries after a loss may be tricky.

 - there's no direct provision for allowing adaptive coding.
   Of course, this is a fairly orthogonal problem.

 - as time passes, the sender may want to remove or substitute
   data it had already enqueued, e.g because there is less
   bandwidth than originally anticipated. So there may be a
   place for aio_forget() at the sender side too.

Now, why could this scheme be "nicer" than just inventing some
new protocol that is designed to do all these things ? The
main thing that "looks good" is that this mechanism could use
all of TCP, and may not even need major maintenance if some
minor aspect of TCP congestion control gets changed.

Anyway, this may be peculiar enough for someone to spin the
idea a little further. In the worst case, I might just have
provided additional evidence that, if you just search long
enough, there's a perfectly plausible problem for every
solution :-)

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: net-AIO and real-time TCP (blue sky research)

[Suparna Bhattacharya]

Hello Werner,

I was hoping all this while that someone with deeper knowledge
in this area than me would respond, but well, maybe they were
all quiet chuckles :) ?

Does your proposal require additional semantics on aio TCP socket
reads and writes that differ from the synchronous TCP case, besides
not blocking and indicating completion through aio_complete ?

On Sun, Aug 01, 2004 at 11:51:02PM -0300, Werner Almesberger wrote:
> Hi Suparna,
> 
> I'm copying this to netdev, because people there may get a good
> chuckle out of this outlandish idea as well :-)
> 
> At OLS we were chatting about using AIO also for networking.
> While this concept didn't seem to rank particularly high on the
> lunacy scale, it didn't appear overly useful either. About the
> only possibly interesting new functionality, besides the
> possibility to connect this with some eccentric TCP offloading
> and zero-copy scheme, would be - when applied to TCP - to make
> unACKed data in the out-of-order buffer available to user
> space.
> 
> Now, it occurred to me that this may lead to something a lot
> more exciting: a step towards making TCP real-time capable.
> I'm using the term "real-time" loosely here, as in "there's a
> deadline, but we're flexible".
> 
> I haven't followed what's going on at IETF in that area for a
> while, and I'm sure plenty of other people must have thought
> of similar schemes before, but since this seems nicer and
> maybe even simpler than some, let me describe it anyway.
> 
> First of all, one of the main complaints of the real-time
> networking people is that TCP stubbornly insists on
> retransmitting every single segment until it is absolutely
> certain that the segment has been received, even if the
> real-time application has long since moved on.
> 
> Now, with net-AIO, the application could already get all the
> data that has arrived after a lost segment. That's a good

> start, but TCP will still try to retransmit. So the next step
> would be to have a means to indicate that we've lost interest
> in the outcome of a pending AIO operation, and - as a side
> effect - communicate this also to TCP, so that TCP can stop
> trying, and do something more useful instead.
> 
> Let's call this operation aio_forget(). For disk IO, this
> may work just like aio_cancel().

The notion of which segment to aio_forget on the Rx path 
is a little hazy to me (were you were indeed referring
to the receive side here ? I can see this more clearly for
the send side when coupled with zero copy).

> 
> Now, aio_forget() would be a great tool for making TCP
> blissfully ignorant of any losses, actually making it very
> TCP-unfriendly. So the next step would be to record the fact
> that we've just forgotten some segments, but still need to
> make the peer aware of the fact that there (may) have been
> losses, and to slow down accordingly. Obviously, if we have
> reason to believe that the peer already knows of a loss in
> the general vicinity, no action is needed.
> 
> Reliably communicating a loss isn't trivial, but there should
> be good background material in the context of ECN. Of course,
> if ECN is available, we may just use that. Otherwise, we may
> have to force a retransmission, to be sure that the peer has
> noticed. (And, if the forgotten segment(s) should arrive while
> TCP is trying to indicate a loss, it should stop doing so.)
> 
> Now, assuming we have a solution for indicating losses that is
> satisfying both in terms of congestion control and in terms of
> efficiency, there are still a few things that would be nice to
> have, that this approach doesn't solve:
> 
>  - message boundaries and segment-message alignment. Not being
>    able to use messages just because a few of their bytes
>    ended up in a lost (and then aio_forgotten) segment would
>    be just too bad. In some cases, it may be possible to just
>    set the MSS to a suitable value. Also, recovering message
>    boundaries after a loss may be tricky.
> 
>  - there's no direct provision for allowing adaptive coding.
>    Of course, this is a fairly orthogonal problem.
> 
>  - as time passes, the sender may want to remove or substitute
>    data it had already enqueued, e.g because there is less
>    bandwidth than originally anticipated. So there may be a
>    place for aio_forget() at the sender side too.
> 
> Now, why could this scheme be "nicer" than just inventing some
> new protocol that is designed to do all these things ? The
> main thing that "looks good" is that this mechanism could use
> all of TCP, and may not even need major maintenance if some
> minor aspect of TCP congestion control gets changed.
> 
> Anyway, this may be peculiar enough for someone to spin the
> idea a little further. In the worst case, I might just have
> provided additional evidence that, if you just search long
> enough, there's a perfectly plausible problem for every
> solution :-)

Thanks for bringing in some fresh perspective :)

Regards
Suparna

> 
> - Werner
> 
> -- 
>   _________________________________________________________________________
>  / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
> /_http://www.almesberger.net/____________________________________________/

-- 
Suparna Bhattacharya (suparna@in.ibm.com)
Linux Technology Center
IBM Software Lab, India

Re: net-AIO and real-time TCP (blue sky research)

[Werner Almesberger]

Suparna Bhattacharya wrote:
> I was hoping all this while that someone with deeper knowledge
> in this area than me would respond, but well, maybe they were
> all quiet chuckles :) ?

Or they haven't stopped laughing yet ;-)

> Does your proposal require additional semantics on aio TCP socket
> reads and writes that differ from the synchronous TCP case, besides
> not blocking and indicating completion through aio_complete ?

Unfortunately, yes. First of all, we'd need a definition of where
in the stream the AIO operation is applied. Two possibilities:

 1) explicit: apply the concept of a "file position" to the stream,
    and make it visible to applications (through aio_offset)

 2) implicit: follow the existing principle that any read consumes
    just the next chunk of data, and internally assign positions
    based on the sequence number. As a consequence, AIOs would be
    ordered over time (in the case of individual aio_reads) and
    space (in the case of lio_listio).

In any case, it's a departure from existing API properties, i.e.
1) would introduce an application-visible "stream position" for
TCP (which doesn't agree with TCP being able to send arbitrarily
long streams, but then, a nice 64 bit position is probably close
enough to near-infinity), and 2) adds ordering to AIO, which may
be undesirable in terms of consistency, and also in terms of
lock avoidance.

There's also the issue of whether an AIO read should complete
after retrieving less than aio_nbytes. Three possibilities:

 1) never (probably not a great idea)
 2) may always (like "read" does)
 3) only on the last AIO read returning data

2) would be the most flexible approach, but requires either
application-settable positions (to fetch the missing part) or
automatic re-arranging of subsequent AIO reads.

3) avoids the problems of 2), but doesn't work well if the
reader didn't correctly predict segment boundaries, and may
cause trouble (like in 2) if there are pending requests after
the one that was "short", and new data arrives.

Last but not least, aio_forget would have to tell TCP that we're
not only no longer interested in retrieving a certain piece of
data, but that we'll never be.

If positions are implicit, aio_cancel would actually have this
effect (since there would be no way to request the same range of
data again), so we wouldn't even need aio_forget.

> The notion of which segment to aio_forget on the Rx path 
> is a little hazy to me (were you were indeed referring
> to the receive side here ? I can see this more clearly for
> the send side when coupled with zero copy).

Yes, this is mainly about receiving. Similar things could be
done for sending, but that's largely a separate issue.

Let's say I'm issuing three AIOs:

 1: offset = 0, nbytes = 100
 2: offset = 100, nbytes = 100
 3: offset = 200, nbytes = 100

Now a segment arrives for 0-99, and another for 200-299.
Normal TCP will retry (by ACKing sequence 100) until also the
segment 100-199 has made it.

With AIO-TCP, if our application is happy with getting two
out of the three requests, it can now aio_forget the 2nd
request. TCP would notice that can now ACK up to sequence 200,
for the forgotten read, and even up to sequence 300, because
the 200-299 has been received. So it'll ACK sequence 300 now,
and happily move on, without caring whether segment 100-199
ever gets through.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: net-AIO and real-time TCP (blue sky research)

[Sridhar Samudrala]

Your AIO-TCP looks pretty similar to the partial reliablity extension to
SCTP that allows an SCTP endpoint to signal to its peer that it is no longer
going to retransmit certain messages and should skip past those messages.
        http://www.ietf.org/rfc/rfc3758.txt

Thanks
Sridhar

On Wed, 11 Aug 2004, Werner Almesberger wrote:

> Suparna Bhattacharya wrote:
> > I was hoping all this while that someone with deeper knowledge
> > in this area than me would respond, but well, maybe they were
> > all quiet chuckles :) ?
>
> Or they haven't stopped laughing yet ;-)
>
> > Does your proposal require additional semantics on aio TCP socket
> > reads and writes that differ from the synchronous TCP case, besides
> > not blocking and indicating completion through aio_complete ?
>
> Unfortunately, yes. First of all, we'd need a definition of where
> in the stream the AIO operation is applied. Two possibilities:
>
>  1) explicit: apply the concept of a "file position" to the stream,
>     and make it visible to applications (through aio_offset)
>
>  2) implicit: follow the existing principle that any read consumes
>     just the next chunk of data, and internally assign positions
>     based on the sequence number. As a consequence, AIOs would be
>     ordered over time (in the case of individual aio_reads) and
>     space (in the case of lio_listio).
>
> In any case, it's a departure from existing API properties, i.e.
> 1) would introduce an application-visible "stream position" for
> TCP (which doesn't agree with TCP being able to send arbitrarily
> long streams, but then, a nice 64 bit position is probably close
> enough to near-infinity), and 2) adds ordering to AIO, which may
> be undesirable in terms of consistency, and also in terms of
> lock avoidance.
>
> There's also the issue of whether an AIO read should complete
> after retrieving less than aio_nbytes. Three possibilities:
>
>  1) never (probably not a great idea)
>  2) may always (like "read" does)
>  3) only on the last AIO read returning data
>
> 2) would be the most flexible approach, but requires either
> application-settable positions (to fetch the missing part) or
> automatic re-arranging of subsequent AIO reads.
>
> 3) avoids the problems of 2), but doesn't work well if the
> reader didn't correctly predict segment boundaries, and may
> cause trouble (like in 2) if there are pending requests after
> the one that was "short", and new data arrives.
>
> Last but not least, aio_forget would have to tell TCP that we're
> not only no longer interested in retrieving a certain piece of
> data, but that we'll never be.
>
> If positions are implicit, aio_cancel would actually have this
> effect (since there would be no way to request the same range of
> data again), so we wouldn't even need aio_forget.
>
> > The notion of which segment to aio_forget on the Rx path
> > is a little hazy to me (were you were indeed referring
> > to the receive side here ? I can see this more clearly for
> > the send side when coupled with zero copy).
>
> Yes, this is mainly about receiving. Similar things could be
> done for sending, but that's largely a separate issue.
>
> Let's say I'm issuing three AIOs:
>
>  1: offset = 0, nbytes = 100
>  2: offset = 100, nbytes = 100
>  3: offset = 200, nbytes = 100
>
> Now a segment arrives for 0-99, and another for 200-299.
> Normal TCP will retry (by ACKing sequence 100) until also the
> segment 100-199 has made it.
>
> With AIO-TCP, if our application is happy with getting two
> out of the three requests, it can now aio_forget the 2nd
> request. TCP would notice that can now ACK up to sequence 200,
> for the forgotten read, and even up to sequence 300, because
> the 200-299 has been received. So it'll ACK sequence 300 now,
> and happily move on, without caring whether segment 100-199
> ever gets through.
>
> - Werner
>
> --
>   _________________________________________________________________________
>  / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
> /_http://www.almesberger.net/____________________________________________/
>
>

Re: net-AIO and real-time TCP (blue sky research)

[Werner Almesberger]

Sridhar Samudrala wrote:
> Your AIO-TCP looks pretty similar to the partial reliablity extension to
> SCTP that allows an SCTP endpoint to signal to its peer that it is no longer
> going to retransmit certain messages and should skip past those messages.

Damn, so it's not such a crazy idea after all :-)

Something like this would be useful for the sender side, if the
receiver can't figure out on its own that it shouldn't wait for
the data to arrive. (And, assuming that the sender skips data by
leaving a gap, not by filling it with other data, which seems
like a reasonable assumption if we use AIO-TCP at both ends. If
the receiver may use regular TCP, the sender would have to try
to fill the missing part, which can be hairy, particularly if
some of the data-to-be-dropped has already be sent.)

Clearly, any such thing on the sender side would need to have some
means to detect that the receiver can recover from segments that
are never sent.

Is a concrete API for this functionality described somewhere ?
(I only skimmed through the RFC, but the API mentioned there
looks more like an abstract one.)

I like the term "partial reliability" :)

Thanks,
- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: net-AIO and real-time TCP (blue sky research)

[Sridhar Samudrala]

On Wed, 11 Aug 2004, Werner Almesberger wrote:

> Sridhar Samudrala wrote:
> > Your AIO-TCP looks pretty similar to the partial reliablity extension to
> > SCTP that allows an SCTP endpoint to signal to its peer that it is no longer
> > going to retransmit certain messages and should skip past those messages.
>
> Damn, so it's not such a crazy idea after all :-)
>
> Something like this would be useful for the sender side, if the
> receiver can't figure out on its own that it shouldn't wait for
> the data to arrive. (And, assuming that the sender skips data by
> leaving a gap, not by filling it with other data, which seems
> like a reasonable assumption if we use AIO-TCP at both ends. If
> the receiver may use regular TCP, the sender would have to try
> to fill the missing part, which can be hairy, particularly if
> some of the data-to-be-dropped has already be sent.)
>
> Clearly, any such thing on the sender side would need to have some
> means to detect that the receiver can recover from segments that
> are never sent.
>
> Is a concrete API for this functionality described somewhere ?
> (I only skimmed through the RFC, but the API mentioned there
> looks more like an abstract one.)

There is a sockets API extensions for SCTP draft that describes a
way for an app to specify timetolive value for a message.
This can be done using the standard sendmsg() with a control
mesage of type SCTP_SNDRCV.

Also a new API sctp_sendmsg() can be used which has timetolive
as an argument.

http://www.ietf.org/internet-drafts/draft-ietf-tsvwg-sctpsocket-08.txt

-Sridhar

>
> I like the term "partial reliability" :)
>
> Thanks,
> - Werner
>
> --
>   _________________________________________________________________________
>  / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
> /_http://www.almesberger.net/____________________________________________/
>

Re: net-AIO and real-time TCP (blue sky research)

[Suparna Bhattacharya]

On Wed, Aug 11, 2004 at 08:18:29PM -0300, Werner Almesberger wrote:
> Suparna Bhattacharya wrote:
> > I was hoping all this while that someone with deeper knowledge
> > in this area than me would respond, but well, maybe they were
> > all quiet chuckles :) ?
> 
> Or they haven't stopped laughing yet ;-)
> 
> > Does your proposal require additional semantics on aio TCP socket
> > reads and writes that differ from the synchronous TCP case, besides
> > not blocking and indicating completion through aio_complete ?
> 
> Unfortunately, yes. First of all, we'd need a definition of where
> in the stream the AIO operation is applied. Two possibilities:
> 
>  1) explicit: apply the concept of a "file position" to the stream,
>     and make it visible to applications (through aio_offset)
> 
>  2) implicit: follow the existing principle that any read consumes
>     just the next chunk of data, and internally assign positions
>     based on the sequence number. As a consequence, AIOs would be
>     ordered over time (in the case of individual aio_reads) and
>     space (in the case of lio_listio).
> 
> In any case, it's a departure from existing API properties, i.e.
> 1) would introduce an application-visible "stream position" for
> TCP (which doesn't agree with TCP being able to send arbitrarily
> long streams, but then, a nice 64 bit position is probably close
> enough to near-infinity), and 2) adds ordering to AIO, which may
> be undesirable in terms of consistency, and also in terms of
> lock avoidance.
> 
> There's also the issue of whether an AIO read should complete
> after retrieving less than aio_nbytes. Three possibilities:
> 
>  1) never (probably not a great idea)
>  2) may always (like "read" does)
>  3) only on the last AIO read returning data
> 
> 2) would be the most flexible approach, but requires either
> application-settable positions (to fetch the missing part) or
> automatic re-arranging of subsequent AIO reads.
> 
> 3) avoids the problems of 2), but doesn't work well if the
> reader didn't correctly predict segment boundaries, and may
> cause trouble (like in 2) if there are pending requests after
> the one that was "short", and new data arrives.
> 
> Last but not least, aio_forget would have to tell TCP that we're
> not only no longer interested in retrieving a certain piece of
> data, but that we'll never be.
> 
> If positions are implicit, aio_cancel would actually have this
> effect (since there would be no way to request the same range of
> data again), so we wouldn't even need aio_forget.
> 
> > The notion of which segment to aio_forget on the Rx path 
> > is a little hazy to me (were you were indeed referring
> > to the receive side here ? I can see this more clearly for
> > the send side when coupled with zero copy).
> 
> Yes, this is mainly about receiving. Similar things could be
> done for sending, but that's largely a separate issue.
> 
> Let's say I'm issuing three AIOs:
> 
>  1: offset = 0, nbytes = 100
>  2: offset = 100, nbytes = 100
>  3: offset = 200, nbytes = 100
> 
> Now a segment arrives for 0-99, and another for 200-299.
> Normal TCP will retry (by ACKing sequence 100) until also the
> segment 100-199 has made it.
> 
> With AIO-TCP, if our application is happy with getting two
> out of the three requests, it can now aio_forget the 2nd
> request. TCP would notice that can now ACK up to sequence 200,
> for the forgotten read, and even up to sequence 300, because
> the 200-299 has been received. So it'll ACK sequence 300 now,
> and happily move on, without caring whether segment 100-199
> ever gets through.

OK, in the light of the change in semantics you described
earlier, introducing the notion of an offset, this makes sense. 
Thanks for clarifying.

Regards
Suparna

> 
> - Werner
> 
> -- 
>   _________________________________________________________________________
>  / Werner Almesberger, Buenos Aires, Argentina     werner@almesberger.net /
> /_http://www.almesberger.net/____________________________________________/

-- 
Suparna Bhattacharya (suparna@in.ibm.com)
Linux Technology Center
IBM Software Lab, India

Re: net-AIO and real-time TCP (blue sky research)

[John Heffner]

On Wed, 11 Aug 2004, Werner Almesberger wrote:

> Sridhar Samudrala wrote:
> > Your AIO-TCP looks pretty similar to the partial reliablity extension to
> > SCTP that allows an SCTP endpoint to signal to its peer that it is no longer
> > going to retransmit certain messages and should skip past those messages.
>
> Damn, so it's not such a crazy idea after all :-)

Perhaps not for SCTP.  I'd love to see a good AIO API for TCP, but if what
you are describing is implemented, the resulting protocol would be
something other than TCP.  There are some RDDP people talking about
similar things, and it is quite controversial within the IETF.

It might be easier to focus on SCTP.  This is what it was designed for.

  -John