number of users, and serves as an example for other free software\r
distributors of the opportunity that can be met with such a system.\r
\r
-The rest of this paper is organized as follows. The background and motivation are presented in Section \ref{situation}, together with related works in Section \ref{related}. We propose\r
-our solution in Section \ref{opportunity}. We then detail our sample\r
-implementation for Debian-based distributions in Section\r
-\ref{implementation}, including an in-depth look at our DHT\r
-customizations in Section \ref{custom_dht}. Its performance is evaluated in Section \ref{analysis}. Finally, \r
-Section \ref{conclusions} concludes the paper and offers some future directions.\r
+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\r
+our solution in Section~\ref{opportunity}. We then detail our sample\r
+implementation for Debian-based distributions in Section~\ref{implementation},\r
+including an in-depth look at our DHT\r
+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\r
+Section~\ref{conclusions} concludes the paper and offers some future directions.\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
\subsection{Why BitTorrent Doesn't Work Well}\r
-\label{related}\r
+\label{bittorrent}\r
\r
Recently, many distributors make their software available using\r
BitTorrent \cite{COHEN03}, in particular, for the distribution of CD\r
\section{Peer-to-Peer Assisted Distributor: An Overview}\r
\label{opportunity}\r
\r
-The situation described in section \ref{situation} presents a clear\r
+The situation described in Section~\ref{situation} presents a clear\r
opportunity to use some form of peer-to-peer file-sharing protocol\r
to allow willing users to contribute upload bandwidth. This sparse\r
interest in a large number of packages undergoing constant updating\r
\texttt{.torrent} files. Khashmir uses the high-level Twisted\r
event-driven networking engine \cite{twisted}, so we also use\r
Twisted in our sample implementation for all other networking needs.\r
-More details of this customized DHT can be found below in section\r
-\ref{custom_dht}.\r
+More details of this customized DHT can be found below in\r
+Section~\ref{custom_dht}.\r
\r
Downloading is accomplished by sending simple HTTP requests to the\r
peers identified by lookups in the DHT to have the desired file.\r
Hashes of pieces of the larger package files are needed to support\r
their efficient downloading from multiple peers.\r
For large files (5 or more pieces), the torrent strings described in\r
-section \ref{downloading}\r
+Section~\ref{downloading}\r
are too long to store with the peer's download info in the DHT. This\r
is due to the limitation that a single UDP packet should be less\r
than 1472 bytes to avoid fragmentation.\r
\subsection{Response Time}\r
\label{response_time}\r
\r
-Most of our customizations to the DHT have been to try and improve\r
+Many of our customizations to the DHT have been to try and improve\r
the time of the recursive \texttt{find\_value} requests, as this can\r
cause long delays for the user waiting for a package download to\r
begin. The one problem that slows down such requests is waiting for\r
respond to a request, as it takes multiple failures (currently 3)\r
before a node is removed from the routing table.\r
\r
+\begin{figure}\r
+\centering\r
+\includegraphics[width=\columnwidth]{apt_p2p_improvements-find_value.eps}\r
+\caption{The distribution of average response times PlanetLab nodes\r
+experience for \texttt{find\_value} queries. The original DHT\r
+implementation results are shown, as well as the successive\r
+improvements that we made to reduce the response time.}\r
+\label{improvements}\r
+\end{figure}\r
+\r
+To test our changes during development, we ran the customized DHT\r
+for several hours after each major change on 300 PlanetLab nodes\r
+\cite{planetlab}. Though the nodes are not expected to be firewalled\r
+or NATted, some can be quite overloaded and so consistently fail to\r
+respond within a timeout period, similar to NATted peers. The\r
+resulting distribution of the nodes' average response times is shown\r
+in Figure~\ref{improvements}. Each improvement successfully reduced\r
+the response time, for a total reduction of more than half. The\r
+final distribution is also narrower, as the improvements make the\r
+system more predictable. However, there are still a large number of\r
+outliers with higher average response times, which are the\r
+overloaded nodes on PlanetLab. This was confirmed by examining the\r
+average time it took for a timeout to occur, which should be\r
+constant as it is a configuration option, but can be much larger if\r
+the node is too overloaded for the program to be able to check for a\r
+timeout very often.\r
+\r
\subsection{Multiple Values}\r
\label{multiple_values}\r
\r
be running.\r
\r
\r
+%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+\r
\section{Related Work}\r
-\label{others}\r
+\label{related}\r
\r
There have also been preliminary attempts to implement peer-to-peer distributors for\r
software packages. apt-torrent \cite{apttorrent} creates torrents\r
for some of the larger packages available, but it ignores the\r
smaller packages, which are often the most popular. DebTorrent\r
\cite{debtorrent} makes widespread modifications to a traditional\r
-BitTorrent client, to try and fix the drawbacks mentioned in section\r
-\ref{bittorrent}. However, these changes also require some\r
-modifications to the distribution system to support it.\r
+BitTorrent client, to try and fix the drawbacks mentioned in\r
+Section~\ref{bittorrent}. However, these changes also require some\r
+modifications to the distribution system to support it. Our system\r
+considers all the files available to users to download, and makes\r
+use of the existing infrastructure unmodified.\r
\r
Others have also used DHTs to support this type of functionality.\r
Kenosis \cite{kenosis} is a P2P Remote Procedure Call\r
\cite{bittorrent-dht, azureus-dht}, but such systems only use the\r
DHT to find peers for the same torrent, so the file sharing uses\r
traditional BitTorrent and so is not ideal for the reasons listed\r
-above.\r
-\r
-Our solution differs from them in that ...\r
+in Section~\ref{bittorrent}.\r
+\r
+% \cite{deltacast}\r
+\r
+There are a number of works dedicated to developing a collaborative\r
+content distribution network (CDN) using peer-to-peer techniques.\r
+Freedman et. al. developed Coral \cite{coral} using a distrbitued\r
+\emph{sloppy} hash table to speed request times. Pierre and van\r
+Steen developed Globule \cite{globule} which uses typical DNS and\r
+HTTP redirection techniques to serve requests from a network of\r
+replica servers, which in turn draw their content from the original\r
+location (or a backup). Shah et. al. \cite{shah08} analyze an\r
+existing software delivery system and use the results to design a\r
+peer-to-peer content distribution network that makes use of\r
+volunteer servers to help with the load. None of these systems meets\r
+our goal of an even distribution of load amongst the users of the\r
+system. Not all users of the systems become peers, and so are not\r
+able to contribute back to the system after downloading. The\r
+volunteers that do contribute as servers are required to contribute\r
+larger amounts of bandwidth, both for uploading to others, and in\r
+downloading content they are not in need of in order to share them\r
+with other users. Our system treats all users equally, requiring all\r
+to become peers in the system, sharing the uploading load equally\r
+amongst all, but doesn't require any user to download files they\r
+would not otherwise need.\r
+\r
+The most similar works to ours are by Shah et. al. \cite{shah08} and\r
+Shark by Annapureddy et. al. \cite{shark}.\r
+Shah's system, in addition to the drawbacks mentioned previously,\r
+is not focused on the interactivity of downloads, as\r
+half of all requests were required ``to wait between 8 and 15\r
+minutes.'' In contrast, lookups in our system take only seconds to\r
+complete, and all requests can be completed in under a minute.\r
+Shark makes use of Coral's distributed sloppy hash table to speed\r
+the lookup time, but their system is more suited to its intended use\r
+as a distributed file server. It doesn't make use of authoritative\r
+copies of the original files, allowing instead any users in the\r
+system to update files and propagate those changes to others. Our\r
+system is well-tailored to the application of disseminating the\r
+unchanging software packages from the authoritative sources to all\r
+users unchanged.\r
\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%% Section %%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
projects / quix0rs-apt-p2p.git / blobdiff