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 a cost-effective
\r
38 vehicle for software development and release, particular in the free software community.
\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 existing peer-to-peer systems for file sharing such 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 developers, and 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 distribution system 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 are effectively utilized and thus significantly reduces the currently
\r
58 large bandwidth requirements of hosting the software, as confirmed by our existing real user statistics over the Internet.
\r
61 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
63 \section{Introduction}
\r
66 With the widespread penetration of broadband access, the Internet has become a cost-effective
\r
67 vehicle for software development and release \cite{feller2000fao}. This is particularly true for the free software
\r
68 community whose developers and users are distributed worldwide and work asynchronously. The ever increasing power of
\r
69 modern programming languages, computer platforms, and operating systems has made this software extremely large and complex,
\r
70 though it is 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 packages over the Internet has become a challenging task \cite{ubuntu-blueprint}.
\r
74 The existing distribution for free software is mostly based on the client/server model, e.g.,
\r
75 the Advanced Package Tool (\texttt{apt}) for Linux \cite{apt}, 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 will scale well with the currently large user bases and can easily explore the resources made available by
\r
83 Unfortunately, this application scenario has many unique characteristics, which
\r
84 make a straightforward adoption of existing peer-to-peer systems for file sharing such 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 developers, and 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 distributions. 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 distribution system 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 are effectively utilized and thus significantly reduces the currently
\r
98 large 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 current 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 system optimization
\r
110 in Section~\ref{custom_dht}. The performance of our implementation is evaluated
\r
111 in Section~\ref{analysis}. We examine some related work in Section~\ref{related}, and then
\r
112 Section~\ref{conclusions} concludes the paper and offers some future directions.
\r
114 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
116 \section{Background and Motivations}
\r
119 In the free software community, there are a large number of groups using the Internet to
\r
120 collaboratively develop and release their software. Efficient and reliable management and distribution
\r
121 of these software packages over the Internet thus has become a critical task. In this section, we offer concrete examples illustrating the
\r
122 unique challenges in this context.
\r
124 \subsection{Free Software Package Distributors}
\r
127 Most Linux distributions use a software package management system
\r
128 that fetches packages to be installed from an archive of packages
\r
129 hosted on a network of mirrors. The Debian project, and other
\r
130 Debian-based distributions such as Ubuntu and Knoppix, use the
\r
131 \texttt{apt} (Advanced Package Tool) program, which downloads Debian
\r
132 packages in the \texttt{.deb} format from one of many HTTP mirrors.
\r
133 The program will first download index files that contain a listing
\r
134 of which packages are available, as well as important information
\r
135 such as their size, location, and a hash of their content. The user
\r
136 can then select which packages to install or upgrade, and
\r
137 \texttt{apt} will download and verify them before installing them.
\r
139 There are also several similar frontends for the RPM-based
\r
140 distributions. Red Hat's Fedora project uses the \texttt{yum}
\r
141 program, SUSE uses \texttt{YAST}, while Mandriva has
\r
142 \texttt{Rpmdrake}, all of which are used to obtain RPMs from
\r
143 mirrors. Other distributions use tarballs (\texttt{.tar.gz} or
\r
144 \texttt{.tar.bz2}) to contain their packages. Gentoo's package
\r
145 manager is called \texttt{portage}, SlackWare Linux uses
\r
146 \texttt{pkgtools}, and FreeBSD has a suite of command-line tools,
\r
147 all of which download these tarballs from web servers.
\r
149 Similar tools have been used for other types of software packages. CPAN
\r
150 distributes packaged software for the PERL
\r
151 programming language, using SOAP RPC requests to find and download
\r
152 files. Cygwin provides many of the
\r
153 standard Unix/Linux tools in a Windows environment, using a
\r
154 package management tool that requests packages from websites. There
\r
155 are two software distribution systems for software that runs on the Macintosh OS, fink and
\r
156 MacPorts, that also retrieve packages in this way.
\r
158 Direct web downloading is also a common way, often coupled with a hash
\r
159 verification file to be downloaded next to the desired
\r
160 file. The hash file usually has the same file name, but with an
\r
161 added extension identifying the hash used (e.g. \texttt{.md5} for
\r
162 the MD5 hash). This type of file downloading and verification is
\r
163 typical of free software hosting facilities that are open to anyone
\r
164 to use, such as SourceForge.
\r
167 Given the free nature of this software, there are often a number of users
\r
168 motivated by altruism to want to help out with the distribution.
\r
169 This is particularly true considering that much of this software is used by
\r
170 groups that are staffed mostly, or sometimes completely, by
\r
171 volunteers. They are thus motivated to contribute their network resources, so as to promote the healthy development
\r
172 of the volunteer community that released the software.
\r
173 We also naturally expect that peer-to-peer distribution can be implemented in
\r
174 this context, which will scale well with the currently large user bases
\r
175 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=0.80\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. Many 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, many later updates are still
\r
220 released for security issues or serious bugs.
\r
224 \includegraphics[width=0.9\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 \cite{microsoft-update}, 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 Though there are a large number of packages and a large number of
\r
241 users, the interest in a particular package, or 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 users.
\r
248 \includegraphics[width=0.80\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 Finally, 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 natural to expect that
\r
267 the new peer-to-peer solution be reasonably responsive at retrieving packages,
\r
268 preferably in a sequential downloading order too.
\r
270 \subsection{Why BitTorrent Does Not 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, since even though peers in the
\r
295 new torrent may share 99\% of the packages in common with peers in the
\r
296 old torrent, they will be unable to communicate.
\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 to download without uploading, incentives to share
\r
311 become a less important issue. Also, the availability of seeders is
\r
312 not critical either, as the servers are already available to serve in
\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 distribution system 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, but with 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.
\r
325 We further assume that the server is always available and has all of the package files.
\r
326 In addition, the cryptographic hash of the packages will be available
\r
327 separately from the package itself, and is usually contained in an
\r
328 \emph{index} file which also contains all the packages' names,
\r
329 locations and sizes.
\r
333 \includegraphics[width=0.9\columnwidth]{model_simple.eps}
\r
334 \caption{The different phases of functionality of our peer-to-peer distribution model.}
\r
338 \subsection{System Overview}
\r
339 Our model for using peer-to-peer to enhance package distribution is shown in
\r
340 Figure~\ref{model}. As shown in Phase~1, our program will act as a
\r
341 proxy (1,2), downloading (3) and caching all files communicated
\r
342 between the user and the server (4). It will therefore also have
\r
343 available the index files containing the cryptographic hashes all
\r
344 packages. Later, in Phase~2, upon receiving a request from the user
\r
345 to download a package (5), our program will search the index files
\r
346 for the package being requested and find its hash (6). This hash can
\r
347 then be looked up recursively in an indexing structure (a Distributed Hash Table, or DHT \cite{kademlia}, in our implementation) (7), which will return a
\r
348 list of peers that have the package already (8). The package can
\r
349 then be downloaded from the peers (11,12), it can be verified using
\r
350 the hash (13), and if valid can be returned to the user (14). The
\r
351 current nodes location is also added to the DHT for that hash (15),
\r
352 as it is now a source for others to download from.
\r
354 In steps (11,12), the fact that this package is also available to download for free
\r
355 from a server is very important to our proposed model. If the package hash
\r
356 can not be found in the DHT, the peer can then fallback to
\r
357 downloading from the original location (i.e. the server).
\r
358 The server thus, with no modification to its
\r
359 functionality, serves as a seed for the packages in the peer-to-peer
\r
360 system. Any packages that have just been updated, or that are very
\r
361 rare, and so do not have any peers available, can always be found on
\r
362 the server. Once the peer has completed the download from the server
\r
363 and verified the package, it can then add itself to the DHT as the
\r
364 first peer for the new package, so that future requests for the package
\r
365 will not need the server.
\r
368 interest in a large number of packages undergoing constant updating
\r
369 is well suited to the functionality provided by a DHT. A DHT requires unique keys to store and retrieve strings
\r
370 of data, for which the cryptographic hashes used by these package
\r
371 management systems are perfect for. The stored and retrieved strings
\r
372 can then be pointers to the peers that have the package that hashes
\r
375 Note that, despite downloading the package from untrustworthy peers,
\r
376 the trust of the package is always guaranteed through the use
\r
377 of the cryptographic hashes. Nothing can be downloaded from a peer
\r
378 until the hash is looked up in the DHT, so a hash must first come
\r
379 from a trusted source (i.e. the distributors server). Most distributors use index
\r
380 files that contain hashes for a large number of the packages in
\r
381 their archive, and which are also hashed. After retrieving the
\r
382 index's hash from the server, the index file can be downloaded from
\r
383 peers and verified. Then the program has access to all the hashes of
\r
384 the packages it will be downloading, all of which can be verified
\r
385 with a \emph{chain of trust} that stretches back to the original
\r
386 distributor's server.
\r
388 % \subsection{Implementation Options}
\r
389 % \label{imp_options}
\r
391 % There are several ways to implement the desired peer-to-peer functionality
\r
392 % into the existing package management software. The functionality can
\r
393 % be directly integrated through modifications to the software, though
\r
394 % this could be difficult as the peer-to-peer functionality should be running
\r
395 % at all times. This is needed both for efficient lookups and to
\r
396 % support uploading of already downloaded packages. Unfortunately, the
\r
397 % package management tools typically only run until the download and
\r
398 % install request is complete.
\r
400 % Many of the package management software implementations use HTTP
\r
401 % requests from web servers to download the packages, which makes it
\r
402 % possible to implement the peer-to-peer aspect as an almost standard HTTP
\r
403 % caching proxy. This proxy will run as a daemon in the background,
\r
404 % listening for requests from the package management tool for package
\r
405 % files, as well as serving (uploading) cached package to other peers.
\r
406 % It will get uncached requests first from the peer-to-peer system, or
\r
407 % fall back to the normal HTTP request from a server should it not
\r
408 % be found. For methods that do not use HTTP requests, other types of
\r
409 % proxies may also be possible.
\r
411 \subsection{Peer Downloading Protocol}
\r
412 \label{downloading}
\r
414 Although not necessary, we recommend implementing a download
\r
415 protocol that is similar to the protocol used to fetch packages from
\r
416 the distributor's server. This simplifies the peer-to-peer program, as it
\r
417 can then treat peers and the server almost identically when requesting
\r
418 packages. In fact, the server can be used when there are only a few
\r
419 slow peers available for a file to help speed up the download
\r
422 Downloading a file efficiently from a number of peers is where
\r
423 BitTorrent shines as a peer-to-peer application. Its method of
\r
424 breaking up larger files into pieces, each with its own hash,
\r
425 makes it very easy to parallelize the downloading process and
\r
426 maximize the download speed. For very small packages (i.e. less than
\r
427 the piece size), this parallel downloading is not necessary, or
\r
428 even desirable. However, this method should still be used, in
\r
429 conjunction with the DHT, for the larger packages that are
\r
432 Since the package management system only stores a hash of the entire
\r
433 package, and not of pieces of that package, we will need to be able
\r
434 to store and retrieve these piece hashes using the peer-to-peer protocol. In
\r
435 addition to storing the file download location in the DHT (which
\r
436 would still be used for small files), a peer will store a
\r
437 \emph{torrent string} containing the peer's hashes of the pieces of
\r
438 the larger files (similar to (15) in Phase 3 of Figure~\ref{model}).
\r
439 These piece hashes will be retrieved and compared ahead of time by
\r
440 the downloading peer ((9,10) in Phase 2 of Figure~\ref{model})
\r
441 to determine which peers have the same piece hashes (they all
\r
442 should), and then used during the download to verify the pieces of
\r
443 the downloaded package.
\r
445 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
447 \section{\texttt{apt-p2p}: A Practical Implementation}
\r
448 \label{implementation}
\r
450 We have created a sample implementation that functions as described
\r
451 in section \ref{opportunity}, and is freely available for other
\r
452 distributors to download and modify \cite{apt-p2p}. This software,
\r
453 called \texttt{apt-p2p}, interacts with the popular \texttt{apt} tool. This tool
\r
454 is found in most Debian-based Linux distributions, with related statistics
\r
455 available for analyzing the popularity of the software packages
\r
458 Since all requests from \texttt{apt} are in the form of HTTP downloads from a
\r
459 server, our implementation takes the form of a caching HTTP proxy.
\r
460 Making a standard \texttt{apt} implementation use the proxy is then
\r
461 as simple as prepending the proxy location and port to the front of
\r
462 the mirror name in \texttt{apt}'s configuration file (i.e.
\r
463 ``http://localhost:9977/mirrorname.debian.org/\ldots'').
\r
465 We created a customized DHT based on Khashmir \cite{khashmir}, which
\r
466 is an implementation of Kademlia \cite{kademlia}. Khashmir is also the same DHT
\r
467 implementation used by most of the existing BitTorrent clients to
\r
468 implement trackerless operation. The communication is all handled by
\r
469 UDP messages, and RPC (remote procedure call) requests and responses
\r
470 are all \emph{bencoded} in the same way as BitTorrent's
\r
471 \texttt{.torrent} files.
\r
472 % 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{System Optimization}
\r
495 Another 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{DHT Details}
\r
507 DHTs operate by storing (\emph{key}, \emph{value}) pairs in a
\r
508 distributed fashion such that no node will, on average, store more or have to work harder
\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 the
\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 randomly 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.
\r
520 Nodes support four primitive requests.
\r
521 \texttt{ping} will cause a peer to return nothing, and is only used
\r
522 to determine if a node is still alive. \texttt{store} tells a
\r
523 node to store a value associated with a given key. The most
\r
524 important primitives are \texttt{find\_node} and
\r
525 \texttt{find\_value}, which both function recursively to find nodes
\r
526 close to a key. The queried nodes will return a list of the nodes
\r
527 they know about that are closest to the key, allowing the querying
\r
528 node to quickly traverse the DHT to find the nodes closest to the
\r
529 desired key. The only difference between \texttt{find\_node} and \texttt{find\_value} is that the
\r
530 \texttt{find\_value} query will cause a node to return a value, if
\r
531 it has one for that key, instead of a list of nodes.
\r
533 \subsection{Piece Hash Storage}
\r
536 Hashes of pieces of the larger package files are needed to support
\r
537 their efficient downloading from multiple peers.
\r
538 For large files (5 or more pieces), the torrent strings described in
\r
539 Section~\ref{downloading}
\r
540 are too long to store with the peer's download info in the DHT. This
\r
541 is due to the limitation that a single UDP packet should be less
\r
542 than 1472 bytes to avoid fragmentation.
\r
543 % For example, for a file of 4 pieces, the peer would need to store a
\r
544 % value 120 bytes in size (IP address, port, four 20-byte pieces and
\r
545 % some overhead), which would limit a return value from including more
\r
546 % than 10 values to a request.
\r
548 Instead, the peers will store the torrent string for large files
\r
549 separately in the DHT, and only contain a reference to it in their
\r
550 stored value for the hash of the file. The reference is an SHA1 hash
\r
551 of the entire concatenated length of the torrent string. If the
\r
552 torrent string is short enough to store in the DHT (i.e. less than
\r
553 1472 bytes, or about 70 pieces for the SHA1 hash), then a lookup of
\r
554 that hash in the DHT will return the torrent string. Otherwise, a
\r
555 request to the peer for the hash (using the same method as file
\r
556 downloads, i.e. HTTP), will cause the peer to return the torrent
\r
559 Figure \ref{size_CDF} shows the size of the 22,298 packages
\r
560 available in Debian in January 2008. We can see that most of the
\r
561 packages are quite small, and so most will therefore not require
\r
562 piece hash information to download. We have chosen a piece
\r
563 size of 512 kB, which means that 17,515 (78\%) of the packages will
\r
564 not require this information. There are 3054 packages that will
\r
565 require 2 to 4 pieces, for which the torrent string can be stored
\r
566 directly with the package hash in the DHT. There are 1667 packages
\r
567 that will require a separate lookup in the DHT for the longer
\r
568 torrent string as they require 5 to 70 pieces. Finally, there are
\r
569 only 62 packages that require more than 70 pieces, and so will
\r
570 require a separate request to a peer for the torrent string.
\r
572 \subsection{Response Time Optimization}
\r
573 \label{response_time}
\r
575 Many of our customizations to the DHT have been to try and improve
\r
576 the time of the recursive \texttt{find\_value} requests, as this can
\r
577 cause long delays for the user waiting for a package download to
\r
578 begin. The one problem that slows down such requests is waiting for
\r
579 timeouts to occur before marking the node as failed and moving on.
\r
581 Our first improvement is to retransmit a request multiple times
\r
582 before a timeout occurs, in case the original request or its
\r
583 response was lost by the unreliable UDP protocol. If it does not
\r
584 receive a response, the requesting node will retransmit the request
\r
585 after a short delay. This delay will increase exponentially for
\r
586 later retransmissions, should the request again fail. Our current
\r
587 implementation will retransmit the request after 2 seconds and 6
\r
588 seconds (4 seconds after the first retransmission), and then timeout
\r
591 We have also added some improvements to the recursive
\r
592 \texttt{find\_node} and \texttt{find\_value} queries to speed up the
\r
593 process when nodes fail. If enough nodes have responded to the
\r
594 current query such that there are many new nodes to query that are
\r
595 closer to the desired key, then a stalled request to a node further
\r
596 away will be dropped in favor of a new request to a closer node.
\r
597 This has the effect of leap-frogging unresponsive nodes and
\r
598 focussing attention on the nodes that do respond. We will also
\r
599 prematurely abort a query while there are still oustanding requests,
\r
600 if enough of the closest nodes have responded and there are no
\r
601 closer nodes found. This prevents a far away unresponsive node from
\r
602 making the query's completion wait for it to timeout.
\r
604 Finally, we made all attempts possible to prevent firewalled and
\r
605 NATted nodes from being added to the routing table for future
\r
606 requests. Only a node that has responded to a request from us will
\r
607 be added to the table. If a node has only sent us a request, we
\r
608 attempt to send a \texttt{ping} to the node to determine if it is
\r
609 NATted or not. Unfortunately, due to the delays used by NATs in
\r
610 allowing UDP packets for a short time if one was recently sent by
\r
611 the NATted host, the ping is likely to succeed even if the node is
\r
612 NATted. We therefore also schedule a future ping to the node to make
\r
613 sure it is still reachable after the NATs delay has hopefully
\r
614 elapsed. We also schedule future pings of nodes that fail once to
\r
615 respond to a request, as it takes multiple failures (currently 3)
\r
616 before a node is removed from the routing table.
\r
620 \includegraphics[width=0.80\columnwidth]{apt_p2p_improvements-find_value.eps}
\r
621 \caption{The distribution of average response times PlanetLab nodes
\r
622 experience for \texttt{find\_value} queries. The original DHT
\r
623 implementation results are shown, as well as the successive
\r
624 improvements that we made to reduce the response time.}
\r
625 \label{improvements}
\r
628 To test our changes during development, we ran our customized DHT
\r
629 for several hours after each major change on over 300 PlanetLab nodes
\r
630 \cite{planetlab}. Though the nodes are not expected to be firewalled
\r
631 or NATted, some can be quite overloaded and so consistently fail to
\r
632 respond within a timeout period, similar to NATted peers. The
\r
633 resulting distribution of the nodes' average response times is shown
\r
634 in Figure~\ref{improvements}. Each improvement successfully reduced
\r
635 the response time, for a total reduction of more than 50\%. The
\r
636 final distribution is also narrower, as the improvements make the
\r
637 system more predictable. However, there are still a large number of
\r
638 outliers with higher average response times, which are the
\r
639 overloaded nodes on PlanetLab. This was confirmed by examining the
\r
640 average time it took for a timeout to occur, which should be
\r
641 constant as it is a configuration option, but can be much larger if
\r
642 the node is too overloaded for the program to be able to check for a
\r
643 timeout very often.
\r
645 \subsection{Multiple Values Extension}
\r
646 \label{multiple_values}
\r
648 The original design of Kademlia specified that each key would have
\r
649 only a single value associated with it. The RPC to find this value
\r
650 was called \texttt{find\_value} and worked similarly to
\r
651 \texttt{find\_node}, iteratively finding nodes with ID's closer to
\r
652 the desired key. However, if a node had a value stored associated
\r
653 with the searched for key, it would respond to the request with that
\r
654 value instead of the list of nodes it knows about that are closer.
\r
656 While this works well for single values, it can cause a problem when
\r
657 there are multiple values. If the responding node is no longer one
\r
658 of the closest to the key being searched for, then the values it is
\r
659 returning will probably be the staler ones in the system, as it
\r
660 will not have the latest stored values. However, the search for
\r
661 closer nodes will stop here, as the queried node only returned
\r
662 values and not a list of nodes to recursively query. We could have
\r
663 the request return both the values and the list of nodes, but that
\r
664 would severely limit the size and number of the values that could be
\r
665 returned in a single UDP packet.
\r
667 Instead, we have broken up the original \texttt{find\_value}
\r
668 operation into two parts. The new \texttt{find\_value} request
\r
669 always returns a list of nodes that the node believes are closest to
\r
670 the key, as well as a number indicating the number of values that
\r
671 this node has for the key. Once a querying node has finished its
\r
672 search for nodes and found the closest ones to the key, it can issue
\r
673 \texttt{get\_value} requests to some nodes to actually retrieve the
\r
674 values they have. This allows for much more control of when and how
\r
675 many nodes to query for values. For example, a querying node could
\r
676 abort the search once it has found enough values in some nodes, or
\r
677 it could choose to only request values from the nodes that are
\r
678 closest to the key being searched for.
\r
680 % \subsection{\textbf{OPTIONAL}: BitTorrent's Improvements}
\r
681 % \label{bittorrent_dht}
\r
683 % In the several years that some BitTorrent clients have been using a
\r
684 % Kademlia-based DHT for tracker-less operation, the developers have
\r
685 % made many enhancements which we can take advantage of. One of the
\r
686 % most important is a security feature added to stop malicious nodes
\r
687 % from subscribing other nodes as downloaders. When a node issues a
\r
688 % request to another node to store its download info for that key, it
\r
689 % must include a \emph{token} returned by the storing node in a recent
\r
690 % \texttt{find\_node} request. The token is created by hashing the IP
\r
691 % address of the requesting peer with a temporary secret that expires
\r
692 % after several minutes. This prevents the requesting peer from faking
\r
693 % its IP address in the store request, since it must first receive a
\r
694 % response from a \texttt{find\_node} on that IP.
\r
696 % We also made some BitTorrent-inspired changes to the parameters of
\r
697 % the DHT originally specified by the authors of Kademlia. Since, as
\r
698 % we will show later, peers stay online in our system for much longer
\r
699 % periods of time, we reduced Kademlia's \emph{k} value from 20 to 8.
\r
700 % The value is supposed to be large enough such that any given
\r
701 % \emph{k} nodes are unlikely to fail within an hour of each other,
\r
702 % which is very unlikely in our system given the long uptimes of
\r
703 % nodes (see Figure~\ref{duration_online_1} in Section~\ref{analysis}.
\r
704 % We also increased the number of concurrent outstanding
\r
705 % requests allowed from 3 to 6 to speed up the recursive key finding
\r
708 % \subsection{\textbf{OPTIONAL}: Other Changes}
\r
709 % \label{other_changes}
\r
711 % In addition, we have allowed peers to store values in the DHT, even
\r
712 % if the hash they are using is not the correct length. Most of the
\r
713 % keys used in the DHT are based on the SHA1 hash, and so they are 20
\r
714 % bytes in length. However, some files in the targetted Debian package
\r
715 % system are only hashed using the MD5 algorithm, and so the hashes
\r
716 % retrieved from the server are 16 bytes in length. The DHT will still
\r
717 % store values using these keys by padding the end of them with zeroes
\r
718 % to the proper length, as the loss of uniqueness from the 4 less
\r
719 % bytes is not an issue. Also, the DHT will happily store hashes that
\r
720 % are longer than 20 bytes, such as those from the 32 byte SHA256
\r
721 % algorithm, by truncating them to the correct length. Since the
\r
722 % requesting peer will have the full length of the hash, this will not
\r
723 % affect its attempt to verify the downloaded file.
\r
725 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
727 \section{Performance Evaluation}
\r
730 Our \texttt{apt-p2p} implementation supporting the Debian package
\r
731 distribution system has been available to all Debian users since May
\r
732 3rd, 2008 \cite{apt-p2p-debian}, and will also be available in the
\r
733 next release of Ubuntu \cite{apt-p2p-ubuntu}. We have since created
\r
734 a \emph{walker} that will navigate the DHT and find all the peers
\r
735 currently connected to it. This allows us to analyze many aspects of
\r
736 our implementation in the real Internet environment.
\r
738 \subsection{Peer Lifetimes}
\r
743 \includegraphics[width=0.80\columnwidth]{AptP2PWalker-peers.eps}
\r
744 \caption{The number of peers found in the system, and how many are
\r
745 behind a firewall or NAT.}
\r
746 \label{walker_peers}
\r
749 We first began analyzing the DHT on June 24th, and continue to this
\r
750 day, giving us 2 months of data so far. Figure~\ref{walker_peers}
\r
751 shows the number of peers we have seen in the DHT during this time.
\r
752 The peer population is very steady, with just over 50 regular users
\r
753 participating in the DHT at any time. We also note that we find 100
\r
754 users who connect regularly (weekly), and we have found 186 unique
\r
755 users in the 2 months of our analysis.
\r
757 We also determined which users are
\r
758 behind a firewall or NAT, which is one of the main problems of
\r
759 implementing a peer-to-peer network. These peers will be
\r
760 unresponsive to DHT requests from peers they have not contacted
\r
761 recently, which will cause the peer to wait for a timeout to occur
\r
762 (currently 9 seconds) before moving on. They will also be
\r
763 unable to contribute any upload bandwidth to other peers, as all
\r
764 requests for packages from them will also timeout. From
\r
765 Figure~\ref{walker_peers}, we see that approximately half of all
\r
766 peers suffered from this restriction. To address this problem, we added one other new RPC request that nodes can make:
\r
767 \texttt{join}. This request is only sent on first loading the DHT,
\r
768 and is usually only sent to the bootstrap nodes that are listed for
\r
769 the DHT. These bootstrap nodes will respond to the request with the
\r
770 requesting peer's IP and port, so that the peer can determine what
\r
771 its oustide IP address is and whether port translation is being
\r
772 used. In the future, we hope to add functionality similar to STUN
\r
773 \cite{STUN}, so that nodes can detect whether they are NATted and
\r
774 take appropriate steps to circumvent it.
\r
779 \includegraphics[width=0.80\columnwidth]{AptP2PDuration-peers.eps}
\r
780 \caption{The CDF of how long an average session will last.}
\r
781 \label{duration_peers}
\r
784 Figure~\ref{duration_peers} shows the cumulative distribution of how
\r
785 long a connection from a peer can be expected to last. Due to our
\r
786 software being installed as a daemon that is started by default
\r
787 every time their computer boots up, peers are expected to stay for a
\r
788 long period in the system.
\r
789 Indeed, we find that 50\% of connections last longer than 5
\r
790 hours, and 20\% last longer than 10 hours. These connections are
\r
791 much longer than those reported by Saroiu et al. \cite{saroiu2001}
\r
792 for other peer-to-peer systems, which had 50\% of Napster and Gnutella
\r
793 sessions lasting only 1 hour.
\r
797 % \includegraphics[width=0.80\columnwidth]{AptP2PDuration-ind_peers.eps}
\r
798 % \caption{\textbf{OPTIONAL}: The CDF of the average time individual peers stay in the
\r
800 % \label{duration_ind_peers}
\r
803 % \textbf{OPTIONAL}: We also examined the average time each individual peer spends in the
\r
804 % system. Figure~\ref{duration_peers} shows the cumulative
\r
805 % distribution of how long each individual peer remains in the system.
\r
806 % Here we see that 50\% of peers have average stays in the system
\r
807 % longer than 10 hours.
\r
811 \includegraphics[width=0.80\columnwidth]{AptP2PDuration-online_1.eps}
\r
812 \caption{The fraction of peers that, given their current duration in
\r
813 the system, will stay online for another hour.}
\r
814 \label{duration_online_1}
\r
817 Since our DHT is based on Kademlia, which was designed based on the
\r
818 probability that a node will remain up another hour, we also
\r
819 analyzed our system for this parameter.
\r
820 Figure~\ref{duration_online_1} shows the fraction of peers that will
\r
821 remain online for another hour, as a function of how long they have
\r
822 been online so far. Maymounkov and Mazieres found that the longer a
\r
823 node has been online, the higher the probability that it will stay
\r
824 online \cite{kademlia}. Our results also show this behavior. In
\r
825 addition, similar to the Gnutella peers, over 90\% of our peers that
\r
826 have been online for 10 hours, will remain online for another hour.
\r
827 Our results also show that, for our system, over 80\% of all peers
\r
828 will remain online another hour, compared with around 50\% for
\r
833 % \includegraphics[width=0.80\columnwidth]{AptP2PDuration-online_6.eps}
\r
834 % \caption{\textbf{OPTIONAL}: The fraction of peers that, given their current duration in
\r
835 % the system, will stay online for another 6 hours.}
\r
836 % \label{duration_online_6}
\r
839 % \textbf{OPTIONAL}: Since our peers are much longer-lived than other peer-to-peer systems, we
\r
840 % also looked at the fraction of peers that stay online for another 6
\r
841 % hours. Figure~\ref{duration_online_6} shows that over 60\% of peers
\r
842 % that are online for 10 hours will stay online for another 6.
\r
843 % However, we see an interesting decrease in this fraction between 8
\r
844 % and 12 hours, which can also be seen in
\r
845 % Figure~\ref{duration_online_1}. We believe this to be due to desktop
\r
846 % users, who regularly turn off their computers at night.
\r
848 \subsection{Peer Statistics}
\r
851 On July 31st we enhanced our walker to retrieve additional
\r
852 information from each contacted peer. The peers are configured, by
\r
853 default, to publish some statistics on how much they are downloading
\r
854 and uploading, and their measured response times for DHT queries.
\r
855 Our walker can extract this information if the peer is not
\r
856 firewalled or NATted, it has not disabled this functionality, and if
\r
857 it uses the same port for both its DHT (UDP) requests and download
\r
858 (TCP) requests (which is also the default configuration parameter).
\r
862 \includegraphics[width=0.80\columnwidth]{AptP2PDownloaded-peers.eps}
\r
863 \caption{The number of peers that were contacted to determine their
\r
864 bandwidth, and the total number of peers in the system.}
\r
868 Figure~\ref{down_peers} shows the total number of peers we have been
\r
869 able to contact since starting to gather this additional
\r
870 information, as well as how many total peers were found. We were
\r
871 only able to contact 30\% of all the peers that connected to the
\r
872 system during this time.
\r
876 \includegraphics[width=0.80\columnwidth]{AptP2PDownloaded-bw.eps}
\r
877 \caption{The bandwidth of data (total number of bytes) that the contacted peers have
\r
878 downloaded and uploaded.}
\r
882 Figure~\ref{down_bw} shows the amount of data the peers we were able
\r
883 to contact have downloaded. Peers measure their downloads from other
\r
884 peers and mirrors separately, so we are able to get an idea of how
\r
885 much savings our system is generating for the mirrors. We see that
\r
886 the peers are downloading approximately 20\% of their package data
\r
887 from other peers, which is saving the mirrors from supplying that
\r
888 bandwidth. The actual numbers are only a lower bound, since we have
\r
889 only contacted 30\% of the peers in the system, but we can estimate
\r
890 that \texttt{apt-p2p} has already saved the mirrors 15 GB of
\r
891 bandwidth, or 1 GB per day. Considering the current small number of
\r
892 users this savings is quite large, and is expected to grow
\r
893 considerably as more users participate in the P2P system.
\r
895 We also collected the statistics on the measured response time peers
\r
896 were experiencing when sending requests to the DHT. We found that
\r
897 the recursive \texttt{find\_value} query, which is necessary before
\r
898 a download can occur, is taking 17 seconds on average. This
\r
899 indicates that, on average, requests are experiencing almost 2 full
\r
900 stalls while waiting for the 9 second timeouts to occur on
\r
901 unresponsive peers. This time is longer than our target of 10 seconds,
\r
902 although it will only lead to a slight average delay in downloading
\r
903 of 1.7 seconds when the default 10 concurrent downloads are
\r
904 occurring.This increased response time is due to the number of peers
\r
905 that were behind firewalls or NATs, which was much higher than we
\r
906 anticipated. We do have plans to improve this through better
\r
907 informing of users of their NATted status, the use of STUN
\r
908 \cite{STUN} to circumvent the NATs, and by better exclusion of
\r
909 NATted peers from the DHT (which does not prevent them from using
\r
912 We were also concerned that the constant DHT requests and responses,
\r
913 even while not downloading, would overwhelm some peers' network
\r
914 connections. However, we found that peers are using 200 to 300 bytes/sec
\r
915 of bandwidth in servicing the DHT. These numbers are
\r
916 small enough to not affect any other network services the peer would
\r
920 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
922 \section{Related Work}
\r
925 There have been other preliminary attempts to implement peer-to-peer distributors for
\r
926 software packages. apt-torrent \cite{apttorrent} creates torrents
\r
927 for some of the larger packages available, but it ignores the
\r
928 smaller packages, which are often the most popular. DebTorrent
\r
929 \cite{debtorrent} makes widespread modifications to a traditional
\r
930 BitTorrent client, to try and fix the drawbacks mentioned in
\r
931 Section~\ref{bittorrent}. However, these changes also require some
\r
932 modifications to the distribution system to support it. Our system
\r
933 considers all the files available to users to download, and makes
\r
934 use of the existing infrastructure unmodified.
\r
936 % \textbf{OPTIONAL}: Others have also used DHTs to support this type of functionality.
\r
937 % Kenosis \cite{kenosis} is a peer-to-peer Remote Procedure Call
\r
938 % client also based on the Kademlia DHT, but it is meant as a peer-to-peer
\r
939 % primitive system on which other tools can be built, and so it has no
\r
940 % file sharing functionality at all. Many have used a DHT as a drop-in
\r
941 % replacement for the tracker in a BitTorrent system
\r
942 % \cite{bittorrent-dht, azureus-dht}, but such systems only use the
\r
943 % DHT to find peers for the same torrent, so the file sharing uses
\r
944 % traditional BitTorrent and so is not ideal for the reasons listed
\r
945 % in Section~\ref{bittorrent}.
\r
949 There are a number of works dedicated to developing a collaborative
\r
950 content distribution network (CDN) using peer-to-peer techniques.
\r
951 Freedman et al. developed Coral \cite{coral} using a distributed
\r
952 \emph{sloppy} hash table to speed request times. Pierre and van
\r
953 Steen developed Globule \cite{globule} which uses typical DNS and
\r
954 HTTP redirection techniques to serve requests from a network of
\r
955 replica servers, which in turn draw their content from the original
\r
956 location (or a backup). Shah et al. \cite{shah08} analyze an
\r
957 existing software delivery system and use the results to design a
\r
958 peer-to-peer content distribution network that makes use of
\r
959 volunteer servers to help with the load. None of these systems meets
\r
960 our goal of an even distribution of load amongst the users of the
\r
961 system. Not all users of the systems become peers, and so are not
\r
962 able to contribute back to the system after downloading. The
\r
963 volunteers that do contribute as servers are required to contribute
\r
964 larger amounts of bandwidth, both for uploading to others, and in
\r
965 downloading content they are not in need of in order to share them
\r
966 with other users. Our system treats all users equally, requiring all
\r
967 to become peers in the system, sharing the uploading load equally
\r
968 amongst all, but does not require any user to download files they
\r
969 would not otherwise need.
\r
971 The most similar works to ours are by Shah et al. \cite{shah08} and
\r
972 Shark by Annapureddy et al. \cite{shark}.
\r
973 Shah's system, in addition to the drawbacks mentioned above,
\r
974 is not focused on the interactivity of downloads, as
\r
975 half of all requests were required ``to wait between 8 and 15
\r
976 minutes.'' In contrast, lookups in our system take only seconds to
\r
977 complete, and all requests can be completed in under a minute.
\r
978 Shark makes use of Coral's distributed sloppy hash table to speed
\r
979 the lookup time, but their system is more suited to its intended use
\r
980 as a distributed file server. It does not make use of authoritative
\r
981 copies of the original files, allowing instead any users in the
\r
982 system to update files and propagate those changes to others. Our
\r
983 system is well-tailored to the application of disseminating the
\r
984 unchanging software packages from the authoritative sources to all
\r
988 %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
990 \section{Conclusion and Future Work}
\r
991 \label{conclusions}
\r
993 In this paper, we have provided strong evidence that free software package distribution
\r
994 and update exhibit many distinct characteristics, which call for new designs other
\r
995 than the existing peer-to-peer systems for file sharing. To this end, we have
\r
996 present \texttt{apt-p2p}, a novel peer-to-peer distributor that sits between
\r
997 client and server, providing efficient and transparent downloading and updating services
\r
998 for software packages. We have addressed the key design issues in \texttt{apt-p2p}, including DHT customization,
\r
999 response time reduction, and multi-value extension. \texttt{apt-p2p} has been used in conjuction with Debian-based distribution of Linux
\r
1000 software packages and will also be available in the next release of Ubuntu. Existing real user statistics
\r
1001 have suggested that it interacts well with clients and substantially reduces server cost.
\r
1003 There are many future avenues toward improving our implementation. Besides
\r
1004 evaluating its performance in larger scales, we are particularly interest in further speeding up some of the slower recursive
\r
1005 DHT requests. We expect to accomplish this by fine tuning the
\r
1006 parameters of our current system, better exclusion of NATted peers
\r
1007 from the routing tables, and through the use of STUN \cite{STUN} to
\r
1008 circumvent the NATs of the 50\% of the peers that have not
\r
1009 configured port forwarding.
\r
1011 One aspect missing from our model is the removal of old packages
\r
1012 from the cache. Since our implementation is still relatively young,
\r
1013 we have not had to deal with the problems of a growing cache of
\r
1014 obsolete packages consuming all of a user's hard drive. We plan to
\r
1015 implement some form of least recently used (LRU) cache removal
\r
1016 technique, in which packages that are no longer available on the
\r
1017 server, no longer requested by peers, or simply are the oldest in
\r
1018 the cache, will be removed.
\r
1022 \bibliographystyle{IEEEtran}
\r
1023 \bibliography{./IEEEabrv,./all}
\r
projects / quix0rs-apt-p2p.git / blob