一种基于三角模糊数的VANETs机会路由算法*

分析了现有车用自组织网络（VANETs）的路由算法,提出一种新的基于三角模糊数的机会路由算法。新算法将转发结点距离目标结点的距离、到达目标结点的方向、行驶速度向量、重传次数、车流状况等因素作为目标函数进行分析计算,采用熵权系数法确定各因素权重。路由过程中,贪婪选择向量值最大的节点转发数据包;遇到网络不连续时,将采用“存储－携带－转发”的机会路由策略。仿真结果表明,该算法能够较好的适用于VANETs各种场景。     

基于节点剩余能量和最大角度的无线传感器网络路由算法

针对传统无线传感器网络(WSNs)路由算法的缺点与不足,为了延长网络的生存时间,提出一种基于节点剩余能量和最大角度相融合的无线传感器网络路由算法.首先构建了无线传感器网络结构和能量模型,然后建立节点剩余能量和角度联合路由优化算法,最后采用Matlab 2012仿真工具进行仿真测试.仿真结果表明:该路由算法延长了整个网络的生存时间,具有较好的容错性和鲁棒性.     

2D Mesh片上网络分区容错路由算法

为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up^*/down^*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up^*/down^*算法和segment算法相当甚至更优的性能。     

一种基于遗传算法的QoS多播路由算法

深入研究基于遗传算法的QoS多播路由算法,建立支持QoS的多播路由模型.对已有的QoS多播路由算法进行优化,提出适用于下一代网络的基于遗传算法的QoS多播路由算法.采用定长的染色体编码和预处理机制降低算法复杂度.仿真试验表明,该算法收敛速度快,可靠性高,能够更好地满足多播业务的需要.     

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。     

蜂窝网格的单播路由算法

六角形蜂窝网格是一种具有良好网络拓扑性质的并行多处理机互连网络.蜂窝网格在某些特性上优于二维网格.不过,这种网络不存在单信道最短路径无死锁路由算法.文中针对该网络设计了两个部分自适应无死锁虫孔路由算法.一个是基于转弯模型单信道非最短路径路由算法,另一个则是采用了虚拟双信道的最短路径路由算法.对第二个算法,还进一步使用转弯模型对其改进.通过仿真实验,结果显示这两个路由算法都具有较好的性能.     

一种基于虫洞交换的竞争预测路由算法

分析了基于虫洞交换技术的片上互连网络路由算法存在的一些问题:固定维序路由当出现竞争时,只能等待,直到链路空闲方可继续前进.热土豆路由在路由器从不等待,任意选择一个空闲的端口进行发送,但却有活锁问题.利用相邻路由节点之间提供的竞争感知信号,提出了一种竞争预测的自适应路由算法,并利用SystemC片上互连网络仿真实现该算法.实验表明,该路由算法的网络传输延时在竞争多发的情况下明显优于热土豆算法与传统的固定维序算法.     

无线传感器网络中路由选择算法的研究

针对无线传感器网络中采用多跳方式建立路由的特点,将蚁群算法用于在无线传感器网络中寻找多跳路由,通过一组"人工蚂蚁"采用并行搜索方式,寻找从源节点到目的节点的最少跳数路径;在算法中通过引入约束条件,既可降低算法的计算开销,又加快了算法的收敛速度;仿真结果说明将该算法用于无线传感器网络中搜寻路由是有效的,且具有鲁棒性特点,同时比传统的路由算法具有更低的时间复杂度。     

分层混合路由协议的研究与仿真

基于分层路由协议LEACH算法提出了改进的分层混合路由算法HMP.从簇建立阶段到稳定的数据传输阶段,对分层混合路由协议进行研究.分层混合路由协议引用了迪杰斯特拉算法计算数据传输的优化路径,减少了簇首节点通信能耗;并考虑了优化路径上节点的剩余能量状况,建立了簇首多跳节能通信机制,防止了靠近汇[聚节点的最优路径上的簇首节点因为能量的过渡消耗而过早死亡.最后采用仿真工具NS2对HMP算法和LEACH算法进行了仿真比较分析,验证了HMP算法更能够均衡网络能量消耗,提高能量的有效性,从而延长网络生命周期.     

基于低轨卫星网络的按需局部拓扑路由算法

提出了一种简单有效的路由算法——按需局部拓扑路由算法。该算法在保证建立的路由具有最小延时的同时,具有很好的收敛时间,能够有效地适应低轨卫星网络的动态拓扑特性。并给出局部拓扑路由算法的仿真结果及分析;最后提出了下一步研究的重点——基于Qos的路由算法。     

一种二维片上网络路由器的设计实现

片上网络(Network on Chip, NoC)作为解决众核芯片互连的主流方案,其性能很大程度上取决于网络的拓扑结构。而网络拓扑结构的效能受到网络路由器的直接影响。因此,基于特定拓扑结构的路由器设计实现具有非常重要的研究意义。因此将XY路由算法应用于路由器节点中,设计了基于2D Mesh拓扑结构、轮询仲裁机制与虫孔交换流控的片上网络路由器,并使用Modelsim对路由器进行了功能验证。实验结果表明,设计的路由器能满足微片数据的处理,能够正确的收发数据包。     

A theory of deadlock-free adaptive multicast routing in wormholenetworks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks, proposed by the author (1991, 1993), supplies sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies were proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. A tree-like routing scheme is not suitable for hardware-supported multicast in wormhole networks because it produces many headers for each message, drastically increasing the probability of a message being blocked. A path-based multicast routing model was proposed by Lin and Ni (1991) for multicomputers with 2D-mesh and hypercube topologies. In this model, messages are not replicated at intermediate nodes. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms. This theory is valid for wormhole networks using the path-based routing model. It is also valid when messages with a single destination and multiple destinations are mixed together. The new channel dependencies produced by messages with several destinations are studied. Also, two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms of Lin and Ni are extended, so that they can take advantage of the alternative paths offered by the network     

蛀洞路由机制及其芯片设计

蛀洞路由技术是“曙光１０００”大规模并行计算机所采用的一面关键技术。本文讨论了蛀洞路由机制，详细介绍了“曙光１０００”的蛀洞路由算法、芯片结构设计，以及由该芯片构成的处理机互连网络。     

A framework for designing deadlock-free wormhole routing algorithms

This paper presents a framework to design fully-adaptive, deadlock-free wormhole algorithms for a variety of network topologies. The main theoretical contributions are: (a) design of new wormhole algorithms using store-and-forward algorithms, (b) a sufficient condition for deadlock free routing by the wormhole algorithms so designed, and (c) a sufficient condition for deadlock free routing by these wormhole algorithms with centralized flit buffers shared among multiple channels. To illustrate the theory, several wormhole algorithms based on store-and-forward hop schemes are designed. The hop-based wormhole algorithms can be applied to a variety of networks including torus, mesh, de Brujin, and a class of Cayley networks, with the best known bounds on virtual channels for minimal routing on the last two classes of networks. An analysis of the resource requirements and performances of a proposed algorithm, called negative-hop algorithm, with some of the previously proposed algorithms for torus and mesh networks is presented     

Alleviating consumption channel bottleneck in wormhole routed k-aryn-cube systems

This paper identifies performance degradation in wormhole routed k-ary n-cube networks due to limited number of router-to-processor consumption channels at each node. Many recent research in wormhole routing have advocated the advantages of adaptive routing and virtual channel flow control schemes to deliver better network performance. This paper indicates that the advantages associated with these schemes cannot be realized with limited consumption capacity. To alleviate such performance bottlenecks, a new network interface design using multiple consumption channels is proposed. To match virtual multiplexing on network channels, we also propose each consumption channel to support multiple virtual consumption channels. The impact of message arrival rate at a node on the required number of consumption channels is studied analytically. It is shown that wormhole networks with higher routing adaptivity, dimensionality, degree of hot-spot traffic, and number of virtual lanes have to take advantage of multiple consumption channels to deliver better performance. The interplay between system topology, routing algorithm, number of virtual lanes, messaging overheads, and communication traffic is studied through simulation to derive the effective number of consumption channels required in a system. Using the ongoing technological trend, it is shown that wormhole-routed systems can use up to two-four consumption channels per node to deliver better system performance     

Compressionless wormhole routing: an analysis for hypercube with virtual channels

Several recent studies have shown that adaptive routing algorithms based on deadlock recovery have superior performance characteristics than those based on deadlock avoidance. Most of these studies, however, have relied on software simulation due to the lack of analytical modelling tools. In an effort towards filling this gap, this paper presents a new analytical model of compressionless routing in wormhole-routed hypercubes. This routing algorithm exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. The advantages of compressionless routing include deadlock-free adaptive routing with no extra virtual channels, simple router design, and order-preserving message transmission. The proposed analytical model computes message latency by determining the message transmission time, blocking delay at each router, multiplexing delay at each network channel, and waiting time in the source before entering the network. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.     

虚网叠加构造自适应路由算法的有效框架

大规模并行处理机系统中路由算法对互联网络通信性能和系统性起着重要作用。     

N-立方体消息通信时延的分析

本文利用生灭过程理论,对Ｎ－立方体的消息通信延时建立了一个计算模型,在存在消息堵塞的情况下对Ｎ－立方体采用虫孔寻径机制和ｅ－ｃｕｂｅ算法时的沙息通信延迟进行了分析求解,最后,通过模拟实验,证明了结果的正确性。     

虫孔网络中的自适应路由算法

互连网络是大规模并行计算机的重要组成部分,路由算法是其中决定网络性能的重要因素,自适应路由算法视网络工作状态可以在源到目的结点之间存在的多条路径中选择合适的一条传送消息,因此选径的灵活性和通道利用率高,提高了网络效率,增强了网络容错能力。文中在直接网络结构基础上对采用虫孔路由的自适应算法进行讨论,给出了一个总结综述。     

一个全互连可伸缩并行加速系统的体系结构设计

可伸缩（分布存储）多计算机系统是目前并行处理系统研究的一个热点，它不有重要的学术价值，而且已被用户广泛地接受，本文介绍了一个计算引擎式的ｓｍＣ并行加速系统的体系结构设计，它的互连网络由支持Ｗｏｒｍｈｏｌｅ寻径技术和虚通道流控制的包寻径开关构成，实现了ＰＥ间逻辑上的全互连拓扑，该系统能够有效地在多用户，多任务状态下工作，具有良好的可伸缩性。