A computationally efficient iterative solution of themultidestination optimal dynamic routing problem

The dynamic routing problem for multiple destination networks is considered. The minimum time rather than total delay cost functional is employed. The problem is solved through an iterative link-by-link optimization. Each link capacity is optimally partitioned by examining the upper bounds for the evacuation time imposed through different capacity allocations for each origin/destination pair traffic. The computational complexity per iteration is polynomial in the number of network nodes. This is due to the examination of origin/destination pairs rather then destinations alone as in previous work where a similar approach led to exponential complexity. Sufficient conditions for the convergence of the iterative algorithm to the optimum are given. If these are not satisfied supplementary steps are described which conduct the algorithm to the desired solution. These involve exponential computational complexity     

A Failsafe Distributed Routing Protocol

An algorithm for constructing and adaptively maintaining routing tables in communication networks is presented. The algorithm can be employed in message as well as circuit switching networks, uses distributed computation, provides routing tables that are loop-free for each destination at all times, adapts to changes in network flows, and is completely failsafe. The latter means that after arbitrary failures and additions, the network recovers in finite time in the sense of providing routing paths between all physically connected nodes. For each destination, the routes are independently updated by an update cycle triggered by the destination.     

交通路灯监控系统的无线传感网链状路由算法

在交通路灯监控系统中为节省网络节点能耗和降低数据传输时延,提出一种无线传感网链状路由算法（CRASMS）。该算法根据节点和监控区域的信息将监控区域分成若干个簇区域,在每一个簇区域中依次循环选择某个节点为簇头节点,通过簇头节点和传感节点的通信建立簇内星型网络,最终簇头节点接收传感节点数据,采用数据融合算法降低数据冗余,通过簇头节点间的多跳路由将数据传输到Sink节点并将用户端的指令传输到被控节点。仿真结果表明：CRASMS算法保持了PEGASIS算法在节点能耗方面和LEACH算法在传输时延方面的优点,克服了PEGASIS 算法在传输时延方面和LEACH算法在节点能耗方面的不足,将网络平均节点能耗和平均数据传输时延保持在较低水平。在一定的条件下,CRASMS算法比LEACH和PEGASIS算法更优。     

一种集中调控的分布式服务路径选择算法

在可重构网络多态路由模型中,通常存在多条满足业务需求的服务路径。针对最优服务路径选择问题,该文设计了一种集中调控的分布式服务路径选择算法,各节点根据服务请求中的第1个元能力和目的节点生成路由表,控制器实时监控网络,调控代价过高路径并平衡网络的带宽和负载。性能分析和仿真结果表明,分布式路由表能够生成有效的服务路径,表项规模、收敛时间与元能力个数成正比,在30%的集中调控比例下,路径代价和负载均衡度性能良好,与其他算法相比,对服务请求的响应时延降低约50%。     

Mobile ad hoc network proactive routing with delay prediction using neural network

Existing MANET routing protocols rely heavily on hop count evaluation. Although this is simple and efficient, it sacrifices the potential performance gains obtainable by considering other dynamic routing metrics. In this paper, we propose a delay prediction mechanism and its integration with a MANET proactive routing protocol. We demonstrate our approach of predicting mean queuing delay as a nonstationary time series using appropriate neural network models: Multi-Layer Perceptron or Radial Basis Function. To support MANET proactive routing, our delay prediction mechanism is devised as a distributed, independent, and continuous neural network training and prediction process conducted on individual nodes. We integrated our delay prediction mechanism with a well-known MANET proactive routing protocol—OLSR. The essential part of this integration is our TierUp algorithm, which is a novel node-state routing table computation algorithm. The structure and the key parameters of the resulting extended OLSR, called OLSR_NN, are also discussed. Our simulation shows that because of its capability of balancing the traffic, OLSR_NN is able to increase data packet delivery ratio and reduce average end-to-end delay in scenarios with complex traffic patterns and wide range of node mobility, compared to OLSR.     

SMART: Statistically Multiplexed Adaptive Routing Technique for Ad Hoc Networks

This paper develops a common solution to the problems of discovery, maintenance, and use of multiple routes in ad hoc networks. The performance criterion is the average time taken by a packet to reach its destination through multiple hops. A source node considers each of its neighbors (reachable by direct wireless transmission) as a next-hop for every possible destination. The effect of delay at a next-hop and beyond, until the packet reaches its destination, is approximately modeled as an equivalent M/M/1 queuing system. Available neighbors at every node provide multiple routes. Multiple routes are statistically multiplexed to distribute the load as well as to deal with changes in data rates and network configuration. The potential of each next-hop neighbor of a node in providing a viable route is estimated on-line and the proportions of traffic routed through these multiple neighbors are also updated adaptively.We study this approach and conduct extensive experiments over a network with two extreme cases of simulated traffic patterns, the Poisson, and the self-similar types. Even when the network topology is static, our algorithm responds to bursts in the traffic pattern and reduces buffer losses through the use of alternative, less congested routes. We also present simulation experiments and results to demonstrate the effectiveness of our algorithm in the presence of mobility, using self-similar traffic. Mobility is simulated by means of the random waypoint model in which nodes move with varying speeds. Results show that our simple unified approach handles the problems of mobility as well as network congestion very well.     

A compressive sensing‐based network tomography approach to estimating origin–destination flow traffic in large‐scale backbone networks

A traffic matrix can exhibit the volume of network traffic from origin nodes to destination nodes. It is a critical input parameter to network management and traffic engineering, and thus it is necessary to obtain accurate traffic matrix estimates. Network tomography method is widely used to reconstruct end‐to‐end network traffic from link loads and routing matrix in a large‐scale Internet protocol backbone networks. However, it is a significant challenge because solving network tomography model is an ill‐posed and under‐constrained inverse problem. Compressive sensing reconstruction algorithms have been well known as efficient and precise approaches to deal with the under‐constrained inference problem. Hence, in this paper, we propose a compressive sensing‐based network traffic reconstruction algorithm. Taking into account the constraints in compressive sensing theory, we propose an approach for constructing a novel network tomography model that obeys the constraints of compressive sensing. In the proposed network tomography model, a framework of measurement matrix according to routing matrix is proposed. To obtain optimal traffic matrix estimates, we propose an iteration algorithm to solve the proposed model. Numerical results demonstrate that our method is able to pursuit the trace of each origin–destination flow faithfully. Copyright © 2014 John Wiley & Sons, Ltd.     

A Basic Dynamic Routing Problem and Diffusion

Diffusion theory has sometimes been successful in providing excellent approximate solutions to difficult queueing problems. Here we explore whether such methods can be used to analyze a basic dynamic routing strategy associated with a single idealized node in a data network. We analyze a dynamic routing policy where messages, or packets, that arrive at a certain node are routed to leave the node on the link having the shorter queue. In the model, message or packet arrivals are Poisson and the service time is exponentially distributed. We explore a heavy traffic diffusion method and we also discuss the limitations of an ad hoc approach to applying diffusion. For a node withKoutgoing queues we find, under the assumption of heavy traffic, the optimum dynamic strategy, in the sense of minimizing the average delay. When this optimum dynamic strategy is compared to a static strategy where the outgoing traffic is split among theKqueues, we find that the average delay for the dynamic system is better by a factor ofK.     

Preconfiguring IP-over-Optical Networks to Handle Router Failures and Unpredictable Traffic

We consider the realization of traffic-oblivious routing in IP-over-optical networks where routers are interconnected over a switched optical backbone. The traffic-oblivious routing we consider is a scheme where incoming traffic is first distributed in a preset manner to a set of intermediate nodes. The traffic is then routed from the intermediate nodes to the final destination. This splitting of the routing into two phases simplifies network configuration significantly. In implementing this scheme, the first and second phase paths are realized at the optical layer with router packet grooming at a single intermediate node only. Given this unreliability of routers, we consider how two-phase routing in IP-over-optical networks can be made resilient against router node failures. We propose two different schemes for provisioning the optical layer to handle router node failures-one that is failure node independent and static, and the other that is failure node dependent and dynamic We develop linear programming formulations for both schemes and a fast combinatorial algorithm for the second scheme so as to maximize network throughput. In each case, we determine (i) the optimal distribution of traffic to various intermediate routers for both normal (no-failure) and failure conditions, and (ii) provisioning of optical layer circuits to provide the needed inter-router links. We evaluate the performance of the two router failure protection schemes and compare it with that of unprotected routing     

Dynamic cache allocation routing strategy of Internet of things satellite node based on traffic prediction

Aiming at the routing problem of low earth orbit (LEO) Internet of things (IoT) satellite systems,a dynamic cache allocation routing strategy based on traffic prediction for IoT satellite nodes was proposed.Firstly,the space-time characteristics of traffic distribution in the LEO coverage area were analyzed,and an end-to-end traffic prediction model was proposed.Then,according to the traffic prediction result,a dynamic cache allocation routing strategy was proposed.The satellite node periodically monitored the traffic load of the inter-satellite link,dynamically allocated the cache resources of each inter-satellite link between the neighboring nodes.The cache allocation process was divided into two phases,initialization and system operation.At the same time,the traffic offload and packet forwarding strategy when the node was congested was proposed.By comparing the queuing delay and the forwarding delay,it was determined whether the data packet needs to be rerouted.The simulation results show that the proposed routing strategy effectively reduces the packet loss rate and average end-to-end delay,and improves the traffic distribution in the whole network.     

Distributed Iterative Optimal Resource Allocation With Concurrent Updates of Routing and Flow Control Variables

Consider a set of active elastic sessions over a network. Session traffic is routed at each hop (potentially through multiple network paths) based only on its destination. Each session is associated with a concave increasing utility function of its transfer rate. The transfer rates of all sessions and the routing policy define the operating point of the network. We construct a metric $f$ of the goodness of this operating point. $f$ is an increasing function of the session utilities and a decreasing function of the extent of congestion in the network. We define “good” operating points as those that maximize $f$, subject to the capacity constraints in the network. This paper presents a distributed, iterative algorithm for adapting the session rates and the routing policy across the network so as to converge asymptotically to the set of “good” operating points. The algorithm updates session rates and routing variables concurrently and is, therefore, amenable to distributed online implementation. The convergence of the concurrent update scheme is proved rigorously.      

Dynamic power allocation and routing for time-varying wireless networks

We consider dynamic routing and power allocation for a wireless network with time-varying channels. The network consists of power constrained nodes that transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support-where /spl lambda//sub ij/ represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed that stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad hoc wireless network, where channel variations are due to user mobility. Centralized and decentralized implementations are compared, and the stability region of the decentralized algorithm is shown to contain that of the mobile relay strategy developed by Grossglauser and Tse (2002).     

Adding sense of spatial locality to routing protocols for mobile ad hoc networks

Recently, there has been an increasing interest in mobile ad hoc networks. In a mobile ad hoc network, each mobile node can freely move around and the network is dynamically constructed by collections of mobile nodes without using any existing network infrastructure. Compared to static networks, it faces many problems such as the inefficiency of routing algorithms. Also, the number of control packets in any routing algorithm increases as the mobile speed or the number of mobile nodes increases. Most of the current routing protocols in ad hoc networks broadcast the control packets to the entire network. Therefore, by reducing the number of control packets, the efficiency of the network routing will be improved. If we know where the destination is, we can beam our search toward that direction. However, without using global positioning systems, how can we do this? Define the range nodes as the 1‐hop or 2‐hop neighbors of the destination node. In this paper, we propose using the range nodes to direct our searches for the destination. It can be combined with the existing routing protocols to reduce the control overhead. We show through simulations that AODV and DSR combined with the range node method outperforms the original AODV and DSR routing protocols in terms of control packets overhead. We also show that the delay introduced in find range nodes is insignificant. Copyright © 2006 John Wiley & Sons, Ltd.     

An efficient routing protocol for the QoS support of large‐scale MANETs

The hierarchical routing algorithm is categorized as a kind of routing method using node clustering to create a hierarchical structure in large‐scale mobile ad hoc network (LMANET). In this paper, we proposed a new hierarchical clustering algorithm (HCAL) and a corresponded protocol for hierarchical routing in LMANET. The HCAL is designed based on a cost metric in the form of the link expiration time and node's relative degree. Correspondingly, the routing protocol for HCAL adopts a reactive protocol to control the existing cluster head (CH) nodes and handle proactive nodes to be considered as a cluster in LMANET. Hierarchical clustering algorithm jointly utilizes table‐driven and on‐demand routing by using a combined weight metric to search dominant set of nodes. This set is composed by link expiration time and node's relative degree to establish the intra/intercommunication paths in LMANET. The performance of the proposed algorithm and protocol is numerically evaluated in average end‐to‐end delay, number of CH per round, iteration count between the CHs, average CH keeping time, normalized routing overhead, and packet delivery ratio over a number of randomly generated benchmark scenarios. Furthermore, to corroborate the actual effectiveness of the HCAL algorithm, extensive performance comparisons are carried out with some state‐of‐the‐art routing algorithms, namely, Dynamic Doppler Velocity Clustering, Signal Characteristic‐Based Clustering, Dynamic Link Duration Clustering, and mobility‐based clustering algorithms.     

LEO星座中基于不完全信息的路由联盟博弈策略

针对LEO卫星网络在多跳转发数据包时流量分布不均问题,提出了一种基于不完全信息的最优收益路由联盟博弈算法.各节点协同联盟邻居节点,共同确定数据报文当前最优转发路径,从而分配和平衡节点间流量负载.仿真结果表明,与最短路径卫星路由DSP或智能路由TLR相比,本文算法的平均数据传输延迟降低了18.5%,节点流量负载均衡度提高了65.6%.     

RPSF: A Routing Protocol with Selective Forwarding for Mobile Ad-Hoc Networks

Many existing reactive routing algorithms for mobile ad-hoc networks use a simple broadcasting mechanism for route discovery which can lead to a high redundancy of route-request messages, contention, and collision. Position-based routing algorithms address this problem but require every node to know the position and velocity of every other node at some point in time so that route requests can be propagated towards the destination without flooding the entire network. In a general ad-hoc network, each node maintaining the position information of every other node is expensive or impossible. In this paper, we propose a routing algorithm that addresses these drawbacks. Our algorithm, based on one-hop neighborhood information, allows each node to select a subset of its neighbors to forward route requests. This algorithm greatly reduces the number of route-request packets transmitted in the route-discovery process. We compare the performance of our algorithm with the well known Ad-hoc On-demand Distance Vector (AODV) routing algorithm. On average, our algorithm needs less than 12.6% of the routing-control packets needed by AODV. Simulation results also show that our algorithm has a higher packet-delivery ratio and lower average end-to-end delay than AODV.     

An extended least-hop distributed routing algorithm

A routing strategy called NELHNET has been developed for networks with multiprecedence traffic and operating under dynamic traffic and topological conditions. An adaptive distributed algorithm that uses least-hop and least-hop-plus-1 routes in a table of routing vectors, as opposed to the usual table of routing scalars, is described. Current delays are passed backward and forward with the packets to allow development of expected delays to each node via all acceptable routes. The route then selected is the acceptable route with the least expected delay. For speedier recovery, a node returning to service receives the current network status from an adjoining node as soon as the link connecting them is operational. The resultant algorithms show far greater than the marginal improvements originally expected over Arpanet simulations. NELHENET strategies also permit the network to function stably under more heavily loaded conditions than do the Arpanet strategies     

一种基于跨层设计和蚁群优化的自组网负载均衡路由协议

针对大部分现有替代路径共同存在的替代路径老化和构建效率问题,本文提出了一种基于跨层设计和蚁群优化的负载均衡路由协议(CALRA),利用蚁群优化算法特有的信息素挥发方法实现对替代路径的老化问题,将蚁群优化和跨层优化方法结合起来解决自组网中的负载均衡问题,通过双向逐跳更新的方式较好的解决了替代路径构建效率问题,并将蚂蚁在所经过的各中间节点为路由表带来的信息素增量映射为蚂蚁离开源节点的距离、移动过程中所遇到的节点拥塞程度、节点当前信息素浓度和节点移动速度等各协议层的统计信息的函数,通过对各种信息所对应的参数赋予不同加权值的方法对概率路由表进行控制,改善了自组网中现有基于蚁群优化的路由协议中普遍存在的拥塞问题、捷径问题、收敛速度问题和引入的路由开销问题.仿真表明,CALRA在分组成功递交率、路由开销、端到端平均时延等方面具有优良性能,能很好地实现网络中的业务负载均衡.     

Link State Routing Based on Compressed Sensing

In table routing protocols such as link state routing, every node in the network periodically broadcasts its link state and the state of its neighbors. These routing updates result in the transmission of a large number of packets. Some of these packets contain correlated or even redundant data which could be compressed if there is central management in the network. However, in autonomous networks, each node acts as a router, in which case central coordination is not possible. In this paper, compressed sensing is used to reduce routing traffic overhead. This can be done at nodes which have greater processing capabilities and no power consumption limitations such as backbone nodes in wireless mesh networks. A method is proposed to select a subset of nodes and thus a subset of links to probe their state. The sensed states are encoded to generate a low dimension sampled vector. This compressed link state vector is broadcast to the entire network. Nodes can then reconstruct link states from this vector using side information. Performance results are presented which demonstrate accurate anomaly detection while adapting to topology changes. Further, it is shown that a proper choice of weighting coefficients in the sampling process can improve detection performance.     

具有传输成功率保证的概率路由算法的TTL预测模型

概率路由算法是机会网络中一种常用的路由算法,其TTL的设置将直接影响路由的性能.本文首先利用马尔可夫链对概率路由的转发过程进行建模,并从消息的传输成功率和传输延时方面进行性能评估,不仅可以计算出一个消息从源节点到目的节点所需的传输延时,还可以预测出在给定传输成功率下所需要的最短消息生存周期TTL,这对于TTL的设置具有理论上的指导作用.其次,本文建立的预测模型还可以使一些无法到达目的节点的消息及时被删除,从而减少不必要的转发,达到节约网络资源的目的.最后,在两个真实数据集中的实验结果表明,本文提出的模型能够为概率路由中TTL值的准确设置提供有效参考.