X hits on this document

# I. Introduction - page 5 / 8

19 views

0 shares

5 / 8

For the periodic random switching, the downloader randomly chooses a path at each time slot, independently of everything else. In other words, the path selection function U(t) forms an i.i.d. sequence of random vari- ables, each of which is again uniformly distributed over {1, 2, . . . , N}. Figure 3 illustrates the operation of the path selection function U(t) for random periodic switch- ing. In this figure, path 1 is selected at time 1, path N is selected at time 2, and so on.

# Let us define an indicator function

Iu(t) =

1, 0,

if U(t) = u otherwise.

Then, since U(t) can take values only from {1, 2, . . . , N}, the actual available capacity at time t can be written as

N

X(t) = CU(t)

(t) =

Cu(t)Iu(t)

u=1

for both the permanent connection and the random peri- odic switching strategies. Since each downloader chooses a path independently of the available capacity, U(t) is also independent from Cu(t), and so is Iu(t). Note that, from E{Iu(t)} = 1/N for any u, we have

E{X(t)} =

E{Cu(t)}E{Iu(t)} =

cu

N

u=1

u=1

### N

= A ( c ) ,

i.e., the average available capacity for the two path selec- tion strategies are the same.

In order to analyze how the two different strategies affect the correlation in X(t), we consider the correlation coefficient of X(t) defined as

Cov{X(t), X(t + τ)} r(τ) = Var{X(t)}

.

Then, we have the following result.

Proposition 1 Let rper(τ) and rran(τ) denote the corre- lation coefficient of X(t) under the permanent connection and the random periodic switching, respectively. Then, we have

rran

(τ )

=

1 N

rper

(τ), t 1.

From Proposition 1, we see that under the random

periodic switching strategy, the correlation of X(t) is N times smaller than that of permanent connection strat- egy. For example, when each downloader has about 10 available source peers (N = 10), the correlation coeffi- cient of the newly obtained capacity process under our random periodic switching is no more than 0.1 regardless of the correlations present in the original capacity fluc- tuation. So, by using our random periodic switching, we can always make the capacity process very lightly corre- lated, or almost independent. From Figure 1, we see that

5

the average download time for a lightly correlated process is very close to that given by Wald’s equation. It is thus reasonable to assume that Wald’s equation holds for the lightly correlated process X(t) under our random peri- odic switching strategy. Specifically, if we define Tran as the download time for a file of size F under the random periodic switching, we have

F =E

T r a n n = 1

## CU (t)

(t)

= E{Tran

}E{CU(t)

(t)}

= E{Tran

 }E E CU(t)(t) | U(t)



= E{Tran

}

= E{Tran

}

1 N

1 N

N

u=1 N

# E{Cu(t)}

cu = E{Tran

}A(c).

(11)

u=1

We then have the following comparison result between the permanent connection and periodic switching.

Proposition 2 Suppose that the process Cu(t) for each u is associated (i.e., it is correlated over time t). Let Tper and Tran be the download time for the permanent connec- tion and for the random periodic switching, respectively. Then, we have

E{Tper

} ≥ E{Tran

}.

Proposition 2 shows that our random periodic switch- ing strategy will always reduce the average download time compared to the permanent strategy and that the aver- age download time under the random periodic switching is given by F/(c) (see (4)). Note that this was made possible since the random periodic switching removes the negative impact of both the heterogeneity and the cor- relations. In addition, our algorithm is extremely simple and does not require any information about the system.