试论互连网络中的路由算法研究

《试论互连网络中的路由算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西安电子科技大学硕士学位论文互连网络中的路由算法研究姓名：牛继云申请学位级别：硕士专业：计算机软件与理论指导教师：王长山20070101摘要互连网络是一种流行的网络拓扑，现已广泛应用于电话网络、多处理器系统、分布式计算机系统及路由器交换机等领域。作为互连网络结构之一的直连网络，以其简单的结构、良好的扩展性及便于实现分布式管理等，正被引入到新一代的大容量核心路由器中。直连网络中不均匀业务的存在要求现有路由算法具有负载均衡能力。然而直连网络中传统的路由算法未能很好地均衡网络流量，如确定性的维序算法对于一对源宿结点只提供一条固定的路径，使得分组无法绕过网络中的拥塞区域：最短路径算法的Duato算法无

2、法充分利用网络中的非最短路径资源；非最短路径算法的GAL算法是针对恶性流量模式设计的，善意模式下性能不佳。本文主要对直连网络的负载均衡路由算法进行了研究，主要的工作和贡献包括如下两个方面：l。根据自然界中的气体扩散现象，提出了一神新的负载均衡路由算法一GD(Gasdiffusjonbasedroutingalgorithm)。该算法是最短路径完全适应性算法，使用基于软件的死锁恢复机制来检测和解除死锁；它根据端口的超时分组数来确定端口的拥塞程度，然后以此为参考来随机路由分组，将分组从拥塞程度重的端口分流到拥塞程度轻的端口来均衡网络负载。我们使用OPNl’T软件在基于虚切通交换机制下的k．arvn

3、．cube网络中对其进行仿真，发现在相同的网络仿真环境下，GD算法的性能要优于传统路由算法(如维序算法、Dualo算法、GAL算法等)。2．研究了生物智能在路由算法中的应用，并提出了一种适用于直连网络的智能路由算法一FoA(FonⅣard．onlvAgentroutinga190rithm)。该算法仍是最短路径完全适应性算法，采用基于软件的死锁恢复机制来检测和解除死锁；它使用前向代理来收集网络中的有限全局信息即当前结点到其源结点的旅行时间，并以此来更新结点的旅行时间表；算法根据结点旅行时间表所记录的历史信息和当前的链路状态来共同确定一个邻结点的路由质量，并以此为参考随机路由分组来均衡网络负载。

4、我们将FOA算法与传统算法(如维序算法、Duat0算法、GA蹲法等)在基于虚切通交换机制下的k—aryn．cube网络中进行了仿真比较。仿真结果表明，相对于传统路由算法，该算法有着较低的时延和较高的吞吐。关键词：直连网络负载均衡交换机制路由算法生物智能ABSTRACT111tcl∞nnectionncMorkshaverecc玎tlyfoundwideappIications，fromtelephonenetworks，multi-proccssorsystem，diStributedsystemstogwitches／routers．AndDirectInte-c0加ectionNet、Ⅳo

5、rk(DlN)，咖etypeoftheInte-co肌eclionnetworknowsen，esasa900dcandidateforTerabjtRouterswitchingfabricsowingtoitsch缸acIeristicsofgoodScaIabiIity卸de越ydistributioncontr01．ThenOn-unifb珊tra硒ciJlDINrequiresavajlableroutingalgorithmstodist曲utelhedalaflowevenIy绑ongallthephysicallinl【s．Howevef，thet珏ditionalroutin

6、gaIgorithmsinDIN，such硒Dimensionorder枷tingaIgorithm(DoR)，Duato’sa190rithm，GALetc，donotbal卸ccthetfaf：ficVerywell．Forexample，DORonlyprovides∞eunch卸gedpathforaccnainsource—destinationpair∞thatpacketscaIlnOtbypa鲻congestedare弱inthenehⅣork；Duato’salgorittllnisaminimalalgofithmwiIhnOn—minimalpathsunexploite

7、d；GALw硒designedfortheadversarialtrafficandgiVesbadperfb册anceunderthebenjgntraf!fic．TosolVethisproblem，t、ⅣonewroutingalgorithmswercpresentedfbrDIN，GD(G勰Diffusionb弱edroutingalgorithm)whichw豁inspired的mth