Information Technology Reference
In-Depth Information
(
t
0
and
b
i
0
), hence its payment is be given by
t
0
∂V
∂V
∂b
i
0
+
b
i
0
. For the remaining agents,
∂t
0
there is only one parameter (
b
i
i
), hence their payments are
b
i
i
∂V
∂b
i
i
. Finally, we obtain
the expressions shown in equations (5):
⎧
⎨
t
0
(
1
b
i
i
)
2
if
i
=0
(
0
b
i
i
)
2
x
i
=
(5)
b
out
0
b
i
i
⎩
t
0
if
i
=0
(
0
b
i
i
)
2
In appendix A we prove that the equations (5) define a payoff division that lies inside
the core.
Finally, we will show that the computations can be done within a reasonable amount
of time and using a reasonable amount of computational efforts. It is obvious that the
above schema provides a set of explicit formulae that compute payments in time linear
with the number of peers.
2.3
Data and Bandwidth Distribution Model
Following on from the example, let us suppose that the peer
p
b
asks
p
0
(
p
a
in the figure)
to download the file Z, and
p
0
decides to initiate a coalition to download the file (figure
1) Then,
p
0
carries out the following steps:
1. To set the coalition size. If the sum of the upload bandwidth,
b
i
i
, of all the interested
peers (let us suppose this value is equal to
n
) joined with
p
0
, is lower than the
download bandwidth of
p
b
,
b
ou
b
, we are in the trivial case (equation 6). In this case,
all the interested peers joined with
p
0
will form the coalition. So,
|
S
|
=
N
:
(
i∈N
b
i
i
)
b
out
b
≤
(6)
Conversely if the expression (6) is false, we must distribute the bandwidth of
p
b
,
b
out
b
between all the interested peers
1
.
For this, it is necessary to distribute the
b
ou
b
of
p
b
among all of them. This can be
done by “the progressive filling algorithm” [10]. Let us suppose
w
i
is the assigned
bandwidth for the interested peers. The algorithm initialises the bandwidth of all
the interested peers to 0,
w
i
=0
,
S
. Then, it increases all the bandwidths at
the
same rate
, until one or several peers hit their limits,
w
i
=
b
i
i
∀
i
∈
S
. Once the
bandwidth assigned to one peer,
p
i
, reaches its limit, it is taken out of the process.
The algorithm will continue to increase the bandwidth of the remaining peers at the
same rate
. The algorithm will finish when all the peers reach their limits, or when
the bandwidth of
p
b
,
b
ou
b
is wasted.
This algorithm provides the
max-min fairness
[9]. A bandwidth allocation is
max-min fair if and only if an increase of
b
i
x
within its domain of feasible allocation
is at the cost of decreasing some other
b
i
y
. So, it gives the peer with the smallest
bidding value the largest feasible bandwidth.
,
∀
i
∈
1
If there are many interested peers, a maximum size of coalition is established in order to avoid
an undue partitioning of
b
out
. This value depends on the
b
out
and the file size.
