Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．     

基于子网的三维Mesh网络容错广播路由算法

在并行计算机系统中,广播通信是极为重要的通信模式之一。该文基于k-Mesh子网(子立方体)连通的概念提出一个基于局部信息和分布式的三维Mesh网络容错广播路由算法。该算法利用邻结点的状态信息,动态地构建以单个k-Mesh子网为结点的广播树,该广播树能容忍相当多的结点出错。模拟结果表明广播路由算法的广播时间步接近最优的。该算法只要求结点知道它的邻结点的状态,而无需知道整个网络状态信息,也就是说,这些算法是基于局部信息的,因而具有很好的实际意义。     

一种基于单播的大规模Mesh网络容错多播路由新算法

本文基于k-Mesh子网连通的概念提出一种基于局部信息和分布式的Mesh网络容错多播路由算法：该算法的基本思想是把大规模的Mesh网络分成若干个较小的子网，多播消息只在各子网间进行路由，并由各子网独立完成操作。该算法的时间复杂性是线性的，模拟结果表明多播路由算法的多播时间步接近网络的直径。     

故障三维Mesh网络中的容错路由

该文在k—Mesh子网连通概念的基础上提出了三维Mesh网络中局部k—Mesh子网弱连通的概念,证明了局部k—Mesh子网弱连通的三维Mesh网络存在全局连通性。基于局部k—Mesh子网弱连通的三维Mesh网络提出了单播、广播容错路由算法。这些算法提高了容错能力且是基于局部信息的,因而具有很好的实际意义。     

故障三维Mesh网络中的容错路由

该文在k—Mesh子网连通概念的基础上提出了三维Mesh网络中局部k—Mesh子网弱连通的概念,证明了局部k—Mesh子网弱连通的三维Mesh网络存在全局连通性。基于局部k—Mesh子网弱连通的三维Mesh网络提出了单播、广播容错路由算法。这些算法提高了容错能力且是基于局部信息的,因而具有很好的实际意义。     

基于子网的E-2DMesh网络容错单播路由算法

基于k-E-2DMesh子网连通概念和局部信息,提出分布式E-2DMesh网络容错单播路由算法。对算法容错性进行概率分析,假设每个节点具有独立的出错概率,推导出路由算法成功返回由正确节点组成路径的概率。推理结果表明,对于规模较大的E-2DMesh网络,当k值为3而节点出错概率小于0．03％时,该算法找到正确节点所组成路径的概率大于等于99％。其具有线性时间复杂性,构造的路由路径长度接近2点间最优路径长度。     

自适应路由算法优于确定性路由算法

在研究并行计算机系统的容错时。自适应路由算法是一个极为重要的研究课题．它是在网络结点出错时，算法通过可选择的路径进行路由．在每个结点具有独立的出错概率的模型下，研究Mesh网络上自适应路由算法和确定性路算法的性能．本文提出的技术使得我们能严格地推导出路由算法的成功的概率，从而能分析和比较算法的性能．研究结果表明自适应路由算法具有明显的优势：一方面确定性路算法需要全局错误信息而变得高效性，另一方面自适应路由算法对于结点出错和网络规模具有更好的健壮性而具有更高的成功概率．     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

基于结点出错概率的Mesh网络容错性分析

在并行计算机系统中,Mesh网络是最重要的网络拓扑结构之一。该文研究了基于结点出错概率Mesh网络的连通性,提出了k-Mesh子网连通的概念,运用严格的数学推理,推导出网络结点出错概率和Mesh网络的连通概率之间的关系。研究表明:特定的Mesh网络能保持相当高的连通概率,例如,笔者严格证明了,当网络结点出错概率控制在0.1%以下,则对多达几十万个结点的Mesh网络,网络连通的概率仍可保持在99%以上。     

在3D-Mesh网络中的两种路由研究

在研究并行计算机系统容错时,路由算法是一个极为重要的研究课题。主要研究的是自适应路由算法和确定性路由算法在3D-Mesh网络上的性能。在每个结点具有独立的出错概率的模型下,提出的方法使得能够严格地推导出路由算法的成功概率,从而能够对算法进行分析和比较。研究结果表明,自适应路由算法具有明显的优势。一方面,自适应路由算法基于局部信息而变得高效;另一方面,自适应路由算法对于结点出错和网络规模具有更好的健壮性,而使其具有更高的成功概率。     

点对点网络容错路由算法的概率分析

基于网络中结点错误概率 ,提出一种新的概率分析方法 ,对网络中点对点的路由算法的容错性概率、路径长度、算法复杂性进行严格的推导 .以超立方体网络为分析的网络拓扑 ,提出在其上的一个路由算法 .分析表明 :在所有实际规模的超立方体网络中 (其结点数可以高达十亿个 ) ,在相当大的结点出错概率 (可高达 8% )的情况下 ,路由算法可达到 99.9%的成功概率     

Stability routing with constrained path length for improved routability in dynamic MANETs

Quality of service (QoS) routing is known to be an NP-hard problem in case of two or more additive constraints, and several exact algorithms and heuristics have been proposed to address this issue. In this paper, we consider a particular two-constrained quality of service routing problem maximizing path stability with a limited path length in the quest of improving routability in dynamic multi-hop mobile wireless ad hoc networks. First, we propose a novel exact algorithm to solve the optimal weight-constrained path problem. We instantiate our algorithm to solve the most stable path not exceeding a certain number of hops, in polynomial time. This algorithm is then applied to the practical case of proactive routing in dynamic multi-hop wireless ad hoc networks. In these networks, an adequate compromise between route stability and its length in hops is essential for appropriately mitigating the impact of the network dynamics on the validity of established routes. Secondly, we set up a common framework for the comparison between three families of proactive routing: the shortest path-based routing, the most stable path-based routing and our proposed most stable constrained path routing. We show then through extensive simulations that routing based on our proposed algorithm selects appropriate stable paths yielding a very high routability with an average path length just above that of the shortest paths.     

点对点网络容错路由算法的路径长度分析

用概率性分析方法 ,研究了在结点错误概率性分布的情形下超立方体网络点对点容错路由算法的路径长度 ,得出了算法的路径长度期望值 ,分析表明 :对于结点错误概率 p≤ 10时 ,源点 U到终点 V所在的 k维子立方体的路径长度期望值不超过 1.11* h,比以往通常的长度分析结果 2 * h小得多 .提出一种改进的算法并证明这一新算法所构造的路径长度的期望值不大于 1.11h- 0 .11k 2 ,这大大改进了以前的路径 2 h k 2 ,其中 h为 U与 V的 Ham ming距离 .     

基于最优Path的Ad Hoc网络地理路由算法

对基于地理信息的自组网路由中的凹节点问题做了分析,并提出了一种新的解决方案——PGA算法及其改进算法.算法采用了最优Path的思想,在Path构造、基于Path的最优寻路、路由恢复等多个方面都应用了最优Path的概念,较好地解决了凹节点的问题.通过证明,该算法具有无环性,从而实现了基于局部路由信息的无状态路由,展示了算法的可扩展性和易维护性.实验表明,即使在大型网络中,算法依然可以保持很高的报文投递率、较短的路径长度、可接受的路由表大小及可控的协议带宽开销,同时该路由算法在动态环境中具有较强的鲁棒性.     

针对无标度网络的紧凑路由方法

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.     

针对无标度网络的紧凑路由方法

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.     

Complexity and design of QoS routing algorithms in wireless mesh networks

Quality of service (QoS) provisioning in wireless mesh networks (WMNs) is an open issue to support emerging multimedia services. In this paper, we study the problem of QoS provisioning in terms of end-to-end bandwidth allocation in WMNs. It is challenging due to interferences in the networks. We consider widely used interference models and show that except a few special cases, the problem of finding a feasible path is NP-complete under the models. We propose a k-shortest path based algorithmic framework to solve this problem. We also consider the problem of optimizing network performance by on-line dynamic routing, and adapt commonly used conventional QoS routing metrics to be used in WMNs. We find the optimal solutions for these problems through formulating them as optimization models. A model is developed to check the existence of a feasible path and another to find the optimal path for a demand; moreover, an on-line optimal QoS routing algorithm is developed. Comparing the algorithms implemented by the proposed framework with the optimization models shows that our solution can find existing feasible paths with high probability, efficiently optimizes path lengths, and has a comparable performance to the optimal QoS routing algorithm. Furthermore, our results show that contrary to wireline networks, minimizing resource consumption should be preferred over load distribution even in lightly loaded WMNs.     

Nearly optimal one-to-many parallel routing in star networks

Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and the running time of our algorithm is bounded by O(n²). More specifically, given a node s and n-1 other nodes {t₁, t₂ , …, t_n-1} in the n-star network, our algorithm constructs n-1 node-disjoint paths P₁, P₂, …, P_n-1, where P_i is a path from s to t_j of length at most dist(s, t_j)+6 and dist(s, t _j) is the distance, i.e., the length of a shortest path, from s to t_j, for i=1, 2, …, n-1.The best bound on the path length by previously known algorithms for the same problem is 5(n-2)≈10Δ_n/3, where Δ_n=max{dist(s, t)} is the diameter of the n-star network