Proactive multipath routing with a predictive mechanism in software‐defined networks

With the growth of network traffic volume, link congestion cannot be avoided efficiently with conventional routing protocols. By utilizing the single shortest‐path routing algorithm from link state advertisement information, standard routing protocols lack of global awareness and are difficult to be modified in a traditional network environment. Recently, software‐defined network (SDN) provided innovative architecture for researchers to program their own network protocols. With SDN, we can divert heavy traffic to multiple paths in order to resolve link congestion. Furthermore, certain network traffics come in periodic fashion such as peak hours at working days so that we can leverage forecasting for resource management to improve its performance. In this paper, we propose a proactive multipath routing with a predictive mechanism (PMRP) to achieve high‐performance congestion resolution. PMRP has two main concepts: (a) a proactive mechanism where PMRP deploys M/M/1 queue and traffic statistics to simulate weighted delay for possible combinations of multipaths placement of all subnet pairs, and leverage genetic algorithm for accelerating selection of optimized solution, and (b) a predictive mechanism whereby PMRP uses exponential smoothing for demand traffic volumes and variance predictions. Experimental results show a 49% reduction in average delay as compared with single shortest routing, and a 16% reduction in average delay compared with utilization & topology‐aware multipath routing (UTAMP). With the predictive mechanism, PMRP can decrease an additional 20% average delay. Furthermore, PMRP reduces 93% of flow table usage on average as compared with UTAMP.     

Non-SPF routing algorithm based on ordered semi-group preference algebra

Layer 2 network technology is extending beyond its traditional local area implementation and finding wider acceptance in provider's metropolitan area networks and large-scale cloud data center networks. This is mainly due to its plug-and-play capability and native mobility support. Many efforts have been put to increase the bisection bandwidth in layer 2 network, which has been constrained by the spanning tree protocol (STP) that layer 2 network uses for preventing looping. The recent trend is to incorporate layer 3's routing approach into layer 2 network so that multiple paths can be used for forwarding traffic between any source-destination (S-D) node pair. Equal cost multipath (ECMP) is one such example. However, ECMP may still be limited in generating multiple paths due to its shortest path (lowest cost) requirement. In this paper, we consider a non-shortest-path routing approach, called equal preference multipath (EPMP) based on ordered semi group theory, which can generate more paths than ECMP. In EPMP routing, all the paths with different traditionally-defined costs, such as hops, bandwidth, etc., can be determined equally now and thus they become equal candidate paths. By the comparative tests with ECMP, EPMP routing not only generates more paths, provides 15% higher bisection bandwidth, but also identifies bottleneck links in a hierarchical network when different traffic patterns are applied. EPMP is more flexible in controlling the number and length of multipath generation. Simulation results indicate the effectiveness of the proposed algorithm. It is a good reference for non-blocking running of big datacenter networks.     

Oblivious Routing in Fat-Tree Based System Area Networks With Uncertain Traffic Demands

We study oblivious routing in fat-tree-based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by the oblivious performance ratio that bounds the relative performance of the routing algorithm with respect to the optimal algorithm for any given traffic demand. We consider both single-path routing, where only one path is used to carry the traffic between each source-destination pair, and multipath routing, where multiple paths are allowed. For single-path routing, we derive lower bounds of the oblivious performance ratio for different fat-trees and develop routing schemes that achieve the optimal oblivious performance ratios for commonly used topologies. Our evaluation results indicate that the proposed oblivious routing schemes not only provide the optimal worst-case performance guarantees but also outperform existing schemes in average cases. For multipath routing, we show that it is possible to obtain an optimal scheme for all traffic demands (an oblivious performance ratio of 1). These results quantitatively demonstrate the performance difference between single-path routing and multipath routing in fat-trees.     

Priority‐based adaptive routing in NGEO satellite networks

In a non‐geostationary satellite constellation with inter satellite links (ISLs), there could be many shortest paths between two satellites in terms of hop count. An efficient routing algorithm should effectively use these paths in order to distribute traffic to ISLs in a balanced way and to improve the performance of the system. This paper presents and evaluates a novel priority‐based adaptive shortest path routing (PAR) scheme in order to achieve this goal. PAR sets the path towards the destination in a distributed manner, using a priority mechanism depending on the past utilization and buffering information of the ISLs. Moreover, to avoid unnecessary splitting of a flow and to achieve better utilization of ISLs, enhanced PAR (ePAR) scheme is proposed. This paper evaluates performance of the proposed techniques by employing an extensive set of simulations. Furthermore, since there are a number of ePAR parameters that should be adjusted depending on the network and traffic characteristics, a detailed analysis of ePAR scheme is provided to form a framework for setting the parameters. This paper also includes a method for adaptation of the proposed algorithms to minimum‐delay path routing. Copyright © 2006 John Wiley & Sons, Ltd.     

IP网络时延敏感型业务流自适应负载均衡算法

互联网对时延敏感的业务数据流,要求具有较低的端到端时延,但是网络拥塞的发生,将会使服务质量无法保证。基于链路关键度提出了一种新的自适应负载均衡路由算法(LARA,load adaptive routing algorithm),能最大限度地避开拥塞链路从而减少端到端延迟。该算法通过得到一个优化目标函数,并利用凸优化理论将优化目标函数分解为若干个子函数,最终得到一个简单的分布式协议。利用NS2仿真器在基于CERNET2真实的拓扑结构上进行仿真实验,同时与网络中能普遍部署的等开销多路径(ECMP,equal-costmulti-path)算法相比较,通过测试反馈时延、分组丢失率、流量负载,结果表明LARA具有更好的自适应性和健壮性,性能相比更优。     

光网络中基于流量均衡的SRLG分离路由算法

基于共享风险链路组(SRLG,shared risk link group)和流量均衡的概念,研究了光网络抗毁设计中基于流量均衡的SRLO尽量分离路由问题,利用网络流量的实际分布来评价链路和SRLG重要性,提出基于流量均衡的SRIG分离算法TBDR.通过计算机仿真表明,TBDR算法性能优于保护路优先算法,该算法能有效降低网络阻塞率,提高网络资源利用率和网络抗毁能力,达到流量均衡的目标.     

无线自组织网络中一种拥塞意识的多径路由算法

提出了无线自组织网络中一种拥塞意识的多径路由算法。该算法在路由发现过程中,综合节点的队列长度和路径跳数来动态确定路由请求消息的转发概率,可以在保证路由请求消息有一定送达率的条件下,降低路由开销;在路径选择和流量分配过程中,综合考虑节点的队列长度和路径质量作为路由度量,发现流量高吞吐量低拥塞路径,并基于该度量值进行流量分配。仿真结果显示,所提出的多径路由算法能有效提高网络性能。     

MPLS网络中保证服务质量的多径路由选择策略

本文提出了一种在多协议标签交换(MPLS, Multiple Protocol Label Switching) 网络中保证服务质量 (QoS,Quality-of-Service) 的多径路由选择策略,其核心思想是引入多路径分散业务量机制,在保证用户服务质量要求的同时达到增加网络呼叫接受率和平衡网络负载的目的.文中着重讨论了用户端对端服务质量要求的多路分解和分配问题,在此基础上提出了多径路由的分支路径选择策略,并研究了策略中的关键参数K对该策略性能的影响.数值结果显示出多路径分散业务量在网络负载均衡方面的重要意义,并且表明用户的要求相对网络资源越高使用多径传输的优势越明显.     

基于位置感知和代理的WSN多径路由方案

针对无线传感器网络(WSN)中多径路由的可靠性和能量效率问题,提出了一种基于代理和位置感知的多径路由发现方案(LABMR).事件节点根据位置信息,动态寻找其到Sink节点之间的特殊中间节点,来构建多径路由.利用移动代理来收集多径路由的局部拓扑结构信息,Sink节点根据代理收集的路由参数来计算路径权值,以此选择最优不相交路径.同时,对于信息的重要性差异,Sink节点选择单条或多条路径来传输数据,在保证传输可靠性的同时减少能耗.与现有的基于代理的多径路由(ABMR)方法相比,LABMP在数据包投递率、能量消耗、额外开销和延迟方面具有更好的性能.     

On the effectiveness of alternative paths in QoS routing

We propose a routing strategy in which connection requests with specific bandwidth demands can be assigned to one of several alternative paths connecting the source to the destination. The primary goal of this multiple‐path approach is to compensate for the inaccuracy of the knowledge available to routing nodes, caused by the limited frequency of link state (LS) information exchanges. We introduce a collection of K‐shortest path routing schemes and investigate their performance under a variety of traffic conditions and network configurations. We subsequently demonstrate that K‐shortest path routing offers a lower blocking probability in all scenarios and more balanced link utilization than other routing methods discussed in the literature. With our approach, it is possible to reduce the frequency of link state exchanges, and the incurred bandwidth overhead, without compromising the overall performance of the network. Based on the proposed routing scheme, we investigate different link state dissemination algorithms, which are aimed at reducing the communication overhead by prioritizing the scope and differentiating the qualitative content of LS update messages. Copyright © 2004 John Wiley & Sons, Ltd.     

Energy‐efficient multihop routing in WSN using the hybrid optimization algorithm

The technical growth in the field of the wireless sensor networks (WSNs) has resulted in the process of collecting and forwarding the massive data between the nodes, which was a major challenge to the WSNs as it is associated with greater energy loss and delay. This resulted in the establishment of a routing protocol for the optimal selection of the multipath to progress the routing in WSNs. This paper proposes an energy‐efficient routing in WSNs using the hybrid optimization algorithm, cat–salp swarm algorithm (C‐SSA), which chooses the optimal hops in progressing the routing. Initially, the cluster heads (CHs) are selected using the low‐energy adaptive clustering hierarchy (LEACH) protocol that minimizes the traffic in the network. The CHs are engaged in the multihop routing, and the selection of the optimal paths is based on the proposed hybrid optimization, which chooses the optimal hops based on the energy constraints, such as energy, delay, intercluster distance, intracluster distance, link lifetime, delay, and distance. The simulation results prove that the proposed routing protocol acquired minimal delay of 0.3165 with 50 nodes and two hops, maximal energy of 0.1521 with 50 nodes and three hops, maximal number of the alive nodes as 39 with 100 nodes and two hops, and average throughput of 0.9379 with 100 nodes and three hops.     

Minimum cost load balanced multipath routing protocol for low power and lossy networks

Conventional shortest path routing mechanisms in low power and lossy networks (LLNs) impose excessive traffic load on some nodes and cause their early battery depletion. Load balancing via multipath routing is a promising solution to increase lifetime. This idea is practised by some algorithms, mostly through limited number of disjoint paths, to reduce inter-path interference. In this paper a proactive multipath routing algorithm called MRPL is proposed, based on the recent standard routing protocol for LLNs. The algorithm tries to distribute the traffic load through a set of braided paths, with the objective of maximizing the network lifetime and minimizing total transmission cost. The traffic distribution mechanism is formulated by a linear program and a heuristic method is proposed to implement it in a distributed manner. Simulation results provide enough evidence for energy and cost efficiency of the proposed routing mechanism.     

Load balance in hierarchical routing network

In this article, the problem of load balance in hierarchical routing network is studied. Since conventional shortest path first (SPF) algorithm over aggregated topology in hierarchical routing network may result in worse routing performance, a traffic sharing path selection algorithm and a variable weight scheme are put forward for hierarchical routing network, which can equilibrate the utilities of link resources and reduce the blocking probability of connections with the improvement on survivability. Simulations are conducted to evaluate proposed variable weight and traffics balance (VWTB) algorithm, which combines traffic sharing and variable weight. From the simulation results, it can be found that the proposed VWTB algorithm can balance the traffics and equilibrate the utilities of link resources significantly.     

一种Ad Hoc网络中路由软切换策略的研究

提出了一种新的Ad Hoc网络中对路由的维护方法,即基于局部多路径路由维护的路由软切换技术。在当前路由中某段或某几段链路出现问题时,通过建立局部的多路径路由,分担问题链路中的负载,维护网络保持通信连接不被中断;当路由稳定时,从局部多路径路由中寻找一条满足当前主路由通信需要的子路径,并且将数据传输切换到此子路径上,达到路由抢先维护和软切换的目的。该方法能够缩短路由重建的时间,延长单路径路由的寿命,使用多路径维护,避免了网络拥塞出现造成路由中断,能够很好地提高网络性能。     

一种基于分时的LEO卫星网络无环路由算法

在分析传统卫星网络路由算法的基础上，提出一种基于分时的LEO卫星网络无环路由算法(DTRA)。针对卫星在各时间片之间进行路由表切换时可能出现的路由环问题，算法采用平滑路由表切换策略消除由于切换前后网络状态信息不一致而产生环路的可能性，保证分组在任何时刻都能够沿无环最短时延路径被转发。同时，DTRA也能够通过使用无环备份路径处理可能出现的链路拥塞、节点失败等突发情况。通过复杂性分析可知，算法只需较小的星上存储开销和星上处理开销，而无需星问通信开销。仿真实验结果也表明算法能够提供数据最优传送，具有较好的端到端时延性能。     

Delay constraint multipath routing for wireless multimedia ad hoc networks

According to the disadvantages of real time and continuity for multimedia services in ad hoc networks, a delay constraint multipath routing protocol for wireless multimedia ad hoc networks, which can satisfy quality of service (QoS) requirement (QoS multipath optimized link state routing [MOLSR]), is proposed. The protocol firstly detects and analyzes the link delay among the nodes and collects the delay information as the routing metric by HELLO message and topology control message. Then, through using the improved multipath Dijkstra algorithm for path selection, the protocol can gain the minimum delay path from the source node to the other nodes. Finally, when the route is launched, several node‐disjoint or link‐disjoint multipaths will be built through the route computation. The simulation and test results show that QoS‐MOLSR is suitable for large and dense networks with heavy traffic. It can improve the real time and reliability for multimedia transmission in wireless multimedia ad hoc networks. The average end‐to‐end delay of QoS‐MOLSR is four times less than the optimized link state routing. Copyright © 2014 John Wiley & Sons, Ltd.     

Energy efficient fault-tolerant multipath routing scheme for wireless sensor networks

In wireless sensor network （MSN）, reliability is the main issue to design any routing technique. To design a comprehensive reliable wireless sensor network, it is essential to consider node failure and energy constrain as inevitable phenomena. In this paper we present energy efficient node fault diagnosis and recovery for wireless sensor networks referred as energy efficient fault tolerant multipath routing scheme for wireless sensor network. The scheme is based on multipath data routing. One shortest path is used for main data routing in our scheme and other two backup paths are used as alternative path for faulty network and to handle the overloaded traffic on main channel. Shortest pat data routing ensures energy efficient data routing. Extensive simulation results have revealed that the performance of the proposed scheme is energy efficient and can tolerates more than 60% of fault.     

一种智慧协同网络多参数的多路径路由算法

多路径路由技术采用多条路径同时传输,作为优化资源配置和负载均衡的重要技术,在路由可靠性、QoS路由、传输效率等多方面比单路径传输具有优势.现有互联网网络资源配置和路由机制相对静态和僵化,导致多路径技术的发展存在发展的局限性.现有多路径技术考虑在路由层面不利于多路径路由选择和计算,难以保证传输性能,降低网络传输效率.智慧协同网络能够动态感知网络需求,灵活适配网络资源,更好的支持路由可扩展性.本文在智慧协同网络架构下提出了一种智慧协同网络多参数的多路径路由算法.该算法制定了智慧协同网络多参数的多路径路由协议,对网络性能参数CPU占用率、往返时延(RTT)、带宽进行加权计算得到路径权重值,根据权重值进行流量分配.采用图论理论对网络流量分配及模型进行了分析.并在Mini-Net平台上进行了开发和实验,结果表明,该算法能够优化网络配置,减小往返时延,提高网络吞吐量,从而提高网络性能,实现负载均衡.     

Multipath Routing Algorithms for Congestion Minimization

Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the single-path routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing. Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish efficient solutions with proven performance guarantees     

弹性光网络中面向任播业务的节能路由算法

为提高数据中心间光互联网络的能效,面向任播业务提出一种具有业务持续时间感知的混合路径传输节能路由算法.为了减少新建光路和工作元器件数量,优先采用单路径传输;若业务阻塞则以传输能耗最小化为目标进行多路径传输.除此之外,引入基于频谱预留的业务疏导策略来降低保护带宽和光收发器的开销.仿真结果表明:与传统节能路由算法相比,所提算法在显著降低网络能耗的同时,有效避免了业务阻塞率的过度增加,实现了网络能耗与性能的平衡.