Semi-Reliable UDP (revised) specs
Raphael Manfredi <[email protected]> Sun, 07 Oct 2012 20:42:23 +0200
| Newsgroups | gmane.network.gnutella.devel |
|---|---|
| Organization | Home, Grenoble, France |
| Message-ID | <[email protected]> |
--V3OuhCkq1Ape4I22fitsGXbIUd4kd1DyrpifcJn
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Here are revised specs corresponding to what has been implemented in
gtk-gnutella.
Raphael
------------------------------------------------------------------------
Gnutella Semi-Reliable UDP
Raphael Manfredi
<[email protected]>
September 23rd, 2012
October, 7th, 2012
1. OVERVIEW
The following specifications document a semi-reliable protocol over UDP to
allow Gnutella servents to exchange "important" information that would be
wasteful if lost along the way.
The architecture fully follows the so-called "G2 UDP Transceiver" proposal,
with two important changes:
- The tag is "GTA" to stand for Gnutella.
- The architecture of acknowledgments was improved for efficiency.
This document fully specifies the protocol but reuses most of the existing
G2 specifications, because they are good and need not be amended. It however
only targets Gnutella.
The usage of the semi-reliable UDP layer in Gnutella will be for the delivery
of query hits over UDP, provided the querying party indicated support for
this semi-reliable UDP layer, of course (otherwise the reply would not be
properly understood).
Section 2 is a mere cut-and-paste of the original G2 specifications, slighly
adapted for Gnutella. My additions have been clearly flagged out.
2. ARCHITECTURE
2.1 Header
A small signature identifies the packet as a Gnutella semi-reliable UDP
datagram. This allows the same port to be used for receiving UDP traffic
for other protocols if desired, and offers some simple protection against
random, unexpected traffic.
A content code identifies the payload as a Gnutella packet message,
allowing future protocols to be added within the same reliability layer if
desired. Flags allow additional attributes to be specified, such as inline
stateless compression of the payload (which is a required feature).
The header has a fixed size of 8 bytes, and is architected as follows:
0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7| Byte
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| idTag | nFlags | 0-3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| nSequence | nPart | nCount | 4-7
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The members of the structure are detailed below:
idTag - contains a three byte encoding protocol identifier, in this case
"GTA" for "GnuTellA". If this signature is not present the packet should
not be interpreted as a Gnutella reliability layer message.
nFlags - contains flags which modify the content of the packet. The low-order
nibble is reserved for critical flags: if one of these bits is set but
the decoding software does not understand the meaning, the packet must
be discarded. The high-order nibble is reserved for non-critical flags:
when set these bits may be interpreted, but an inability to interpret a
bit does not cause the packet to be discarded.
Currently defined flags are:
0x01 - Deflate
When the deflate bit is set, the entire payload is compressed with
the deflate algorithm. The compression method used is the Deflate
Compression Data Format (RFC 1951). On top of this compression a ZLIB
`wrapper' is applied (RFC 1950, ZLIB Compressed Data Format). The
ZLIB wrapper ensures packet integrity, among other things.
Note that the entire payload must be reassembled in the correct order
before it can be deflated if the packet was fragmented. Fragments are
not compressed separately!
0x02 - Acknowledge Me
When the acknowledge-me bit is set, the sender is expecting an
acknowledgement for this packet.
nSequence - contains the sequence number of the packet. This sequence
number is unique to the sending host only. It is not unique to the pair
of the sending host and receiving host as in TCP, as there is no concept
of connection state. Sequence numbers on consecutive packets need not be
increasing (although that is convenient), they must only be different. If
a packet is fragmented, all of its fragments will have the same sequence
number. Byte order is unimportant here since this is an opaque ID.
nPart - contains the fragment part number (1 <= nPart <= nCount)
nCount - contains the number of fragment parts in this packet. On a
transmission, this value will be non-zero (all packets must have at least
one fragment). If nCount is zero, this is an acknowledgement (see below).
2.2 Fragmentation
Large packets must be fragmented before they can be sent through most network
interfaces. Different network media have different MTUs, and it is difficult
to predict what the lowest common size will be. Fragmentation and reassembly
is performed by the existing Internet protocols, however, there are two
important reasons why the reliability layer performs its own fragmentation:
Sockets implementations specify a maximum datagram size. This is adequate
for the vast majority of transmissions, but it is desirable to have
the transparent ability to send larger packets without worrying about
the host implementation.
When the Internet protocols fragment, a packet and one or more fragments
are lost, it may decide to discard the whole packet in an unreliable
datagram protocol. The Gnutella reliability layer can compensate by
retransmitting the whole packet, which would then be re-fragmented and
each fragment resent - however, this wastes the fragments that were
successfully received before. Managing fragmentation natively allows
this optimisation.
Each node determines its own MTU, often based on a best guess combined with
information from the host's sockets implementation. Packets exceeding this
size are fragmented into multiple datagrams of the appropriate size. Each
datagram has the same sequence number and the same fragment count (nCount),
but a different fragment number (nPart).
2.3 Transmission Process
When a packet is to be transmitted, the network layer must:
- Cache the payload
- Allocate a new locally and temporally unique sequence number
- Derive the appropriate number of fragments
- Queue the fragments for dispatch
- If the fragments do not need to be acknowledged, the packet can be
flushed now
The payload will generally be cached for an appropriate timeout period,
or until the data cache becomes full, at which time older payloads can be
discarded. Fragments are dispatched according to the dispatch algorithm of
choice, and the sender listens for acknowledgements.
When an acknowledgement is received:
- Lookup the sent packet by sequence number
- Mark the nPart fragment as received and cancel any retransmissions
of this part
- If all fragments have been acknowledged, flush this packet from
the cache
If a fragment has been transmitted but has not been acknowledged within the
timeout, it should be retransmitted. A finite number of retransmissions are
allowed before the packet as a whole expires, at which time it is assumed
that the packet was not received.
2.4 Reception Process
When a new datagram is received, the network layer must:
- If the acknowledge bit was set, send an acknowledge packet for this
sequence number and part number, with nCount set to zero (ACK)
- Lookup any existing packet by the sending IP and sequence number
- If there is no existing packet, create a new packet entry with the IP,
sequence number, fragment count and flags
- If there was an existing packet, make sure it is not marked as done -
if so, abort
- Add the transmitted fragment to the (new or old) packet entry
- If the packet now has all fragments, mark it as done, decode it
and pass it up to the application layer (who will not know it was
received via semi-reliable UDP).
- Leave the packet on the cache even if it was finished, in case any
parts are retransmitted
- Expire old packets from the receive buffer after a timeout, or if
the buffer is full
2.5 Dispatch Algorithm
Fragment datagrams need to be dispatched intelligently, to spread the load
on network resources and maximise the chance that the receiver will get
the message. To do this, the dispatch algorithm should take into account
several points:
- Prioritize acknowledgements.
- If fragments are waiting to be sent to a number of hosts, do not send
to the same host twice in a row. Alternating, or looping through the
target hosts achieves the same data rate locally, but spreads out the
load over downstream links.
- Do not exceed or approach the capacity of the local network
connection. If a host has a 128 kb/s outbound bandwidth, dispatching
32 KB of data in one second will likely cause massive packet loss,
leading to a retransmission.
- After considering the above points, prefer fragments that were queued
recently to older packets. A LIFO or stack type approach means that
even if a transmitter is becoming backed up, some fragments will get
there on time, while others will be delayed. A FIFO approach would mean
that a backed up host delivers every fragment late.
2.6 Parameters
[Settings have been changed for gkt-gnutella --RAM]
The recommended parameters for the reliability layer are as follows:
- Payload maximum size = 476 bytes (MTU for THIS layer)
- The fragment transmission timeout (ACK not received) is set to
5 secs for the first transmission, 10 secs for the second and 20
secs for the third and last attempt (exponential retry delay).
- The packet transmission timeout is set to 45 secs (larger than
5+10+20=35 in case each fragment is not immediately sent out).
The UDP/IP header being typically 28 bytes, it is best to limit the payload
of the messages to 476 bytes. That way, with the 8-byte header we're topping
plus the UDP/IP header, the whole message will not be greater than 512 bytes.
2.7 Performance Considerations
Relatively low-level network implementations such as this are reasonably
complicated, but must operate fast. It is desirable to avoid runtime
memory allocations in network code as much as possible, and particularly
at this level.
It should be noted that in almost all cases, transmissions to "untested"
nodes are single fragment. Replies on the other hand are often larger, and
may be deflated in many fragments. This is optimal, because attempting to
contact a node which may be unavailable, involves a retransmission of only
a single fragment.
Flow control is an important topic, however, it is handled at a higher layer.
The UDP reliability layer is only responsible for guaranteeing delivery of
selected datagrams.
Only critical transmissions whose reception cannot otherwise be inferred,
should have the acknowledge request bit set.
2.8 Extended Acknowledgments
[This part is my addition to the original G2 specifications --RAM]
Because acknowledgment messages can be lost in the way or arrive out of
order, it is best to include as much of the reception state as possible so
that the sending party can optimize retransmissions.
In order to do that, the following extensions to the original specifications
has been added by gtk-gnutella:
- Cumulative Acknowledgements: when the flag 0x10 is set, it tells the
other party that all the fragments up to nPart have been received.
- Extended Acknowledgments: when the flag 0x20 is set, it tells the
other party that an acknowledgment payload is present. It immediately
follows the header and is architected thusly:
0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7| Byte
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| nReceived | missingBits | 0-3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
nReceived is the total amount of parts successfully received so far.
missingBits is a bitfield that is read as a big-endian number and which
contains set bits (i.e. "1") for the parts still missing. The base part
number is normally 0, unless flag 0x10 was set, in which case the nPart
value indicates the base. The rule is then that if bit b is set, then the
fragment number b + base + 1 is still missing.
In the unlikely case where missingBits is too small to hold all the missing
parts, only the ones that can be represented are included, the nReceived
field being there to provide additional information.
Proper generation and parsing of the missingBits field is crucial, so to
remove any ambiguity, it is best to interpret missingBits as a number. Then
bit 0 is the bit corresponding to 2^0, bit n is the bit corresponding to 2^n.
In the above pictogram, bit 0 of missingBits is the 7th bit of the 3rd byte.
Bit 0 corresponds to fragment #1, unless the 0x10 flag was set. In that
case, if for instance nPart is 3, then it means fragments #1, #2 and #3
were already received. The base is therefore 3, and if bit 0 is set in
missingBits, it means fragment #4 (0 + 3 + 1) is still missing.
This extended acknowledgment lets the sending party optimize its
retransmissions even when some acknowledgments are lost.
Extended Acknowlegments are only useful when the total amount of fragments
is 3 or above. Indeed, with only 2 fragments, the Cumulative Acknowledgment
lets the receiving party know about the whole reception state.
When the amount of fragments is 3 or more and only a Cumulative Acknowledgment
is sent out, it implicitly denies reception of any other fragments. This
optimizes bandwidth since the 4 extra bytes sent out will only be required
for large messages (more than 2 fragments) in case fragments are received
out-of-order.
2.9 Delayed Acknowledgments
To maximize the usefulness of Cumulative Acknowledgments, the receiver can
delay its acknowledgments for a small period of time (100 ms, say) in the
hope that more fragments of the message will arrive meanwhile, provided the
message has more than 1 fragment naturally. When the 100 ms delay is expired,
it can then acknowledge everything it got so far. Performance will not be
impacted by this small delaying, but it can save a few acknowledgments for
larger messages.
This means a sender must use a transmission policy whereby it first sends
all the fragments of each message at once, then waits for acknowledgments or
timeouts before retransmitting the missing fragments. In other words, the
sender should not send a fragment, wait for its acknowledge before sending
the next one: this delays the reception of the entire message and it prevents
using the optimizations that extended acknowledgments bring!
3. SEMI-RELIABLE NEGOCIATION
Because legacy servents do not know about this new semi-reliable UDP layer,
it is important to negotiate its usage. This is done by stealing a bit in
the query flags.
Recall that the old "speed" field in queries (the first 2 bytes of the
Gnutella payload) have been re-architected circa 2003 as query flags:
the field is now read as a big-endian number, with bit 15 being set to
mark the field as being a "modern" one. Bits 0-8 were reserved during this
re-architecture to specify the maximum amount of hits desired.
So we're stealing bit 8 from this reserved set to flag support for the
semi-reliable UDP layer. If intepreted by legacy code, this will appear
to request at least 256 hits (I say "at least" because maybe we can steal
more bits in the future, but this bit will now always be set by gtk-gnutella
and hopefully other modern Gnutella servents). Therefore, since 256 hits
constitutes a lot of hits, it should not become a problem for anyone.
Here are the specs for this new bit:
#define QUERY_F_SR_UDP 0x0100 /* Accepts semi-reliable UDP */
To avoid ambiguity, here are the other existing flags for queries:
#define QUERY_F_MARK 0x8000 /* Field is special: not a speed */
#define QUERY_F_FIREWALLED 0x4000 /* Issuing servent is firewalled */
#define QUERY_F_XML 0x2000 /* Supports XML in result set */
#define QUERY_F_LEAF_GUIDED 0x1000 /* Leaf-guided query */
#define QUERY_F_GGEP_H 0x0800 /* Recipient understands GGEP "H" */
#define QUERY_F_OOB_REPLY 0x0400 /* Out-of-band reply possible */
#define QUERY_F_FW_TO_FW 0x0200 /* Can do fw to fw transfers */
GUESS servers and replying hosts can then peruse this information to send
hits and "OOB Reply Indication" messages (LIME/12) through the semi-reliable
layer instead of plain UDP, requesting acknowledgments. This helps ensure
the notification is not lost and that hits are subsequently reliably sent,
and possibly better compressed.
4. GNUTELLA VERSUS SEMI-RELIABLE TRAFFIC DISCRIMINATION
Because semi-reliable UDP traffic and regular Gnutella UDP traffic all happen
on the same socket, it is necessary to implement logic that will sort out
which is which.
When the GUID of messages is not starting with the "GTA" bytes, we know we
are not facing semi-reliable UDP traffic. When it starts with "GTA", it
could be valid Gnutella or semi-reliable UDP traffic, creating an ambiguity...
It is relatively easy to discriminate the traffic using simple logic. For
instance:
- Check the "size" field of the Gnutella header for consistency. If it is not
consistent with the length of the message, then the traffic is not Gnutella
and is therefore a semi-reliable UDP traffic.
- If the semi-reliable header is inconsistent (fragment part and count being
off, critical flags that we do not know about being set, sequence ID unknown
by the receiving side -- for followup fragments, of course), then we can
rule out semi-reliable UDP traffic.
The discriminating logic implemented by gtk-gnutella is more complex than that
and involves deeper inspection, but the above logic should be able to only
mis-classify 1 message out of 1 billion, which in practice should not create
problems.
Raphael
--V3OuhCkq1Ape4I22fitsGXbIUd4kd1DyrpifcJn
Content-Type: text/html; charset=US-ASCII
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
</head>
<body style="background-color: #fff;">
<span style="display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id="ygrp-mlmsg" style="position:relative;">
<div id="ygrp-msg" style="z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id="ygrp-text" >
<p>Here are revised specs corresponding to what has been implemented in<br>
gtk-gnutella.<br>
<br>
Raphael<br>
<br>
----------------------------------------------------------<br>
Gnutella Semi-Reliable UDP<br>
<br>
Raphael Manfredi<br>
<<a href="mailto:Raphael_Manfredi%40pobox.com">[email protected]</a>><br>
September 23rd, 2012<br>
October, 7th, 2012<br>
<br>
1. OVERVIEW<br>
<br>
The following specifications document a semi-reliable protocol over UDP to<br>
allow Gnutella servents to exchange "important" information that would be<br>
wasteful if lost along the way.<br>
<br>
The architecture fully follows the so-called "G2 UDP Transceiver" proposal,<br>
with two important changes:<br>
<br>
- The tag is "GTA" to stand for Gnutella.<br>
- The architecture of acknowledgments was improved for efficiency.<br>
<br>
This document fully specifies the protocol but reuses most of the existing<br>
G2 specifications, because they are good and need not be amended. It however<br>
only targets Gnutella.<br>
<br>
The usage of the semi-reliable UDP layer in Gnutella will be for the delivery<br>
of query hits over UDP, provided the querying party indicated support for<br>
this semi-reliable UDP layer, of course (otherwise the reply would not be<br>
properly understood).<br>
<br>
Section 2 is a mere cut-and-paste of the original G2 specifications, slighly<br>
adapted for Gnutella. My additions have been clearly flagged out.<br>
<br>
2. ARCHITECTURE<br>
<br>
2.1 Header<br>
<br>
A small signature identifies the packet as a Gnutella semi-reliable UDP<br>
datagram. This allows the same port to be used for receiving UDP traffic<br>
for other protocols if desired, and offers some simple protection against<br>
random, unexpected traffic.<br>
<br>
A content code identifies the payload as a Gnutella packet message,<br>
allowing future protocols to be added within the same reliability layer if<br>
desired. Flags allow additional attributes to be specified, such as inline<br>
stateless compression of the payload (which is a required feature).<br>
<br>
The header has a fixed size of 8 bytes, and is architected as follows:<br>
<br>
0 1 2 3<br>
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7| Byte<br>
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>
| idTag | nFlags | 0-3<br>
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>
| nSequence | nPart | nCount | 4-7<br>
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>
<br>
The members of the structure are detailed below:<br>
<br>
idTag - contains a three byte encoding protocol identifier, in this case<br>
"GTA" for "GnuTellA". If this signature is not present the packet should<br>
not be interpreted as a Gnutella reliability layer message.<br>
<br>
nFlags - contains flags which modify the content of the packet. The low-order<br>
nibble is reserved for critical flags: if one of these bits is set but<br>
the decoding software does not understand the meaning, the packet must<br>
be discarded. The high-order nibble is reserved for non-critical flags:<br>
when set these bits may be interpreted, but an inability to interpret a<br>
bit does not cause the packet to be discarded.<br>
<br>
Currently defined flags are:<br>
<br>
0x01 - Deflate <br>
<br>
When the deflate bit is set, the entire payload is compressed with<br>
the deflate algorithm. The compression method used is the Deflate<br>
Compression Data Format (RFC 1951). On top of this compression a ZLIB<br>
`wrapper' is applied (RFC 1950, ZLIB Compressed Data Format). The<br>
ZLIB wrapper ensures packet integrity, among other things.<br>
<br>
Note that the entire payload must be reassembled in the correct order<br>
before it can be deflated if the packet was fragmented. Fragments are<br>
not compressed separately!<br>
<br>
0x02 - Acknowledge Me <br>
<br>
When the acknowledge-me bit is set, the sender is expecting an<br>
acknowledgement for this packet.<br>
<br>
nSequence - contains the sequence number of the packet. This sequence<br>
number is unique to the sending host only. It is not unique to the pair<br>
of the sending host and receiving host as in TCP, as there is no concept<br>
of connection state. Sequence numbers on consecutive packets need not be<br>
increasing (although that is convenient), they must only be different. If<br>
a packet is fragmented, all of its fragments will have the same sequence<br>
number. Byte order is unimportant here since this is an opaque ID.<br>
<br>
nPart - contains the fragment part number (1 <= nPart <= nCount)<br>
<br>
nCount - contains the number of fragment parts in this packet. On a<br>
transmission, this value will be non-zero (all packets must have at least<br>
one fragment). If nCount is zero, this is an acknowledgement (see below).<br>
<br>
2.2 Fragmentation<br>
<br>
Large packets must be fragmented before they can be sent through most network<br>
interfaces. Different network media have different MTUs, and it is difficult<br>
to predict what the lowest common size will be. Fragmentation and reassembly<br>
is performed by the existing Internet protocols, however, there are two<br>
important reasons why the reliability layer performs its own fragmentation:<br>
<br>
Sockets implementations specify a maximum datagram size. This is adequate<br>
for the vast majority of transmissions, but it is desirable to have<br>
the transparent ability to send larger packets without worrying about<br>
the host implementation.<br>
<br>
When the Internet protocols fragment, a packet and one or more fragments<br>
are lost, it may decide to discard the whole packet in an unreliable<br>
datagram protocol. The Gnutella reliability layer can compensate by<br>
retransmitting the whole packet, which would then be re-fragmented and<br>
each fragment resent - however, this wastes the fragments that were<br>
successfully received before. Managing fragmentation natively allows<br>
this optimisation.<br>
<br>
Each node determines its own MTU, often based on a best guess combined with<br>
information from the host's sockets implementation. Packets exceeding this<br>
size are fragmented into multiple datagrams of the appropriate size. Each<br>
datagram has the same sequence number and the same fragment count (nCount),<br>
but a different fragment number (nPart).<br>
<br>
2.3 Transmission Process<br>
<br>
When a packet is to be transmitted, the network layer must:<br>
<br>
- Cache the payload<br>
<br>
- Allocate a new locally and temporally unique sequence number<br>
<br>
- Derive the appropriate number of fragments<br>
<br>
- Queue the fragments for dispatch<br>
<br>
- If the fragments do not need to be acknowledged, the packet can be<br>
flushed now<br>
<br>
The payload will generally be cached for an appropriate timeout period,<br>
or until the data cache becomes full, at which time older payloads can be<br>
discarded. Fragments are dispatched according to the dispatch algorithm of<br>
choice, and the sender listens for acknowledgements.<br>
<br>
When an acknowledgement is received:<br>
<br>
- Lookup the sent packet by sequence number<br>
<br>
- Mark the nPart fragment as received and cancel any retransmissions<br>
of this part<br>
<br>
- If all fragments have been acknowledged, flush this packet from<br>
the cache<br>
<br>
If a fragment has been transmitted but has not been acknowledged within the<br>
timeout, it should be retransmitted. A finite number of retransmissions are<br>
allowed before the packet as a whole expires, at which time it is assumed<br>
that the packet was not received.<br>
<br>
2.4 Reception Process<br>
<br>
When a new datagram is received, the network layer must:<br>
<br>
- If the acknowledge bit was set, send an acknowledge packet for this<br>
sequence number and part number, with nCount set to zero (ACK)<br>
<br>
- Lookup any existing packet by the sending IP and sequence number<br>
<br>
- If there is no existing packet, create a new packet entry with the IP,<br>
sequence number, fragment count and flags<br>
<br>
- If there was an existing packet, make sure it is not marked as done -<br>
if so, abort<br>
<br>
- Add the transmitted fragment to the (new or old) packet entry<br>
<br>
- If the packet now has all fragments, mark it as done, decode it<br>
and pass it up to the application layer (who will not know it was<br>
received via semi-reliable UDP).<br>
<br>
- Leave the packet on the cache even if it was finished, in case any<br>
parts are retransmitted<br>
<br>
- Expire old packets from the receive buffer after a timeout, or if<br>
the buffer is full<br>
<br>
2.5 Dispatch Algorithm<br>
<br>
Fragment datagrams need to be dispatched intelligently, to spread the load<br>
on network resources and maximise the chance that the receiver will get<br>
the message. To do this, the dispatch algorithm should take into account<br>
several points:<br>
<br>
- Prioritize acknowledgements.<br>
<br>
- If fragments are waiting to be sent to a number of hosts, do not send<br>
to the same host twice in a row. Alternating, or looping through the<br>
target hosts achieves the same data rate locally, but spreads out the<br>
load over downstream links.<br>
<br>
- Do not exceed or approach the capacity of the local network<br>
connection. If a host has a 128 kb/s outbound bandwidth, dispatching<br>
32 KB of data in one second will likely cause massive packet loss,<br>
leading to a retransmission.<br>
<br>
- After considering the above points, prefer fragments that were queued<br>
recently to older packets. A LIFO or stack type approach means that<br>
even if a transmitter is becoming backed up, some fragments will get<br>
there on time, while others will be delayed. A FIFO approach would mean<br>
that a backed up host delivers every fragment late.<br>
<br>
2.6 Parameters<br>
<br>
[Settings have been changed for gkt-gnutella --RAM]<br>
<br>
The recommended parameters for the reliability layer are as follows:<br>
<br>
- Payload maximum size = 476 bytes (MTU for THIS layer)<br>
<br>
- The fragment transmission timeout (ACK not received) is set to<br>
5 secs for the first transmission, 10 secs for the second and 20<br>
secs for the third and last attempt (exponential retry delay).<br>
<br>
- The packet transmission timeout is set to 45 secs (larger than<br>
5+10+20=35 in case each fragment is not immediately sent out).<br>
<br>
The UDP/IP header being typically 28 bytes, it is best to limit the payload<br>
of the messages to 476 bytes. That way, with the 8-byte header we're topping<br>
plus the UDP/IP header, the whole message will not be greater than 512 bytes.<br>
<br>
2.7 Performance Considerations<br>
<br>
Relatively low-level network implementations such as this are reasonably<br>
complicated, but must operate fast. It is desirable to avoid runtime<br>
memory allocations in network code as much as possible, and particularly<br>
at this level.<br>
<br>
It should be noted that in almost all cases, transmissions to "untested"<br>
nodes are single fragment. Replies on the other hand are often larger, and<br>
may be deflated in many fragments. This is optimal, because attempting to<br>
contact a node which may be unavailable, involves a retransmission of only<br>
a single fragment.<br>
<br>
Flow control is an important topic, however, it is handled at a higher layer.<br>
The UDP reliability layer is only responsible for guaranteeing delivery of<br>
selected datagrams.<br>
<br>
Only critical transmissions whose reception cannot otherwise be inferred,<br>
should have the acknowledge request bit set.<br>
<br>
2.8 Extended Acknowledgments<br>
<br>
[This part is my addition to the original G2 specifications --RAM]<br>
<br>
Because acknowledgment messages can be lost in the way or arrive out of<br>
order, it is best to include as much of the reception state as possible so<br>
that the sending party can optimize retransmissions.<br>
<br>
In order to do that, the following extensions to the original specifications<br>
has been added by gtk-gnutella:<br>
<br>
- Cumulative Acknowledgements: when the flag 0x10 is set, it tells the<br>
other party that all the fragments up to nPart have been received.<br>
<br>
- Extended Acknowledgments: when the flag 0x20 is set, it tells the<br>
other party that an acknowledgment payload is present. It immediately<br>
follows the header and is architected thusly:<br>
<br>
0 1 2 3<br>
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7| Byte<br>
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>
| nReceived | missingBits | 0-3<br>
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>
<br>
nReceived is the total amount of parts successfully received so far.<br>
<br>
missingBits is a bitfield that is read as a big-endian number and which<br>
contains set bits (i.e. "1") for the parts still missing. The base part<br>
number is normally 0, unless flag 0x10 was set, in which case the nPart<br>
value indicates the base. The rule is then that if bit b is set, then the<br>
fragment number b + base + 1 is still missing.<br>
<br>
In the unlikely case where missingBits is too small to hold all the missing<br>
parts, only the ones that can be represented are included, the nReceived<br>
field being there to provide additional information.<br>
<br>
Proper generation and parsing of the missingBits field is crucial, so to<br>
remove any ambiguity, it is best to interpret missingBits as a number. Then<br>
bit 0 is the bit corresponding to 2^0, bit n is the bit corresponding to 2^n.<br>
In the above pictogram, bit 0 of missingBits is the 7th bit of the 3rd byte.<br>
<br>
Bit 0 corresponds to fragment #1, unless the 0x10 flag was set. In that<br>
case, if for instance nPart is 3, then it means fragments #1, #2 and #3<br>
were already received. The base is therefore 3, and if bit 0 is set in<br>
missingBits, it means fragment #4 (0 + 3 + 1) is still missing.<br>
<br>
This extended acknowledgment lets the sending party optimize its<br>
retransmissions even when some acknowledgments are lost.<br>
<br>
Extended Acknowlegments are only useful when the total amount of fragments<br>
is 3 or above. Indeed, with only 2 fragments, the Cumulative Acknowledgment<br>
lets the receiving party know about the whole reception state.<br>
<br>
When the amount of fragments is 3 or more and only a Cumulative Acknowledgment<br>
is sent out, it implicitly denies reception of any other fragments. This<br>
optimizes bandwidth since the 4 extra bytes sent out will only be required<br>
for large messages (more than 2 fragments) in case fragments are received<br>
out-of-order.<br>
<br>
2.9 Delayed Acknowledgments<br>
<br>
To maximize the usefulness of Cumulative Acknowledgments, the receiver can<br>
delay its acknowledgments for a small period of time (100 ms, say) in the<br>
hope that more fragments of the message will arrive meanwhile, provided the<br>
message has more than 1 fragment naturally. When the 100 ms delay is expired,<br>
it can then acknowledge everything it got so far. Performance will not be<br>
impacted by this small delaying, but it can save a few acknowledgments for<br>
larger messages.<br>
<br>
This means a sender must use a transmission policy whereby it first sends<br>
all the fragments of each message at once, then waits for acknowledgments or<br>
timeouts before retransmitting the missing fragments. In other words, the<br>
sender should not send a fragment, wait for its acknowledge before sending<br>
the next one: this delays the reception of the entire message and it prevents<br>
using the optimizations that extended acknowledgments bring!<br>
<br>
3. SEMI-RELIABLE NEGOCIATION<br>
<br>
Because legacy servents do not know about this new semi-reliable UDP layer,<br>
it is important to negotiate its usage. This is done by stealing a bit in<br>
the query flags.<br>
<br>
Recall that the old "speed" field in queries (the first 2 bytes of the<br>
Gnutella payload) have been re-architected circa 2003 as query flags:<br>
the field is now read as a big-endian number, with bit 15 being set to<br>
mark the field as being a "modern" one. Bits 0-8 were reserved during this<br>
re-architecture to specify the maximum amount of hits desired.<br>
<br>
So we're stealing bit 8 from this reserved set to flag support for the<br>
semi-reliable UDP layer. If intepreted by legacy code, this will appear<br>
to request at least 256 hits (I say "at least" because maybe we can steal<br>
more bits in the future, but this bit will now always be set by gtk-gnutella<br>
and hopefully other modern Gnutella servents). Therefore, since 256 hits<br>
constitutes a lot of hits, it should not become a problem for anyone.<br>
<br>
Here are the specs for this new bit:<br>
<br>
#define QUERY_F_SR_UDP 0x0100 /* Accepts semi-reliable UDP */<br>
<br>
To avoid ambiguity, here are the other existing flags for queries:<br>
<br>
#define QUERY_F_MARK 0x8000 /* Field is special: not a speed */<br>
#define QUERY_F_FIREWALLED 0x4000 /* Issuing servent is firewalled */<br>
#define QUERY_F_XML 0x2000 /* Supports XML in result set */<br>
#define QUERY_F_LEAF_GUIDED 0x1000 /* Leaf-guided query */<br>
#define QUERY_F_GGEP_H 0x0800 /* Recipient understands GGEP "H" */<br>
#define QUERY_F_OOB_REPLY 0x0400 /* Out-of-band reply possible */<br>
#define QUERY_F_FW_TO_FW 0x0200 /* Can do fw to fw transfers */<br>
<br>
GUESS servers and replying hosts can then peruse this information to send<br>
hits and "OOB Reply Indication" messages (LIME/12) through the semi-reliable<br>
layer instead of plain UDP, requesting acknowledgments. This helps ensure<br>
the notification is not lost and that hits are subsequently reliably sent,<br>
and possibly better compressed.<br>
<br>
4. GNUTELLA VERSUS SEMI-RELIABLE TRAFFIC DISCRIMINATION<br>
<br>
Because semi-reliable UDP traffic and regular Gnutella UDP traffic all happen<br>
on the same socket, it is necessary to implement logic that will sort out<br>
which is which.<br>
<br>
When the GUID of messages is not starting with the "GTA" bytes, we know we<br>
are not facing semi-reliable UDP traffic. When it starts with "GTA", it<br>
could be valid Gnutella or semi-reliable UDP traffic, creating an ambiguity...<br>
<br>
It is relatively easy to discriminate the traffic using simple logic. For<br>
instance:<br>
<br>
- Check the "size" field of the Gnutella header for consistency. If it is not<br>
consistent with the length of the message, then the traffic is not Gnutella<br>
and is therefore a semi-reliable UDP traffic.<br>
<br>
- If the semi-reliable header is inconsistent (fragment part and count being<br>
off, critical flags that we do not know about being set, sequence ID unknown<br>
by the receiving side -- for followup fragments, of course), then we can<br>
rule out semi-reliable UDP traffic.<br>
<br>
The discriminating logic implemented by gtk-gnutella is more complex than that<br>
and involves deeper inspection, but the above logic should be able to only<br>
mis-classify 1 message out of 1 billion, which in practice should not create<br>
problems.<br>
<br>
Raphael<br>
</p>
</div>
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style="color: #fff; height: 0;">__._,_.___</div>
<table cellspacing=4px style="margin-top: 20px; margin-bottom: 10px;">
<tbody>
<tr>
<td style="font-size: 12px; font-family: arial; font-weight: bold; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA " >
<a style="text-decoration: none; color: #2D50FD" href="http://groups.yahoo.com/group/the_gdf/post;_ylc=X3oDMTJxcWJuOGJ0BF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBG1zZ0lkAzIzODA2BHNlYwNmdHIEc2xrA3JwbHkEc3RpbWUDMTM0OTYzNTM1NA--?act=reply&messageNum=23806">Reply via web post</a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="mailto:[email protected]?subject=Re%3A%20Semi-Reliable%20UDP%20%28revised%29%20specs" style="text-decoration: none; color: #2D50FD;">
Reply to sender </a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; ">
<a href="mailto:[email protected]?subject=Re%3A%20Semi-Reliable%20UDP%20%28revised%29%20specs" style="text-decoration: none; color: #2D50FD">
Reply to group </a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="http://groups.yahoo.com/group/the_gdf/post;_ylc=X3oDMTJlbjV2ZTZtBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0OTYzNTM1NA--" style="text-decoration: none; color: #2D50FD">Start a New Topic</a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #2D50FD; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="http://groups.yahoo.com/group/the_gdf/message/23806;_ylc=X3oDMTM2YmZ2bjE0BF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBG1zZ0lkAzIzODA2BHNlYwNmdHIEc2xrA3Z0cGMEc3RpbWUDMTM0OTYzNTM1NAR0cGNJZAMyMzgwNg--" style="text-decoration: none; color: #2D50FD;">Messages in this topic</a>
(1)
</td>
</tr>
</tbody>
</table>
<!------- Start Nav Bar ------>
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-vital" style="background-color: #f2f2f2; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span>
<ul style="list-style-type: none; margin: 0; padding: 0; display: inline;">
<li style="border-right: 1px solid #000; font-weight: 700; display: inline; padding: 0 5px; margin-left: 0;">
<span class="cat"><a href="http://groups.yahoo.com/group/the_gdf/members;_ylc=X3oDMTJmZ2gzN2RvBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDk2MzUzNTQ-?o=6" style="text-decoration: none;">New Members</a></span>
<span class="ct" style="color: #ff7900;">1</span>
</li>
</ul>
<div style="clear: both; padding-top: 2px; color: #1e66ae;">
<a href="http://groups.yahoo.com/group/the_gdf;_ylc=X3oDMTJlOXU4MTRtBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM0OTYzNTM1NA--" style="text-decoration: none;">Visit Your Group</a>
</div>
</div>
<div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;">
<a href="http://groups.yahoo.com/;_ylc=X3oDMTJkZDJoa20wBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzQ5NjM1MzU0" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a>
<div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a> • <a href="mailto:[email protected]?subject=Feedback on the redesigned individual mail v1" style="text-decoration: none;">Send us Feedback </a></div>
</div>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id="ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style="clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src="http://geo.yahoo.com/serv?s=97359714/grpId=2684253/grpspId=1705016061/msgId=23806/stime=1349635354/nc1=5028928/nc2=5741391/nc3=5758222" width="1" height="1"> <br>
<div style="color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type="text/css">
<!--
#ygrp-mkp {
border: 1px solid #d8d8d8;
font-family: Arial;
margin: 10px 0;
padding: 0 10px;
}
#ygrp-mkp hr {
border: 1px solid #d8d8d8;
}
#ygrp-mkp #hd {
color: #628c2a;
font-size: 85%;
font-weight: 700;
line-height: 122%;
margin: 10px 0;
}
#ygrp-mkp #ads {
margin-bottom: 10px;
}
#ygrp-mkp .ad {
padding: 0 0;
}
#ygrp-mkp .ad p {
margin: 0;
}
#ygrp-mkp .ad a {
color: #0000ff;
text-decoration: none;
}
#ygrp-sponsor #ygrp-lc {
font-family: Arial;
}
#ygrp-sponsor #ygrp-lc #hd {
margin: 10px 0px;
font-weight: 700;
font-size: 78%;
line-height: 122%;
}
#ygrp-sponsor #ygrp-lc .ad {
margin-bottom: 10px;
padding: 0 0;
}
#actions {
font-family: Verdana;
font-size: 11px;
padding: 10px 0;
}
#activity {
background-color: #e0ecee;
float: left;
font-family: Verdana;
font-size: 10px;
padding: 10px;
}
#activity span {
font-weight: 700;
}
#activity span:first-child {
text-transform: uppercase;
}
#activity span a {
color: #5085b6;
text-decoration: none;
}
#activity span span {
color: #ff7900;
}
#activity span .underline {
text-decoration: underline;
}
.attach {
clear: both;
display: table;
font-family: Arial;
font-size: 12px;
padding: 10px 0;
width: 400px;
}
.attach div a {
text-decoration: none;
}
.attach img {
border: none;
padding-right: 5px;
}
.attach label {
display: block;
margin-bottom: 5px;
}
.attach label a {
text-decoration: none;
}
blockquote {
margin: 0 0 0 4px;
}
.bold {
font-family: Arial;
font-size: 13px;
font-weight: 700;
}
.bold a {
text-decoration: none;
}
dd.last p a {
font-family: Verdana;
font-weight: 700;
}
dd.last p span {
margin-right: 10px;
font-family: Verdana;
font-weight: 700;
}
dd.last p span.yshortcuts {
margin-right: 0;
}
div.attach-table div div a {
text-decoration: none;
}
div.attach-table {
width: 400px;
}
div.file-title a, div.file-title a:active, div.file-title a:hover, div.file-title a:visited {
text-decoration: none;
}
div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div.photo-title a:visited {
text-decoration: none;
}
div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts {
font-family: Verdana;
font-size: 10px;
font-weight: normal;
}
.green {
color: #628c2a;
}
.MsoNormal {
margin: 0 0 0 0;
}
o {
font-size: 0;
}
#photos div {
float: left;
width: 72px;
}
#photos div div {
border: 1px solid #666666;
height: 62px;
overflow: hidden;
width: 62px;
}
#photos div label {
color: #666666;
font-size: 10px;
overflow: hidden;
text-align: center;
white-space: nowrap;
width: 64px;
}
#reco-category {
font-size: 77%;
}
#reco-desc {
font-size: 77%;
}
.replbq {
margin: 4px;
}
#ygrp-actbar div a:first-child {
/* border-right: 0px solid #000;*/
margin-right: 2px;
padding-right: 5px;
}
#ygrp-mlmsg {
font-size: 13px;
font-family: Arial, helvetica,clean, sans-serif;
*font-size: small;
*font: x-small;
}
#ygrp-mlmsg table {
font-size: inherit;
font: 100%;
}
#ygrp-mlmsg select, input, textarea {
font: 99% Arial, Helvetica, clean, sans-serif;
}
#ygrp-mlmsg pre, code {
font:115% monospace;
*font-size:100%;
}
#ygrp-mlmsg * {
line-height: 1.22em;
}
#ygrp-mlmsg #logo {
padding-bottom: 10px;
}
#ygrp-msg p a {
font-family: Verdana;
}
#ygrp-msg p#attach-count span {
color: #1E66AE;
font-weight: 700;
}
#ygrp-reco #reco-head {
color: #ff7900;
font-weight: 700;
}
#ygrp-reco {
margin-bottom: 20px;
padding: 0px;
}
#ygrp-sponsor #ov li a {
font-size: 130%;
text-decoration: none;
}
#ygrp-sponsor #ov li {
font-size: 77%;
list-style-type: square;
padding: 6px 0;
}
#ygrp-sponsor #ov ul {
margin: 0;
padding: 0 0 0 8px;
}
#ygrp-text {
font-family: Georgia;
}
#ygrp-text p {
margin: 0 0 1em 0;
}
#ygrp-text tt {
font-size: 120%;
}
#ygrp-vital ul li:last-child {
border-right: none !important;
}
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--V3OuhCkq1Ape4I22fitsGXbIUd4kd1DyrpifcJn--