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.     

Balancing CapEx reduction and network stability with stable routing–virtual topology capacity adjustment (SR–VTCA)

This paper investigates the merits of the SR–VTCA (stable routing–virtual topology capacity adjustment) approach as a mechanism to find a beneficial trade-off between network stability and reduction in capital expenditures (CapEx). These are two main objectives for the entities that own the optical infrastructure, such as network operators (NOs), and those also acting as Internet service providers (ISPs). The SR–VTCA scheme is a novel approach to adapt transparent optical networks to time-varying traffic by adjusting the number of lightpaths between node pairs, while keeping the IP routing unchanged. Lightpath bundling (LB) and anycast (AS) switching are combined in SR–VTCA operation to advertise lightpath additions/removals to the IP layer as mere adjustments (increments or decrements) in the capacity, allowing to keep the IP routing stable, and thus, simplifying control plane operations. On the contrary, a fully-reconfigurable (FR) network design, where IP routing can be also modified, would increase the burden in the control plane, but at a higher CapEx reduction, since the optical infrastructure is used more efficiently. In this work, we investigate the CapEx overprovision introduced by SR–VTCA with respect to a FR scheme. In order to do this, SR–VTCA planning problem is first modeled as a MILP formulation. A heuristic procedure based on traffic domination is then proposed to solve large instances of the problem. Exhaustive experiments are conducted comparing the SR–VTCA solutions obtained by the aforementioned MILP and heuristic proposal with solutions found by other optimization methods presented in the literature to solve the FR planning problem. Finally, the results show that SR–VTCA can achieve similar results to the FR case in terms of CapEx reduction, while a huge number of IP reroutings are saved by maintaining IP stability. Thus, SR–VTCA provides an advantageous balance between CapEx overprovisioning and the control plane overhead associated with IP rerouting.     

A heuristic to solve the synchronized log-truck scheduling problem

We present a synchronized routing and scheduling problem that arises in the forest industry, as a variation of the log-truck scheduling problem. It combines routing and scheduling of trucks with specific constraints related to the Canadian forestry context. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developed a decomposition approach to solve the weekly problem in two phases. In the first phase we use a MIP solver to solve a tactical model that determines the destinations of full truckloads from forest areas to woodmills. In the second phase, we make use of two different methods to route and schedule the daily transportation of logs: the first one consists in using a constraint-based local search approach while the second one is a hybrid approach involving a constraint programming based model and a constraint-based local search model. These approaches have been implemented using COMET2.0. The method, was tested on two industrial cases from forest companies in Canada.     

A note on the time travel approach for handling time windows in vehicle routing problems

In this paper, we identify two cases in which the proposition for calculating time window penalties presented in Nagata, Y., Bräysy, O. and Dullaert, W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research 2010;37(4): 724–37 yields incorrect results. We derive the corrected proposition and use numerical studies to show that a significant proportion of the evaluations performed by a Tabu Search for VRPTW falls under the two incorrect cases. Moreover, we demonstrate that the incorrect time window handling has a significant negative impact on the solution quality of the Tabu Search.     

Energy‐efficient void avoidance geographic routing protocol for underwater sensor networks

Underwater wireless sensor networks (UWSNs) consist of a group of sensors that send the information to the sonobuoys at the surface level. Void area, however, is one of the challenges faced by UWSNs. When a sensor falls in a void area of communication, it causes problems such as high latency, power consumption, or packet loss. In this paper, an energy‐efficient void avoidance geographic routing protocol (EVAGR) has been proposed to handle the void area with low amount of energy consumption. In this protocol, a suitable set of forwarding nodes is selected using a weight function, and the data packets are forwarded to the nodes inside the set. The weight function includes the consumed energy and the depth of the candidate neighboring nodes, and candidate neighboring node selection is based on the packet advancement of the neighboring nodes toward the sonobuoys. Extensive simulation experiments were performed to evaluate the efficiency of the proposed protocol. Simulation results revealed that the proposed protocol can effectively achieve better performance in terms of energy consumption, packet drop, and routing overhead compared with the similar routing protocol.     

无线传感器网络体系结构和关键技术研究

文章介绍了无线传感器网络的体系结构,提出了一种基于跨层设计的管理控制机制;在对无线传感器网络的关键技术,如媒体接入控制(MAC)技术和无线路由协议,分别进行阐述和比较的基础上,提出了一种把简单的IEEE 802 MAC协议应用于无线传感器网络的思想;为了提高系统容量,提出了多信道策略,可以用来有效减少系统碰撞阻塞率,减少接入时延;认为虽然无线传感器网络的应用前景非常广阔,但是仍存在很多问题,除了要尽量减少功耗外,必须提高系统容量,减少碰撞阻塞率,以加快无线传感器网络实用化的进程.     

Adaptive quality of service‐based routing approaches: development of neuro‐dynamic state‐dependent reinforcement learning algorithms

In this paper, we propose two adaptive routing algorithms based on reinforcement learning. In the first algorithm, we have used a neural network to approximate the reinforcement signal, allowing the learner to take into account various parameters such as local queue size, for distance estimation. Moreover, each router uses an online learning module to optimize the path in terms of average packet delivery time, by taking into account the waiting queue states of neighbouring routers. In the second algorithm, the exploration of paths is limited to N‐best non‐loop paths in terms of hops number (number of routers in a path), leading to a substantial reduction of convergence time. The performances of the proposed algorithms are evaluated experimentally with OPNET simulator for different levels of traffic's load and compared with standard shortest‐path and Q‐routing algorithms. Our approach proves superior to classical algorithms and is able to route efficiently even when the network load varies in an irregular manner. We also tested our approach on a large network topology to proof its scalability and adaptability. Copyright © 2006 John Wiley & Sons, Ltd.     

A survey of cross‐layer protocols for IEEE 802.11 wireless multi‐hop mesh networks

There has been an escalation in deployment and research of wireless mesh networks by both the business community and academia in the last few years. Their attractive characteristics include low deployment cost, a low‐cost option to extend network coverage and ease of maintenance due to their self‐healing properties. Multiple routes exist between the sender and receiver nodes because of the mesh layout that ensures network connectivity even when node or link failures occur. Recent advances among others include routing metrics, optimum routing, security, scheduling, cross‐layer designs and physical layer techniques. However, there are still challenges in wireless mesh networks as discussed in this paper that need to be addressed. Cross‐layer design allows information from adjacent and non‐adjacent layers to be used at a particular layer for performance improvement. This paper presents a survey of cross‐layer protocol design approaches applied to the IEEE 802.11 standards for wireless multi‐hop mesh networks that have been proposed over the last few years for improved performance. We summarize the current research efforts in cross‐layer protocol design using the IEEE 802.11 standard in identifying unsolved issues that are a promising avenue to further research. Copyright © 2016 John Wiley & Sons, Ltd.     

一种基于路径的新型自适应路由算法

构造了一种新型的路由表,设计了基于遗传算法的自适应路由算法(GAR),并在PC机上实现了简化的GAR.在局域网环境下,对GAR和基于跳计数准则的RIP的模拟试验表明,在相同的网络负载下GAR的平均通信延时是RIP的20%.该算法能够降低网络延时,平衡网络负载,提高网络性能.     

LLN中基于能量均衡的高效低时延路由算法

针对有损低功耗网络(Low-power and Lossy Network,LLN)中由于无线链路的有损特性以及节点部署不均匀无法有效实现网络能量均衡,提出一种基于能量均衡的高效低时延路由算法(Efficient Low Latency Routing Algorithm Based on Energy Balance in Low-Power and Lossy Networks,ELLEB-RPL)。该算法采用“ELLEB组网”策略,使得节点能够有效避免在DODAG(Destination Oriented Directed Acyclic Graph)间来回切换;通过采用“最优父节点选择”策略,使得节点选择的父节点达到最优;通过采用“流量自适应分配”策略,达到网络能量均衡的目的。仿真结果表明,ELLEB-RPL在Sink节点平均吞吐量、网络平均寿命以及端到端时延上均有提升。