Forward Error Correcting Methods.

The Digital Fountain system described by Byers et al. assumes a multicast channel for distributing data to multiple clients [11]. Data are encoded using forward error correcting (FEC) methods, which allows a file to be reconstructed using a specific number of distinct blocks. This approach eliminates the need for acknowledgment messages, and improves service scalability. The system can be extended to provide large file transport to a client from multiple collaborating sources in overlay networks [10]. For congestion control, receiver-driven layered multicast has been proposed based on multi-layer data encoding and selective forwarding of layer subsets to constrained network links [26].

In a unicast network, FEC encoding can be applied for improved caching efficiency at the server [36]. Since a minimum number of any distinct blocks can be used for reconstructing a transmitted file, the FEC codes make the data retrieved from the disk useful to multiple clients concurrently served. Retransmissions triggered by packet losses can be satisfied with any blocks not yet sent to the client, and are not limited to the actually lost blocks. Thus, caching of transmitted data packets on the sender becomes unnecessary. However, channel transmission efficiency requires avoidance of duplicate packets received by an individual client [11,36]. In a typical heterogeneous environment, where client receiving rates can differ by several orders of magnitude, the encoded version of the transmitted file should be accordingly orders of magnitude larger than the original. This cost scales with the skew in client transfer rates. Recent theoretical work begins to address this problem [25]; if a satisfactory solution is found, then FEC could meet our objectives for downloading large files with a high degree of sharing as well as reducing total network impact, assuming multicasting is available.

In the present paper, we demonstrate that it is possible to directly address the problem of sending unique data to each client according to its individual receiving rate without FEC codes, and at the same time maximize the advantage from data sharing across concurrent requests within a unicasting environment. If multicast is available, Circus can also use it to send shared blocks to all clients who will receive it, but its choice is to improve download performance and reduce the storage system cost to achieve a given network bandwidth.