[Concept] Disconnect Policies

arne_bab · #18 (**permalink**) October 19th, 2008

The code could be adapted to use chunks which begin and end at places, where a dropped message gets followed by a sent packet.

For received messages it would work as it is.

For sent messages, we can just make X larger (for example 0.95).

The math for calculation of a fitting X is pretty simple:

- We take the base value (for example 90% good packets - 10% drop -> base connection quality: 0.9)
- We want this quality to stay above 0.3 as long as the size of the chunk of dropped messages doesn't exceed a certain threshold (for example 200).

Math: base quality * X**(max length of drop chunk) > 0.3

Example:
- base quality: 0.9
- X: 0.995
- max drop chunk length: 200
0.9 * 0.995**(200) = 0.33026203955355032

This will make the outgoing window larger, but it has the advantage of still being extremly simple, and of suplpying a connection quality which can mean something to users.

As you can see in the attached plots (which already use "sent" = "success"), it takes about 300 to 600 packets for the algorithm to stabilize with X = 0.995

With chunks it will take about the same time, but it will reach that lower quality at the end of a drop chunk and fluctuate a bit more.

Using "sent packets" and "dropped" instead "successful" and "dropped" should be no problem. It just increases the connection quality given back by the algorithm, so we can just increase the bar of what is "good".

"Sent" is just taken as "successful", and we have a bit more "successful" packages in the algorithm (success + drop rate) than in the ideal algorithm, but that shouldn't do harm. The mean quality now can't go below 0.5, but the mean quality isn't the parameter for disconnect - the parameter is how far the drop chunk will decrease the connection quallity. Maybe it would also be possible, though, to take the mean of the quality by storing the extrema of the quality and using the mean of those (with expiration time).

pseudocode:

Code:

if current_quality > previous_quality: 
  set the latest maximum to current_quality. 
  if the latest minimum is not None: // if the latest minimum has been set in the last step
    add a minimum with the value None // we add a new one without value - we set the minimum to change to the next one in line. 
else if current_quality < previous quality: 
  set the latest minimum to current_quality. 
  if the latest maximum is not None: // if the latest maximum has been set in the last step
    add a maximum with the value None // we add a new one without value

This gets all local extrema which can be used for the mean calculation. With drop chunks the number of extrema shouldn't rise too fast (the list of extrema could also just have a length limit - when it is reached, the new maxima are added at the beginning again, overwriting the old ones).

The advantage of this algorithm is that it is very easy to code (and should be very fast).

The "base quality" of a 30% drop connection which drops in chunks (see 0.9*0.995**200) should be well above the 0.7 which we get from a randomly dropping connection, as it will have long phases in which no packets get dropped.

Example:

Code:

>>> a = 0.9
>>> for i in range(200):
...  a *= 0.995
...
>>> a
0.33026203955355027
>>> for i in range(600):
...  a = a*0.995 + 0.005
...
>>> a
0.96690568756215878
>>> for i in range(200):
...  a *= 0.995
...
>>> a
0.35481360492245118
>>> for i in range(600):
...  a = a*0.995 + 0.005
...
>>> a
0.96811887424582133
>>> (a + 0.35481360492245118 ) / 2.0
0.6614662395841362

(that's a quality 0.5 connection: 200 drops, 400 successes, 600 total packets - 1/3rd of the packets get dropped -> 0.66).