JC's updated changes to the INFOCOM paper.

diff --git a/docs/paper/paper.tex b/docs/paper/paper.tex
index f8cb8fbbc2418047abc2350a9f357abcf61638e8..0bf3df7243ef812d8b3c48d3f5328a5ac68102d8 100644 (file)
--- a/docs/paper/paper.tex
+++ b/docs/paper/paper.tex
@@ -34,22 +34,28 @@ Email: jcliu@cs.sfu.ca}}
 \maketitle\r
 \r
 \begin{abstract}\r
 \maketitle\r
 \r
 \begin{abstract}\r

-A large amount of free software packages are available over the\r
-Internet from many different distributors. Most of these\r
-distributors use the traditional client-server model to handle\r
-requests from users. However, there is an excellent opportunity to\r
-use peer-to-peer techniques to reduce the cost of much of this\r
-distribution, especially due to the altruistic nature of many of\r
-these users. There are no existing solutions suitable for this\r
-situation, so we present a new technique for satisfying the needs of\r
-this P2P distribution which is generally applicable to many of\r
-these distributors' systems. Our method makes use of a DHT for\r
-storing the location of peers, using the cryptographic hash of the\r
-package as a key. To show the simplicity and functionality of our model, we\r
-implement a solution for the distribution of Debian software\r
-packages, including details on the DHT customizations and system optimizations needed. Finally, we\r
-analyze our system to determine how it is performing and what effect\r
-it is having.\r
+The Internet has become an cost-effective\r
+vehicle for software development and release, particular in the free software society.\r
+Given the free nature of these software, there are often a number of users\r
+motivated by altruism to help out with the distribution, so as to promote the healthy development\r
+of this voluntary society. It is thus naturally expected that peer-to-peer distribution can be implemented,\r
+which scale well with large user bases and can easily explore the network resources made available by\r
+the volunteers.\r
+\r
+Unfortunately, this application scenario has many unique characteristics, which\r
+make a straightforward adoption of such existing peer-to-peer systems for file sharing as BitTorrent suboptimal. In particular,\r
+a software release often consists of a large number of packages, which are difficult to be distributed individually, but the archive is\r
+too large to be distributed in its entirety. The packages are also being constantly\r
+updated by the loosely-managed developed; yet the interest in a particular version of a package can be very\r
+limited depending on the computer platforms and operating systems used.\r
+\r
+In this paper, we propose a novel peer-to-peer assisted distributor design that\r
+addresses the above challenges. It enhances the existing distribution systems by providing compatible and yet more efficient downloading and updating services\r
+for software packages. Our design leads to \texttt{apt-p2p}, a practical implementation that extends the popular \texttt{apt} distributor.  \texttt{apt-p2p}  has been used in conjuction with Debian-based distribution of Linux\r
+software packages and will also be available in the next release of Ubuntu. We have addressed the key design issues in \texttt{apt-p2p}, including indexing table customization,\r
+response time reduction, and multi-value extension. They together ensure\r
+that the altruistic users' resources be effectively utilized and thus significantly reduce the currently\r
+sheer bandwidth requirements of hosting the software, as confirmed by our existing real user statistics.\r

 \end{abstract}\r
 \r
 %%%%%%%%%%%%%%%%%%%%%%%%%%%  Section  %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 \end{abstract}\r
 \r
 %%%%%%%%%%%%%%%%%%%%%%%%%%%  Section  %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r


@@ -57,39 +63,45 @@ it is having.
 \section{Introduction}\r
 \label{intro}\r
 \r
 \section{Introduction}\r
 \label{intro}\r
 \r

-There are a large number of free software package distributors using\r
-package distribution systems over the Internet to distribute\r
-software to their users. These distributors have developed many\r
-different methods for this distribution, but they almost exclusively\r
-use a client-server model to satisfy user requests. The popularity\r
-and number of users results in a large number of requests, which\r
-usually requires a network of mirrors to handle. Due to the free\r
-nature of this software, many users are willing and able to\r
-contribute upload bandwidth to this distribution, but have no\r
-current way to do this.\r
-\r
-We present a new peer-to-peer distribution model to meet these\r
-demands. It is based on many previous implementations of successful\r
-peer-to-peer protocols, especially distributed hash tables (DHT) and\r
-BitTorrent. The model relies on the pre-existence of cryptographic\r
-hashes of the packages, which uniquely identify it for a\r
-request from other peers. If the peer-to-peer download fails, then\r
-the original request to the server is used as a fallback to prevent\r
-any dissatisfaction from users. The peer can then share this new\r
-package with others through the P2P system.\r
-\r
-First, we examine the opportunity that is available for many of\r
-these free software package distributors. We present an overview of\r
-a system that would efficiently satisfy the demands of a large\r
-number of users, and should significantly reduce the currently\r
-substantial bandwidth requirements of hosting this software. We then\r
-present an example implementation based on the Debian package\r
-distribution system. This implementation will be used by a large\r
-number of users, and serves as an example for other free software\r
-distributors of the opportunity that can be met with such a system.\r
-Finally, we analyze our currently deployed implementation to\r
+With the widespread penetration of broadband accesses, the Internet has become an cost-effective\r
+vehicle for software development and release. This is particularly true for the free software\r
+society whose developers and users are worldwide distributed and work asynchronously. The ever increasing power of\r
+modern programming languages, computer platforms, and operating systems has made these software extremely large and complex,\r
+which are often divided into a huge number of small packages.\r
+Together with their popularity among users,\r
+an efficient and reliable management and distribution of these software over the Internet has become a challenging task.\r
+\r
+The existing distributor for free software are mostly based on the client/server model, e.g.,\r
+the Advanced Package Tool (\texttt{apt}) for Linux, which suffers from the well-known bottleneck problem.\r
+Given the free nature of these software, there are often a number of users\r
+motivated by altruism to help out with the distribution, so as to promote the healthy development\r
+of this voluntary society.\r
+We thus naturally expect that peer-to-peer distribution can be implemented in\r
+this context, which scale well with large user bases and can easily explore the network resources made available by\r
+the volunteers.\r
+\r
+Unfortunately, this application scenario has many unique characteristics, which\r
+make a straightforward adoption of such existing peer-to-peer systems for file sharing as BitTorrent suboptimal. In particular,\r
+there are too many packages to distribute each individually, but the archive is\r
+too large to distribute in its entirety. The packages are also being constantly\r
+updated by the loosely-managed developed; yet the interest in a particular version of a package can be very\r
+limited. They together make it very difficult to efficiently create and manage torrents/trackers. The random downloading nature of BitTorrent-like systems is also different from the\r
+sequential order used in existing software package distributors. This in turn suppresses interaction with users\r
+given the difficulty in tracking speed and downloading progress.\r
+\r
+In this paper, we propose a novel peer-to-peer assisted distributor design that\r
+addresses the above challenges. It enhances the existing distribution systems by providing compatible and yet more efficient downloading and updating services\r
+for software packages. Our design leads to the development of \texttt{apt-p2p}, a practical implementation based on the Debian \footnote{Debian - The Universal Operating System: {\it http://www.debian.org/}} package\r
+distribution system.  We have addressed the key design issues in \texttt{apt-p2p}, including indexing table customization,\r
+response time reduction, and multi-value extension. They together ensure\r
+that the altruistic users' resources be effectively utilized and thus significantly reduce the currently\r
+sheer bandwidth requirements of hosting the software.\r
+\r
+\texttt{apt-p2p}  has been used in conjuction with Debian-based distribution of Linux\r
+software packages and will also be available in the next release of Ubuntu. We have evaluated our currently deployment  to\r

 determine how effective it is at meeting our goals, and to see what\r
 determine how effective it is at meeting our goals, and to see what\r

-effect it is having on the Debian package distribution system.\r
+effect it is having on the Debian package distribution system. In particular, our existing real user statistics\r
+have suggested that it responsively interacts with clients and substantially reduces server cost.\r

 \r
 The rest of this paper is organized as follows. The background and motivation are presented in Section~\ref{situation}, including an analysis of BitTorrent's use for this purpose in Section~\ref{bittorrent}. We propose\r
 our solution in Section~\ref{opportunity}. We then detail our sample\r
 \r
 The rest of this paper is organized as follows. The background and motivation are presented in Section~\ref{situation}, including an analysis of BitTorrent's use for this purpose in Section~\ref{bittorrent}. We propose\r
 our solution in Section~\ref{opportunity}. We then detail our sample\r


@@ -103,12 +115,12 @@ Section~\ref{conclusions} concludes the paper and offers some future directions.
 \section{Background and Motivations}\r
 \label{situation}\r
 \r
 \section{Background and Motivations}\r
 \label{situation}\r
 \r

-In the free software society, there are a large number of groups using the Internet to \r
+In the free software society, there are a large number of groups using the Internet to\r

 collaboratively develop and release their software. The ever increasing power of\r
 modern programming languages and operating systems has made this software, like commercial software, extremely large and complex, though it is often\r
 collaboratively develop and release their software. The ever increasing power of\r
 modern programming languages and operating systems has made this software, like commercial software, extremely large and complex, though it is often\r

-distributed in many small units (packages). Together with their popularity among users, \r
-an efficient and reliable management and distribution of these packages over the Internet has become a daunting task. In this section, we offer concrete examples illustrating the \r
-unique challenges in this context. \r
+distributed in many small units (packages). Together with their popularity among users,\r
+an efficient and reliable management and distribution of these packages over the Internet has become a daunting task. In this section, we offer concrete examples illustrating the\r
+unique challenges in this context.\r

 \r
 \subsection{Free Software Package Distributors}\r
 \label{examples}\r
 \r
 \subsection{Free Software Package Distributors}\r
 \label{examples}\r


@@ -153,15 +165,15 @@ typical of free software hosting facilities that are open to anyone
 to use, such as SourceForge.\r
 \r
 \r
 to use, such as SourceForge.\r
 \r
 \r

-Given the free nature of this software, there are often a number of users \r
+Given the free nature of this software, there are often a number of users\r

 motivated by altruism to want to help out with the distribution.\r
 This is particularly true considering that many of this software is used by\r
 groups that are staffed mostly, or sometimes completely, by\r
 motivated by altruism to want to help out with the distribution.\r
 This is particularly true considering that many of this software is used by\r
 groups that are staffed mostly, or sometimes completely, by\r

-volunteers. They are thus motivated to contribute their network resources, so as to promote the healthy development \r
+volunteers. They are thus motivated to contribute their network resources, so as to promote the healthy development\r

 of the volunteer community that released the software.\r
 of the volunteer community that released the software.\r

-We also naturally expect that peer-to-peer distribution can be implementation in \r
+We also naturally expect that peer-to-peer distribution can be implementation in\r

 this context, which scale well with large user bases and can easily explore the network resources made available by\r
 this context, which scale well with large user bases and can easily explore the network resources made available by\r

-the volunteers. \r
+the volunteers.\r

 \r
 \r
 \r
 \r
 \r
 \r


@@ -193,7 +205,7 @@ For example, Figure~\ref{size_CDF} shows the size of the packages in the
 current Debian distribution. While 80\% of the packages are less than\r
 512~KB, some of the packages are hundreds of megabytes. The entire\r
 archive consists of 22,298 packages and is approximately 119,000 MB\r
 current Debian distribution. While 80\% of the packages are less than\r
 512~KB, some of the packages are hundreds of megabytes. The entire\r
 archive consists of 22,298 packages and is approximately 119,000 MB\r

-in size. Most of the packages are to be installed in any computer environment, but there are \r
+in size. Most of the packages are to be installed in any computer environment, but there are\r

 also OS- or architecture-specific packages.\r
 \r
 \subsubsection{Package Updates}\r
 also OS- or architecture-specific packages.\r
 \r
 \subsubsection{Package Updates}\r


@@ -226,7 +238,7 @@ asynchronously on a worldwide scale.
 \subsubsection{Limited Interest}\r
 \r
 Finally, though there are a large number of packages and a large number of\r
 \subsubsection{Limited Interest}\r
 \r
 Finally, though there are a large number of packages and a large number of\r

-users, the interest in a particular version of a package can be very \r
+users, the interest in a particular version of a package can be very\r

 limited. Specifically, there are core packages that every user has to download, but most\r
 packages would fall in the category of optional or extra, and so are\r
 interesting to only a limited number of people.\r
 limited. Specifically, there are core packages that every user has to download, but most\r
 packages would fall in the category of optional or extra, and so are\r
 interesting to only a limited number of people.\r


@@ -247,13 +259,13 @@ users.
 \r
 \subsubsection{Interactive Users}\r
 \r
 \r
 \subsubsection{Interactive Users}\r
 \r

-The package management software that downloads packages displays\r
+Given the relatively long time for software package downloading, existing package management systems generally display\r

 some kind of indication of speed and completeness for users to\r
 some kind of indication of speed and completeness for users to\r

-watch. Since previous client-server downloads occurred in a sequential\r
+monitor. Since previous client-server downloads occurred in a sequential\r

 fashion, the package management software also measures the speed\r
 fashion, the package management software also measures the speed\r

-based on sequential downloading. This requires the peer-to-peer\r
-solution to be reasonably responsive at retrieving packages\r
-sequentially.\r
+based on sequential downloading. To offer comparable user experience, it is naturally to expect that\r
+the new peer-to-peer solution be reasonably responsive at retrieving packages,\r
+preferably enabling sequential downloading order, too.\r

 \r
 \subsection{Why BitTorrent Doesn't Work Well}\r
 \label{bittorrent}\r
 \r
 \subsection{Why BitTorrent Doesn't Work Well}\r
 \label{bittorrent}\r


@@ -264,10 +276,10 @@ images. This straightforward use however can be very ineffective, as it requires
 peers to download large numbers of packages that they are not\r
 interested in, and prevents them from updating to new packages\r
 without downloading another image containing a lot of the same\r
 peers to download large numbers of packages that they are not\r
 interested in, and prevents them from updating to new packages\r
 without downloading another image containing a lot of the same\r

-packages they already have. \r
+packages they already have.\r

 \r
 An alternative is to create torrents tracking smaller groups of packages. Unfortunately, we find that this enhancement can be\r
 \r
 An alternative is to create torrents tracking smaller groups of packages. Unfortunately, we find that this enhancement can be\r

-quite difficult given the unique characteristic of free software packages. \r
+quite difficult given the unique characteristic of free software packages.\r

 First, there is no obvious way to divide the packages into torrents.\r
 Most of the packages are too small, and there are too many packages\r
 in the entire archive to create individual torrents for each one.\r
 First, there is no obvious way to divide the packages into torrents.\r
 Most of the packages are too small, and there are too many packages\r
 in the entire archive to create individual torrents for each one.\r


@@ -288,13 +300,13 @@ this problem. In particular, BitTorrent's fixed piece sizes (usually 512 KB) tha
 boundaries are bigger than many of the packages in the archive. This\r
 will waste peers' downloading bandwidth as they will end up\r
 downloading parts of other packages just to get the piece that\r
 boundaries are bigger than many of the packages in the archive. This\r
 will waste peers' downloading bandwidth as they will end up\r
 downloading parts of other packages just to get the piece that\r

-contains the package they do want. \r
+contains the package they do want.\r

 Finally, note that BitTorrent downloads files\r
 randomly, which does not work well with the interactive package\r
 management tools expectation of sequential downloads.\r
 \r
 On the other hand, there are aspects of BitTorrent that are no\r
 Finally, note that BitTorrent downloads files\r
 randomly, which does not work well with the interactive package\r
 management tools expectation of sequential downloads.\r
 \r
 On the other hand, there are aspects of BitTorrent that are no\r

-longer needed in a system such as this one. With altruistic peers\r
+longer critical. Specifically, with altruistic peers\r

 and all files being available without uploading, incentives to share\r
 become a less important issue. Also, the availability of seeds are\r
 not critical either, as the mirror sites serve in that capacity\r
 and all files being available without uploading, incentives to share\r
 become a less important issue. Also, the availability of seeds are\r
 not critical either, as the mirror sites serve in that capacity\r


@@ -305,12 +317,12 @@ already.
 \section{Peer-to-Peer Assisted Distributor: An Overview}\r
 \label{opportunity}\r
 \r
 \section{Peer-to-Peer Assisted Distributor: An Overview}\r
 \label{opportunity}\r
 \r

-We assume that the user is attempting to download packages from a\r
-server, using package management software to find and retrieve the\r
-packages. Further, we assume that the requests from the user to the\r
-server are able to be proxied by our peer-to-peer program, and that\r
-the server is always available and has all of the package files.\r
-Finally, the cryptographic hash of the packages must be available\r
+We now present the design of our peer-to-peer assisted distributor for free software package releases and\r
+updates. A key principle in our design is that the new functionalities implemented in our distributor should be transparent to users,\r
+thus offering the same experience as using conventional software management systems, despite enhanced efficiency.\r
+That said, we assume that the user is still attempting to download packages from a\r
+server, but the requests will be proxied by our peer-to-peer program. The server is always available and has all of the package files.\r
+In addition, the cryptographic hash of the packages will be available\r

 separately from the package itself, and is usually contained in an\r
 \emph{index} file which also contains all the packages' names,\r
 locations and sizes.\r
 separately from the package itself, and is usually contained in an\r
 \emph{index} file which also contains all the packages' names,\r
 locations and sizes.\r


@@ -322,7 +334,7 @@ locations and sizes.
 \label{model}\r
 \end{figure}\r
 \r
 \label{model}\r
 \end{figure}\r
 \r

-Our model for using P2P to enhance such a system is shown in\r
+Our model for using peer-to-peer to enhance package distribution is shown in\r

 Figure~\ref{model}. As shown in Phase~1, our program will act as a\r
 proxy (1,2), downloading (3) and caching all files communicated\r
 between the user and the server (4). It will therefore also have\r
 Figure~\ref{model}. As shown in Phase~1, our program will act as a\r
 proxy (1,2), downloading (3) and caching all files communicated\r
 between the user and the server (4). It will therefore also have\r


@@ -330,7 +342,7 @@ available the index files containing the cryptographic hashes all
 packages. Later, in Phase~2, upon receiving a request from the user\r
 to download a package (5), our program will search the index files\r
 for the package being requested and find its hash (6). This hash can\r
 packages. Later, in Phase~2, upon receiving a request from the user\r
 to download a package (5), our program will search the index files\r
 for the package being requested and find its hash (6). This hash can\r

-then be looked up recursively in the DHT (7), which will return a\r
+then be looked up recursively in an indexing structure (a Distributed Hash Table [] in our implementation) (7), which will return a\r

 list of peers that have the package already (8). The package can\r
 then be downloaded from the peers (11,12), it can be verified using\r
 the hash (13), and if valid can be returned to the user (14). The\r
 list of peers that have the package already (8). The package can\r
 then be downloaded from the peers (11,12), it can be verified using\r
 the hash (13), and if valid can be returned to the user (14). The\r


@@ -379,10 +391,10 @@ distributor's server.
 \subsection{Implementation Options}\r
 \label{imp_options}\r
 \r
 \subsection{Implementation Options}\r
 \label{imp_options}\r
 \r

-There are several ways to implement the desired P2P functionality\r
+There are several ways to implement the desired peer-to-peer functionality\r

 into the existing package management software. The functionality can\r
 be directly integrated through modifications to the software, though\r
 into the existing package management software. The functionality can\r
 be directly integrated through modifications to the software, though\r

-this could be difficult as the P2P functionality should be running\r
+this could be difficult as the peer-to-peer functionality should be running\r

 at all times. This is needed both for efficient lookups and to\r
 support uploading of already downloaded packages. Unfortunately, the\r
 package management tools typically only run until the download and\r
 at all times. This is needed both for efficient lookups and to\r
 support uploading of already downloaded packages. Unfortunately, the\r
 package management tools typically only run until the download and\r


@@ -390,11 +402,11 @@ install request is complete.
 \r
 Many of the package management software implementations use HTTP\r
 requests from web servers to download the packages, which makes it\r
 \r
 Many of the package management software implementations use HTTP\r
 requests from web servers to download the packages, which makes it\r

-possible to implement the P2P aspect as an almost standard HTTP\r
+possible to implement the peer-to-peer aspect as an almost standard HTTP\r

 caching proxy. This proxy will run as a daemon in the background,\r
 listening for requests from the package management tool for package\r
 files, as well as serving (uploading) cached package to other peers.\r
 caching proxy. This proxy will run as a daemon in the background,\r
 listening for requests from the package management tool for package\r
 files, as well as serving (uploading) cached package to other peers.\r

-It will get uncached requests first from the P2P system, or\r
+It will get uncached requests first from the peer-to-peer system, or\r

 fall back to the normal HTTP request from a server should it not\r
 be found. For methods that don't use HTTP requests, other types of\r
 proxies may also be possible.\r
 fall back to the normal HTTP request from a server should it not\r
 be found. For methods that don't use HTTP requests, other types of\r
 proxies may also be possible.\r


@@ -404,7 +416,7 @@ proxies may also be possible.
 \r
 Although not necessary, we recommend implementing a download\r
 protocol that is similar to the protocol used to fetch packages from\r
 \r
 Although not necessary, we recommend implementing a download\r
 protocol that is similar to the protocol used to fetch packages from\r

-the distributor's servers. This simplifies the P2P program, as it\r
+the distributor's servers. This simplifies the peer-to-peer program, as it\r

 can then treat peers and mirrors almost identically when requesting\r
 packages. In fact, the mirrors can be used when there are only a few\r
 slow peers available for a file to help speed up the download\r
 can then treat peers and mirrors almost identically when requesting\r
 packages. In fact, the mirrors can be used when there are only a few\r
 slow peers available for a file to help speed up the download\r


@@ -422,7 +434,7 @@ available.
 \r
 Since the package management system only stores a hash of the entire\r
 package, and not of pieces of that package, we will need to be able\r
 \r
 Since the package management system only stores a hash of the entire\r
 package, and not of pieces of that package, we will need to be able\r

-to store and retrieve these piece hashes using the P2P protocol. In\r
+to store and retrieve these piece hashes using the peer-to-peer protocol. In\r

 addition to storing the file download location in the DHT (which\r
 would still be used for small files), a peer will store a\r
 \emph{torrent string} containing the peer's hashes of the pieces of\r
 addition to storing the file download location in the DHT (which\r
 would still be used for small files), a peer will store a\r
 \emph{torrent string} containing the peer's hashes of the pieces of\r


@@ -439,25 +451,20 @@ the downloaded package.
 We have created a sample implementation that functions as described\r
 in section \ref{opportunity}, and is freely available for other\r
 distributors to download and modify \cite{apt-p2p}. This software,\r
 We have created a sample implementation that functions as described\r
 in section \ref{opportunity}, and is freely available for other\r
 distributors to download and modify \cite{apt-p2p}. This software,\r

-called \texttt{apt-p2p}, interacts with the \texttt{apt} tool which\r
-is found in most Debian-based Linux distributions. \texttt{apt} uses\r
-SHA1 hashes to verify most downloaded files, including the large\r
-index files that contain the hashes of the individual packages. We\r
-chose this distribution system as it is familiar to us, it allows\r
-software contributions, and there are interesting statistics\r
+called \texttt{apt-p2p}, interacts with the popular \texttt{apt} tool. This tool \r
+is found in most Debian-based Linux distributions, with related statistics\r

 available for analyzing the popularity of the software packages\r
 \cite{popcon}.\r
 \r
 Since all requests from \texttt{apt} are in the form of HTTP downloads from a\r
 available for analyzing the popularity of the software packages\r
 \cite{popcon}.\r
 \r
 Since all requests from \texttt{apt} are in the form of HTTP downloads from a\r

-server, the implementation takes the form of a caching HTTP proxy.\r
+server, our implementation takes the form of a caching HTTP proxy.\r

 Making a standard \texttt{apt} implementation use the proxy is then\r
 as simple as prepending the proxy location and port to the front of\r
 the mirror name in \texttt{apt}'s configuration file (i.e.\r
 ``http://localhost:9977/mirrorname.debian.org/\ldots'').\r
 \r
 We created a customized DHT based on Khashmir \cite{khashmir}, which\r
 Making a standard \texttt{apt} implementation use the proxy is then\r
 as simple as prepending the proxy location and port to the front of\r
 the mirror name in \texttt{apt}'s configuration file (i.e.\r
 ``http://localhost:9977/mirrorname.debian.org/\ldots'').\r
 \r
 We created a customized DHT based on Khashmir \cite{khashmir}, which\r

-is an implementation of Kademlia \cite{kademlia} using methods\r
-familiar to BitTorrent developers. Khashmir is also the same DHT\r
+is an implementation of Kademlia \cite{kademlia}. Khashmir is also the same DHT\r

 implementation used by most of the existing BitTorrent clients to\r
 implement trackerless operation. The communication is all handled by\r
 UDP messages, and RPC (remote procedure call) requests and responses\r
 implementation used by most of the existing BitTorrent clients to\r
 implement trackerless operation. The communication is all handled by\r
 UDP messages, and RPC (remote procedure call) requests and responses\r


@@ -476,7 +483,9 @@ for the proxy also doubles as the server listening for requests for
 downloads from other peers. All peers support HTTP/1.1, both in the\r
 server and the client, which allows for pipelining of multiple\r
 requests to a peer, and the requesting of smaller pieces of a large\r
 downloads from other peers. All peers support HTTP/1.1, both in the\r
 server and the client, which allows for pipelining of multiple\r
 requests to a peer, and the requesting of smaller pieces of a large\r

-file using the HTTP Range request header.\r
+file using the HTTP Range request header. Like in \texttt{apt}, \r
+SHA1 hashes are then used to verify downloaded files, including the large\r
+index files that contain the hashes of the individual packages. \r

 \r
 %%%%%%%%%%%%%%%%%%%%%%%%%%%  Section  %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 \r
 \r
 %%%%%%%%%%%%%%%%%%%%%%%%%%%  Section  %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 \r


@@ -492,7 +501,7 @@ up queries, allowed the storage of multiple values for each key, and
 incorporated some improvements from BitTorrent's tracker-less DHT\r
 implementation.\r
 \r
 incorporated some improvements from BitTorrent's tracker-less DHT\r
 implementation.\r
 \r

-\subsection{DHT Background}\r
+\subsection{Kademlia DHT Background}\r

 \label{dht}\r
 \r
 DHT's operate by storing (\emph{key}, \emph{value}) pairs in a\r
 \label{dht}\r
 \r
 DHT's operate by storing (\emph{key}, \emph{value}) pairs in a\r


@@ -563,7 +572,7 @@ torrent string as they require 5 to 70 pieces. Finally, there are
 only 62 packages that require more than 70 pieces, and so will\r
 require a separate request to a peer for the torrent string.\r
 \r
 only 62 packages that require more than 70 pieces, and so will\r
 require a separate request to a peer for the torrent string.\r
 \r

-\subsection{Response Time}\r
+\subsection{Response Time Optimization}\r

 \label{response_time}\r
 \r
 Many of our customizations to the DHT have been to try and improve\r
 \label{response_time}\r
 \r
 Many of our customizations to the DHT have been to try and improve\r


@@ -636,7 +645,7 @@ constant as it is a configuration option, but can be much larger if
 the node is too overloaded for the program to be able to check for a\r
 timeout very often.\r
 \r
 the node is too overloaded for the program to be able to check for a\r
 timeout very often.\r
 \r

-\subsection{Multiple Values}\r
+\subsection{Extension with Multiple Values}\r

 \label{multiple_values}\r
 \r
 The original design of Kademlia specified that each key would have\r
 \label{multiple_values}\r
 \r
 The original design of Kademlia specified that each key would have\r


@@ -671,60 +680,7 @@ abort the search once it has found enough values in some nodes, or
 it could choose to only request values from the nodes that are\r
 closest to the key being searched for.\r
 \r
 it could choose to only request values from the nodes that are\r
 closest to the key being searched for.\r
 \r

-\subsection{\textbf{OPTIONAL}: BitTorrent's Improvements}\r
-\label{bittorrent_dht}\r
-\r
-In the several years that some BitTorrent clients have been using a\r
-Kademlia-based DHT for tracker-less operation, the developers have\r
-made many enhancements which we can take advantage of. One of the\r
-most important is a security feature added to stop malicious nodes\r
-from subscribing other nodes as downloaders. When a node issues a\r
-request to another node to store its download info for that key, it\r
-must include a \emph{token} returned by the storing node in a recent\r
-\texttt{find\_node} request. The token is created by hashing the IP\r
-address of the requesting peer with a temporary secret that expires\r
-after several minutes. This prevents the requesting peer from faking\r
-its IP address in the store request, since it must first receive a\r
-response from a \texttt{find\_node} on that IP.\r
-\r
-We also made some BitTorrent-inspired changes to the parameters of\r
-the DHT originally specified by the authors of Kademlia. Since, as\r
-we will show later, peers stay online in our system for much longer\r
-periods of time, we reduced Kademlia's \emph{k} value from 20 to 8.\r
-The value is supposed to be large enough such that any given\r
-\emph{k} nodes are unlikely to fail within an hour of each other,\r
-which is very unlikely in our system given the long uptimes of\r
-nodes (see Figure~\ref{duration_online_1} in Section~\ref{analysis}.\r
-We also increased the number of concurrent outstanding\r
-requests allowed from 3 to 6 to speed up the recursive key finding\r
-processes.\r
-\r
-\subsection{\textbf{OPTIONAL}: Other Changes}\r
-\label{other_changes}\r
-\r
-We added one other new RPC request that nodes can make:\r
-\texttt{join}. This request is only sent on first loading the DHT,\r
-and is usually only sent to the bootstrap nodes that are listed for\r
-the DHT. These bootstrap nodes will respond to the request with the\r
-requesting peer's IP and port, so that the peer can determine what\r
-its oustide IP address is and whether port translation is being\r
-used. In the future, we hope to add functionality similar to STUN\r
-\cite{STUN}, so that nodes can detect whether they are NATted and\r
-take appropriate steps to circumvent it.\r

 \r
 \r

-In addition, we have allowed peers to store values in the DHT, even\r
-if the hash they are using is not the correct length. Most of the\r
-keys used in the DHT are based on the SHA1 hash, and so they are 20\r
-bytes in length. However, some files in the targetted Debian package\r
-system are only hashed using the MD5 algorithm, and so the hashes\r
-retrieved from the server are 16 bytes in length. The DHT will still\r
-store values using these keys by padding the end of them with zeroes\r
-to the proper length, as the loss of uniqueness from the 4 less\r
-bytes is not an issue. Also, the DHT will happily store hashes that\r
-are longer than 20 bytes, such as those from the 32 byte SHA256\r
-algorithm, by truncating them to the correct length. Since the\r
-requesting peer will have the full length of the hash, this will not\r
-affect its attempt to verify the downloaded file.\r

 \r
 %%%%%%%%%%%%%%%%%%%%%%%%%%%  Section  %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 \r
 \r
 %%%%%%%%%%%%%%%%%%%%%%%%%%%  Section  %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 \r


@@ -767,7 +723,16 @@ recently, which will cause the peer to wait for a timeout to occur
 unable to contribute any upload bandwidth to other peers, as all\r
 requests for packages from them will also timeout. From\r
 Figure~\ref{walker_peers}, we see that approximately half of all\r
 unable to contribute any upload bandwidth to other peers, as all\r
 requests for packages from them will also timeout. From\r
 Figure~\ref{walker_peers}, we see that approximately half of all\r

-peers suffered from this restriction.\r
+peers suffered from this restriction. To address this problem, we added one other new RPC request that nodes can make:\r
+\texttt{join}. This request is only sent on first loading the DHT,\r
+and is usually only sent to the bootstrap nodes that are listed for\r
+the DHT. These bootstrap nodes will respond to the request with the\r
+requesting peer's IP and port, so that the peer can determine what\r
+its oustide IP address is and whether port translation is being\r
+used. In the future, we hope to add functionality similar to STUN\r
+\cite{STUN}, so that nodes can detect whether they are NATted and\r
+take appropriate steps to circumvent it.\r
+\r

 \r
 \begin{figure}\r
 \centering\r
 \r
 \begin{figure}\r
 \centering\r


@@ -784,7 +749,7 @@ long period in the system.
 Indeed, we find that 50\% of connections last longer than 5\r
 hours, and 20\% last longer than 10 hours. These connections are\r
 much longer than those reported by Saroiu et. al. \cite{saroiu2001}\r
 Indeed, we find that 50\% of connections last longer than 5\r
 hours, and 20\% last longer than 10 hours. These connections are\r
 much longer than those reported by Saroiu et. al. \cite{saroiu2001}\r

-for other P2P systems, which had 50\% of Napster and Gnutella\r
+for other peer-to-peer systems, which had 50\% of Napster and Gnutella\r

 sessions lasting only 1 hour.\r
 \r
 \begin{figure}\r
 sessions lasting only 1 hour.\r
 \r
 \begin{figure}\r


@@ -831,7 +796,7 @@ the system, will stay online for another 6 hours.}
 \label{duration_online_6}\r
 \end{figure}\r
 \r
 \label{duration_online_6}\r
 \end{figure}\r
 \r

-\textbf{OPTIONAL}: Since our peers are much longer-lived than other P2P systems, we\r
+\textbf{OPTIONAL}: Since our peers are much longer-lived than other peer-to-peer systems, we\r

 also looked at the fraction of peers that stay online for another 6\r
 hours. Figure~\ref{duration_online_6} shows that over 60\% of peers\r
 that are online for 10 hours will stay online for another 6.\r
 also looked at the fraction of peers that stay online for another 6\r
 hours. Figure~\ref{duration_online_6} shows that over 60\% of peers\r
 that are online for 10 hours will stay online for another 6.\r


@@ -927,8 +892,8 @@ considers all the files available to users to download, and makes
 use of the existing infrastructure unmodified.\r
 \r
 \textbf{OPTIONAL}: Others have also used DHTs to support this type of functionality.\r
 use of the existing infrastructure unmodified.\r
 \r
 \textbf{OPTIONAL}: Others have also used DHTs to support this type of functionality.\r

-Kenosis \cite{kenosis} is a P2P Remote Procedure Call\r
-client also based on the Kademlia DHT, but it is meant as a P2P\r
+Kenosis \cite{kenosis} is a peer-to-peer Remote Procedure Call\r
+client also based on the Kademlia DHT, but it is meant as a peer-to-peer\r

 primitive system on which other tools can be built, and so it has no\r
 file sharing functionality at all. Many have used a DHT as a drop-in\r
 replacement for the tracker in a BitTorrent system\r
 primitive system on which other tools can be built, and so it has no\r
 file sharing functionality at all. Many have used a DHT as a drop-in\r
 replacement for the tracker in a BitTorrent system\r


@@ -983,26 +948,25 @@ users.
 \section{Conclusion and Future Work}\r
 \label{conclusions}\r
 \r
 \section{Conclusion and Future Work}\r
 \label{conclusions}\r
 \r

-We have designed a generally applicable peer-to-peer content\r
-distribution model to be used by many of the free software\r
-distributors operating today. It makes use of already existing\r
-features of most package management systems to create a\r
-peer-to-peer distribution that should substantially reduce the costs\r
-of hosting the software packages.\r
-\r
-We have also implemented our design in freely available software to\r
-be used in conjuction with Debian-based distribution of Linux\r
-software packages. It is currently in use by some users of the\r
-Debian project's distribution, and so serves as an example of the\r
-possibilities that exist.\r
-\r
-We feel that our P2P software package distribution model is\r
-well-suited to be used by many free software distributors. We hope\r
-to convince them to adopt such a model in their distribution, or we\r
-may port our existing system to some of the other groups for them to\r
-try.\r
-\r
-\textbf{OPTIONAL}: One aspect missing from our model is the removal of old packages\r
+In this paper, we have provided strong evidence that free software package distribution \r
+and update exhibit many distinct characteristics, which call for new designs other\r
+than the existing peer-to-peer systems for file sharing. To this end, we have \r
+present \texttt{apt-p2p}, a novel peer-to-peer distributor that sits between\r
+client and server, providing efficient and transparent downloading and updating services\r
+for software packages. We have addressed the key design issues in \texttt{apt-p2p}, including DHT customization,\r
+response time reduction, and multi-value extension. \texttt{apt-p2p}  has been used in conjuction with Debian-based distribution of Linux\r
+software packages and will also be available in the next release of Ubuntu. Existing real user statistics\r
+have suggested that it interacts well with clients and substantially reduces server cost. \r
+\r
+There are many future avenues toward improving our implementation. Besides \r
+evaluating its performance in larger scales, we are particularly interest in further speeding up some of the slower recursive\r
+DHT requests. We expect to accomplish this by fine tuning the\r
+parameters of our current system, better exclusion of NATted peers\r
+from the routing tables, and through the use of STUN \cite{STUN} to\r
+circumvent the NATs of the 50\% of the peers that have not\r
+configured port forwarding.\r
+\r
+One aspect missing from our model is the removal of old packages\r

 from the cache. Since our implementation is still relatively young,\r
 we have not had to deal with the problems of a growing cache of\r
 obsolete packages consuming all of a user's hard drive. We plan to\r
 from the cache. Since our implementation is still relatively young,\r
 we have not had to deal with the problems of a growing cache of\r
 obsolete packages consuming all of a user's hard drive. We plan to\r


@@ -1011,13 +975,7 @@ technique, in which packages that are no longer available on the
 server, no longer requested by peers, or simply are the oldest in\r
 the cache, will be removed.\r
 \r
 server, no longer requested by peers, or simply are the oldest in\r
 the cache, will be removed.\r
 \r

-The most significant area of improvement still needed in our sample\r
-implementation is to further speed up some of the slower recursive\r
-DHT requests. We hope to accomplish this by further tuning the\r
-parameters of our current system, better exclusion of NATted peers\r
-from the routing tables, and through the use of STUN \cite{STUN} to\r
-circumvent the NATs of the 50\% of the peers that have not\r
-configured port forwarding.\r
+\r

 \r
 \bibliographystyle{IEEEtran}\r
 \bibliography{./IEEEabrv,./all}\r
 \r
 \bibliographystyle{IEEEtran}\r
 \bibliography{./IEEEabrv,./all}\r