超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定Hn是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到Hn中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.     

蜂窝网络上的虫孔容错路由算法

蜂窝网络是新近提出的并行多处理机互连网络结构.针对该网络提出了一个无故障最短路径单播路由算法,然后基于该算法使用虚拟信道技术设计了一个凸形故障容错路由算法.这2个算法都是无死锁的,容错路由算法也只使用局部信息路由报文.     

基于列分转弯模型的片上网络路由算法

针对现有的判断片上网络路由算法是否含有死锁的方法都比较复杂,以及传统转弯模型存在不足的问题,提出了一种更简单更直观的判断路由算法是否包含死锁的算法,并证明了该算法的正确性,然后提出了一种列分转弯模型。列分转弯模型能实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径部分自适应路由,并且不需要额外的虚拟通道。该模型会在网络节点处限制某些转弯,从而避免死锁,类似于奇偶转弯模型。模拟实验结果表明:基于该模型的路由算法与基于奇偶转弯模型的路由算法相比,在不同的流量模式下平均延迟都有所降低,饱和点有所上升,从而提高了整个网络的性能。     

一种基于局部扭曲立方体多计算机网络的顺序诊断算法

顺序诊断是对多计算机网络进行故障诊断的一种比较实际的方法。局部扭曲立方体是超立方体的一种新变体结构,具有可并行处理的某些性质。在PMC模型下提出了一个基于局部扭曲立方体的顺序诊断算法。该算法表明了n维局部扭曲立方体是Ω(NlloogglNogN)-可诊断的,这里N=2n是总的结点数。     

网环步进码片上网络自适应路由算法设计

针对片上系统使用过多虚拟通道带来大量的缓存面积及能耗开销问题,提出了一种网环步进码(TSC)片上网络自适应路由算法.将网环网络中2个虚拟通道划分为按编码"O"或"1"数量递减或者递增的2个子网络,按TSC编码为网环拓扑结构中的网络节点进行编码,每个节点与相邻节点有且仅有一位不同,由此可以减小网络开销,避免片上死锁.实验结果表明:在均匀传输模式下,算法可为94%的数据包提供自适应路由选择,并在不增加虚拟通道数量的前提下,提高路由算法在网络负载增大时的适应能力.     

超立方体中基于安全矩阵的容错路由

超立方体网络拓扑结构是多处理机系统中常见的一种.随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大.针对超立方体结构的容错路由设计在信息传输过程中出现迂回的情况,提出了安全矩阵(safety matrices,简称SMs)这一概念,给出了一种建立SMs的方法及其容错路由算法.n维超立方体每个结点所需的存储开销为n2个字,安全矩阵记录了局部更多的信息.与传统的路由算法相比,该算法可以避免信息在传输过程中出现迂回和死锁,使路径达到最优.     

基于局部信息的单播容错路由算法研究

文章提出了局部k维子交叉立方体连通性和局部子交叉立方体连通性的概念,给出交叉立方体互联网络中基于子交叉立方体结构的局部连通性容错模型.以此模型设计了局部信息的高效的单播容错路由算法(文中称之算法B),算法具有很好的通信性能和具体意义.     

消息传递网络中的消息传递机制和路由算法

消息传递网络应用十分广泛，小到超大规模集成（VLSI）内部总线，大到计算机广域网.对其中一种消息传递网络——3D环型立方体结构中消息传递机制以及路由算法进行了深入研究，提出了无死锁和无活锁的确定性路由与自适应路由相结合的路由算法，考察了虚拟直通（cut-through）和存储转发（store-and-forward）两种消息传递机制下的性能表现.通过在3D环型立方体网络上的模拟运算，验证了所提出的算法在传输延时、吞吐率等方面的性能提高；也验证了不同的消息传递机制对网络传输效率的影响.     

局部扭曲立方体在一维阵列光网络中的路由与波长分配

探讨局部扭曲立方体LTQ_n通信模式在一维阵列波分复用光网络中的路由与波长分配问题.首先通过LTQ_n的最大导出子图得到拥塞,即所需要的最少波长数;其次给出一个路由与波长分配策略,从而证明了最优波长数为2~(n+1)/3.     

片上网络中基于拓扑排序的死锁检测与恢复方法

提出了一种将拓扑排序应用于片上网络的死锁检测与恢复的方法.利用片上网络线资源丰富的特点,使用专用线路采集并分析网络中各通道之间的依赖关系,快速确定处于死锁环路中的通道位置,并对死锁环路进行解锁.结果表明,所提出的方法简单有效,可以支持各种路由算法,与广泛应用的死锁避免策略相比,其网络资源的利用率和网络性能有所提高,并具有一定的容错能力.
     

局部纽立方体网络的容错泛圈性

n维局部纽立方体网络LTQn是超立方体网络的一种新变型。已经证明：LTQn中就包含任意长度l（4≤l≤2^n）的圈。我们改进了这个结果，证明了：只要网络故障点数fv和故障边数fe之和不超过（n-2），LTQn中就包含任意长度l（4≤l≤2^n-fv）的圈。     

局部扭曲立方体单播容错路由算法

局部扭曲立方体是一种新型的网络拓扑结构．基于此网络拓扑结构,利用安全级概念以及此种网络拓扑结构自身特有的性质设计了一种单播容错路由算法．通过模拟仿真实验对该算法进行了性能评价与分析．当故障节点的数目达到或超过一半时,仍能保持在一个相当高的容错路由成功率上．另外,该算法所选线路在多数情况下是最短距离．     

关于旋转交换网络的直径

本文讨论了旋转交换网络REn 的一些代数性质并给出了此网络的一个路由算法. 并且证明了(n2-2n 1)/4相似文献   

周期系数高阶线性微分方程的次正规解

考虑周期系数高阶线性微分方程f~((n))+∑j=1 n[P_(n-j)(e~z)+Q_(n-j)(e~(-z))]f~((n-j))=R_1(e~z)+R_2(e~(-z)),其中n≥2,P_j(z),Q_j(z)(j=0,1,2,…,n-1),R_1(z)和R_2(z)均是关于z的多项式,且Pj(z),Qj(z)(j=0,1,2,…,n-1)不全为常数.在条件degPjdegP0(j=1,2,…,n-1)下,获得方程的次正规解的表示.     

通信网络路由新算法

通信网向高可靠性、高利用率和高服务质量方面发展,现有路由算法已难以适应发展要求,需要寻找新算法。研究出一种易于多处理器并行运算的快速路由算法,采用逻辑代数运算规则,按照逐步变换、整合及删除中间节点关联分组方式计算,对于有n个节点的网络只需n-2次整合运算就能得到网络两节点间全部路由,且不会出现违反通信传输规则的闭环问题。详细论证了算法的正确性与合理性,简介了算法的并行运算可行性问题。通过算例详细说明算法的计算过程。     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

无线传感器网络自适应拥塞控制的路由算法分析

无线传感器网络中节点的覆盖范围有限,因而采用多跳路由传输方式.无线自组网中的多跳路由是由普通节点协作完成的,选择不同的转发节点,会对网络的信息传输产生不同的影响.对不同路由(洪泛路由、最短路径等)算法下的网络自适应拥塞控制进行了分析,研究了不同路由算法下的网络性能和拥塞控制效果.根据节点跳数与缓存占用的关系,提出一种基于节点跳数和缓存占用的性能函数的改进最短路径算法,算法选取使性能函数值最小的节点作为转发节点.最后,通过实验比较了最短路径算法与改进路由算法的网络性能,发现改进路由算法相比最短路径算法,具有较好的网络性能和服务质量.     

关于树的第二个最大特征值

令T(n,i)表示顶点数为n,且匹配数为i的所有树的集合,研究了T(4n-1,2n-1)中哪些树的第二个最大特征值等于√1/2[n+1+√(n+1)2-8]的一个猜想.此外,还进一步得到了T(4n-1,2n-1)中树的第二个最大特征值的3个新的上界,并且确定了达到上界的所有的树.