\usepackage[noadjust]{cite}
-%\ifCLASSINFOpdf
- % \usepackage[pdftex]{graphicx}
- % declare the path(s) where your graphic files are
- % \graphicspath{{../pdf/}{../jpeg/}}
- % and their extensions so you won't have to specify these with
- % every instance of \includegraphics
- % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
-%\else
- % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
- % will default to the driver specified in the system graphics.cfg if no
- % driver is specified.
\usepackage[dvips]{graphicx}
- % declare the path(s) where your graphic files are
- % \graphicspath{{../eps/}}
- % and their extensions so you won't have to specify these with
- % every instance of \includegraphics
- % \DeclareGraphicsExtensions{.eps}
-%\fi
\usepackage{url}
\usepackage[cmex10]{amsmath}
\begin{document}
-\title{Using Altruistic Peers to Supplement Downloading Bandwidth}
+\title{Using Altruistic Peers to Help With Free Web Downloads}
\author{\IEEEauthorblockN{Cameron Dale}
\IEEEauthorblockA{School of Computing Science\\
Simon Fraser University\\
\maketitle
\begin{abstract}
+A large amount of free content is available over the Internet from
+many different sources. Most of this content uses the traditional
+client-server model of requests from users. However, there is an
+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. We present a general technique for
+satisfying the needs of this P2P distribution, which is 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 file as a key. We then go further and implement a solution for
+the distribution of Debian software packages.
\end{abstract}
-%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{intro}
+There are a large number of free content distributors with using
+package distribution systems over the Internet to distribute content
+to their users. These distributors have developed many different
+methods for this distribution, but they mostly 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
+content, 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, including distributed hash tables (DHT) and
+BitTorrent. The model relies on the pre-existence of cryptographic
+hashes of the content, 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 mirrors. The peer can then share this new
+content with others.
-%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+First, we examine the opportunity that is available for many of
+these free content distributors. We present an overview of a system
+that would efficiently satisfy the demands of a large number of
+users, and should substantially reduce the currently substantial
+bandwidth requirements of hosting this content. 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 content distributors of the
+opportunity that can be met with such a system.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}
\label{related}
+There are many peer-to-peer implementations available today, but
+none is very well suited to this specific problem.
+
+Many distributors make their content 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 amounts of content that they are not
+interested in, and prevents them from updating to new content
+without downloading another image containing a lot of the same
+content they already have. There have also been other attempted
+implementations, usually based on some form of BitTorrent, to
+address this problem. Unfortunately, BitTorrent is not ideally
+suited to an application such as this one, for the following
+reasons:
+\begin{itemize}
+ \item The packages are too small and there are too many to create
+ individual torrents for each one.
+ \item All the packages together are too large to track efficiently
+ as a single torrent.
+ \item BitTorrent's piece sizes are bigger than many of the
+ packages, which wastes bandwidth downloading parts of other
+ packages.
+ \item A small number of the packages can be updated every day,
+ which may require a new torrent, therefore splitting the
+ download population.
+ \item Incentives to share (upload) are no longer needed, as the
+ content is freely available for anyone to download without
+ sharing (seeds are also not needed).
+\end{itemize}
+
+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 content available, but it ignores
+the smaller content, which is often the more requested content.
+DebTorrent \cite{debtorrent} makes widespread modifications to a
+traditional BitTorrent client, but also requires some changes to the
+distribution system to support it, and separates peers into groups
+based on their characteristics which limits the effectiveness of the
+sharing. 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{Situation}
+\label{situation}
+
+There are a large number of groups using the Internet to distribute
+their free content. This content is usually available from a free
+download site, which usually requires a network of mirrors to
+support the large number of requests. This content almost always
+supports 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 a network of mirrors. The
+Debian project \cite{debian} (and other Debian-based distributions)
+uses the \texttt{apt} program, which downloads Debian packages in
+the \texttt{.deb} format from one of many 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. Red Hat's Fedora project
+\cite{fedora} (and other RPM-based distributions) use the
+\texttt{yum} program to obtain RPMs, and Gentoo \cite{gentoo} uses
+\texttt{portage} in a similar way.
+
+Other software vendors also use a similar system. CPAN \cite{cpan}
+distrbutes files containing software packages for the PERL
+programming language. CYGWIN \cite{cygwin} provides many of the
+standard Unix/Linux tools in a Windows environment, also 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).
+
+Finally, there are other programs that use cryptographic hashing to
+identify files. Git is a version control system in which all files,
+commits, and tags, are identified by their SHA1 hash. These hashes
+are used to verify the origin of these items, but are also used when
+clients update their local files with new remote information.
+
+\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 avaliable for anyone to freely download.
+ \item The content is divided into packages, each of which contains
+ a small independent part of all the content.
+ \item No peers are interested in downloading all of the content
+ available.
+ \item Hashes of the content and its size are available before the
+ download is attempted.
+ \item Requests for the content 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 content 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 \emph{give back}
+to the volunteer community that has created the content 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. For one, though they sometimes
+distribute nearly identical content (e.g. the same software
+available in multiple Linux distributions), it is not exactly
+identical and has usually been tailored to the system. The small
+differences will make it impossible to distribute similar content
+across systems. And, although peer-to-peer systems 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.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Opportunity}
+\label{opportunity}
+
+The situation described in section \ref{situation} presents a clear
+opportunity to use some form of peer-to-peer file sharing protocols.
+This sparse interest in a large number of packages, and 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
+content package that hashes to that key. A downloading peer can then
+lookup the package hash in the DHT, and then, if it is found,
+download the file from those peers and verify the content. If the
+package hash can not be found in the DHT, the peer will fallback to
+downloading from the original content location (i.e. the network of
+mirrors), and once complete will add a new entry to the DHT
+indicating that it has the package.
+
+\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 into the software, though this can be
+difficult as the DHT should be running at all times, both for
+efficient lookups and to support uploading of already downloaded
+content. Many of the package management software implmentations use
+HTTP requests to download the files, which makes it possible to
+implement the P2P aspect as a standard HTTP caching proxy, which
+will get uncached requests first from the P2P system, and then
+fallback to the normal HTTP request from a server. For methods that
+don't use HTTP requests, other types of proxies may also be
+possible.
+
+\subsection{Downloading From Peers}
+\label{downloading}
+
+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 sub-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 sub-piece size), this parallel downloading is not necessary, or
+even desirable. However, this method can still be used in
+conjunction with the DHT, for the larger packages that are
+available.
+
+In addition to storing the file download location (which would still
+be used for small files), a peer will store a \emph{torrent string}
+containing the peer's hashes of the individual pieces for 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 downloaded pieces.
+
+For very large files (about 5 or more pieces), the torrent strings
+are too long to store in the DHT (a single UDP packet should be less
+than 1472 bytes to avoid fragmentation). 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 would be a hash 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 would give the torrent-like string.
+Otherwise, a request to the peer for the hash (just like files are
+downloaded), should return the torrent string.
+
+% This can cause a problem with hash checking the returned data, as
+% hashes for the pieces are not known. Any file that fails a hash
+% check should be downloaded again, with each piece being downloaded
+% from different peers than it was previously. The peers are shifted
+% by 1, so that if a peers previously downloaded piece i, it now
+% downloads piece i+1, and the first piece is downloaded by the
+% previous downloader of the last piece, or preferably a previously
+% unused peer. As each piece is downloaded the running hash of the
+% file should be checked to determine the place at which the file
+% differs from the previous download.
+%
+% If the hash check then passes, then the peer who originally provided
+% the bad piece can be assessed blame for the error. Otherwise, the
+% peer who originally provided the piece is probably at fault, since
+% he is now providing a later piece. This doesn't work if the
+% differing piece is the first piece, in which case it is downloaded
+% from a 3rd peer, with consensus revealing the misbehaving peer.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Sample Implementation}
+\label{implementation}
+
+A sample implementation has been created that functions as described
+in section \ref{opportunity}. This software, called
+\texttt{apt-dht}, interacts with the \texttt{apt} tool found in most
+Debian-based Linux distributions. Our tool 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, 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 requests to a
+server, the implementation takes the form of a caching HTTP proxy.
+Pointing a standard apt implementation to use the proxy is as simple
+as prepending the proxy location and port to the front of the mirror
+name (i.e. ``localhost:9977/mirrorname.debian.org/\ldots'').
+
+The DHT is based on Khashmir, which is an implementation of the
+Kademlia DHT using methods familiar to BitTorrent developers. The
+communication is all handled by UDP messages, and RPC requests are
+bencoded similar to torrent files. Khashmir uses the high-level
+Twisted event-driven networking engine, so Twisted is also used for
+all other networking needs.
+
+The torrent strings stored in the DHT are all bencoded dictionaries
+containing similar information to what is in a torrent file. This
+includes the piece size used, the length of the piece hash, and of
+course the hashes of all the sub-pieces of the content.
+
+Downloading is accomplished by sending simple HTTP requests to the
+peer's identified by lookups in the DHT to have the desired file.
+The HTTP server used for the proxy also doubles as the server
+listeneing 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.
+\begin{figure}
+\centering
+\includegraphics[width=\columnwidth]{apt_dht_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}
-%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+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
+sub-piece information to download. We have chosen a maximum 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 the user for the torrent string.
-\section{Background}
-\label{background}
+\subsection{Current Status}
+\label{status}
+Though functional and useful, the current implementation is not
+complete, and is missing some of the downloading details necessary
+to make it complete. It operates as a caching HTTP proxy, serving
+requests from apt and other peers. Index files are identified by the
+current implementation, and parsed to find hashed of files for DHT
+lookups if they are later requested. Files are downloaded from
+peers, and those not available in peers are downloaded correctly
+from the mirror. Any downloaded files are hash checked to verify
+them, and then added to the DHT.
+However, the current implementation does not use the sub-piece
+hashing described in section \ref{downloading}, or any parallelizing
+of downloads. Instead, it currently chooses a peer at random from
+the list of possible peers, and downloads the entire file from that
+peer, regardless of the size of the file. This needs to change if
+both a) the file is large (more than 512 KB), and b) there are
+multiple peers with the file. The storage and retrieval of sub-piece
+hashes has not yet been finalized though, and until it is this final
+step is not possible.
-%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%% 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 content
+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 content.
+We have also implemented our design in software to be used in
+conjuction with Debian-based distribution of Linux software
+packages. It will soone be in use by many users of the Debian
+project's distribution, and so serves as an example of the
+possibilities that exist.
\bibliographystyle{IEEEtran}
\bibliography{./IEEEabrv,./all}
projects / quix0rs-apt-p2p.git / blobdiff