In order to characterize any degree of positive correlations in C(n), we adopt the notion of ‘association’ [9, 12].

The set of associated processes comprises a large class of processes, and the most popular example is of the fol- lowing type: Theorem 4.3.13. in [9]: Let {X(t)} be a stochastic

process with static space S = R^{d }of the form

X(t + 1) = ϕ(X(t), Z(t)), for t = 0, 1, . . .

(6)

If the {Z(t)} are mutually independent and independent of X(0), then {X(t)} is associated if ϕ(x, z) is increasing

in x.

✷

Stochastic processes of the form (6) constitute large portion of Markov processes. For example, any auto- regressive type model with positive correlation coefficient can be written in the form of (6). Specifically, for an AR-1 sequence X(t) defined by

# X(t + 1) = ρX(t) + bξ(t),

where 0 < ρ < 1 and ξ(t) (t = 0, 1, . . .) is a sequence of i.i.d. random variables and independent of X(0), we can write X(t + 1) = ϕ(X(t), ξ(t)) where ϕ(x, ξ) = ρx + bξ. Since ϕ is increasing in x, the process {X(t)} is associ- ated.

We below present our theorem. Due to space con- straint, we refer to our technical report [3] for all the proofs.

Theorem 1 Suppose that {C(t), t ≥ 1} is associated. Then, we have

E{T_{cor }

} ≥ E{T_{ind }

}.

(7)

✷ Theorem 1 states that the average download time of a file over a path with correlated service capacity is always larger than that of an i.i.d. counterpart. In the subse- quent section, we show the relationship between the de- gree of correlation of a process and the average first fitting

time of that process, and illustrate how much E{T_{cor }be larger than E{T_{ind}}.

} can

II.C First Hitting Time and Degree of Correlation

# Suppose that C(t) is given by a stationary first-order

autoregressive process (AR-1), i.e.,

C(t + 1) = ρ · C(t) + (t) + α.

(8)

Here, (n) is a sequence of i.i.d. random variables with zero mean, which represents a noise term of the process. Then, from the stationarity of the process, we get

E{C(t)} = µ = α/(1 − ρ).

(9)

We vary the constant α such that the average capac- ity is always fixed to E{C(t)} = µ = 10 under differ- ent ρ. Since the available bandwidth cannot be nega- tive, we impose restriction on the range of C(t) such that

3

C(t) ∈ [0, 20], while keeping the mean still the same. The file size is F = 250 and the noise term, (t), is chosen to be uniformly distributed over [−1, 1], [−5, 5], and [−9, 9] to see how the noise term affects the average download time.

40

## Average Download Time (slots)

35

30

25

[−1, 1]

[−5, 5]

[−9, 9]

0.1

0.2

0.3 0.4 0.5 0.6 0.7 0.8 Correlation coefficient ()

0.9

1

Figure 1: Relationship between the average download time and different degrees of correlation ρ under different noise term (t) in (8).

Figure 1 shows the relationship between the average download time and the degree of correlation of the process (8) for different ρ and (t). As the degree of correlation increases, the average download time increases. In partic- ular, for a heavily correlated process, the average down- load time can be about 40% larger than for uncorrelated or lightly correlated process, regardless of different noise terms. In real data networks, the available capacity of a connection typically shows wild fluctuation; it becomes very low when congestion occurs, and it can reach up to the maximum link bandwidth when things go well. In addition, as technology advances, people are getting links of higher and higher speed, hence the range of available capacity fluctuation is also likely to increase. Therefore, it is very important to consider the effect of correlation in capacity over time when we calculate the average down- load time of a file transfer.

III. Minimizing Average Download Time Over Stochastic Channels

Given the characterization of the average download time in Section II, we can now analyze the performance of different strategies that help reduce the average download time for each user. In this section we will analyze the per- formance of (i) random chunk-based switching, and (ii) random time-based (periodic) switching. Both methods allow only one active link simultaneously. Although par- allel downloading is another commonly used method to reduce file download time, as we will show in the sim- ulation section, parallel downloading performs well only when there are very few users in the network and almost no heterogeneity in service capacity. In all other cases as in reality, the parallel downloading may even perform worse than single-link download. Hence we will focus on the performance analysis of single-link download strate- gies.