Project Design

In this Section:

	Introduction
	FEC Codes
	How does it work?
	The distribution server
	The download manager
	The data format
	The encoding procedure
	The decoding procedure

Abstract

Mirror sites enable client requests to be serviced by any of a number of servers, reducing load at individual servers and dispersing network load. Typically a client requests service from a single mirror site. We suggest a way for the client to access a file from multiple mirror sites in parallel to speed up the download. We have developed a technique that can deliver dramatic speedups as well as fault tolerance. Our approach doesn’t require a feedback from the client to the servers, thus speeding up the process even more.

Introduction

Downloading a large file from a heavily loaded server or through a highly congested link can be a painfully slow experience. The many proposed solutions for addressing these problems share a common theme: improve performance at the bottleneck.

For modem users, there is not much that can be done: to improve downloading time they must either upgrade to higher baud rates or settle for receiving distilled, lower bandwidth versions of the content they wish to access.

However even today, not all modems run at full speed due to network and servers loads, and much can be done to solve this problem as well.

For most of us, for whom the last mile is not the bottleneck, there are a wide variety of techniques to improve performance in the network and at the server. The most relevant to our discussion is the use of mirror sites. The mirroring approach deploys multiple servers storing the same data at geographically distributed locations, in an effort to both distribute the load of requests across servers and to make network connections shorter in length, thereby reducing network traffic. A limitation of current mirroring technology is that the user must choose a single mirror site from which to access data. While the choice of server may appear obvious when the number of mirror sites is small, some works indicate that the obvious choice is not always the best choice and dramatic performance improvements can result from more careful selection.

Our first objective is to enable users to download data from multiple mirror sites in parallel in order to reduce downloading time. This technique not only has the potential to improve performance substantially over a single server approach, but can eliminate the need for a complex selection process. We do so, by using forward error correction codes, as described below.

Forward Error Correction Codes

FEC techniques are generally based on the use of error detection and correction codes. These codes have been studied for a long time and are widely used in many fields of information processing, particularly in telecommunications systems. In the context of computer communications, error detection is generally provided by the lower protocol layers, which use checksums (such as CRC) to discard corrupted packets. (Error correcting codes are also used in special cases, e.g., in modems, wireless, satellite or otherwise noisy links, in order to make the residual error rate comparable to that of dedicated wired connections. One error correcting code is the Hamming code). The upper protocol layers have mainly to deal with erasures, i.e., missing packets in a stream. FEC codes were designed to allow recovery of the original data from the packets, which have arrived. FEC codes can be also extended to allow reception of data from multiple sources.

As mentioned above, Forward Error Correction (FEC) codes allow a recovery of data sent over an unreliable channel, where data packets can be received incorrectly or even lost. Sending a redundant data, which is sent along with the original data, does this. If the size of our data is k packets, FEC codes encode the data in such manner that the original data can be reconstructed from any k packets received. Multiple servers can send these packets to the receiver. A receiver could gather an encoded file in parallel, from multiple sources .As soon as any k packets arrive from any combination of the sources, the original file can be reconstructed.

The following figure illustrates a client downloading a file consisting of 3 packets from three servers, in parallel. Each server has 3 encoded packets of the original data. As soon as the client receives 3 packets, it has enough data to decode the file, and therefore aborts all open connections.

How does it work?

The scenario of a file download process should be as follows:

The user wants to download a file, either via a hyperlink on a web page, or directly (the user has the URL). The user then clicks on the hyperlink, or enters the URL in the browser window. This takes the user to an HTML page, containing a Java applet, which is responsible to the download process. The applet downloads the file, saves it to user’s hard drive, and optionally opens it in the browser window (if the browser can display this media type).

Our system consists of several parts:

	A distribution center, residing on a dedicated machine (either as a server or as a local application). This application will receive the file from the file creator; encode it using the FEC algorithm producing ‘s’ encoded files, when ‘s’ is the number of data servers (described below). The original file is divided into several chunks, and each chunk is encoded separately. The distribution application will upload the encoded chunks to the data servers. Each server will hold a full image of the original file, so the file can be downloaded even when there is only one data server available. The distribution center can work with up to 8 file servers (imposed by the limitations of the current implementation of our FEC algorithm).
	Data servers, that hold the encoded file chunks. The client will download the file from these servers using the HTTP protocol.
	The client is a Java applet, which manages the download process. The applet will initially download the data server list, containing the locations of all data chunks. Then, it will download and decode the chunks in the original chunk order. While the first chunk is being decoded, the second chunk will be downloaded in parallel, and so on. Finally, all the chunks are combined to reproduce the original file. The whole process is completely transparent to the user, who will only see a progress bar and a completion notification.

The distribution server

The distribution server will allow the content distributor to encode the content and upload it to a predefined group of servers, which will be specified as a configuration file.

Each chunk of the encoded data will be stored in a separate file, since this will make the download manager implementation simpler. Also not all servers allow downloading from an arbitrary position in the file (e.g. some proxy servers don’t support it). The names of the encoded files will be determined by the application based on the original file name. As mentioned above, there is a limit of 8 servers at this moment.

The distribution application will also prepare the HTML page that contains the client applet, which will manage the download process on the client machine. The HTML file will also have an embedded data regarding the locations of the data (the list of the mirror sites). This data will be passed to the applet when the applet is activated.

Note: the encoding procedure is done off-line.

The download manager

The user can start the file download either by following a link from a web page or by entering the URL of the download manager (the HTML page). When the user initializes the download process (by either method) it receives the HTML page, which was prepared (customized) by the distribution application for this particular file.

The HTML page contains a Java applet, which is the download manager and is described below.

First of all, the Java applet will parse the HTML page and extract the locations of the mirror sites. Then, we open HTTP connections to all the mirror sites, and start downloading the first chunk of data from all mirror sites in parallel. Now we wait until the download of the first chunk finishes, and then we start downloading the second chunk and decoding the first chunk in parallel. When the last chunk finishes downloading the user must wait until the decoding of the last chunk is over. This is the only time when the user actually feels the price of the decoding process. We try to minimize this time by choosing a smaller chunk size, although it is negligible when using fast CPUs and JVMs that support Just In Time compiling (JIT).

When the process finishes the downloaded file will be saved to the disk

How a chunk is being downloaded?

We receive the data from all the servers and as soon as we have enough data for the chunk we abort all existing connections. In order to avoid unnecessary packets to be sent over the network, we close all but the fastest connections when the amount of data we have already received is close enough to the chunk size. We close the last connection as soon as the last byte needed for the decoding arrives. However due to the TCP limitations more unnecessary data can be received (due to a large window size or fast network).

Since the opening of anew connection to a remote server (the three way handshake and sending and processing the request header), we open the connections for the next chunk before the current chunk is completely downloaded .The amount of data sent during the setup is not big and we save precious time which otherwise would be wasted.

If a connection to one of the servers fails, we try to open another connection to that server, and resume downloading from the position we stopped. If resume is not available, we might consider starting from the beginning, or give up using this server for the current chunk, depending on the amount of data we have already downloaded from this server, and the download progress on other connections.

The data format

Our basic unit of work is a packet (1KB). A strip is a sequence of packets, in our case, 32 packets. Therefore, the size of a strip is 32Kb. 32 strips are combined to form a chunk (1Mb).

Strips are the basic units of the encoding/decoding process, while chunks are the basic units of the download process. We store each chunk of encoded data in a separate file.

According to our FEC algorithm, each server must hold a complete (encoded) copy of data. Therefore the total size of the encoded data is the size of the original data multiplied by the number of the data servers.

Each encoded chunk of data is an interleaved sequence of encoded strips.

Suppose our chunk has only four strips, then the encoding procedure can be described as below:

The format of original data chunk:

	Packet 1	Packet 2	Packet 3	Packet 4	Packet 31	Packet 32
Strip A	A1	A2	A3			A32
Strip B	B1	B2	B3			B32
Strip C	C1	C2	C3			C32
Strip D	D1	D2	D3			D32

The chunk is stored in a file by rows (A1, A2… B1, … D1, …D32).

The format of the encoded data chunk:

	Strip A'	Strip B'	Strip C'	Strip D'
Packet 1	A'1	B'1	C'1	D'1
Packet 2	A'2	B'2	C'2	D'2
Packet 3	A'3	B'3	C'3	D'3
Packet 4

Packet 31
Packet 32	A'32	B'32	C'32	D'32

The encoded chunk is also stored in a file by rows (A'1, B'1, ... D'1, A'2, B'2 …..., A'32, .. D'32).

The number of encoded data chunks is equal to the number of servers, which means that the encoded chunk above will exist on a number of servers (of course it will be encoded differently for each server).

Now, let's focus on a single strip, "Strip A": Suppose 'n' is the number of servers. Then, a strip consisting of 32 packets is encoded into 'n' strips of 32 packets, a total of 32*'n' packets. Our encoding algorithm has a property, that the first 32 packets (which make a strip) of the 32*'n' encoded packets are exact copies of the original packets. This means that when these original packets arrive, we don't have to spend time to decode them. For example, if we consistently put all this "good" packets at the first server, then the whole chunk on the first server will be an exact copy of the original chunk.

However, it is unlikely that we will get all our data from the first server. If we still want to benefit from the "good" packets we must equally distribute them across the servers and place them at the beginning of each chunk. We do so by the following algorithm: (We don't alter the ordering of the strips inside the chunk (the interleaving alg.)). Let's number all the encoded packets of our strip from A₁ to A_'n'*32 (assuming 32 packets per strip). The first 32 packets, A₁ to A₃₂ are "good" packets, and are marked in bold. The encoded chunk will look like this: (4 servers, two shown, 3 strips per chunk):

Server 1 Server 2

	Strip A'	Strip B'	Strip C'	Strip A'	Strip B'	Strip C'
Packet 1	A'₁	B'₁	C'₁	A'₂	B'₂	C'₂
Packet 2	A'₅	B'₅	C'₅	A'₆	B'₆	C'₆

Packet 9	A'₃₃	B'₃₃	C'₃₃	A'₃₄	B'₃₄	C'₃₄

Packet 31
Packet 32	A'₁₂₇	B'₁₂₇	C'₁₂₇	A'₁₂₇	B'₁₂₇	C'₁₂₇

The encoding procedure

In the encoding procedure we take a file, and split it to chunks, and then split the chunks to strips. Lets focus on a single chunk.

Let ‘n’ be the number of servers. The encoding algorithm produces ‘n’ encoded strips out of one original strip. Each encoded strip will go to a different server. Then for each server, we collect all its strips and store them in an interleaved format described above.

For each packet we must know few things for the decoding procedure that will occur at the client:

1. The strip it belongs to.

2. It's index in the strip.

3. The server on which the strip resides.

We don’t have to specify these details explicitly for each packet. The client knows exactly, which server the packet came from, and the strip number can be calculated from the relative position of the packet in the chunk.

The decoding procedure

The decoding procedure reconstructs a strip from a collection of packets belonging to that strip. As we mentioned above, if the size of a strip is ‘k’ packets, then any ‘k’ packets from any server in any order can be used to reconstruct the strip (of course only if they belong to that strip). After all strips are decoded, we combine them back into a chunk, and append the chunk to the target file. When the last chunk is written, the download process is complete.

Please contact Genady or Nir regarding copyright issues
For problems or questions regarding this web contact the members.
Last updated: Monday, September 20, 1999.