We propose a simple distributed hash table called ReCord, which is a generalized version of Randomized-Chord and offers improved tradeoffs in performance and topology maintenance over existing P2P systems. ReCord is scalable and can be easily implemented as an overlay network, and offers a good tradeoff between the node degree and query latency. For instance, an @math -node ReCord with @math node degree has an expected latency of @math hops. Alternatively, it can also offer @math hops latency at a higher cost of @math node degree. Meanwhile, simulations of the dynamic behaviors of ReCord are studied.
Plaxton @cite_2 proposed a distributed routing protocol based on hypercubes for a static network with given collection of nodes. Plaxton's algorithm uses the technique to locate the shared resources on an overlay network in which each node only maintains a small-sized routing table. Pastry @cite_3 and Tapestry @cite_1 use Plaxton's scheme in the dynamic distributed environment. The difference between them is that Pastry uses routing scheme, whereas Tapestry uses scheme. The number of bits per digit for both Tapestry and Pastry can be reconfigured but it remains fixed during run-time. Both Pastry and Tapestry can build the overlay topology using proximity neighbor selection. However, it is still unclear whether there is any better approach to achieve globally effective routing.
@cite_1 @cite_3 @cite_2
1650675509 2167898414 2000876023
Structured peer-to-peer overlay networks such as CAN, Chord, Pastry, and Tapestry can be used to implement Internet-scale application-level multicast. There are two general approaches to accomplishing this: tree building and flooding. This paper evaluates these two approaches using two different types of structured overlay: 1) overlays which use a form of generalized hypercube routing, e.g., Chord, Pastry and Tapestry, and 2) overlays which use a numerical distance metric to route through a Cartesian hyperspace, e.g., CAN. Pastry and CAN are chosen as the representatives of each type of overlay. To the best of our knowledge, this paper reports the first head-to-head comparison of CAN-style versus Pastry-style overlay networks, using multicast communication workloads running on an identical simulation infrastructure. The two approaches to multicast are independent of overlay network choice, and we provide a comparison of flooding versus tree-based multicast on both overlays. Results show that the tree-based approach consistently outperforms the flooding approach. Finally, for tree-based multicast, we show that Pastry provides better performance than CAN. Scalable overlay networks such as Chord, CAN, Pastry, and Tapestry have recently emerged as flexible infrastructure for building large peer-to-peer systems. In practice, such systems have two disadvantages: They provide no control over where data is stored and no guarantee that routing paths remain within an administrative domain whenever possible. SkipNet is a scalable overlay network that provides controlled data placement and guaranteed routing locality by organizing data primarily by string names. SkipNet allows for both fine-grained and coarse-grained control over data placement: Content can be placed either on a pre-determined node or distributed uniformly across the nodes of a hierarchical naming sub-tree. An additional useful consequence of SkipNet's locality properties is that partition failures, in which an entire organization disconnects from the rest of the system, can result in two disjoint, but well-connected overlay networks. This paper presents the design and evaluation of Pastry, a scalable, distributed object location and routing substrate for wide-area peer-to-peer ap- plications. Pastry performs application-level routing and object location in a po- tentially very large overlay network of nodes connected via the Internet. It can be used to support a variety of peer-to-peer applications, including global data storage, data sharing, group communication and naming. Each node in the Pastry network has a unique identifier (nodeId). When presented with a message and a key, a Pastry node efficiently routes the message to the node with a nodeId that is numerically closest to the key, among all currently live Pastry nodes. Each Pastry node keeps track of its immediate neighbors in the nodeId space, and notifies applications of new node arrivals, node failures and recoveries. Pastry takes into account network locality; it seeks to minimize the distance messages travel, according to a to scalar proximity metric like the number of IP routing hops. Pastry is completely decentralized, scalable, and self-organizing; it automatically adapts to the arrival, departure and failure of nodes. Experimental results obtained with a prototype implementation on an emulated network of up to 100,000 nodes confirm Pastry's scalability and efficiency, its ability to self-organize and adapt to node failures, and its good network locality properties. We present Tapestry, a peer-to-peer overlay routing infrastructure offering efficient, scalable, location-independent routing of messages directly to nearby copies of an object or service using only localized resources. Tapestry supports a generic decentralized object location and routing applications programming interface using a self-repairing, soft-state-based routing layer. The paper presents the Tapestry architecture, algorithms, and implementation. It explores the behavior of a Tapestry deployment on PlanetLab, a global testbed of approximately 100 machines. Experimental results show that Tapestry exhibits stable behavior and performance as an overlay, despite the instability of the underlying network layers. Several widely distributed applications have been implemented on Tapestry, illustrating its utility as a deployment infrastructure. In today’s chaotic network, data and services are mobile and replicated widely for availability, durability, and locality. Components within this infrastructure interact in rich and complex ways, greatly stressing traditional approaches to name service and routing. This paper explores an alternative to traditional approaches called Tapestry. Tapestry is an overlay location and routing infrastructure that provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources. The routing and directory information within this infrastructure is purely soft state and easily repaired. Tapestry is self-administering, faulttolerant, and resilient under load. This paper presents the architecture and algorithms of Tapestry and explores their advantages through a number of experiments. Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly different from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems.In this paper, we discuss a random sampling technique that incrementally improves lookup latency in DHT systems. Our sampling can be implemented using information gleaned from lookups traversing the overlay network. For this reason, we call our approach lookup-parasitic random sampling (LPRS). LPRS is fast, incurs little network overhead, and requires relatively few modifications to existing DHT systems.For idealized versions of DHT systems like Chord, Tapestry and Pastry, we analytically prove that LPRS can result in lookup latencies proportional to the average unicast latency of the network, provided the underlying physical topology has a power-law latency expansion. We then validate this analysis by implementing LPRS in the Chord simulator. Our simulations reveal that LPRS-Chord exhibits a qualitatively better latency scaling behavior relative to unmodified Chord.Finally, we provide evidence which suggests that the Internet router-level topology resembles power-law latency expansion. This finding implies that LPRS has significant practical applicability as a general latency reduction technique for many DHT systems. This finding is also of independent interest since it might inform the design of latency-sensitive topology models for the Internet. The Chord peer-to-peer system is considered, together with CAN, Tapestry and Pastry, as one of the pioneering works on peer-to-peer distributed hash tables (DHT) that inspired a large volume of papers and projects on DHTs as well as peer-to-peer systems in general. Chord, in particular, has been studied thoroughly, and many variants of Chord have been presented that optimize various criteria. Also, several implementations of Chord are available on various platforms. Though Chord is known to be very efficient and scalable and it can handle churn quite well, no protocol is known yet that guarantees that Chord is self-stabilizing, i.e., the Chord network can be recovered from any initial state in which the network is still weakly connected. This is not too surprising since it is known that in the Chord network it is not locally checkable whether its current topology matches the correct topology. We present a slight extension of the Chord network, called Re-Chord (reactive Chord), that turns out to be locally checkable, and we present a self-stabilizing distributed protocol for it that can recover the Re-Chord network from any initial state, in which the n peers are weakly connected, in O(n log n) communication rounds. We also show that our protocol allows a new peer to join or an old peer to leave an already stable Re-Chord network so that within O((log n)2) communication rounds the Re-Chord network is stable again. This paper uses big data and machine learning for the real-time management of Internet scale quality-of-service (QoS) route optimisation with an overlay network. Based on the collection of data sampled every 2 min over a large number of source–destinations pairs, we show that intercontinental Internet protocol (IP) paths are far from optimal with respect to QoS metrics such as end-to-end round-trip delay. We, therefore, develop a machine learning-based scheme that exploits large scale data collected from communicating node pairs in a multihop overlay network that uses IP between the overlay nodes, and selects paths that provide substantially better QoS than IP. Inspired from cognitive packet network protocol, it uses random neural networks with reinforcement learning based on the massive data that is collected, to select intermediate overlay hops. The routing scheme is illustrated on a 20-node intercontinental overlay network that collects some @math measurements per week, and makes scalable distributed routing decisions. Experimental results show that this approach improves QoS significantly and efficiently. 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. This paper sketches the design of PAST, a large-scale, Internet-based, global storage utility that provides scalability, high availability, persistence and security. PAST is a peer-to-peer Internet application and is entirely self-organizing. PAST nodes serve as access points for clients, participate in the routing of client requests, and contribute storage to the system. Nodes are not trusted, they may join the system at any time and may silently leave the system without warning. Yet, the system is able to provide strong assurances, efficient storage access, load balancing and scalability. Among the most interesting aspects of PAST's design are (1) the Pastry location and routing scheme, which reliably and efficiently routes client requests among the PAST nodes, has good network locality properties and automatically resolves node failures and node additions; (2) the use of randomization to ensure diversity in the set of nodes that store a file's replicas and to provide load balancing; and (3) the optional use of smartcards, which are held by each PAST user and issued by a third party called a broker The smartcards support a quota system that balances supply and demand of storage in the system. A number of distributed hash table (DHT)-based protocols have been proposed to address the issue of scalability in peer-to-peer networks. In this paper, we present Ulysses, a peer-to-peer network based on the butterfly topology that achieves the theoretical lower bound of log n log log n on network diameter when the average routing table size at nodes is no more than log n. Compared to existing DHT-based schemes with similar routing table size, Ulysses reduces the network diameter by a factor of log log n, which is 2–4 for typical configurations. This translates into the same amount of reduction on query latency and average traffic per link node. In addition, Ulysses maintains the same level of robustness in terms of routing in the face of faults and recovering from graceful ungraceful joins and departures, as provided by existing DHT-based schemes. The performance of the protocol has been evaluated using both analysis and simulation. Copyright © 2004 AEI We present gradient landmark-based distributed routing (GLIDER), a novel naming addressing scheme and associated routing algorithm, for a network of wireless communicating nodes. We assume that the nodes are fixed (though their geographic locations are not necessarily known), and that each node can communicate wirelessly with some of its geographic neighbors - a common scenario in sensor networks. We develop a protocol which in a preprocessing phase discovers the global topology of the sensor field and, as a byproduct, partitions the nodes into routable tiles - regions where the node placement is sufficiently dense and regular that local greedy methods can work well. Such global topology includes not just connectivity but also higher order topological features, such as the presence of holes. We address each node by the name of the tile containing it and a set of local coordinates derived from connectivity graph distances between the node and certain landmark nodes associated with its own and neighboring tiles. We use the tile adjacency graph for global route planning and the local coordinates for realizing actual inter- and intra-tile routes. We show that efficient load-balanced global routing can be implemented quite simply using such a scheme. Dipsea is a modular architecture for building a Distributed Hash Table (DHT). A DHT is a large hash table that is cooperatively maintained by a large number of machines communicating over the Internet. Decentralization and automatic re-configuration are two key design goals for a DHT. The architecture of Dipsea consists of three layers: ID Management, Overlay Routing and Data Management. The Overlay Routing layer consists of three modules: Emulation Engine, Ring Management and Choice of Long-Distance Links. Efficient algorithms for ID Management are designed—these algorithms require few messages, require few re-assignments of existing IDs and ensure that the hash table is divided among the participating machines as evenly as possible. Ring Management ensures that participating machines establish connections among themselves, as a function of their IDs, to form a fault-tolerant ring. The Emulation Engine is responsible for “emulation” of arbitrary families of routing networks. It handles issues arising out of dynamism (arrival and departure of participating machines), scale (variation in the average number of participating machines) and physical network proximity. Choice of Long-Distance Links allows a DHT to choose any family of routing networks (deterministic or randomized) for emulation. Several deterministic and randomized routing networks are designed and analyzed. Among these are Symphony (one of the first randomized DHT routing networks), Papillon (a deterministic routing network that guarantees asymptotically optimal route lengths with greedy routing for a fixed out-degree of nodes), and Mariposa (a randomized routing network that also guarantees optimal route lengths for a given out-degree of nodes). We study a fundamental tradeoff issue in designing a distributed hash table (DHT) in peer-to-peer (P2P) networks: the size of the routing table versus the network diameter. Observing that existing DHT schemes have either 1) a routing table size and network diameter both of O(log sub 2 n), or 2) a routing table of size d and network diameter of O(n sup 1 d ), S. (2001) asked whether this represents the best asymptotic "state-efficiency" tradeoffs. We show that some straightforward routing algorithms achieve better asymptotic tradeoffs. However, such algorithms all cause severe congestion on certain network nodes, which is undesirable in a P2P network. We rigorously define the notion of "congestion" and conjecture that the above tradeoffs are asymptotically optimal for a congestion-free network. The answer to this conjecture is negative in the strict sense. However, it becomes positive if the routing algorithm is required to eliminate congestion in a "natural" way by being uniform. We also prove that the tradeoffs are asymptotically optimal for uniform algorithms. Furthermore, for uniform algorithms, we find that the routing table size of O(log sub 2 n) is a magic threshold point that separates two different "state-efficiency" regions. Our third result is to study the exact (instead of asymptotic) optimal tradeoffs for uniform algorithms. We propose a new routing algorithm that reduces the routing table size and the network diameter of Chord both by 21.4 without introducing any other protocol overhead, based on a novel number-theory technique. Our final result is to present Ulysses, a congestion-free nonuniform algorithm that achieves a better asymptotic "state-efficiency" tradeoff than existing schemes in the probabilistic sense, even under dynamic node joins leaves. The task of moving data (i.e., the routing problem) in large-scale sensor networks has to contend with several obstacles, including severe power constraints at each node and temporary, but random, failures of nodes, rendering routing schemes designed for traditional communication networks ineffective. We consider the open problem of finding optimum routes between any fixed source-destination pair in a large-scale network, such that the communication load (i.e., the required power) is distributed among all the nodes, the overall latency is minimized, and the algorithm is decentralized and robust. A recent work addressed this problem in the context of a grid topology and showed how to obtain load-balanced routing, but transmissions are restricted to be among near-neighbors and the overall latency grows linearly with the number of nodes. We show how one can route messages between source and destination nodes along random small-world topologies using a decentralized algorithm. Specifically, nodes make connections independently (based only on the source and destination information in the packets), according to a distribution that guarantees an average latency of O(log sup 2 (N)), while preventing hotspot regions by providing an almost uniform distribution of traffic load over all nodes. Surprisingly, the randomized nature of the network structure keeps the average per-node power consumption almost the same as in the case of a grid topology (i.e., local transmissions), while providing an exponential reduction in latency, resulting in a highly fault-tolerant and stable design capable of working in very dynamic environments. This paper presents Virtual Ring Routing (VRR), a new network routing protocol that occupies a unique point in the design space. VRR is inspired by overlay routing algorithms in Distributed Hash Tables (DHTs) but it does not rely on an underlying network routing protocol. It is implemented directly on top of the link layer. VRR provides both raditional point-to-point network routing and DHT routing to the node responsible for a hash table key.VRR can be used with any link layer technology but this paper describes a design and several implementations of VRR that are tuned for wireless networks. We evaluate the performance of VRR using simulations and measurements from a sensor network and an 802.11a testbed. The experimental results show that VRR provides robust performance across a wide range of environments and workloads. It performs comparably to, or better than, the best wireless routing protocol in each experiment. VRR performs well because of its unique features: it does not require network flooding or trans-lation between fixed identifiers and location-dependent addresses. Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick [2001] to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by [2000]. Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme. Let n denote the number of nodes in the network. We provide a labeled routing scheme that, after a stretch--5 handshaking step (similar to DNS lookup in TCP IP), routes messages along stretch--3 paths. We prove that, instead of routing tables with O(n1 2) bits (O suppresses factors logarithmic in n) as in the general scheme by Thorup and Zwick, expected sizes of O(nγ log n) bits are sufficient, and that all the routing tables can be constructed at once in expected time O(n1+γ log n), with γ = τ-22 τ-3 + e, where τ∈(2,3) is the power-law exponent and e 0 (which implies e With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick [2001, 2005] for stretch-3 and we obtain a new upper bound of expected O(n1+γ) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5--approximate distance queries in time at most O(n1 4+e) (similar to γ, the exponent actually depends on τ and lies between e and 1 4 + e). We propose optimal routing algorithms for Chord [1], a popular topology for routing in peer-to-peer networks. Chord is an undirected graph on 2b nodes arranged in a circle, with edges connecting pairs of nodes that are 2k positions apart for any k ≥ 0. The standard Chord routing algorithm uses edges in only one direction. Our algorithms exploit the bidirectionality of edges for optimality. At the heart of the new protocols lie algorithms for writing a positive integer d as the difference of two non-negative integers d′ and d″ such that the total number of 1-bits in the binary representation of d′ and d″ is minimized. Given that Chord is a variant of the hypercube, the optimal routes possess a surprising combinatorial structure. We adapt the compact routing scheme by Thorup and Zwick to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu. Our result is the first theoretical bound coupled to the parameter of the power-law graph model for a compact routing scheme. In particular, we prove that, for stretch 3, instead of routing tables with O(n1 2) bits as in the general scheme by Thorup and Zwick, expected sizes of O(nγ log n) bits are sufficient, and that all the routing tables can be constructed at once in expected time O(n1 + γ log n), with γ = τ - 2 2τ - 3 + Ɛ, where τ ∈ (2, 3) is the power-law exponent and Ɛ > 0. Both bounds also hold with probability at least 1 - 1 n (independent of Ɛ). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step and using addresses and message headers with O(log n log log n) bits, with probability at least 1 - o(1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick for stretch 3 and obtain a new upper bound of expected O(n1+γ) for space and preprocessing. The first sublinear average space universal compact routing schemes for directed networks are presented. For each integer k ≥ 1, they use O(k log n)size addresses; O(kn1 (k+1))-sized routing tables on average at each node; and achieve roundtrip routes of stretch at most 2k+1 - 1 in any (weighted) directed network. We also present universal compact roundtrip routing schemes with the stronger requirement that they use sublinear maximum space at every node. These schemes also use O(k log n) size addresses and achieve roundtrip routes of stretch at most 2k+ 1 -1 in any (weighted) directed network, and they bound the maximum sized table at each node by O(kn(3k+1) (2ċ3k)).