Optimal layer division for low latency in DHT‐based hierarchical P2P network

Hierarchical architecture can significantly reduce the workload overheads and facilitate effective search in peer‐to‐peer (P2P) network by dividing the peers into two layers: a supernode layer and an ordinary node layer. System scalability is therefore improved, which is critical to the deployment of P2P applications, particularly for the P2P‐based Voice over Internet Protocol systems. However, the lack of appropriate size ratio of the supernode layer to the ordinary node layer makes the system search performance far from being optimal. To address the problem, the goal of this paper is to find the optimal layer ratio, such that lookup latency is minimized, subject to the capacity constraint of supernodes. With this particular objective, this paper first formulates a search delay model for the distributed hash table (DHT)‐based layered P2P architecture, taking account of two main sources of latency: DHT routing and queuing delay at the supernode. Then the optimal ratio between supernodes and ordinary nodes is found with the analytical model. Simulation and numerical results show that the obtained solution can improve the performance of a two‐layer P2P system in terms of lookup latency. Copyright © 2016 John Wiley & Sons, Ltd.     

一种对等网络层次比率优化模型

层次比率是影响层次P2P系统查找性能的主要因素,利用节点能力的差异性,建立了基于DHT的两层P2P网络结构的查询时延模型和节点负荷模型,并根据模型求出最优层次比率。仿真结果证明了提出的求解方案能有效地提高两层P2P网络的查找性能,使系统具有更好的可扩展性,有利于P2P网络应用,尤其是基于P2P的VoIP应用的大规模部署。     

Lookup Performance Deficiencies in the KAD Network

The KAD network is one of the largest distributed hash tables (DHT) deployed in the real world. DHT is designed to provide scalable peer-to-peer lookup service. Its real-world lookup performance, however, is recognized as inefficient. We ran wide-range measurements on the KAD network to evaluate this inefficiency by examining peer behaviors in publishing and retrieving information using routing tables and publishing tables. Our measurements show that even though routing tables are well maintained, the current refreshment scheme of publishing tables and lack of effective incentive policy cause lookup performance deficiency. Based on our findings, we propose three improvement schemes, analyze their strengths, and give suggestions to implementations.     

结构化P2P资源搜索算法及其在未来光网络中的应用

推进绿色节能光网络是未来光网络面临的重要挑战之一。基于DHT的结构化P2P资源搜索算法因为可扩展性、鲁棒性、负载均衡、查询效率高等特点更适用于具有云计算、物联网、移动互联网等特点的未来光网络中的资源搜索。研究结构化P2P资源搜索算法的特点,从降低能耗角度分析算法对未来光网络产生的影响,提出在名址分离架构的未来网中快速资源搜索设计方法,最后探讨P2P资源搜索算法在未来光网络中面临的挑战。     

SDHT:面向P2P直播系统的高效单跳分布式哈希查找策略

Video data location plays a key role for Peer-to-Peer (P2P) live streaming applications. In this paper, we propose a new one-hop Distributed Hash Table (DHT) lookup framework called Streaming-DHT (SDHT) to provide efficient video data location service. By adopting an enhanced events dissemination mechanism-EDRA+ , the accuracy of routing table at peers can be guaranteed. More importantly, in order to enhance the performance of video data lookup operation without incurring extra overhead, we design a so-called Distributed Index Mapping and Management Mechanism (DIMM) for SDHT. Both analytical modeling and intensive simulation experiments are conducted to demonstrate the effectiveness of SDHT framework. Numerical results show that almost 90% requested video data can be retrieved within one second in SDHT based systems, and SDHT needs only 26% average bandwidth consumption when compared with similar one-hop DHT solutions such as D1HT. This indicates that SDHT framework is an appropriate data lookup solution for time-sensitive network applications such as P2P live streaming.     

RepMChord: A novel replication approach for mobile Chord with reduced traffic overhead

Structured peer‐to‐peer systems based on distributed hash table (DHT) have known a great popularity and performance since their appearance. They have experienced multiple improvements to increase the efficiency, like replication mechanism with different used methods and different objectives like increasing data availability or fitting to churn. Besides their benefits, these methods suffer from the excessive generated overhead in maintenance process. On the other side, we have the interest deployment of DHT overlay on mobile ad hoc network, which benefits from the infrastructure‐less architecture, but presents some shortcomings because of the limited bandwidth and energy batteries, what require a reduced overhead. Therefore, the aim of this work is to improve the lookup efficiency of DHT‐based Chord on mobile ad hoc network underlay. For that, we propose a novel replication mechanism based on data structure to determine the replica nodes, while avoiding the excessive generated overhead in maintenance process to cope with the problem of limited energy batteries. To evaluate the proposed method, we present an extensive simulation study that compares the work to another efficient replication method and to mobile basic Chord. The results show the efficiency of our approach in decreasing the lookup path, the maintenance overhead, and the energy consumption.     

GTPP: General Truncated Pyramid Peer-to-Peer Architecture over Structured DHT Networks

Hierarchical Distributed Hash Table (DHT) architectures have been among the most interesting research topics since the birth of flat DHT architecture. However, most of the previous work has merely focused on the two-tier hierarchy. In this paper, we study and analyze General Truncated Pyramid Peer-to-Peer (GTPP) architecture, the generalized version of Partially Vertical Hierarchical Architecture (PV-HA). The idea is to study whether added tiers of hierarchy can provide added value in performance and functionality. Through mathematical analysis, we demonstrate performance results in comparison to flat architecture, which helps understanding the typical characteristics of hierarchical architectures. Firstly, GTPP has slightly higher expected lookup hop count, although it can be decreased with optimizing the sub-overlay setup. However, GTPP significantly decreases the expected lookup routing latency. Secondly, GTPP has clearer and more reasonable traffic distribution among all the peers from different tiers of sub-overlays, and can work with slightly lower maintenance traffic. Thirdly, our studies indicate that two to three tiers are most suitable in most cases for GTPP, considering all the parameters.     

Distributed Hash table-based routing and data management in wireless sensor networks: a survey

Recent advances in Wireless Sensor Networks (WSN) have led to a great breakthrough in sensors design and features. These technological novelties have brought additional challenges to WSN. Sensornets are seeking for new approaches for efficient data routing and management. The last few years have witnessed the emergence of several approaches that build Distributed Hash Tables (DHTs) over WSN. DHTs are initially conceived for efficient data lookup in large-scale wired networks. The main objective of this combination is to manage location-independent data and nodes identification. DHT mapping over WSN brings however new challenges. This paper presents an analytical survey on applying DHT techniques in WSNs. It describes existing DHT-based routing and data management protocols and includes a detailed classification of them.     

IP lookups using multiway and multicolumn search

IP address lookup is becoming critical because of increasing routing table sizes, speed, and traffic in the Internet. Given a set S of prefixes and an IP address D, the IP address lookup problem is to find the longest matching prefix of D in set S. This paper shows how binary search can be adapted for solving the best-matching prefix problem. Next, we show how to improve the performance of any best-matching prefix scheme using an initial array indexed by the first X bits of the address. We then describe how to take advantage of cache line size to do a multiway search with six-way branching. Finally, we show how to extend the binary search solution and the multiway search solution for IPv6. For a database of N prefixes with address length W, naive binary search would take O(W*log N); we show how to reduce this to O(W+log N) using multiple-column binary search. Measurements using a practical (Mae-East) database of 38000 entries yield a worst-case lookup time of 490 ns, five times faster than the Patricia trie scheme used in BSD UNIX. Our scheme is attractive for IPv6 because of its small storage requirement (2N nodes) and speed (estimated worst case of 7 cache line reads per lookup)     

对等网的快速路由模型

在DHT基础上建立一种快速的自组织路由模型(FSRM),设计了该模型的路由查找方法,节点加入与离开机制。同时,针对扰动环境下临近节点选择问题,提出稳定性阈值度量的方法,保证了对等网的快速路由和快速收敛。并在仿真测试中对该模型的性能进行了分析,证明该模型在收敛时间,节点查询速度,和对扰动的适应性方面优于传统的模型。     

The connection between information theory and object search in networks

This paper aims to establish a connection between information theory and object search in networks. We make two contributions: 1) Using information theoretical arguments, we establish fundamental lower bounds on lookup table sizes and search step numbers. These bounds generalize those derived previously and can deal with non-uniform lookup distributions and object popularities. 2) Using the analogy between search sequences and data compression and coding, we propose a distributed implementation of Shannon code that can reduce the expected length of search sequences to an arbitrarily small value at the cost of at most doubling the table sizes.     

IPv6快速路由查找算法分析与研究

分析了IPv6路由结构的特点,介绍了IPv6中的各种路由查找技术,提出了基于聚集位向量的快速路由查找算法,并对该算法和常用二分查找算法的性能进行了分析比较,实验结果表明该算法较好地提高了查找速度,减少了对内存的消耗.     

Survey and taxonomy of IP address lookup algorithms

Due to the rapid growth of traffic in the Internet, backbone links of several gigabits per second are commonly deployed. To handle gigabit-per-second traffic rates, the backbone routers must be able to forward millions of packets per second on each of their ports. Fast IP address lookup in the routers, which uses the packet's destination address to determine for each packet the next hop, is therefore crucial to achieve the packet forwarding rates required. IP address lookup is difficult because it requires a longest matching prefix search. In the last couple of years, various algorithms for high-performance IP address lookup have been proposed. We present a survey of state-of-the-art IP address lookup algorithms and compare their performance in terms of lookup speed, scalability, and update overhead     

Efficient lookup on unstructured topologies

We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of LMS. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size     

基于非重叠前缀集合的并行路由查找系统

快速的路由查找机制是高性能路由器设计的关键.最长匹配查找是路由查找的难点所在.本文提出一个并行路由查找系统.它使用一种路由表划分方法,可将路由表中的前缀划分为若干个集合,集合内前缀没有重叠.从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找.基于这种方法,本文还提出一个通用的并行路由查找框架,框架适用于大多数路由查找算法.并行查找框架可简化查找算法的设计,提高查找算法的速度.使用二分查找算法,并行查找系统可以达到log₂(2N/B)的查找复杂度 (N为路由表前缀数目,B为大于4的整数).同时,并行查找系统对IPv6也具有很好的扩展性.     

IP Address Lookup for Internet Routers Using Balanced Binary Search with Prefix Vector

We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.     

Arranging multicast forwarding table in class sequence in ternary-cam for line-speed lookup

PIM-SM (Protocol Independent Multicast-Sparse Mode) is a main multicast routing protocol in the IPv6 (Internet Protocol version 6). It can use either a shared tree or a shortest path tree to deliver data packets, consequently the multicast IP lookup engine requires, in some cases, two searches to get a correct lookup result according to its multicast forwarding rule, and it may result in a new requirement of doubling the lookup speed of the lookup engine. The ordinary method to satisfy this requirement in TCAM (Ternary Content Addressable Memory) based lookup engines is to exploit parallelism among multiple TCAMs. However, traditional parallel methods always induce more resources and higher design difficulty. We propose in this paper a novel approach to solve this problem. By arranging multicast forwarding table in class sequence in TCAM and making full use of the intrinsic characteristic of the TCAM, our approach can get the right lookup result with just one search and a single TCAM, while keeping the hardware of lookup engine unchanged. Experimental results have shown that the approach make it possible to satisfy forwarding IPv6 multicast packets at the full link rate of 20 Gb/s with just one TCAM with the current TCAM chip.     

高性能安全路由器中快速路由查找算法的研究与实现

设计快速的路由查找算法是提高路由器整体性能的关键之一.文章在一种基于RAM快速路由查找算法的基础上,根据高性能安全路由器的设计要求,进一步融入Hash链式表以及Trie树查找算法的设计思想,提出了一种可配置的路由查找算法.通过动态配置算法中的评价函数系数,该算法可以适用于多种网络应用环境.     

Resource-Cardinality Based Scheme to Reduce Resource Lookup Cost in Structured P2P Networks

A P2P (peer-to-peer) network is a distributed system dependent on the IP-based networks, where independent nodes join and leave the network at their drive. The files (resource) are shared in distributed manner and each participating node ought to share its resources. Some files in P2P networks are accessed frequently by many users and such files are called popular files. Replication of popular files at different nodes in structured P2P networks provides significant reduction in resource lookup cost. Most of the schemes for resource access in the structured P2P networks are governed by DHT (Distributed Hash Table) or DHT-based protocols like Chord. Chord protocol is well accepted protocol among structured P2P networks due to its simple notion and robust characteristics. But Chord or other resource access protocols in structured P2P networks do not consider the cardinality of replicated files to enhance the lookup performance of replicated files. In this paper, we have exploited the cardinality of the replicated files and proposed a resource cardinality-based scheme to enhance the resource lookup performance in the structured P2P networks. We have also proposed the notion of trustworthiness factor to judge the reliability of a donor node. The analytical modelling and simulation analysis indicate that the proposed scheme performs better than the existing Chord and PCache protocols.

     

星上路由查找的设计与分析

星上路由器是构建下一代全球信息网络的重要节点设备,路由查找是影响数据转发性能的关键技术之一。考虑到空间环境对设备在可靠性、重量和功耗等因素的限制,该文通过分析比较多种路由查找算法,根据软硬件协同设计的思想,给出了适合星上硬件路由查找的设计与分析。