3.2 FastReplica in the Small

In this Section, we describe a core of FastReplica which is directly applicable to a case when a set of recipient nodes $N_1, ..., N_n$ is small, e.g. in a range of 10-30 nodes. File $F$ is divided in $n$ equal subsequent subfiles:

$$F_1, ...., F_n$$

where $Size(F_i) = {{Size(F)} \over n}$ bytes for each $i$: $1\leq i \leq n$. Step 1: Distribution Step. The originator node $N_0$ opens $n$ concurrent network connections to nodes $N_1, ..., N_n$, and sends to each recipient node $N_i$ ( $1\leq i \leq n$) the following items:

• a distribution list of nodes $R = \{N_1, ..., N_n\}$ to which subfile $F_i$ has to be sent on the next step;
• subfile $F_i$.

The activities taking place on the first step of the FastReplica algorithm are shown in Figure 1. We will denote this step as a distribution step.

Figure 1: FastReplica in the small: distribution step.

Step 2: Collection Step. After receiving file $F_i$, node $N_i$ opens $n -1$ concurrent network connections to remaining nodes in the group and send subfile $F_i$ to them as shown in Figure 2 for node $N_1$.

Figure 2: FastReplica in the small: a set of outgoing connections of node $N_1$ at collection step.

Figure 3: FastReplica in the small: a set of incoming connections of node $N_1$ at collection step.

Similarly, Figure 3 shows the set of incoming concurrent connections to node $N_1$ from the remaining nodes $N_2, ... , N_n$ transferring the complementary subfiles $F_2, ... , F_n$ during the second logical step of the algorithm. Thus at this step, each node $N_i$ has the following set of network connections:

• there are $n -1$ outgoing connections from node $N_i$: one connection to each node $N_k$ ($k \neq i$) for sending the corresponding subfile $F_i$ to node $N_k$.
• there are $n -1$ incoming connections to node $N_i$: one connection from each node $N_k$ ($k \neq i$) for sending the corresponding subfile $F_k$ to node $N_i$.

Thus at the end of this step, each node receives all subfiles $F_1, ...., F_n$ comprising the entire original file $F$. We will denote this step as a collection step. In summary, the main idea behind FastReplica is that instead of the typical replication of an entire file to $n$ nodes by using $n$ Internet paths connecting the original node to the replication group, the FastReplica algorithm exploits $n \times n$ different Internet paths within the replication group where each path is used for transferring $1\over n$-th of the file. Thus, the impact of congestion on any particular Internet path participating in the schema is limited for a transfer of $1\over n$-th of the file. Additionally, FastReplica takes advantage of the upload and download bandwidth of the recipient nodes.