1 \documentclass[conference]{IEEEtran}
\r
6 \def\@oddhead{\mbox{}\scriptsize\rightmark \hfil \thepage}%
\r
7 \def\@evenhead{\scriptsize\thepage \hfil\leftmark\mbox{}}%
\r
11 \pagestyle{headings}
\r
13 \usepackage[noadjust]{cite}
\r
15 \usepackage[dvips]{graphicx}
\r
21 \title{\texttt{apt-p2p}: A Peer-to-Peer Distributor for Free Software Package Release and Update}
\r
22 \author{\IEEEauthorblockN{Cameron Dale}
\r
23 \IEEEauthorblockA{School of Computing Science\\
\r
24 Simon Fraser University\\
\r
25 Burnaby, British Columbia, Canada\\
\r
26 Email: camerond@cs.sfu.ca}
\r
28 \IEEEauthorblockN{Jiangchuan Liu}
\r
29 \IEEEauthorblockA{School of Computing Science\\
\r
30 Simon Fraser University\\
\r
31 Burnaby, British Columbia, Canada\\
\r
32 Email: jcliu@cs.sfu.ca}}
\r
37 A large amount of free software packages are available over the
\r
38 Internet from many different distributors. Most of these
\r
39 distributors use the traditional client-server model to handle
\r
40 requests from users. However, there is an excellent opportunity to
\r
41 use peer-to-peer techniques to reduce the cost of much of this
\r
42 distribution, especially due to the altruistic nature of many of
\r
43 these users. There are no existing solution suitable for this
\r
44 situation, so we present a new technique for satisfying the needs of
\r
45 this P2P distribution, which is generally applicable to many of
\r
46 these distributors' systems. Our method makes use of a DHT for
\r
47 storing the location of peers, using the cryptographic hash of the
\r
48 package as a key. To show the simplicity and functionality, we
\r
49 implement a solution for the distribution of Debian software
\r
50 packages, including the many DHT customizations needed. Finally, we
\r
51 analyze our system to determine how it is performing and what effect
\r
55 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
57 \section{Introduction}
\r
60 There are a large number of free software package distributors using
\r
61 package distribution systems over the Internet to distribute
\r
62 software to their users. These distributors have developed many
\r
63 different methods for this distribution, but they almost exclusively
\r
64 use a client-server model to satisfy user requests. The popularity
\r
65 and number of users results in a large number of requests, which
\r
66 usually requires a network of mirrors to handle. Due to the free
\r
67 nature of this software, many users are willing and able to
\r
68 contribute upload bandwidth to this distribution, but have no
\r
69 current way to do this.
\r
71 We present a new peer-to-peer distribution model to meet these
\r
72 demands. It is based on many previous implementations of successful
\r
73 peer-to-peer protocols, especially distributed hash tables (DHT) and
\r
74 BitTorrent. The model relies on the pre-existence of cryptographic
\r
75 hashes of the packages, which should uniquely identify it for a
\r
76 request from other peers. If the peer-to-peer download fails, then
\r
77 the original request to the server is used as a fallback to prevent
\r
78 any dissatisfaction from users. The peer can then share this new
\r
79 package with others through the P2P system.
\r
81 First, we examine the opportunity that is available for many of
\r
82 these free software package distributors. We present an overview of
\r
83 a system that would efficiently satisfy the demands of a large
\r
84 number of users, and should significantly reduce the currently
\r
85 substantial bandwidth requirements of hosting this software. We then
\r
86 present an example implementation based on the Debian package
\r
87 distribution system. This implementation will be used by a large
\r
88 number of users, and serves as an example for other free software
\r
89 distributors of the opportunity that can be met with such a system.
\r
91 The rest of this paper is organized as follows. The background and motivation are presented in Section \ref{situation}, together with related works in Section \ref{related}. We propose
\r
92 our solution in Section \ref{opportunity}. We then detail our sample
\r
93 implementation for Debian-based distributions in Section
\r
94 \ref{implementation}, including an in-depth look at our DHT
\r
95 customizations in Section \ref{custom_dht}. Its performance is evaluated in Section \ref{analysis}. Finally,
\r
96 Section \ref{conclusions} concludes the paper and offers some future directions.
\r
98 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
100 \section{Background and Motivations}
\r
103 In the free software society, there are a large number of groups using the Internet to
\r
104 collaboratively develop and release their software. The ever increasing power of
\r
105 modern programming languages and operating systems has made these software, like commercial software, extremely large and complex, which often
\r
106 consists of many small units (packages). Together with their popularity among users,
\r
107 an efficient and reliable management and distribution of these packages over the Internet has become an daunting task. In this section, we offer concrete examples illustrating the
\r
108 unique challenges in this context.
\r
110 \subsection{Free Software Package Distributor: Examples}
\r
114 Most Linux distributions use a software package management system
\r
115 that fetches packages to be installed from an archive of packages
\r
116 hosted on a network of mirrors. The Debian project, and other
\r
117 Debian-based distributions such as Ubuntu and Knoppix, use the
\r
118 \texttt{apt} (Advanced Package Tool) program, which downloads Debian
\r
119 packages in the \texttt{.deb} format from one of many HTTP mirrors.
\r
120 The program will first download index files that contain a listing
\r
121 of which packages are available, as well as important information
\r
122 such as their size, location, and a hash of their content. The user
\r
123 can then select which packages to install or upgrade, and
\r
124 \texttt{apt} will download and verify them before installing them.
\r
126 There are also several similar frontends for the RPM-based
\r
127 distributions. Red Hat's Fedora project uses the \texttt{yum}
\r
128 program, SUSE uses \texttt{YAST}, while Mandriva has
\r
129 \texttt{Rpmdrake}, all of which are used to obtain RPMs from
\r
130 mirrors. Other distributions use tarballs (\texttt{.tar.gz} or
\r
131 \texttt{.tar.bz2}) to contain their packages. Gentoo's package
\r
132 manager is called \texttt{portage}, SlackWare Linux uses
\r
133 \texttt{pkgtools}, and FreeBSD has a suite of command-line tools,
\r
134 all of which download these tarballs from web servers.
\r
136 Similar tools have been used for other software packages. CPAN
\r
137 distributes software packages for the PERL
\r
138 programming language, using SOAP RPC requests to find and download
\r
139 files. Cygwin provides many of the
\r
140 standard Unix/Linux tools in a Windows environment, using a
\r
141 package management tool that requests packages from websites. There
\r
142 are two software distribution systems for Mac OSX, fink and
\r
143 MacPorts, that also retrieve packages in this way.
\r
145 Direct web downloading is also a common way, often coupled with a hash
\r
146 verification file to be downloaded next to the desired
\r
147 file. The hash file usually have the same file name, but with an
\r
148 added extension identifying the hash used (e.g. \texttt{.md5} for
\r
149 the MD5 hash). This type of file downloading and verification is
\r
150 typical of free software hosting facilities that are open to anyone
\r
151 to use, such as SourceForge.
\r
154 Given the free nature of these software, there are often a number of users
\r
155 motivated by altruism to want to help out with their distribution.
\r
156 This is particularly true considering that many of these software are used by
\r
157 groups that are staffed mostly, or sometimes completely, by
\r
158 volunteers. They are thus motivated to contribute their network resources, so as to promote the healthy development
\r
159 of the volunteer community that released the software. As a matter of fact,
\r
160 we have see many free mirror sites hosting these software packages for downloading.
\r
161 We also naturally expect that peer-to-peer distribution can be implementation in
\r
162 this context, which scale well with large user bases and can easily explore the network resources made available by
\r
167 \subsection{Unique Characteristics}
\r
170 While it seems straightforward to use an existing peer-to-peer file sharing tool like BitTorrent for
\r
171 free software package distribution, there are indeed a series of new challenges in this unique scenario:
\r
173 \subsubsection{Archive Dimensions}
\r
175 While most of the packages of a software release are very small in
\r
176 size, there are some that are quite large. There are too many
\r
177 packages to distribute each individually, but the archive is also
\r
178 too large to distribute in its entirety. In some archives there are
\r
179 also divisions of the archive into sections, e.g. by the operating system (OS) or computer
\r
180 architecture that the package is intended for.
\r
184 \includegraphics[width=\columnwidth]{apt_p2p_simulation-size_CDF.eps}
\r
185 \caption{The CDF of the size of packages in a Debian system, both
\r
186 for the actual size and adjusted size based on the popularity of
\r
191 For example, Figure~\ref{size_CDF} shows the size of the packages in the
\r
192 current Debian distribution. While 80\% of the packages are less than
\r
193 512~KB, some of the packages are hundreds of megabytes. The entire
\r
194 archive consists of 22,298 packages and is approximately 119,000 MB
\r
195 in size. Most of the packages are to be installed in any computer environment, but there are
\r
196 also OS- or architecture-specific packages, as shown by the adjusted sizes based on popularity of the packages. ((((more words on how the size is adjusted by popularity))))
\r
198 \subsubsection{Package Updates}
\r
200 The software packages being distributed are being constantly
\r
201 updated. These updates could be the result of the software creators
\r
202 releasing a new version with improved functionality,
\r
203 or the distributor updating their packaging of the
\r
204 software to meet new requirements. Even if the distributor
\r
205 periodically makes \emph{stable} releases, which are snapshots of
\r
206 all the packages in the archive at a certain time, updates are still
\r
207 released for security issues or serious bugs.
\r
211 \includegraphics[width=\columnwidth]{size-quarter.eps}
\r
212 \caption{The amount of data in the Debian archive that is updated
\r
213 each day, broken down by architecture.}
\r
214 \label{update_size}
\r
217 For example, Figure~\ref{update_size} shows the amount of data in
\r
218 the Debian archive that was updated each day over a period of 3
\r
219 months. In every single day, approximately 1.5\% of the 119,000 MB archive is
\r
220 updated with new versions of packages. Note that this frequency is much higher than
\r
221 that of most commercial software, mainly because many free software are
\r
222 developed in a loosely management environment with developers working
\r
223 asynchronously from worldwide.
\r
225 \subsubsection{Limited Interest}
\r
227 Finally, though there are a large number of packages and a large number of
\r
228 users, the interest in a particular version of a package can be very
\r
229 limited. Specifically, there are core packages that every user has to download, but most
\r
230 packages would fall in the category of optional or extra, and so are
\r
231 interesting to only a limited number of people.
\r
235 \includegraphics[width=\columnwidth]{apt_p2p_popularity-cdf.eps}
\r
236 \caption{The CDF of the popularity of packages in a Debian system.}
\r
237 \label{popularity_CDF}
\r
240 For example, the Debian distribution tracks the popularity of its
\r
241 packages using popcon \cite{popcon}. Figure~\ref{popularity_CDF}
\r
242 shows the cumulative distribution function of the percentage of all
\r
243 users who install each package. Though some packages are installed
\r
244 by everyone, 80\% of the packages are installed by less than 1\% of
\r
248 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
250 \subsection{Why BitTorrent Doesn't Work Well}
\r
253 Recently, many distributors make their software available using
\r
254 BitTorrent \cite{COHEN03}, in particular, for the distribution of CD
\r
255 images. This straightforward use however is far ineffective, as it requires the
\r
256 peers to download large numbers of packages that they are not
\r
257 interested in, and prevents them from updating to new packages
\r
258 without downloading another image containing a lot of the same
\r
259 packages they already have.
\r
261 An alternative is to create torrents tracking individual packages. Unfortunately, we find that this enhancement can be
\r
262 quite difficult given the unique characteristic of free software packages.
\r
264 First, there is no obvious way to divide the packages into torrents.
\r
265 Most of the packages are too small, and there are too many packages
\r
266 in the entire archive to create individual torrents for each one.
\r
267 On the other hand, all the packages together are too large to track
\r
268 efficiently as a single torrent. Hence, some division of the archive's
\r
269 packages into torrents is obviously necessary, but wherever that
\r
270 split occurs it will cause either some duplication of connections,
\r
271 or prevent some peers from connecting to others who do have the same
\r
272 content. In addition, a small number of the packages can be updated every
\r
273 day which would add new files to the torrent, thereby changing its
\r
274 \emph{infohash} identifier and making it a new torrent. This will
\r
275 severely fracture the download population, even though peers in the
\r
276 new torrent may share 99\% of the packages in common with peers in the
\r
279 Other issues also prevent BitTorrent from being a good solution to
\r
280 this problem. In particular, BitTorrent's fixed piece sizes (?KB) that disregard file
\r
281 boundaries are bigger than many of the packages in the archive. This
\r
282 will waste peers' downloading bandwidth as they will end up
\r
283 downloading parts of other packages just to get the piece that
\r
284 contains the package they do want.
\r
286 Finally, note that BitTorrent downloads files
\r
287 randomly, which does not work well with the interactive package
\r
288 management tools expectation of sequential downloads. On the other hand, with altruistic peers, incentives to share (upload)
\r
289 become a less important issue, and the availability of seeds are not critical, either, as the mirror sites
\r
290 can serve in that capacity.
\r
294 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
296 \section{Peer-to-Peer Assisted Distributor: An Overview}
\r
297 \label{opportunity}
\r
299 The situation described in section \ref{situation} presents a clear
\r
300 opportunity to use some form of peer-to-peer file-sharing protocol
\r
301 to allow willing users to contribute upload bandwidth. This sparse
\r
302 interest in a large number of packages undergoing constant updating
\r
303 is well suited to the functionality provided by a Distributed Hash
\r
304 Table (DHT). DHTs require unique keys to store and retrieve strings
\r
305 of data, for which the cryptographic hashes used by these package
\r
306 management systems are perfect for. The stored and retrieved strings
\r
307 can then be pointers to the peers that have the package that hashes
\r
308 to that key. A downloading peer can lookup the package hash in the
\r
309 DHT and, if it is found, download the file from those peers and
\r
310 verify the package with the hash. Once the download is complete, the
\r
311 peer will add its entry to the DHT indicating that it now has the
\r
314 The fact that this package is also available to download for free
\r
315 from a server is very important to our proposal. If the package hash
\r
316 can not be found in the DHT, the peer can then fallback to
\r
317 downloading from the original location (i.e. the network of
\r
318 mirrors). The mirrors thus, with no modification to their
\r
319 functionality, serve as seeds for the packages in the peer-to-peer
\r
320 system. Any packages that have just been updated, or that are very
\r
321 rare, and so don't have any peers available can always be found on
\r
322 the mirror. Once the peer has completed the download from the mirror
\r
323 and verified the package, it can then add itself to the DHT as the
\r
324 first peer for the new package, so that future requests from peers
\r
325 will not need the mirror.
\r
327 The trust of the package is also always guaranteed through the use
\r
328 of the cryptographic hashes. Nothing can be downloaded from a peer
\r
329 until the hash is looked up in the DHT, so a hash must first come
\r
330 from a trusted source (i.e. a mirror). Most distributors use index
\r
331 files that contain hashes for a large number of the packages in
\r
332 their archive, and which are also hashed. After retrieving the
\r
333 index's hash from the mirror, the index file can be downloaded from
\r
334 peers and verified. Then the program has access to all the hashes of
\r
335 the packages it will be downloading, all of which can be verified
\r
336 with a \emph{chain of trust} that stretches back to the original
\r
337 distributor's server.
\r
339 \subsection{Implementation Options}
\r
340 \label{imp_options}
\r
342 There are several ways to implement the desired P2P functionality
\r
343 into the existing package management software. The functionality can
\r
344 be directly integrated through modifications to the software, though
\r
345 this could be difficult as the P2P functionality should be running
\r
346 at all times. This is needed both for efficient lookups and to
\r
347 support uploading of already downloaded packages. Unfortunately, the
\r
348 package management tools typically only run until the download and
\r
349 install request is complete.
\r
351 Many of the package management software implementations use HTTP
\r
352 requests from web servers to download the packages, which makes it
\r
353 possible to implement the P2P aspect as an almost standard HTTP
\r
354 caching proxy. This proxy will run as a daemon in the background,
\r
355 listening for requests from the package management tool for package
\r
356 files. It will get uncached requests first from the P2P system, or
\r
357 falling back to the normal HTTP request from a server should it not
\r
358 be found. For methods that don't use HTTP requests, other types of
\r
359 proxies may also be possible.
\r
361 \subsection{Downloading From Peers}
\r
362 \label{downloading}
\r
364 Although not necessary, we recommend implementing a download
\r
365 protocol that is similar to the protocol used to fetch packages from
\r
366 the distributor's servers. This simplifies the P2P program, as it
\r
367 can then treat peers and mirrors almost identically when requesting
\r
368 packages. In fact, the mirrors can be used when there are only a few
\r
369 slow peers available for a file to help speed up the download
\r
372 Downloading a file efficiently from a number of peers is where
\r
373 BitTorrent shines as a peer-to-peer application. Its method of
\r
374 breaking up larger files into pieces, each with its own hash,
\r
375 makes it very easy to parallelize the downloading process and
\r
376 maximize the download speed. For very small packages (i.e. less than
\r
377 the piece size), this parallel downloading is not necessary, or
\r
378 even desirable. However, this method should still be used, in
\r
379 conjunction with the DHT, for the larger packages that are
\r
382 Since the package management system only stores a hash of the entire
\r
383 package, and not of pieces of that package, we will need to be able
\r
384 to store and retrieve these piece hashes using the P2P protocol. In
\r
385 addition to storing the file download location in the DHT (which
\r
386 would still be used for small files), a peer will store a
\r
387 \emph{torrent string} containing the peer's hashes of the pieces of
\r
388 the larger files. These piece hashes could be compared ahead of time
\r
389 to determine which peers have the same piece hashes (they all
\r
390 should), and then used during the download to verify the pieces of
\r
391 the downloaded package.
\r
393 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
395 \section{\texttt{apt-p2p}: A Practical Implementation}
\r
396 \label{implementation}
\r
398 We have created a sample implementation that functions as described
\r
399 in section \ref{opportunity}, and is freely available for other
\r
400 distributors to download and modify \cite{apt-p2p}. This software,
\r
401 called \texttt{apt-p2p}, interacts with the \texttt{apt} tool, which
\r
402 is found in most Debian-based Linux distributions. \texttt{apt} uses
\r
403 SHA1 hashes to verify most downloaded files, including the large
\r
404 index files that contain the hashes of the individual packages. We
\r
405 chose this distribution system as it is familiar to us, it allows
\r
406 software contributions, and there are interesting statistics
\r
407 available for analyzing the popularity of the software packages
\r
410 Since all requests from apt are in the form of HTTP downloads from a
\r
411 server, the implementation takes the form of a caching HTTP proxy.
\r
412 Making a standard \texttt{apt} implementation use the proxy is then
\r
413 as simple as prepending the proxy location and port to the front of
\r
414 the mirror name in \texttt{apt}'s configuration file (i.e.
\r
415 ``localhost:9977/mirrorname.debian.org/\ldots'').
\r
417 We created a customized DHT based on Khashmir \cite{khashmir}, which
\r
418 is an implementation of Kademlia \cite{kademlia} using methods
\r
419 familiar to BitTorrent developers. Khashmir is also the same DHT
\r
420 implementation used by most of the existing BitTorrent clients to
\r
421 implement trackerless operation. The communication is all handled by
\r
422 UDP messages, and RPC (remote procedure call) requests and responses
\r
423 are all \emph{bencoded} in the same way as BitTorrent's
\r
424 \texttt{.torrent} files. Khashmir uses the high-level Twisted
\r
425 event-driven networking engine \cite{twisted}, so we also use
\r
426 Twisted in our sample implementation for all other networking needs.
\r
427 More details of this customized DHT can be found below in section
\r
430 Downloading is accomplished by sending simple HTTP requests to the
\r
431 peers identified by lookups in the DHT to have the desired file.
\r
432 Requests for a package are made using the package's hash, properly
\r
433 encoded, as the URL to request from the peer. The HTTP server used
\r
434 for the proxy also doubles as the server listening for requests for
\r
435 downloads from other peers. All peers support HTTP/1.1, both in the
\r
436 server and the client, which allows for pipelining of multiple
\r
437 requests to a peer, and the requesting of smaller pieces of a large
\r
438 file using the Range request header.
\r
440 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
442 \section{Customized DHT}
\r
445 A large contribution of our work is in the customization and use of
\r
446 a Distributed Hash Table (DHT). Although our DHT is based on
\r
447 Kademlia, we have made many improvements to it to make it suitable
\r
448 for this application. In addition to a novel storage technique to
\r
449 support piece hashes, we have improved the response time of looking
\r
450 up queries, allowed the storage of multiple values for each key, and
\r
451 incorporated some improvements from BitTorrent's tracker-less DHT
\r
454 \subsection{Kademlia Background}
\r
457 The Kademlia DHT, like most other DHTs, assigns IDs to peers from
\r
458 the same space that is used for keys. The peers with IDs closest to
\r
459 the desired key will then store the values for that key. Lookups are
\r
460 recursive, as nodes are queried in each step that are exponentially
\r
461 closer to the key than in the previous step.
\r
463 Nodes in a Kademlia system support four primitive requests.
\r
464 \texttt{ping} will cause a peer to return nothing, and is only used
\r
465 to determine if a node is still alive, while \texttt{store} tells a
\r
466 node to store a value associated with a given key. The most
\r
467 important primitives are \texttt{find\_node} and
\r
468 \texttt{find\_value}, which both function recursively to find nodes
\r
469 close to a key. The queried nodes will return a list of the nodes
\r
470 they know about that are closest to the key, allowing the querying
\r
471 node to quickly traverse the DHT to find the nodes close to the
\r
472 desired key. The only difference between them is that the
\r
473 \texttt{find\_value} query will cause a node to return a value, if
\r
474 it has one for that key, instead of a list of nodes.
\r
476 \subsection{Piece Hash Storage}
\r
479 Hashes of pieces of the larger package files are needed to support
\r
480 their efficient downloading from multiple peers.
\r
481 For large files (5 or more pieces), the torrent strings described in
\r
482 section \ref{downloading}
\r
483 are too long to store with the peer's download info in the DHT. This
\r
484 is due to the limitation that a single UDP packet should be less
\r
485 than 1472 bytes to avoid fragmentation.
\r
486 % For example, for a file of 4 pieces, the peer would need to store a
\r
487 % value 120 bytes in size (IP address, port, four 20-byte pieces and
\r
488 % some overhead), which would limit a return value from including more
\r
489 % than 10 values to a request.
\r
491 Instead, the peers will store the torrent string for large files
\r
492 separately in the DHT, and only contain a reference to it in their
\r
493 stored value for the hash of the file. The reference is an SHA1 hash
\r
494 of the entire concatenated length of the torrent string. If the
\r
495 torrent string is short enough to store in the DHT (i.e. less than
\r
496 1472 bytes, or about 70 pieces for the SHA1 hash), then a lookup of
\r
497 that hash in the DHT will return the torrent string. Otherwise, a
\r
498 request to the peer for the hash (using the same method as file
\r
499 downloads, i.e. HTTP), will cause the peer to return the torrent
\r
502 Figure \ref{size_CDF} shows the package size of the 22,298 packages
\r
503 available in Debian in January 2008. We can see that most of the
\r
504 packages are quite small, and so most will therefore not require
\r
505 piece hash information to download. We have chosen a piece
\r
506 size of 512 kB, which means that 17,515 (78\%) of the packages will
\r
507 not require this information. There are 3054 packages that will
\r
508 require 2 to 4 pieces, for which the torrent string can be stored
\r
509 directly with the package hash in the DHT. There are 1667 packages
\r
510 that will require a separate lookup in the DHT for the longer
\r
511 torrent string as they require 5 to 70 pieces. Finally, there are
\r
512 only 62 packages that require more than 70 pieces, and so will
\r
513 require a separate request to a peer for the torrent string.
\r
515 \subsection{Response Time}
\r
516 \label{response_time}
\r
518 Most of our customizations to the DHT have been to try and improve
\r
519 the time of the recursive \texttt{find\_value} requests, as this can
\r
520 cause long delays for the user waiting for a package download to
\r
521 begin. The one problem that slows down such requests is waiting for
\r
522 timeouts to occur before marking the node as failed and moving on.
\r
524 Our first improvement is to retransmit a request multiple times
\r
525 before a timeout occurs, in case the original request or its
\r
526 response was lost by the unreliable UDP protocol. If it does not
\r
527 receive a response, the requesting node will retransmit the request
\r
528 after a short delay. This delay will increase exponentially for
\r
529 later retransmissions, should the request again fail. Our current
\r
530 implementation will retransmit the request after 2 seconds and 6
\r
531 seconds (4 seconds after the first retransmission), and then timeout
\r
534 We have also added some improvements to the recursive
\r
535 \texttt{find\_node} and \texttt{find\_value} queries to speed up the
\r
536 process when nodes fail. If enough nodes have responded to the
\r
537 current query such that there are many new nodes to query that are
\r
538 closer to the desired key, then a stalled request to a node further
\r
539 away will be dropped in favor of a new request to a closer node.
\r
540 This has the effect of leap-frogging unresponsive nodes and
\r
541 focussing attention on the nodes that do respond. We will also
\r
542 prematurely abort a query while there are still oustanding requests,
\r
543 if enough of the closest nodes have responded and there are no
\r
544 closer nodes found. This prevents a far away unresponsive node from
\r
545 making the query's completion wait for it to timeout.
\r
547 Finally, we made all attempts possible to prevent firewalled and
\r
548 NATted nodes from being added to the routing table for future
\r
549 requests. Only a node that has responded to a request from us will
\r
550 be added to the table. If a node has only sent us a request, we
\r
551 attempt to send a \texttt{ping} to the node to determine if it is
\r
552 NATted or not. Unfortunately, due to the delays used by NATs in
\r
553 allowing UDP packets for a short time if one was recently sent by
\r
554 the NATted host, the ping is likely to succeed even if the node is
\r
555 NATted. We therefore also schedule a future ping to the node to make
\r
556 sure it is still reachable after the NATs delay has hopefully
\r
557 elapsed. We also schedule future pings of nodes that fail once to
\r
558 respond to a request, as it takes multiple failures (currently 3)
\r
559 before a node is removed from the routing table.
\r
561 \subsection{Multiple Values}
\r
562 \label{multiple_values}
\r
564 The original design of Kademlia specified that each keywould have
\r
565 only a single value associated with it. The RPC to find this value
\r
566 was called \texttt{find\_value} and worked similarly to
\r
567 \texttt{find\_node}, iteratively finding nodes with ID's closer to
\r
568 the desired key. However, if a node had a value stored associated
\r
569 with the searched for key, it would respond to the request with that
\r
570 value instead of the list of nodes it knows about that are closer.
\r
572 While this works well for single values, it can cause a problem when
\r
573 there are multiple values. If the responding node is no longer one
\r
574 of the closest to the key being searched for, then the values it is
\r
575 returning will probably be the staler ones in the system, and it
\r
576 will not have the latest stored values. However, the search for
\r
577 closer nodes will stop here, as the queried node only returned the
\r
578 values and not a list of nodes to recursively query. We could have
\r
579 the request return both the values and the list of nodes, but that
\r
580 would severely limit the size and number of the values that could be
\r
583 Instead, we have broken up the original \texttt{find\_value}
\r
584 operation into two parts. The new \texttt{find\_value} request
\r
585 always returns a list of nodes that the node believes are closest to
\r
586 the key, as well as a number indicating the number of values that
\r
587 this node has for the key. Once a querying node has finished its
\r
588 search for nodes and found the closest ones to the key, it can issue
\r
589 \texttt{get\_value} requests to some nodes to actually retrieve the
\r
590 values they have. This allows for much more control of when and how
\r
591 many nodes to query for values. For example, a querying node could
\r
592 abort the search once it has found enough values in some nodes, or
\r
593 it could choose to only request values from the nodes that are
\r
594 closest to the key being searched for.
\r
596 \subsection{BitTorrent's Improvements}
\r
597 \label{bittorrent_dht}
\r
599 In the many years that some BitTorrent clients have been using a
\r
600 Kademlia based DHT for tracker-less operation, the developers have
\r
601 made many enhancements which we can take advantage of. One of the
\r
602 most important is a security feature added to stop malicious nodes
\r
603 from subscribing other nodes as downloaders. When a node issues a
\r
604 request to another node to store its download info for that key, it
\r
605 must include a \emph{token} returned by the storing node in a recent
\r
606 \texttt{find\_node} request. The token is created by hashing the IP
\r
607 address of the requesting peer with a temporary secret that expires
\r
608 after several minutes. This prevents the requesting peer from faking
\r
609 its IP address in the store request, since it must first receive a
\r
610 response from a \texttt{find\_node} on that IP.
\r
612 We also made some BitTorrent-inspired changes to the parameters of
\r
613 the DHT originally specified by the authors of Kademlia. Since, as
\r
614 we will show later, peers stay online in our system for much longer
\r
615 periods of time, we reduced Kademlia's \emph{k} value from 20 to 8.
\r
616 The value is supposed to be large enough such that any given
\r
617 \emph{k} nodes are unlikely to fail within an hour of each other,
\r
618 which is very unlikely in our system given the long uptimes of
\r
619 nodes. We also increased the number of concurrent outstanding
\r
620 requests allowed from 3 to 6 to speed up the recursive key finding
\r
623 \subsection{Other Changes}
\r
624 \label{other_changes}
\r
626 We added one other new RPC request that nodes can make:
\r
627 \texttt{join}. This request is only sent on first loading the DHT,
\r
628 and is usually only sent to the bootstrap nodes that are listed for
\r
629 the DHT. These bootstrap nodes will respond to the request with the
\r
630 requesting peer's IP and port, so that the peer can determine what
\r
631 its oustide IP address is and whether port translation is being
\r
632 used. In the future, we hope to add functionality similar to STUN
\r
633 \cite{STUN}, so that nodes can detect whether they are NATted and
\r
634 take appropriate steps to circumvent it.
\r
636 In addition, we have allowed peers to store values in the DHT, even
\r
637 if the hash they are using is not the correct length. Most of the
\r
638 keys used in the DHT are based on the SHA1 hash, and so they are 20
\r
639 bytes in length. However, some files in the targetted Debian package
\r
640 system are only hashed using the MD5 algorithm, and so the hashes
\r
641 retrieved from the server are 16 bytes in length. The DHT will still
\r
642 store values using these keys by padding the end of them with zeroes
\r
643 to the proper length, as the loss of uniqueness from the 4 less
\r
644 bytes is not an issue. Also, the DHT will happily store hashes that
\r
645 are longer than 20 bytes, such as those from the 32 byte SHA256
\r
646 algorithm, by truncating them to the correct length. Since the
\r
647 requesting peer will have the full length of the hash, this will not
\r
648 affect its attempt to verify the downloaded file.
\r
650 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
652 \section{Performance Evaluation}
\r
655 Our \texttt{apt-p2p} implementation supporting the Debian package
\r
656 distribution system has been available to all Debian users since May
\r
657 3rd, 2008 \cite{apt-p2p-debian}, and will also be available in the
\r
658 next release of Ubuntu \cite{apt-p2p-ubuntu}. We have since created
\r
659 a \emph{walker} that will navigate the DHT and find all the peers
\r
660 currently connected to it. This allows us to analyze many aspects of
\r
661 our implementation.
\r
663 \subsection{Peer Lifetimes}
\r
668 \includegraphics[width=\columnwidth]{AptP2PWalker-peers.eps}
\r
669 \caption{The number of peers found in the system, and how many are
\r
670 behind a firewall or NAT.}
\r
671 \label{walker_peers}
\r
674 We first began analyzing the DHT on June 24th, and continue to this
\r
675 day, giving us 2 months of data so far. Figure~\ref{walker_peers}
\r
676 shows the number of peers we have seen in the DHT during this time.
\r
677 The peer population is very steady, with just over 50 regular users
\r
678 participating in the DHT at any time. We also note that we find 100
\r
679 users who connect regularly (weekly), and we have found 186 unique
\r
680 users in the 2 months of our analysis. We determined which users are
\r
681 behind a firewall or NAT, which is one of the main problems of
\r
682 implementing a peer-to-peer network. These peers will be
\r
683 unresponsive to DHT requests from peers they have not contacted
\r
684 recently, which will cause the peer to wait for a timeout to occur
\r
685 (currently set at 9 seconds) before moving on. They will also be
\r
686 unable to contribute any upload bandwidth to other peers, as all
\r
687 requests for packages from them will also timeout. From
\r
688 Figure~\ref{walker_peers}, we see that approximately half of all
\r
689 peers suffered from this restriction.
\r
693 \includegraphics[width=\columnwidth]{AptP2PDuration-peers.eps}
\r
694 \caption{The CDF of how long an average session will last.}
\r
695 \label{duration_peers}
\r
698 Figure~\ref{duration_peers} shows the cumulative distribution of how
\r
699 long a connection from a peer can be expected to last. Due to our
\r
700 software being installed as a daemon that is started by default
\r
701 every time their computer boots up, peers are expected to stay for a
\r
702 long period in the system. 50\% of connections last longer than 5
\r
703 hours, and 20\% last longer than 10 hours. These connections are
\r
704 much longer than those reported by Saroiu et. al. \cite{saroiu2001}
\r
705 for other P2P systems, which had 50\% of Napster and Gnutella
\r
706 sessions lasting only 1 hour.
\r
710 \includegraphics[width=\columnwidth]{AptP2PDuration-ind_peers.eps}
\r
711 \caption{The CDF of the average time individual peers stay in the
\r
713 \label{duration_ind_peers}
\r
716 We also examined the average time each individual peer spends in the
\r
717 system. Figure~\ref{duration_peers} shows the cumulative
\r
718 distribution of how long each individual peer remains in the system.
\r
719 Here we see that 50\% of peers have average stays in the system
\r
720 longer than 10 hours.
\r
724 \includegraphics[width=\columnwidth]{AptP2PDuration-online_1.eps}
\r
725 \caption{The fraction of peers that, given their current duration in
\r
726 the system, will stay online for another hour.}
\r
727 \label{duration_online_1}
\r
730 Since our DHT is based on Kademlia, which was designed based on the
\r
731 probability that a node will remain up another hour, we also
\r
732 analyzed our system for this parameter.
\r
733 Figure~\ref{duration_online_1} shows the fraction of peers will
\r
734 remain online for another hour, as a function of how long they have
\r
735 been online so far. Maymounkov and Mazieres found that the longer a
\r
736 node has been online, the higher the probability that it will stay
\r
737 online \cite{kademlia}. Our results also show this behavior. In
\r
738 addition, similar to the Gnutella peers, over 90\% of our peers that
\r
739 have been online for 10 hours, will remain online for another hour.
\r
740 Our results also show that, for our system, over 80\% of all peers
\r
741 will remain online another hour, compared with around 50\% for
\r
746 \includegraphics[width=\columnwidth]{AptP2PDuration-online_6.eps}
\r
747 \caption{The fraction of peers that, given their current duration in
\r
748 the system, will stay online for another 6 hours.}
\r
749 \label{duration_online_6}
\r
752 Since our peers are much longer-lived than other P2P systems, we
\r
753 also looked at the fraction of peers that stay online for another 6
\r
754 hours. Figure~\ref{duration_online_6} shows that over 60\% of peers
\r
755 that are online for 10 hours will stay online for another 6.
\r
756 However, we see an interesting decrease in this fraction between 8
\r
757 and 12 hours, which can also be seen in
\r
758 Figure~\ref{duration_online_1}. We believe this to be due to desktop
\r
759 users, who regularly turn off their computers at night.
\r
761 \subsection{Peer Statistics}
\r
764 On July 31st we enhanced our walker to retrieve additional
\r
765 information from each contacted peer. The peers are configured, by
\r
766 default, to publish some statistics on how much they are downloading
\r
767 and uploading, and their measured response times for DHT queries.
\r
768 Our walker can extract this information if the peer is not
\r
769 firewalled or NATted, it has not disabled this functionality, and if
\r
770 it uses the same port for both its DHT (UDP) requests and download
\r
771 (TCP) requests (which is also a configuration parameter).
\r
775 \includegraphics[width=\columnwidth]{AptP2PDownloaded-peers.eps}
\r
776 \caption{The number of peers that were contacted to determine their
\r
777 bandwidth, and the total number of peers in the system.}
\r
781 Figure~\ref{down_peers} shows the total number of peers we have been
\r
782 able to contact since starting to gather this additional
\r
783 information, as well as how many total peers were found. We were
\r
784 only able to contact 30\% of all the peers that connected to the
\r
785 system during this time.
\r
789 \includegraphics[width=\columnwidth]{AptP2PDownloaded-bw.eps}
\r
790 \caption{The bandwidth of data that the contacted peers have
\r
791 downloaded and uploaded.}
\r
795 Figure~\ref{down_bw} shows the amount of data the peers we were able
\r
796 to contact have downloaded. Peers measure their downloads from other
\r
797 peers and mirrors separately, so we are able to get an idea of how
\r
798 much savings our system is generating for the mirrors. We see that
\r
799 the peers are downloading approximately 20\% of their package data
\r
800 from other peers, which is saving the mirrors from supplying that
\r
801 bandwidth. The actual numbers are only a lower bound, since we have
\r
802 only contacted 30\% of the peers in the system, but we can estimate
\r
803 that \texttt{apt-p2p} has already saved the mirrors 15 GB of
\r
804 bandwidth, or 1 GB per day.
\r
806 We also collected the statistics on the measured response time peers
\r
807 were experiencing when sending requests to the DHT. We found that
\r
808 the recursive \texttt{find\_value} query, which is necessary before
\r
809 a download can occur, is taking 17 seconds on average. This
\r
810 indicates that, on average, requests are experiencing almost 2
\r
811 stalls while waiting for the 9 second timeouts to occur on
\r
812 unresponsive peers. This is longer than our target of 10 seconds,
\r
813 although it will only lead to a slight average delay in downloading
\r
814 of 1.7 seconds when the default 10 concurrent downloads are
\r
815 occurring.This increased response time is due to the number of peers
\r
816 that were behind firewalls or NATs, which was much higher than we
\r
817 anticipated. We do have plans to improve this through better
\r
818 informing of users of their NATted status, the use of STUN
\r
819 \cite{STUN} to circumvent the NATs, and by better exclusion of
\r
820 NATted peers from the DHT (which will not prevent them from using
\r
823 We were also concerned that the constant DHT requests and responses,
\r
824 even while not downloading, would overwhelm some peers' network
\r
825 connections. However, we found that peers are using 200 to 300 bytes
\r
826 per second of bandwidth in servicing the DHT. These numbers are
\r
827 small enough to not affect any other network services the peer would
\r
831 \section{Related Work}
\r
834 There have also been preliminary attempts to implement peer-to-peer distributors for
\r
835 software packages. apt-torrent \cite{apttorrent} creates torrents
\r
836 for some of the larger packages available, but it ignores the
\r
837 smaller packages, which are often the most popular. DebTorrent
\r
838 \cite{debtorrent} makes widespread modifications to a traditional
\r
839 BitTorrent client, to try and fix the drawbacks mentioned in section
\r
840 \ref{bittorrent}. However, these changes also require some
\r
841 modifications to the distribution system to support it.
\r
843 Others have also used DHTs to support this type of functionality.
\r
844 Kenosis \cite{kenosis} is a P2P Remote Procedure Call
\r
845 client also based on the Kademlia DHT, but it is meant as a P2P
\r
846 primitive system on which other tools can be built, and so it has no
\r
847 file sharing functionality at all. Many have used a DHT as a drop-in
\r
848 replacement for the tracker in a BitTorrent system
\r
849 \cite{bittorrent-dht, azureus-dht}, but such systems only use the
\r
850 DHT to find peers for the same torrent, so the file sharing uses
\r
851 traditional BitTorrent and so is not ideal for the reasons listed
\r
854 Our solution differs from them in that ...
\r
857 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
859 \section{Conclusion and Future Work}
\r
860 \label{conclusions}
\r
862 We have designed a generally applicable peer-to-peer content
\r
863 distribution model to be used by many of the free software
\r
864 distributors operating today. It makes use of already existing
\r
865 features of most package management systems to create a
\r
866 peer-to-peer distribution that should substantially reduce the costs
\r
867 of hosting the software packages.
\r
869 We have also implemented our design in freely available software to
\r
870 be used in conjuction with Debian-based distribution of Linux
\r
871 software packages. It is currently in use by some users of the
\r
872 Debian project's distribution, and so serves as an example of the
\r
873 possibilities that exist.
\r
875 We feel that our P2P software package distribution model is
\r
876 well-suited to be used by many free software distributors. We hope
\r
877 to convince them to adopt such a model in their distribution, or we
\r
878 may port our existing system to some of the other groups for them to
\r
881 One aspect missing from our model is the removal of old packages
\r
882 from the cache. Since our implementation is still relatively young,
\r
883 we have not had to deal with the problems of a growing cache of
\r
884 obsolete packages consuming all of a user's hard drive. We plan to
\r
885 implement some form of least recently used (LRU) cache removal
\r
886 technique, in which packages that are no longer available on the
\r
887 server, no longer requested by peers, or simply are the oldest in
\r
888 the cache, will be removed.
\r
890 The most significant area of improvement still needed in our sample
\r
891 implementation is to further speed up some of the slower recursive
\r
892 DHT requests. We hope to accomplish this by further tuning the
\r
893 parameters of our current system, better exclusion of NATted peers
\r
894 from the routing tables, and through the use of STUN \cite{STUN} to
\r
895 circumvent the NATs of the 50\% of the peers that have not
\r
896 configured port forwarding.
\r
898 \bibliographystyle{IEEEtran}
\r
899 \bibliography{./IEEEabrv,./all}
\r
projects / quix0rs-apt-p2p.git / blob