nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Structured Peer-to-Peer Systems

Fundamentals of Hierarchical Organization, Routing, Scaling, and Security

verfasst von: Dmitry Korzun, Andrei Gurtov

Verlag: Springer New York

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The field of structured P2P systems has seen fast growth upon the introduction of Distributed Hash Tables (DHTs) in the early 2000s. The first proposals, including Chord, Pastry, Tapestry, were gradually improved to cope with scalability, locality and security issues. By utilizing the processing and bandwidth resources of end users, the P2P approach enables high performance of data distribution which is hard to achieve with traditional client-server architectures. The P2P computing community is also being actively utilized for software updates to the Internet, P2PSIP VoIP, video-on-demand, and distributed backups. The recent introduction of the identifier-locator split proposal for future Internet architectures poses another important application for DHTs, namely mapping between host permanent identity and changing IP address. The growing complexity and scale of modern P2P systems requires the introduction of hierarchy and intelligence in routing of requests.

Structured Peer-to-Peer Systems covers fundamental issues in organization, optimization, and tradeoffs of present large-scale structured P2P systems, as well as, provides principles, analytical models, and simulation methods applicable in designing future systems. Part I presents the state-of-the-art of structured P2P systems, popular DHT topologies and protocols, and the design challenges for efficient P2P network topology organization, routing, scalability, and security. Part II shows that local strategies with limited knowledge per peer provide the highest scalability level subject to reasonable performance and security constraints. Although the strategies are local, their efficiency is due to elements of hierarchical organization, which appear in many DHT designs that traditionally are considered as flat ones. Part III describes methods to gradually enhance the local view limit when a peer is capable to operate with larger knowledge, still partial, about the entire system. These methods were formed in the evolution of hierarchical organization from flat DHT networks to hierarchical DHT architectures, look-ahead routing, and topology-aware ranking. Part IV highlights some known P2P-based experimental systems and commercial applications in the modern Internet. The discussion clarifies the importance of P2P technology for building present and future Internet systems.

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

Chapter 1. Terminology, Problems, and Design Issues

Abstract

The aim of this chapter is to introduce first the basic concepts, terminology, and notation we use throughout this book. Although the term “structure” is central in our discussion on structured P2P networks, its definition is quite fuzzy in recent P2P literature. Secondly, the chapter aims at common understanding about intuition and reasons behind this term. The description is assisted with introduction to a set of challenging problems that the P2P networking faces today.

Dmitry Korzun, Andrei Gurtov

Chapter 2. Flat DHT Routing Topologies

Abstract

In this chapter, we survey existing classical DHTs grouped according to their topologies. We describe basic architectures for efficient overlay routing and corresponding classes of graphs. We start with introducing Content Addressable Network (CAN) as an example of Torus topology. It is followed by Chord, Kademlia and Accordion as DHTs using the Ring topology. Pastry, Tapestry and Bamboo DHTs are grouped under the PRR tree topology. Trie and balanced trees are represented by P-Grid, skip graphs. Finally, we present several DHTs that are using De Bruijn and Kautz graphs, Butterfly and O(1)-hop topologies. These topologies differ in how they collect local information in a DHT node about the global network. The next chapter will show how these architectures can be generalized using hierarchical approach.

Dmitry Korzun, Andrei Gurtov

Local Strategies

Frontmatter

Chapter 3. Hierarchical Neighbor Maintenance

Abstract

In flat DHTs, various kinds of arranging items occur very frequently, leading to tree-like structures and hierarchical routing schemes. Different existing proposals can be unified in the terms of hierarchy, and routing schemes are built into a logical structure. There are certain design principles that define general directions for various hierarchical techniques to improve DHT routing. This chapter shows that the known routing efficiency of flat DHTs is due to hierarchical schemes in the local construction and maintenance of routing tables.

Dmitry Korzun, Andrei Gurtov

Chapter 4. Adaptable Overlay Network Topology

Abstract

The previous chapter overviewed hierarchical schemes that a node uses locally to arrange its neighbors, achieving effective routing in a flat network. This chapter focuses on further advanced routing schemes where nodes are intentionally specialized in routing. Such schemes lead to a kind of global hierarchy in the network; nodes become globally differentiated, specializing their roles in routing. According to the participants heterogeneity, the schemes differentiate (1) nodes in their routing responsibility (node specialization) and (2) resources in their distribution in the whole system (resource distribution).

Dmitry Korzun, Andrei Gurtov

Chapter 5. Clustering

Abstract

In the previous chapters we considered the dynamic differentiation of nodes and resources in flat P2P systems. This chapter shows that the design principles of the differentiation evolve to the clustering principle. It is the last conceptual step before the traditional hierarchy of HDHTs. We focus on reasons of clustering and consider local group formations possible on the top flat DHT overlays. Such formations eventually appear non-negligible from the point of view of the global overlay topology. They provide a mechanism to control the tradeoff between local and global routing.

Dmitry Korzun, Andrei Gurtov

Chapter 6. Local Ranking

Abstract

Intrinsically, P2P networks are anonymous, dynamic, and autonomous. Participants have natural disincentives to cooperate because cooperation consumes their own resources and may degrade their own performance. Consequently, each node selfishly attempts to maximize own utility lowering the overall utility of the system. Avoiding this “tragedy of the commons” requires incentives for cooperation. This chapter considers design principles for providing incentives for cooperation in resource sharing among nodes. Fair resource sharing needs differentiation based on the contribution/consumption each node has in the system. We state the problem of local ranking in a P2P resource sharing system with multiple resources. It provides rank-based differentiation of competing nodes and their resources. Introducing ranks rewards cooperating nodes and punishes defect behavior. In this chapter, we focus on ranking models with local knowledge only; the class of models with global system knowledge is discussed later in Chap. 10.

Dmitry Korzun, Andrei Gurtov

Beyond the Local Knowledge

Frontmatter

Chapter 7. Hierarchical DHT Architectures

Abstract

Distributed Hash Tables (DHT) are presently used in several large-scale distributed systems in the Internet and envisaged as a key mechanism to provide identifier-locator separation for mobile hosts in Future Internet. Such decentralized structured data storage systems become increasingly complex serving popular social networking, P2P applications, and Internet-scale infrastructures. Hierarchy is a standard mechanism for coping with complexity, scalability, and heterogeneity in distributed systems. To address the shortcomings of flat DHT designs, many hierarchical P2P designs have been proposed over recent years. The last generation is hierarchical DHTs (HDHTs) where nodes are organized onto layers and groups. This chapter discusses concepts of hierarchical architectures in structured P2P overlay networks, focusing on HDHT designs. We introduce a framework consisting of conceptual models of network hierarchy, multi-layer hierarchical P2P architectures, and principles affecting the design choices. Based on the framework we provide taxonomy of existing P2P systems and thoroughly go over proposed hierarchical P2P alternatives.

Dmitry Korzun, Andrei Gurtov

Chapter 8. Cyclic Routing

Abstract

Distributed Hash Tables (DHT) provide a lookup service in peer-to-peer overlay networks. The known problem is that lookups function poorly when no direct IP connectivity is available to some nodes (e.g., located behind a NAT or firewall) or in the presence of overloaded or malicious nodes. In this chapter, we describe a method for DHT-based routing called Cyclic Routing (CR). It generalizes existing single-hop look-ahead approach (also known as “Know thy neighbor’s neighbor”) and supports multipath routing. The method provides a systematic way for collecting stable and efficient overlay paths. Cyclic routing has the same theoretical dependability and efficiency upper bounds as basic DHT routing but it is more resilient when IP connectivity is limited or when the overlay suffers from overloaded nodes. The CR method was implemented in the CR-Chord protocol and its experimental evaluation showed improvement in the lookup availability.

Dmitry Korzun, Andrei Gurtov

Chapter 9. Diophantine Routing

Abstract

An important problem in any structured P2P overlay network is what routes are available between nodes. Understanding the structure of routes helps to solve problems related to routing performance, security, and scalability. In this chapter, we propose a theoretical approach for describing routes and their structures. It is based on recent results in the linear Diophantine analysis. A route aggregates several P2P paths that packets follow. A commutative context-free grammar describes the forwarding behavior of P2P nodes. Derivations in the grammar correspond to P2P routes. Initial and final strings of a derivation define packet sources and destinations, respectively. Based on that we construct a linear Diophantine equation system, where any solution counts forwarding actions in a route representing certain integral properties. Therefore, P2P paths and their composition into routes are described by a linear Diophantine system—a Diophantine model of P2P routes. Its finite basis of the solution set defines the structure of available routes.

Dmitry Korzun, Andrei Gurtov

Chapter 10. Structural Ranking

Abstract

Open P2P networks are subject for selfish and incorrect behavior of nodes and even intentional attacks. A maintenance protocol must preserve topology structure not only according with the rules of the efficient graph for routing, but also accounting the cooperation level of nodes. Although the actions taken by intermediate nodes in the P2P network are hidden from the source node, the latter must have some guarantees on their correctness. This problem leads to incentive mechanisms to encourage cooperation of nodes. Such mechanisms provide each node with estimates of others behavior and the node makes own decisions when it selects its actions. In Chap. 6 we consider local ranking models when a node u decides its actions for node v based solely on directly observed past behavior of v. In this chapter, we focus on structural ranking models when network topology structure essentially information for computing ranks of nodes, as it is assumed in such well-known graph-based algorithms as PageRank and EigenTrust. We study models with partial knowledge and distributed computations when each node maintains some knowledge about the global network topology. The knowledge is a topology subgraph that aggregates, in form of cycles, direct and indirect observations of past behavior of nodes.

Dmitry Korzun, Andrei Gurtov

Applications

Frontmatter

Chapter 11. CR-Chord

Abstract

Without additional mechanisms conventional DHTs are vulnerable to attacks. In particular, previous research showed that Chord is not well resistant to malicious nodes that joined the DHT. This chapter describes the CR-Chord protocol, our implementation of the cyclic routing algorithm. Using simulations we compare the lookup availability of basic Chord and CR-Chord. The results suggest that CR-Chord improves the lookup availability on the average by 1.4 times. When the number of malicious nodes is small, such as 5%, CR-Chord has almost twice lower lookup failure rate.

Dmitry Korzun, Andrei Gurtov

Chapter 12. Indirection Infrastructures

Abstract

The Host Identity Indirection Infrastructure (Hi3) is a general-purpose networking architecture, derived from the Internet Indirection Infrastructure (i3) and the Host Identity Protocol (HIP). Hi3 combines efficient and secure end-to-end data plane transmission of HIP with robustness and resilience of i3. The architecture is well-suited for mobile hosts given the support for simultaneous host mobility, rendezvous and multi-homing. Although an Hi3 prototype is implemented and tested on PlanetLab, scalability properties of Hi3 for a large number of hosts are unknown. In this chapter, we propose a simple model for bounds of size and latency of the Hi3 control plane for a large number of clients and in the presence of DoS attacks. The model can be used for a first approximation study of a large-scale Internet control plane before its deployment. We apply the model to quantify the performance of the Hi3 control plane. Our results show that the Hi3 control plane can support a large number of mobile hosts with acceptable latency.

Dmitry Korzun, Andrei Gurtov

Chapter 13. Commercial Applications

Abstract

This chapter describes several distributed databases for storing structured data in the Internet. They are known under a common name of NoSQL, to separate from traditional relational database management systems (RDBMSes). NoSQL databases are often built on top of classical DHT functionality with goals of high performance put and get operations for data using a key. Databases such as Cassandra power popular services including Facebook and therefore have to scale up to billions of users.

Dmitry Korzun, Andrei Gurtov

Backmatter

Titel: Structured Peer-to-Peer Systems
verfasst von: Dmitry Korzun
Andrei Gurtov
Verlag: Springer New York
Electronic ISBN: 978-1-4614-5483-0
Print ISBN: 978-1-4614-5482-3
DOI: https://doi.org/10.1007/978-1-4614-5483-0