Mesh网中高效无死锁自适应路由算法

提出了一种新的应用于三维Mesh网中的无死锁路由算法.在当今的商用多计算机系统中,二维和三维的Mesh网是多处理器网络最为常用的拓扑结构之一.在应用于Mesh网的平面自适应路由(Planar Adaptive Routing)算法中,每条物理通道只需三条虚拟通道就可以有效地在三维以及更高维的Mesh网中避免死锁的产生.然而,采用该算法,网络拓扑一维和三维分别有两条和一条虚拟通道始终处于空闲状态.该文所提出的算法针对三维Mesh网,每条物理通道只需两条虚拟通道就可以有效地避免死锁.文中通过充分的模拟数据验证了此算法的有效性.     

Deadlock-Free Multicasting in Irregular Networks Using Prefix Routing

A deadlock-free multicast scheme called prefix multicasting in irregular networks (i.e., networks with irregular topology) is studied. In prefix routing, a compact routing table is associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labelling in an irregular network is based on a pre-defined spanning tree which may or may not be minimum. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel between two branches of the tree between two phases. It is shown that the proposed routing scheme is deadlock- and livelock-free. The approach is extended to multicasting in which the multicast packet is first forwarded up the tree to the longest common prefix (LCP) of destinations in the multicast. The packet is then treated as a multi-head worm that can split at branches of the spanning tree as the packet is sent down the tree.     

Efficient Deadlock-Free Wormhole Routing and Virtual-Channel Reduction in Shuffle-Based Networks

Many aspects of shuffle-based networks have recently been studied by numerous researchers. However, no attention has been paid to deadlock-free wormhole routing algorithms. In this paper, for a set of shuffle-based networks, we introduce a graph-partitioning technique that enables a deadlock-free routing algorithm with fewer virtual channels than the known algorithms. This is achieved for the de Bruijn digraphs which are shown to require a maximum ofm− ⌊(m− 1)/r⌋ virtual channels per physical channel, wheremis the diameter andris the radix. Algorithms for the generalized de Bruijn graph, the de Bruijn Cube (dBCube) graph and the Shuffle–Exchange network are introduced, and virtual channel requirements are determined. The dBCube graph of size (r,N_b,n) requires a maximum ofm− ⌊(m− 1)/r⌋ virtual channels for the outcluster channels, and a maximum ofm+ 1 − ⌊m/r⌋ virtual channels for the incluster channels in most cases, wherem= ⌊log_rN_b⌋,ris the radix of a generalized de Bruijn graph of sizeN_b, andnrepresents the number of dimensions in a binary hypercube. We also show that a maximum ofm− ⌊(m− 1)/2⌋ virtual channels are required in shuffle-exchange networks with 2^mnodes.     

On the Flattest Common Supersequence Method for Deadlock-Free Routing in Arbitrary Networks

In this paper we consider the problem of deadlock-free routing in arbitrary parallel and distributed computers. We focus on asynchronous routing algorithms which continuously receive new packets to route and which do not discard packets that encounter congestion. Specifically, we examine what we call the deadlock-free routing (DFR ) problem. The input to the DFR problem consists of an arbitrary network and an arbitrary set of paths in the network. The output consists of a routing algorithm, which is a list of the buffers used along each of the paths. The routing algorithm is required to be free from deadlock and the goal is to minimize the number of buffers required in any one node. We study the DFR problem by converting it into an equivalent problem which we call the flattest common supersequence (FCS ) problem. The input to the FCS problem consists of a set of sequences and the output consists of a single sequence that contains all of the input sequences as (possibly noncontiguous) subsequences. The goal of the FCS problem is to minimize the maximum frequency of any symbol in the output sequence. We present three main results. First, we prove that the decision version of the FCS problem is NP-complete, and has no polynomial-time approximation scheme unless P= NP . An alternative proof is presented which shows that unlike the shortest common supersequence (SCS) problem, the FCS problem is still NP-complete for two input sequences. This implies that approximation algorithms for FCS based on an exact pairwise merge are not possible. Next, we propose and experimentally evaluate a range of heuristics for FCS. Our experimental results show that one of these heuristics performs very well over a wide range of inputs. Lastly, we prove that this heuristic is in fact optimal for certain restricted classes of inputs. Online publication November 27, 2000.     

An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks

System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up*/down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up*/down*-based routings, and also reduce latency     

A Comparative Study of Switching Methods in Multicomputer Networks

The switching method determines the way messages visit intermediate routers, and has a great impact on network performance. This paper conducts an extensive comparative performance analysis, by means of analytical modelling, of three well-known switching methods proposed for multicomputer networks, namely wormhole switching, circuit switching, and pipelined circuit switching. The results reveal that wormhole switching is the most efficient when messages are short. Pipelined circuit switching can perform better than circuit switching and provides superior performance over wormhole switching when messages are relatively long.     

A Generic Framework for Anonymous Authentication in Mobile Networks

Designing an anonymous user authentication scheme in global mobility networks is a non-trivial task because wireless networks are susceptible to attacks and mobile devices powered by batteries have limited communication, processing and storage capabilities. In this paper, we present a generic construction that converts any existing secure password authen- tication scheme based on a smart card into an anonymous authentication scheme for roaming services. The security proof of our construction can be derived from the underlying password authentication scheme employing the same assumptions. Compared with the original password authentication scheme, the transformed scheme does not sacrifice the authentication effciency, and additionally, an agreed session key can be securely established between an anonymous mobile user and the foreign agent in charge of the network being visited. Furthermore, we present an instantiation of the proposed generic construction. The performance analysis shows that compared with other related anonymous authentication schemes, our instantiation is more effcient.     

机会网络中多使者交叉区域摆渡路由协议

针对传统摆渡路由中使者调度和协作的问题,设计一种交叉区域的多使者摆渡路由协议.将网络划分成若干横向区域和纵向区域,每个区域内存在一个使者轮询节点.通过单个使者或一个横向区域使者与一个纵向区域使者的协作实现数据的传递.从理论上分析了提出协议的期望延时,并从延时和容错性两个方面对协议进行了改善.仿真评估结果表明,交叉区域摆渡路由在平衡网络负载和端到端的延时的同时,具有单一使者的容错能力,是一种合理有效的多使者调度方法.     

Ad hoc网络路由优化的微粒群方法

Adhoe网络是由彼此对等的、自主的无线节点组成的自组织多跳网络,由于Adhoe网络的特点，使得网络拓扑设计的优化问题变得更加复杂，传统的方法甚至难于实现．本文应用微粒群算法，构造了一个适合自组网网络架构设计的运算法则，建立了一个新的对约束的处理技巧，通过引入共生机制，实现了网络设计在约束下的多目标优化设计，其微粒群的解关于约束是理想的，解集间是非次等的，不分优劣，仿真结果表明，该方法是有效的，它的实时性适应了Aclhoe网络结构动态的变化．     

无线传感器网络路由协议的优化设计

无线传感器网络是一种全新的信息获取和处理技术.对无线传感器网络设计了一个能量有效的分簇路由协议.为了提高能量和宽带的利用率,协议应用了一个能量有效的路由算法对LEACH协议进行了改进,从而减少数据传输的能量消耗,并且延长了网络的生命周期.上述算法为簇头到基站的数据传输构建了一个多跳路由.运用这个多跳路由来传输数据,簇头可以节省大量的能量.为了能延长网络的生命周期,能量的分布也考虑在这个算法中.通过在仿真平台上跟其它两个已经存在的分簇路由协议的比较来评价所设计协议的性能进行仿真.仿真结果显示设计的路由协议有更好的节能效果和更长的网络生命周期.     

蛀洞路由器C104及其在多计算机系统中的应用

采用蛀洞路由机制是新型多计算机系统的重要特征。介绍了多计算机系统中蛀洞路由机制的基本概念。     

无线网状网跨层路由的研究

目前,无线网状网跨层路由设计方兴未艾,以往无线路由设计是基于最小跳数的,缺少对无线网状网特性的综合考虑,并不能充分发挥出无线网状网的优势。该文提出了基于"队列负载率"和"链路传输效率"的跨层路由协议算法,通过将MAC层的网络状态信息传递给网络层的路由代理,以便选择负载较小的最佳路由。通过仿真可以发现,改文提出的路由不仅显著提高了吞吐量,而且使包的投递更加可靠,提高了QoS。     

一种面向认知网络的QoS路由协议

随着网络应用的快速发展,传统网络面临诸多挑战,难以满足新型应用的服务质量QoS(Quality of Service)需求,网络管理变得极其复杂,迫切要求网络具备认知能力.文中提出了一种面向认知网络的QoS路由协议.为了满足不同应用的QoS需求,路由请求对应不同业务类型和服务等级,映射到相应的QoS参数.文中赋予路由节点感觉、活动感、记忆、查找、决策、执行、推理、解释等认知行为,设计了与这些行为相对应的协议报文,支持节点之间通过这些报文进行交互,从而具备认知能力.节点只收集和维护局部邻居和链路状态信息,通过使用和维护经验路段信息提高路由效率.文中对所提出的路由协议在原型系统上进行了实现,对协议的多项性能指标进行了评价.实验结果表明,文中所提出的路由协议是可行和有效的.     

基于模糊策略的ATM网络路由选择

文章综合考虑了用户需求和网络状态,制定出相应的模糊规则,采用模糊逻辑方法完成ATM网络的路由选择。仿真结果表明,该方法具有运算简单,实时性强,硬件实现方便的优点。     

一种基于稳定性的无线mesh网络路由协议

无线网状网络(mesh)以其高速率高容量,易于部署的特点受到学术界和产业界的格外关注,其路由协议是研究重点与难点之一.本文分析了无线mesh网络路由协议的设计特点,在经典移动ad-hoc路由协议AODV的基础上提出了一种基于稳定性的无线mesh网络的路由协议并在ns2上给予仿真了实现,仿真结果表明该协议在所需性能上优于AODV,更适合无线mesh网络.     

On the Design of Link-State Routing Protocol for Connection-Oriented Networks

Link-state routing protocols are being increasingly used in modern communications networks. A salient feature of this class of routing protocols is that network connectivity and state information of all links are available to nodes for making routing decision. Two main components of a link-state routing protocol are an update mechanism and a routing algorithm. These components must be properly designed for efficient routing. Various alternatives are possible for each of these components leading to different scenarios for routing protocol. In this paper, we quantitatively examine the impact of these alternatives on network performance using call-by-call simulations. Our design objective is to reduce call blocking ratio without significantly increasing routing overhead. We also present a new signaling scheme that can be used in conjunction with link-state protocols. We show that, if properly designed, this scheme can enhance the network performance.     

WDM网络中考虑Qos约束的动态业务路由算法

路由问题是WDM网络中的一个核心问题。该文研究了WDM网络中受瓶颈带宽Qos和时延Qos约束的动态业务路由算法。算法以链路的延时值作为链路的权值,为网络中所有节点对计算所有代价有限的路由,作为备用路由。当一个连接请求到达时,考察其瓶颈带宽Qos指标与时延Qos指标,在备用路由集中选择满足Qos指标的路由;对所选路由综合考察其跳数、成本以及链路瓶颈带宽,计算目标函数,选择目标函数值最优的路由建立连接。     

A Routing Protocol for Enhanced Efficiency in Cognitive Radio Networks

This paper proposes a novel routing protocol enriched with an assigning mechanism that enables for efficient data flow coordination, among communication nodes with heterogeneous spectrum availability in distributed cognitive radio networks. Efficient routing protocol operation, as a matter of maximum-possible routing paths establishments and minimum delays is obtained, by utilizing a signaling mechanism that was developed based on a simulation scenario. This simulation scenario includes a number of secondary communication nodes, operating over TVWS （television white spaces） under the ＂spectrum of commons＂ regulation regime. The validity of the proposed routing protocol for enhanced efficiency in cognitive radio networks is validated, by conducting experimental simulations and obtaining performance evaluation results. Simulation results verified the efficiency of the proposed routing protocol for minimizing routing delays among secondary communication nodes and indentified fields for further research.     

基于信誉机制的传感器网络安全路由协议设计

无线传感器网络具有与传统网络不同的特点,传统的安全路由协议不能有效地应用于无线传感器网络,所以无线传感器网络安全问题成为亟待解决的课题。针对无线传感器网络路由面临安全威胁和节点能量有限的不足,提出了一种新的安全路由协议R-GEAR。该协议在GEAR路由算法的基础上,引入了信誉评测机制对攻击节点进行检测;并在能耗方面对其加以改进,通过在数据传输时进行数据融合来节约能量。仿真结果表明,在存在攻击节点的情况下,R-GEAR协议比GEAR协议具有较高的包传输率和较低的包丢失率等属性。     

一种能量高效无线传感器网络路由协议的设计

在无线传感器网络中提高节点能量问题的研究中,首先对无线传感器网络经典的分簇路由协议LEACH进行分析,针对LEACH中存在的少能量节点,或者偏远节点选为簇头节点,容易导致节点加快死亡、网络能量利用率降低的问题,通过改变簇头选择策略,综合考虑节点剩余能量和地理位置等参数的方法,提出一种新的路由协议,避免选取少能量节点为簇头.经NS2的仿真结果表明,提高了网络能量利用率.能量高效LEACH协议比LEACH原协议延长了28%的网络生存时间,并对延迟了第一节点死亡(FND)时间27%,并使得更多的能量利用于网络开始真正死亡之前,提高了网络能量利用率.