Scalable Semi-Reliable Datagram Protocol
The Goal: have a high-quality, bandwidth friendly Internet radio.
Using TCP for broadcasts is icky, because it chews up kernel resources
for every open socket. Its not really scalable. Besides, if TCP runs
behind the rate of audio delivery ... its useless, because we don't need
old stale audio packets. Packet delivery needs to be reliable only if
if the packets are timely. If they are not timely, they are useless.
Using UDP is better, but packets get lost, and this leads to audio
dropouts. A good radio needs a UDP-based protocol that is reliable
for "recent" packets, but doesn't attempt to retransmit very old,
stale packets.
Implementation
The implementation of such a thing is straightforward and fairly simple.
Packets are given sequence numbers. The radio transmitter keeps a
buffer of the most recent 20-odd seconds worth of packets (for 8K ulaw,
thats about 200KBytes of packets). The radio receiver plays about 20
seconds behind the transmitter. It keeps a buffer of packets that
arrived by UDP. If it sees holes in the buffer, it re-requests those
packets from the transmitter. It either gets them, or it doesn't.
If it doesn't get all th packets it needs in 20 seconds ... tough. Those
packets are simply too old.
The careful reader will note that this scheme involves NACK's, and thus,
anti-congestion (anti-anti-congestion?) control. The harm of this
congestion generating algorithm can be minimized to a degree by having
the transmitter inform the receiver what it's buffer size is. That way,
the receiver won't go around asking for packets that the transmitter has
already thrown away.
Implementers of Internet telephones will be disappointed: this protocol
does nothing for them. The quality of this algorithm depends on the
assumptions that its OK for the radio receiver to be 5 or 10 or 20
seconds behind the transmitter.
More Congestion Control
Every receiver can be allocated a "Nack quota". Once a receiver runs
out of NACK's, it agrees not to transmit any more. Transmitters renew
receiver's nack quotas from time to time. On a congested link, the
receiver runs out of its quota, and stops sending NACK's.
Two questions suggest themselves: how should transmitters
allocate quotes? Constant number, or a sliding scale? If a transmitter
increases nack quotas when it gets fewer NACK's. a pathological situation
could arise ...
How should receivers conserve their precious nacks?
With this scheme, receivers throttle back on the number of NACK's.
Transmitters, of course, continue to blast full-ahead, damned the
congestion ...
Congestion on Multi-cast Links
Nack quotas also offer a mechanism whereby congested multi-cast links can
participate in congestion control. A link can snoop a receiver's nack
quota, and add it to it's own quota. A link may want to derate its
total quota by some factor.
Congestion due to an excessive number of transmitters on a link can be
regulated by an entirely independent mechanism, following more
traditional approaches.
Related References
Has anyone heard of anything like this? I am looking for something
like this for Linux, and am toying with idea of implementing it if I
can't find it.
I've heard of several similar things:
- RMP
- Reliable
Multi-Cast Protocol. Linux source code is available.
- SRM
-
Scalable Reliable Multi-cast. This is interesting, but ...
for radio broadcast purposes, this is overkill.
- SRTP
-
Selectively Reliable Transport Protocol. It seems that SRTP
mode 1 is close to what an internet radio needs, but not quite ...
- LRMP
-
LRMP: the Light-weight Reliable Multi-cast Protocol
Nice discussion of similar ideas ...
- SACK TCP
- Selective
Acknowledgment TCP is a mechanism whereby specific packets are
identified in the ACK messages. This allows "holes" between
received packets to be filled in, instead of reseting sequence
numbers to just before the first hole.
SACK is available on
FreeBSD, not yet on Linux ...
- SRDP
- Scalable Reliable Datagram Protocol, coming from Worlds Inc
as a proposal to help with VRML. I think Mitra helped get
the spec published. The VRML group discussed DIS protocols
at length, SRDP was one of the resulting proposals.
I have lost the reference ... can anyone help?
- Other Links
-
other links
Linas Vepstas linas@linas.org 21 March 1997
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.1;
with no Invariant Sections, with no Front-Cover Texts, and with no
Back-Cover Texts. A copy of the license is included at the URL
http://www.linas.org/fdl.html,
the web page titled
"GNU Free Documentation License".
Return to:
[Linux Enterprise Computing]
[Linas' Home Page]