Fault-tolerant communication with partitioned dimension-orderrouters

The current fault-tolerant routing methods require extensive changes to practical routers such as the Cray T3D's dimension-order router to handle faults. In this paper, we propose methods to handle faults in multicomputers with dimension-order routers with simple changes to router structure and logic. Our techniques can be applied to current implementations in which the router is partitioned into multiple modules and no centralized crossbar is used. We consider arbitrarily located faulty blocks and assume only local knowledge of faults. We apply our techniques for torus networks and show that, with as few as four virtual channels per physical channel, deadlock- and livelock-free routing can be provided even with multiple faults and multimodule implementation of routers. Our simulations of the proposed technique for 2D tori and mesh indicate that the performance degradation is similar to that seen in the case of cross-bar based designs previously proposed     

环网中的维度气泡流控与自适应路由算法

介绍了一个称为环网维度气泡流控(TDBFC)的新型流控策略和称为环网维度气泡路由(TADBR)算法的新型自适应路由算法.在Bubble流控和DBFC流控的基础上设计了适合于环网的维度气泡流控.在环网中,如果采用TDBFC流控策略,设计的TADBR自适应路由算法可实现无死锁的最短距离的路由.对于以上结论,提供了详细的证明.最后,介绍了自行设计的模拟工具RingNetSim,该模拟器实现了TDBFC流控策略和TADBR算法.在RingNetSim上分析了TADBR算法的性能,结果显示环网维度气泡路由算法拥有较好的性能.     

基于卫星网的路由算法研究及其伪代码实现

路由问题在通信网中一直是一个核心问题，路由算法的优劣将直接影响到整个通信网络的性能以及通信的质量，在卫星网络中也不例外。由于卫星网络具有区别于地面网络的拓扑结构的动态变化等独有的特点，使得适用于地面网络的路由算法不能用于卫星网络上，因此必须针对卫星网络的特点设计适合于卫星网络的路由算法。本文先阐述了路由算法的影响因素及设计目标，然后提出了一种运行于卫星网络上的基于时空的路由算法，给出了算法的详细步骤，并详细介绍了算法的伪代码实现。实验表明该算法能很好地满足卫星网络的要求。     

一种构建超大规模数据中心的模块化网络结构

模块化数据中心网络的模块间互联结构和路由负责模块的有效组织,以及不同模块服务器间的高效通信.为此,如何设计具有高带宽、高容错和高可扩展能力的互联结构以支持大规模、超大规模数据中心的构建成为模块化数据中心网络需要解决的首要问题.提出了一种构建超大规模模块化数据中心的模块间互联结构MDKautz,该结构通过模块内大量未被使用的交换机预留高速端口将模块以Kautz图互连,在无需额外增加任何高端交换设备的前提下,构造出具有高带宽、高容错和灵活可持续扩展性的超大规模数据中心网络.对MDKautz的构建方法、路由策略以及扩展方法进行了分析,数学分析和模拟实验结果证明了该新型网络结构具有良好的拓扑特性和通信性能,可有效支持数据中心高带宽、高容错的典型应用.     

基于Bayes与多层Bayes估计的WSN链路选择算法

无线传感器网络（WSN）节点能量有限,采用传统的链路选择的方法（经验法）进行链路选择,需要发送大量的数据包作为测试样本,这在WSN中是不合适的。设计了两种基于Bayes估计与一种基于多层Bayes估计的WSN链路选择算法,分别记为BLSP-B1、BLSP-B2、BLSP-HE。仿真实验发现,在小样本的条件下,BLSP-B1、BLSP-B2、BLSP-HE选择高质量的链路的概率比经验法要高出10%～20%,其中BLSP-HE算法最稳健,性能较好。     

Design and performance analysis of an inductive QoS routing algorithm

Routing mechanism is key to the success of large-scale, distributed communication and heterogeneous networks. Consequently, computing constrained shortest paths is fundamental to some important network functions such as QoS routing and traffic engineering. The problem of QoS routing with multiple additive constraints is known to be NP-complete but researchers have been designing heuristics and approximation algorithms for multi-constrained paths algorithms to propose pseudo-polynomial time algorithms. This paper introduces a polynomial time approximation quality of service (QoS) routing algorithm and constructs dynamic state-dependent routing policies. The proposed algorithm uses an inductive approach based on trial/error paradigm combined with swarm adaptive approaches to optimize lexicographically various QoS criteria. The originality of our approach is based on the fact that our system is capable to take into account the dynamics of the network where no model of the network dynamics is assumed initially. Our approach samples, estimates, and builds the model of pertinent aspects of the environment which is very important in heterogeneous networks. The algorithm uses a model that combines both a stochastic planned pre-navigation for the exploration phase and a deterministic approach for the backward phase. Multiple paths are searched in parallel to find the K best qualified ones. To improve the overall network performance, a load adaptive balancing policy is defined and depends on a dynamic traffic path probability distribution function. We conducted a performance analysis of the proposed QoS routing algorithm using OPNET based on a platform simulated network. The obtained results demonstrate substantial performance improvements as well as the benefits of learning approaches over networks with dynamically changing traffic.     

卫星时变拓扑网络最短路径算法研究

在提出卫星时变拓扑网络模型的基础上,首先证明了传统网络中的最短路径算法（如Dijkstra算法）在卫星时变拓扑网络中使用存在局限性,给出了一种可适用于卫星时变拓扑网络的最短路径算法并利用卫星节点间邻居关系的相对规律性,对算法进行了优化．相关仿真表明该算法比目前常用的卫星网络路由算法（如DVTR）更适合于切换频繁的卫星网络．     

Distributed iterative aggregation algorithms for box-constrainedminimization problems and optimal routing in data networks

A gradient-projection algorithm using iterative aggregation and disaggregation is proposed and analyzed for box-constrained minimization problems. In a distributed computation model, the algorithm is shown to converge. The algorithm is applied to optimal routing in a large interconnected data communication network, resulting in a multilevel hierarchical clustering that naturally fits the hierarchical topological structure of such networks. An implementation of the algorithm for a 52-node network shows that the serial version of the algorithm has a saving of 35% of the computational time as compared to a path-formulated gradient-projection code that is among the fastest existing programs for path-formulated optimal routing     

Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology cannot ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.     

An agent-assisted QoS-based routing algorithm for wireless sensor networks

Existing routing algorithms are not effective in supporting the dynamic characteristics of wireless sensor networks (WSNs) and cannot ensure sufficient quality of service in WSN applications. This paper proposes a novel agent-assisted QoS-based routing algorithm for wireless sensor networks. In the proposed algorithm, the synthetic QoS of WSNs is chosen as the adaptive value of a Particle Swarm Optimization algorithm to improve the overall performance of network. Intelligent software agents are used to monitor changes in network topology, network communication flow, and each node's routing state. These agents can then participate in network routing and network maintenance. Experiment results show that the proposed algorithm can ensure better quality of service in wireless sensor networks compared with traditional algorithms.     

Comparing Adaptive Routing and Dynamic Voltage Scaling for Link Power Reduction

We compare techniques that dynamically scale the voltage of individual network links to reduce power consumption with an approach in which all links in the network are set to the same voltage and adaptive routing is used to distribute load across the network. Our results show that adaptive routing with static network link voltages outperforms dimension-order routing with dynamic link voltages in all cases, because the adaptive routing scheme can respond more quickly to changes in network demand. Adaptive routing with static link voltages also outperforms adaptive routing with dynamic link voltages in many cases, although dynamic link voltage scaling gives better behavior as the demand on the network grows.     

Adaptive Multimodule Routers for Multiprocessor Architectures

Recent multiprocessors such as Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate adaptivity into such routers with simple changes to the router structure and logic. We show that with as few as two virtual channels per physical channel, adaptivity can be provided to handle nonuniform traffic in multidimensional meshes.     

QoS-based routing algorithms for ATM networks

This paper presents a planned routing algorithm (PRA) and a hierarchical routing algorithm (HRA) for ATM networks. The PRA can establish the multicast tree with the presence of bandwidth and delay constraints. The HRA can be compliant with the PNNI specification from the ATM Forum. It uses an adaptive and iterative path search approach and takes advantage of the PNNI hierarchical network structure to reduce path computation complexity and maximize network throughput. The performances of the PRA and HRA are evaluated by simulations. The simulation results show that the PRA can provide the best performance while the complexity is acceptable and the HRA can reduce processing time and improve network utilization, and both are suited for QoS requirements of ATM networks’ routing.     

一种动态传感网络中的新型路由算法

随着无线传感网络技术和其应用领域的不断发展,网络模型趋于动态化,网络节点具有移动性,这给路由算法设计带来新的挑战。该文介绍动态叶子树网络模型,针对没有定位信息的场景提出适合动态网络的DLR路由算法。该算法包含路径相似度计算以及最佳路径选择2个步骤。仿真模拟表明,DLR路由算法能够在动态网络中保证超过90%的通信可靠性。     

Weighted Random Routing on Torus Networks

In this paper, we introduce a new closed-form oblivious routing algorithm called W2TURN that is worst-case throughput optimal for 2D-torus networks. W2TURN is based on a weighted random selection of paths that contain at most two turns. In terms of average hop count, W2TURN outperforms the best previously known closed-form worst-case throughput optimal routing algorithm called IVAL. In addition, we present a new optimal weighted random routing algorithm for rings called WRD.     

Routing management in very large-scale networks

Very large-scale networks and internetworks are already a reality, and routing constitutes an essential element for the operation of such networks. Unfortunately, the overhead of an adaptive routing algorithm becomes prohibitive in a network or an internetwork with several nodes (in the order of thousands or more) and a flat routing architecture in which each node must know how to reach every other node in the system. In this paper, we discuss the problems with existing network architectures and adaptive routing algorithms when they are applied to very large networks. Then we present a new hierarchical network architecture designed to solve these problems. The two key features of the new architecture are a new loop-free routing algorithm and a new hierarchical addressing mechanism. We compare this architecture with others previously proposed from the standpoint of the savings in routing overhead and the optimality of the paths obtained.     

Impact of sensing coverage on greedy geographic routing algorithms

Greedy geographic routing is an attractive localized routing scheme for wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks (e.g., surveillance or object tracking systems) that provide sensing coverage over a geographic area. Our analysis and simulation results demonstrate that an existing geographic routing algorithm, greedy forwarding (GF), can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under GF. We also propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that achieves path dilation lower than 4.62 in sensing-covered networks as long as the communication range is at least twice the sensing range. Furthermore, we extend GF and BVGF to achieve provable performance bounds in terms of total number of transmissions and reliability in lossy networks.     

A new algorithm for packet routing problems using chaotic neurodynamics and its surrogate analysis

We propose a new algorithm for routing packets which effectively avoids packet congestion in computer networks. The algorithm involves chaotic neurodynamics. To realize effective packet routing, we first composed a basic method by a neural network, which routes packets with shortest path information between two nodes in the computer network. When the computer network has an irregular topology, the basic routing method does not work well, because most of packets cannot be transmitted to their destinations due to packet congestion in the computer network. To avoid such an undesirable problem, we employed chaotic neurodynamics to extend the basic method. Numerical experiments show that our proposed method exhibits good performance for scale-free networks. We also analyze why the proposed routing method is effective, comparing the proposed method with several stochastic methods. We introduced the method of surrogate data, a statistical hypothesis testing which is often used in the field of nonlinear time-series analysis. Analysis of the proposed method by the method of surrogate data reveals that the chaotic neurodynamics is most effective to decentralize the packet congestion in the computer network.     

Resource deadlocks and performance of wormhole multicast routingalgorithms

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of resource deadlocks has not been addressed in many previously proposed wormhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. We provide upper bounds for the number of consumption channels required to avoid deadlocks. In addition, we present a new multicast routing algorithm, column-path, which is based on the well-known dimension-order routing used in many multicomputers and multiprocessors. Therefore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multicast routing algorithms. Our results show that for multicast traffic, the column-path routing offers higher throughputs, while the multipath algorithm offers lower message latencies. Another result of our study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good performance provided the number of destinations is small     

能量均衡的动态间隔分层路由协议*

针对无线传感器网络中分簇多跳通信方式产生的能量负载不均衡问题,提出一种能量均衡的动态间隔分层路由协议（EHRD）。它通过层次间隔动态调整算法动态调整层次间隔,使得层次的能量消耗不均匀状况得到缓解,从而达到整个网络能量负载均衡。用NS2仿真测试结果显示：能量均衡的动态间隔分层路由协议在网络能量负载、网络生存时间、缓解网络“热区”问题上有所提高。