基于多路广播树的SDN多路径路由算法

传统的网络使用基于最短路径的单一路径路由,无法有效地利用网络的全部带宽。软件定义网络(Software Defined Networking,SDN)采用中心化的控制平面能方便地实现对路由的精确控制。针对SDN网络下的多路径路由问题,提出了基于多路广播树的路由存储结构及相应的多路径选择算法。该算法根据各路径的可用带宽和时延进行概率分配,优先选择可用带宽大和时延小的路径。实验结果表明,该算法能快速地进行路由,并有效地减小传输时延和增大吞吐率。     

认知无线传感器网络中基于流量的多路径路由

人们对无线传感器网络多路径路由问题的讨论很多,但从流量分配的角度来讨论路由问题相对较少。主要讨论无线传感器网络通过认知无线电租赁有限的频谱资源,从网络流量分配的角度,利用微分博弈模型来解决无线传感器网络多路径路由问题,同时也考虑了多路径路由的稳定性及经济效益问题。通过求微分博弈反馈纳什均衡的解对n条路径进行了动态流量分配,给出了可以提高认知无线传感器网络有效性、稳定性、可靠性及经济效益的多路径路由算法。     

最小割多路径路由算法

在最小割理论基础上提出了最小割多路径(min-cut multi-path,简称MCMP)路由算法,为流量请求选取少量关键路径,并在这些路径间均衡流量,在获得方法易实现性的同时能够有效地控制网络瓶颈链路拥塞通过实际流量数据在北美和欧洲骨干网络中的实验,对比常用的OSPF(open shortest path first)路由算法和模型中的多路径路由算法,MCMP路由算法可降低拥塞链路负载分别达到41％和20％以上.     

一种智能多路径路由及子流分配协同算法

传统单一路径的传输机制难以满足当前以智慧城市为代表的新一代应用对时延、丢包率等网络性能的要求,而现有多路径传输机制在路由算法及子流分配等方面不能根据网络实时状态调整且互相缺乏协同。引入强化学习理论并结合软件定义网络,提出多路径路由及子流分配协同算法。基于Q-learning设计多路径路由算法,并从策略协同角度对其进行改进,实现路由与子流分配的相互协同。在此基础上,通过Q-value的回环消除方法保证路由准确性并提高算法收敛速度。实验结果表明,该算法在网络负载动态变化过程中能实时调整最佳的多路径路由及子流分配协同策略,提高了传输成功率。     

邻居认证的Mesh网络安全多路径路由协议

Mesh网络节点的移动性和数据传输的多跳性,使得路由协议的质量以及安全性成为衡量Mesh网络性能的关键因素,迫切需要一种能适应网络拓扑变化,高效、安全的路由协议。而目前针对Mesh网络的路由协议很少考虑到协议本身的安全性问题。提出了一种基于认证的节点分离安全多路径路由协议,在多路径的建立过程中加入了安全机制。分析表明,该路由算法在提供负载平衡、提高整体吞吐量、增加容错性的基础上能够很好地保证路由协议的安全性,而且多路径之间节点分离能够降低链路断开的概率,为数据传输提供更高的可靠性。     

Ad hoc网络节点不相交多路径距离矢量路由协议

AMR算法是Ad hoc网络计算节点不相交最大路径集合的累积多路径路由机制。针对节点不相交多路径源路由协议MNVP及SMNVP存在的问题,整合按需距离矢量路由AODV和AMR算法,提出了节点不相交多路径距离矢量路由协议MDVRo MDVR协议建立的路径信息分布在网络节点中,可缩短路由分组长度以及减轻路由发现源节点建立路由的负担;可防止攻击者通过墓改路由消息中的路径信息攻陷协议。     

无线传感器网络能量多路径路由研究

研究了无线传感器分层网络模型及能量多路径路由机制．为解决现有协议的缺陷，提出了改进型能量多路径路由协议(IMP-EA)，建立了路由算法．以网络寿命和丢包率作为评价指标，对改进型能量多路径路由协议和其它3种路由协议进行了仿真实验．仿真结果表明，改进后的协议有效地延长了网络的生存时间，提高了数据转发效率．     

一种具有负载感知的WMN多路径路由协议

为了使得WMN获得更好的负载均衡以防止网络拥塞,提出了一种适用于WMN的多路径路由协议.首先定义了一种综合考虑链路质量和节点负载的负载感知路由判据和可用带宽的计算方法,然后对路由更新机制进行了优化,并在路由请求阶段进行带宽预留,最后根据每条路径所分配的权值概率进行数据转发,进行节点间的负载均衡.仿真结果表明,与HWMP和AOMDV相比,改进后的路由协议有效避免了网络拥塞,增加了网络吞吐量,降低了平均端到端的延迟,提高了网络性能     

移动Ad Hoc网络中的多路径路由技术研究

多路径路由是AdHoc网络路由协议族中一个重要的分支,多路径路由能够给m7络提供更好的通信质量和更高的传输速度。首先介绍了移动AdHoc网络多路径路由技术的概念和特点,对典型的几种多路径路由协议进行了分析,并进一步讨论了当前研究的重点和关键技术。     

基于人工免疫的工业认知无线网络路由机制

工业互联网（industrial Internet）已成为第四次工业革命的代表技术.根据工业网络数据传输服务的需求,以及针对工业无线网络拓扑相对稳定、流量规律变化等特点,提出了一种基于人工免疫系统（artificial immune system,简称AIS）的工业认知无线网络路由机制,包含基于链路质量的域内静态路由算法和基于多路径的域间动态路由算法,以实现工业网络的可靠路由.根据人工免疫系统特点,将工业网络的拓扑结构进行区域划分：提出了基于链路质量的域内静态路由算法,采用软硬件结合的方式监视网络链路,并根据移动窗口指数加权平均法计算链路丢包率;提出了基于多路径的域间动态路由算法,根据模式距离对节点的流量周期进行预测,防止节点因流量过大而导致丢包.基于OMNET++仿真平台进行仿真实验,结果表明,所提出的路由机制在应对突发流量时与组合定向地理路由算法相比,丢包率及网络开销分别降低1倍;应对链路失效的情况时与图路由算法相比丢包率降低4倍.     

网络成员关联度计算方法研究

从成员相互关系角度研究网络。首先介绍一种现有的网络成员关联度计算方法——Ad-Ch算法,结合实例分析了Ad-Ch算法并指出其不足之处,然后提出一种新的网络成员关联度计算方法——不相交路径权值累积算法,最后通过实验对不相交路径权值累积算法的性能进行了验证。分析实验结果发现,不相交路径权值累积算法能有效计算网络成员关联度。     

Transient chaotic neural network-based disjoint multipath routing for mobile ad-hoc networks

Due to mobility of wireless hosts, routing in mobile ad-hoc networks (MANETs) is a challenging task. Multipath routing is employed to provide reliable communication, load balancing, and improving quality of service of MANETs. Multiple paths are selected to be node-disjoint or link-disjoint to improve transmission reliability. However, selecting an optimal disjoint multipath set is an NP-complete problem. Neural networks are powerful tools for a wide variety of combinatorial optimization problems. In this study, a transient chaotic neural network (TCNN) is presented as multipath routing algorithm in MANETs. Each node in the network can be equipped with a neural network, and all the network nodes can be trained and used to obtain optimal or sub-optimal high reliable disjoint paths. This algorithm can find both node-disjoint and link-disjoint paths with no extra overhead. The simulation results show that the proposed method can find the high reliable disjoint path set in MANETs. In this paper, the performance of the proposed algorithm is compared to the shortest path algorithm, disjoint path set selection protocol algorithm, and Hopfield neural network (HNN)-based model. Experimental results show that the disjoint path set reliability of the proposed algorithm is up to 4.5 times more than the shortest path reliability. Also, the proposed algorithm has better performance in both reliability and the number of paths and shows up to 56% improvement in path set reliability and up to 20% improvement in the number of paths in the path set. The proposed TCNN-based algorithm also selects more reliable paths as compared to HNN-based algorithm in less number of iterations.     

Designing a Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network with Disjoint Paths

Multi-stage Interconnection Networks (MINs) are designed to achieve fault-tolerance and collision solving by providing a set of disjoint paths. Ching-Wen Chen and Chung-Ping Chung had proposed a fault-tolerant network called Combining Switches Multi-stage Interconnection Network (CSMIN) and an inaccurate algorithm that provided two correct disjoint paths only for some source-destination pairs. This paper provides a more comprehensive and accurate algorithm that always generate correct routing-tags for two disjoint paths for every source-destination pair in the CSMIN. The 1-fault tolerant CSMIN causes the two disjoint paths to have regular distances at each stage. Moreover, our algorithm backtracks a packet to the previous stage and takes the other disjoint path in the event of a fault or a collision in the network. Furthermore, to eliminate the backtracking penalties of CSMIN, we propose a new design called Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network (FCSMIN). It has similar characteristics of 1-fault tolerance and two disjoint paths between any source-destination pair, but it can tolerate only one link or switch fault at each stage without backtracking. Our simulation and comparative analysis result shows that FCSMIN has added advantages of destination-tag routing, lower hardware costs, strong reroutability, lower preprocessing overhead, and higher fault-tolerance power in comparison to CSMIN.     

基于基本路径集算法生成最小长度测试序列的方法

在协议工程中,一致性测试已成为非常活跃的领域,而测试序列的产生是一致性测试非常关键的环节。文章基于基本路径集的生成算法,获得不相交路径,并利用测试子序列的一个重要特征—“重叠”来获得连接正收敛边和不相交路径的最小费用迁移路径,从而减少了测试序列的长度。     

Finding non-dominated bicriteria shortest pairs of disjoint simple paths

In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an adaptation of a path ranking algorithm applied to a network obtained from the original one after a suitable modification of the topology. Each path in this new network corresponds to a pair of paths in the former one. Computational results are presented and analysed for randomly generated networks.     

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

On a relaxed maximally disjoint path pair problem: a bicriteria approach

In some application areas in telecommunication and transportation networks, there are problems requiring the determination of pairs of paths, aiming at minimizing the number of links, or link groups that they share, and their total cost. In this paper, a new bicriteria algorithm is proposed to deal with this problem. The algorithm is based on ranking pairs of paths by order of the total cost, using an adaptation of a path‐ranking algorithm, after a suitable modification of the network topology. Nondominated solutions are then filtered by means of a dominance test. First, computational experiments are reported in order to assess the efficiency of the algorithm to calculate the whole set of nondominated pairs of paths. Second, we present computational results focused on the nondominated solutions close to the maximal disjoint pair (i.e., quasi‐disjoint pairs only, for a predefined admissible relaxation value) because in some application problems, such as shared risk link group pairs of paths, only those solutions have practical relevance.     

Linear time distributed construction of colored trees for disjoint multipath routing

Disjoint multipath routing (DMPR) is an effective strategy to achieve robustness in networks where data is forwarded along multiple link- or node-disjoint paths. DMPR poses significant challenges in terms of obtaining loop-free multiple (disjoint) paths and effectively forwarding data over the multiple paths, the latter being particularly significant in datagram networks. One approach to reduce the number of routing table entries for disjoint multipath forwarding is to construct two trees, namely red and blue, rooted at a destination node such that the paths from a source to the destination on the two trees are link/node-disjoint. This paper develops the first distributed algorithm for constructing the colored trees whose running time is linear in the number of links in the network. The paper also demonstrates the effectiveness of employing generalized low-point concept rather than traditional low-point concept in the DFS-tree to reduce the average path lengths on the colored trees.     

基于改进的不交化最小路集的网络系统可靠性算法

本文根据不交化布尔代数及BDD原理提出了一种简化的求解不交化最小路集的改进算法。对最小路集的路长进行排序,按最小路集的不同路长分两种方法不交化:对于长度为n-1的最小路集,在保持原有弧不变外,将网络图中其余未包含在该条最小路内的弧取逆加入,直接获得不交化运算结果;其余最小路集采用BDD方法进行不交化。最后的实例计算表明,改进的算法有较小的分枝树、较高的计算效率和精度,为大型网络系统的可靠性分析提供了一种新的途径。     

一种端到端网络的不相交多路径QoS路由算法

不相交多路径路由算法旨在一个端到端的网络中为应用流选择多个路径，且这些路径在瓶颈链路上是彼此不相交的。本文提出的不相交多路径QoS路由（DMQR）算法在Dijkstra最短路径和最短最宽路径（SWP）算法的基础上，能够动态地计算时延最短、带宽最宽、在瓶颈链路上互不相交的路径，且保证每个路径都是满足一定服务质量的。在视频会议、远程医疗和远程教育等重要的视频通信场合，要求应用层和网络层必须协同工作以保证一些必要的QoS，例如端到端的带宽、时延和包丢失率等。本文针对端到端的网络，重点讨论不相交多路径QoS路由算法在应用层的设计和实现。性能分析和模拟结果显示，所提出的不相交多路径QoS路由算法总是收敛的，且当网络流量增加时，该算法具有较低的包丢失率和较高的吞吐量。