--- /dev/null
+\documentclass[conference]{IEEEtran}
+
+%% INFOCOM addition:
+\makeatletter
+\def\ps@headings{%
+\def\@oddhead{\mbox{}\scriptsize\rightmark \hfil \thepage}%
+\def\@evenhead{\scriptsize\thepage \hfil\leftmark\mbox{}}%
+\def\@oddfoot{}%
+\def\@evenfoot{}}
+\makeatother
+\pagestyle{headings}
+
+\usepackage[noadjust]{cite}
+
+\usepackage[dvips]{graphicx}
+
+\usepackage{url}
+
+\begin{document}
+
+\title{Peer-to-Peer Distribution of Free Software Packages}
+\author{\IEEEauthorblockN{Cameron Dale}
+\IEEEauthorblockA{School of Computing Science\\
+Simon Fraser University\\
+Burnaby, British Columbia, Canada\\
+Email: camerond@cs.sfu.ca}
+\and
+\IEEEauthorblockN{Jiangchuan Liu}
+\IEEEauthorblockA{School of Computing Science\\
+Simon Fraser University\\
+Burnaby, British Columbia, Canada\\
+Email: jcliu@cs.sfu.ca}}
+
+\maketitle
+
+\begin{abstract}
+A large amount of free software packages are available over the
+Internet from many different distributors. Most of these
+distributors use the traditional client-server model to handle
+requests from users. However, there is an excellent opportunity to
+use peer-to-peer techniques to reduce the cost of much of this
+distribution, especially due to the altruistic nature of many of
+these users. There are no existing solution suitable for this
+situation, so we present a new technique for satisfying the needs of
+this P2P distribution, which is generally applicable to many of
+these distributors' systems. Our method makes use of a DHT for
+storing the location of peers, using the cryptographic hash of the
+package as a key. To show the simplicity and functionality, we
+implement a solution for the distribution of Debian software
+packages, including the many DHT customizations needed. Finally, we
+analyze our system to determine how it is performing and what effect
+it is having.
+\end{abstract}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Introduction}
+\label{intro}
+
+There are a large number of free software package distributors using
+package distribution systems over the Internet to distribute
+software to their users. These distributors have developed many
+different methods for this distribution, but they almost exclusively
+use a client-server model to satisfy user requests. The popularity
+and number of users results in a large number of requests, which
+usually requires a network of mirrors to handle. Due to the free
+nature of this software, many users are willing and able to
+contribute upload bandwidth to this distribution, but have no
+current way to do this.
+
+We present a new peer-to-peer distribution model to meet these
+demands. It is based on many previous implementations of successful
+peer-to-peer protocols, especially distributed hash tables (DHT) and
+BitTorrent. The model relies on the pre-existence of cryptographic
+hashes of the packages, which should uniquely identify it for a
+request from other peers. If the peer-to-peer download fails, then
+the original request to the server is used as a fallback to prevent
+any dissatisfaction from users. The peer can then share this new
+package with others through the P2P system.
+
+First, we examine the opportunity that is available for many of
+these free software package distributors. We present an overview of
+a system that would efficiently satisfy the demands of a large
+number of users, and should significantly reduce the currently
+substantial bandwidth requirements of hosting this software. We then
+present an example implementation based on the Debian package
+distribution system. This implementation will be used by a large
+number of users, and serves as an example for other free software
+distributors of the opportunity that can be met with such a system.
+
+This paper is organized as follows. The current situation and its
+problems are presented in section \ref{situation}. We analyze some
+related solutions in section \ref{related}, and then present our
+solution in section \ref{opportunity}. We then detail our sample
+implementation for Debian-based distributions in section
+\ref{implementation}, including an in-depth look at our DHT
+customizations in section \ref{custom_dht}. We analyze our deployed
+sample implementation in section \ref{analysis}, suggest some future
+enhancements in section \ref{future}, and conclude the paper in
+section \ref{conclusions}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Problem/Situation}
+\label{situation}
+
+There are a large number of groups using the Internet to distribute
+their free software packages. These packages are usually available
+from a free download site, which usually requires a network of
+mirrors to support the large number of requests. These distribution
+systems almost always support some kind of file verification,
+usually cryptographic hashes, to verify the completed downloads
+accuracy or authenticity.
+
+\subsection{Examples}
+\label{examples}
+
+Most Linux distributions use a software package management system
+that fetches packages to be installed from an archive of packages
+hosted on a network of mirrors. The Debian project, and other
+Debian-based distributions such as Ubuntu and Knoppix, use the
+\texttt{apt} (Advanced Package Tool) program, which downloads Debian
+packages in the \texttt{.deb} format from one of many HTTP mirrors.
+The program will first download index files that contain a listing
+of which packages are available, as well as important information
+such as their size, location, and a hash of their content. The user
+can then select which packages to install or upgrade, and
+\texttt{apt} will download and verify them before installing them.
+
+There are also several similar frontends for the RPM-based
+distributions. Red Hat's Fedora project uses the \texttt{yum}
+program, SUSE uses \texttt{YAST}, while Mandriva has
+\texttt{Rpmdrake}, all of which are used to obtain RPMs from
+mirrors. Other distributions use tarballs (\texttt{.tar.gz} or
+\texttt{.tar.bz2}) to contain their packages. Gentoo's package
+manager is called \texttt{portage}, SlackWare Linux uses
+\texttt{pkgtools}, and FreeBSD has a suite of command-line tools,
+all of which download these tarballs from web servers.
+
+Other software distributors also use a similar system. CPAN
+distributes software packages for the PERL
+programming language, using SOAP RPC requests to find and download
+files. Cygwin provides many of the
+standard Unix/Linux tools in a Windows environment, using a
+package management tool that requests packages from websites. There
+are two software distribution systems for Mac OSX, fink and
+MacPorts, that also retrieve packages in this way.
+
+Also, some systems use direct web downloads, but with a hash
+verification file also available for download next to the desired
+file. These hash files usually have the same file name, but with an
+added extension identifying the hash used (e.g. \texttt{.md5} for
+the MD5 hash). This type of file downloading and verification is
+typical of free software hosting facilities that are open to anyone
+to use, such as SourceForge.
+
+\subsection{Similarities}
+\label{similarities}
+
+The important things to note for each of the systems mentioned in
+section \ref{examples}, is that they all have the following in
+common:
+\begin{itemize}
+ \item The content is divided into distinct units (packages), each
+ of which contains a small independent part of all the
+ content.
+ \item The packages are avaliable for anyone to freely download.
+ \item Users are typically not interested in downloading all of the
+ packages available.
+ \item Hashes of the packages are available before the download is
+ attempted.
+ \item Requests to download the packages are sent by a tool, not
+ directly by the user (though the tool is responding to
+ requests from the user).
+\end{itemize}
+
+We also expect that there are a number of users of these systems
+that are motivated by altruism to want to help out with this
+distribution. This is common in these systems due to the free nature
+of the software being delivered, which encourages some to want to
+help out in some way. A number of the systems are also used by
+groups that are staffed mostly, or sometimes completely, by
+volunteers. This also encourages users to want to give back
+to the volunteer community that has created the software they are
+using.
+
+\subsection{Differences}
+\label{differences}
+
+Although at first it might seem that a single all-reaching solution
+is possible for this situation, there are some differences in each
+system that require independent solutions. The systems all use
+different tools for their distribution, so any implementation would
+have to be specific to the tool it is to integrate with. In
+particular, how to obtain requests from the tool or user, and how to
+find a hash that corresponds to the file being requested, is very
+specific to each system.
+
+Also, there may be no benefit in creating a single large solution to
+integrate all these problems. Although they sometimes distribute
+nearly identical packages (e.g. the same software available in
+multiple Linux distributions), it is not exactly identical and has
+usually been tailored to the system by the distributor. The small
+differences will change the hash of the files, and so will make it
+impossible to distribute similar packages across systems. And,
+although peer-to-peer systems can scale very well with the number of
+peers in the system, there is some overhead involved, so having a
+much larger system of peers would mean that requests could take
+longer to complete.
+
+\subsection{Problems}
+\label{problems}
+
+There are some attributes of software package distribution that make
+it difficult to use an existing peer-to-peer solution with, or to
+design a new solution for this need.
+
+\subsubsection{Archive Dimensions}
+
+The dimensions of the software archive makes it difficult to
+distribute efficiently. While most of the packages are very small in
+size, there are some that are quite large. There are too many
+packages to distribute each individually, but the archive is also
+too large to distribute in its entirety. In some archives there are
+also divisions of the archive into sections, e.g. by the computer
+architecture that the package is intended for.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{apt_p2p_simulation-size_CDF.eps}
+\caption{The CDF of the size of packages in a Debian system, both
+for the actual size and adjusted size based on the popularity of
+the package.}
+\label{size_CDF}
+\end{figure}
+
+For example, Figure~\ref{size_CDF} shows the size of packages in the
+Debian distribution. While 80\% of the packages are less than
+512~KB, some of the packages are hundreds of megabytes. The entire
+archive consists of 22,298 packages and is approximately 119,000 MB
+in size. Some packages are divided by architecture, but there are a
+large number of packages that are not architecture specific and so
+can be installed on any computer architecture.
+
+\subsubsection{Package Updates}
+
+The software packages being distributed are being constantly
+updated. These updates could be the result of the software creators
+releasing a new version of the software with improved functionality,
+or the result of the distributor updating their packaging of the
+software to meet new requirements. Even if the distributor
+periodically makes \emph{stable} releases, which are snapshots of
+all the packages in the archive at a certain time, updates are still
+released for security issues or serious bugs.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{size-quarter.eps}
+\caption{The amount of data in the Debian archive that is updated
+each day, broken down by architecture.}
+\label{update_size}
+\end{figure}
+
+For example, Figure~\ref{update_size} shows the amount of data in
+the Debian archive that was updated each day over a period of 3
+months. Each day approximately 1.5\% of the 119,000 MB archive is
+updated with new versions of packages.
+
+\subsubsection{Limited Interest}
+
+Though there are a large number of packages, and a large number of
+users, interest in a given version of a package could be very
+limited. If the package is necessary for the system (e.g. the
+package distribution software), then it is likely that everyone will
+have it installed, but there are very few of these packages. Most
+packages fall in the category of optional or extra, and so are
+interesting to only a limited number of people.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{apt_p2p_popularity-cdf.eps}
+\caption{The CDF of the popularity of packages in a Debian system.}
+\label{popularity_CDF}
+\end{figure}
+
+For example, the Debian distribution tracks the popularity of its
+packages using popcon \cite{popcon}. Figure~\ref{popularity_CDF}
+shows the cumulative distribution function of the percentage of all
+users who install each package. Though some packages are installed
+by everyone, 80\% of the packages are installed by less than 1\% of
+users.
+
+\subsubsection{Interactive Users}
+
+The package management software that downloads packages displays
+some kind of indication of speed and completeness for users to
+watch. Since previous client-server downloads occur in a sequential
+fashion, the package management software also measures the speed
+based on sequential downloading. This requires the peer-to-peer
+solution to be reasonably responsive at retrieving packages
+sequentially.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Related Work/Existing Solutions}
+\label{related}
+
+There are many peer-to-peer implementations available today, but
+none is very well suited to this specific problem.
+
+\subsection{BitTorrent}
+\label{bittorrent}
+
+Many distributors make their software available in some form using
+BitTorrent \cite{COHEN03}, e.g. for the distribution of CD
+images. This is not an ideal situation though, as it requires the
+peers to download large numbers of packages that they are not
+interested in, and prevents them from updating to new packages
+without downloading another image containing a lot of the same
+packages they already have. Unfortunately, BitTorrent is not ideally
+suited to an application such as this one.
+
+First, there is no obvious way to divide the packages into torrents.
+Most of the packages are too small, and there are too many packages
+in the entire archive, to create individual torrents for each one.
+However, all the packages together are too large to track
+efficiently as a single torrent. Some division of the archive's
+packages into torrents is obviously necessary, but wherever that
+split occurs it will cause either some duplication of connections,
+or prevent some peers from connecting to others who do have the same
+content. Also, a small number of the packages can be updated every
+day which would add new files to the torrent, thereby changing its
+\emph{infohash} identifier and making it a new torrent. This will
+severely fracture the download population, even though peers in the
+new torrent share 99\% of the packages in common with peers in the
+old torrent.
+
+Other issues also prevent BitTorrent from being a good solution to
+this problem. BitTorrent's fixed piece sizes that disregard file
+boundaries are bigger than many of the packages in the archive. This
+will waste peers' downloading bandwidth as they will end up
+downloading parts of other packages just to get the piece that
+contains the package they do want. Incentives to share (upload) are
+no longer needed, as the software is freely available for anyone to
+download without sharing. Seeds are also not needed as the mirrors
+can serve in that capacity. Finally, BitTorrent downloads files
+randomly, which does not work well with the interactive package
+management tools expectation of sequential downloads.
+
+\subsection{Other Solutions}
+\label{others}
+
+There have also been other attempted implementations, usually based
+on some form of BitTorrent, to address this problem. Some other
+implementations have used BitTorrent almost unmodified, while others
+have only looked at using DHTs to replace the tracker in a
+BitTorrent system. apt-torrent \cite{apttorrent} creates torrents
+for some of the larger packages available, but it ignores the
+smaller packages, which are often the most popular. DebTorrent
+\cite{debtorrent} makes widespread modifications to a traditional
+BitTorrent client, to try and fix the drawbacks mentioned in section
+\ref{bittorrent}. However, these changes also require some
+modifications to the distribution system to support it.
+
+Others have also used DHTs to support this type of functionality.
+Kenosis \cite{kenosis} is a P2P Remote Procedure Call
+client also based on the Kademlia DHT, but it is meant as a P2P
+primitive system on which other tools can be built, and so it has no
+file sharing functionality at all. Many have used a DHT as a drop-in
+replacement for the tracker in a BitTorrent system
+\cite{bittorrent-dht, azureus-dht}, but such systems only use the
+DHT to find peers for the same torrent, so the file sharing uses
+traditional BitTorrent and so is not ideal for the reasons listed
+above.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Opportunity/Our Proposal}
+\label{opportunity}
+
+The situation described in section \ref{situation} presents a clear
+opportunity to use some form of peer-to-peer file-sharing protocol
+to allow willing users to contribute upload bandwidth. This sparse
+interest in a large number of packages undergoing constant updating
+is well suited to the functionality provided by a Distributed Hash
+Table (DHT). DHTs require unique keys to store and retrieve strings
+of data, for which the cryptographic hashes used by these package
+management systems are perfect for. The stored and retrieved strings
+can then be pointers to the peers that have the package that hashes
+to that key. A downloading peer can lookup the package hash in the
+DHT and, if it is found, download the file from those peers and
+verify the package with the hash. Once the download is complete, the
+peer will add its entry to the DHT indicating that it now has the
+package.
+
+The fact that this package is also available to download for free
+from a server is very important to our proposal. If the package hash
+can not be found in the DHT, the peer can then fallback to
+downloading from the original location (i.e. the network of
+mirrors). The mirrors thus, with no modification to their
+functionality, serve as seeds for the packages in the peer-to-peer
+system. Any packages that have just been updated, or that are very
+rare, and so don't have any peers available can always be found on
+the mirror. Once the peer has completed the download from the mirror
+and verified the package, it can then add itself to the DHT as the
+first peer for the new package, so that future requests from peers
+will not need the mirror.
+
+The trust of the package is also always guaranteed through the use
+of the cryptographic hashes. Nothing can be downloaded from a peer
+until the hash is looked up in the DHT, so a hash must first come
+from a trusted source (i.e. a mirror). Most distributors use index
+files that contain hashes for a large number of the packages in
+their archive, and which are also hashed. After retrieving the
+index's hash from the mirror, the index file can be downloaded from
+peers and verified. Then the program has access to all the hashes of
+the packages it will be downloading, all of which can be verified
+with a \emph{chain of trust} that stretches back to the original
+distributor's server.
+
+\subsection{Implementation Options}
+\label{imp_options}
+
+There are several ways to implement the desired P2P functionality
+into the existing package management software. The functionality can
+be directly integrated through modifications to the software, though
+this could be difficult as the P2P functionality should be running
+at all times. This is needed both for efficient lookups and to
+support uploading of already downloaded packages. Unfortunately, the
+package management tools typically only run until the download and
+install request is complete.
+
+Many of the package management software implementations use HTTP
+requests from web servers to download the packages, which makes it
+possible to implement the P2P aspect as an almost standard HTTP
+caching proxy. This proxy will run as a daemon in the background,
+listening for requests from the package management tool for package
+files. It will get uncached requests first from the P2P system, or
+falling back to the normal HTTP request from a server should it not
+be found. For methods that don't use HTTP requests, other types of
+proxies may also be possible.
+
+\subsection{Downloading From Peers}
+\label{downloading}
+
+Although not necessary, we recommend implementing a download
+protocol that is similar to the protocol used to fetch packages from
+the distributor's servers. This simplifies the P2P program, as it
+can then treat peers and mirrors almost identically when requesting
+packages. In fact, the mirrors can be used when there are only a few
+slow peers available for a file to help speed up the download
+process.
+
+Downloading a file efficiently from a number of peers is where
+BitTorrent shines as a peer-to-peer application. Its method of
+breaking up larger files into pieces, each with its own hash,
+makes it very easy to parallelize the downloading process and
+maximize the download speed. For very small packages (i.e. less than
+the piece size), this parallel downloading is not necessary, or
+even desirable. However, this method should still be used, in
+conjunction with the DHT, for the larger packages that are
+available.
+
+Since the package management system only stores a hash of the entire
+package, and not of pieces of that package, we will need to be able
+to store and retrieve these piece hashes using the P2P protocol. In
+addition to storing the file download location in the DHT (which
+would still be used for small files), a peer will store a
+\emph{torrent string} containing the peer's hashes of the pieces of
+the larger files. These piece hashes could be compared ahead of time
+to determine which peers have the same piece hashes (they all
+should), and then used during the download to verify the pieces of
+the downloaded package.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Sample Implementation/Implementation}
+\label{implementation}
+
+We have created a sample implementation that functions as described
+in section \ref{opportunity}, and is freely available for other
+distributors to download and modify \cite{apt-p2p}. This software,
+called \texttt{apt-p2p}, interacts with the \texttt{apt} tool, which
+is found in most Debian-based Linux distributions. \texttt{apt} uses
+SHA1 hashes to verify most downloaded files, including the large
+index files that contain the hashes of the individual packages. We
+chose this distribution system as it is familiar to us, it allows
+software contributions, and there are interesting statistics
+available for analyzing the popularity of the software packages
+\cite{popcon}.
+
+Since all requests from apt are in the form of HTTP downloads from a
+server, the implementation takes the form of a caching HTTP proxy.
+Making a standard \texttt{apt} implementation use the proxy is then
+as simple as prepending the proxy location and port to the front of
+the mirror name in \texttt{apt}'s configuration file (i.e.
+``localhost:9977/mirrorname.debian.org/\ldots'').
+
+We created a customized DHT based on Khashmir \cite{khashmir}, which
+is an implementation of Kademlia \cite{kademlia} using methods
+familiar to BitTorrent developers. Khashmir is also the same DHT
+implementation used by most of the existing BitTorrent clients to
+implement trackerless operation. The communication is all handled by
+UDP messages, and RPC (remote procedure call) requests and responses
+are all \emph{bencoded} in the same way as BitTorrent's
+\texttt{.torrent} files. Khashmir uses the high-level Twisted
+event-driven networking engine \cite{twisted}, so we also use
+Twisted in our sample implementation for all other networking needs.
+More details of this customized DHT can be found below in section
+\ref{custom_dht}.
+
+Downloading is accomplished by sending simple HTTP requests to the
+peers identified by lookups in the DHT to have the desired file.
+Requests for a package are made using the package's hash, properly
+encoded, as the URL to request from the peer. The HTTP server used
+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
+server and the client, which allows for pipelining of multiple
+requests to a peer, and the requesting of smaller pieces of a large
+file using the Range request header.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Customized DHT}
+\label{custom_dht}
+
+A large contribution of our work is in the customization and use of
+a Distributed Hash Table (DHT). Although our DHT is based on
+Kademlia, we have made many improvements to it to make it suitable
+for this application. In addition to a novel storage technique to
+support piece hashes, we have improved the response time of looking
+up queries, allowed the storage of multiple values for each key, and
+incorporated some improvements from BitTorrent's tracker-less DHT
+implementation.
+
+\subsection{Kademlia Background}
+\label{kademlia}
+
+The Kademlia DHT, like most other DHTs, assigns IDs to peers from
+the same space that is used for keys. The peers with IDs closest to
+the desired key will then store the values for that key. Lookups are
+recursive, as nodes are queried in each step that are exponentially
+closer to the key than in the previous step.
+
+Nodes in a Kademlia system support four primitive requests.
+\texttt{ping} will cause a peer to return nothing, and is only used
+to determine if a node is still alive, while \texttt{store} tells a
+node to store a value associated with a given key. The most
+important primitives are \texttt{find\_node} and
+\texttt{find\_value}, which both function recursively to find nodes
+close to a key. The queried nodes will return a list of the nodes
+they know about that are closest to the key, allowing the querying
+node to quickly traverse the DHT to find the nodes close to the
+desired key. The only difference between them is that the
+\texttt{find\_value} query will cause a node to return a value, if
+it has one for that key, instead of a list of nodes.
+
+\subsection{Piece Hash Storage}
+\label{pieces}
+
+Hashes of pieces of the larger package files are needed to support
+their efficient downloading from multiple peers.
+For large files (5 or more pieces), the torrent strings described in
+section \ref{downloading}
+are too long to store with the peer's download info in the DHT. This
+is due to the limitation that a single UDP packet should be less
+than 1472 bytes to avoid fragmentation.
+% For example, for a file of 4 pieces, the peer would need to store a
+% value 120 bytes in size (IP address, port, four 20-byte pieces and
+% some overhead), which would limit a return value from including more
+% than 10 values to a request.
+
+Instead, the peers will store the torrent string for large files
+separately in the DHT, and only contain a reference to it in their
+stored value for the hash of the file. The reference is an SHA1 hash
+of the entire concatenated length of the torrent string. If the
+torrent string is short enough to store in the DHT (i.e. less than
+1472 bytes, or about 70 pieces for the SHA1 hash), then a lookup of
+that hash in the DHT will return the torrent string. Otherwise, a
+request to the peer for the hash (using the same method as file
+downloads, i.e. HTTP), will cause the peer to return the torrent
+string.
+
+Figure \ref{size_CDF} shows the package size of the 22,298 packages
+available in Debian in January 2008. We can see that most of the
+packages are quite small, and so most will therefore not require
+piece hash information to download. We have chosen a piece
+size of 512 kB, which means that 17,515 (78\%) of the packages will
+not require this information. There are 3054 packages that will
+require 2 to 4 pieces, for which the torrent string can be stored
+directly with the package hash in the DHT. There are 1667 packages
+that will require a separate lookup in the DHT for the longer
+torrent string as they require 5 to 70 pieces. Finally, there are
+only 62 packages that require more than 70 pieces, and so will
+require a separate request to a peer for the torrent string.
+
+\subsection{Response Time}
+\label{response_time}
+
+Most of our customizations to the DHT have been to try and improve
+the time of the recursive \texttt{find\_value} requests, as this can
+cause long delays for the user waiting for a package download to
+begin. The one problem that slows down such requests is waiting for
+timeouts to occur before marking the node as failed and moving on.
+
+Our first improvement is to retransmit a request multiple times
+before a timeout occurs, in case the original request or its
+response was lost by the unreliable UDP protocol. If it does not
+receive a response, the requesting node will retransmit the request
+after a short delay. This delay will increase exponentially for
+later retransmissions, should the request again fail. Our current
+implementation will retransmit the request after 2 seconds and 6
+seconds (4 seconds after the first retransmission), and then timeout
+after 9 seconds.
+
+We have also added some improvements to the recursive
+\texttt{find\_node} and \texttt{find\_value} queries to speed up the
+process when nodes fail. If enough nodes have responded to the
+current query such that there are many new nodes to query that are
+closer to the desired key, then a stalled request to a node further
+away will be dropped in favor of a new request to a closer node.
+This has the effect of leap-frogging unresponsive nodes and
+focussing attention on the nodes that do respond. We will also
+prematurely abort a query while there are still oustanding requests,
+if enough of the closest nodes have responded and there are no
+closer nodes found. This prevents a far away unresponsive node from
+making the query's completion wait for it to timeout.
+
+Finally, we made all attempts possible to prevent firewalled and
+NATted nodes from being added to the routing table for future
+requests. Only a node that has responded to a request from us will
+be added to the table. If a node has only sent us a request, we
+attempt to send a \texttt{ping} to the node to determine if it is
+NATted or not. Unfortunately, due to the delays used by NATs in
+allowing UDP packets for a short time if one was recently sent by
+the NATted host, the ping is likely to succeed even if the node is
+NATted. We therefore also schedule a future ping to the node to make
+sure it is still reachable after the NATs delay has hopefully
+elapsed. We also schedule future pings of nodes that fail once to
+respond to a request, as it takes multiple failures (currently 3)
+before a node is removed from the routing table.
+
+\subsection{Multiple Values}
+\label{multiple_values}
+
+The original design of Kademlia specified that each keywould have
+only a single value associated with it. The RPC to find this value
+was called \texttt{find\_value} and worked similarly to
+\texttt{find\_node}, iteratively finding nodes with ID's closer to
+the desired key. However, if a node had a value stored associated
+with the searched for key, it would respond to the request with that
+value instead of the list of nodes it knows about that are closer.
+
+While this works well for single values, it can cause a problem when
+there are multiple values. If the responding node is no longer one
+of the closest to the key being searched for, then the values it is
+returning will probably be the staler ones in the system, and it
+will not have the latest stored values. However, the search for
+closer nodes will stop here, as the queried node only returned the
+values and not a list of nodes to recursively query. We could have
+the request return both the values and the list of nodes, but that
+would severely limit the size and number of the values that could be
+returned.
+
+Instead, we have broken up the original \texttt{find\_value}
+operation into two parts. The new \texttt{find\_value} request
+always returns a list of nodes that the node believes are closest to
+the key, as well as a number indicating the number of values that
+this node has for the key. Once a querying node has finished its
+search for nodes and found the closest ones to the key, it can issue
+\texttt{get\_value} requests to some nodes to actually retrieve the
+values they have. This allows for much more control of when and how
+many nodes to query for values. For example, a querying node could
+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
+closest to the key being searched for.
+
+\subsection{BitTorrent's Improvements}
+\label{bittorrent_dht}
+
+In the many years that some BitTorrent clients have been using a
+Kademlia based DHT for tracker-less operation, the developers have
+made many enhancements which we can take advantage of. One of the
+most important is a security feature added to stop malicious nodes
+from subscribing other nodes as downloaders. When a node issues a
+request to another node to store its download info for that key, it
+must include a \emph{token} returned by the storing node in a recent
+\texttt{find\_node} request. The token is created by hashing the IP
+address of the requesting peer with a temporary secret that expires
+after several minutes. This prevents the requesting peer from faking
+its IP address in the store request, since it must first receive a
+response from a \texttt{find\_node} on that IP.
+
+We also made some BitTorrent-inspired changes to the parameters of
+the DHT originally specified by the authors of Kademlia. Since, as
+we will show later, peers stay online in our system for much longer
+periods of time, we reduced Kademlia's \emph{k} value from 20 to 8.
+The value is supposed to be large enough such that any given
+\emph{k} nodes are unlikely to fail within an hour of each other,
+which is very unlikely in our system given the long uptimes of
+nodes. We also increased the number of concurrent outstanding
+requests allowed from 3 to 6 to speed up the recursive key finding
+processes.
+
+\subsection{Other Changes}
+\label{other_changes}
+
+We added one other new RPC request that nodes can make:
+\texttt{join}. This request is only sent on first loading the DHT,
+and is usually only sent to the bootstrap nodes that are listed for
+the DHT. These bootstrap nodes will respond to the request with the
+requesting peer's IP and port, so that the peer can determine what
+its oustide IP address is and whether port translation is being
+used. In the future, we hope to add functionality similar to STUN
+\cite{STUN}, so that nodes can detect whether they are NATted and
+take appropriate steps to circumvent it.
+
+In addition, we have allowed peers to store values in the DHT, even
+if the hash they are using is not the correct length. Most of the
+keys used in the DHT are based on the SHA1 hash, and so they are 20
+bytes in length. However, some files in the targetted Debian package
+system are only hashed using the MD5 algorithm, and so the hashes
+retrieved from the server are 16 bytes in length. The DHT will still
+store values using these keys by padding the end of them with zeroes
+to the proper length, as the loss of uniqueness from the 4 less
+bytes is not an issue. Also, the DHT will happily store hashes that
+are longer than 20 bytes, such as those from the 32 byte SHA256
+algorithm, by truncating them to the correct length. Since the
+requesting peer will have the full length of the hash, this will not
+affect its attempt to verify the downloaded file.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Analysis}
+\label{analysis}
+
+Our \texttt{apt-p2p} implementation supporting the Debian package
+distribution system has been available to all Debian users since May
+3rd, 2008 \cite{apt-p2p-debian}, and will also be available in the
+next release of Ubuntu \cite{apt-p2p-ubuntu}. We have since created
+a \emph{walker} that will navigate the DHT and find all the peers
+currently connected to it. This allows us to analyze many aspects of
+our implementation.
+
+\subsection{Peer Lifetimes}
+\label{peer_life}
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PWalker-peers.eps}
+\caption{The number of peers found in the system, and how many are
+behind a firewall or NAT.}
+\label{walker_peers}
+\end{figure}
+
+We first began analyzing the DHT on June 24th, and continue to this
+day, giving us 2 months of data so far. Figure~\ref{walker_peers}
+shows the number of peers we have seen in the DHT during this time.
+The peer population is very steady, with just over 50 regular users
+participating in the DHT at any time. We also note that we find 100
+users who connect regularly (weekly), and we have found 186 unique
+users in the 2 months of our analysis. We determined which users are
+behind a firewall or NAT, which is one of the main problems of
+implementing a peer-to-peer network. These peers will be
+unresponsive to DHT requests from peers they have not contacted
+recently, which will cause the peer to wait for a timeout to occur
+(currently set at 9 seconds) before moving on. They will also be
+unable to contribute any upload bandwidth to other peers, as all
+requests for packages from them will also timeout. From
+Figure~\ref{walker_peers}, we see that approximately half of all
+peers suffered from this restriction.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PDuration-peers.eps}
+\caption{The CDF of how long an average session will last.}
+\label{duration_peers}
+\end{figure}
+
+Figure~\ref{duration_peers} shows the cumulative distribution of how
+long a connection from a peer can be expected to last. Due to our
+software being installed as a daemon that is started by default
+every time their computer boots up, peers are expected to stay for a
+long period in the system. 50\% of connections last longer than 5
+hours, and 20\% last longer than 10 hours. These connections are
+much longer than those reported by Saroiu et. al. \cite{saroiu2001}
+for other P2P systems, which had 50\% of Napster and Gnutella
+sessions lasting only 1 hour.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PDuration-ind_peers.eps}
+\caption{The CDF of the average time individual peers stay in the
+system.}
+\label{duration_ind_peers}
+\end{figure}
+
+We also examined the average time each individual peer spends in the
+system. Figure~\ref{duration_peers} shows the cumulative
+distribution of how long each individual peer remains in the system.
+Here we see that 50\% of peers have average stays in the system
+longer than 10 hours.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PDuration-online_1.eps}
+\caption{The fraction of peers that, given their current duration in
+the system, will stay online for another hour.}
+\label{duration_online_1}
+\end{figure}
+
+Since our DHT is based on Kademlia, which was designed based on the
+probability that a node will remain up another hour, we also
+analyzed our system for this parameter.
+Figure~\ref{duration_online_1} shows the fraction of peers will
+remain online for another hour, as a function of how long they have
+been online so far. Maymounkov and Mazieres found that the longer a
+node has been online, the higher the probability that it will stay
+online \cite{kademlia}. Our results also show this behavior. In
+addition, similar to the Gnutella peers, over 90\% of our peers that
+have been online for 10 hours, will remain online for another hour.
+Our results also show that, for our system, over 80\% of all peers
+will remain online another hour, compared with around 50\% for
+Gnutella.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PDuration-online_6.eps}
+\caption{The fraction of peers that, given their current duration in
+the system, will stay online for another 6 hours.}
+\label{duration_online_6}
+\end{figure}
+
+Since our peers are much longer-lived than other P2P systems, we
+also looked at the fraction of peers that stay online for another 6
+hours. Figure~\ref{duration_online_6} shows that over 60\% of peers
+that are online for 10 hours will stay online for another 6.
+However, we see an interesting decrease in this fraction between 8
+and 12 hours, which can also be seen in
+Figure~\ref{duration_online_1}. We believe this to be due to desktop
+users, who regularly turn off their computers at night.
+
+\subsection{Peer Statistics}
+\label{peer_stats}
+
+On July 31st we enhanced our walker to retrieve additional
+information from each contacted peer. The peers are configured, by
+default, to publish some statistics on how much they are downloading
+and uploading, and their measured response times for DHT queries.
+Our walker can extract this information if the peer is not
+firewalled or NATted, it has not disabled this functionality, and if
+it uses the same port for both its DHT (UDP) requests and download
+(TCP) requests (which is also a configuration parameter).
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PDownloaded-peers.eps}
+\caption{The number of peers that were contacted to determine their
+bandwidth, and the total number of peers in the system.}
+\label{down_peers}
+\end{figure}
+
+Figure~\ref{down_peers} shows the total number of peers we have been
+able to contact since starting to gather this additional
+information, as well as how many total peers were found. We were
+only able to contact 30\% of all the peers that connected to the
+system during this time.
+
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{AptP2PDownloaded-bw.eps}
+\caption{The bandwidth of data that the contacted peers have
+downloaded and uploaded.}
+\label{down_bw}
+\end{figure}
+
+Figure~\ref{down_bw} shows the amount of data the peers we were able
+to contact have downloaded. Peers measure their downloads from other
+peers and mirrors separately, so we are able to get an idea of how
+much savings our system is generating for the mirrors. We see that
+the peers are downloading approximately 20\% of their package data
+from other peers, which is saving the mirrors from supplying that
+bandwidth. The actual numbers are only a lower bound, since we have
+only contacted 30\% of the peers in the system, but we can estimate
+that \texttt{apt-p2p} has already saved the mirrors 15 GB of
+bandwidth, or 1 GB per day.
+
+We also collected the statistics on the measured response time peers
+were experiencing when sending requests to the DHT. We found that
+the recursive \texttt{find\_value} query, which is necessary before
+a download can occur, is taking 17 seconds on average. This
+indicates that, on average, requests are experiencing almost 2
+stalls while waiting for the 9 second timeouts to occur on
+unresponsive peers. This is longer than our target of 10 seconds,
+although it will only lead to a slight average delay in downloading
+of 1.7 seconds when the default 10 concurrent downloads are
+occurring.This increased response time is due to the number of peers
+that were behind firewalls or NATs, which was much higher than we
+anticipated. We do have plans to improve this through better
+informing of users of their NATted status, the use of STUN
+\cite{STUN} to circumvent the NATs, and by better exclusion of
+NATted peers from the DHT (which will not prevent them from using
+the system).
+
+We were also concerned that the constant DHT requests and responses,
+even while not downloading, would overwhelm some peers' network
+connections. However, we found that peers are using 200 to 300 bytes
+per second of bandwidth in servicing the DHT. These numbers are
+small enough to not affect any other network services the peer would
+be running.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Future Work}
+\label{future}
+
+We feel that our P2P software package distribution model is
+well-suited to be used by many free software distributors. We hope
+to convince them to adopt such a model in their distribution, or we
+may port our existing system to some of the other groups for them to
+try.
+
+One aspect missing from our model is the removal of old packages
+from the cache. Since our implementation is still relatively young,
+we have not had to deal with the problems of a growing cache of
+obsolete packages consuming all of a user's hard drive. We plan to
+implement some form of least recently used (LRU) cache removal
+technique, in which packages that are no longer available on the
+server, no longer requested by peers, or simply are the oldest in
+the cache, will be removed.
+
+The most significant area of improvement still needed in our sample
+implementation is to further speed up some of the slower recursive
+DHT requests. We hope to accomplish this by further tuning the
+parameters of our current system, better exclusion of NATted peers
+from the routing tables, and through the use of STUN \cite{STUN} to
+circumvent the NATs of the 50\% of the peers that have not
+configured port forwarding.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Conclusions}
+\label{conclusions}
+
+We have designed a generally applicable peer-to-peer content
+distribution model to be used by many of the free software
+distributors operating today. It makes use of already existing
+features of most package management systems to create a
+peer-to-peer distribution that should substantially reduce the costs
+of hosting the software packages.
+
+We have also implemented our design in freely available software to
+be used in conjuction with Debian-based distribution of Linux
+software packages. It is currently in use by some users of the
+Debian project's distribution, and so serves as an example of the
+possibilities that exist.
+
+\bibliographystyle{IEEEtran}
+\bibliography{./IEEEabrv,./all}
+
+\end{document}
projects / quix0rs-apt-p2p.git / blobdiff