Adaptive deadlock- and livelock-free routing with all minimal pathsin torus networks

This paper consists of two parts. In the first part, two new algorithms for deadlock- and livelock-free wormhole routing in the torus network are presented. The first algorithm, called Channels, is for the n-dimensional torus network. This technique is fully-adaptive minimal, that is, all paths with a minimal number of hops from source to destination are available for routing, and needs only five virtual channels per bidirectional link, the lowest channel requirement known in the literature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literature for packet-switched fully-adaptive minimal routing. The second algorithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual channels per bidirectional link. Also, it allows for a highly parallel implementation of its associated routing node. In the second part of this paper, four worm-hole routing techniques for the two-dimensional torus are experimentally evaluated using a dynamic message injection model and different traffic patterns and message lengths     

Adaptive routing with stale information

We investigate the behaviour of load-adaptive rerouting policies in the Wardrop model where decisions must be made on the basis of stale information. In this model, each one of an infinite number of agents controls an infinitesimal amount of flow, thus contributing to a network flow which induces latency. In our dynamic extension of this model, agents are activated in a concurrent and asynchronous fashion and may reroute their flow with the aim of reducing their sustained latency. It is a well-known problem that in settings where latency information is not always up-to-date, such behaviour may lead to oscillation effects which seriously harm network performance. Two quantities determine the difficulty of avoiding oscillation: the steepness of the latency functions and the maximum possible age of the information T$T$.     

Adaptive routing for road traffic

The article reports on an integrated system which uses road congestion information to guide routing, both in advance and while in transit. It offers two novel features: historic information about congestion is collected and retained for use when planning routes; and GPS tracks vehicles while they undertake journeys, and the Global System for Mobile Communications (GSM) Short Message Service (SMS) maintains communications between a moving vehicle and a central planning service to suggest revised routes avoiding congestion     

A simple livelock-free algorithm for packet switching

Store-and-forward deadlock (SFD) occurs in packet switched computer networks when, among some cycle of packets buffered by the communication system, each packet in the cycle waits for the use of the buffer currently occupied by the next packet in the cycle. In this paper, a deadlock-free algorithm as well as a livelock-free algorithm for packet switching is obtained using the strategy of the banker's algorithm. Furthermore, the solution obtained is interpreted for the hyper-fast banker's problem.     

Adaptive fault-tolerant routing in cube-based multicomputers usingsafety vectors

Reliable communication in cube-based multicomputers using the safety vector concept is studied in this paper. In our approach, each node in a cube-based multicomputer of dimension n is associated with a safety vector of n bits, which is an approximated measure of the number and distribution of faults in the neighborhood. The safety vector of each node can be easily calculated through n-1 rounds of information exchange among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source and destination nodes. The concept of dynamic adaptivity is introduced, representing the ability of a routing algorithm to dynamically adjust its routing adaptivity based on fault distribution in the neighborhood. The feasibility of the proposed unicasting can be easily determined at the source node by comparing its safety vector with the Hamming distance between the source and destination nodes. The proposed unicasting can also be used in disconnected hypercubes, where nodes in a hypercube are disjointed (into two or more parts). We then extend the safety vector concept to general cube-based multicomputers     

Adaptive inter-layer message routing in 3D networks-on-chip

Existing routing algorithms for 3D deal with regular mesh/torus 3D topologies. Today 3D NoCs are quite irregular, especially those with heterogeneous layers. In this paper, we present a routing algorithm targeting 3D networks-on-chip (NoCs) with incomplete sets of vertical links between adjacent layers. The routing algorithm tolerates multiple link and node failures, in the case of absence of NoC partitioning. In addition, it deals with congestion. The routing algorithm for 3D NoCs preserves the deadlock-free propriety of the chosen 2D routing algorithms. It is also scalable and supports a local reconfiguration that complements the reconfiguration of the 2D routing algorithms in case of failures of nodes or links. The algorithm incurs a small overhead in terms of exchanged messages for reconfiguration and does not introduce significant additional complexity in the routers. Theoretical analysis of the 3D routing algorithm is provided and validated by simulations for different traffic loads and failure rates.     

Adaptive routing protocols for hypercube interconnection networks

A taxonomy for characterizing adaptive routing protocols for hypercube interconnection networks (HINs) is presented. The taxonomy is based on classes of routing decisions common to any HIN. This taxonomy is used to discuss existing and proposed protocols. Rather than an exhaustive enumeration of related research, the protocols selected for discussion are intended to be representative of the classes defined by the taxonomy. These protocols are candidates for use in massively parallel architectures configured with HINs. To provide some insight into their behavior in very large HINs, results of simulation studies of representative protocols are presented     

Adaptive routing in wormhole-switched necklace-cubes: Analytical modelling and performance comparison

The necklace hypercube has recently been introduced as an attractive alternative to the well-known hypercube. Previous research on this network topology has mainly focused on topological properties, VLSI and algorithmic aspects of this network. Several analytical models have been proposed in the literature for different interconnection networks, as the most cost-effective tools to evaluate the performance merits of such systems. This paper proposes an analytical performance model to predict message latency in wormhole-switched necklace hypercube interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has been shown to be the most effective for necklace hypercube networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions.     

自组网环境下具有能量和移动感知的自适应路由协议

自组网是由一组带有无线收发装置的移动节点组成的一个能够支持多跳的临时性的通信网络,动态拓扑变化是它的最大特征之一;此外,由于自组网的大多数节点是由有限寿命的电池来提供的,能量保护策略成为设计该类网络协议的一个重要依据。文章提出了一种基于动态源路由的具有能量和移动感知的自适应路由协议,仿真表明该协议有效地延长了网络的生存时间,并提高了网络吞吐量。     

自适应的移动Ad hoc网络贪婪地理路由协议

通过分析传统的基于地理位置的路由协议在比较困难的环境下很难取得理想的高可靠性、低负载的问题,提出了一种自适应的贪婪地理路由协议。该协议总结了对网络移动性能造成影响的两个因素,即节点移动速度和停留时间,自动调整节点发送信标的周期和选择下一跳的方案,从而达到减少负载和增加转发成功率的目的。仿真结果显示,该协议在两方面都取得了较好的效果。     

面向WSN安全路由协议的自适应威胁模型

针对无线传感器网络路由发现过程中安全性评估问题,提出一种新的自适应威胁模型。该模型通过对传统Dolev-Yao模型进行改进,将攻击分为限定接收传输范围的单个攻击者到不限定任何能力的多个共谋攻击者等九类,在无须任何安全假设的情形下对不同路由发现过程的攻击进行分类安全评估,自适应地确定破坏协议时的攻击强度和破坏协议所需的最小攻击强度,以评估路由发现协议的安全性,进而采取相应的安全措施予以预防。最后以一类无线传感器网络自适应威胁模型为实例,说明该模型的正确性、有效性。     

多信道无线网状网自适应路由算法

针对无线网状网的网络容量优化问题,通过建立无线网状网容量优化的数学模型,利用线性规划公式对无线网状网的路由问题进行描述,在此基础上提出了一个自适应路由算法。根据网络的拓扑结构和业务请求特点,自适应地改变路由扩张因子和负载均衡率进行优化路由,达到提高无线网状网的网络容量的目的。仿真结果表明,该算法能明显提高网络容量。     

Adaptive and deadlock-free routing for irregular faulty patterns inmesh multicomputer

Message routing achieves the internode communication in parallel computers. A reliable routing is supposed to be deadlock-free and fault-tolerant. While many routing algorithms are able to tolerate a large number of faults enclosed by rectangular faulty blocks, there is no existing algorithm that is capable of handling irregular faulty patterns for wormhole networks. In this paper, a two-staged adaptive and deadlock-free routing algorithm called “Routing for Irregular Faulty Patterns” (RIFP) is proposed. It can tolerate irregular faulty patterns by transmitting messages from sources or to destinations within faulty blocks via multiple “intermediate nodes.” A method employed by RIFP is first introduced to generate intermediate nodes using the local failure information. By its aid, two communicating nodes can always exchange their data or intermediate results if there is at least one path between them. RIFP needs two virtual channels per physical link in meshes     

WSN自适应负载均衡集簇分层路由协议

结合考虑传统无线传感器网络(wireless sensor networks,WSN)路由协议特点以及实际应用中节点的不对等性,提出了一种自适应负载均衡集簇分层路由协议——ALBCH.该协议在簇头选举时引入剩余能量等相关因子,将贪婪算法成链机制分别引入分层路由协议的簇内通信和簇头间通信,对贪婪算法成链机制进行了一些改进.仿真结果表明,ALBCH能更有效地均衡网络负载,具有更好的健壮性和更高的实时性能,同时解决了传统协议在处理异构网络时的局限性.     

Adaptive routing protocol for mobile ad hoc networks

Artificial immune systems (AIS) are used for solving complex optimization problems and can be applied to the detection of misbehaviors, such as a fault tolerant. We present novel techniques for the routing optimization from the perspective of the artificial immunology theory. We discussed the bioinspired protocol AntOR and analyze its new enhancements. This ACO protocol based on swarm intelligence takes into account the behavior of the ants at the time of obtaining the food. In the simulation results we compare it with the reactive protocol AODV observing how our proposal improves it according to Jitter, the delivered data packet ratio, throughput and overhead in number of packets metrics.     

DTN中基于节点质量的自适应散发和等待路由

针对节点活动性的差异,给出了节点质量的定义,提出了基于节点质量的自适应散发和等待路由协议。该协议通过引入节点质量的观点来动态地转发报文拷贝数,从而避免了二分散发和等待路由协议在转发报文拷贝数时的盲目性。仿真结果显示,该协议更能够适应自组织状况下动态的网络拓扑,在改善报文递交率和延迟的同时能显著提高报文的递交效用、减小网络开销率。     

Adaptive state-based multi-radio multi-channel multi-path routing in Wireless Mesh Networks

Wireless Mesh Networks (WMNs) are envisioned to seamlessly extend the network connectivity to end users by forming a wireless backbone that requires minimal infrastructure. Unfortunately for WMNs, frequent link quality fluctuations, excessive load on selective links, congestion, and limited capacity due to the half-duplex nature of radios are some key limiting factors that hinder their deployment. To address these problems, we propose a novel Adaptive State-based Multi-path Routing Protocol (ASMRP), which constructs Directed Acyclic Graphs (DAGs) from each Mesh Router (MR) to Internet Gateways (IGWs) and effectively discovers multiple optimal path set between any given MR-IGW pair. A congestion aware traffic splitting algorithm to balance traffic over these multiple paths is presented which synergistically improves the overall performance of the WMNs. We design a novel Neighbor State Maintenance module that innovatively employs a state machine at each MR to monitor the quality of links connecting its neighbors in order to cope with unreliable wireless links. We also employ a 4-radio architecture for MRs, which allows them to communicate over multiple radios tuned to non-overlapping channels and better utilize the available spectrum. Through extensive simulations using ns-2, we observe that ASMRP substantially improves the achieved throughput (～5 times gain in comparison to AODV), and significantly minimizes end-to-end latencies. We also show that ASMRP ensures fairness in the network under varying traffic load conditions.     

一种基于散列链的自适应网格安全路由协议

LEACH(Low Energy Adaptive Clustering Hierarchy)路由协议是无线传感器网络拓扑控制中最具代表性和重要性的算法之一。针对LEACH路由协议簇头分布不均匀,节点死亡率高,易产生路由空洞及其所面临安全威胁等问题,提出一种基于散列链的区域划分网格自治安全路由协议LEACH-SEED。剔除低能量节点入选簇头的权利,改进簇头选举机制,簇头选举完成之后,每个簇头节点随机从散列链组成的密钥池中分配q个链密钥,其他节点利用单向哈希函数和伪随机函数生成通信密钥,网络遭受攻击后利用网格自治和待选簇头身份标识编号进行网络恢复。实验结果表明,改进的分簇算法能有效地降低节点死亡率,增强抗攻击能力,提高数据融合度,延长网络生存时间。     

Adaptive wormhole routing in k-ary n-cubes

Distributed memory multiprocessor (DMMP) systems have gained much attention because their performance can be easily scaled up by increasing the number of processor-memory modules. The k-ary n-cube is the most popular interconnection network topology currently used in DMMPs. Wormhole routing is one of the most promising switching technology and has been used in many new generation multicomputers. Wormhole routing makes the communication latency insensitive to the network diameter and reduces the size of the channel buffer of each router. The concept of virtual channels and virtual networks are widely invented for deadlock-free design. A fully adaptive wormhole routing method for k-ary n-cubes has been proposed by Linder in 1991 [10]. Unfortunately, the need of 2^{n − 1} virtual networks makes it unreasonable. In this paper, we propose a virtual network system to support an adaptive, minimal and deadlock free routing in k-ary n-cubes. It uses only four virtual networks but can get a higher degree of adaptability and higher traffic capacity. Simulation results are presented to verify the performance.     

Adaptive memory programming for the vehicle routing problem with multiple trips

The Vehicle Routing Problem with Multiple Trips is an extension of the classical Vehicle Routing Problem in which each vehicle may perform several routes in the same planning period. In this paper, an adaptive memory algorithm to solve this problem is proposed. Computational experience is reported over a set of benchmark problem instances.