分层P2P管理网的端到端路由优化

P2P技术的出现对于互联网的管理是一个挑战,但同时也给管理网络的构建带来了新的思路.本文讨论在一个基于P2P技术构建的分层管理网络中,如何实现端到端的路由优化.基于分层结构的重叠网,论文根据业务的不同需要,采用分布式多个节点协同建立端到端的路由,实现相关业务的路由优化机制,为终端用户提供近优的路径选择.仿真实验表明,该方案能够规划出较为理想的端到端路径.     

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.     

一种基于P2P网络的层次化覆盖多播模型

P2P网络的应用日益广泛,但是针对网络中各个终端主机网络接口带宽各异的实际情况,目前的覆盖多播模型没有综合考虑节点的延迟和实际可用带宽的限制。针对上述问题,提出了一种基于P2P网络的层次化覆盖多播模型(HOMM),该模型综合考虑了延迟和带宽两种因素,采用优先度作为构建ALM树的标准,在簇内构建局部ALM树,同时节点的加入、失效等操作的影响只局限于较小的局部范围内,使整个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.     

时延和时延差别受限的最大带宽多播路由分布式算法

本文采用反映网络实时特性的可用带宽代替代价作为第一度量，提出一种基于最大可用带宽路径且满足时延和时延差别约束的QoS实时多播路由分布式启发算法，该算法具有多项式复杂性，并通过分析得到每路径时延和二约束度量之间的关系，有效降低涉及时延和时延差别此类问题的复杂性。仿真实验证明，该算法具有较好的带宽性能。     

QoS多播路由算法研究

随着当前Intemet的发展和各种多媒体应用的出现,多播技术得到大量应用。多播路由算法主要用来建立一棵性能良好的多播树,并使它能够满足各种业务的服务质量需求。将多种群并行技术和退火技术相结合,克服了基于标准遗传算法的多播路由算法过早收敛和后期搜索速度较慢的缺陷,且使用树状编码方法,提出求解带宽、时延、时延抖动和分组丢失率约束的代价最小多播树的多种群并行退火遗传多播路由算法。对QoS多播路由选择问题进行了描述,给出多种群并行退火多播路由遗传算法和一种有效去除冗余信息的遗传算法编码设计技术,通过仿真实验证明了算法的正确性,分析了算法的时间性能,表明该算法快速有效。     

一种链路不相交的多约束QoS路由算法

为提高网络路由可靠性,改善网络资源利用率,提出一种满足多个QoS约束的基于链路保护机制的路由算法.该算法首先通过图论的有关性质找到满足给定约束条件的节点对间的全部路径,并在此基础上利用邻接矩阵的方法得到其最短链路不相交相似路径,最后赋以算例分析.结果证明,该算法在减小网路传输时延方面有一定的优势,对于高实时性网络应用有更好的优化作用.     

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.     

Analysis of large scale traceroute datasets in Internet routing overlays by parallel computation

The creation of a routing overlay network on the Internet requires the identification of shorter detour paths between end hosts in comparison to the default path available. These detour paths are typically the edges forming a Triangle Inequality Violation (TIV), an artifact of the Internet delay space where the sum of latencies across an intermediate hop is lesser than the direct latency between the pair of end hosts. These violations are caused mainly due to interdomain routing policies between Autonomous Systems (ASes) and AS peering through Internet eXchange Points (IXPs). Identifying detours for a global overlay network requires large amounts of computational capabilities due to the sheer number of possible paths linking source and destination ASes. In this work, we use parallel programming paradigms to exploit the massively parallel capabilities of analyzing the large network measurement datasets made available to the network research community by CAIDA. We study Internet routes traversing IXPs and measure potential TIVs created by these paths. Large scale analysis of the dataset is carried out by implementing an efficient parallel solution on the CPU and then the general purpose graphics processor unit (GPGPU) as well. Both multicore CPU and GPGPU implementations can be carried out with ease on desktop environments with readily available software. We find both parallel solutions yield high improvements in speedup (2-35x) in comparison to the serial methodologies thereby opening up the possibility of harnessing the power of parallel programming with readily available hardware. The large amount of data analyzed and studied helps draw various inferences for the networking research community in building future scalable Internet routing overlays with greater routing efficiencies.     

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.     

Optimizing content-based routers: posets and forests

Event-based systems are seen as good candidates for supporting distributed applications in dynamic and ubiquitous environments because they support decoupled and asynchronous one-to-many and many-to-many information dissemination. Event systems are widely used because asynchronous messaging provides a flexible alternative to RPC. They are typically implemented using an overlay network of routers. A content-based router forwards event messages based on filters that are installed by subscribers and other routers. This paper addresses the optimization of content-based routing tables organized using the covering relation and presents novel configurations for improving local and distributed operation. We present the poset-derived forest data structure and variants that perform considerably better under frequent filter additions and removals than existing data structures. The results offer a significant performance increase to currently known covering-based routing mechanisms. Sasu Tarkoma received his M.Sc. and Ph.Lic degrees in Computer Science from the University of Helsinki, Department of Computer Science. He has over 20 scientific publications and has also contributed to several books on mobile middleware. His research interests include distributed computing and middleware. Jaakko Kangasharju is a PhD student at the University of Helsinki and working as a researcher at the Helsinki Institute for Information Technology. His research is concentrated on XML messaging and processing in the mobile wireless environment. He has participated in related standardization efforts at the Object Management Group and the World Wide Web Consortium.     

改善多媒体通信质量的覆盖层路由系统

针对近年来互联网上迅速兴起的多媒体通信应用,分析和指出了当前互联网网络层路由不适于传输多媒体数据的内在缺陷,为改善多媒体通信质量,设计并实现了一个名为CORS的覆盖层路由系统,通过构建和使用多条覆盖层路径来突破网络层单路径路由的局限性,并提供应用感知的传输层服务。利用在全球网络实验平台——PlanetLab上的真实实验验证了CORS的有效性。     

一种基于时延的高效Koorde模型

Koorde是一种新型的分布式哈希表(DHT),但它所选取的路由机制有待改进,而且在构造覆盖网络时没有考虑底层网络拓扑的信息。从减少路由跳数和降低网络时延两个方面来对原路由协议进行改进,进而实现了一种更加高效的koorde路由模型。实验表明,改进后模型的路由跳转比和时延系数两项性能指标得到了提升。     

Efficient techniques and tools for intra‐domain traffic engineering

Intra‐domain routing protocols are based on Shortest Path First (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre‐assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing costs subject to the traffic demands and the protocol constraints. However, determining a link weight combination that meets a network operator's objectives is a difficult task. In this paper, we study the link weight optimization problem in intra‐domain networks. This problem is proved to be NP‐hard with hard protocol constraints, e.g., a flow is evenly distributed along the shortest paths between its origin and destination nodes. We present two fast heuristic approaches to generate efficient link metrics for intra‐domain routing. Some promising experimental results are reported.     

Semi-Fluid content distribution model for fast data dissemination in heterogeneous overlay networks

Overlay networks and peer-to-peer networking have emerged as alternative solutions to solve many problems related to massive information distribution and processing tasks by providing enhanced services in the application layer. For instance, overlay networks can improve data dissemination in P2P file sharing overlays and Content Distribution Networks (CDNs). In such overlay networks, delay is considered as a critical performance metric. A viable content distribution model could considerably minimize the completion time and would lead to efficient utilization of resources such as network bandwidth. The main objective of this paper is to design a new flexible content distribution model for fast data dissemination in overlay networks with heterogeneous nodes. The proposed “Semi-Fluid” content distribution model is a hybrid model that enables fast data dissemination in overlay networks by combining Chunk and Fluid content distribution models. In this new content distribution model, the chunk content is distributed into heterogeneous overlay nodes in a fluid manner. The proposed hybrid content distribution model eliminates both a backpressure problem caused by the Fluid content distribution model, as well as a chunk transition delay caused by the Chunk content distribution model. The performance of the proposed Semi-Fluid content distribution model has been evaluated by mathematical analysis as well as by real implementation over the “PlanetLab” platform, and the obtained results show that the Semi-Fluid content distribution model efficiently reduces the total download time of the clients. Hence, the Semi-Fluid content distribution model can be deployed as a promising solution for fast data dissemination in heterogeneous overlay networks.     

多跳无线网络跨层协作式路由协议实现和性能分析

为了提高多跳无线网络的带宽利用率, 引入了辅助节点来帮助其他链路进行数据传输并重新定义了协作式路由的概念。在此基础上, 提出了协作式路由算法, 并且在实际平台上进行了实验。结果表明, 协作式路由能够显著提高网络传输带宽。     

SKoorde:一种基于de Bruijn图的高效P2P模型

Koorde是一种常数度分布式哈希表（DHT）,但它的定位策略有待改进以减少逻辑路由跳数,而且它存在着逻辑拓扑和物理拓扑失配的问题。在定位过程中采用最短路径路由策略以减少定位跳数．同时提出一种利用IP地址的特性来增强拓扑一致性的路由模型SKoorde。实验仿真表明,SKoorde的平均查询率和平均跳转比两项指标均优于改进前的Koorde,能够较好地提高路由效率。     

基于流媒体服务的覆盖网络多路路由方案

本文提出一种基于流媒体服务的覆盖网络多路路由方案（SSONM）。本方案考虑了备选路径与主路径的关系,路径之间相交比较小,数据流出现拥塞的可能就比较小,提高了 网络的性能和利用率。SSONM结合物理网络找出最短路径作为主路径,并计算其他路径与主路径之间的相关率,在进行多路选择时按照相关率从小到大顺序选择多路路径。该方案是一种简单可行的覆盖网络QoS多路选择策略,可以达到较少的包丢失率和较高的QoS请求满足率,可以很好地满足流媒体服务。     

基于DSR协议的备用路由机制设计和性能评价

由于Adhoc网络中无线节点的移动性及无线信道的不稳定性,已经建立起来的源和目的节点间的路由在多媒体业务传输过程中往往会失效,重新发现路由会导致较大延迟和丢包,对实时多媒体业务传输这是不能接受的,因此需要在Adhoc网络中建立一种快速路由恢复机制以减少因路由失效引起的较大端到端的延迟和丢包。将有线网络中广泛使用的备用路由机制扩充到了无线Adhoc网络DSR路由协议上,并通过实验床上进行的户外实验,分析和评价了增加了备用路由的DSR协议在减少路由失效次数和投递率方面的性能改善。