Peer-to-Peer Systems and Applications

The term “Peer-to-Peer” has drawn much attention in the last few years; particularly for applications providing file-sharing, but distributed computing and Internet-based telephony have also been successfully implemented. Within these applications the Peer-to-Peer concept is mainly used to share files, i.e., the exchange of diverse media data, like music, films, and programs. The growth in the usage of these applications is enormous and even more rapid than that of the World Wide Web. Also, much of the attention focused on early Peer-to-Peer systems concerned copyright issues of shared content.

Currently, a new and highly interesting paradigm for communication on the Internet, known as

Peer-to-Peer (P2P)

, is emerging. Although originally designed exclusively for pragmatic (and legally controversial) file swapping applications, Peer-to-Peer mechanisms can be used to access any kind of distributed resources and may offer new possibilities for Internet-based applications.

Within the last few years, starting with the introduction of Napster in May 1999, the disruptive technology of Peer-to-Peer networking has encountered an enormous growth. Today the traffic caused by Peer-to-Peer networks represents a significant portion in the Internet. For example in the German Research Network (Deutsches Forschungsnetz DFN) Peer-to-Peer causes up to 60 percent of the traffic [210]. Similar trends can be observed in other networks e.g. in the Abilene backbone [42].

The Peer-to-Peer paradigm provides an alternative way of managing resources in various application domains. The primary emphasis of this chapter is placed on presenting an overview of possible approaches for managing the various types of resources, i.e., information, files, bandwidth, storage, and processor cycles, with Peer-to-Peer networks.

Peer-to-Peer (P2P) networks appeared roughly around the year 2000 when a broadband Internet infrastructure (even at the network edge) became widely available. Other than traditional networks Peer-to-Peer networks do not rely on a specific infrastructure offering transport services. Instead they form “overlay structures” focusing on content allocation and distribution based on TCP or HTTP connections. Whereas in a standard Client-Server configuration content is stored and provided only via some central server(s), Peer-to-Peer networks are highly decentralized and locate a desired content at some participating peer and provide the corresponding IP address of that peer to the searching peer. The download of that content is then initiated using a separate connection, often using HTTP. Thus, the high load usually resulting for a central server and its surrounding network is avoided leading to a more even distribution of load on the underlying physical network. On the other hand, such networks are typically subject to frequent changes because peers join and leave the network without any central control.

In this chapter we will introduce two famous network models that arose much interest in recent years: The small-world model of Duncan Watts and Steven Strogatz [615] and scale-free or power-law networks, first presented by the Faloutsos brethren [201] and filled with life by a model of Albert- László Barabási and Réka Alberts [60]. These models describe some structural aspects of most real-world networks. The most prevalent network structure of small-world networks is a local mesh-like part combined with some random edges that make the network small.

In the last few years, an increasing number of massively distributed systems with millions of participants has emerged within very short time frames. Applications, such as instant messaging, file-sharing, and content distribution have attracted countless numbers of users. For example, Skype gained more than 2.5 millions of users within twelve months, and more than 50% of Internet traffic is originated by BitTorrent. These very large and still rapidly growing systems attest to a new era for the design and deployment of distributed systems [52]. In particular, they reflect what the major challenges are today for designing and implementing distributed systems:

scalability, flexibility, and instant deployment

.

Several different approaches to realizing the basic principles of DHTs have emerged over the last few years. Although they rely on the same fundamental idea, there is a large diversity of methods for both organizing the identifier space and performing routing. The particular properties of each approach can thus be exploited by specific application scenarios and requirements.

This overview focuses on the three DHT systems that have received the most attention in the research community: Chord, Pastry, and Content Addressable Networks (CAN). Furthermore, the systems Symphony, Viceroy, and Kademlia are discussed because they exhibit interesting mechanisms and properties beyond those of the first three systems.

After introducing some selected Distributed Hash Table (DHT) systems, this chapter introduces algorithms for DHT-based systems which balance the storage data load (Section 9.1) or care for the reliability of the data (Section 9.2).

Peer-to-peer systems are often characterized as self-organizing systems. Such characterization is frequently used to informally express properties of Peer-to-Peer systems such as the distribution of control, locality of processing, and the emergence of global structures from local interactions. Self-organizing systems are considered as being particularly scalable and failure resilient.

Since the early days of the Internet, extending routing capabilities beyond point-to-point communication has been a desired feature, mostly as a means of resource discovery. The limited size of the Internet at that time permitted the technique of broadcasting a single packet to every possible node. With its growth, Internet-wide broadcasting became increasingly expensive which imposed constraining the scope of broadcast packets to end points that expressed interest in receiving packets of a specific service (Selective Broadcast [612]). This was in fact the first attempt to offer indirectly a group communication service over the Internet.

ePOST is a Peer-to-Peer email system that provides the same functionality as existing, server-based email systems while providing better availability, scalability, fault tolerance, and security. The ePOST system has been in production use within the Computer Science department at Rice University since early 2004 and is being adopted by an increasing number of outside users.

The idea of GRID computing originated in the scientific community and was initially motivated by processing power and storage intensive applications [213]. The basic objective of GRID computing is to support resource sharing among individuals and institutions (organizational units), or resource entities within a networked infrastructure. Resources that can be shared are, for example, bandwidth, storage, processing capacity, and data [304, 429]. The resources pertain to organizations and institutions across the world; they can belong to a single enterprize or be in an external resource-sharing and service provider relationship. On the GRID, they form distributed, heterogeneous, dynamic

virtual organizations

[221]. The GRID provides a resource abstractions in which the resources are represented by services. Through the strong service-orientation the GRID effectively becomes a networked infrastructure of interoperating services. The driving vision behind this is the idea of “service-oriented science” [215].

Peer-to-Peer and Web services both address decentralized computing. They can be considered as rather distinct from each other, but a closer look at the Web services technology reveals a great potential for a combination of both Peer-to-Peer and Web services.

Self-organization is used in many disciplines to refer to several, related phenomenons. Some of the more prominent phenomenons summarized under the umbrella of self-organization are autonomy, self-maintenance, optimization, adaptivity, rearrangement, reproduction or emergence. An exact match, however, has yet to be accomplished. Even in the context of this book on Peer-to-Peer systems, self-organization is used in various forms to relate to several interesting but distinct properties of Peer-to-Peer networking.

Self-organization is seen as an attractive feature of Peer-to-Peer networks although meaning and significance of this term are far from being clear. In this chapter, principles of self-organization in Peer-to-Peer systems are identified. The potential enabled by incorporating these principles and further potentials of increasing the degree of self-organization are outlined. The Active Virtual Peer (AVP) concept is used as an example for incorporation of an enhanced level of self-organization into Peer-to-Peer systems.

In large-scale Peer-to-Peer networks without any central server instances, lookup and search,

i.e.

, locating or finding objects by their unique name or a keyword description, respectively, require the collaboration of many nodes. Peers initiate and forward or route queries for objects along overlay links. Other peers who have information on how to locate the searched for objects send their answers via the same or different overlay links back to the initially requesting peer. Finally, the object itself is normally transferred to the requestor by directly using the underlying network protocol, thus, in most cases the Internet Protocol (IP).

This chapter studies basic algorithmic tasks over overlay networks. The main idea is to explore both the communication and the computation needed to perform a task. Unlike many of the work in this area (and other chapters of the book) we mainly consider in this chapter tasks related to information gathering or dissemination, as they can be used as building blocks in many overlay applications.

When sharing information or resources - the most prominent application of Peer-to-Peer systems - one is immediately faced with the issue of searching. Any application which provides an information collection needs some means to enable users finding relevant information. Therefore, the expressivity of the query language supported by the system is a crucial aspect of Peer-to-Peer networks. Daswani et al. [154] distinguish key-based, keyword-based and schema-based systems.

This chapter focuses on information retrieval techniques in Peer-to-Peer infrastructures. Peer-to-peer systems are already being used for a vast number of applications in content exchange, but most searching is done by simple keyword lookups. In contrast information retrieval means that not only some more or less matching objects have to be retrieved, but a list of the best matching objects over the entire network given a user’s information needs. Since the 1960ies the information retrieval community considers ways to efficiently and effectively query document collections and designs dedicated retrieval systems like e.g. SMART [96].

Peer-to-Peer systems have been receiving considerable attention from the networking research community recently. Several approaches have been proposed as communication schemes in order to supply efficient and scalable inter-peer communication. These schemes are designed on top of the physical networking infrastructure as

overlay networks

taking advantage of the rich flexibility, which is accomplished at low cost. A number of important design approaches has been already presented in previous chapters. Their topologies and operation mechanisms influence greatly the performance of routing and topology maintenance algorithms and hence, the efficiency of the corresponding Peer-to-Peer system.

Peer-to-peer (P2P) applications presently contribute the main part of the traffic volume on Internet access platforms in Europe and North America. Distributed file sharing systems first emerged as a widely used application supported by a number of protocols, where the size of most popular networks counts millions of nodes being involved in mutual online data exchange. In addition, large voice over IP networks are using Peer-to-Peer technology and more applications based on a Peer-to-Peer overlay structure are expected to become popular. This has ambivalent consequences on the business models of service and network providers.

Peer-to-Peer services have become the main source of traffic in the Internet and are even challenging the World Wide Web (WWW) in popularity. Backbone operators and Internet Service Providers (ISP) consistently report Peer-to-Peer-type traffic volumes exceeding 50% of the total traffic in their networks [42, 337, 372, 556], sometimes even reaching 80% at nonpeak times [39, 236], see also chapter 22.

As we have seen in previous chapters, Peer-to-Peer-based applications are not limited to the well-known file sharing applications. Also, the Peer-to-Peer infrastructure is not limited to the hard-wired Internet infrastructure, but is starting to penetrate wireless networks of different characteristics. This chapter discusses the application of Peer-to-Peer based concepts in mobile infrastructure environments - including cellular systems and ad-hoc style networks. Starting with a motivation, application scenarios, and an overview of mobile system characteristics, the main part of this chapter describes challenges and possible solutions for optimizing Peer-to-Peer systems to meet the requirements of mobile scenarios. Both unstructured and structured Peer-to-Peer concepts for mobile scenarios are analyzed and discussed.

The field of

mobile

Peer-to-Peer networks (MP2P) has various forms and currently there exists no coherent view on what is understood by it. The term

mobile

emphasizes that nodes/peers in the network are mobile, and therefore need to be equipped with some kind of wireless communication technology. Examples of nodes include pedestrians with mobile devices [284] or vehicles with wireless communication capabilities [632]. Since all mobile Peer-to-Peer networks construct an overlay over an existing wireless network, implementations range from MP2P over mobile ad hoc networks (MANETs) [156] to MP2P over cellular based networks [299, 298].

Building efficient lookup services for the Internet constitutes an active area of research. Recent issues concentrate on building Internet-scale distributed hash tables as building block of Peer-to-Peer systems, see e.g., [505], [575]. Castro et al. proposed the VIA protocol, which enables location of application data across multiple service discovery domains, using a self-organizing hierarchy [111]. Recently, Sun and Garcia-Molina introduced a partial lookup service, exploiting the fact that for many applications it is sufficient to resolve a key to a subset of all matching values [581]. The paper discusses various design alternatives for a partial lookup service in the Internet. However, none of these papers consider distributed lookup services for mobile ad-hoc networks.

Ubiquitous computing was introduced byMarcWeiser in the early 1990s [619]. In Weiser’s vision, computers would become ubiquitous, that is, they would be present in every facet of human life. This vision has sometimes also been called the vision of the disappearing computer, since, as Weiser said, once computers become so commonplace that they are everywhere, they become such a natural part of the environment that we no longer notice them. Hence, it can be said that once computers are everywhere, they are, in fact, nowhere.

With the maturation of its technology, Peer-to-Peer applications have come increasingly into the focus of business. The promise to do business in a faster, more cost-effective and flexible way has lead to the rise of various start-ups as well as the engagement of established market players. They have created a broad variety of Peer-to-Peer business applications and services that have come to the market. However, there has to be a viable revenue model behind these business applications and services to lead them to economic success. In other words, applications should not only be highly successful in terms of adoption rates, like Instant Messaging, but also in terms of revenue generation. This chapter contains a discussion of revenue models for Peer-to-Peer business applications.

This chapter focuses on the

economic

aspects of Peer-to-Peer networks. In particular, it describes the most important requirements and presents a basic architecture for a

market-managed

Peer-to-Peer system supporting commercial applications going beyond pure file sharing. In general Peer-to-Peer systems can be used to share

any

kind of resource, including but not limited to, computing power, storage space, network capacity, files, and any combination thereof,

e.g.

, online games or multimedia streams. In the following, the term

service

will be used to refer to the individual provision of goods or resources by peers. The main goal is a completely decentralized and generic marketplace for efficient trading of such services among peers.

Markets – in their ideal form – naturally represent Peer-to-Peer (P2P) systems: market participants can be both client

and

server when exchanging offers, general messages, or goods. They can directly address each other, and interact in a decentralized and autonomous fashion. Most market implementations in history, however, were far from this ideal form.

The main characteristic of great autonomy of peers in Peer-to-Peer networks and the resulting “openness” of such networks makes them vulnerable to diverse attacks on their integrity and security. The possibility and the feasibility of obstruction of a Peer-to-Peer network as a whole, or forthright attacks on a single peer depend largely on a usage scenario of a Peer-to-Peer network. This aspect conditions the possibilities of attacks one has to either take care of or ignore.

Today’s Peer-to-Peer (P2P) systems seem to work fine for file sharing applications. Though, is that true for all kinds of applications or is it just true for file sharing of copyright protected content? In the latter case, clear incentives for sharing exist - users download copyright protected media content for free. Even here free riding is a widespread behavior [11]. Therefore, many file sharing systems introduced incentive systems, like the eMule credit system [192] or BitTorrent [320]. Obviously, for legally used Peer-to-Peer file sharing applications giving incentives to users for sharing their resources in a fair manner is an important feature.

PlanetLab is an extensively used, global, community-maintained platform for researchers to develop, deploy, and evaluate widely-distributed applications such as Peer-to-Peer systems. Because of PlanetLab’s shared nature, and its unusual design goal of continuous replacement of components by the research community, it can also be viewed somewhat as a Peer-to-Peer system (and an ongoing research project) itself. This chapter describes PlanetLab’s goals and origins, and discusses in detail the design principles that have governed its development and growth so far. It also discusses some of the methodological issues in performing research using a platform like PlanetLab - what can be learned from experimentation on PlanetLab, and what research claims can be validated by the system.