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

I_{u}(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) = C_{U(t) }

(t) =

C_{u}(t)I_{u}(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 C_{u}(t), and so is I_{u}(t). Note that, from E{I_{u}(t)} = 1/N for any u, we have

E{X(t)} =

E{C_{u}(t)}E{I_{u}(t)} =

c_{u }

N

u=1

u=1

### N

### 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 r_{per}(τ) and r_{ran}(τ) denote the corre- lation coefficient of X(t) under the permanent connection and the random periodic switching, respectively. Then, we have

r_{ran }

(τ )

=

1 N

r_{per }

(τ), ∀ 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 T_{ran }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

## C_{U (t) }

(t)

= E{T_{ran }

}E{C_{U(t) }

(t)}

= E{T_{ran }

}E E C_{U(t)}(t) | U(t)

= E{T_{ran }

}

= E{T_{ran }

}

1 N

1 N

N

u=1 N

# E{C_{u}(t)}

c_{u }= E{T_{ran }

}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 C_{u}(t) for each u is associated (i.e., it is correlated over time t). Let T_{per }and T_{ran }be the download time for the permanent connec- tion and for the random periodic switching, respectively. Then, we have

E{T_{per }

} ≥ E{T_{ran }

}.

✷ 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.

# IV. Numerical Results

In this section we provide numerical results to support our analysis and compare the performance of the four schemes for file download under various network configu- rations. In any case, in our configuration, different paths have different average service capacities, and the service capacity of each path is correlated in time. We consider a single downloading peer as well as multiple downloading peers to allow competition among the downloading peers for limited service capacity of each source peer.

IV.A Single Downloader with Heterogeneous Path Characteristics

We first show the impact of both heterogeneity and correlations in service capacities on the average download time when there is a single user (downloader) in the net- work. There are N = 4 source peers in the network, each offering different average service capacities. Let c_{i }be the