3.3 Preliminary Performance Analysis of FastReplica in the Small

Let $Time^i(F)$ denote the transfer time of file $F$ from the original node $N_0$ to node $N_i$ as measured at node $N_i$. We use transfer time and replication time interchangeably in the text. In our study, we consider the following two performance metrics:

• Average replication time:
  $$\begin{eqnarray*} \nonumber Time_{aver} = \frac{1}{n} \sum_{i=1}^n Time^i (F) \end{eqnarray*}$$
  
  

• Maximum replication time:
  $$\begin{eqnarray*} \nonumber Time_{max} = max \{Time^i (F)\} , i \in \{1, \cdots, n\} \end{eqnarray*}$$
  
  

$Time_{max}$ reflects the time when all the nodes in the replication set receive a copy of the original file, and the primary goal of FastReplica is to minimize the maximum replication time. However, we are also interested in understanding the impact of FastReplica on the average replication time $Time_{aver}$. First, let us consider an idealistic setting, where nodes $N_1, ..., N_n$ have symmetrical (or nearly symmetrical) incoming and outgoing bandwidth which is typical for CDNs, distributed IDCs, and a distributed enterprise environment. In addition, let nodes $N_0, N_1, ...., N_n$ be homogeneous, and let each node can support $k$ network connections to other nodes at $B$ bytes per second on average.

Figure 4: Uniform-random model: speedup in file replication time under FastReplica vs Multiple Unicast for a different number of nodes in replication set for a) average replication time, and b) maximum replication time.

In the idealistic setting, there is no difference between maximum and average replication times. Using the assumption on homogeneity of nodes' bandwidth, we can estimate the transfer time for each concurrent connection $i$ $(1\leq i \leq n)$ during the distribution step:

$$Time_{distr} = { {Size(F)} \over {n \times B}}$$ (1)

The transfer time at the collection step is similar to the time encountered at the first (distribution) step:

$$Time_{collect} = { {Size(F)} \over {n \times B}}$$ (2)

Thus the overall replication time under FastReplica in the small is the following:

$$Time^{small}_{FR} = Time_{distr} + Time_{collect} =2 \times {{Size(F)}\over {n \times {B}}}$$ (3)

Let Multiple Unicast denote a schema that transfers the entire file $F$ from the original node $N_0$ to nodes $N_1, ...., N_{n}$ by simultaneously using $n$ concurrent network connections. The overall transfer time under Multiple Unicast is the following:

$$Time^{small}_{MU} = { {Size(F)} \over { B}}$$ (4)

Thus, in an idealistic setting, FastReplica in the small provides the following speedup of file replication time compared to the Multiple Unicast strategy:

$$Replication\_Time\_Speedup ={Time^{small}_{FR} \over {Time^{small}_{MU}} } = {n \over 2}$$ (5)

While the comparison of FastReplica and Multiple Unicast in the idealistic environment gives insights into why the new algorithm may provide significant performance benefits for replication of the large files, the bandwidth conditions in the realistic setting could be very different from the idealistic assumptions. Due to changing network conditions, even the same link might have a different available bandwidth when measured at different times. Let us analyze how FastReplica performs when network paths participating in the transfers have a different available bandwidth. Let $BW$ denote a bandwidth matrix, where $BW[i][j]$ reflects the available bandwidth of the path from node $N_i$ to node $N_j$ as measured at some time $T$, and let Var be the ratio of maximum to minimum available bandwidth along the paths participating in the file transfers. We call Var a bandwidth variation. In our analysis, we consider the bandwidth matrix $BW$ to be populated in the following way:

$$BW[i][j] = {B \times random(1,{\it Var})},$$

where function $random(1,{\it Var})$ returns a random integer $var$: $1 \leq var \leq {\it Var}$. While it is still a simplistic model, it helps to reflect a realistic situation, where the available bandwidth of different links can be significantly different. We will call this model a uniform-random model. To perform a sensitivity analysis of how the FastReplica performance depends on a bandwidth variation of participating paths, we experimented with a range of different values for Var between $1$ and $10$. When ${\it Var} = 1$, it is the idealistic setting, discussed above, where all of the paths are homogeneous and have the same bandwidth $B$ (i.e. no variation in bandwidth). When ${\it Var} = 10$, the network paths between the nodes have highly variable available bandwidth with a possible difference of up to 10 times. Using the uniform-random model and its bandwidth matrix $BW$, we compute the average and maximum file replication times under FastReplica and Multiple Unicast methods for a different number of nodes in the replication set, and derive the relative speedup of the file replication time under FastReplica compared to the replication time under the Multiple Unicast strategy. For each value of Var, we repeated the experiments multiple times, where the bandwidth matrix $BW$ is populated by using the random number generator with different seeds. Figure 4 a) shows the relative average replication time speedup under FastReplica in the small compared to Multiple Unicast in the uniform-random model. For Var=2, the average replication time for 8 nodes under FastReplica is 3 times better compared to Multiple Unicast, and for 20 nodes, it is 8 times better. While the performance benefits of FastReplica against Multiple Unicast are decreasing for higher variation of bandwidth of participating paths, FastReplica still remains quite efficient, with performance benefits converging to a practically fixed ratio for ${\it Var} >4$. Figure 4 b) shows the relative maximum replication time speedup under FastReplica in the small compared to Multiple Unicast in the uniform-random model. We can observe that, independent of the values of bandwidth variation, the maximum replication time under FastReplica for n nodes is $n\over 2$ times better compared to the maximum replication time under Multiple Unicast. It can be explained in the following way:
$\bullet \,\,$ Multiple Unicast: The maximum replication time is defined by the entire file transfer time over the path with the worst available bandwidth among the paths connecting $N_0$ and $N_i$, $1\leq i \leq n$.
$\bullet \,\,$ FastReplica: Figure 5 shows the set of paths participating in the file transfer from node $N_0$ to node $N_1$ under the FastReplica algorithm (we use $N_1$ as a representative of the recipient nodes).

Figure 5: FastReplica in the small: a set of paths used in file $F$ replication from node $N_0$ to node $N_1$.

The replication time observed at node $N_1$ is defined by the maximum transfer time of $1\over n$-th of the file over either:

• the path from $N_0$ to $N_1$, or
• the path with the worst overall available bandwidth consisting of two subpaths:
  • the subpath from $N_0$ to $N_j$ and
  • the subpath from $N_j$ to $N_1$,
  for some $j: 1\leq j \leq n$.
  In the considered uniform-random model, a worst case scenario is when both subpaths have a minimal bandwidth, and since each path is used for transferring $1\over n$-th of the entire file, this would lead to $n\over 2$ times latency improvement under FastReplica compared to the maximum replication time under Multiple Unicast.

Now, let us consider a special, somewhat artificial example, which aims to provide an additional insight into the possible performance outcomes under FastReplica when the values of bandwidth matrix $BW$ are significantly skewed. Let $N_0$ be the origin node, and $N_1, ..., N_{10}$ be the recipient nodes, and the bandwidth between the nodes be defined by the following matrix:

$$BW(i,j) = \left \{ \begin{array}{lll} {{1 \over 10} \time... ...B} & \mbox{if $1\leq i,j \leq 10$} \end{array} \right.$$ (6)

In other words, the origin node $N_0$ has a limited bandwidth of ${{1\over 10} \times B}$ to node $N_1$, while the bandwidth from $N_0$ to the rest of the recipient nodes $N_2, ..., N_{10}$ is equal to $B$. In addition, the cross-bandwidth between the nodes $N_1, ..., N_{10}$ is also very limited, such that any pair $N_i$ and $N_j$ is connected via a path with available bandwidth of ${{1\over 10} \times B}$. At a glance, it seems that FastReplica might perform badly in this configuration because the additional cross-bandwidth between the recipient nodes $N_1, ..., N_{10}$ is so poor relative to the bandwidth available between the origin node $N_0$ and the recipient nodes $N_2, ..., N_{10}$. Let us compute the average and maximum replication times for this configuration under Multiple Unicast and FastReplica strategies.
$\bullet \,\,$ Multiple Unicast:

$$Time_{aver}={{{19}\times {Size(F)} \over {10 \times B}}}, Time_{max} = {{{10}\times {Size(F)} \over {B}}}.$$

$\bullet \,\,$ FastReplica:

$$Time_{aver}={{{191}\times {Size(F)} \over {100 \times B}}}, Time_{max} = {{{2}\times {Size(F)} \over {B}}}.$$

The maximum replication time in this configuration is $5$ times better under FastReplica than under Multiple Unicast. In FastReplica, any path between the nodes is used to transfer only $1\over n$-th of the entire file. Thus, the paths with poor bandwidth are used for much shorter transfers which leads to a significant improvement in maximum replication time. However, the average replication time in this example is not improved under FastReplica compared to Multiple Unicast. The reason for this is that the high bandwidth paths in this configuration are used similarly: to transfer only $1\over n$-th of the entire file, and during the collection step of the FastReplica algorithm, the transfers of complementary $1\over n$-th size subfiles within the replication group are performed over poor bandwidth paths. Thus, in certain cases, like considered above, FastReplica may provide significant improvements in maximum replication time, but may not improve the average replication time. The analysis considered in this section outlines the conditions when FastReplica is expected to perform well, providing the essential performance benefits. Similar reasoning can be applied to derive the situations when FastReplica might be inefficient. For example, let us slightly modify the previous example. Let the bandwidth matrix $BW$ be defined in the following way:

$$BW(i,j) = \left \{ \begin{array}{ll} {B} & \mbox{if i=0, ... ...B} & \mbox{if $1\leq i,j \leq 10$} \end{array} \right.$$ (7)

In this configuration, the bandwidth from the origin node $N_0$ to the rest of the recipient nodes $N_1, ..., N_{10}$ is equal to $B$, while the cross-bandwidth between the nodes $N_1, ..., N_{10}$ is very limited: any pair $N_i$ and $N_j$ is connected via a path with available bandwidth of ${{1\over 10} \times B}$. The average and maximum replication times for this configuration under Multiple Unicast and FastReplica strategies can be computed as follows:
$\bullet \,\,$ Multiple Unicast: $Time_{aver} = Time_{max}={{Size(F)} \over {B}}.$
$\bullet \,\,$ FastReplica: $Time_{aver} = Time_{max} = {{{11}\times {Size(F)} \over {10 \times B}}}.$
Thus in this configuration, FastReplica does not provide any performance benefits. In a general case, if there is a node $N_k$ in the replication set such that most of the paths between $N_k$ and the rest of the nodes have a very limited available bandwidth (say, $n$ times worse than the minimal available bandwidth of the paths connecting $N_0$ and $N_i$, $1\leq i \leq n$) then the performance of FastReplica during the second (collection) step is impacted by the poor bandwidth of the paths between $N_k$ and $N_i$, $1\leq i \leq n,$ and FastReplica will not provide expected performance benefits. Note, that $n$ (the number of nodes in the replication group) plays a very important role here: a larger value of $n$ provides a higher ``safety'' level for FastReplica efficiency. A larger value of $n$ helps to offset a higher difference in bandwidth between the available bandwidth within the replication group and the available bandwidth from the original node to the nodes in the replication group. To apply FastReplica efficiently, the preliminary bandwidth estimates are useful. These bandwidth estimates are also essential for correct clustering of the appropriate nodes into the replication subgroups in FastReplica in the large discussed in the next section.