3元n立方网络的2阶超连通性

为了度量以3元n立方网络为底层拓扑结构的并行与分布式系统的连通性,通过构造其2阶超割的方法,计算出当n不小于2时,3元n立方网络的2阶超连通度是6n-7。证明了对于以3元n立方网络为底层拓扑结构的并行与分布式计算机系统,当有不超过6n-8个节点发生故障且每个连通分支至少还有3个健康的节点时,该并行与分布式系统的任意两个节点之间仍然有一条无故障的通信线路。     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

基于交通引力场的复杂网络路由选择方法*

为提高网络吞吐量、缓解交通拥塞程度,结合复杂网络理论和引力场理论研究了在交通引力场下的动态路由选择过程,定义了传输路径对数据包的引力计算公式。基于路径的引力,顾及数据包的传输路径长度、节点畅通度及介数对传输过程的影响,提出了一种在介数约束下的引力场路由选择策略,并引入参数 用于调节路由过程对节点介数的控制强度。为描述数据包传输过程的有效性,引入有序参数 , 利用其由自由流到拥塞态的指标流量相变值度量网络的传输能力,并对网络节点拥塞分布情况进行了统计分析。仿真结果显示,与最短路由选择算法相比,本文路由策略较大地提高了网络传输能力,有效地均衡了网络交通负载,大部分节点均得到了高效利用,路由算法稳定、可靠。     

基于三维胞元空间的自适应多跳能量高效路由

针对无线传感器网络中三维路由算法的能耗问题,提出了基于三维胞元空间的自适应多跳能量高效路由(3D-SMEER)。该路由算法根据自适应多跳机制确定跳数,利用协同节点转发消息包到邻居最优胞父,从而减轻当前胞父的传输负担。同时,对协同节点的选择区域进行了研究,并且考虑节点的剩余能量和相关位置信息选择协同节点,以平衡网络的能耗。仿真结果表明,与其他算法相比3D-SMEER算法节省了网络的平均能耗,有效地提高了网络的能耗平衡度。     

多协议标签交换网络中最小干扰路由算法的研究

在最小干扰路由(MIR)算法基础上，提出一种改进的MIR算法。该算法结合了基于多商品流理论的流量描述路由（PBR）算法将节点对带宽预测作为路由信息的优点，以及MIR算法的核心思想，给出了节点对的权值计算公式，并说明了如何在现有MIR算法中利用节点对的权值。改进后的算法能更好地适应实际网络路由需要，提高网络资源利用率和吞吐量。     

基于移动agent的能量平衡环形路由算法

由于无线传感器网络(WSNs)自身的特点,将移动agent(MA)用于WSNs可以解决诸多网络问题.提出一种基于MA的能量平衡环形路由算法(EBRRMA),网络首先建立节点到sink节点的最小跳数链路,形成环状跳数梯度,为MA提供路由和工作空间;然后MA在梯度环内以记录迁移路径方式和最小延时策略完成环内巡游,融合节点数据并找到环内能量最多的节点;最后MA通过此节点与sink节点通信链路将融合信息回传并且休眠和等待下一次工作.该算法引入MA技术来降低网络能耗和时延,利用梯度环中能量最多的节点提供MA所需能量以及数据回传路径,以达到网络能量平衡.仿真表明,此路由算法可以有效地平衡网络能量,延长网络寿命.与DD路由相比,该路由算法节能效果显著.     

基于动态规划的无线传感器网络的路由算法

路由问题是无线传感器网络中的核心问题之一,其数据传送的多跳特点使得非常适合用动态规划的原理来设计传感器网络的路由算法.基于动态规划,通过节点跳数生成算法为传感器网络中的每个节点赋一个表示到Sink点跳数的节点跳数值,并分析了传感器网络的拓扑结构特点,然后给出了无线传感器网络中寻找从源到汇满足不同设计目标的最小跳数(MinH)、最小跳数最大剩余能量(MinHMaxRE)和最小跳数最小费用(MinHMinC)3种路由算法.探讨了最小跳数最小费用路由与最小费用路由之间的关系,并给出了判断最小跳数最小费用路径就是最小费用路径的一个充要条件.算法的能量消耗分析表明,所给路由算法能实现大幅度的能量节省.     

GcChord:基于组和缓存的改进型DHT网络

在基于DHT技术的对等网络中,一个重要的研究内容是减少逻辑网络和物理网络不匹配所带来的寻路时延过长的问题。文章提出一种利用组来匹配物理网络,利用超级节点缓存查询和地址信息,并且在普通节点收到查询请求时缓存查询源节点地址信息的路由算法GcChord(Group Cache based Chord)。仿真结果表明,GcChord的路由性能优于Chord系统,并且节点重复(有一定倾向)查询越多,其平均物理、逻辑跳数越少。     

UWSNs中基于深度的抑制空洞路由优化算法

针对传统的水下无线传感器网络(UWSNs)的位置路由存在路由空洞问题,提出了基于深度的抑制空洞路由(DSVR)的UWSNs路由协议.DSVR协议通过融合跳数、物理距离和邻居数多个指标决策路由.为了提高通信可靠和缓解路由空洞,DSVR协议选择具有最小跳数路径、最少邻居数的节点作为下一跳转发节点.同时,DSVR协议利用定时器抑制冗余数据包.仿真结果表明:提出的DSVR协议能有效地提高数据包传递率,并降低端到端传输时延以及能耗.     

改进的ZigBee网状网络路由算法研究

针对ZigBee网络中AODVjr路由算法存在节点死亡率高、网络能耗大的问题,结合节点的存储结构、能量和链路质量特点,提出一种改进的ZigBee网状网络路由算法F-AODVjr。在路由发现之前,利用路由节点自动维护的邻居表寻找目的节点,以降低因路由请求(RREQ)分组寻址目的节点导致的能量消耗。在路由发现阶段,通过改进AODVjr路由算法的最短路径寻址思想,设计含有路由跳数、节点剩余能量和链路质量的路由算法,寻找具有最低路由成本的优化路径。仿真结果表明,F-AODVjr路由算法可以有效降低网络整体能量消耗,提高节点生存率及数据分组成功投递率。     

Fault diameter of k-ary n-cube networks

We obtain the fault diameter of k-ary n-cube interconnection networks (also known as n-dimensional k-torus networks). We start by constructing a complete set of node-disjoint paths (i.e., as many paths as the degree) between any two nodes of a k-ary n-cube. Each of the obtained paths is of length zero, two, or four plus the minimum length except for one path in a special case (when the Hamming distance between the two nodes is one) where the increase over the minimum length may attain eight. These results improve those obtained by B. Bose et al. (1995) where the length of some of the paths has a variable increase (which can be arbitrarily large) over the minimum length. These results are then used to derive the fault diameter of the k-ary n-cube, which is shown to be Δ+1 where Δ is the fault free diameter     

故障广义4元n方体中不同长度的路嵌入

k元n方体是传输信息的一种重要网络,研究含有故障点的广义4元n方体。证明了当其故障点数f≤n-1时,对每个整数l∈{2n-1,2n,…,4ⁿ-f-1},任意两个非故障点之间存在长度为l的无故障路。     

k元n立方网络的k圈排除问题的递归算法

为了度量以k元n立方网络为底层网络拓扑的并行计算机系统的容错能力,通过构造k元n立方网络中使得所有的k元1立方子网都发生故障的最小节点集合的方法,提出求解其k元1立方子网排除点割集的一种递归算法;证明了要使k元n立方网络中所有k元1立方子网都发生故障至少需要破坏掉kn-1个节点。结果表明,在不超过kn-1-1个节点被破坏的情况下,以k元n立方网络为底层拓扑构建的并行计算机系统中依然存在无故障的k元1立方子网。     

Embedding of generalized Fibonacci cubes in hypercubes with faultynodes

The generalized Fibonacci cubes (abbreviated to GFCs) were recently proposed as a class of interconnection topologies, which cover a spectrum ranging from regular graphs such as the hypercube to semiregular graphs such as the second order Fibonacci cube. It has been shown that the kth order GFC of dimension n+k is equivalent to an n-cube for 0⩽n相似文献   

Performance-based path determination for interprocessorcommunication in distributed computing systems

The different types of messages used by a parallel application program executing in a distributed computing system can each have unique characteristics so that no single communication network can produce the lowest latency for all messages. For instance, short control messages may be sent with the lowest overhead on one type of network, such as Ethernet, while bulk data transfers may be better suited to a different type of network, such as Fibre Channel or HIPPI. This work investigates how to exploit multiple heterogeneous communication networks that interconnect the same set of processing nodes using a set of techniques we call performance-based path determination (PBPD). The performance-based path selection (PBPS) technique selects the best (lowest latency) network among several for each individual message to reduce the communication overhead of parallel programs. The performance-based path aggregation (PBPA) technique, on the other hand, aggregates multiple networks into a single virtual network to increase the available bandwidth. We test the PBPD techniques on a cluster of SGI multiprocessors interconnected with Ethernet, Fibre Channel, and HiPPI networks using a custom communication library built on top of the TCP/IP protocol layers. We find that PBPS can reduce communication overhead in applications compared to using either network alone, while aggregating networks into a single virtual network can reduce communication latency for bandwidth-limited applications. The performance of the PBPD techniques depends on the mix of message sizes in the application program and the relative overheads of the networks, as demonstrated in our analytical models     

Designing clustered multiprocessor systems under packaging andtechnological advancements

Clustered or hierarchical interconnections have advantages when designing large scale multiprocessor systems. Earlier studies have either focused on only flat interconnections or proposed hierarchical/clustered interconnections with limited packaging and demanded performance constraints. Large systems require several levels of packaging. Packaging technologies impose various physical constraints on bisection bandwidth and channel width of a system. Pinout technologies and the capacity of packaging modules have been ignored in earlier studies, often leading to configurations that are not design-feasible. Similarly, the impact of processor and interconnect technologies on demanded performance has not been considered. We propose a new supply-demand framework for multiprocessor system design by considering packaging, processor, and interconnect technologies in an integrated manner. The elegance of this framework lies in its parameterised representation of different technologies. For a given set of technological parameters the framework derives the best configuration while considering practical design aspects like maximum board area, maximum available pinout, fixed channel width, and scalability. In order to build a scalable parallel system with a given number of processors, the framework explores the design space of flat k-ary n-cube topologies and their clustered variations (k-ary n-cube cluster-c) to derive design-feasible configurations with best system performance     

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树（transposition tree）的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。     

Performance analysis of mesh interconnection networks withdeterministic routing

This paper develops detailed analytical performance models for k-ary n-cube networks with single-hit or infinite buffers, wormhole routing, and the nonadaptive deadlock-free routing scheme proposed by Dally and Seitz (1987). In contrast to previous performance studies of such networks, the system is modeled as a closed queueing network that: includes the effects of blocking and pipelining of messages in the network; allows for arbitrary source-destination probability distributions; and explicitly models the virtual channels used in the deadlock-free routing algorithm. The models are used to examine several performance issues for 2-D networks with shared-memory traffic. These results should prove useful for engineering high-performance systems based on low-dimensional k-ary n-cube networks     

超立方体互连网络自适应简捷盲寻径搜索算法

根据n-cube超立方体互连网络的并行特点，分析了任意当前结点相邻集合类的求解方法，并给出一种自适应优化盲寻径搜索算法，即通过任一当前结点的Hamming距离相邻测度，寻找从任一始发结点到目标结点的所有可能的自适应盲寻径优化算法．