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 Distribution System for Software Package Releases and Updates}
\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 The Internet has become an cost-effective
\r
38 vehicle for software development and release, particular in the free software society.
\r
39 Given the free nature of these software, there are often a number of users
\r
40 motivated by altruism to help out with the distribution, so as to promote the healthy development
\r
41 of this voluntary society. It is thus naturally expected that peer-to-peer distribution can be implemented,
\r
42 which scale well with large user bases and can easily explore the network resources made available by
\r
45 Unfortunately, this application scenario has many unique characteristics, which
\r
46 make a straightforward adoption of such existing peer-to-peer systems for file sharing as BitTorrent suboptimal. In particular,
\r
47 a software release often consists of a large number of packages, which are difficult to be distributed individually, but the archive is
\r
48 too large to be distributed in its entirety. The packages are also being constantly
\r
49 updated by the loosely-managed developed; yet the interest in a particular version of a package can be very
\r
50 limited depending on the computer platforms and operating systems used.
\r
52 In this paper, we propose a novel peer-to-peer assisted distributor design that
\r
53 addresses the above challenges. It enhances the existing distribution systems by providing compatible and yet more efficient downloading and updating services
\r
54 for software packages. Our design leads to \texttt{apt-p2p}, a practical implementation that extends the popular \texttt{apt} distributor. \texttt{apt-p2p} has been used in conjuction with Debian-based distribution of Linux
\r
55 software packages and will also be available in the next release of Ubuntu. We have addressed the key design issues in \texttt{apt-p2p}, including indexing table customization,
\r
56 response time reduction, and multi-value extension. They together ensure
\r
57 that the altruistic users' resources be effectively utilized and thus significantly reduce the currently
\r
58 sheer bandwidth requirements of hosting the software, as confirmed by our existing real user statistics.
\r
61 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
63 \section{Introduction}
\r
66 With the widespread penetration of broadband accesses, the Internet has become an cost-effective
\r
67 vehicle for software development and release. This is particularly true for the free software
\r
68 society whose developers and users are worldwide distributed and work asynchronously. The ever increasing power of
\r
69 modern programming languages, computer platforms, and operating systems has made these software extremely large and complex,
\r
70 which are often divided into a huge number of small packages.
\r
71 Together with their popularity among users,
\r
72 an efficient and reliable management and distribution of these software over the Internet has become a challenging task.
\r
74 The existing distributor for free software are mostly based on the client/server model, e.g.,
\r
75 the Advanced Package Tool (\texttt{apt}) for Linux, which suffers from the well-known bottleneck problem.
\r
76 Given the free nature of these software, there are often a number of users
\r
77 motivated by altruism to help out with the distribution, so as to promote the healthy development
\r
78 of this voluntary society.
\r
79 We thus naturally expect that peer-to-peer distribution can be implemented in
\r
80 this context, which scale well with large user bases and can easily explore the network resources made available by
\r
83 Unfortunately, this application scenario has many unique characteristics, which
\r
84 make a straightforward adoption of such existing peer-to-peer systems for file sharing as BitTorrent suboptimal. In particular,
\r
85 there are too many packages to distribute each individually, but the archive is
\r
86 too large to distribute in its entirety. The packages are also being constantly
\r
87 updated by the loosely-managed developed; yet the interest in a particular version of a package can be very
\r
88 limited. They together make it very difficult to efficiently create and manage torrents/trackers. The random downloading nature of BitTorrent-like systems is also different from the
\r
89 sequential order used in existing software package distributors. This in turn suppresses interaction with users
\r
90 given the difficulty in tracking speed and downloading progress.
\r
92 In this paper, we propose a novel peer-to-peer assisted distributor design that
\r
93 addresses the above challenges. It enhances the existing distribution systems by providing compatible and yet more efficient downloading and updating services
\r
94 for software packages. Our design leads to the development of \texttt{apt-p2p}, a practical implementation based on the Debian \footnote{Debian - The Universal Operating System: {\it http://www.debian.org/}} package
\r
95 distribution system. We have addressed the key design issues in \texttt{apt-p2p}, including indexing table customization,
\r
96 response time reduction, and multi-value extension. They together ensure
\r
97 that the altruistic users' resources be effectively utilized and thus significantly reduce the currently
\r
98 sheer bandwidth requirements of hosting the software.
\r
100 \texttt{apt-p2p} has been used in conjuction with Debian-based distribution of Linux
\r
101 software packages and will also be available in the next release of Ubuntu. We have evaluated our currently deployment to
\r
102 determine how effective it is at meeting our goals, and to see what
\r
103 effect it is having on the Debian package distribution system. In particular, our existing real user statistics
\r
104 have suggested that it responsively interacts with clients and substantially reduces server cost.
\r
106 The rest of this paper is organized as follows. The background and motivation are presented in Section~\ref{situation}, including an analysis of BitTorrent's use for this purpose in Section~\ref{bittorrent}. We propose
\r
107 our solution in Section~\ref{opportunity}. We then detail our sample
\r
108 implementation for Debian-based distributions in Section~\ref{implementation},
\r
109 including an in-depth look at our DHT
\r
110 customizations in Section~\ref{custom_dht}. The performance of our implementation is evaluated in Section~\ref{analysis}. We examine some related work in Section~\ref{related}, and then
\r
111 Section~\ref{conclusions} concludes the paper and offers some future directions.
\r
113 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
115 \section{Background and Motivations}
\r
118 In the free software society, there are a large number of groups using the Internet to
\r
119 collaboratively develop and release their software. The ever increasing power of
\r
120 modern programming languages and operating systems has made this software, like commercial software, extremely large and complex, though it is often
\r
121 distributed in many small units (packages). Together with their popularity among users,
\r
122 an efficient and reliable management and distribution of these packages over the Internet has become a daunting task. In this section, we offer concrete examples illustrating the
\r
123 unique challenges in this context.
\r
125 \subsection{Free Software Package Distributors}
\r
128 Most Linux distributions use a software package management system
\r
129 that fetches packages to be installed from an archive of packages
\r
130 hosted on a network of mirrors. The Debian project, and other
\r
131 Debian-based distributions such as Ubuntu and Knoppix, use the
\r
132 \texttt{apt} (Advanced Package Tool) program, which downloads Debian
\r
133 packages in the \texttt{.deb} format from one of many HTTP mirrors.
\r
134 The program will first download index files that contain a listing
\r
135 of which packages are available, as well as important information
\r
136 such as their size, location, and a hash of their content. The user
\r
137 can then select which packages to install or upgrade, and
\r
138 \texttt{apt} will download and verify them before installing them.
\r
140 There are also several similar frontends for the RPM-based
\r
141 distributions. Red Hat's Fedora project uses the \texttt{yum}
\r
142 program, SUSE uses \texttt{YAST}, while Mandriva has
\r
143 \texttt{Rpmdrake}, all of which are used to obtain RPMs from
\r
144 mirrors. Other distributions use tarballs (\texttt{.tar.gz} or
\r
145 \texttt{.tar.bz2}) to contain their packages. Gentoo's package
\r
146 manager is called \texttt{portage}, SlackWare Linux uses
\r
147 \texttt{pkgtools}, and FreeBSD has a suite of command-line tools,
\r
148 all of which download these tarballs from web servers.
\r
150 Similar tools have been used for other software packages. CPAN
\r
151 distributes software packages for the PERL
\r
152 programming language, using SOAP RPC requests to find and download
\r
153 files. Cygwin provides many of the
\r
154 standard Unix/Linux tools in a Windows environment, using a
\r
155 package management tool that requests packages from websites. There
\r
156 are two software distribution systems for software that runs on the Macintosh OS, fink and
\r
157 MacPorts, that also retrieve packages in this way.
\r
159 Direct web downloading is also a common way, often coupled with a hash
\r
160 verification file to be downloaded next to the desired
\r
161 file. The hash file usually has the same file name, but with an
\r
162 added extension identifying the hash used (e.g. \texttt{.md5} for
\r
163 the MD5 hash). This type of file downloading and verification is
\r
164 typical of free software hosting facilities that are open to anyone
\r
165 to use, such as SourceForge.
\r
168 Given the free nature of this software, there are often a number of users
\r
169 motivated by altruism to want to help out with the distribution.
\r
170 This is particularly true considering that many of this software is used by
\r
171 groups that are staffed mostly, or sometimes completely, by
\r
172 volunteers. They are thus motivated to contribute their network resources, so as to promote the healthy development
\r
173 of the volunteer community that released the software.
\r
174 We also naturally expect that peer-to-peer distribution can be implementation in
\r
175 this context, which scale well with large user bases and can easily explore the network resources made available by
\r
180 \subsection{Unique Characteristics}
\r
183 While it seems straightforward to use an existing peer-to-peer file sharing tool like BitTorrent for
\r
184 free software package distribution, there are indeed a series of new challenges in this unique scenario:
\r
186 \subsubsection{Archive Dimensions}
\r
188 While most of the packages of a software release are very small in
\r
189 size, there are some that are quite large. There are too many
\r
190 packages to distribute each individually, but the archive is also
\r
191 too large to distribute in its entirety. In some archives there are
\r
192 also divisions of the archive into sections, e.g. by the operating system (OS) or computer
\r
193 architecture that the package is intended for.
\r
197 \includegraphics[width=\columnwidth]{apt_p2p_simulation-size_CDF.eps}
\r
198 \caption{The CDF of the size of packages in a Debian system, both
\r
199 for the actual size and adjusted size based on the popularity of
\r
204 For example, Figure~\ref{size_CDF} shows the size of the packages in the
\r
205 current Debian distribution. While 80\% of the packages are less than
\r
206 512~KB, some of the packages are hundreds of megabytes. The entire
\r
207 archive consists of 22,298 packages and is approximately 119,000 MB
\r
208 in size. Most of the packages are to be installed in any computer environment, but there are
\r
209 also OS- or architecture-specific packages.
\r
211 \subsubsection{Package Updates}
\r
213 The software packages being distributed are being constantly
\r
214 updated. These updates could be the result of the software creators
\r
215 releasing a new version with improved functionality,
\r
216 or the distributor updating their packaging of the
\r
217 software to meet new requirements. Even if the distributor
\r
218 periodically makes \emph{stable} releases, which are snapshots of
\r
219 all the packages in the archive at a certain time, updates are still
\r
220 released for security issues or serious bugs.
\r
224 \includegraphics[width=\columnwidth]{size-quarter.eps}
\r
225 \caption{The amount of data in the 119,000 MB Debian archive that is
\r
226 updated each day, broken down by architecture.}
\r
227 \label{update_size}
\r
230 For example, Figure~\ref{update_size} shows the amount of data in
\r
231 the Debian archive that was updated each day over a period of 3
\r
232 months. Every single day, approximately 1.5\% of the 119,000 MB archive is
\r
233 updated with new versions of packages. This frequency is much higher than
\r
234 that of most commercial software, mainly because much of free software is
\r
235 developed in a loosely managed environment of developers working
\r
236 asynchronously on a worldwide scale.
\r
238 \subsubsection{Limited Interest}
\r
240 Finally, though there are a large number of packages and a large number of
\r
241 users, the interest in a particular version of a package can be very
\r
242 limited. Specifically, there are core packages that every user has to download, but most
\r
243 packages would fall in the category of optional or extra, and so are
\r
244 interesting to only a limited number of people.
\r
248 \includegraphics[width=\columnwidth]{apt_p2p_popularity-cdf.eps}
\r
249 \caption{The CDF of the popularity of packages in a Debian system.}
\r
250 \label{popularity_CDF}
\r
253 For example, the Debian distribution tracks the popularity of its
\r
254 packages using popcon \cite{popcon}. Figure~\ref{popularity_CDF}
\r
255 shows the cumulative distribution function of the percentage of all
\r
256 users who install each package. Though some packages are installed
\r
257 by everyone, 80\% of the packages are installed by less than 1\% of
\r
260 \subsubsection{Interactive Users}
\r
262 Given the relatively long time for software package downloading, existing package management systems generally display
\r
263 some kind of indication of speed and completeness for users to
\r
264 monitor. Since previous client-server downloads occurred in a sequential
\r
265 fashion, the package management software also measures the speed
\r
266 based on sequential downloading. To offer comparable user experience, it is naturally to expect that
\r
267 the new peer-to-peer solution be reasonably responsive at retrieving packages,
\r
268 preferably enabling sequential downloading order, too.
\r
270 \subsection{Why BitTorrent Doesn't Work Well}
\r
273 Many distributors make their software available using
\r
274 BitTorrent \cite{COHEN03}, in particular for the distribution of CD
\r
275 images. This straightforward use however can be very ineffective, as it requires the
\r
276 peers to download large numbers of packages that they are not
\r
277 interested in, and prevents them from updating to new packages
\r
278 without downloading another image containing a lot of the same
\r
279 packages they already have.
\r
281 An alternative is to create torrents tracking smaller groups of packages. Unfortunately, we find that this enhancement can be
\r
282 quite difficult given the unique characteristic of free software packages.
\r
283 First, there is no obvious way to divide the packages into torrents.
\r
284 Most of the packages are too small, and there are too many packages
\r
285 in the entire archive to create individual torrents for each one.
\r
286 On the other hand, all the packages together are too large to track
\r
287 efficiently as a single torrent. Hence, some division of the archive's
\r
288 packages into torrents is obviously necessary, but wherever that
\r
289 split occurs it will cause either some duplication of connections,
\r
290 or prevent some peers from connecting to others who do have the same
\r
291 content. In addition, a small number of the packages can be updated every
\r
292 day which would add new files to the torrent, thereby changing its
\r
293 \emph{infohash} identifier and making it a new torrent. This will
\r
294 severely fracture the download population, even though peers in the
\r
295 new torrent may share 99\% of the packages in common with peers in the
\r
298 Other issues also prevent BitTorrent from being a good solution to
\r
299 this problem. In particular, BitTorrent's fixed piece sizes (usually 512 KB) that disregard file
\r
300 boundaries are bigger than many of the packages in the archive. This
\r
301 will waste peers' downloading bandwidth as they will end up
\r
302 downloading parts of other packages just to get the piece that
\r
303 contains the package they do want.
\r
304 Finally, note that BitTorrent downloads files
\r
305 randomly, which does not work well with the interactive package
\r
306 management tools expectation of sequential downloads.
\r
308 On the other hand, there are aspects of BitTorrent that are no
\r
309 longer critical. Specifically, with altruistic peers
\r
310 and all files being available without uploading, incentives to share
\r
311 become a less important issue. Also, the availability of seeds are
\r
312 not critical either, as the mirror sites serve in that capacity
\r
315 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
317 \section{Peer-to-Peer Assisted Distributor: An Overview}
\r
318 \label{opportunity}
\r
320 We now present the design of our peer-to-peer assisted distributor for free software package releases and
\r
321 updates. A key principle in our design is that the new functionalities implemented in our distributor should be transparent to users,
\r
322 thus offering the same experience as using conventional software management systems, despite enhanced efficiency.
\r
323 That said, we assume that the user is still attempting to download packages from a
\r
324 server, but the requests will be proxied by our peer-to-peer program. The server is always available and has all of the package files.
\r
325 In addition, the cryptographic hash of the packages will be available
\r
326 separately from the package itself, and is usually contained in an
\r
327 \emph{index} file which also contains all the packages' names,
\r
328 locations and sizes.
\r
332 \includegraphics[width=\columnwidth]{model_simple.eps}
\r
333 \caption{The different phases of functionality of our peer-to-peer distribution model.}
\r
337 Our model for using peer-to-peer to enhance package distribution is shown in
\r
338 Figure~\ref{model}. As shown in Phase~1, our program will act as a
\r
339 proxy (1,2), downloading (3) and caching all files communicated
\r
340 between the user and the server (4). It will therefore also have
\r
341 available the index files containing the cryptographic hashes all
\r
342 packages. Later, in Phase~2, upon receiving a request from the user
\r
343 to download a package (5), our program will search the index files
\r
344 for the package being requested and find its hash (6). This hash can
\r
345 then be looked up recursively in an indexing structure (a Distributed Hash Table [] in our implementation) (7), which will return a
\r
346 list of peers that have the package already (8). The package can
\r
347 then be downloaded from the peers (11,12), it can be verified using
\r
348 the hash (13), and if valid can be returned to the user (14). The
\r
349 current nodes location is also added to the DHT for that hash (15),
\r
350 as it is now a source for others to download from.
\r
352 In steps (11,12), the fact that this package is also available to download for free
\r
353 from a server is very important to our proposed model. If the package hash
\r
354 can not be found in the DHT, the peer can then fallback to
\r
355 downloading from the original location (i.e. the network of
\r
356 mirrors). The mirrors thus, with no modification to their
\r
357 functionality, serve as seeds for the packages in the peer-to-peer
\r
358 system. Any packages that have just been updated, or that are very
\r
359 rare, and so don't have any peers available, can always be found on
\r
360 the mirror. Once the peer has completed the download from the mirror
\r
361 and verified the package, it can then add itself to the DHT as the
\r
362 first peer for the new package, so that future requests for the package
\r
363 will not need the mirror.
\r
366 interest in a large number of packages undergoing constant updating
\r
367 is well suited to the functionality provided by a Distributed Hash
\r
368 Table (DHT). DHTs require unique keys to store and retrieve strings
\r
369 of data, for which the cryptographic hashes used by these package
\r
370 management systems are perfect for. The stored and retrieved strings
\r
371 can then be pointers to the peers that have the package that hashes
\r
372 to that key. A downloading peer can lookup the package hash in the
\r
373 DHT and, if it is found, download the file from those peers and
\r
374 verify the package with the hash. Once the download is complete, the
\r
375 peer will add its entry to the DHT indicating that it now has the
\r
378 Note that, despite downloading the package from untrustworthy peers,
\r
379 the trust of the package is always guaranteed through the use
\r
380 of the cryptographic hashes. Nothing can be downloaded from a peer
\r
381 until the hash is looked up in the DHT, so a hash must first come
\r
382 from a trusted source (i.e. the distributors server). Most distributors use index
\r
383 files that contain hashes for a large number of the packages in
\r
384 their archive, and which are also hashed. After retrieving the
\r
385 index's hash from the mirror, the index file can be downloaded from
\r
386 peers and verified. Then the program has access to all the hashes of
\r
387 the packages it will be downloading, all of which can be verified
\r
388 with a \emph{chain of trust} that stretches back to the original
\r
389 distributor's server.
\r
391 \subsection{Implementation Options}
\r
392 \label{imp_options}
\r
394 There are several ways to implement the desired peer-to-peer functionality
\r
395 into the existing package management software. The functionality can
\r
396 be directly integrated through modifications to the software, though
\r
397 this could be difficult as the peer-to-peer functionality should be running
\r
398 at all times. This is needed both for efficient lookups and to
\r
399 support uploading of already downloaded packages. Unfortunately, the
\r
400 package management tools typically only run until the download and
\r
401 install request is complete.
\r
403 Many of the package management software implementations use HTTP
\r
404 requests from web servers to download the packages, which makes it
\r
405 possible to implement the peer-to-peer aspect as an almost standard HTTP
\r
406 caching proxy. This proxy will run as a daemon in the background,
\r
407 listening for requests from the package management tool for package
\r
408 files, as well as serving (uploading) cached package to other peers.
\r
409 It will get uncached requests first from the peer-to-peer system, or
\r
410 fall back to the normal HTTP request from a server should it not
\r
411 be found. For methods that don't use HTTP requests, other types of
\r
412 proxies may also be possible.
\r
414 \subsection{Downloading From Peers}
\r
415 \label{downloading}
\r
417 Although not necessary, we recommend implementing a download
\r
418 protocol that is similar to the protocol used to fetch packages from
\r
419 the distributor's servers. This simplifies the peer-to-peer program, as it
\r
420 can then treat peers and mirrors almost identically when requesting
\r
421 packages. In fact, the mirrors can be used when there are only a few
\r
422 slow peers available for a file to help speed up the download
\r
425 Downloading a file efficiently from a number of peers is where
\r
426 BitTorrent shines as a peer-to-peer application. Its method of
\r
427 breaking up larger files into pieces, each with its own hash,
\r
428 makes it very easy to parallelize the downloading process and
\r
429 maximize the download speed. For very small packages (i.e. less than
\r
430 the piece size), this parallel downloading is not necessary, or
\r
431 even desirable. However, this method should still be used, in
\r
432 conjunction with the DHT, for the larger packages that are
\r
435 Since the package management system only stores a hash of the entire
\r
436 package, and not of pieces of that package, we will need to be able
\r
437 to store and retrieve these piece hashes using the peer-to-peer protocol. In
\r
438 addition to storing the file download location in the DHT (which
\r
439 would still be used for small files), a peer will store a
\r
440 \emph{torrent string} containing the peer's hashes of the pieces of
\r
441 the larger files. These piece hashes are compared ahead of time
\r
442 to determine which peers have the same piece hashes (they all
\r
443 should), and then used during the download to verify the pieces of
\r
444 the downloaded package.
\r
446 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
448 \section{\texttt{apt-p2p}: A Practical Implementation}
\r
449 \label{implementation}
\r
451 We have created a sample implementation that functions as described
\r
452 in section \ref{opportunity}, and is freely available for other
\r
453 distributors to download and modify \cite{apt-p2p}. This software,
\r
454 called \texttt{apt-p2p}, interacts with the popular \texttt{apt} tool. This tool
\r
455 is found in most Debian-based Linux distributions, with related statistics
\r
456 available for analyzing the popularity of the software packages
\r
459 Since all requests from \texttt{apt} are in the form of HTTP downloads from a
\r
460 server, our implementation takes the form of a caching HTTP proxy.
\r
461 Making a standard \texttt{apt} implementation use the proxy is then
\r
462 as simple as prepending the proxy location and port to the front of
\r
463 the mirror name in \texttt{apt}'s configuration file (i.e.
\r
464 ``http://localhost:9977/mirrorname.debian.org/\ldots'').
\r
466 We created a customized DHT based on Khashmir \cite{khashmir}, which
\r
467 is an implementation of Kademlia \cite{kademlia}. Khashmir is also the same DHT
\r
468 implementation used by most of the existing BitTorrent clients to
\r
469 implement trackerless operation. The communication is all handled by
\r
470 UDP messages, and RPC (remote procedure call) requests and responses
\r
471 are all \emph{bencoded} in the same way as BitTorrent's
\r
472 \texttt{.torrent} files. Khashmir uses the high-level Twisted
\r
473 event-driven networking engine \cite{twisted}, so we also use
\r
474 Twisted in our sample implementation for all other networking needs.
\r
475 More details of this customized DHT can be found below in
\r
476 Section~\ref{custom_dht}.
\r
478 Downloading is accomplished by sending simple HTTP requests to the
\r
479 peers identified by lookups in the DHT to have the desired file.
\r
480 Requests for a package are made using the package's hash, properly
\r
481 encoded, as the URL to request from the peer. The HTTP server used
\r
482 for the proxy also doubles as the server listening for requests for
\r
483 downloads from other peers. All peers support HTTP/1.1, both in the
\r
484 server and the client, which allows for pipelining of multiple
\r
485 requests to a peer, and the requesting of smaller pieces of a large
\r
486 file using the HTTP Range request header. Like in \texttt{apt},
\r
487 SHA1 hashes are then used to verify downloaded files, including the large
\r
488 index files that contain the hashes of the individual packages.
\r
490 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
492 \section{Customized DHT / System Optimization}
\r
495 A large contribution of our work is in the customization and use of
\r
496 a Distributed Hash Table (DHT). Although our DHT is based on
\r
497 Kademlia, we have made many improvements to it to make it suitable
\r
498 for this application. In addition to a novel storage technique to
\r
499 support piece hashes, we have improved the response time of looking
\r
500 up queries, allowed the storage of multiple values for each key, and
\r
501 incorporated some improvements from BitTorrent's tracker-less DHT
\r
504 \subsection{Kademlia DHT Background}
\r
507 DHT's operate by storing (\emph{key}, \emph{value}) pairs in a
\r
508 distributed fashion such that no node will, on average, store more
\r
509 than any other node. They support two primitive operations:
\r
510 \emph{put}, which takes a key and a value and stores it in the DHT;
\r
511 and \emph{get}, which takes a key and returns a value (or values)
\r
512 that was previously stored with that key. These operations are
\r
513 recursive, as each node does not know about all the other nodes in a
\r
514 DHT, and so must recursively search for the correct node to put to
\r
517 The Kademlia DHT, like most other DHTs, assigns IDs to peers from
\r
518 the same space that is used for keys. The peers with IDs closest to
\r
519 the desired key will then store the values for that key. Lookups are
\r
520 recursive, as nodes are queried in each step that are exponentially
\r
521 closer to the key than in the previous step.
\r
523 Nodes in a Kademlia system support four primitive requests.
\r
524 \texttt{ping} will cause a peer to return nothing, and is only used
\r
525 to determine if a node is still alive, while \texttt{store} tells a
\r
526 node to store a value associated with a given key. The most
\r
527 important primitives are \texttt{find\_node} and
\r
528 \texttt{find\_value}, which both function recursively to find nodes
\r
529 close to a key. The queried nodes will return a list of the nodes
\r
530 they know about that are closest to the key, allowing the querying
\r
531 node to quickly traverse the DHT to find the nodes close to the
\r
532 desired key. The only difference between \texttt{find\_node} and \texttt{find\_value} is that the
\r
533 \texttt{find\_value} query will cause a node to return a value, if
\r
534 it has one for that key, instead of a list of nodes.
\r
536 \subsection{Piece Hash Storage}
\r
539 Hashes of pieces of the larger package files are needed to support
\r
540 their efficient downloading from multiple peers.
\r
541 For large files (5 or more pieces), the torrent strings described in
\r
542 Section~\ref{downloading}
\r
543 are too long to store with the peer's download info in the DHT. This
\r
544 is due to the limitation that a single UDP packet should be less
\r
545 than 1472 bytes to avoid fragmentation.
\r
546 % For example, for a file of 4 pieces, the peer would need to store a
\r
547 % value 120 bytes in size (IP address, port, four 20-byte pieces and
\r
548 % some overhead), which would limit a return value from including more
\r
549 % than 10 values to a request.
\r
551 Instead, the peers will store the torrent string for large files
\r
552 separately in the DHT, and only contain a reference to it in their
\r
553 stored value for the hash of the file. The reference is an SHA1 hash
\r
554 of the entire concatenated length of the torrent string. If the
\r
555 torrent string is short enough to store in the DHT (i.e. less than
\r
556 1472 bytes, or about 70 pieces for the SHA1 hash), then a lookup of
\r
557 that hash in the DHT will return the torrent string. Otherwise, a
\r
558 request to the peer for the hash (using the same method as file
\r
559 downloads, i.e. HTTP), will cause the peer to return the torrent
\r
562 Figure \ref{size_CDF} shows the size of the 22,298 packages
\r
563 available in Debian in January 2008. We can see that most of the
\r
564 packages are quite small, and so most will therefore not require
\r
565 piece hash information to download. We have chosen a piece
\r
566 size of 512 kB, which means that 17,515 (78\%) of the packages will
\r
567 not require this information. There are 3054 packages that will
\r
568 require 2 to 4 pieces, for which the torrent string can be stored
\r
569 directly with the package hash in the DHT. There are 1667 packages
\r
570 that will require a separate lookup in the DHT for the longer
\r
571 torrent string as they require 5 to 70 pieces. Finally, there are
\r
572 only 62 packages that require more than 70 pieces, and so will
\r
573 require a separate request to a peer for the torrent string.
\r
575 \subsection{Response Time Optimization}
\r
576 \label{response_time}
\r
578 Many of our customizations to the DHT have been to try and improve
\r
579 the time of the recursive \texttt{find\_value} requests, as this can
\r
580 cause long delays for the user waiting for a package download to
\r
581 begin. The one problem that slows down such requests is waiting for
\r
582 timeouts to occur before marking the node as failed and moving on.
\r
584 Our first improvement is to retransmit a request multiple times
\r
585 before a timeout occurs, in case the original request or its
\r
586 response was lost by the unreliable UDP protocol. If it does not
\r
587 receive a response, the requesting node will retransmit the request
\r
588 after a short delay. This delay will increase exponentially for
\r
589 later retransmissions, should the request again fail. Our current
\r
590 implementation will retransmit the request after 2 seconds and 6
\r
591 seconds (4 seconds after the first retransmission), and then timeout
\r
594 We have also added some improvements to the recursive
\r
595 \texttt{find\_node} and \texttt{find\_value} queries to speed up the
\r
596 process when nodes fail. If enough nodes have responded to the
\r
597 current query such that there are many new nodes to query that are
\r
598 closer to the desired key, then a stalled request to a node further
\r
599 away will be dropped in favor of a new request to a closer node.
\r
600 This has the effect of leap-frogging unresponsive nodes and
\r
601 focussing attention on the nodes that do respond. We will also
\r
602 prematurely abort a query while there are still oustanding requests,
\r
603 if enough of the closest nodes have responded and there are no
\r
604 closer nodes found. This prevents a far away unresponsive node from
\r
605 making the query's completion wait for it to timeout.
\r
607 Finally, we made all attempts possible to prevent firewalled and
\r
608 NATted nodes from being added to the routing table for future
\r
609 requests. Only a node that has responded to a request from us will
\r
610 be added to the table. If a node has only sent us a request, we
\r
611 attempt to send a \texttt{ping} to the node to determine if it is
\r
612 NATted or not. Unfortunately, due to the delays used by NATs in
\r
613 allowing UDP packets for a short time if one was recently sent by
\r
614 the NATted host, the ping is likely to succeed even if the node is
\r
615 NATted. We therefore also schedule a future ping to the node to make
\r
616 sure it is still reachable after the NATs delay has hopefully
\r
617 elapsed. We also schedule future pings of nodes that fail once to
\r
618 respond to a request, as it takes multiple failures (currently 3)
\r
619 before a node is removed from the routing table.
\r
623 \includegraphics[width=\columnwidth]{apt_p2p_improvements-find_value.eps}
\r
624 \caption{The distribution of average response times PlanetLab nodes
\r
625 experience for \texttt{find\_value} queries. The original DHT
\r
626 implementation results are shown, as well as the successive
\r
627 improvements that we made to reduce the response time.}
\r
628 \label{improvements}
\r
631 To test our changes during development, we ran the customized DHT
\r
632 for several hours after each major change on over 300 PlanetLab nodes
\r
633 \cite{planetlab}. Though the nodes are not expected to be firewalled
\r
634 or NATted, some can be quite overloaded and so consistently fail to
\r
635 respond within a timeout period, similar to NATted peers. The
\r
636 resulting distribution of the nodes' average response times is shown
\r
637 in Figure~\ref{improvements}. Each improvement successfully reduced
\r
638 the response time, for a total reduction of more than half. The
\r
639 final distribution is also narrower, as the improvements make the
\r
640 system more predictable. However, there are still a large number of
\r
641 outliers with higher average response times, which are the
\r
642 overloaded nodes on PlanetLab. This was confirmed by examining the
\r
643 average time it took for a timeout to occur, which should be
\r
644 constant as it is a configuration option, but can be much larger if
\r
645 the node is too overloaded for the program to be able to check for a
\r
646 timeout very often.
\r
648 \subsection{Extension with Multiple Values}
\r
649 \label{multiple_values}
\r
651 The original design of Kademlia specified that each key would have
\r
652 only a single value associated with it. The RPC to find this value
\r
653 was called \texttt{find\_value} and worked similarly to
\r
654 \texttt{find\_node}, iteratively finding nodes with ID's closer to
\r
655 the desired key. However, if a node had a value stored associated
\r
656 with the searched for key, it would respond to the request with that
\r
657 value instead of the list of nodes it knows about that are closer.
\r
659 While this works well for single values, it can cause a problem when
\r
660 there are multiple values. If the responding node is no longer one
\r
661 of the closest to the key being searched for, then the values it is
\r
662 returning will probably be the staler ones in the system, as it
\r
663 will not have the latest stored values. However, the search for
\r
664 closer nodes will stop here, as the queried node only returned
\r
665 values and not a list of nodes to recursively query. We could have
\r
666 the request return both the values and the list of nodes, but that
\r
667 would severely limit the size and number of the values that could be
\r
668 returned in a single UDP packet.
\r
670 Instead, we have broken up the original \texttt{find\_value}
\r
671 operation into two parts. The new \texttt{find\_value} request
\r
672 always returns a list of nodes that the node believes are closest to
\r
673 the key, as well as a number indicating the number of values that
\r
674 this node has for the key. Once a querying node has finished its
\r
675 search for nodes and found the closest ones to the key, it can issue
\r
676 \texttt{get\_value} requests to some nodes to actually retrieve the
\r
677 values they have. This allows for much more control of when and how
\r
678 many nodes to query for values. For example, a querying node could
\r
679 abort the search once it has found enough values in some nodes, or
\r
680 it could choose to only request values from the nodes that are
\r
681 closest to the key being searched for.
\r
685 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
687 \section{Performance Evaluation}
\r
690 Our \texttt{apt-p2p} implementation supporting the Debian package
\r
691 distribution system has been available to all Debian users since May
\r
692 3rd, 2008 \cite{apt-p2p-debian}, and will also be available in the
\r
693 next release of Ubuntu \cite{apt-p2p-ubuntu}. We have since created
\r
694 a \emph{walker} that will navigate the DHT and find all the peers
\r
695 currently connected to it. This allows us to analyze many aspects of
\r
696 our implementation.
\r
698 \subsection{Peer Lifetimes}
\r
703 \includegraphics[width=\columnwidth]{AptP2PWalker-peers.eps}
\r
704 \caption{The number of peers found in the system, and how many are
\r
705 behind a firewall or NAT.}
\r
706 \label{walker_peers}
\r
709 We first began analyzing the DHT on June 24th, and continue to this
\r
710 day, giving us 2 months of data so far. Figure~\ref{walker_peers}
\r
711 shows the number of peers we have seen in the DHT during this time.
\r
712 The peer population is very steady, with just over 50 regular users
\r
713 participating in the DHT at any time. We also note that we find 100
\r
714 users who connect regularly (weekly), and we have found 186 unique
\r
715 users in the 2 months of our analysis.
\r
717 We also determined which users are
\r
718 behind a firewall or NAT, which is one of the main problems of
\r
719 implementing a peer-to-peer network. These peers will be
\r
720 unresponsive to DHT requests from peers they have not contacted
\r
721 recently, which will cause the peer to wait for a timeout to occur
\r
722 (currently 9 seconds) before moving on. They will also be
\r
723 unable to contribute any upload bandwidth to other peers, as all
\r
724 requests for packages from them will also timeout. From
\r
725 Figure~\ref{walker_peers}, we see that approximately half of all
\r
726 peers suffered from this restriction. To address this problem, we added one other new RPC request that nodes can make:
\r
727 \texttt{join}. This request is only sent on first loading the DHT,
\r
728 and is usually only sent to the bootstrap nodes that are listed for
\r
729 the DHT. These bootstrap nodes will respond to the request with the
\r
730 requesting peer's IP and port, so that the peer can determine what
\r
731 its oustide IP address is and whether port translation is being
\r
732 used. In the future, we hope to add functionality similar to STUN
\r
733 \cite{STUN}, so that nodes can detect whether they are NATted and
\r
734 take appropriate steps to circumvent it.
\r
739 \includegraphics[width=\columnwidth]{AptP2PDuration-peers.eps}
\r
740 \caption{The CDF of how long an average session will last.}
\r
741 \label{duration_peers}
\r
744 Figure~\ref{duration_peers} shows the cumulative distribution of how
\r
745 long a connection from a peer can be expected to last. Due to our
\r
746 software being installed as a daemon that is started by default
\r
747 every time their computer boots up, peers are expected to stay for a
\r
748 long period in the system.
\r
749 Indeed, we find that 50\% of connections last longer than 5
\r
750 hours, and 20\% last longer than 10 hours. These connections are
\r
751 much longer than those reported by Saroiu et. al. \cite{saroiu2001}
\r
752 for other peer-to-peer systems, which had 50\% of Napster and Gnutella
\r
753 sessions lasting only 1 hour.
\r
757 \includegraphics[width=\columnwidth]{AptP2PDuration-ind_peers.eps}
\r
758 \caption{\textbf{OPTIONAL}: The CDF of the average time individual peers stay in the
\r
760 \label{duration_ind_peers}
\r
763 \textbf{OPTIONAL}: We also examined the average time each individual peer spends in the
\r
764 system. Figure~\ref{duration_peers} shows the cumulative
\r
765 distribution of how long each individual peer remains in the system.
\r
766 Here we see that 50\% of peers have average stays in the system
\r
767 longer than 10 hours.
\r
771 \includegraphics[width=\columnwidth]{AptP2PDuration-online_1.eps}
\r
772 \caption{The fraction of peers that, given their current duration in
\r
773 the system, will stay online for another hour.}
\r
774 \label{duration_online_1}
\r
777 Since our DHT is based on Kademlia, which was designed based on the
\r
778 probability that a node will remain up another hour, we also
\r
779 analyzed our system for this parameter.
\r
780 Figure~\ref{duration_online_1} shows the fraction of peers that will
\r
781 remain online for another hour, as a function of how long they have
\r
782 been online so far. Maymounkov and Mazieres found that the longer a
\r
783 node has been online, the higher the probability that it will stay
\r
784 online \cite{kademlia}. Our results also show this behavior. In
\r
785 addition, similar to the Gnutella peers, over 90\% of our peers that
\r
786 have been online for 10 hours, will remain online for another hour.
\r
787 Our results also show that, for our system, over 80\% of all peers
\r
788 will remain online another hour, compared with around 50\% for
\r
793 \includegraphics[width=\columnwidth]{AptP2PDuration-online_6.eps}
\r
794 \caption{\textbf{OPTIONAL}: The fraction of peers that, given their current duration in
\r
795 the system, will stay online for another 6 hours.}
\r
796 \label{duration_online_6}
\r
799 \textbf{OPTIONAL}: Since our peers are much longer-lived than other peer-to-peer systems, we
\r
800 also looked at the fraction of peers that stay online for another 6
\r
801 hours. Figure~\ref{duration_online_6} shows that over 60\% of peers
\r
802 that are online for 10 hours will stay online for another 6.
\r
803 However, we see an interesting decrease in this fraction between 8
\r
804 and 12 hours, which can also be seen in
\r
805 Figure~\ref{duration_online_1}. We believe this to be due to desktop
\r
806 users, who regularly turn off their computers at night.
\r
808 \subsection{Peer Statistics}
\r
811 On July 31st we enhanced our walker to retrieve additional
\r
812 information from each contacted peer. The peers are configured, by
\r
813 default, to publish some statistics on how much they are downloading
\r
814 and uploading, and their measured response times for DHT queries.
\r
815 Our walker can extract this information if the peer is not
\r
816 firewalled or NATted, it has not disabled this functionality, and if
\r
817 it uses the same port for both its DHT (UDP) requests and download
\r
818 (TCP) requests (which is also the default configuration parameter).
\r
822 \includegraphics[width=\columnwidth]{AptP2PDownloaded-peers.eps}
\r
823 \caption{The number of peers that were contacted to determine their
\r
824 bandwidth, and the total number of peers in the system.}
\r
828 Figure~\ref{down_peers} shows the total number of peers we have been
\r
829 able to contact since starting to gather this additional
\r
830 information, as well as how many total peers were found. We were
\r
831 only able to contact 30\% of all the peers that connected to the
\r
832 system during this time.
\r
836 \includegraphics[width=\columnwidth]{AptP2PDownloaded-bw.eps}
\r
837 \caption{\textbf{OPTIONAL}: The bandwidth of data that the contacted peers have
\r
838 downloaded and uploaded.}
\r
842 Figure~\ref{down_bw} shows the amount of data the peers we were able
\r
843 to contact have downloaded. Peers measure their downloads from other
\r
844 peers and mirrors separately, so we are able to get an idea of how
\r
845 much savings our system is generating for the mirrors. We see that
\r
846 the peers are downloading approximately 20\% of their package data
\r
847 from other peers, which is saving the mirrors from supplying that
\r
848 bandwidth. The actual numbers are only a lower bound, since we have
\r
849 only contacted 30\% of the peers in the system, but we can estimate
\r
850 that \texttt{apt-p2p} has already saved the mirrors 15 GB of
\r
851 bandwidth, or 1 GB per day.
\r
853 We also collected the statistics on the measured response time peers
\r
854 were experiencing when sending requests to the DHT. We found that
\r
855 the recursive \texttt{find\_value} query, which is necessary before
\r
856 a download can occur, is taking 17 seconds on average. This
\r
857 indicates that, on average, requests are experiencing almost 2
\r
858 stalls while waiting for the 9 second timeouts to occur on
\r
859 unresponsive peers. This is longer than our target of 10 seconds,
\r
860 although it will only lead to a slight average delay in downloading
\r
861 of 1.7 seconds when the default 10 concurrent downloads are
\r
862 occurring.This increased response time is due to the number of peers
\r
863 that were behind firewalls or NATs, which was much higher than we
\r
864 anticipated. We do have plans to improve this through better
\r
865 informing of users of their NATted status, the use of STUN
\r
866 \cite{STUN} to circumvent the NATs, and by better exclusion of
\r
867 NATted peers from the DHT (which does not prevent them from using
\r
870 We were also concerned that the constant DHT requests and responses,
\r
871 even while not downloading, would overwhelm some peers' network
\r
872 connections. However, we found that peers are using 200 to 300 bytes
\r
873 per second of bandwidth in servicing the DHT. These numbers are
\r
874 small enough to not affect any other network services the peer would
\r
878 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
880 \section{Related Work}
\r
883 There have been other preliminary attempts to implement peer-to-peer distributors for
\r
884 software packages. apt-torrent \cite{apttorrent} creates torrents
\r
885 for some of the larger packages available, but it ignores the
\r
886 smaller packages, which are often the most popular. DebTorrent
\r
887 \cite{debtorrent} makes widespread modifications to a traditional
\r
888 BitTorrent client, to try and fix the drawbacks mentioned in
\r
889 Section~\ref{bittorrent}. However, these changes also require some
\r
890 modifications to the distribution system to support it. Our system
\r
891 considers all the files available to users to download, and makes
\r
892 use of the existing infrastructure unmodified.
\r
894 \textbf{OPTIONAL}: Others have also used DHTs to support this type of functionality.
\r
895 Kenosis \cite{kenosis} is a peer-to-peer Remote Procedure Call
\r
896 client also based on the Kademlia DHT, but it is meant as a peer-to-peer
\r
897 primitive system on which other tools can be built, and so it has no
\r
898 file sharing functionality at all. Many have used a DHT as a drop-in
\r
899 replacement for the tracker in a BitTorrent system
\r
900 \cite{bittorrent-dht, azureus-dht}, but such systems only use the
\r
901 DHT to find peers for the same torrent, so the file sharing uses
\r
902 traditional BitTorrent and so is not ideal for the reasons listed
\r
903 in Section~\ref{bittorrent}.
\r
907 There are a number of works dedicated to developing a collaborative
\r
908 content distribution network (CDN) using peer-to-peer techniques.
\r
909 Freedman et. al. developed Coral \cite{coral} using a distributed
\r
910 \emph{sloppy} hash table to speed request times. Pierre and van
\r
911 Steen developed Globule \cite{globule} which uses typical DNS and
\r
912 HTTP redirection techniques to serve requests from a network of
\r
913 replica servers, which in turn draw their content from the original
\r
914 location (or a backup). Shah et. al. \cite{shah08} analyze an
\r
915 existing software delivery system and use the results to design a
\r
916 peer-to-peer content distribution network that makes use of
\r
917 volunteer servers to help with the load. None of these systems meets
\r
918 our goal of an even distribution of load amongst the users of the
\r
919 system. Not all users of the systems become peers, and so are not
\r
920 able to contribute back to the system after downloading. The
\r
921 volunteers that do contribute as servers are required to contribute
\r
922 larger amounts of bandwidth, both for uploading to others, and in
\r
923 downloading content they are not in need of in order to share them
\r
924 with other users. Our system treats all users equally, requiring all
\r
925 to become peers in the system, sharing the uploading load equally
\r
926 amongst all, but doesn't require any user to download files they
\r
927 would not otherwise need.
\r
929 The most similar works to ours are by Shah et. al. \cite{shah08} and
\r
930 Shark by Annapureddy et. al. \cite{shark}.
\r
931 Shah's system, in addition to the drawbacks mentioned above,
\r
932 is not focused on the interactivity of downloads, as
\r
933 half of all requests were required ``to wait between 8 and 15
\r
934 minutes.'' In contrast, lookups in our system take only seconds to
\r
935 complete, and all requests can be completed in under a minute.
\r
936 Shark makes use of Coral's distributed sloppy hash table to speed
\r
937 the lookup time, but their system is more suited to its intended use
\r
938 as a distributed file server. It doesn't make use of authoritative
\r
939 copies of the original files, allowing instead any users in the
\r
940 system to update files and propagate those changes to others. Our
\r
941 system is well-tailored to the application of disseminating the
\r
942 unchanging software packages from the authoritative sources to all
\r
946 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
948 \section{Conclusion and Future Work}
\r
949 \label{conclusions}
\r
951 In this paper, we have provided strong evidence that free software package distribution
\r
952 and update exhibit many distinct characteristics, which call for new designs other
\r
953 than the existing peer-to-peer systems for file sharing. To this end, we have
\r
954 present \texttt{apt-p2p}, a novel peer-to-peer distributor that sits between
\r
955 client and server, providing efficient and transparent downloading and updating services
\r
956 for software packages. We have addressed the key design issues in \texttt{apt-p2p}, including DHT customization,
\r
957 response time reduction, and multi-value extension. \texttt{apt-p2p} has been used in conjuction with Debian-based distribution of Linux
\r
958 software packages and will also be available in the next release of Ubuntu. Existing real user statistics
\r
959 have suggested that it interacts well with clients and substantially reduces server cost.
\r
961 There are many future avenues toward improving our implementation. Besides
\r
962 evaluating its performance in larger scales, we are particularly interest in further speeding up some of the slower recursive
\r
963 DHT requests. We expect to accomplish this by fine tuning the
\r
964 parameters of our current system, better exclusion of NATted peers
\r
965 from the routing tables, and through the use of STUN \cite{STUN} to
\r
966 circumvent the NATs of the 50\% of the peers that have not
\r
967 configured port forwarding.
\r
969 One aspect missing from our model is the removal of old packages
\r
970 from the cache. Since our implementation is still relatively young,
\r
971 we have not had to deal with the problems of a growing cache of
\r
972 obsolete packages consuming all of a user's hard drive. We plan to
\r
973 implement some form of least recently used (LRU) cache removal
\r
974 technique, in which packages that are no longer available on the
\r
975 server, no longer requested by peers, or simply are the oldest in
\r
976 the cache, will be removed.
\r
980 \bibliographystyle{IEEEtran}
\r
981 \bibliography{./IEEEabrv,./all}
\r
projects / quix0rs-apt-p2p.git / blob