RE: returning results for partial downloads

This is interesting work. My opinion is that such optimization should not be
based on a average local metric but on the network as a whole. If you take
the network as a whole, it's clear that each byte downloaded by someone is
also a byte uploaded by another one.

So the metric does not indicate how the network works really, but will just
measure the capacity of the whole network to work at is maximum total
bandwidth that it can support: it will then measure the efficiency of the
network deployment, comparing the resources needed for its construction and
the effective utility of that network in its capacity to use the bandwidth
it promised.

But for now, the total network resources does not seem to be scarce: we can
most frequently see that nodes are constantly waiting for availability of
resources, and the average speed does not grow as promised. So the problem
lives elsewhere, and this is where "fairness" can be defined:

You need not only compare the average upload speed to the average download
speed (my opinion is that when the network grows enough, both are converging
rapidly to equal values), but more interestingly how the ratio of these two
values is distributed around this average value within the network.

So I would compute "instant fairness" as being the ratio between the
standard deviation of download/upload and the average of download/upload
computed for each node at the same instant. (the fact that some or most
nodes have asymmetric connections should not matter here, given that the
network on average will converge so that both download and upload speeds are
equilibrated, whatever you want to do, as soon as it grows with more nodes).

Then I would integrate this ratio over time to compute an average fairness,
and this would be the interesting metric.

If nodes are given indice t, and time iterations indice t in your model,
then at each instant t in your simulation you have d_i(t) bytes/s downloaded
by node number i and u_i(t) bytes/s uploaded by the same node.

Instant fairness at time t is then:

        stddev_i(d_i(t)/u_i(t))
f(t) = ----------------------------
           avg_i(d_i(t)/u_i(t))

One problem is that stddev is a square root, but you could as well try to
compare the square of f(t), which is simpler to compute. Note that ideally
f(t) should be zero. Comparing the square of f(t) will not change the
policy: you want to minimize it, as near as possible from 0, so you can
integrate it also over time.

So let's take more simply the variance in the formula by taking the square
of f.

                 var_i(d_i(t)/u_i(t))
g(t) = f^2(t) = ----------------------
                 avg_i(d_i(t)/u_i(t)) 

        N     sum_i(d_i(t)/u_i(t)) ^ 2
     = --- . --------------------------,
       N-1    sum_i(d_i(t)^2/u_i(t)^2)

where N is the number of nodes in your simulation.

Then compute the sum over time iterations t from 0 to the length of your
simulation (i.e. the N iterations), divide it by N and try comparing it...

Note: g(t) does not really measure fairness but unfairness, i.e. its
inverse. Fairness is defined simply by 1/g(t) but we don't need it really,
as this complicates the analysis of the metric, because the ideal system
would have a null standard deviation, and the wanted convergence to infinite
is not easy to satisfy and even measure (there's no way to measure the
distance to the infinite because this distance is always infinite and
comparing two infinite distances is impossible).

If g(t) converges to some small values (on average to 0 on a ideal system)
this means that the download/upload resources of the network are equally
distributed all over the network, so it can converge more rapidly to the
situation where both the total download speed or total upload speed (they
are equal at each instant) will grow to their maximum. (It will never be
able to reach the point where the maximum download speed will be reached,
because of the prevalence of asymmetric connection speeds in the Gnutella
network, which is supported by the Internet hosts made by end-user
connections that are most often assymmetric).

If g(t) converges to large values, the network contains large privileged
nodes that behave unfairly.

If g(t) diverges, the network will die rapidly because it will so instable
that its capacity can only be used by some nodes blocking it completely.

Note: the criteria of convergence of g(t) is quite equivalent to integrating
it after letting the system run for enough time, and integrating only over a
final interval of time, provided that g'(t), its derivation, does not
diverge. Ideally g'(t) should converge to 0, but this is not needed for
network fairness, only for network stability, so this can be a secondary
metric, which would be interesting to compute too in the simulation (if two
simulations have approximately the same average value for g(t), i.e. behave
nearly as fairly as the other, the second criteria is stability)

You may in fact want to satisfy first the criteria of stability i.e.
minimizing the value of g'(t) before minimizing g(t) itself.

Note that you cannot compute really a derivative like g'(t) in a discrete
system where t is just an iteration number, but you can still equivalently
use g(t+1)-g(t) which represents the average of g't(t) between these two
instants t and (t+1).

So:

         N  [ sum_i( d_i(t+1)/u_i(t+1) )^2 - sum_i( d_i(t)/u_i(t) )^2 ]
g'(t)= ------------------------------------------------------------------
       (N-1)  sum_i[ d_i(t+1)^2/u_i(t+1)^2 -        d_i(t)^2/u_i(t)^2 ]

This value starts being computable if N=2, but this is the basic network
with only 2 nodes: stability is not a criteria in this case. A minimum
simulation should take a minimum of N=100 nodes (numbered with indice i) and
iterate for about T=100 times (numbered with indice t).

> -----Message d'origine-----
> De : [email protected] [mailto:[email protected]] De la part
> de Serguei Osokine
> Envoyé : dimanche 7 octobre 2007 00:38
> À : [email protected]
> Objet : RE: [the_gdf] returning results for partial downloads
> 
> On Saturday, October 06, 2007 Michael Rogers wrote:
> > In terms of comparing strategies, you could compare bytes downloaded
> > per byte uploaded or bytes downloaded in a given time.
> 
> 	So it is your intent to compare how multiple algorithms fight
> each other on the same network? Thanks, I missed it. Thought that you
> are going to load the same algorithm on all the nodes and see what
> happens.
> 
> 	But is the best fighter algorithm necessarily the best one for
> the network as a whole? Let's say you have two algorithms: 'generous
> giver' and 'shameless leecher'. You load them on the network, and
> shameless leacher beats the generous giver hands down in you metrics
> of bytes downloaded per bytes uploaded. But does it mean that the
> shameless leecher algorithm has any useful qualities? Not necessarily.
> 
> 	Am I missing something in what you're going to do?
> 
> 	Best wishes -
> 	Oso.
> 
> 
> -----Original Message-----
> From: [email protected] [mailto:[email protected]]On Behalf
> Of Michael Rogers
> Sent: Saturday, October 06, 2007 3:10 PM
> To: [email protected]
> Subject: Re: [the_gdf] returning results for partial downloads
> 
> 
> Serguei Osokine wrote:
> > 	Nice to see someone doing some math on that subject. However,
> > after the first cursory reading I was not able to understand - what
> > is it exactly  that you are aiming to maximize? Is it your goal to
> > maximize the cumulative upload rate of the network, or you also
> > want to divide it between the downloaded in some fair way? What
> > is your definition of fair, if this is the case? I mean, you need
> > to calculate a single one-dimensional value (call it the algorithm
> > quality or utility) for each algorithm to compare them, right? What
> > is this value and how is it calculated?
> 
> Hi Serguei,
> 
> Each node is selfishly trying to maximise the number of bytes downloaded
> per byte uploaded - the expected utility of uploading a byte is the
> number of bytes you can expect to download in return, based on the
> number of bytes uploaded to and downloaded from each peer so far. I've
> tended to interpret that in terms of maximising the download speed for a
> given upload speed, but as far as I can see you could use the same
> strategies to minimise the upload speed for a given download speed.
> 
> Because there's no explicit choke/unchoke signalling and the utilities
> are cheap to calculate, the selection could be made very frequently
> (send a packet, choose the recipient of the next packet, repeat).
> 
> I haven't explicitly aimed to maximise the total download speed, but I'm
> hoping the best selfish strategies will also be Pareto efficient as in
> the prisoner's dilemma. Fairness is harder, especially since there seem
> to be two contradictory definitions - "equal benefit for all" or
> "benefit proportional to contribution" - so I tend to steer clear of
> that word. ;-)
> 
> In terms of comparing strategies, you could compare bytes downloaded per
> byte uploaded or bytes downloaded in a given time.
> 
> Cheers,
> Michael
> 
> 
> 
> Yahoo! Groups Links
> 
> 
> 
> 
> 
> 
> 
> Yahoo! Groups Links
> 
> 
> 
>