BLOR: An efficient bandwidth and latency sensitive overlay routing approach for flash data dissemination

The problem of flash data dissemination refers to transmitting time‐critical data to a large group of distributed receivers in a timely manner, which widely exists in many mission‐critical applications and Web services. However, existing approaches for flash data dissemination fail to ensure the timely and efficient transmission, because of the unpredictability of the dissemination process. Overlay routing has been widely used as an efficient routing primitive for providing better end‐to‐end routing quality by detouring inefficient routing paths in the real networks. To improve the predictability of the flash data dissemination process, we propose a bandwidth and latency sensitive overlay routing approach named BLOR, by optimizing the overlay routing and avoiding inefficient paths in flash data dissemination. BLOR tries to select optimal routing paths in terms of network latency, bandwidth capacity, and available bandwidth in nature, which has never been studied before. Additionally, a location‐aware unstructured overlay topology construction algorithm, an unbiased top‐k dominance model, and an efficient semi‐distributed information management strategy are proposed to assist the routing optimization of BLOR. Extensive experiments have been conducted to verify the effectiveness and efficiency of the proposals with real‐world data sets. Copyright © 2014 John Wiley & Sons, Ltd.     

Scheduling algorithms for conducting conflict-free measurements in overlay networks

Network monitoring is essential to the correct and efficient operation of ISP networks and the kind of applications they support, and active measurement is a key design problem in network monitoring. Unfortunately, almost all active probing algorithms ignore the measurement conflict problem: Active measurements conflict with each other – due to the nature of these measurements, the associated overhead, and the network topology – which leads to reporting incorrect results. In this paper, we consider the problem of scheduling periodic QoS measurement tasks in overlay networks. We first show that this problem is NP-hard, and then propose two conflict-aware scheduling algorithms for uniform and non-uniform tasks whose goal is to maximize the number of measurement tasks that can run concurrently, based on a well-known approximation algorithm. We incorporate topological information to devise a topology-aware scheduling algorithm that reduces the number of time slots required to produce a feasible measurement schedule. Also, we study the conflict-causing overlap among overlay paths using various real-life Internet topologies of the two major service carriers in the US. Experiments conducted using the PlanetLab testbed confirm that measurement conflict is a real issue that needs to be addressed. Simulation results show that our algorithms achieve at least 25% better schedulability over an existing algorithm. Finally, we discuss various practical considerations, and identify several interesting research problems in this context.     

Enhancing end-to-end availability and performance via topology-aware overlay networks

This paper proposes a novel overlay architecture to improve availability and performance of end-to-end communication over the Internet. Connectivity and network availability are becoming business-critical resources as the Internet is increasingly utilized as a business necessity. For example, traditional voice and military systems are turning into IP-based network applications. With these applications, even short-lived failures of the Internet infrastructure can generate significant losses.To satisfy these needs, the concept of overlay networks has been widely discussed. However, in the previous studies of overlay networks, a measurable number of path outages were still unavoidable even with use of such overlay networks. We believe that an overlay network’s ability to quickly recover from path outages and congestion is limited unless we ensure path independence at the IP layer. Hence, we develop a simple but effective overlay architecture increasing path independence without degrading performance. The proposed overlay architecture enhances prior studies in the following ways: (1) we deploy overlay nodes considering topology and latency information inside an ISP and also across ISP boundaries; (2) we use a source-based single-hop overlay routing combined with the above topology-aware node deployment; (3) we increase the usage of multi-homing environment at endhosts. In this framework, we develop measurement-based heuristics using extensive data collection from 232 points in 10 ISPs, and 100 PlanetLab nodes. We also validate the proposed framework using real Internet outages to show that our architecture is able to provide a significant amount of resilience to real-world failures.     

On investigating overlay service topologies

Recently, a moderate amount of work has been reported on the use of overlay networks to support value-added network services, such as multicasting, Quality-of-Service (QoS), security, etc. To design an overlay network, the first step is to choose an overlay topology connecting all the overlay service nodes. When considering overlay topologies, several questions need to be answered first: How overlay topologies affect overlay routing performance? Which topologies can provide satisfactory performance? How can we construct efficient overlay topologies connecting all the overlay nodes?In this paper, we focus on the overlay network topology construction issue. First, we evaluate and compare the performance and overhead of the existing overlay topologies. Second, we formalize the overlay topology construction problem and propose two new heuristic methods to construct efficient overlay topologies. Simulation results have demonstrated the efficiency of the two proposed approaches. It is shown that overlay service performance varies significantly with respect to different overlay topologies. Thus, it is important to choose an appropriate overlay network topology. The knowledge of IP-layer topology information also benefits significantly in constructing efficient overlay topologies as inferred from the results.     

SPAD: A distributed middleware architecture for QoS enhanced alternate path discovery

In the next generation Internet, the network will evolve from a plain communication medium into one that provides endless services to the users. These services will be composed of multiple cooperative distributed application elements. We name these services overlay applications. The cooperative application elements within an overlay application will build a dynamic communication mesh, namely an overlay association. The Quality of Service (QoS) perceived by the users of an overlay application greatly depends on the QoS experienced on the communication paths of the corresponding overlay association. In this paper, we present super-peer alternate path discovery (SPAD), a distributed middleware architecture that aims at providing enhanced QoS between end-points within an overlay association. To achieve this goal, SPAD provides a complete scheme to discover and utilize composite alternate end-to-end paths with better QoS than the path given by the default IP routing mechanisms.     

非结构化P2P覆盖网络通信协议研究

针对各种基于流言机制的通信协议在构造非结构化P2P覆盖网络中,其适用范围缺乏广泛的实证问题,提出了一个通用的协议框架——基于流言机制的节点采样服务,以执行高效和可靠的节点采样服务。在这种协议框架下通过实验分析了8种通信协议的差异。实验表明,采用不同的通信协议,所构造的非结构化P2P覆盖网络就表现出多种不同的行为特性,为构造非结构化P2P覆盖网络中选取通信协议提供了重要的参考依据。     

An optimal inherently stabilizing routing algorithm for star P2P overlay networks

Star graphs possess many desirable properties such as scalable node degrees and diameters, which are essential to facilitate reduced routing table sizes and low maximum path length for routing in large P2P networks. In addition, because a large number of disjoint paths are available and each data/replica in an n‐star can be placed in an (n − 1)‐star, load balancing and alleviation of network bottlenecks can be implemented in star P2P overlay networks. Therefore, star networks have been proposed as viable alternatives to existing overlay topologies for large P2P networks. In this paper, we propose an optimal stabilizing and inherently stabilizing algorithm for routing messages over all disjoint paths between two peers in a star P2P overlay network. The algorithm is optimal in terms of its time complexity in rounds and the length of the longest path traversed by the messages, and fault tolerant due to being stabilizing and inherently stabilizing, allowing the system to withstand transient faults. The algorithm can be used to increase network reliability and survivability in P2P networks. In addition, the usage of all disjoint paths to route messages between two peers leads to increased network bandwidth while distributing the communication overhead across the network and eliminating network bottlenecks in P2P networks. Copyright © 2016 John Wiley & Sons, Ltd.     

GMAC: An overlay multicast network for mobile agent platforms

The lack of proper support for multicast services in the Internet has hindered the widespread use of applications that rely on group communication services such as mobile software agents. Although they do not require high bandwidth or heavy traffic, these types of applications need to cooperate in a scalable, fair and decentralized way. This paper presents GMAC, an overlay network that implements all multicast related functionality–including membership management and packet forwarding–in the end systems. GMAC introduces a new approach for providing multicast services for mobile agent platforms in a decentralized way, where group members cooperate in a fair way, minimize the protocol overhead, thus achieving great scalability. Simulations comparing GMAC with other approaches, in aspects such as end-to-end group propagation delay, group latency, group bandwidth, protocol overhead, resource utilization and failure recovery, show that GMAC is a scalable and robust solution to provide multicast services in a decentralized way to mobile software agent platforms with requirements similar to MoviLog.     

A novel hybrid immune-based GA for dynamic routing to multiple destinations for overlay networks

Overlay networks play an important role in group communication applications in Internet. These applications require better efficiency in terms of delay, cost and load balancing. This paper presents an artificial immune system (AIS)-based hybrid genetic algorithm for the construction of Quality of Service (QoS) multicast tree among multicast service nodes in overlay network which optimizes path delivery, load-balancing variance and cost under bounded delay–degree constraint. This paper proposes an alternative AIS-based approach to handle the constraints instead of penalty function in overlay multicast routing problem. The clonal selection method of AIS is incorporated into the genetic algorithm (GA) to improve the diversity–convergence relationship which leads to optimized results. Proposed algorithm has the following features: (1) embedded problem specific local search function along with random point crossover to fine tune the search; (2) AIS principle is used to solve the constraints in GA; (3) clonal selection method to get the optimized results. Adaptable procedure is embedded into algorithm to handle the end user join/end user drop. Non-parametric statistical analysis has performed to show the significant difference among the proposed and existing algorithms. Simulation results reveal that our proposed algorithm produces better results in terms of cost, average path length, user rejection rate and convergence. Statistical analysis is also performed to assure the significance of the differences among the tested algorithms.     

Multi-channel live streaming in service overlay network

Service overlay network (SON) provides an effective means to deploy quality of service (QoS)-guaranteed live streaming over today’s Internet. A major challenge in designing such a network is dealing with resource sharing among multiple channels. To achieve the best overall QoS in SON, we devise a new multi-channel live streaming scheme. First, we propose a multi-tree construction algorithm by infrastructure-based overlay multicast. The algorithm employs pre-allocated session degree constraints in overlay nodes to reserve resources for multiple channels, and constructs multiple trees by considering the total resource utilization of overlay nodes. Second, we propose a tree-aware queue scheduling algorithm to reduce the overlay processing delay in view of the entire overlay network. Scheduling priority is identified to trade off session priority with node location in different trees. From simulation and experimental results, the scheme achieves a differentiated control among different sessions, provides load balancing among overlay nodes, and improves the delay performance on SON.     

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.     

PSON: A scalable P2P file sharing system with efficient complex query support

A desired P2P file sharing system is expected to achieve the following design goals: scalability, routing efficiency and complex query support. In this paper, we propose a powerful P2P file sharing system, PSON, which can satisfy all the three desired properties. PSON is essentially a semantic overlay network of logical nodes. Each logical node represents a cluster of peers that are close to each other. A powerful peer is selected in each cluster to support query routing on the overlay network while the less powerful peers are responsible for the maintenance of shared contents. To facilitate query routing, super peers are organized in form of a balanced binary search tree. By exploiting the concept of semantics, PSON can support complex queries in a scalable and efficient way. In this paper, we present the basic system design such as the semantic overlay construction, query routing and system dynamics. A load balancing scheme is proposed to further enhance the system performance. By simulation experiments, we show that PSON is scalable, efficient and is able to support complex queries.     

Probabilistic and reactive fault diagnosis for dynamic overlay networks

Overlay networks have emerged as a powerful and flexible platform for developing new disruptive network applications. The attractive characteristics of overlay networks such as routing flexibility and overlay topology dynamics bring to overlay fault diagnosis new challenges, which include the dynamical overlay symptom-fault correlation, multi-layer (i.e., underlay vs. overlay) abstraction, and unregulated overlay symptoms. To address these challenges, we propose a novel user-level probabilistic and reactive fault diagnosis technique, called ProFis for overlay networks, which can seamlessly integrate passive and active fault reasoning to develop an optimal fault diagnosis framework. ProFis uses observable overlay symptoms as reported by overlay applications to dynamically correlate overlay symptoms and faults. ProFis diagnoses overlay faults passively and selects optimal actions (i.e., with the least cost) to enhance the passive diagnosis whenever necessary. Our evaluation study shows that ProFis can efficiently (i.e., low latency) and accurately localize the root causes of overlay faults, even when symptom loss rate is high.     

基于主机的跨网段多播系统设计

多播是一种重要的群组通信技术,在许多领域正得到越来越广泛的应用.传统的多播服务由于实现在TCP/IP协议的网络层,跨网段的多播需要路由器的支持.给出了一种基于主机端应用程序的跨网段多播解决方案,在不改变现有网络结构的基础上,为处于不同子网的主机提供了群组通信服务.详细阐述了该解决方案的设计思想以及适用情况.     

Utility maximization for communication networks with multipath routing

In this paper, we study utility maximization problems for communication networks where each user (or class) can have multiple alternative paths through the network. This type of multi-path utility maximization problems appear naturally in several resource allocation problems in communication networks, such as the multi-path flow control problem, the optimal quality-of-service (QoS) routing problem, and the optimal network pricing problem. We develop a distributed solution to this problem that is amenable to online implementation. We analyze the convergence of our algorithm in both continuous-time and discrete-time, and with and without measurement noise. These analyses provide us with guidelines on how to choose the parameters of the algorithm to ensure efficient network control.     

基于Spines覆盖网络的流媒体并行传输研究

以Spines覆盖网络通用平台为基础,对流媒体数据多流并行传输的相关问题进行了研究。简要介绍了Spines网络,根据流媒体实时并行传输的要求,对Spines网络中的相关协议进行了改进,并引入了具有QoS保证的覆盖网络多路路由策略、DHT技术及LEACH协议。     

Inter-domain policy violations in multi-hop overlay routes: Analysis and mitigation

The Internet is a complex structure arising from the interconnection of numerous autonomous systems (AS), each exercising its own administrative policies to reflect the commercial agreements behind the interconnection. However, routing in service overlay networks is quite capable of violating these policies to its advantage. To prevent these violations, we see an impending drive in the current Internet to detect and filter overlay traffic. In this paper, we first present results from a case study overlay network, constructed on top of PlanetLab, that helps us gain insights into the frequency and characteristics of the different inter-domain policy violations. Further, we investigate the impact of two types of overlay traffic filtering that aim to prevent these routing policy violations: blind filtering and policy-aware filtering. We show that such filtering can be detrimental to the performance of overlay routing. We next consider two approaches that allow the overlay network to realize the full advantage of overlay routing in this context. In the first approach, overlay nodes are added so that good overlay paths do not represent inter-domain policy violations. In the second approach, the overlay acquires permits from certain ASes that allow certain policy violations to occur. We develop a single cost-sharing framework that allows the incorporation of both approaches into a single strategy. We formulate and solve an optimization problem that aims to determine how the overlay network should allocate a given budget between paying for additional overlay nodes and paying for permits (transit and exit) to ASes. We illustrate the use of this approach on our case study overlay network and evaluate its performance under varying network characteristics.     

IQ-Paths: Predictably High Performance Data Streams Across Dynamic Network Overlays

Overlay networks are a key vehicle for delivering network and processing resources to high performance applications. For shared networks, however, to consistently deliver such resources at desired levels of performance, overlays must be managed at runtime, based on the continuous assessment and prediction of available distributed resources. Data-intensive applications, for example, must assess, predict, and judiciously use available network paths, and dynamically choose alternate or exploit concurrent paths. Otherwise, they cannot sustain the consistent levels of performance required by tasks like remote data visualization, online program steering, and remote access to high end devices. The multiplicity of data streams occurring in complex scientific workflows or in large-scale distributed collaborations exacerbate this problem, particularly when different streams have different performance requirements. This paper presents IQ-Paths, a set of techniques and their middleware realization that implement self-regulating overlay streams for data-intensive distributed applications. Self-regulation is based on (1) the dynamic and continuous assessment of the quality of each overlay path, (2) the use of online network monitoring and statistical analyses that provide probabilistic guarantees about available path bandwidth, loss rate, and RTT, and (3) self-management, via an efficient packet routing and scheduling algorithm that dynamically schedules data packets to different overlay paths in accordance with their available bandwidths. IQ-Paths offers probabilistic guarantees for application-level specifications of stream utility, based on statistical predictions of available network bandwidth. This affords applications with the ability, for instance, to send control or steering data across overlay paths that offer strong guarantees for future bandwidth vs. across less guaranteed paths. Experimental results presented in this paper use IQ-Paths to better handle the different kinds of data produced by two high performance applications and one multimedia application: (1) a data-driven interactive high performance code with user-defined utility requirements, (2) an adaptive overlay version of the popular Grid-FTP application, and (3) a MPEG-4 Fine-Grained Scalable layered video streaming.     

Network-aware service placement and selection algorithms on large-scale overlay networks

Currently many service providers offer their services on a private and proprietary hard- and software infrastructure. These infrastructures often share many similarities. Hence we believe a generic service management architecture, that allows service providers to offer a large array of different services on a single infrastructure or multiple providers to offer their services cooperatively, would provide many advantages over current silo-based approaches. Additionally, by allowing the distributed service management components to cooperate in a peer-to-peer overlay network, scalability and resilience of the system could be greatly improved.In this paper we propose an optimal algorithm, based on an integer linear programming (ILP) formulation, and several heuristics to support such a generic overlay-based service management architecture. More specifically, we propose algorithms for dynamically allocating server and network resources to a set of services and selecting a suitable service instance for each client. Service instances are placed on a set of servers, taking into account server resource constraints (e.g. CPU and memory). Unlike existing algorithms for this problem, those proposed in this paper also support service level agreements (SLAs), which take the form of Quality of Service demands such as transmission latency constraints and bandwidth requirements. The optimisation goal is to maximise the percentage of satisfied demand (answered requests) and minimise the total number of required overlay servers, while satisfying the SLAs and resource constraints. Additionally, we propose an extension that allows the algorithms to find overlay routing paths to improve the transmission latency for latency-sensitive services.Extensive simulations were performed to evaluate the performance and scalability of the heuristics. They showed that in many cases the heuristics perform close to optimal and they scale well in terms of network size.