[p2p-hackers] UDP file transfer protocol peer review

[David Barrett]

In light of of my previous question on link speed identification of a 
UDP file-transfer protocol, I'd like to share my overall protocol and 
ask for feedback on how to improve it.  Here's a (slightly long) 
overview of the protocol, followed by specific questions at the end:


--- Rationale ---
I'm using SIP and RTP as the basis for a P2P system that includes (among 
other things) VoIP and a file transfer feature.  To simplify my 
networking layer, I'm using custom RTP profiles for all non-SIP (ie, 
non-signaling) traffic.  Thus I'm creating a simple file transfer 
profile for RTP.


--- Terminology ---
- server = sending peer
- client = receiving peer


--- Priorities ---
The overall priorities for my file transfer protocol are as follows:
- Fast link speed discovery (to maximize file transfer speed)
- Client-side bandwidth management (to free bandwidth for VoIP)
- High efficiency (minimal bandwidth lost to overhead)
- Minimal fragmentation (all packets fit within UDP MTU)
- Play nice with TCP and other applications


--- Protocol Overview ---
The overall protocol works as follows:
1) Client sends GETINFO to the server
2) Server responds with INFO, which includes the length of the file, as 
well as a strong hash
3) Client send GETBLOCKS to the server, containing a bit vector 
describing which blocks the client hasn't yet received, as well as a 
rate (in blocks per second) at which the server should begin sending them
4) Server sends a series of BLOCK packets to the client, each of which 
contains a block identifier, sequence number, and 1024 bytes of the file 
(except for the final block, which might contain less)
5) Throughout the transfer, the client periodically adjusts the download 
rate by sending CHANGERATE requests to the server.
6) Throughout the transfer, the client occasionally sends an updated bit 
  vector to the server in a new GETBLOCKS request.
7) At the end of the transfer, the client sends DONE and verifies it 
received the file correctly by testing the strong hash.


--- Lessons from TCP ---
I'd like to model the protocol on TCP as much as possible.  But a direct 
application can't be done for at least two reasons:
- TCP puts the server in charge of choosing the send rate (advised by 
the client), while I need to have the client decide (ie, the client 
needs the ability to instantly reduce file transfer bandwidth to free up 
room for an incoming VoIP stream about which the server has no knowledge).
- TCP uses immediate, per-packet ACKs, which are overkill for an 
any-order bulk transfer.  (Upstream bandwidth is an absolute premium so 
I need to conserve wherever possible.)

Regardless, I like the TCP concepts of "slow start" and "congestion 
avoidance", and I'd like to apply them here.


--- Adjusting the Send Rate ---
Whenever the client determines data is being sent too fast or too slow, 
the client calculates a new send rate and requests it using CHANGERATE. 
  If increasing, it can either use the "slow start" or "congestion 
avoidance" formula.  If decreasing, it uses the "decrease" formula. 
These are defined as follows:
- floor                   = Rate after the last decrease
- rate                    = Current send rate
- span                    = rate - floor
- newRate_slowStart       = rate + span
- newRate_congestionAvoid = rate + CONSTANT
- newRate_decrease        = floor + span*FRAC

The "floor" is a deviation from TCP (which always uses a zero floor), 
and is actually the top value of a stack that is adjusted as follows:
- When decreasing after period of increase, push "newRate" on top
- When decreasing twice in a row, pop the stack
- If the stack is empty, reset to initial values

The net result should ideally produce a graph like this:

    |- - - -|- -/|-/|/|/|/- - link speed
    |       |  / |/
    |      || /
   r|      ||/
   a|      |
   t|     |
   e|     |
    |    /
    |__-^
    +-------------------------- time
    0       a    b  c d e ...

(As for the discontinuities at a-e, I'll use the notation rate(a) to 
mean the rate just before, and rate(a') to mean the adjusted rate 
immediately after.)

0-a: Slow start, exponential increase from scratch
a-b: Congestion avoid, CONSTANT slope starting from FRAC*rate(a)
b-c: Congestion avoid from rate(a')+FRAC*(rate(b)-rate(a'))
c-d: Congestion avoid from rate(b')+FRAC*(rate(c)-rate(b'))
d-e: Congestion avoid from rate(c')+FRAC*(rate(d)-rate(c'))

In other words, it starts with exponential increase to quickly get in 
the right ballpark, and then switches to linear increase while it zeros 
in on the link speed.  Eventually it'll oscillate with low magnitude 
right around the actual rate.


--- Rate Change Trigger ---
One big question is "how does the client decide when to change rates?" 
I don't have a good answer here, and I'd love your advice.  It seems 
that there are a few options to decide when to increase:
a) When it receives COUNT packets without packet loss
b) When it receives some duration of packets without packet loss
c) When it downloads at the full requested rate for some period

Likewise, there is a similar list of options about when to decrease:
a) When it detects a single packet loss
b) When it is unable to download at the requested rate for some period

I really don't know which to use.  I've experimented with "increase:c" 
and "decrease:b", but I find the download rate is so erratic that it 
requires a long sample period to average out, which in turn makes the 
whole system respond very slowly.

I'm considering using "increase:a" and "decrease:a" as it seems to work 
well for TCP, but I'm concerned about the impact of wireless networks 
(which I'm told have high packet loss).


--- Questions for the Reader ---
So, with all that played out, here are my specific questions for you:
1) What's a good value for CONSTANT?
2) What's a good value for FRAC?
3) What's a good value for COUNT?
4) Which option should I use to trigger increases?
5) Which option should I use to trigger decreases?
6) What are the ramifications using a non-zero "floor" (ie, being more 
aggressive than TCP)?
7) What would the ramifications be for using only "slow start", and 
skipping "collision avoidance" altogether?

Likewise, I'm sure there are plenty of areas that deserve additional 
scrutiny, so feel encouraged to point them out.

Thanks, I look forward to hearing your thoughts!

-david