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 are effectively utilized and thus significantly reduces the currently\r
-large bandwidth requirements of hosting the software, as confirmed by our existing real user statistics.\r
+large bandwidth requirements of hosting the software, as confirmed by our existing real user statistics over the Internet.\r
\end{abstract}\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\label{intro}\r
\r
With the widespread penetration of broadband access, the Internet has become a cost-effective\r
-vehicle for software development and release. This is particularly true for the free software\r
+vehicle for software development and release \cite{feller2000fao}. This is particularly true for the free software\r
community whose developers and users are distributed worldwide and work asynchronously. The ever increasing power of\r
modern programming languages, computer platforms, and operating systems has made this software extremely large and complex,\r
though it is 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 packages over the Internet has become a challenging task.\r
+an efficient and reliable management and distribution of these software packages over the Internet has become a challenging task \cite{ubuntu-blueprint}.\r
\r
The existing distribution for free software is 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 this software, there are often a number of users\r
+the Advanced Package Tool (\texttt{apt}) for Linux \cite{apt}, 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 will scale well with the currently large user bases and can easily explore the network resources made available by\r
+this context, which will scale well with the currently large user bases and can easily explore the resources made available by\r
the volunteers.\r
\r
Unfortunately, this application scenario has many unique characteristics, which\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
-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
+In the free software community, there are a large number of groups using the Internet to\r
+collaboratively develop and release their software. Efficient and reliable management and distribution \r
+of these software packages over the Internet thus has become a critical task. In this section, we offer concrete examples illustrating the\r
unique challenges in this context.\r
\r
\subsection{Free Software Package Distributors}\r
or the distributor updating their packaging of the\r
software to meet new requirements. Even if the distributor\r
periodically makes \emph{stable} releases, which are snapshots of\r
-all the packages in the archive at a certain time, later updates are still\r
+all the packages in the archive at a certain time, many later updates are still\r
released for security issues or serious bugs.\r
\r
\begin{figure}\r
the Debian archive that was updated each day over a period of 3\r
months. Every single day, approximately 1.5\% of the 119,000 MB archive is\r
updated with new versions of packages. This frequency is much higher than\r
-that of most commercial software, mainly because much of free software is\r
+that of most commercial software \cite{microsoft-update}, mainly because much of free software is\r
developed in a loosely managed environment of developers working\r
asynchronously on a worldwide scale.\r
\r
\subsubsection{Limited Interest}\r
\r
-Finally, though there are a large number of packages and a large number of\r
+Though there are a large number of packages and a large number of\r
users, the interest in a particular package, or 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
+interesting to only a limited number of users.\r
\r
\begin{figure}\r
\centering\r
\r
\subsubsection{Interactive Users}\r
\r
-Given the relatively long time for software package downloading, existing package management systems generally display\r
+Finally, 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
monitor. Since previous client-server downloads occurred in a sequential\r
fashion, the package management software also measures the speed\r
based on sequential downloading. To offer comparable user experience, it is natural to expect that\r
the new peer-to-peer solution be reasonably responsive at retrieving packages,\r
-preferably in a sequential downloading order too.\r
+preferably in a sequential downloading order too. \r
\r
-\subsection{Why BitTorrent Doesn't Work Well}\r
+\subsection{Why BitTorrent Does Not Work Well}\r
\label{bittorrent}\r
\r
Many distributors make their software available using\r
\label{model}\r
\end{figure}\r
\r
+\subsection{System Overview}\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
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 an indexing structure (a Distributed Hash Table in our implementation) (7), which will return a\r
+then be looked up recursively in an indexing structure (a Distributed Hash Table, or DHT \cite{kademlia}, 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
The server thus, with no modification to its\r
functionality, serves as a seed for the packages in the peer-to-peer\r
system. Any packages that have just been updated, or that are very\r
-rare, and so don't have any peers available, can always be found on\r
+rare, and so do not have any peers available, can always be found on\r
the server. Once the peer has completed the download from the server\r
and verified the package, it can then add itself to the DHT as the\r
first peer for the new package, so that future requests for the package\r
\r
This sparse\r
interest in a large number of packages undergoing constant updating\r
-is well suited to the functionality provided by a Distributed Hash\r
-Table (DHT). DHTs require unique keys to store and retrieve strings\r
+is well suited to the functionality provided by a DHT. A DHT requires unique keys to store and retrieve strings\r
of data, for which the cryptographic hashes used by these package\r
management systems are perfect for. The stored and retrieved strings\r
can then be pointers to the peers that have the package that hashes\r
\r
% \subsection{Implementation Options}\r
% \label{imp_options}\r
-% \r
+%\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
% support uploading of already downloaded packages. Unfortunately, the\r
% package management tools typically only run until the download and\r
% install request is complete.\r
-% \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 peer-to-peer aspect as an almost standard HTTP\r
% files, as well as serving (uploading) cached package to other peers.\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
+% be found. For methods that do not use HTTP requests, other types of\r
% proxies may also be possible.\r
\r
\subsection{Peer Downloading Protocol}\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 popular \texttt{apt} tool. This tool \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
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. Like in \texttt{apt}, \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
+index files that contain the hashes of the individual packages.\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
\r
% \subsection{\textbf{OPTIONAL}: BitTorrent's Improvements}\r
% \label{bittorrent_dht}\r
-% \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
% 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
+%\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
% 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
+%\r
% \subsection{\textbf{OPTIONAL}: Other Changes}\r
% \label{other_changes}\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
next release of Ubuntu \cite{apt-p2p-ubuntu}. We have since created\r
a \emph{walker} that will navigate the DHT and find all the peers\r
currently connected to it. This allows us to analyze many aspects of\r
-our implementation.\r
+our implementation in the real Internet environment.\r
\r
\subsection{Peer Lifetimes}\r
\label{peer_life}\r
% system.}\r
% \label{duration_ind_peers}\r
% \end{figure}\r
-% \r
+%\r
% \textbf{OPTIONAL}: We also examined the average time each individual peer spends in the\r
% system. Figure~\ref{duration_peers} shows the cumulative\r
% distribution of how long each individual peer remains in the system.\r
% the system, will stay online for another 6 hours.}\r
% \label{duration_online_6}\r
% \end{figure}\r
-% \r
+%\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
downloading content they are not in need of in order to share them\r
with other users. Our system treats all users equally, requiring all\r
to become peers in the system, sharing the uploading load equally\r
-amongst all, but doesn't require any user to download files they\r
+amongst all, but does not require any user to download files they\r
would not otherwise need.\r
\r
The most similar works to ours are by Shah et. al. \cite{shah08} and\r
complete, and all requests can be completed in under a minute.\r
Shark makes use of Coral's distributed sloppy hash table to speed\r
the lookup time, but their system is more suited to its intended use\r
-as a distributed file server. It doesn't make use of authoritative\r
+as a distributed file server. It does not make use of authoritative\r
copies of the original files, allowing instead any users in the\r
system to update files and propagate those changes to others. Our\r
system is well-tailored to the application of disseminating the\r
\section{Conclusion and Future Work}\r
\label{conclusions}\r
\r
-In this paper, we have provided strong evidence that free software package distribution \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
+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
+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
+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
projects / quix0rs-apt-p2p.git / blobdiff