Efficient, Self-Contained Handling of Identityin Peer-to-Peer SystemsKarl Aberer, Member, IEEE, Anwitaman Datta, and Manfred Hauswirth, Member, IEEEAbstract—Identification is an essential building block for many services in distributed information systems. The quality and purpose ofidentification may differ, but the basic underlying problem is always to bind a set of attributes to an identifier in a unique anddeterministic way. Name/directory services, such as DNS, X.500, or UDDI, are a well-established concept to address this problem indistributed information systems. However, none of these services addresses the specific requirements of peer-to-peer systems withrespect to dynamism, decentralization, and maintenance. We propose the implementation of directories using a structured peer-to-peer overlay network and apply this approach to support self-contained maintenance of routing tables with dynamic IP addresses instructured P2P systems. Thus, we can keep routing tables intact without affecting the organization of the overlay networks, making itlogically independent of the underlying network infrastructure. Even though the directory is self-referential, since it uses its own serviceto maintain itself, we show that it is robust due to a self-healing capability. For security, we apply a combination of PGP-like public keydistribution and a quorum-based query scheme. We describe the algorithm as implemented in the P-Grid P2P lookup system (http://www.p-grid.org/) and give a detailed analysis and simulation results demonstrating the efficiency and robustness of our approach.Index Terms—Peer-to-peer systems, identity handling, self-maintaining, decentralized directory service, distributed hash tables,dynamic resilience.æ1INTRODUCTIONIDENTIFICATION provides an essential building block for alarge number of services and functionalities in distrib-uted information systems. In its simplest form, identifica-tion is used to uniquely denote computers on the Internetby IP addresses in combination with the Domain NameSystem (DNS) as a mapping service between symbolicnames and IP addresses. Thus, computers can conveni-ently be referred to by their symbolic names, whereas, inthe routing process, their IP addresses must be used.Higher-level directories, such as X.500/LDAP, consistentlymap properties to objects which are uniquely identified bytheir distinguished name (DN), i.e., their position in theX.500 tree. Other directories, such as UDDI, map namesonto service descriptions and vice versa. These are just afew examples among many others that map sets ofattributes onto objects and that are essential to providingbasic functionalities, suchasroutingofIPpackets,searching distributed databases, or retrieving certificatesfrom public key authorities to conduct secure e-commerce.Although the quality and purpose of identification maydiffer in the various domains, due to varying requirementsand levels of abstraction, the basic underlying problem isalways the one of binding a set of attributes to an identifier ina unique and deterministic way. Name/directory services,such as DNS, X.500, or UDDI, are a well-established conceptto address this problem in distributed information systems.Usually, these services are optimized toward the targetedproblem area and differ in the degree of (de)centralization,security guarantees, descriptive power, and flexibility.However, none of these preexisting services addresses thespecific requirements of peer-to-peer systems. Peer-to-peersystems are inherently decentralized and, thus, identifica-tion management should be decentralized as well to avoidscalability problems. For example, peer-to-peer systems arerather dynamic, with nodes frequently joining and leavingthe system, and a centralized identification service mayeasily become a bottleneck. Additionally, it is favorable notto depend on a third-party infrastructure because, if thisexternal service ceases to exist, the peer-to-peer systemwould no longer be operable. Thus, the peers should be ableto manage identification issues themselves. This providesexcellent scalability, but introduces security problems thatneed to be addressed, for example, ensuring that entries areupdated only by legitimate parties, being able to detectmalicious use, and surviving attacks.Peer-to-peer systems (also called overlay networks in theliterature) such as Chord [29], CAN [24], Freenet [7], [8],Pastry [27], or P-Grid [1], [4] operate on top of a routinginfrastructure based on a logical identification of the peersparticipating in the overlay. For routing, this logicalidentification is mapped onto an IP address in the routingtables. Since IP addresses are scarce, most peers will havedynamic IP addresses that may change over time. Thisproblem would be solved if Mobile IP [21] or IPv6 [28] werein place already and available at a large scale because theytake into account mobility (dynamism) and offer a muchlarger address space. However, this requires considerablechanges in the basic networking infrastructure of the858 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 16, NO. 7, JULY 2004. The authors are with the School of Computer and Communication Sciences,Swiss Federal Institute of Technology Lausanne (EPFL), DistributedInformation Systems Laboratory (LSIR), Batiment PSE-A, CH-1015Lausanne, Switzerland.E-mail: {karl.aberer, anwitaman.datta, manfred.hauswirth}@epfl.ch.Manuscript received 31 May 2003; revised 14 Aug. 2003; accepted 8 Dec.2003.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TKDESI-0079-0503.1041-4347/04/$20.00 ß 2004 IEEE Published by the IEEE Computer Societycomplete Internet and it cannot be foreseen at the momentwhen this will happen. Our approach could bridge this gap,but it can also be applied in many other settings, forexample, in mobile ad hoc networks, because it is indepen-dent of the networking infrastructure. Additionally, peerscan leave and join the overlay at any time. This dynamismintroduces inconsistencies into the routing tables and thewhole routing process, which may make correct routingimpossible if it is not dealt with appropriately.In Chord [29], peers that (re)join the overlay with a newIP address adopt a new identity and introduce themselvesinto the routing infrastructure like a completely new node.This is mainly due to the fact that, in Chord, the logicalidentifier depends on the IP address. To repair faultyentries
View Full Document
Unlocking...