k-ary n-cube网络中的死锁及负载均衡研究

论文摘要

作为互连网络中一种流行的拓扑网络,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的性能优于这些传统路由算法。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景及价值
• 1.2 k-ary n-cube 网络研究基础及现状
• 1.2.1 拓扑结构
• 1.2.2 交换机制
• 1.2.3 路由算法
• 1.2.4 死锁、活锁、饿死
• 1.3 论文研究内容及结构安排
• 第二章 已有死锁与负载均衡技术研究
• 2.1 死锁
• 2.1.1 死锁定义
• 2.1.2 死锁理论基础
• 2.2 死锁解决相关技术
• 2.2.1 死锁避免技术
• 2.2.2 死锁检测与恢复技术
• 2.3 负载均衡
• 2.4 本章小结
• 第三章 基于环的死锁检测路由算法研究
• 3.1 死锁问题描述
• 3.2 CDD 死锁检测算法详述
• 3.2.1 算法来源及知识预备
• 3.2.2 算法设计与实现
• 3.3 CDD 算法的死锁解决性证明
• 3.4 算法仿真及对比分析
• 3.4.1 仿真参数设置
• 3.4.2 仿真结果分析
• 3.5 有关死锁的几点考虑
• 第四章 跨区域适应性的负载均衡路由算法研究
• 4.1 算法动因
• 4.2 算法详述
• 4.2.1 路由区域的划分
• 4.2.2 路由区域权重的设定、边界点及可跨区域的定义
• 4.2.3 路由决策详述
• 4.3 QCR 算法死锁活锁的解决性证明
• 4.4 算法仿真与结果分析
• 4.4.1 仿真参数设置
• 4.4.2 仿真结果分析
• 4.5 本章小结
• 第五章 结束语
• 5.1 工作总结
• 5.2 展望
• 致谢
• 参考文献
• 在读期间研究成果