Routing with a peer-to-peer overlay network in large-scale distributed computing environments
Cheng-Jia Lai, Richard R. Muntz · 2005
In a large-scale distributed computing environment, a vast number of objects are installed on nodes at different locations; thus, any mechanism for processing a query for a remote object must employ a routing algorithm so that the query is forwarded to a node where the queried object is installed. Nodes and objects can be dynamically inserted and deleted. Each object is presumably mobile among nodes, though this mobility is transparent to any accessing party. Further, an object may have replicas on multiple nodes simultaneously. As the routing problem is ubiquitous in distributed computing with various formats of object labels that are the keys for object identification, an efficient and scalable solution is to create a distributed hash table (DHT) that provides a mechanism for routing by a fixed-length object identifier (OID). The OID of an object is generated by a hash function that takes as input the object label, descriptive properties, or contents, so that an OID is effectively assigned at random. Autonomous DHT's used in different user groups, such as clusters of servers in a peer-to-peer web-browsing application, can evolve in a complex way such that one DHT needs to merge with another, to extend DHT user population or object availability. DHT partitions due to node failures also need to remerge in a timely fashion. In fact, it is inefficient to merge two DHT's by simply deleting all nodes in one DHT and inserting them into the other and re-registering all objects on those migrating nodes. As an alternative, we propose a new DHT approach that provides a more efficient merging mechanism by partially re-computing the routing tables, and a relatively short latency with O (1) stretch in forwarding a query. The average routing table size is O (log n) if there are n nodes. The proposed approach handles adding and deleting a link between any two nodes, and maintains a high performance link structure by adapting to updates in link costs at run time, with soft-state techniques for fault-tolerance. Thus, it has significant new advantages for building an efficient DHT for real applications in large-scale distributed computing environments.