% Template article for preprint document class `elsart' % SP 2001/01/05 \documentclass{elsart} % Use the option doublespacing or reviewcopy to obtain double line spacing % \documentclass[doublespacing]{elsart} % if you use PostScript figures in your article % use the graphics package for simple commands % \usepackage{graphics} % or use the graphicx package for more complicated commands % \usepackage{graphicx} % or use the epsfig package if you prefer to use the old commands % \usepackage{epsfig} % The amssymb package provides various useful mathematical symbols \usepackage{amssymb} \begin{document} \begin{frontmatter} % Title, authors and addresses % use the thanksref command within \title, \author or \address for footnotes; % use the corauthref command within \author for corresponding author footnotes; % use the ead command for the email address, % and the form \ead[url] for the home page: % \title{Title\thanksref{label1}} % \thanks[label1]{} % \author{Name\corauthref{cor1}\thanksref{label2}} % \ead[url]{home page} % \thanks[label2]{} % \corauth[cor1]{} % \address{Address\thanksref{label3}} % \thanks[label3]{} \title{P2P networks: Methods and open problems} % use optional labels to link authors explicitly to addresses: % \author[label1,label2]{} % \address[label1]{} % \address[label2]{} \author{Hermanni Hyyti\"al\"a} \ead{hemppah@cc.jyu.fi} \thanks[*]{This work was funded by the Agora Center InBCT project.} \address{Agora Center, University of Jyv\"askyl\"a P.O. Box 35, FIN-40014 Jyv\"askyl\"a Tel.: +358 14 260 1211} \begin{abstract} In this paper we make a survey of existing P2P approaches. We characterize different P2P systems and classify them into four different categories with regard to the level of topology structure. Also, we give a overview of principal problems for each category and summarize key differences between categories. Finally, we outline possible future research directions in the P2P domain. \end{abstract} \begin{keyword} % keywords here, in the form: keyword \sep keyword % PACS codes here, in the form: \PACS code \sep code \PACS \end{keyword} \end{frontmatter} % main text \section{Introduction} Peer-to-Peer (P2P) systems have recently received considerable attention in both academia \cite{projectirisurl} and industry \cite{p2pworkinggroup,jxtaurl}. The lack of centralization in P2P systems means that the participants can form a distributed system \cite{couloris94distributedsystems} without any investment in centralized hardware by sharing their services and by connecting to each other directly. P2P systems can be characterized as distributed systems in which all communication is symmetrical and all participant entities have similar capabilities and responsibilities \cite{oram01harnessingpower}. Schollmeier \cite{schollmeier01p2pdefinition} describes a P2P system as a system of distributed entities that share their own services. Each entity, i.e., \emph{peer}, may contribute services to the overall system. The distributed and ad hoc nature of P2P improves scalability and avoids single points of failure. A P2P system is composed of an \emph{application} level overlay network, i.e., the network operates at the application level and forms a logical network overlay on top of the physical network. P2P systems are ad hoc, i.e., peers join and leave the system constantly. Thus, the dynamic behaviour poses challenges for efficient construction and maintenance of the overlay network. In recent years a high number of P2P systems have been proposed and developed. Altough all systems have the characteristics of a P2P system, there are major differences between the systems. However, not all P2P system are suitable for specific tasks. For instance, Gnutella (see \cite{ripeanu02mappinggnutella} for example) may be suitable for sharing material between your colleagues in a company's network but may not be a good choice for very large scale data sharing. Also, Distributed Hash Tables (DHT) (see \cite{harren02complex} for example) could be an ideal for indexing large amounts of data but may a deficient choice when complex queries are required for searching data in a P2P network. The construction and maintenance of the application level overlay differ among the systems and is the determinant factor for a P2P system with regard to its performance, scalability and fault tolerance properties. Because of the high number of proposed P2P systems, we believe that there is a need for P2P system classification. Classification helps developers and researchers to understand existing and future P2P systems better. We consider P2P systems how deterministically the application level overlay is constructed and maintained: \begin{itemize} \item Category 0: The overlay topology of the overlay has no structure at all \item Category 1: The overlay topology of the overlay has slight structure \item Category 2: The overlay topology of the overlay is structured \item Category 3: The overlay topology of the overlay is highly structured \end{itemize} By structure, we refer to the topology of the overlay network, i.e., how the connections between participating peers are created and maintained. Please notice that this paper does not provide detailed information about algorithms used overlays. More detailed information can be found within references. The following discusses related work. In Chapter 3, we define our categorization methods. Then, we classify P2P systems into four different categories in Chapters 4 with general characterization of each category and listing category specific open problems. Chapter 5 summarizes each category's properties and key differences. In Chapter 6 we discuss briefly problems related to all P2P systems and outline possible future research. We conclude with Chapter 7. \section{Related work} Routing Networks for Distributed Hash Tables, by G S Manku \cite{gavoille01routing} \cite{milojicic02peertopeer} \cite{daswani03openproblems} \section{Survey methodology} -four levels, starting from level 0 and ending to level 3 -level 0: ad hoc and unstructured, overlay is a random graph -level 1: there is a slight form of deternism in they overlay -level 2: there is a slight form of deternism in they overlay -level 3: the construction and the maintenance of the overlay is highly deterministic -measure of determinism in the overlay topology \subsection{0-Level (Gnutella)} the construction and maintenance of the overlay is controlled loosely. The placement of services and the topology of overlay is random. The data lookup model in loosely structured systems is not very efficient because of unstructured properties of the overlay. The data lookup model is a combination of methods which are used for locating data in the overlay. Gnutella \cite{gnutellaurl} is a well-known example of loosely structured overlay system. Gnutella is is a pure P2P network as no peer is more important than any other peer in the network. The construction and maintenance of Gnutella network is extremely ad hoc, since participating peers can form the overlay network based on local knowledge (i.e., a peer has no knowledge of global state of the system). Figure illustrates the overlay network of Gnutella network. The Gnutella network can be considered as a variation of power-law graph \cite{albert-02-statistical}. In power-law graphs only few peers have high number of neighbor connections and the majority of peers have low number of neighbor connections. In Gnutella, each participating peer maintains a local index of its own shared content. Also, each peer has some connections to other peers, i.e., the peer's \emph{neighbors}. Basic Gnutella data lookup works as follows: a peer broadcasts a query request to its neighbors, which in turnmukainen forward the query to their neighbors. The number of messages in the network can grow with $O(n^{2})$ where $n$ is the number of participating peers in the Gnutella network. Figure illustrates why Gnutella's data lookup model has $O(n^{2})$ properties. To limit the amount of network traffic, Gnutella uses Time-To-Live limited (TTL) flooding to distribute queries. Therefore, Gnutella's data lookup algorithm is a Breadth-First-Search (BFS) with depth limit $T$ (e.g., 7), where $T$ is the system-wide maximum TTL of a message in hops. Thus, only peers that are TTL hops away from the query originator will forward the query or respond to the query. In the Gnutella network, search results are fast, because BFS sends queries to every possible neighbor. According to Lv et al. \cite{lv02searchreplication}, Gnutella's way to perform data lookups, known as \emph{flooding}, has the following limitations. First, choosing the appropriate TTL is not easy. If the TTL is too high, the query originator may unnecessarily strain the network. If the TTL is too low, the query originator might not find the desired data even if it is available somewhere in the network. Second, there are many duplicate messages generated by flooding, especially in high connectivity graphs. It is obvious that, with these limitations, flooding creates significant message processing overhead for each data lookup. Even worse, flooding may increase the load on a participating peer to the point where it has to leave the network. \subsection{1-level (superpeers)} Napster\footnote{We decided to include Napster in this section only because it has historical value (see previous section).} \cite{napsterurl} was designed to allow people to share music. It was a hybrid P2P file-sharing system, i.e., the search index was centralized and the distribution of storage and serving of files was distributed. Peers in the Napster network made requests to the central directory server to find other peers hosting desirable content. Since service requests were totally based on a centralized index, Napster didn't scale because of constantly updated central directory, and had a single point of failure. Adamic et al. \cite{adamic99small,adamic02localsearch,adamic01powerlawsearch} have studied different data lookup methods in power-law networks and have found that by instructing peers that forward data lookups to select high degree peers, the performance of data lookup increases significantly. Figure presents an example topology of power-law network with three high degree peers. Some of the most recent loosely structured P2P protocols have adopted this method: Shareaza \cite{shareazaurl} uses the Gnutella2-based flooding protocol \cite{gnutella2url}, Morpheus \cite{morpheusurl} and KaZaa \cite{kazaaurl} use the FastTrack-based flooding protocol \cite{fasttrackurl}. However, it is not clear whether the power-law method is scalable or not, as the majority of the query requests are sent only to the high degree peers while making these peers bear the load of the entire system. The improvements presented above are only partial solutions. More advanced techniques to improve data lookup of loosely structured systems are discussed in Chapter 3. However, techniques presented in Chapter 3 have not been adopted in any loosely structured system. - \subsection{2-level (clusters / smallworld)} -Symphony -SETS -Future work by Manku, i.e., interconnection networks (ICNs). \subsection{3-level (DHTs)} With tightly structured systems, it is feasible to efficiently perform global data lookups in the overlay. By global lookup, we mean that the system is able to find a information from the overlay, if the information exists. While there are significant differences among proposed tightly structured systems, they all share common property: peer identifiers are assigned to participating peers from a large identifier space by the overlay. Globally unique identifiers, known as \emph{keys}, are also assigned to application-specific data items that are selected from the same identifier space. For instance, globally unique keys can be created using a cryptographic content hash function (see SHA-1 \cite{fips-sha-1}) over the contents of a data item. The form of identifier space differs between proposed systems. A geometrical circular form of identifier space (and variants) is most widely used. For instance, Chord \cite{stoica01chord}, Koorde \cite{kaashoek03koorde}, Pastry \cite{rowston01pastry}, SWAN \cite{bonsma02swan}, Tapestry \cite{zhao01tapestry} and Viceroy \cite{malkhi02viceroy} use a circular form of identifier space of $n$-bit integers modulo $2^{n}$. The value of $n$ varies among systems. On the other hand, CAN \cite{ratnasamy01can} uses a $d$-dimensional geometrical torus model to implement the form of identifier space. To store data in a tightly structured overlay, each application-specific unique key (see SHA-1 \cite{fips-sha-1}) is mapped uniformly (e.g., using consistent hashing \cite{258660}) to an existing peer in the overlay. Thus, a tightly structured overlay assigns a subset of all possible keys to every participating peer. We say that a peer is responsible for the keys that are assigned by the overlay. Figure illustrates this process. Also, each peer in the tightly structured overlay maintains a routing table, which consists of identifiers and IP addresses of other peers in the overlay. Entries of the routing table represent peer's neighbors in the overlay network. Currently, all tightly structured overlays provide at least polylogarithmical data lookup operations. However, there are some key differences between the data structures representing the identifier space. For example, Chord \cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and SkipNet \cite{harvey03skipnet2} maintain a distributed data structure that resembles skip lists \cite{78977}. In figure , we present an overview of Chord's data lookup process. On the right side of Chord's lookup process, the same data lookup process is shown as a binary-tree abstraction. It can be seen that, in each step, the distance decreases with a logarithmic efficiency. Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and Tapestry \cite{zhao01tapestry} use balanced k-trees to implement the data structure of the identifier space. Figure shows the process of Kademlia's data lookup. Viceroy \cite{malkhi02viceroy} maintains a butterfly data structure (see \cite{226658}), which requires only a constant number of neighbor peers while providing $O(\log{n})$ data lookup efficiency where $n$ is the number of peers in the system. Koorde \cite{kaashoek03koorde}, a recent modification of Chord, uses de Bruijn graphs \cite{debruijn46graph} to maintain local routing tables. It requires each peer to have only about two links to other peers to provide $O(\log{n})$ performance. Currently, only three higher level abstractions are provided by the tightly structured overlays \cite{zhao03api}. Each of these abstractions represent a storage layer in the overlay, but have semantical differences in the usage of the overlay. First, Distributed Hash Table (DHT) (see e.g., \cite{dabek01widearea}, \cite{rowstron01storage}) implements the same functionality as a regular hash table by storing the mapping between a key and a value: \begin{itemize} \item \texttt{lookup(key)}: perform a data lookup with a given key. \item \texttt{insert(key)}: insert a data item with a given key. \item \texttt{remove(key)}: remove a data item with a given key. \end{itemize} DHT's interface is generic; values can be any size and type (e.g., content hash over a file). In the DHT abstraction the overlay itself stores the data items. Figure shows the DHT abstraction of the tightly structured overlay. Second, Decentralized Object Location (DOLR) (see e.g., \cite{kubiatowicz00oceanstore}, \cite{iyer02squirrel}) is a distributed directory service. DOLR stores pointers to data items throughout the overlay. DOLR's main operations are: \begin{itemize} \item \texttt{publish(key)}: announce availability of a data item. \item \texttt{removePublished(key)}: remove a data item. \item \texttt{sendToObject(key)}: deliver a data item to a nearby peer hosting the replica of data item. \end{itemize} The key difference between the DHT and the DOLR abstraction is that, in the DOLR abstraction, the overlay maintains only pointers to the data. Also, the DOLR abstraction routes overlay messages to the nearest available peer hosting a specific data item. This form of locality is not supported by DHT. DOLR's interface is similar to the DHT's interface, i.e., values can be any size and type. Third, tightly structured overlays can be used for scalable group multicast or anycast operations (CAST) (see e.g., \cite{zhuang01bayeux}). The basic operations include: \begin{itemize} \item \texttt{join(groupIdentifier)}: join group with a given group identifer. \item \texttt{leave(groupIdentifier)}: leave group with a given group identifier. \item \texttt{multicast(message, groupIdentifier)}: multicast a message to a group with a given group identifier. \item \texttt{anycast(message, groupIdentifier)}: anycast a message to a group with a given group identifier. \end{itemize} The DOLR and CAST abstractions both use network proximity techniques to optimize their operations in the overlay. Figure presents the DOLR abstraction. In tightly structured systems, messages are routed across the overlay toward peers, whose peer identifier is gradually ''closer'' to the key's identifier in the identifier space. The distance can be measured by numerical difference between identifiers (see Chord \cite{stoica01chord}), number of same prefix bits between identifiers (see Pastry \cite{rowston01pastry} and Tapestry \cite{zhao01tapestry}) or Bit-Wise Exclusive Or (XOR) (see Kademlia \cite{maymounkov02kademlia}). Chord's \cite{stoica01chord} distance function does have the property of unidirection (for a given point $p_i$ in the identifier space and distance $d$ > 0, there is exactly one point $p_j$ in a way that the distance between $p_i$ and $p_j$ is $d$), but does not have symmetry (the distance from $p_i$ to $p_j$ is same as the distance from $p_j$ to $p_i$). Pastry's \cite{rowston01pastry} distance function supports symmetry, but does not support unidirection. According to Balakrishnan et al. \cite{balakrishanarticle03lookupp2p}, Kademlia's distance function is both unidirectional and symmetric because of the XOR-metric. Moreover, Kademlia's \cite{maymounkov02kademlia} XOR-based metric does not need stabilization (like in Chord \cite{stoica01chord}) and backup links (like in Pastry \cite{rowston01pastry}). However, in all of the above schemes, each hop in the overlay shortens the distance between current peer working with the data lookup and the key that was looked up in the identifier space. Skip Graphs \cite{AspnesS2003} and SWAN \cite{bonsma02swan} employ a identifier space in which queries are routed to keys. In these systems a peer occupies several positions in the identifier space, one for each application-specific key. The opposite action of placing close keys in the custody of a provider peer is removed at the cost of each peer maintaining one ''resource peer'' in the overlay network for each data item it publishes. The provider peer is a peer that has initially published services into the overlay. PeerNet \cite{eriksson03peernet} differs from other tightly structured overlays in that it operates at the \emph{network} layer instead of application layer (see the ISO-OSI reference model \cite{800902}). This property would provide a common interface to all P2P systems using PeerNet. PeerNet makes an explicit distinction between peer identity and address, which is not supported by standard TCP/IP-protocols. PeerNet has the same performance properties as other tightly structured overlays, i.e., $O(\log{n})$ space required for maintaining information about other peers in the system and $O(\log{n})$ data lookup efficiency. Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed four requirements for tightly structured overlays\footnote{The authors use the term 'DHT' in their text, but in this paper it is not meant to be specific as the authors list \emph{general} properties of tightly structured overlays.} that have to be addressed in order to perform efficient data lookups in tightly structured overlays. First, the mapping of keys to peers must be done in a load-balanced way. Second, the overlay must be able to forward a data lookup for a specific key to an appropriate peer. Third, the overlay must support efficient distance function. Finally, the routing tables for each peer must be constructed and maintained adaptively. Additionally, Balakrishnan et al. argue \cite{balakrishnan03semanticfree} that tightly structured systems are suitable for next generation Reference Resolutions Services (RRS)\footnote{ Domain Name System (DNS) \cite{rfc1101} is a widely used RRS system on the Internet.}. They present two requirements about the nature of reference resolution. First, there should be a general-purpose and application-indepedent substratum for reference resolution. Second, the references themselves should be unstructured and semantic-free. In this paper, we define a unstructured reference as one that does not expose the target in any way and a semantic-free reference as a reference that has no directives in the reference itself that would expose how the reference should be processed. -ID Selection for Distributed Hash Tables, by G S Manku, \section{Summary} Even though the loosely structured and the tightly structured approaches are both P2P schemes, they have very little in common. Indeed, the only similarity they share is the fact that no one peer is more important than another within the P2P network. Fault tolerance \emph{may} be an other area in which these approaches have similar properties (e.g., no single point of failure) \cite{milojicic02peertopeer}. The fault tolerance properties of both approaches are currently only initial calculations, or experimented in simulation environments. In practical applications, however, measuring fault tolerance is a much more challenging task and requires additional research to obtain reliable answers. The most important differences between the approaches are in the performance and scalability properties. Generally, tightly structured systems can perform all internal operations in polylogarithmic time, while the performance of loosely structured systems is not always even linear \cite{balakrishanarticle03lookupp2p}. Moreover, loosely structured systems scale to millions of peers, whereas tightly structured systems are able to cope with billions of concurrent peers \cite{osokine02distnetworks}, \cite{kubiatowicz00oceanstore}. However, it is unknown whether or not all proposed algorithms can preserve logarithmic efficiency and scalability properties in real-life applications; several tightly structured systems assume that participating peers are homogeneous, and the rate of join or leave operation is low \cite{gurmeet03symphony,libennowell01observations,rowston03controlloingreliability}. For the end user, the biggest difference between these systems is how data lookups are performed. Loosely structured systems provide a more rich and user friendly way of searching for data than do tightly structured systems, as the former have a support for keyword searches \cite{yang02efficientsearch,lv02searchreplication}. Tightly structured systems support only exact key lookups since each data item is identified by globally unique keys \cite{balakrishanarticle03lookupp2p,harren02complex,ansaryefficientbroadcast03}. Table lists the primary differences between the loosely structured approach and the tightly structured approach. \section{Discussion} -future directions -research challanges -security and trust (concerns all categories) DHT Design: A Modular Approach ID Selection for Distributed Hash Tables Common API \section{Conclusions} In this paper, we have reviewed existing P2P approaches, algorithms and their properties. Our perception is that despite the great number of P2P systems, we are able to classify \emph{all} systems either to loosely or tightly structured systems. % The Appendices part is started with the command \appendix; % appendix sections are then done as normal sections % \appendix % \section{} % \label{} \bibliographystyle{elsart-num} %\bibliographystyle{gradu} \bibliography{progradu} \end{document}