[asio-users] [asio] RFC on new reliable UDP library

[Niall Douglas]

Dear Boost and ASIO users,

CC: ***@lists.boost.org, asio-***@lists.sourceforge.net

I am writing to ask for comments on the design of and interest in a
generic reliable messaging library based on ASIO. Such a library
could bring to ASIO very considerably improved data transfer
performance over TCP, plus the ability to ignore NAT firewalls. The
design imperatives for such a library are proving tricky to reach
consensus upon, so perhaps the community might be able to help.


Firstly, what features should such a reliable messaging library have?
Here are some for you to consider:

* Should it have wire transport backends with an abstraction from
wire transports, so a UDT backend could be interchangeable with TCP
for example with just a recompile needed? Upper level code need
therefore not consider what format the wire transport takes, just
that messages are reliably delivered or we are told of the connection
failure. Some mechanism for dealing with out of order messages, and
message expiry in case congestion control excessively delays outbound
messages would also be included.

You should be aware that congestion control for a reliable messaging
library means one has no choice but to pace message construction
(i.e. block/EWOULDBLOCK handing out new message send templates),
otherwise one ends up buffering more data for sending than
potentially can ever be delivered. This is because we cannot drop
reliable messages, nor can we pace writes, so pacing new message
construction is the only alternative.


* Should it be zero copy for both receipt and send? If so, we'll have
to break with the existing ASIO API somewhat - namely that
MutableBufferSequence will need to now become
MutableFileOffsetBufferSequence so one can supply scatter/gathers of
user space buffers and kernel side buffers. We'll also have to
templatise the buffer management so client code can supply the
virtualisation (e.g. an iterator) which remaps inbound message
fragments into apparently contiguous regions. By the time we have
done these, the API looks quite different.


* Should it be written using C++ 14 idioms instead of the existing 03
idioms ASIO uses? If so, basing read and write handlers on the C++ 17
proposed experimental::expected<T, E>
(http://www.hyc.io/boost/expected-proposal.pdf) makes much more sense
than the fixed ASIO handler prototype void (*handler)(const
boost::system::error_code& ec, std::size_t bytes_transferred) - it is
more powerful, more expressive, optionally integrates cleanly with
no-alloc future-promise and the rest of the C++ 11/14 STL, and lets
handlers use any mix of error reporting mechanism they choose. It
also opens the door to a much cleaner and tighter integration of the
future C++ 17 Networking TS with Concurrency TS.

Equally, especially if combined with the earlier changes, it goes
further and further away from the present ASIO design.


* How concurrent should it be capable of? Unlike TCP where it makes
not much sense to have concurrent writers, UDP allows enormous
parallelism, potentially into queue depths of thousands on decent
NICs, sufficiently so where a strand based design may simply not
scale. We believe that with some effort a completely lock free design
which can make full use of the batch datagram send and receive APIs
on Linux and Windows is possible - we believe that such a design
would scale close to linearly to CPU cores available. Unfortunately,
as batch datagram send/receive is not supported by ASIO and on POSIX
the main dispatcher appears to be locked by a mutex, this would
require a custom code path and i/o service. If combined with all of
the above, it starts to look like a rewrite of the core of ASIO which
seems very big just to implement reliable messaging.


I guess that is good for now for starting discussion. My thanks for
your time in advance.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/

[Niall Douglas]

On 9 Sep 2014 at 15:03, Rodrigo Madera wrote:

> Looks very interesting and I would love to see that lib happen.
>
> I believe in building up on knowledge recursively. So the first thing I
> would do is read on the enormous effort ZeroMQ [1] has put into analysing
> this problem domain. They have a (very) large set of material debating and
> explaining design decisions made on the library. After that, there is
> nanomsg [2], which is a derivative work from the lessons learned from
> ZeroMQ itself. Have you read through those in search of insights? It would
> be a very good source of debate material for this brand new library. There
> are problems they have encountered already, though you may decide to solve
> them differently.

Yes, we did. And therein lies the debate: ASIO's design was a product
of its time, and while its design was close to optimal for its time,
it now makes life harder than it should be in a world with 40Gbit
ethernet, mobile devices where power consumption is important, and
where non-Linux operating system kernels can DMA straight to and from
user space if and only if you are very careful with how you use ASIO.

The debate lies in to what extent does one break with ASIO's
established norms and practices to achieve the features I listed.
Even deciding on how much C++ 14 to use, or how much to embrace C++
17 resumable functions is controversial.

> Of course, that is if you haven't read that already. It just reminded me of
> how many insights these guys had in all the years they spent using and
> creating network middleware code. And basing a new network library off of
> this knowledge could be good.

I would strongly emphasise that no one is proposing we try doing
ZeroMQ or anything like it "better". In our reliable messaging
library we would provide the absolute minimum abstraction with which
one could build *any* reliable messaging solution of their choice.
The contract does involve the replication of at least one reliable
UDP implementation (actually one of Chris' early implementations) as
the original has heavily bitrotted, but apart from that we were
thinking of UDT as a second backend, and leaving it at that. We chose
UDT mainly because we believe we can reuse some of it for duplicating
Chris' RUDP implementation.

> About the language, I would totally look forward into C++11 and up design.

Be aware that C++ 11, and especially C++ 17 as it currently is
thought to become, consider future-promise as the sole way for i/o
completion handlers to be invoked via the new
future<T>.then(callable) function. In particular, 17's resumable
function support *requires* that the function must return a future,
so if you want language based coroutine support, you must use
future<T>.

As much as Chris and many ASIO users are opposed to that design
choice, we must play with the hand we have been dealt by WG21. I will
say that future-promise can be made constexpr and no-alloc, and that
makes an awful lot of the inefficiency go away, though an implicit
synchronisation is unavoidable as .then() must check if the operation
has already completed.


On 9 Sep 2014 at 21:31, Andrew Marlow wrote:

> Is it going to include reliable multicast? If so then a good place to
> start is the RFCs and various attempts at reliable multicast in the past.
> The two that spring to mind are NORM (
> http://downloads.pf.itd.nrl.navy.mil/docs/norm/NormDeveloperGuide.html)
> for which there is a reference implementation, and PGM (Pragmatic General
> Multicast, http://tools.ietf.org/html/rfc3208). Don't forget Scalable
> Reliable Multicast, SRM,
> http://en.wikipedia.org/wiki/Scalable_Reliable_Multicast. There are
> whole frameworks based just on reliable multicast, e.g. spread,
> http://www.spread.org. Personally, I think this is far too big an area
> for boost. $0.02.

We are very much thinking of an abstraction framework with which one
could implement things like the above. The hope would be that our new
library would take care of platform-specific hassle like making whole
system zero-copy networking right to and from the NIC disappear,
stuff like that.

We are also considering a monadic continuations framework allowing
code just above ASIO to use ASIO generically. In other words, the
standard C++ i/o monad equals ASIO. This ought to very significantly
ease the writing of highly generic code avoiding much of the
boilerplate you often need to join up ASIO async handlers, and
therefore should make much easier implementing ZeroMQ or reliable
multicast or any other messaging protocol.

Another debate is indeed where the bottom level wire protocol should
end and the monadic high level part should begin. For example some
feel this approach would make impossible the reuse of third party
implementation libraries.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/

[Cory Nelson]

I'd suggest looking at BitTorrent's uTP. It's well established and is built
with reliability, perf, and firewall compatibility in mind. It does have
congestion control tuned to be a lower priority than any other traffic, but
I see no reason that couldn't be changed (or made configurable).

https://en.wikipedia.org/wiki/Micro_Transport_Protocol

On Tue, Sep 9, 2014 at 11:59 AM, Niall Douglas <***@nedprod.com>
wrote:

> Dear Boost and ASIO users,
>
> CC: ***@lists.boost.org, asio-***@lists.sourceforge.net
>
> I am writing to ask for comments on the design of and interest in a
> generic reliable messaging library based on ASIO. Such a library
> could bring to ASIO very considerably improved data transfer
> performance over TCP, plus the ability to ignore NAT firewalls. The
> design imperatives for such a library are proving tricky to reach
> consensus upon, so perhaps the community might be able to help.
>
>
> Firstly, what features should such a reliable messaging library have?
> Here are some for you to consider:
>
> * Should it have wire transport backends with an abstraction from
> wire transports, so a UDT backend could be interchangeable with TCP
> for example with just a recompile needed? Upper level code need
> therefore not consider what format the wire transport takes, just
> that messages are reliably delivered or we are told of the connection
> failure. Some mechanism for dealing with out of order messages, and
> message expiry in case congestion control excessively delays outbound
> messages would also be included.
>
> You should be aware that congestion control for a reliable messaging
> library means one has no choice but to pace message construction
> (i.e. block/EWOULDBLOCK handing out new message send templates),
> otherwise one ends up buffering more data for sending than
> potentially can ever be delivered. This is because we cannot drop
> reliable messages, nor can we pace writes, so pacing new message
> construction is the only alternative.
>
>
> * Should it be zero copy for both receipt and send? If so, we'll have
> to break with the existing ASIO API somewhat - namely that
> MutableBufferSequence will need to now become
> MutableFileOffsetBufferSequence so one can supply scatter/gathers of
> user space buffers and kernel side buffers. We'll also have to
> templatise the buffer management so client code can supply the
> virtualisation (e.g. an iterator) which remaps inbound message
> fragments into apparently contiguous regions. By the time we have
> done these, the API looks quite different.
>
>
> * Should it be written using C++ 14 idioms instead of the existing 03
> idioms ASIO uses? If so, basing read and write handlers on the C++ 17
> proposed experimental::expected<T, E>
> (http://www.hyc.io/boost/expected-proposal.pdf) makes much more sense
> than the fixed ASIO handler prototype void (*handler)(const
> boost::system::error_code& ec, std::size_t bytes_transferred) - it is
> more powerful, more expressive, optionally integrates cleanly with
> no-alloc future-promise and the rest of the C++ 11/14 STL, and lets
> handlers use any mix of error reporting mechanism they choose. It
> also opens the door to a much cleaner and tighter integration of the
> future C++ 17 Networking TS with Concurrency TS.
>
> Equally, especially if combined with the earlier changes, it goes
> further and further away from the present ASIO design.
>
>
> * How concurrent should it be capable of? Unlike TCP where it makes
> not much sense to have concurrent writers, UDP allows enormous
> parallelism, potentially into queue depths of thousands on decent
> NICs, sufficiently so where a strand based design may simply not
> scale. We believe that with some effort a completely lock free design
> which can make full use of the batch datagram send and receive APIs
> on Linux and Windows is possible - we believe that such a design
> would scale close to linearly to CPU cores available. Unfortunately,
> as batch datagram send/receive is not supported by ASIO and on POSIX
> the main dispatcher appears to be locked by a mutex, this would
> require a custom code path and i/o service. If combined with all of
> the above, it starts to look like a rewrite of the core of ASIO which
> seems very big just to implement reliable messaging.
>
>
> I guess that is good for now for starting discussion. My thanks for
> your time in advance.
>
> Niall
>
> --
> ned Productions Limited Consulting
> http://www.nedproductions.biz/
> http://ie.linkedin.com/in/nialldouglas/
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>



--
Cory Nelson
http://int64.org

[Niall Douglas]

On 10 Sep 2014 at 13:36, Cory Nelson wrote:

> I'd suggest looking at BitTorrent's uTP. It's well established and is built
> with reliability, perf, and firewall compatibility in mind. It does have
> congestion control tuned to be a lower priority than any other traffic, but
> I see no reason that couldn't be changed (or made configurable).
>
> https://en.wikipedia.org/wiki/Micro_Transport_Protocol

I didn't know about this protocol before, thank you. It seems this
wheel is constantly reinvented.


On 10 Sep 2014 at 23:12, Andrey Semashev wrote:

> On Tuesday 09 September 2014 17:59:12 Niall Douglas wrote:
> > Dear Boost and ASIO users,
> >
> > CC: ***@lists.boost.org, asio-***@lists.sourceforge.net
> >
> > I am writing to ask for comments on the design of and interest in
a
> > generic reliable messaging library based on ASIO.
>
> How would it compare to SCTP and why not just add support for SCTP
to
> Boost.ASIO?

It wouldn't compare to SCTP. It would make the adding of SCTP support
to ASIO much easier hopefully.


On 11 Sep 2014 at 9:26, Václav Zeman wrote:

> +1. I have had the same thought.

For my client's purposes, SCTP is not useful because it is not TCP
nor UDP, and therefore is not understood by home networking
equipment. This is a showstopper for them. There is SCTP over UDP,
however there is no mature portable implementation library for that
which I am aware of. In comparison, UDT is portable and has a mature
portable implementation library, and one in fairly high quality C++
at that too. Hence the choice of UDT over SCTP as the second wire
format we are likely to implement.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/

[Niall Douglas]

On 11 Sep 2014 at 15:10, Andrey Semashev wrote:

> > For my client's purposes, SCTP is not useful because it is not TCP
> > nor UDP, and therefore is not understood by home networking
> > equipment. This is a showstopper for them. There is SCTP over UDP,
> > however there is no mature portable implementation library for that
> > which I am aware of. In comparison, UDT is portable and has a mature
> > portable implementation library, and one in fairly high quality C++
> > at that too. Hence the choice of UDT over SCTP as the second wire
> > format we are likely to implement.
>
> There is libusrsctp [1][2], although it's under BSD license (as is the
> UDT library) and in C.
>
> UDT over SCTP looks like a duplicate work since the functionality of
> these protocols largely overlap (as far as I can see from Wikipedia).
> Basically, that's why SCTP looks so appealing - it offers everything
> UDT does and then some, and it is standardized.

I think you thought I said we intend to implement UDT atop of SCTP.
SCTP isn't useful to us due to the lack of home networking equipment
support, we won't be implementing that. We will probably be
implementing UDT though instead, it can NAT hole punch too. No SCTP,
but someone else not us might find our library useful in such an
implementation.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/

[Niall Douglas]

On 11 Sep 2014 at 9:50, adzm wrote:

> asio support for UDT could easily stand alone. I have considered embarking
> upon this project myself, but the UDT library does not easily fit into
> asio's patterns. However, there is also the possiblity of implementing the
> UDT protocol rather than wrapping the UDT library, but that is obviously
> much more work and more surface area for bugs. But UDT fulfills most needs
> for mixing reliable with unreliable transport.

You hit the nail on the head exactly. There will have to be _some_
breakage to ASIO norms to implement this. The question is how much
and in which ways? If you are going to break, why not use 11/14
idiomatic C++ instead of 03 C++? Should we bother to do absolute
zero-copy from the NIC given the additional design complexity? Just
how much do you change before it starts to look not that much like
ASIO at all?

During the last few days I persuaded proposed
experimental::expected<T, E> to compile and run on VS 14 CTP 3, and I
believe a usable port to VS2013 ought to be straightforward. That
opens the door to very low latency future-promise on all recent
compilers.

> Are there other popular user-mode protocols built over UDP that provide
> similar functionality? Elsewhere in this thread uTP was mentioned, but I am
> unfamiliar. SCTP is also mentioned, but has the unfortunate and significant
> drawback of being both painful and rare on Windows.

Our primary purpose is actually to provide an early RUDP
implementation by Chris. His original needs rewriting. UDT is only
really in there because we believe we can reuse implementation and
save effort.

> I really think supporting UDT, either via wrapping the library or
> implementing the protocol, would be a great first step. It would be
> immediately usable by many users, and I am certain the process of
> implementation will reveal where the limitations of asio hurt the most.
>
> Beyond that, I think there is a definite need for this, but the biggest
> obstacle is that most applicable standards are either very complex or don't
> exist in the first place. And boost is probably not the best place for
> implementing a custom protocol, although would be a great home for the
> building blocks.

If the standard C++ networking library provides some standard
reliable messaging implementation with performance far in excess of
TCP for some use cases, you betcha it becomes the standard (if it
isn't braindead designed).

In GSoC 2014 a new Boost HTTP library was designed and written. It
could look very interesting to combine that with reliable UDP for a
whole new viewpoint on HTTP 2.0, especially as Google QUIC seems to
have ground to a halt.

> For example, over the years I've coded several UDP hole punch
> implementations, and have always wanted to submit them to boost, but they
> ended up depending on some non-standard functionality for things like
> authentication, match-making, IP address detection, etc. The alternative
> leads to something like ICE, but the complexity level rises quickly after
> that.

Well, we won't be going beyond what the client absolutely needs - the
reason for considering the future-promise-on-expected design is due
to wider needs to offload incoming and outgoing messages to OpenCL
for processing, and therefore some form of low latency continuations
framework is needed, and it might as well be the potential C++ 17
one. Chris's RUDP can do NAT hole punching, and we'll be duplicating
his implementation which looks very similar to UDT's. We are
certainly not looking to reinvent anything here, just aim for a very
conservative set of minimum goals which are to reimplement Chris'
RUDP in a more scalable solution.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/