UDP use cases
Martin Sustrik
More investigation of UDP use cases seem to point at the fact that UDP
is used in widely disparate scenarios. So far I was able to identify at
least 3 of them:
1. UDP/IP broadcast/multicast. People with need for IP multicast often
build it on top of UDP. The reason being that you need no special
privileges to use UDP, while using raw IP sockets is often restricted in
some way. There's a lot of inhouse solutions build on top of UDP/IP
multicast. From publicly available solution, PGM (RFC 3208) encapsulated
in UDP falls to this catergory. The two main use cases are high-volume
data distribution (financial services) on LAN and service discovery
(generic local network services).
2. Transports based on UDP are used to transfer bulk data via
high-bandwidth high-latency links. It's basically a workaround for TCP's
peformance deficiencies on such links. UDT is an example of solution
aimed at this use case (high performance computing).
3. Finally, UDP is often use for transferring unreliable real-time
streams. Streaming audio, Internet telephony, and massively multiplayer
on-line games. An example of protocol explicitly aiming at these use
cases is DCCP (RFC 4340).
From framing point of view, each of these use cases seems to imply
different design decisions. Case 1 would be more similar to other
multicast framings, e.g. PGM. In case 2 the framing can be almost
identitcal to TCP framing. Case 3 seems to be a problem of its own.
Thoughts?
Martin
cerber
One more use case of UDP would be gossip protocols, DHT implementations, and such. The use case is very different from described above - no multicast, low-volume, high scalability and low overhead both in terms of system resources and brandwidth used. Each packet usually represents a single self-contained message, no streams, no acks etc., very effective congestion control mechanisms. Framing for this use case would probably be different from the 3 use cases you mentioned.
Artur Brugeman
Martin Sustrik
How does that differ from the case 3 (DCCP)? Can you give a concrete
example of such a use case/application/protocol?
Thanks!
Martin
brugeman
I've never investigated DCCP, but from your description of use case 3, and my own brief look at RFC4340 I can tell that DCCP is about streams. You establish a (sort of) connection, you start sending (big amount of) data, and you can be sure that underlying transport will make it's best to deliver the data to receiver w/o congestion (with some part of the stream probably being lost).
A concrete example of, say, DHT, is very different. It's a p2p overlay network, each peer communicates with a selected set of other peers, each communication usually consists of a single request and reply frame, congestion is prevented by dropping above-rate frames, a single "REQUEST" to DHT consists of several communications with different peers, set of known peers is updated to drop inactive ones. The DHT itself is usually used to discover the source of data, after discovery a better suited protocols are used to deliver the data, thus DHT must be very low-overhead to allow the main transport to work at full speed.
Another thing, which I'm currently trying to implement with zmq by the way, is anty-entropy gossip protocol. It is used to share global state in a p2p network in a predictable time and with consistency guarantees. Although the use case seems different from DHT, the underlying communication patterns are similar - peers are selected randomly, data is exchanged say every second, a single exchange is a request and reply consisting of single frame, congestion is prevented by dropping excessive incoming frames, and carefully limiting the size and amount of outgoing frames. Again, the gossiping is usually a job supporting the main application activity, so very low cpu and brandwidth must be used. A nice article on the topic is this.
I'm not a profi in these both areas, just have some practical experience of working with both, so my descriptions could be not 100% accurate. Still my feeling is that they differ from DCCP greatly.
Artur Brugeman
J. Andrew Rogers
As an observation, there does not seem to be many obvious advantages
to using UDP for gossip protocols; many of the important gossip
protocols (e.g. BGP4) run over TCP. Not that you can't run it over
UDP, just that many of the most successful applications of gossip
protocols don't seem to. I suppose some p2p apps might rely on
gossip-like protocols for UDP.
Tangentially, gossip protocols have scalability limitations accurately
documented in literature. They work very well for certain use cases
but there is a reason large clusters tend to manage their metadata
differently even though modern gossip protocols are (at least) 20
years old. At least in e.g. the BigData space almost no one uses
gossip protocols, Cassandra is the primary exception.
If p2p is more important than scale then gossip is the way to go. The
caveat is that there is (currently) no math for robust decentralized
protocols; it is arguably one of the more important unsolved problems
in the theory of how one routes a network. Provably robust p2p systems
all have a central actor buried in them somewhere, even if not
obvious. It is one of the reasons p2p has had a hard time establishing
itself -- too easy to attack.
Which is a long way of saying that if you need a scalable and robust
quasi-decentralized network topology, you'll probably be happy with
TCP in real systems even if implementing gossip protocols. There are
cases where UDP could be useful but it could be argued whether or not
it has a justifiable ROI.
--
J. Andrew Rogers
Pieter Hintjens
> More investigation of UDP use cases seem to point at the fact that UDP is
> used in widely disparate scenarios. So far I was able to identify at least 3
> of them...
> Thoughts?
1. My usual complaint that email is a lousy medium for collecting
knowledge, whereas wikis do this very well. I.e., could we not adopt
the model of posting such analyses to a wiki, followed by discussion
by email? Especially if the reader needs some background material.
2. Concretely, what impact do these use case differences have on
framing? We've not defined what "multicast framing" and "TCP framing"
are, afaics. Are these terms accurate? What is the distinction here?
I'd assume the distinction is between connected and disconnected
transports, where connected transports can send data frames within an
established context, and disconnected transports cannot.
But it would be helpful to define terminology and context, so we don't
need to make assumptions.
Cheers
Pieter
brugeman
This seems a bit off the topic (UPD use cases), but still...
> As an observation, there does not seem to be many obvious advantages
> to using UDP for gossip protocols; many of the important gossip
> protocols (e.g. BGP4) run over TCP. Not that you can't run it over
> UDP, just that many of the most successful applications of gossip
> protocols don't seem to. I suppose some p2p apps might rely on
> gossip-like protocols for UDP.
protocols. I'd be very thankful if you could point out the important
gossip protocols and their successful applications you are
mentioning.
> Tangentially, gossip protocols have scalability limitations accurately
> documented in literature. They work very well for certain use cases
> but there is a reason large clusters tend to manage their metadata
> differently even though modern gossip protocols are (at least) 20
> years old. At least in e.g. the BigData space almost no one uses
> gossip protocols, Cassandra is the primary exception.
scalability limitations, I'd be very grateful. I'm researching
this field currently and any helpful information will be appreciated. And
btw Dynamo (and probably many clones of it) would be a secondary
> If p2p is more important than scale then gossip is the way to go. The
> caveat is that there is (currently) no math for robust decentralized
> protocols; it is arguably one of the more important unsolved problems
> in the theory of how one routes a network. Provably robust p2p systems
> all have a central actor buried in them somewhere, even if not
> obvious. It is one of the reasons p2p has had a hard time establishing
> itself -- too easy to attack.
Please mention the names of those provably robust p2p systems
- I seem to have not enough theoretical knowledge to get your point
w/o concrete examples.
> Which is a long way of saying that if you need a scalable and robust
> quasi-decentralized network topology, you'll probably be happy with
> TCP in real systems even if implementing gossip protocols. There are
> cases where UDP could be useful but it could be argued whether or not
> it has a justifiable ROI.
high scale communications. What I was saying was that if I try to use UDP for this,
such usage would differ from use cases Martin mentioned. The closest one would
probably be the UDP/IP broadcast/multicast.
Martin Sustrik
> 1. My usual complaint that email is a lousy medium for collecting
> knowledge, whereas wikis do this very well. I.e., could we not adopt
> the model of posting such analyses to a wiki, followed by discussion
> by email? Especially if the reader needs some background material.
The goal is to move to IETF, thus we should observe IETF process, ie.
knowledge is gathered in I-Ds, discussion happens via the mailing list.
I will setup a wiki, however, it should be used only for transient work
in progress. Any relevant results should be published as I-Ds.
> 2. Concretely, what impact do these use case differences have on
> framing? We've not defined what "multicast framing" and "TCP framing"
> are, afaics. Are these terms accurate? What is the distinction here?
The point is that people are using UDP instead of IP to implement their
own L4 protocols on top of it. So speaking of "UDP" transport doesn't
makes much sense. PGM-style scenarios are very different form UDT-style
scenarios which are different from DCCP-style scenarios etc.
For example, with UDP/IP multicast you have to take late joiners into
account (and modify the protocol accordingly) while this in not the case
with UDT.
"mutlicast framing" and "TCP framing" are used just as placehoders here.
What I was trying to say "we can use the same protocol for TCP and UDT
whatever the protocol happens to be".
> I'd assume the distinction is between connected and disconnected
> transports, where connected transports can send data frames within an
> established context, and disconnected transports cannot.
That's one disctinction, but there are lots of others: ordering
guarantees, reliability guarantees, unicast vs. multicast etc.
> But it would be helpful to define terminology and context, so we don't
> need to make assumptions.
That's what I am trying to do here. Analysing use cases should result in
context and terminology.
Martin
Martin Sustrik
I did some quick reading about gossip protocols and it seems the reason
why the TCP doesn't fit (if it doesn't) is that:
1. There are too many peers to speak to, however, you speak only to
limited subset (one?) at each specific moment. Thus, maintaining TCP
connections to all the peers doesn't make sense.
2. There's no need for reliability.
What it boils down to, AFAICS, is some kind of anycast behaviour...
Am I on a completely wrong track here?
Martin
Pieter Hintjens
> The goal is to move to IETF, thus we should observe IETF process, ie.
> knowledge is gathered in I-Ds, discussion happens via the mailing list.
>
> I will setup a wiki, however, it should be used only for transient work in
> progress. Any relevant results should be published as I-Ds.
"I-D"?
You mean an RFC? Yes, you would typically have transient work in
progress, use cases, background material, etc. on a wiki, disposable
discussion by email, and formal results published as stand-alone
documents.
> The point is that people are using UDP instead of IP to implement their own
> L4 protocols on top of it. So speaking of "UDP" transport doesn't makes much
> sense. PGM-style scenarios are very different form UDT-style scenarios which
> are different from DCCP-style scenarios etc.
Certainly. You can define "transport" quite variably. But when we
speak of UDP as a transport, I think it's clear what semantics we're
talking about: datagrams sent without prior connections. If we talk of
PGM, UDT, DCCP, RDP, each these can be considered as a transport with
their own characteristics. Layering transports on top of UDP doesn't
make UDP more ambiguous, does it?
> "mutlicast framing" and "TCP framing" are used just as placehoders here.
> What I was trying to say "we can use the same protocol for TCP and UDT
> whatever the protocol happens to be".
:) I know what you meant, but only because we share lots of common
experience. You can't assume that more broadly. It's useful to anchor
terminology with definitions, even if these are speculative.
>> I'd assume the distinction is between connected and disconnected
>> transports, where connected transports can send data frames within an
>> established context, and disconnected transports cannot.
>
> That's one disctinction, but there are lots of others: ordering guarantees,
> reliability guarantees, unicast vs. multicast etc.
How do these aspects concern framing, specifically? You contrasted two
types of framing. I'd like to understand what specifically this means
(and I'm referring to bits on the wire here, not use cases, and not
higher-level semantics).
For example, do frames need versioning? Over disconnected transports,
yes. Over connected transports, this can be normalised into a greeting
frame.
> That's what I am trying to do here. Analysing use cases should result in
> context and terminology.
Sure. I'd like to avoid discussions based on assumptions and
terminology that aren't documented and/or 100% obvious to all
participants.
What emerges from this thread seems to be that (a) we have a lot of
potential transports, (b) they seem to fall into two broad groups, (c)
that will create two types of framing, (d) higher-level semantics
(patterns) will be dependent on these groups.
Can we give these groups names, define them speculatively, and sketch
requirements for framing in each case?
-Pieter
Martin Sustrik
> "I-D"?
"Internet drafts", transient documents managed by RFC editor. I-Ds are
versioned. If I-D is not updated in 6 months, it expires.
> You mean an RFC? Yes, you would typically have transient work in
> progress, use cases, background material, etc. on a wiki, disposable
> discussion by email, and formal results published as stand-alone
> documents.
Use cases, background etc. are published as I-Ds as well. They often
make it even to RFC status.
Martin
Pieter Hintjens
> "Internet drafts", transient documents managed by RFC editor. I-Ds are
> versioned. If I-D is not updated in 6 months, it expires.
Don't want to be pedantic but it's perhaps better to avoid jargon, or
at least explain it. "Draft" or "proposal" is quite clear.
The BWTP (bidirectional web transport) wiki I showed as example has a
mix of semi-persistent knowledge and proposals. It did expire, but was
very useful for collaborating on the work.
If you'd like me to set-up a wiki, I can do that.
-Pieter
Martin Sustrik
> Don't want to be pedantic but it's perhaps better to avoid jargon, or
> at least explain it. "Draft" or "proposal" is quite clear.
There's education involved. Once we move to IETF we'll have to
understand the jargon :)
Btw, speaking of moving to IETF, we should aim at organising BoF ("birds
of feather" session, prerequisite for creating an IETF working group) as
soon as possible.
IETF 81 (July) is not reallistic IMO, but we can plan for either IETF 82
(November) or IETF 83 (March 2012). Given that IETF 82 happens in Taipei
and IETF 83 is located in Paris, I would personally prefer the latter.
> The BWTP (bidirectional web transport) wiki I showed as example has a
> mix of semi-persistent knowledge and proposals. It did expire, but was
> very useful for collaborating on the work.
>
> If you'd like me to set-up a wiki, I can do that.
I'll create a wiki under the related github project to keep everything
in one place.
Martin
Pieter Hintjens
> There's education involved. Once we move to IETF we'll have to understand
> the jargon :)
For sure, but it's wise to explain jargon and only use it when there's
no real alternative. Otherwise you make it harder for people to
participate. I've been on the IETF HyBi list for ages and they use the
term "draft", or sometimes "I-D draft-whatever".
> IETF 81 (July) is not reallistic IMO, but we can plan for either IETF 82
> (November) or IETF 83 (March 2012). Given that IETF 82 happens in Taipei and
> IETF 83 is located in Paris, I would personally prefer the latter.
March 2012 seems late. But Taipei is far for all of us based in
Europe, at least.
> I'll create a wiki under the related github project to keep everything in
> one place.
You'll hit the standard github problem that notifications do not work
sanely. Github "try to avoid email as much as possible", in their own
words. So wiki changes don't generate emails, meaning that you have to
manually tell people about changes. It's annoying and breaks the cycle
of collaboration.
-Pieter
Martin Sustrik
> March 2012 seems late. But Taipei is far for all of us based in
> Europe, at least.
Keep in mind that most people at IETF meetings are not freelancers of
hobbyists, they are paid by companies to take part. Thus, they have to
get an approval from their company to participate in the WG. Taking that
into account March 2012 seems almost too early.
In any case we should start approaching IETF community as soon as
possible...
> You'll hit the standard github problem that notifications do not work
> sanely. Github "try to avoid email as much as possible", in their own
> words. So wiki changes don't generate emails, meaning that you have to
> manually tell people about changes. It's annoying and breaks the cycle
> of collaboration.
If you want a wiki, feel free to create one. However, any output must in
the end be in I-D format.
Martin
Pieter Hintjens
> Keep in mind that most people at IETF meetings are not freelancers of
> hobbyists, they are paid by companies to take part. Thus, they have to get
> an approval from their company to participate in the WG. Taking that into
> account March 2012 seems almost too early.
:-) 10 months to get T&A approved seems a lot even for large firms.
> In any case we should start approaching IETF community as soon as
> possible...
Ack.
> If you want a wiki, feel free to create one. However, any output must in the
> end be in I-D format.
You mean as drafts? Sure, that's your job as editor :-)
Here's a wiki: http://scalability.wikidot.com/
It works like the 0MQ wiki, click to join, click to edit. Anyone who
edits a page automatically gets email notifications of changes to it.
-Pieter
Martin Sustrik
>> That's one disctinction, but there are lots of others: ordering guarantees,
>> reliability guarantees, unicast vs. multicast etc.
>
> How do these aspects concern framing, specifically? You contrasted two
> types of framing. I'd like to understand what specifically this means
> (and I'm referring to bits on the wire here, not use cases, and not
> higher-level semantics).
Take the 'offset' field as used say in 0MQ-over-PGM wire format. It's
there to account for late joiners. Thus it makes sense for UDP/IP
multicast, however, it's completely useless in DCCP-like scenarios.
> What emerges from this thread seems to be that (a) we have a lot of
> potential transports, (b) they seem to fall into two broad groups, (c)
> that will create two types of framing, (d) higher-level semantics
> (patterns) will be dependent on these groups.
>
> Can we give these groups names, define them speculatively, and sketch
> requirements for framing in each case?
My experience is that transports are so widely different in so many ways
that trying to sort them into disjunct groups is a wasted effort. You
could think of it as N-dimensional space of transports, but that's too
complex and pedantic to be of any practical use.
What we should do, IMO, is to take few well-known transports (say TCP,
SCTP, PGM, DCCP, WebSockets) and define the framing for those. That
could serve as a learn-by-example guide for defining any future framings
on top of new transport protocols.
In any case, the rule of the thumb should be "strive to preserve the
semantics of the underlying transport to the maximum possible extent."
If the underlying transport is unreliable, the SP framing layer should
keep it unreliable. If it's unordered, SP framing should not introduce
ordering. If it's connection-less we should not define connections on
top of it. Etc.
In other words, the framing layer should add minimum functionality,
necessary for messaging. Message delimitation (if not offered by
underlying protocol) is a nice example.
Martin
Martin Sustrik
> :-) 10 months to get T&A approved seems a lot even for large firms.
When you account for "selling it to the management" part, it's not that
much time :)
Martin
Pieter Hintjens
> In other words, the framing layer should add minimum functionality,
> necessary for messaging. Message delimitation (if not offered by underlying
> protocol) is a nice example.
OK, we now have a definition of "frame" and "message" that makes more
sense. The framing layer encodes/decodes messages into frames that
suit the transport layer. The interface to higher layer is "message".
The framing layer doesn't modify the transport's semantics for
reliability or ordering or anything else.
Right?
-Pieter
J. Andrew Rogers
>
>> As an observation, there does not seem to be many obvious advantages
>> to using UDP for gossip protocols; many of the important gossip
>> protocols (e.g. BGP4) run over TCP. Not that you can't run it over
>> UDP, just that many of the most successful applications of gossip
>> protocols don't seem to. I suppose some p2p apps might rely on
>> gossip-like protocols for UDP.
>
> Feels like you have much broader knowledge of gossip-based
> protocols. I'd be very thankful if you could point out the important
> gossip protocols and their successful applications you are
> mentioning.
Nah, I learned the old fashioned way. I used to work with and design
low-level network protocols and moved on to distributed database
theory. I have a lot of exposure to the theory of robust routing
protocols. The mathematics surrounding it is interesting; there are
hard unsolved problems in this space that might not have a solution
and which have been resistant to attack.
Probably the most successful gossip protocol is BGP4 (the router
protocol); it scales to the entire Internet. The caveat is that BGP4
is pretty low traffic in practice but even so there are significant
issues with the size of the network metadata it manages. It has been
patched a few times against defects and attacks.
>> Tangentially, gossip protocols have scalability limitations accurately
>> documented in literature. They work very well for certain use cases
>> but there is a reason large clusters tend to manage their metadata
>> differently even though modern gossip protocols are (at least) 20
>> years old. At least in e.g. the BigData space almost no one uses
>> gossip protocols, Cassandra is the primary exception.
>
> Again, if you could give me a link to the literature documenting
> scalability limitations, I'd be very grateful. I'm researching
> this field currently and any helpful information will be appreciated. And
> btw Dynamo (and probably many clones of it) would be a secondary
> exception.
Probably the first official mention of the limitations of gossip
protocols are from the Dynamo literature. At some point, your metadata
traffic swamps most of the normal network traffic.
There are two problems: frequency of updates and the size of the
global state. IP routing protocols never had the former problem
because networks do not change that often but the latter became a
large problem, particularly with IPv6. It consumes an inordinate
amount of system resources. Distributed databases tend to have the
opposite problem, moderate global state and frequent updates that have
a hard time propagating on active clusters.
>> If p2p is more important than scale then gossip is the way to go. The
>> caveat is that there is (currently) no math for robust decentralized
>> protocols; it is arguably one of the more important unsolved problems
>> in the theory of how one routes a network. Provably robust p2p systems
>> all have a central actor buried in them somewhere, even if not
>> obvious. It is one of the reasons p2p has had a hard time establishing
>> itself -- too easy to attack.
>
> Please mention the names of those provably robust p2p systems
> - I seem to have not enough theoretical knowledge to get your point
> w/o concrete examples.
That was my point, it is not possible to given current mathematics on
robust Nash equilibria to design a P2P system that is fully
decentralized. Robustness requires some element of centralization but
that in turn creates a single point of failure. This affects things as
simple as making sure network resources are being used and balanced
optimally.
An elementary case is that while some strategies based on transaction
cost are provably optimal in a couple different scenarios, they
require a central clearinghouse for the transactions.
> Well, I wasn't saying that UDP is the (only) right way to implement
> gossip-style
> high scale communications. What I was saying was that if I try to use UDP
> for this,
> such usage would differ from use cases Martin mentioned. The closest one
> would
> probably be the UDP/IP broadcast/multicast.
Right. Make no mistake, I have a weird attraction to UDP as a
foundation for protocols and have implemented many protocols that used
it. It is more that I am begrudgingly admitting that UDP does not
justify the investment in most cases even when I want it to.
--
J. Andrew Rogers
brugeman
brugeman
Andrew, thank you for quite a lesson. Researching a field, listen to someone who talks not only pros but also cons :)
On the gossiping part of the story - in my own use case I have small global state and small update rate, so I hope it'll work.
On UDP - I have to admit my experience using it seems to be much less than yours, hope one day I'll make my knowledge deeper.
Thank you once more, Andrew.
Artur
Martin Sustrik
> I think you are on the right track. Many papers on this topic don't
> mention any specific transport. Others mention "lightweight transport
> protocol", with UDP as an example in parenthesis.
Thanks for the detailed explanation.
So what we can do, IMO, is not to define any specific framing for UDP at
the moment, mention the different semantics required by different use
cases (multicast, DCCP, UDT, gossip) and put it in "future work" section.
Martin