A distributed routing algorithm for multihop packet radio networkswith uni- and bi-directional links

Multihop packet radio networks require routing algorithms which are distributed in nature and which have the ability to timely detect changes in the network topology. These changes are mostly changes in connectivity caused by link or node failures and by the relative motion of the nodes. This paper describes and analyzes an adaptive decentralized routing algorithm for packet radio networks. The network connectivity, as perceived by each node, is translated into a graph representation of the network. The proposed routing mechanism then uses a breadth-first search algorithm along the inbound links of such a graph. Unlike most of the algorithms found in the open literature the one proposed here can be used in networks having both uni- and bi-directional radio links. Examples are shown to illustrate the methodology     

Fault-tolerant routing algorithms using estimator discretizedlearning automata for high-speed packet-switched networks

We present an adaptive routing algorithm (VP-LA) for high speed packet-switched networks. We use the source routing strategy. VP-LA uses anew S-Model Ergodic Discretized Estimator Learning Automaton (SEDEL), specially designed for the routing problem, to select accurately and rapidly the minimum delay routes in high-speed packet-switched networks. The estimator provides VP-LA with excellent fault-tolerant properties. Moreover, the VP-LA is E-optimal. VP-LA was extensively simulated; the results showed the superiority of VP-LA over other source and link-by-link routing algorithms. VP-LA performs quite well even where the network feedback is misleading, and can be easily and efficiently applied because of its reduced complexity and overhead     

基于内建自测技术的Mesh结构NoC无虚通道容错路由算法

 在Zhang's算法绕行思想的基础上,提出了一种2D-Mesh结构片上网络无虚通道容错路由算法,用于解决多故障节点情况下片上网络的无虚通道容错路由问题.算法利用内建自测试机制获取故障区域的位置信息,通过优化绕行策略来均衡故障区域周围链路的负载并减少部分数据的绕行距离.针对8×8的2D-Mesh网络的仿真表明,与Chen's算法相比,在故障区域大小为2×2,网络时延为70 cycles的情况下,随着故障区域位置的变化所提算法可提高1.2%到4.8%的网络注入率.且随着故障区域面积的扩大,所提算法在减少通信时延,提高网络吞吐量方面的作用更为明显.     

A Region-based Fault-Tolerant Routing Algorithmfor 2D Irregular Mesh Network-on-Chip

This paper presents a deadlock-free fault-tolerant routing algorithm for irregular mesh network-on-chips based on a region-based approach. In this approach, a set of rectangular faulty regions called faulty blocks is formed for faulty nodes and a detour path is defined for each faulty block to indicate how packets must detour thefaulty block. The most recent routing algorithm on this approach is Message-Route (Holsmark and Kumar J Inf Sci Eng 23:1649–1662, 2007) which does not have restrictions on the number of tolerable faulty nodes and its distribution. However, this algorithm has three crucial problems; (1) this algorithm fails to provide complete and deadlock-free routing, (2) many nonfaulty nodes are contained in faulty blocks and thus deactivated, and (3) complex routing functions are not feasible for hardware implementation. In this paper, we give a solution for each of the above three problems. We correct the errors of Message-Route to make it complete and deadlock-free. Then, we propose a deadlock-free fault-tolerant routing algorithm which can work under small-sized faulty blocks with a simple routing control. Experimental results show that the proposed algorithm significantly reduces the size of faulty blocks and improves communication latency for both random and cluster faults. Moreover, an FPGA implementation of the proposed algorithm is also discussed.     

Survivable routing in IP-over-WDM networks: An efficient and scalable local search algorithm

In IP-over-WDM networks, a logical IP network is routed on top of a physical optical fiber network. An important challenge here is to make the routing survivable. We call a routing survivable if the connectivity of the logical network is guaranteed in the case of a failure in the physical network. In this paper we describe FastSurv, a local search algorithm for survivable routing. The algorithm works in an iterative manner: after each iteration it learns more about the structure of the logical graph and in the next iteration it uses this information to improve its solution. The algorithm can take link capacity constraints into account and can be extended to deal with multiple simultaneous link failures and node failures. In a large series of tests we compare FastSurv with current state-of-the-art algorithms for this problem. We show that it can provide better solutions in much shorter time, and that it is more scalable with respect to the number of nodes, both in terms of solution quality and run time.     

Providing Fault-Tolerant Ad hoc Routing Service in Adversarial Environments

Most existing designs of ad hoc networks are based on the assumption of non-adversarial environments, where each node in the network is cooperative and well-behaved. When misbehaving nodes exist in the network, the performance of current routing protocols degrades significantly. Since ad hoc networks, consisting of autonomous nodes, are open and distributed in nature, maintaining a fault-free network environment is extremely difficult and expensive. In this paper, we propose a new routing service named best-effort fault-tolerant routing (BFTR). The design goal of BFTR is to provide packet routing service with high delivery ratio and low overhead in presence of misbehaving nodes. Instead of judging whether a path is good or bad, i.e., whether it contains any misbehaving node, BFTR evaluates the routing feasibility of a path by its end-to-end performance (e.g. packet delivery ratio and delay). By continuously observing the routing performance, BFTR dynamically routes packets via the most feasible path. BFTR provides an efficient and uniform solution for a broad range of node misbehaviors with very few security assumptions. The BFTR algorithm is evaluated through both analysis and extensive simulations. The results show that BFTR greatly improves the ad hoc routing performance in the presence of misbehaving nodes.     

Adaptive Optimization-based Routing in Wireless Mesh Networks

Routing is a critical component in wireless mesh networks. The inherent shared-medium nature of the wireless mesh networks, however, poses fundamental challenges to the design of effective routing policies that are optimal with respect to the resource utilization. Node churns and traffic fluctuations exacerbate such a problem. In this paper, we propose a novel adaptive routing algorithm for multiple subscribers in wireless mesh networks. We view a mesh network with multiple nodes as an entity that optimizes some global utility function constrained by the underlying MAC layer interference. By solving the optimization problem, the network is driven to an efficient operating point with a certain routing policies for each node. We then use this operating point information to adaptively find better paths, which is able to gear the network towards optimal routing. Further, we take the fluctuations of the network into consideration and thus render our algorithm more robust for a variety of network situations. Simulations demonstrate the efficiency and efficacy of our algorithm.     

具有扩展局部连通性超立方体中的容错路由

在局部连通性的基础上,提出了针对超立方体网络Hn的扩展的局部k-维子立方体连通性概念,证明了具有扩展的局部k-维子立方体连通性的Hn中正确结点问是连通的;提出了超立方体网络Hn中基于扩展局部k-堆子立方体连通性的路由算法。     

Dimensioning of adaptively routed networks

The authors present an algorithm for the multihour dimensioning of telephone networks operating with residual capacity adaptive routing. The method is based on dimensioning techniques for networks operating with nonhierarchical alternate routing and relies on a conservative approximation for traffic evaluation. It is a decomposition method involving a set of fixed-point equations which are solved iteratively until the Kuhn-Tucker conditions are met. The authors investigate the convergence of the method and find that some of the variables of the model are almost stationary after only a few iterations. This leads to some simplifications that make it suitable for large networks with minor modifications. They also investigate the optimality of adaptive routing by comparing it with the optimal routing coefficients and verify the operation of this routing in a network dimensioned for adaptive technique. A question of interest is how well an adaptive algorithm can adapt to dimensioning errors and how well it compares with the optimal routing in these situations     

基于蚁群算法的自适应QoS路由优化

Internet网络规模的迅速增长和网络技术的不断完善，使得如何在满足QoS（quality of service）要求下进行路由选择成为路由算法研究的重要方向。提出了一种多约束条件下的自适应蚁群算法，该算法基于目标函数的信息素分配策略来自适应地调整蚂蚁的搜索行为，使多约束QoS路由优化问题得到了很好的解决。     

一种自选路由ATM容错交换网络

本文提出一种自选路由ＡＴＭ容错交换网络结构，网络通过在基准网的级间增加交换单元来增加输入到输出间的通路，进而达到容错的目的，它具有选路简单，可提高交换网络性能的优点，与同等硬件量的其它容错方案比较，它可容纳更多的网络内部故障，且随着网络规模的增大，效果更明显。     

基于网络监控器的专用片上网络动态容错路由

针对专用片上网络（Network on Chip,NoC）全局通信事务管理和可靠性设计问题,提出片上网络监控器的概念,用于获取全局网络实时状态信息及执行路径分配算法,基于此提出一种动态路由机制DyRS-NM.该机制能检测和定位NoC中的拥塞和故障链路,并能区分瞬时和永久性链路故障,采用重传方式避免瞬时故障,通过重新路由计算绕开拥塞和永久性故障.设计实现了RTL级网络监控器和与之通信的容错路由器模块,并将MPEG4解码器应用映射至基于网络监控器的4×4Mesh结构NoC体系结构中,验证了系统性能以及面积功耗开销.相比静态XY路由和容错动态路由FADR,DyRS-NM机制在可接受的开销代价下获得了更优的性能.     

Constructions of link-fault-tolerant q-ary k-cube networks

A technique for constructing fault-tolerant q-ary k-cube networks for an arbitrary positive integer q is investigated. Extra sets of links are added to construct the fault-tolerant network such that in the presence of link faults, the remaining healthy portion is guaranteed to contain an original fault-free network. Linear codes over an integer ring are used for this approach     

A fault-tolerant switching network for B-ISDN

The author proposes a self-routing fault-tolerant switching network for asynchronous transfer mode (ATM) switching systems. The network has many subswitches to enhance the fault tolerance of the conventional multistage interconnection network which only has a unique path. The subswitches provide large numbers of alternative paths between switching stages and allow the network to tolerate multiple paths. The routing algorithm is quite simple. The paths can also be used to route cells under the condition that internal cell contentions occur in switching elements. A reliability analysis shows a quantitative measurement of the improvement in fault tolerance as compared with previously presented fault-tolerant networks. A performance analysis and simulation results show that the proposed network has a high level of maximum throughput. In addition, that level of throughput is maintained with reasonable cell delay even though the number of faulty components increases in the network     

Traffic engineering in next-generation optical Networks

In this article traffic-engineering issues regarding network survivability, traffic grooming, impairment-aware routing, virtual-topology engineering, and coordination among multiple layers of network architecture will be reviewed for next-generation optical networks based on Wavelength-Division Multiplexing (WDM). Due to the recent progress and development of WDM technology, increasing traffic demands can be readily accommodated in the next-generation optical networks. In spite of the huge amount of capacity (e.g., OC-192) provided by a WDM channel, enhanced network services and network performance improvement can only be achieved with efficient traffic-engineering mechanisms. The fault-tolerant function is essential in order to provide seamless services to users by protecting their traffic against failures in the optical network because many connections can be carried on a fiber. Because the capacity of a WDM channel is very large, its bandwidth may not be efficiently utilized by a single connection. Hence, low-rate user connections need to be efficiently aggregated through the traffic-grooming scheme. An intelligent routing algorithm is especially necessary in the optical network where signal impairments due to device imperfections might degrade the signal quality. In addition, the virtual network connectivity (topology) should be flexibly maintained such that dynamic changes to the traffic demands can be easily absorbed, which can be implemented by the virtualtopology engineering method in a WDM network. As the dominant usage of Internet Protocol (IP) of the Internet is expected to reside directly above the WDM layer in the future network, the coordinated trafficengineering scheme should be deliberately designed for the multi-layer network by judiciously choosing where to put many overlapping functions in the different network layers.     

Generic prediction assisted single-copy routing in underwater delay tolerant sensor networks

One challenge in delay tolerant networks (DTNs) is efficient routing, as the lack of contemporaneous end-to-end paths makes conventional routing schemes inapplicable. Although many DTN routing protocols have been proposed, they often have two limitations: many protocols are not mobility cognizant, so they only suit specific mobility models and become inefficient when the environment changes; some protocols employ multi-copy replication to accommodate mobility diversity for increased delivery probability or reduced delay, but they usually do not perform well in resource constrained networks. Due to the unique characteristics of underwater sensor networks (UWSNs), efficient DTN routing becomes even more challenging. In this paper, we propose a generic prediction assisted single-copy routing (PASR) scheme that can be instantiated for different mobility models. PASR first collects a short-duration trace with network connectivity information and employs an effective off-line greedy algorithm to characterize the underlying network mobility patterns, depict the features of best routing paths and provide guidance on how to use historical information. Then it instantiates prediction assisted single-copy online routing protocols based on the guidance. As a result, the instantiated protocols are energy efficient and cognizant of the underlying mobility patterns. We demonstrate the advantages of PASR in underwater sensor networks with various mobility models.     

An energy‐efficient localized topology control algorithm for wireless ad hoc and sensor networks

Topology control plays an important role in the design of wireless ad hoc and sensor networks and has demonstrated its high capability in constructing networks with desirable characteristics such as sparser connectivity, lower transmission power, and smaller node degree. However, the enforcement of a topology control algorithm in a network may degrade the energy‐draining balancing capability of the network and thus reduce the network operational lifetime. For this reason, it is important to take into account energy efficiency in the design of a topology control algorithm in order to achieve prolonged network lifetime. In this paper, we propose a localized energy‐efficient topology control algorithm for wireless ad hoc and sensor networks with power control capability in network nodes. To achieve prolonged network lifetime, we introduce a concept called energy criticality avoidance and propose an energy criticality avoidance strategy in topology control and energy‐efficient routing. Through theoretical analysis and simulation results, we prove that the proposed topology control algorithm can maintain the global network connectivity with low complexity and can significantly prolong the lifetime of a multi‐hop wireless network as compared with existing topology control algorithms with little additional protocol overhead. Copyright © 2008 John Wiley & Sons, Ltd.     

Self-organization of sensor networks for detection of pervasive faults

Resource aware operation of sensor networks requires adaptive re-organization to dynamically adapt to the operational environment. A complex dynamical system of interacting components (e.g., computer network and social network) is represented as a graph, component states as spins, and interactions as ferromagnetic couplings. Using an Ising-like model, the sensor network is shown to adaptively self-organize based on partial observation, and real-time monitoring and detection is enabled by adaptive redistribution of limited resources. The algorithm is validated on a test-bed that simulates the operations of a sensor network for detection of percolating faults (e.g. computer viruses, infectious disease, chemical weapons, and pollution) in an interacting multi-component complex system.     

Coordinated dual-homing in designing hierarchical wireless access network with a genetic algorithm based approach

With the growth of mobile users and the increasing deployment of wireless access network infrastructures, the issue of fault tolerance is becoming an important component of efficient wireless access network design. In this work, we study a survivable hierarchical network design problem. Given the available capacity, connectivity, and reliability at each level, the problem is to minimize overall connection cost for multiple requests such that the capacity, connectivity, and minimum survivability constraints are not violated. Our study is different than earlier research in regard to the coordination of multiple layers of access networks. The connectivity to the core network may be fully or partially dual-homed paths, or may be single-homed paths. Dual-homing schemes spanning to different levels in the network hierarchy are used if the single-homed connectivity is not enough to guarantee the minimum required survivability. We formulate the problem using mixed integer linear programming and prove the complexity class to be NP-hard. We then propose an off-line genetic algorithm based meta-heuristic. Given the complexity of the problem, simulation results demonstrate that the proposed approach is viable in designing fault-tolerant access networks with dual-homing capability.     

On adaptive routing in urban vehicular networks

Efficient data delivery in vehicular networks has received increasing attention in recent years. Existing routing protocols for vehicular networks can be loosely divided into two classes: road based routing (RBR) and road oblivious routing (ROR). RBR finds a routing path along roads while ROR does not explicitly forward packets along roads. Our empirical study based on real trace-driven experiments shows that using either of an RBR algorithm or an ROR algorithm alone in a realistic vehicular network setting leads to deficiency. This results from the fact that network conditions can be different at different locations and evolving over time. Motivated by this important observation, this paper proposes an adaptive routing algorithm called RWR that adapts its routing strategy to network dynamics as the packet travels from the source to the destination. Extensive simulations based on a large dataset of real vehicular traces collected from around 2,600 taxis in Shanghai have been conducted. Comparison study shows that RWR produces higher delivery ratio than TSF and GPCR, representative routing algorithms of RBR and ROR, respectively. It achieves low delivery delay at the same time.