论文部分内容阅读
作为互连网络中一种流行的拓扑网络,k-ary n-cube网络目前面临着多应用、多业务以及业务分布不均等问题,这就要求设计的路由算法要有较强的负载均衡能力,以及所采用的死锁解决算法具有适应各种网络业务的能力。当前相关技术都没有很好地解决这些问题,如负载均衡路由算法存在着资源利用失衡等问题;死锁方面则存在着死锁检测时误检率过高等问题。基于此,本文的主要工作和贡献包括如下两方面:1.在研究现有死锁技术的基础上,提出了基于环的死锁检测路由算法(Cycle based Deadlock Detection routing algorithm,CDD)。与传统检测算法仅采用超时机制不同,CDD从信道依赖环——死锁形成的原因入手对死锁进行检测。根据k-ary n-cube网络拓扑特性,CDD分别检测同维环中形成的死锁与不同维(即异维)环中形成的死锁。在同维中CDD运用流控策略,即分组进入当前所在信道前,该信道的缓存剩余量大小进行检测;在异维中CDD则通过分组的转向来检测。CDD继而对那些初步检测判定为死锁的分组,分别根据其所申请的所有输出信道处于忙状态的时间间隔做最后的检测。本文运用OPNET仿真软件对其进行仿真,结果表明,CDD与现有soft-based死锁检测算法相比,具有较低的死锁误检率,较低的时间门限值敏感性等。2.针对现有负载均衡路由算法存在的问题,提出了跨区域的适应性路由算法(Quadrant Crossing Routing algorithm,QCR)。QCR按照分组源、目的结点相对位置将网络划分路由区域,并给予这些区域不同的权重,同时设定跨区域规则,允许分组根据网络负载状态,跨区域路由。这就提高了分组路由的适应性,并使网络的负载更均衡。网络的负载程度由输出端口等待分组请求的时间间隔的大小决定。运用OPNET对QCR在不同流量模式下进行仿真,结果表明,相比已有同类算法,如维序算法,Duato及GAL等算法,QCR的性能优于这些传统路由算法。