\begin{abstract}\r
The Internet has become a cost-effective\r
vehicle for software development and release, particular in the free software community.\r
-Given the free nature of these 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 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
+of this voluntary society. It is thus naturally expected that a peer-to-peer distribution can be implemented,\r
+which will 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 existing peer-to-peer systems for file sharing such 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
+make a straightforward adoption of existing peer-to-peer systems for file sharing (such as BitTorrent) suboptimal. In particular,\r
+a software release often consists of a large number of packages, which are difficult to distribute 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 developers, and 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 distribution system 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
+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 conjunction with Debian-based distribution of Linux\r
+software packages and is also available in the latest 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 over the Internet.\r
+large bandwidth requirements of hosting the software, as confirmed by our existing real user statistics gathered over the Internet.\r
\end{abstract}\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\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 \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
+Given the free nature of this 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
the volunteers.\r
\r
Unfortunately, this application scenario has many unique characteristics, which\r
-make a straightforward adoption of existing peer-to-peer systems for file sharing such as BitTorrent suboptimal. In particular,\r
+make a straightforward adoption of existing peer-to-peer systems for file sharing (such 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 developers, and 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 distributions. This in turn suppresses interaction with users\r
+limited. They together make it very difficult to efficiently create and manage torrents and 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 distribution system 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
+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 are effectively utilized and thus significantly reduces the currently\r
large 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 current deployment to\r
+\texttt{apt-p2p} has been used in conjunction with the Debian-based distribution of Linux\r
+software packages and is also available in the latest release of Ubuntu. We have evaluated our current deployment to\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. In particular, our existing real user statistics\r
have suggested that it responsively interacts with clients and substantially reduces server cost.\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
-\section{Background and Motivations}\r
+\section{Background and Motivation}\r
\label{situation}\r
\r
In the free software community, there are a large number of groups using the Internet to\r
are two software distribution systems for software that runs on the Macintosh OS, fink and\r
MacPorts, that also retrieve packages in this way.\r
\r
-Direct web downloading is also a common way, often coupled with a hash\r
+Direct web downloading by users is also common, often coupled with a hash\r
verification file to be downloaded next to the desired\r
file. The hash file usually has the same file name, but with an\r
added extension identifying the hash used (e.g. \texttt{.md5} for\r
\label{problems}\r
\r
While it seems straightforward to use an existing peer-to-peer file sharing tool like BitTorrent for\r
-free software package distribution, there are indeed a series of new challenges in this unique scenario:\r
+this free software package distribution, there are indeed a series of new challenges in this unique scenario:\r
\r
\subsubsection{Archive Dimensions}\r
\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
-available the index files containing the cryptographic hashes all\r
+available the index files containing the cryptographic hashes of all\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, 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
+list of peers that have the package already (8). Then, in Phase~3, the package\r
+can 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
-current nodes location is also added to the DHT for that hash (15),\r
+current node's location is also added to the DHT for that hash (15),\r
as it is now a source for others to download from.\r
\r
In steps (11,12), the fact that this package is also available to download for free\r
downloading from the original location (i.e. the server).\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 do not have any peers available, can always be found on\r
+system. Any packages that have just been updated or that are very\r
+rare, and so do not yet 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
-will not need the server.\r
+will not need to use the server.\r
\r
This sparse\r
interest in a large number of packages undergoing constant updating\r
the trust of the package is always guaranteed through the use\r
of the cryptographic hashes. Nothing can be downloaded from a peer\r
until the hash is looked up in the DHT, so a hash must first come\r
-from a trusted source (i.e. the distributors server). Most distributors use index\r
+from a trusted source (i.e. the distributor's server). Most distributors use index\r
files that contain hashes for a large number of the packages in\r
their archive, and which are also hashed. After retrieving the\r
-index's hash from the server, the index file can be downloaded from\r
+index file's hash from the server, the index file can also be downloaded from\r
peers and verified. Then the program has access to all the hashes of\r
the packages it will be downloading, all of which can be verified\r
with a \emph{chain of trust} that stretches back to the original\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
+UDP messages, and RPC (remote procedure call) requests and responses between nodes\r
are all \emph{bencoded} in the same way as BitTorrent's\r
\texttt{.torrent} files.\r
% Khashmir uses the high-level Twisted\r
\r
Downloading is accomplished by sending simple HTTP requests to the\r
peers identified by lookups in the DHT to have the desired file.\r
-Requests for a package are made using the package's hash, properly\r
-encoded, as the URL to request from the peer. The HTTP server used\r
+Requests for a package are made using the package's hash (properly\r
+encoded) as the URL to request from the peer. The HTTP server used\r
for the proxy also doubles as the server listening for requests for\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
DHT, and so must recursively search for the correct node to put to\r
or get from.\r
\r
-The Kademlia DHT, like most other DHTs, assigns IDs to peers randomly from\r
-the same space that is used for keys. The peers with IDs closest to\r
+The Kademlia DHT, like most other DHTs, assigns Ids to peers randomly from\r
+the same space that is used for keys. The peers with Ids closest to\r
the desired key will then store the values for that key.\r
Nodes support four primitive requests.\r
\texttt{ping} will cause a peer to return nothing, and is only used\r
separately in the DHT, and only contain a reference to it in their\r
stored value for the hash of the file. The reference is an SHA1 hash\r
of the entire concatenated length of the torrent string. If the\r
-torrent string is short enough to store in the DHT (i.e. less than\r
+torrent string is short enough to store separately in the DHT (i.e. less than\r
1472 bytes, or about 70 pieces for the SHA1 hash), then a lookup of\r
that hash in the DHT will return the torrent string. Otherwise, a\r
request to the peer for the hash (using the same method as file\r
require 2 to 4 pieces, for which the torrent string can be stored\r
directly with the package hash in the DHT. There are 1667 packages\r
that will require a separate lookup in the DHT for the longer\r
-torrent string as they require 5 to 70 pieces. Finally, there are\r
+torrent string, as they require 5 to 70 pieces. Finally, there are\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
closer to the desired key, then a stalled request to a node further\r
away will be dropped in favor of a new request to a closer node.\r
This has the effect of leap-frogging unresponsive nodes and\r
-focussing attention on the nodes that do respond. We will also\r
+focussing attention on the closer nodes that do respond. We will also\r
prematurely abort a query while there are still oustanding requests,\r
if enough of the closest nodes have responded and there are no\r
closer nodes found. This prevents a far away unresponsive node from\r
The original design of Kademlia specified that each key would have\r
only a single value associated with it. The RPC to find this value\r
was called \texttt{find\_value} and worked similarly to\r
-\texttt{find\_node}, iteratively finding nodes with ID's closer to\r
+\texttt{find\_node}, iteratively finding nodes with Id's closer to\r
the desired key. However, if a node had a value stored associated\r
with the searched for key, it would respond to the request with that\r
value instead of the list of nodes it knows about that are closer.\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
+% which is very unlikely in our system given the long uptime 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
\r
Our \texttt{apt-p2p} implementation supporting the Debian package\r
distribution system has been available to all Debian users since May\r
-3rd, 2008 \cite{apt-p2p-debian}, and will also be available in the\r
-next release of Ubuntu \cite{apt-p2p-ubuntu}. We have since created\r
+3rd, 2008 \cite{apt-p2p-debian}, and is also available in the\r
+latest release of Ubuntu \cite{apt-p2p-ubuntu}. We 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 in the real Internet environment.\r
\label{walker_peers}\r
\end{figure}\r
\r
-We first began analyzing the DHT on June 24th, and continue to this\r
-day, giving us 2 months of data so far. Figure~\ref{walker_peers}\r
+We first began analyzing the DHT on June 24th, 2008, and continued\r
+until we had gathered almost 2 months of data. Figure~\ref{walker_peers}\r
shows the number of peers we have seen in the DHT during this time.\r
The peer population is very steady, with just over 50 regular users\r
participating in the DHT at any time. We also note that we find 100\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
+its outside 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
Our walker can extract this information if the peer is not\r
firewalled or NATted, it has not disabled this functionality, and if\r
it uses the same port for both its DHT (UDP) requests and download\r
-(TCP) requests (which is also the default configuration parameter).\r
+(TCP) requests (which is also the default configuration behavior).\r
\r
\begin{figure}\r
\centering\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
+presented \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
+response time reduction, and multi-value extension. \texttt{apt-p2p} has been used in conjunction with Debian-based distribution of Linux\r
+software packages and is also available in the latest 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
projects / quix0rs-apt-p2p.git / blobdiff