[Concept] Disconnect Policies
 

Hi,

Currently Phex has individual disconnect policies, which are off by default.

This means, that it routes all packets, and if a "greedy" client connects, that client can severly decrease our own search performance.

To gather ideas how to change this (and talk about if it's needed), I want to add the following idea as starting point for discussion:

So I think it would be useful to instead try to "get into a part of the network we can manage".

A possible way to archieve that is the following set of disconnect policies:

Drop single congested outgoing connections
If only one outgoing connection is severly congested, disconnect it.
Metric: outgoing dropped % / mean outgoing dropped percentage.

used parameters:
dropped_threshold: below this threshold, no connection gets dropped.
dropped_ratio_threshold: How much the ratio of a single connection must be below the mean ratio to drop a connection.

close the single connection if
- outgoing drop % > dropped_threshold, AND
- outgoing drop % / mean outgoing drop % > dropped_ratio_threshold

example values are:
dropped_threshold: 30%
dropped_ratio_threshold: 3

The result of this is, that a single too weak link gets closed, so we don't batter too weak nodes.

If only one node drops packets, this node gets removed, if it reaches the dropepd_threshold.

On general congestion, drop the most greedy incoming connection

If the mean dropped ratio rises above a threshold (and only then), check all incoming connections and close the one with the highest dropped %.

(is it possible to only count incoming packets we have to forward?)

Target overall effect

The goal is to have Phex move itself automatically towards other nodes who have similar bandwidth requirements.

Slow nodes group themselves around other slow nodes, and greedy nodes get pushed out automatically, but only when they begin to harm the network (no need to do unnecessary policing - as long as it doesn't harm the network the node with the highest incoming packet rate may well be the best source for Query Replies).

Since all used values are accessible from the network tab, I assume that Phex already has all necessary information.

What do you think about the idea?

They are not off, they are active just not configurable through the UI anymore.

Check NetworkHostsContainer.periodicallyCheckHosts()

Good to know :)
Thanks!

I think I can code a part of the policy myself - do you see any direct weaknesses in it (means: is it ready to go into code)?

What I don't yet know is how to efficiently get the mean drop ratio and the mean send queue (I don't want to iterate over all hosts everytime I need to check it).

A possible way would be a simple attribute of the NetworkHostContainer. It could be updated by adding ((host.dropRatio - networkHostsContainer.overallDropRatio) / number_of_hosts) to it for every host (doing it for all hosts once before doing any checks and then inside the checks to keep it up to date).

Which concepts do other vendors follow? Is our current implementation so inefficient that it needs to be replaced? Will the new concept be so much better?

For LimeWire I don't know.

gtk-gnutella limits
* duplicate packets to 5 or 1.5% (the higher one)
* flow controlled time (max. 70% of the time, max 180s) - I'm not sure what that means, but I assume it's the time when packets get dropped.

I don't think that our implementation is inefficient, and the code is very nice to read, but I think that the proposed one will be better for the network and the user, since the client will automatically move towards clients with similar bandwidth capacity and query behaviour.

I like the use of time when calculating the drops.. When you are very good connected to a host for a long time and it's drop count rises it will take very very long until you reach the limit when you don't calculate in time frames.

You mean, for example, taking the mean drop rate over time as measure?

That has the disadvantage of not avoiding overload if the other host suddenly gets flooded and forwards the flood to us.

But maybe the measured drop rate could be adjusted via the connect time (for example reducing the drop rate used for selecting the host to disconnect by up to 1/3rd of the maximum allowed drop rate for long standing connections) to avoid disconnecting good hosts to early.

As far as I know, there's already a measure for "connection already lasts long" (at least for Phex hosts "is good phex").

I think I just misunderstood your post.

Did you mean: "Have a time window in which to calculate the drop rate"?

If so, I think your perfectly right.

With that added, what do you think about the concept of a more "directed" disconnect policy?

directed?

Directed as in "don't just disconnect the one where we have the highest overload, but disconnect to move into a region of the network where we won't get overloaded".

Currently if all outgoings are overloaded , they will get disconnected, which can be contraproductive, if the reason for them being overloaded is a greedy incoming client which we don't detect as greedy, because our inbound bandwidth is far higher than our outbound bandwidth (and because we replicate its requests, so each inbound requests creates up to 31 outbound requests).

That means you like to disconnect connections which are not overloaded because other are overloaded and you are unsure if the not overloaded connections cause that the other connections are overloaded because they could generate to much traffic?

No.

It means, I want to disconnect those not overloaded hosts if I am fairly sure that they cause the others to be overloaded.

I can't be perfectly sure (I could be generating messages myself), but if

* most of the outgoing are overloaded and
* one of the incoming ones creates much more traffic than the others

I can be fairly sure that the one incoming connection causes the outgoing ones to be overloaded.

Note on the words: With "incoming" I mean "incoming stream of data" and with "outgoing" "outgoing stream of data". Since all connections are both-way I don't differenciate between connections initiated by me or by others.

Sure detecting spamming connections is always desirable. I guess the challenge would be to decide what is the better alternative. Disconnect the faster better connected host that send to much data (no spam) for others but maybe not for you or to disconnect the slower host on the edge of the network.

Its always good to have a mix of almost equally weaker and stronger connections around you, to achieve this, looking at message drops because of congestions in a certain time frame might not be such a bad solution and likely a much more easier solution to implement then a complicated algorithm. Why not check out first how the time frame approach will improve things already?

It would in every case be a good first step.

Here's a simple way to get a window (borrowed from TCP):

When receiving

new_connection_quality = old_connection_quality*X + current_measurement * (1-X)

current_measurement is 1 (packet successfully transfered) or 0 (packet dropped).

TCP uses 0.8 for X.

The connection_quality gets initialized with 1 (good).

Since a disconnect is stronger than the "reduce" of TCP, I'd suggest using 0.9 for X and disconnecting when the connection quality drops below 0.3 (I added simulation code to SVN; needs pyxplot so i attached an image of the algo in operation).

These settings disconnect people who have an average drop rate of 30% when they have a burst of drops, anything below is fine. 60% drop rate gets dropped quickly.

The attached images are

- 30% drop rate with X = 0.9
- 60% drop rate with X = 0.9
- 10% drop rate with X = 0.9

I did a test implementation. The following problems exists:
We don't count successful messages. This is hard since a message can be dropped anywhere else much later in the call chain. We count the total messages and the dropped. The good messages would be =total-dropped.

We drop received and sent queue messages. Both works quite differently. Received messages dropped are mostly because of parsing problems, spam or unsupported messages. They come once in a while between good messages.
Sent messages are most of the time dropped in large chunks. This is because of the send queue and message priority. First important messages are transferred, low priority messages are queued for the next rotation. This continues until the live time of queued messages is over, then they are dropped.
This might cause large chunks of messages (lets say 50-200) be dropped at once. And will immediately let your algorithm drop down below the threshold, even though its only a short few seconds lasting low bandwidth period.

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

I thought some more about the above, and I think it grows too complex.

I think it would be more useful to just take (packets - dropped / packets) as quality in a time window equal to the lifetime of a low-priority query.

To not just disconnect the node for one bad value, using this value as base for the TCP algorithm with X=0.9 should do the job (which will also give just connecting nodes a grace period).

Together these keep it simple and don't try to fix one algorithm with esoteric adjustments :)

The smallest single value for the calculation of the quality then isn't one packet but the mean successful/packets ratio the window of one liftetime (successful = packets - dropped).

For incoming packets the simple algorithm from TCP can be used with X=0.9 which will lead to blocking incoming abuse far faster than outgoing drops. That fits the reasoning that incoming abuse is worse than a too weak outgoing link, because incoming abuse gets replicated.

Why not just count total count and drops for a 10 minute window and then check if values are to high, reset counts and wait again 10 minutes until next recheck.

Because you then have to check and store 10 minutes worth of packets instead of only one number and the query lifetime worth of packets.

And because a slowly changing "connection quality" is a neat GUI feature. :)

To make it visually appealing it would be possible to just substract the minimum connection quality and multiply the result with (1/(1 - min. quality)), so users see "OK, it went negative, so the node was disconnected". Could even be done with a simply 0%-100% "progressbar" which goes red when it closes in on 0 and turns dark read when the node gets disconnected (<=0).

you only need to store 2 additional numbers.. total packages and dropped packages since last check.

You're right - I had a wrong preconception in my mind (store every packet info instead of just adding them up).

But please use TCPs algorithm at least for incoming traffic - there the faster update time is more important, since we replicate the queries.

Besides: Should I keep spending quite some time to find elegant solutions, or should I rather first write a short idea and only do more extensive thinking/testing when you did a test (and save time which might else be wasted on stuff which never gets in)?

You should find time to use a more comfortable communication device then a forum... like IRC maybe

The problem with IRC is that we have different IRC times (I'm online a couple of times per week).

Cant we just disable the allow to become UltraPeer in the UI? Or are you strictly speaking about being an ultrapeer and then trying to normalize traffic?

Or did i misunderstand?

Well the rules apply to both, UP and leafs. After going through some tests and algorithm tuning we pretty much implemented Arnes idea of connection quality calculation.
It's not as smart as Arne would like it to be ;) but should do a better job then the old one.

Just looking a the code :)

Host.calcSentQuality()
in case you have not found it already.

Thanks, took me some time to figure it was sentWindowGoodMsgCount being incremented and not sentWindowDropMsgCount in the else clause.

And we dont send queries to unstable hosts. Looks nice.