[p2p-hackers] Simple reliable UDP data transfer

[Ian Clarke]

On 19 Nov 2004, at 21:50, Bryan Turner wrote:
> [Sorry for the length, I got to rambling a bit..]

Not at all, this is fascinating - and given that P2P applications are 
likely to form an increasing proportion of Internet traffic, it is 
essential that the protocols used account for the lessons of the past.

> Not to hijack the thread, here's my input on reliable-UDP..

Interesting, although it seems like it might be overkill for what I 
need :-/

Here is what I am doing now, I was working on the assumption that I 
would need to revamp it, but after testing for a few days, I'm 
surprised by how well it is working, so perhaps that won't be 
necessary.  Comments (and/or shrieks of abject horror) are welcome:

The 256k block is split into 256 packets which are transmitted at 
regular intervals determined by our upstream bandwidth limit which we 
adjust on the fly (see below).  If two or more blocks are being 
transmitted at once, then they share the available upstream bandwidth 
(ie. for 2 the interval for each is doubled).  The transmitter will 
always transmit the lowest untransmitted block next.

Once every few packets (I use 64) the sender sends a check message 
which contains a bit array indicating which packets it has sent.  The 
receiver, on getting this, checks to see that the transmitted blocks 
correspond to what it has received, and if not, sends a message to the 
sender indicating which blocks are missing.  The sender marks these as 
untransmitted and thus resends them at the next interval.  On 
completion the sender sends a check message and awaits either a 
completed message from the receiver, or another retransmission request. 
  These are resent periodically if sender or receiver don't hear from 
each-other to account for the possibility that they are dropped.

Right now the upstream bandwidth limit is fixed, but if I decide to 
stick with this algorithm I will adjust it based on round-trip time.  
The way I do this is the question mark right now, but essentially I was 
thinking that I would set a RTT threshold designed to be triggered when 
the user's last-mile connection starts to buffer packets.  At this 
point I use an additive increase multiplicative decrease approach using 
constants that achieve TCP friendliness as described in this paper 
(look around page 13):

    http://www.cs.utexas.edu/users/lam/Vita/Misc/YangLam00tr.pdf

Specifically:

public static final float PACKET_DROP_DECREASE_MULTIPLE = 0.875f;
public static final float PACKET_TRANSMIT_INCREMENT = (4 * (1 - 
(PACKET_DROP_DECREASE_MULTIPLE *
			PACKET_DROP_DECREASE_MULTIPLE))) / 3;

Anyway, that is the rough outline, comments are appreciated.

Incidentally,  the fruits of this labour will be open source, you can 
see what I have done so-far at http://dijjer.org/.  You can browse the 
messy and so-far uncommented code here:

    http://cvs.sourceforge.net/viewcvs.py/dijjer/Dijjer/

(Don't worry, I will go through, tidy up, and comment it in due course).

I'm trying to maintain a low profile until the code is reasonably 
stable, but that can create a chicken and egg issue because its hard to 
know that it is stable until it has been tested on a reasonably large 
scale.

Ian.

--
Founder, The Freenet Project	http://freenetproject.org/
CEO, Cematics Ltd				http://cematics.com/
Personal Blog					http://locut.us/~ian/blog/