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