From 1b817aa5ea45f80ef6c21152593a9e63d5ae9080 Mon Sep 17 00:00:00 2001 From: Cameron Dale Date: Tue, 26 Aug 2008 16:27:35 -0700 Subject: [PATCH] More work on the paper, including adding a new response time improvement figure. --- docs/paper/all.bib | 55 ++- docs/paper/apt-p2p-paper.kilepr | 10 +- .../paper/apt_p2p_improvements-find_value.eps | 394 ++++++++++++++++++ docs/paper/paper.tex | 107 ++++- 4 files changed, 541 insertions(+), 25 deletions(-) create mode 100644 docs/paper/apt_p2p_improvements-find_value.eps diff --git a/docs/paper/all.bib b/docs/paper/all.bib index 376a0c5..6a34406 100644 --- a/docs/paper/all.bib +++ b/docs/paper/all.bib @@ -239,6 +239,59 @@ %%%%%%% BibSonomy References %%%%%%%%% +@article{globule, + title={{Globule: a collaborative content delivery network}}, + author={Pierre, G. and van Steen, M.}, + journal={IEEE Communications Magazine}, + volume={44}, + number={8}, + pages={127--133}, + year={2006} +} + +@inproceedings{shah08, + title = {A {P2P} Based Architecture for Secure Software Delivery Using Volunteer Assistance}, + author = {P. Shah and J.-F. Pâris and J. Morgan and J. Schettino and C. Venkatraman}, + booktitle = {P2P}, + publisher = {IEEE}, + year = {2008}, + keywords = {apt-p2p } +} + +% P. Shah, J.-F. Pâris, J. Morgan, J. Schettino and C. Venkatraman, +% A P2P Based Architecture for Secure Software Delivery Using Volunteer Assistance, +% Proceedings of the 8th International Conference on Peer-to-Peer Computing 2008 (P2P'08), +% Aachen, Germany, Sept. 2008 + +@inproceedings{coral, + title = {Democratizing Content Publication with {Coral}}, + author = {Michael J. Freedman and Eric Freudenthal and David Mazières}, + booktitle = {NSDI}, + pages = {239-252}, + publisher = {USENIX}, + year = {2004}, + keywords = {apt-p2p } +} + +@inproceedings{shark, + title = {Shark: Scaling File Servers via Cooperative Caching}, + author = {Siddhartha Annapureddy and Michael J. Freedman and David Mazières}, + booktitle = {NSDI}, + publisher = {USENIX}, + year = {2005}, + keywords = {apt-p2p } +} + +@inproceedings{deltacast, + title = {{DeltaCast}: efficient file reconciliation in wireless broadcast systems}, + author = {Julian Chesterfield and Pablo Rodriguez}, + booktitle = {MobiSys}, + pages = {93-106}, + publisher = {ACM}, + year = {2005}, + keywords = {apt-p2p } +} + @techreport{saroiu2001, title={{A measurement study of peer-to-peer file sharing systems}}, author={Saroiu, S. and Gummadi, P.K. and Gribble, S.D. and others}, @@ -251,7 +304,7 @@ @article{kademlia, title = {{Kademlia: A Peer-to-Peer Information System Based on the XOR Metric}}, author = {P. Maymounkov and D. Mazieres}, - journal = {Peer-To-Peer Systems: First International Workshop, IPTPS 2002, Cambridge, MA, USA, March 7-8, 2002}, + journal = {Peer-To-Peer Systems: First International Workshop, IPTPS 2002, Cambridge, MA, USA, March 7-8}, publisher = {Springer}, year = 2002, entrytype = {article}, diff --git a/docs/paper/apt-p2p-paper.kilepr b/docs/paper/apt-p2p-paper.kilepr index 9065c39..06bb960 100644 --- a/docs/paper/apt-p2p-paper.kilepr +++ b/docs/paper/apt-p2p-paper.kilepr @@ -17,11 +17,11 @@ QuickBuild=LaTeX+ViewDVI [item:all.bib] archive=true -column=0 +column=1 encoding=UTF-8 highlight=BibTeX -line=234 -open=false +line=249 +open=true [item:apt-p2p-paper.kilepr] archive=true @@ -33,8 +33,8 @@ open=false [item:paper.tex] archive=true -column=16 +column=19 encoding=UTF-8 highlight=LaTeX -line=35 +line=585 open=true diff --git a/docs/paper/apt_p2p_improvements-find_value.eps b/docs/paper/apt_p2p_improvements-find_value.eps new file mode 100644 index 0000000..487d73c --- /dev/null +++ b/docs/paper/apt_p2p_improvements-find_value.eps @@ -0,0 +1,394 @@ +%!PS-Adobe-2.0 EPSF-1.2 +%%Creator: MATLAB, The Mathworks, Inc. Version 7.6.0.324 (R2008a). Operating System: Linux 2.6.18.8-0.10-default #1 SMP Wed Jun 4 15:46:34 UTC 2008 i686. +%%Title: /cs/grad1/camerond/school/matlab/cache/apt_p2p_improvements-find_value.20080826T161213.eps +%%CreationDate: 08/26/2008 16:12:22 +%%DocumentNeededFonts: Helvetica +%%DocumentProcessColors: Cyan Magenta Yellow Black +%%Extensions: CMYK +%%Pages: 1 +%%BoundingBox: 52 199 548 591 +%%EndComments + +%%BeginProlog +% MathWorks dictionary +/MathWorks 160 dict begin +% definition operators +/bdef {bind def} bind def +/ldef {load def} bind def +/xdef {exch def} bdef +/xstore {exch store} bdef +% operator abbreviations +/c /clip ldef +/cc /concat ldef +/cp /closepath ldef +/gr /grestore ldef +/gs /gsave ldef +/mt /moveto ldef +/np /newpath ldef +/cm /currentmatrix ldef +/sm /setmatrix ldef +/rm /rmoveto ldef +/rl /rlineto ldef +/s {show newpath} bdef +/sc {setcmykcolor} bdef +/sr /setrgbcolor ldef +/sg /setgray ldef +/w /setlinewidth ldef +/j /setlinejoin ldef +/cap /setlinecap ldef +/rc {rectclip} bdef +/rf {rectfill} bdef +% page state control +/pgsv () def +/bpage {/pgsv save def} bdef +/epage {pgsv restore} bdef +/bplot /gsave ldef +/eplot {stroke grestore} bdef +% orientation switch +/portraitMode 0 def /landscapeMode 1 def /rotateMode 2 def +% coordinate system mappings +/dpi2point 0 def +% font control +/FontSize 0 def +/FMS {/FontSize xstore findfont [FontSize 0 0 FontSize neg 0 0] + makefont setfont} bdef +/reencode {exch dup where {pop load} {pop StandardEncoding} ifelse + exch dup 3 1 roll findfont dup length dict begin + { 1 index /FID ne {def}{pop pop} ifelse } forall + /Encoding exch def currentdict end definefont pop} bdef +/isroman {findfont /CharStrings get /Agrave known} bdef +/FMSR {3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse + exch FMS} bdef +/csm {1 dpi2point div -1 dpi2point div scale neg translate + dup landscapeMode eq {pop -90 rotate} + {rotateMode eq {90 rotate} if} ifelse} bdef +% line types: solid, dotted, dashed, dotdash +/SO { [] 0 setdash } bdef +/DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef +/DA { [6 dpi2point mul] 0 setdash } bdef +/DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 + dpi2point mul] 0 setdash } bdef +% macros for lines and objects +/L {lineto stroke} bdef +/MP {3 1 roll moveto 1 sub {rlineto} repeat} bdef +/AP {{rlineto} repeat} bdef +/PDlw -1 def +/W {/PDlw currentlinewidth def setlinewidth} def +/PP {closepath eofill} bdef +/DP {closepath stroke} bdef +/MR {4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto + neg 0 exch rlineto closepath} bdef +/FR {MR stroke} bdef +/PR {MR fill} bdef +/L1i {{currentfile picstr readhexstring pop} image} bdef +/tMatrix matrix def +/MakeOval {newpath tMatrix currentmatrix pop translate scale +0 0 1 0 360 arc tMatrix setmatrix} bdef +/FO {MakeOval stroke} bdef +/PO {MakeOval fill} bdef +/PD {currentlinewidth 2 div 0 360 arc fill + PDlw -1 eq not {PDlw w /PDlw -1 def} if} def +/FA {newpath tMatrix currentmatrix pop translate scale + 0 0 1 5 -2 roll arc tMatrix setmatrix stroke} bdef +/PA {newpath tMatrix currentmatrix pop translate 0 0 moveto scale + 0 0 1 5 -2 roll arc closepath tMatrix setmatrix fill} bdef +/FAn {newpath tMatrix currentmatrix pop translate scale + 0 0 1 5 -2 roll arcn tMatrix setmatrix stroke} bdef +/PAn {newpath tMatrix currentmatrix pop translate 0 0 moveto scale + 0 0 1 5 -2 roll arcn closepath tMatrix setmatrix fill} bdef +/vradius 0 def /hradius 0 def /lry 0 def +/lrx 0 def /uly 0 def /ulx 0 def /rad 0 def +/MRR {/vradius xdef /hradius xdef /lry xdef /lrx xdef /uly xdef + /ulx xdef newpath tMatrix currentmatrix pop ulx hradius add uly + vradius add translate hradius vradius scale 0 0 1 180 270 arc + tMatrix setmatrix lrx hradius sub uly vradius add translate + hradius vradius scale 0 0 1 270 360 arc tMatrix setmatrix + lrx hradius sub lry vradius sub translate hradius vradius scale + 0 0 1 0 90 arc tMatrix setmatrix ulx hradius add lry vradius sub + translate hradius vradius scale 0 0 1 90 180 arc tMatrix setmatrix + closepath} bdef +/FRR {MRR stroke } bdef +/PRR {MRR fill } bdef +/MlrRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lry uly sub 2 div def + newpath tMatrix currentmatrix pop ulx rad add uly rad add translate + rad rad scale 0 0 1 90 270 arc tMatrix setmatrix lrx rad sub lry rad + sub translate rad rad scale 0 0 1 270 90 arc tMatrix setmatrix + closepath} bdef +/FlrRR {MlrRR stroke } bdef +/PlrRR {MlrRR fill } bdef +/MtbRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lrx ulx sub 2 div def + newpath tMatrix currentmatrix pop ulx rad add uly rad add translate + rad rad scale 0 0 1 180 360 arc tMatrix setmatrix lrx rad sub lry rad + sub translate rad rad scale 0 0 1 0 180 arc tMatrix setmatrix + closepath} bdef +/FtbRR {MtbRR stroke } bdef +/PtbRR {MtbRR fill } bdef +/stri 6 array def /dtri 6 array def +/smat 6 array def /dmat 6 array def +/tmat1 6 array def /tmat2 6 array def /dif 3 array def +/asub {/ind2 exch def /ind1 exch def dup dup + ind1 get exch ind2 get sub exch } bdef +/tri_to_matrix { + 2 0 asub 3 1 asub 4 0 asub 5 1 asub + dup 0 get exch 1 get 7 -1 roll astore } bdef +/compute_transform { + dmat dtri tri_to_matrix tmat1 invertmatrix + smat stri tri_to_matrix tmat2 concatmatrix } bdef +/ds {stri astore pop} bdef +/dt {dtri astore pop} bdef +/db {2 copy /cols xdef /rows xdef mul dup 3 mul string + currentfile exch readhexstring pop + dup 0 3 index getinterval /rbmap xdef + dup 2 index dup getinterval /gbmap xdef + 1 index dup 2 mul exch getinterval /bbmap xdef pop pop}bdef +/it {gs np dtri aload pop moveto lineto lineto cp c + cols rows 8 compute_transform + rbmap gbmap bbmap true 3 colorimage gr}bdef +/il {newpath moveto lineto stroke}bdef +currentdict end def +%%EndProlog + +%%BeginSetup +MathWorks begin + +0 cap + +end +%%EndSetup + +%%Page: 1 1 +%%BeginPageSetup +%%PageBoundingBox: 52 199 548 591 +MathWorks begin +bpage +%%EndPageSetup + +%%BeginObject: obj1 +bplot + +/dpi2point 12 def +portraitMode 0216 7344 csm + + 413 247 5958 4708 MR c np +76 dict begin %Colortable dictionary +/c0 { 0.000000 0.000000 0.000000 sr} bdef +/c1 { 1.000000 1.000000 1.000000 sr} bdef +/c2 { 0.900000 0.000000 0.000000 sr} bdef +/c3 { 0.000000 0.820000 0.000000 sr} bdef +/c4 { 0.000000 0.000000 0.800000 sr} bdef +/c5 { 0.910000 0.820000 0.320000 sr} bdef +/c6 { 1.000000 0.260000 0.820000 sr} bdef +/c7 { 0.000000 0.820000 0.820000 sr} bdef +c0 +1 j +1 sg + 0 0 6913 5186 PR +6 w +0 4226 5356 0 0 -4226 899 4615 4 MP +PP +-5356 0 0 4226 5356 0 0 -4226 899 4615 5 MP stroke +4 w +DO +SO +6 w +0 sg + 899 4615 mt 6255 4615 L + 899 389 mt 6255 389 L + 899 4615 mt 899 389 L +6255 4615 mt 6255 389 L + 899 4615 mt 6255 4615 L + 899 4615 mt 899 389 L + 899 4615 mt 899 4561 L + 899 389 mt 899 442 L +%%IncludeResource: font Helvetica +/Helvetica /ISOLatin1Encoding 120 FMSR + + 866 4760 mt +(0) s +1791 4615 mt 1791 4561 L +1791 389 mt 1791 442 L +1758 4760 mt +(5) s +2684 4615 mt 2684 4561 L +2684 389 mt 2684 442 L +2618 4760 mt +(10) s +3577 4615 mt 3577 4561 L +3577 389 mt 3577 442 L +3511 4760 mt +(15) s +4469 4615 mt 4469 4561 L +4469 389 mt 4469 442 L +4403 4760 mt +(20) s +5362 4615 mt 5362 4561 L +5362 389 mt 5362 442 L +5296 4760 mt +(25) s +6255 4615 mt 6255 4561 L +6255 389 mt 6255 442 L +6189 4760 mt +(30) s + 899 4615 mt 952 4615 L +6255 4615 mt 6201 4615 L + 798 4659 mt +(0) s + 899 4192 mt 952 4192 L +6255 4192 mt 6201 4192 L + 631 4236 mt +(0.05) s + 899 3769 mt 952 3769 L +6255 3769 mt 6201 3769 L + 698 3813 mt +(0.1) s + 899 3347 mt 952 3347 L +6255 3347 mt 6201 3347 L + 631 3391 mt +(0.15) s + 899 2924 mt 952 2924 L +6255 2924 mt 6201 2924 L + 698 2968 mt +(0.2) s + 899 2502 mt 952 2502 L +6255 2502 mt 6201 2502 L + 631 2546 mt +(0.25) s + 899 2079 mt 952 2079 L +6255 2079 mt 6201 2079 L + 698 2123 mt +(0.3) s + 899 1656 mt 952 1656 L +6255 1656 mt 6201 1656 L + 631 1700 mt +(0.35) s + 899 1234 mt 952 1234 L +6255 1234 mt 6201 1234 L + 698 1278 mt +(0.4) s + 899 811 mt 952 811 L +6255 811 mt 6201 811 L + 631 855 mt +(0.45) s + 899 389 mt 952 389 L +6255 389 mt 6201 389 L + 698 433 mt +(0.5) s + 899 4615 mt 6255 4615 L + 899 389 mt 6255 389 L + 899 4615 mt 899 389 L +6255 4615 mt 6255 389 L +gs 899 389 5357 4227 MR c np +179 -548 179 69 178 -34 179 102 178 -68 179 -34 178 0 179 34 +178 -34 179 137 178 0 179 0 178 205 179 -171 178 68 179 411 +179 855 178 2156 179 -3593 178 -103 179 0 178 0 179 0 178 0 +179 0 178 0 179 35 178 -35 179 0 1077 4615 30 MP stroke +/c8 { 1.000000 0.000000 0.000000 sr} bdef +c8 +179 -197 179 0 178 0 179 0 178 0 179 0 178 99 179 -99 +178 230 179 -164 178 0 179 33 178 0 179 33 178 32 179 295 +179 0 178 524 179 1868 178 -328 179 -2490 178 -33 179 0 178 0 +179 0 178 0 179 0 178 0 179 0 1077 4615 30 MP stroke +/c9 { 0.000000 1.000000 0.000000 sr} bdef +c9 +179 -235 179 30 178 -30 179 0 178 0 179 30 178 0 179 -30 +178 89 179 0 178 -30 179 -29 178 -30 179 147 178 30 179 -59 +179 352 178 -88 179 558 178 997 179 1585 178 -3492 179 -30 178 0 +179 89 178 -89 179 0 178 59 179 -59 1077 4615 30 MP stroke +/c10 { 1.000000 0.000000 1.000000 sr} bdef +c10 +179 -27 179 0 178 53 179 -26 178 0 179 0 178 -27 179 79 +178 -26 179 -26 178 52 179 -79 178 79 179 -52 178 52 179 -79 +179 79 178 53 179 105 178 315 179 52 178 394 179 184 178 2598 +179 -3517 178 -263 179 0 178 53 179 -53 1077 4615 30 MP stroke +/c11 { 0.000000 0.000000 1.000000 sr} bdef +c11 +179 -264 179 27 178 0 179 0 178 -27 179 27 178 0 179 0 +178 -27 179 0 178 27 179 -27 178 0 179 27 178 26 179 -53 +179 79 178 0 179 79 178 79 179 237 178 -52 179 316 178 500 +179 2975 178 -3923 179 -290 178 0 179 0 1077 4615 30 MP stroke +gr + +c11 +0 sg +2757 4903 mt +(Average Response Time \(sec.\)) s + 549 3260 mt -90 rotate +(Fraction of PlanetLab Nodes) s +90 rotate + 882 4658 mt +( ) s +6239 431 mt +( ) s +1 sg +0 772 1813 0 0 -772 4384 1222 4 MP +PP +-1813 0 0 772 1813 0 0 -772 4384 1222 5 MP stroke +4 w +DO +SO +6 w +0 sg +4384 1222 mt 6197 1222 L +4384 450 mt 6197 450 L +4384 1222 mt 4384 450 L +6197 1222 mt 6197 450 L +4384 1222 mt 6197 1222 L +4384 1222 mt 4384 450 L +4384 1222 mt 6197 1222 L +4384 450 mt 6197 450 L +4384 1222 mt 4384 450 L +6197 1222 mt 6197 450 L +4849 585 mt +(Original Implementation) s +gs 4384 450 1814 773 MR c np +358 0 4455 542 2 MP stroke +gr + +4849 732 mt +(Add Re-transmissions) s +gs 4384 450 1814 773 MR c np +c8 +358 0 4455 689 2 MP stroke +gr + +c8 +0 sg +4849 879 mt +(Leap-frog Unresponsive) s +gs 4384 450 1814 773 MR c np +c9 +358 0 4455 836 2 MP stroke +gr + +c9 +0 sg +4849 1025 mt +(Abort Early) s +gs 4384 450 1814 773 MR c np +c10 +358 0 4455 982 2 MP stroke +gr + +c10 +0 sg +4849 1172 mt +(Re-ping) s +gs 4384 450 1814 773 MR c np +c11 +358 0 4455 1129 2 MP stroke +gr + +c11 + +end %%Color Dict + +eplot +%%EndObject + +epage +end + +showpage + +%%Trailer +%%EOF diff --git a/docs/paper/paper.tex b/docs/paper/paper.tex index 8423d82..afd3bef 100644 --- a/docs/paper/paper.tex +++ b/docs/paper/paper.tex @@ -88,12 +88,12 @@ distribution system. This implementation will be used by a large number of users, and serves as an example for other free software distributors of the opportunity that can be met with such a system. -The rest of this paper is organized as follows. The background and motivation are presented in Section \ref{situation}, together with related works in Section \ref{related}. We propose -our solution in Section \ref{opportunity}. We then detail our sample -implementation for Debian-based distributions in Section -\ref{implementation}, including an in-depth look at our DHT -customizations in Section \ref{custom_dht}. Its performance is evaluated in Section \ref{analysis}. Finally, -Section \ref{conclusions} concludes the paper and offers some future directions. +The rest of this paper is organized as follows. The background and motivation are presented in Section~\ref{situation}, and we analyze BitTorrent's use for this purpose in Section~\ref{bittorrent}. We propose +our solution in Section~\ref{opportunity}. We then detail our sample +implementation for Debian-based distributions in Section~\ref{implementation}, +including an in-depth look at our DHT +customizations in Section~\ref{custom_dht}. Its performance is evaluated in Section~\ref{analysis}. We examine some related work in Section~\ref{related}, and then +Section~\ref{conclusions} concludes the paper and offers some future directions. %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -248,7 +248,7 @@ users. %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Why BitTorrent Doesn't Work Well} -\label{related} +\label{bittorrent} Recently, many distributors make their software available using BitTorrent \cite{COHEN03}, in particular, for the distribution of CD @@ -296,7 +296,7 @@ can serve in that capacity. \section{Peer-to-Peer Assisted Distributor: An Overview} \label{opportunity} -The situation described in section \ref{situation} presents a clear +The situation described in Section~\ref{situation} presents a clear opportunity to use some form of peer-to-peer file-sharing protocol to allow willing users to contribute upload bandwidth. This sparse interest in a large number of packages undergoing constant updating @@ -424,8 +424,8 @@ are all \emph{bencoded} in the same way as BitTorrent's \texttt{.torrent} files. Khashmir uses the high-level Twisted event-driven networking engine \cite{twisted}, so we also use Twisted in our sample implementation for all other networking needs. -More details of this customized DHT can be found below in section -\ref{custom_dht}. +More details of this customized DHT can be found below in +Section~\ref{custom_dht}. Downloading is accomplished by sending simple HTTP requests to the peers identified by lookups in the DHT to have the desired file. @@ -479,7 +479,7 @@ it has one for that key, instead of a list of nodes. Hashes of pieces of the larger package files are needed to support their efficient downloading from multiple peers. For large files (5 or more pieces), the torrent strings described in -section \ref{downloading} +Section~\ref{downloading} are too long to store with the peer's download info in the DHT. This is due to the limitation that a single UDP packet should be less than 1472 bytes to avoid fragmentation. @@ -515,7 +515,7 @@ require a separate request to a peer for the torrent string. \subsection{Response Time} \label{response_time} -Most of our customizations to the DHT have been to try and improve +Many of our customizations to the DHT have been to try and improve the time of the recursive \texttt{find\_value} requests, as this can cause long delays for the user waiting for a package download to begin. The one problem that slows down such requests is waiting for @@ -558,6 +558,33 @@ elapsed. We also schedule future pings of nodes that fail once to respond to a request, as it takes multiple failures (currently 3) before a node is removed from the routing table. +\begin{figure} +\centering +\includegraphics[width=\columnwidth]{apt_p2p_improvements-find_value.eps} +\caption{The distribution of average response times PlanetLab nodes +experience for \texttt{find\_value} queries. The original DHT +implementation results are shown, as well as the successive +improvements that we made to reduce the response time.} +\label{improvements} +\end{figure} + +To test our changes during development, we ran the customized DHT +for several hours after each major change on 300 PlanetLab nodes +\cite{planetlab}. Though the nodes are not expected to be firewalled +or NATted, some can be quite overloaded and so consistently fail to +respond within a timeout period, similar to NATted peers. The +resulting distribution of the nodes' average response times is shown +in Figure~\ref{improvements}. Each improvement successfully reduced +the response time, for a total reduction of more than half. The +final distribution is also narrower, as the improvements make the +system more predictable. However, there are still a large number of +outliers with higher average response times, which are the +overloaded nodes on PlanetLab. This was confirmed by examining the +average time it took for a timeout to occur, which should be +constant as it is a configuration option, but can be much larger if +the node is too overloaded for the program to be able to check for a +timeout very often. + \subsection{Multiple Values} \label{multiple_values} @@ -828,17 +855,21 @@ small enough to not affect any other network services the peer would be running. +%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%% + \section{Related Work} -\label{others} +\label{related} There have also been preliminary attempts to implement peer-to-peer distributors for software packages. apt-torrent \cite{apttorrent} creates torrents for some of the larger packages available, but it ignores the smaller packages, which are often the most popular. DebTorrent \cite{debtorrent} makes widespread modifications to a traditional -BitTorrent client, to try and fix the drawbacks mentioned in section -\ref{bittorrent}. However, these changes also require some -modifications to the distribution system to support it. +BitTorrent client, to try and fix the drawbacks mentioned in +Section~\ref{bittorrent}. However, these changes also require some +modifications to the distribution system to support it. Our system +considers all the files available to users to download, and makes +use of the existing infrastructure unmodified. Others have also used DHTs to support this type of functionality. Kenosis \cite{kenosis} is a P2P Remote Procedure Call @@ -849,9 +880,47 @@ replacement for the tracker in a BitTorrent system \cite{bittorrent-dht, azureus-dht}, but such systems only use the DHT to find peers for the same torrent, so the file sharing uses traditional BitTorrent and so is not ideal for the reasons listed -above. - -Our solution differs from them in that ... +in Section~\ref{bittorrent}. + +% \cite{deltacast} + +There are a number of works dedicated to developing a collaborative +content distribution network (CDN) using peer-to-peer techniques. +Freedman et. al. developed Coral \cite{coral} using a distrbitued +\emph{sloppy} hash table to speed request times. Pierre and van +Steen developed Globule \cite{globule} which uses typical DNS and +HTTP redirection techniques to serve requests from a network of +replica servers, which in turn draw their content from the original +location (or a backup). Shah et. al. \cite{shah08} analyze an +existing software delivery system and use the results to design a +peer-to-peer content distribution network that makes use of +volunteer servers to help with the load. None of these systems meets +our goal of an even distribution of load amongst the users of the +system. Not all users of the systems become peers, and so are not +able to contribute back to the system after downloading. The +volunteers that do contribute as servers are required to contribute +larger amounts of bandwidth, both for uploading to others, and in +downloading content they are not in need of in order to share them +with other users. Our system treats all users equally, requiring all +to become peers in the system, sharing the uploading load equally +amongst all, but doesn't require any user to download files they +would not otherwise need. + +The most similar works to ours are by Shah et. al. \cite{shah08} and +Shark by Annapureddy et. al. \cite{shark}. +Shah's system, in addition to the drawbacks mentioned previously, +is not focused on the interactivity of downloads, as +half of all requests were required ``to wait between 8 and 15 +minutes.'' In contrast, lookups in our system take only seconds to +complete, and all requests can be completed in under a minute. +Shark makes use of Coral's distributed sloppy hash table to speed +the lookup time, but their system is more suited to its intended use +as a distributed file server. It doesn't make use of authoritative +copies of the original files, allowing instead any users in the +system to update files and propagate those changes to others. Our +system is well-tailored to the application of disseminating the +unchanging software packages from the authoritative sources to all +users unchanged. %%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%% -- 2.39.5