Replica-aided load balancing in overlay networks

In recent years, there have been rapid advances in network infrastructure and technologies for end-user communication. However, because of network dynamics and resource limitation, providing scalable end-user communication services is challenging when the applications are utilized on a large-scale. To address this challenge, a replica-aided load balancing scheme (RALB) is proposed for enabling the nodes in an overlay networks to support the communication applications for a large number of users. This paper makes three unique contributions. First, we study the existing load balancing schemes and identify their weakness in handling time-varying workloads with frequent load fluctuations. Second, we introduce a sophisticated cost model for load balancing cost estimation, which captures the dependencies between the factors (e.g., the load, message number, and link latency). Third, we propose a performance tuning technique to minimize the load balancing cost. The extensive experiments show that RALB effectively reduces the load imbalance and eliminates the load balancing cost when compared to the existing load balancing schemes.     

A new and effective hierarchical overlay structure for Peer-to-Peer networks

The tremendous growth of public interest in Peer-to-Peer (P2P) networks in recent years has initiated a lot of research work on how to design efficient overlay structures for P2P systems. Scalable overlay networks such as Chord, CAN, Pastry, and Tapestry provide no control over where data is stored and the location of the peers and resources is determined by the hash values of their identifiers and keys respectively. As a result, these overlays cannot support range queries and other proximity-aware complex queries directly.In this paper, we present a hierarchical P2P overlay network called SkipCluster, which is capable of supporting both exact-match and multi-dimensional range queries efficiently without consumption of extra memory space. SkipCluster is derived from skip graphs and SkipNet, but it has a two-tier hierarchical architecture.In both tiers, peers are connected in sequence according to the order of their peer IDs, and related resources are stored near each other without hashing of their resource keys. We design a novel data structure called Triple Linked List (TLL) to store each super-peer’s pointers in the higher tier, which can be used to find the longest prefix and speed up query routing of inter-cluster. In the lower tier, each intra-cluster peer’s routing table contains pointers with exponentially incremental distance. Experimental results show that SkipCluster can speed up both exact-match and range queries in different network sizes.     

基于语言分类的P2P覆盖网络

基于Web语言分布和P2P中共享信息的特点,提出了一个基于语言类别的P2P覆盖网络。该方法通过对节点共享信息的语言进行识别,将节点根据不同的语言类别进行组织,查询时对查询问题进行同样的分类,并在对应语言类别中进行查找。仿真表明,该方法有效地提高了不同语言用户的查询成功率,同时便于已有语义分析技术在P2P网络中的进一步应用。     

Multicast tree rearrangement to recover node failures in overlay multicast networks

Overlay multicast makes use of the Internet as a low level infrastructure to provide multicast service to end hosts. The strategy of overlay multicast slides over most of the basic deployment issues associated with IP multicast, such as end-to-end reliability, flow and congestion control, and assignment of an unique address for each multicasting group.     

Counteracting free riding in Peer-to-Peer networks

The existence of a high degree of free riding is a serious threat to Peer-to-Peer (P2P) networks. In this paper, we propose a distributed framework to reduce the adverse effects of free riding on P2P networks. Our solution primarily focuses on locating free riders and taking actions against them. We propose a framework in which each peer monitors its neighbors, decides if they are free riders, and takes appropriate actions. Unlike other proposals against free riding, our framework does not require any permanent identification of peers or security infrastructures for maintaining a global reputation system. Our simulation results show that the framework can reduce the effects of free riding and can therefore increase the performance of a P2P network.     

Predictable service overlay networks: Predictability through adaptive monitoring and efficient overlay construction and management

Providing bounded communication among participating nodes is significant for distributed systems. Internet-based applications suffer with lower performance due to absence of bounded latency. We describe PSON, an overlay network solution to this challenging problem. PSON has two components. The monitoring component, SyncProbe, utilizes efficient and adaptive monitoring techniques to measure latency, detect packet loss, and provide real-time estimates of maximum expected latency along paths of an Internet substrate. The QoSMap component constructs and manages overlay such that it yields application-level QoS and provides resilience against network failures. A distinctive feature of QoSMap is construction of QoS-compliant backup paths which facilitate in overlay management and operation during the period when primary overlay paths violate QoS. We evaluate PSON on PlanetLab to provide predictable communication for applications with different topology and QoS requirement. Our experiments confirm the effectiveness of PSON in providing an inexpensive and efficient application-layer solution to Internet’s unpredictable behavior.     

Technology challenges for virtual overlay networks

An emerging generation of mission-critical networked applications is placing demands on the Internet protocol suite that go well beyond the properties they were designed to guarantee. Although the “next generation internet” (NGI) is intended to respond to the need, when we review such applications in light of the expected functionality of the NGI, it becomes apparent that the NGI will be faster but not more robust. We propose a new kind of virtual overlay network (VON) that overcomes this deficiency and can be constructed using only simple extensions of existing network technology. In this paper, we use the restructured electric power grid to illustrate the issues, and elaborate on the technical implications of our proposal     

Increasing QoS in selfish overlay networks

A routing overlay network is an application-layer overlay on the existing Internet routing substrate that allows an alternative routing service. Recent studies have suggested that such networks might contain selfish nodes, which develop their strategies by considering only their own objectives. Extremely selfish nodes, called free-riders, might even refuse to share their resources with the network, thus making overlay service unavailable to the nodes that depend on them. The authors use a game-theoretic approach to evaluate the selfish-node mechanism and increase quality of service (QoS) by detecting and excluding free-riders.     

Rewiring strategies for semantic overlay networks

Semantic overlay networks cluster peers that are semantically, thematically or socially close into groups, by means of a rewiring procedure that is periodically executed by each peer. This procedure establishes new connections to similar peers and disregards connections to peers that are dissimilar. Retrieval effectiveness is then improved by exploiting this information at query time (as queries may address clusters of similar peers). Although all systems based on semantic overlay networks apply some rewiring technique, there is no comprehensive study showing the effect of rewiring on system’s performance. In this work, a framework for studying the attribution of rewiring strategies in semantic overlay networks is proposed. A generic approach to rewiring is presented and several variants of this approach are reviewed and evaluated. We show how peer organisation is affected by the different design choices of the rewiring mechanism and how these choices affect the performance of the system overall (both in terms of communication overhead and retrieval effectiveness). Our experimental evaluation with real-word data and queries confirms the dependence between rewiring strategies and retrieval performance, and gives insights on the trade-offs involved in the selection of a rewiring strategy.     

一种半全局化的P2P信誉度模型

提出了一种新颖的信誉管理机制,首先给出了一套客观的信誉跟踪评价标准,然后根据各个节点的能力与行为表现将它们划分成两类：信誉值和能力均很出众的精英节点,一般的或新加入系统的普通节点。精英节点享有一定特权并组成结构化的网络,普通节点组成无结构的网络。接着用一种半全局化的方法来计算和存储各节点的信誉值。最后,通过实验证明此机制的有效性和健壮性。     

Hierarchical architectures in structured peer-to-peer overlay networks

Distributed Hash Tables (DHT) are presently used in several large-scale systems in the Internet and envisaged as a key mechanism to provide identifier-locator separation for mobile hosts in Future Internet. Such P2P-based systems become increasingly complex serving popular social networking, resource sharing applications, and Internet-scale infrastructures. Hierarchy is a standard mechanism for coping with heterogeneity and scalability 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 article discusses hierarchical architectures applied in structured P2P overlay networks, focusing on HDHT designs. We introduce a framework consisting of conceptual models of network hierarchy, multi-layer hierarchical DHT architectures, principles affecting the design choices, and cost models for system tradeoff analysis, performance evaluation, and scalability estimation. Based on the framework we provide a taxonomy and survey more than 20 hierarchical HDHT proposals.     

Network load-aware content distribution in overlay networks

Massive content distribution on overlay networks stresses both the server and the network resources because of the large volumes of data, relatively high bandwidth requirement, and many concurrent clients. While the server limitation can be circumvented by replicating the data at more nodes, the network limitation is far less easy to cope with, due to the difficulty in determining the cause and location of congestion and in provisioning extra resources. In this paper, we present novel schemes for massive content distribution, that assign the clients to appropriate servers, so that the network load is reduced and also well balanced, and the network resource consumption is low. Our schemes allow scaling to very large system because the algorithms are very efficient and do not require network measurement, or topology or routing information. The core problems are formulated as partitioning the clients into disjoint subsets according to the degree of interference criterion, which reflects network resource usage and the interference among the concurrent connections. We prove that these problems are NP-complete, and present heuristic algorithms for them. Through simulation, we show that the algorithms are simple yet effective in achieving the design goals.     

Capacity-aware multicast algorithms on heterogeneous overlay networks

The global deployment of IP multicast has been slow due to the difficulties related to heterogeneity, scalability, manageability, and lack of a robust interdomain multicast routing protocol. Application-level multicast becomes a promising alternative. Many overlay multicast systems have been proposed in recent years. However, they are insufficient in supporting applications that require any-source multicast with varied host capacities and dynamic membership. In this paper, we propose two capacity-aware multicast systems that focus on host heterogeneity, any source multicast, dynamic membership, and scalability. We extend Chord and Koorde to be capacity-aware. We then embed implicit degree-varying multicast trees on top of the overlay network and develop multicast routines that automatically follow the trees to disseminate multicast messages. The implicit trees are well balanced with the workload evenly spread across the network. We rigorously analyze the expected performance of multisource capacity-aware multicasting, which was not thoroughly addressed in any previous work. We also perform extensive simulations to evaluate the proposed multicast systems.     

SocialVPN: Enabling wide-area collaboration with integrated social and overlay networks

Trusted collaborative systems require peers to be able to communicate over private, authenticated end-to-end channels. Network-layer approaches such as Virtual Private Networks (VPNs) exist, but require considerable setup and management which hinder the establishment of ad-hoc collaborative environments: trust needs to be established, cryptographic keys need to be exchanged, and private network tunnels need to be created and maintained among end users. In this paper, we propose a novel system architecture which leverages existing social infrastructures to enable ad-hoc VPNs which are self-configuring, self-managing, yet maintain security amongst trusted and untrusted third parties. The key principles of our approach are: (1) self-configuring virtual network overlays enable seamless bi-directional IP-layer connectivity to socially connected parties; (2) online social networking relationships facilitate the establishment of trust relationships among peers; and (3) both centralized and decentralized databases of social network relationships can be securely integrated into existing public-key cryptography (PKI) implementations to authenticate and encrypt end-to-end traffic flows. The main contribution of this paper is a new peer-to-peer overlay architecture that securely and autonomously creates VPN tunnels connecting social peers, where online identities and social networking relationships may be obtained from centralized infrastructures, or managed in a decentralized fashion by the peers themselves.This paper also reports on the design and performance of a prototype implementation that embodies the SocialVPN architecture. The SocialVPN router builds upon IP-over-P2P (IPOP) virtual networks and a PKI-based tunneling infrastructure, which integrates with both centralized and decentralized social networking systems including Facebook, the Drupal open-source content management system, and emailing systems with PGP support. We demonstrate our prototype’s ability to support existing, unmodified TCP/IP applications while transparently dealing with user connectivity behind Network Address Translators (NATs). We also present qualitative and quantitative analyses of functionality and performance based on wide-area network experiments using PlanetLab and Amazon EC2.     

包含关联的语义覆盖网构建方法研究

现实世界中信息资源之间存在着各种各样的关联关系,而当前的搜索引擎只能提供基于关键字的搜索,不能为用户提供他们所关心的与关键字相关的各类信息。针对这个问题,提出了构建语义覆盖网,以用户需求为导向,以用户所关心的信息为中心,将所有与此资源相关的信息全部汇聚起来提供给用户。这里先根据语义相似度将节点聚类,然后在聚类的基础上,根据各类关联关系构建基于关联关系的语义覆盖网。