% 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. 

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. Also, we give 
a overview of principal research problems for each category and summarize key 
differences between the categories. In this paper, we consider P2P systems in
for different categories 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. The 
structure 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. Specifically, the structure of an application 
level overlay affects directly to the how data lookups are performed in a P2P 
system, i.e., a combination of algorithms which are used for locating a specific 
data item in the overlay.  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 methology. 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}

\cite{harren02complex}

\cite{ratnasamy02routing}

\section{Survey methodology}

-define application level overlay
-four categories, starting from level 0 and ending to level 3
-category 0: ad hoc and unstructured, overlay is a random graph 
-category 1: there is a slight form of deternism in they overlay
-category 2: there is a slight form of deternism in they overlay
-category 3: the construction and the maintenance of the overlay is highly 
             deterministic
-measure of determinism in the overlay topology
-By structure
-by 


\subsection{0-Category (Gnutella)}
<directly from thesis, to be changed>

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.  

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 turn 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 TL 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. 

</directly from thesis, to be changed>
\subsection{1-category (superpeers)}
<directly from thesis, to be changed>

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.

</directly from thesis, to be changed>
\subsection{2-category (clusters / smallworld)}


-"social networks" a.k.a. small world networks
-overlay construction short/long range links
-common interest, physical locations, document's content
-Symphony
-SETS
-SWAP


\subsection{3-category (DHTs)}
<directly from thesis, to be changed>

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,

</directly from thesis, to be changed>
\section{Summary}

-list key differences and properties in table

<directly from thesis, to be changed>

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.

</directly from thesis, to be changed>
\section{Discussion}

-future directions: work by Manku, i.e., interconnection networks (ICNs).
-outline research challanges
-security and trust (concerns all categories)
DHT Design: A Modular Approach
ID Selection for Distributed Hash Tables
Common API
Abstractions (DHT/DOLR)

\section{Conclusions}
<directly from thesis, to be changed>

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.  
</directly from thesis, to be changed>

% 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}

