肖晓麟[1]2004年在《基于负载均衡的超立方体网络容错路由算法研究》文中研究表明超立方体网络是迄今为止最为重要和最具吸引力的网络拓扑结构之一。本文通过对当前网络中的拥塞控制、流量控制和负载均衡等问题的深入研究，提出和设计了基于负载均衡的超立方体网络中的单播容错路由算法。 本文研究了超立方体网络中容错路由算法的有效性及其保障机制。现有的超立方体网络中的容错模型和容错路由算法存在着安全性和有效性方面的欠缺，因而不能避免网络路由中出现的死锁、冲突、消息拥塞等现象的发生。而以前对负载均衡等技术的研究很少针对超立方体网络。本文在全面了解了当前网络上的流量控制、拥塞控制和负载均衡等技术的基础上，重点挖掘出这些技术在超立方体网络及其容错路由算法上的适用性。 本文在引入了负载均衡机制的基础上，对原有的基于局部连通性容错模型的超立方体网络上的单播容错路由算法进行了改进。改进后的算法既是简单的同时又是高效的。首先，不管所给定的超立方体网络是否满足要求的条件，算法都能适用：在满足要求的条件时，算法将成功地构造一条满足负载均衡的路由路径；在不满足要求的条件时，如果算法不能成功地构造一条路径，则算法将正确地报告出给定的超立方体网络不满足要求的条件。其次，这些算法是分布式的和基于局部信息的：网络中的每一个结点只需要知道其邻结点的状态而不要求知道网络的全局信息。更重要的是，路由算法的有效性得到了进一步的提高。模拟实验结果表明，改造后的算法不仅成功地达到了负载均衡的目的，所成功发现路由路径的概率得到了提高。
王洪伟[2]2013年在《超立方体网络中多播路由优化策略研究》文中提出超立方体是一种具有优良性质的拓扑，它具有高度冗余通信路径与强容错通信能力、结构对称引入的自嵌入性、便于增加节点的可扩展性、网络寻路算法简洁性等优点。并且其它多种类型拓扑网络均可以便捷的与之相结合形成复合型拓扑，从而该型拓扑成为了高性能并行计算机系统设计中最具吸引力的网络模型之一。应用超立方体作为拓扑连接方式的并行计算机系统性能在很大程度上取决于其所采用的多播路由策略，其主要包括多播通信策略，容错多播通信策略和不相交路径多播通信策略。多播操作产生的通信量在众多并行计算机运算环境中的全部通信量中占相当大比重，设计能够提供高效通信服务的多播通信策略是提高系统通信效率和计算机整体可靠性的有效途径。而并行计算机规模扩大带来计算节点增多，系统中出现计算节点或通信链路故障频率也随之变高，因而在存在部分节点故障和连接故障情况下为了保证系统连续正确运行，设计产生通信信息量尽量小的容错多播通信策略是一个重要挑战性问题。不相交路径路由策略从目标节点数量上分为单目标节点和多目标节点两类，单目标节点不相交路径路由是增大节点间网络带宽并提高容错能力的综合解决方案，而多目标节点不相交路径通信可以看作是以路径不相交为约束条件的多播通信，他们为网络及系统可靠性提供了更高层次保障。如何在容错能力，通信效率，通信开销等方面对这叁种通信策略进行优化成为超立方体网络路由策略研究的热点问题。本文的主要研究内容如下：以减少基于树型拓扑多播策略通信开销为目标，提出了一个超立方体网络基于逐层聚簇策略的启发式多播树构造算法（LWC-MT）。利用树型拓扑多播方案生成过程的分析结论及分簇模型，LWC-MT采用了以聚簇代价沿着最小增长方向进行聚簇操作的方法，对多播树建立过程进行了优化。仿真实验结果也表明，该算法在通信开销上优于现存算法。以在保证一定容错通信能力条件下减小多播通信开销为目标，提出了一种容错多播路由策略（FT-MT）和基于局部k维子立方连通超立方体网络的分布式容错多播路由策略（DFT-MT）。FT-MT利用近优容错路径存储模型构造容错多播方案，在保证容错能力的同时，得到了降低多播方案总体网络通信开销的优化结果。DFT-MT针对局部k维子立方连通超立方体网络，实现了对近优容错路径存储模型局部化管理和分布式存储，规避了近优容错路径存储模型在更新过程中的大量信息交换开销。模拟实验结果显示在确保满足局部k维子立方连通约束条件下，算法产生的通信开销优于相关文献中的方法。针对基于路径的多播通信中大量目标节点情况下对路径长度进行优化的问题，提出了一种基于极大目标节点分布密度的多播路径构造策略（MDPMP）和基于蚁群的多播路径构造算法（AMPA）。MDPMP利用目标节点分布密度不均匀性质进行子立方体划分，从而构造多播路径。仿真实验数据显示出在目标节点较多情形下，算法输出路径长度优于相关文献中的策略。为获得更短的多播路径，引入蚁群算法来求取子立方体划分问题（其为组合优化问题）的优化解，并以此建立多播路径，仿真实验数据表明路径长度得到了减小。进一步，论文通过把MDPMP和AMPA相结合的方式给出了分布式蚁群优化策略，有效缓解了蚁群算法引入较大计算时间复杂度问题。实验获得的数据显示，相对于源节点计算路由策略，分布式优化算法对优化结果的影响在可接受范围之内。以减小节点不相交路径通信策略的路径长度为目标，提出了一种一对多目标节点不相交容错优化路径算法和一对一不相交容错双路径算法。一对多目标节点不相交容错优化路径算法利用近优容错路径存储模型优化生成多条不相交路径，其在最长路径上限和平均路径长度两方面均优于已有算法。然后，基于一对一节点不相交多路径的特点，即在大多数情况下两条不相交路径提供了比较充分容错能力和接近扩展一倍的网络带宽，并且其求解效率也明显高于求解多于两条不相交路径，在此条件下，给出了一对一节点不相交容错双路径算法，该算法生成两条不相交路径中至少一条是两点之间经过近优容错路径矩阵充分优化的路径。
章毅[3]2011年在《K-Ary N-Cubes网络中离性能无死销多播路算法研究》文中研究指明互连网络是构成高性能并行多处理器计算机系统和决定系统通信性能的关键部分。K元N立方体是人们最早研究且仍是目前最重要的互连网络拓扑结构之一。在K元N立方体中,每一维上,每一个结点物理上都只与临结点相连。这是K元N立方体一个重要优势,使得硬件实现容易,并具有可扩展性。由于硬件上的优势和理论的普遍性K元N立方体己成为多处理器体系结构的研究焦点。多播路由技术一直是当前K元N立方体互连网络领域内的前沿和重点研究课题,因此,展开对K元N立方体网络多播路由技术的有关理论与应用技术方面的研究有非常重要的理论意义和实际意义。本文针对K元N立方体网络,提出了一种无死锁新的多播路由算法MRIFF(Multicast Routing Based on Independent Flit Flow)。在MRIFF算法中为了使得微片能够携带额外的确定它们归属的标识信息,微片的流动相互独立。附加的信息用于避免死锁。MRIFF算法允许一旦中间结点的连接准备好传送时结点发送微片。MRIFF多播路由算法消除了增加死锁避免,检测和恢复机制的必要,但是需要更大的输出缓冲。最后,利用OPNET对所提多播路由算法在不同流量模式下进行了模拟实验。模拟结果表明提出的新多播路由算法相比已有的同类算法,如DOR (dimension order routing), HTA (hardware tree-based routing), DFMR (deadlock-free multicast routing algorithm)在平均消息延迟、平均通信开销、平均负载等方面性能要优于其它协议。本文的研究工作对K元N立方体网络多播路由设计与研究具有重要的理论和实践意义。
李洋[4]2014年在《交换折迭超立方体网络结构的研究》文中研究指明拓扑结构是网络中最重要的设计问题。现有的网络拓扑结构如线性,环形,星形,二叉树等。近年来,超立方体型网络已经受到多方关注,由于超立方体很多优秀特性吸引着大规模并行超级计算系统。本文中的两个创新点分别是：1、我们提出和分析了新的超立方体型结构称为交换折迭超立方体。该新型超立方体结构是在交换超立方体的基础上通过添加二进制位距离最远的结点组成的。相对于交换超立方体,新型超立方体结构具有直径减半,更低的成本因素和恒定的结点度。对于新提出的结构,我们提出其最佳的路由算法,它是简单,易于实现。并比较了超立方体、交换超立方体、折迭超立方体、交换折迭超立方体等各种网络的网络参数属性。证明了交换折迭超立方体比交换超立方体拥有更短的直径,几乎是交换超立方体的一半,相对于折迭超立方体而言,交换折迭超立方体具有更低的硬件成本,此外,交换折迭超立方体拥有突出的成本因素,更短的延迟,更少的信息流量密度。2、负载均衡是影响网络性能指标的重要因素,因此有必要对提出的新型网络进行负载均衡研究。我们提出基于超立方体经典维负载算法的改进负载均衡算法。并考虑了在容错环境下,对J.wu提出的容错超立方体结构的负载均衡算法进行改进。提出了具有m(D 梁活民[5]2012年在《基于Cayley图的结构化P2P覆盖网络拓扑构造及资源定位研究》文中研究表明基于应用层的覆盖网络技术正迅速兴起并得到广泛的应用。结构化P2P覆盖网络凭借其去中心化、扩展性好、容错性高等优点，日益在互联网信息共享方面显示出巨大潜力。而拓扑构造和资源定位是结构化P2P覆盖网络研究两个核心问题，直接影响了结构化P2P覆盖网络的可用性和系统效率。结构化P2P覆盖网络的拓扑性质决定了其拓扑维护的代价以及节点间路由寻址的性能。常数度结构化P2P覆盖网络在保证了高效路由的同时具备稳定性强、控制信息少、网络负载小等优点，而利用小世界网络理论构造的覆盖网络较小的平均路径长度和较大的聚类系数等优点有利于提高网络的路由效率，这两点对近年来的覆盖网络拓扑研究都产生了一定的影响。结合这些因素构造具有优良特性的结构化网络拓扑是结构化P2P覆盖网络构造的重要研究方向。分布式哈希表技术使结构化P2P覆盖网络能准确定位具有精确标识符的资源，但对于不具备精确标识符的资源却非常困难。在结构化P2P覆盖网络没有目录服务器、各个节点没有全局索引的前提下，为资源定位提供更强大的查询手段是结构化P2P覆盖网络能否得到广泛应用的重要因素。论文以上述两个核心问题为主线，主要开展了以下几方面的研究工作：1.具有小世界网络特性的常数度结构化P2P覆盖网络拓扑构造。基于群论中的半直积方法和具有小世界网络特性的凯莱图模型，提出了一种新型的常数度结构化覆盖网络CayDHT。CayDHT继承了凯莱图的点可迁特性，具有简单高效的路由算法，而常数度特性使得构造大规模的对等网络称为可能。理论分析和实验表明，CayDHT具有O (l)大小的常数路由表、 O (log N)大小的网络直径和优良的容错能力，并具有小世界网络的特性。2.结构化P2P覆盖网络的多关键字搜索研究。一般来说，在结构化P2P覆盖网络中通过多关键字来定位资源需要分布式倒排索引等额外机制。水平切分和垂直切分是分布式倒排索引的两种主要存储方式，本文讨论和分析了结构化P2P覆盖网络在这两种模式下实现多关键字超集搜索的关键问题，并基于CayDHT对这两种模式进行了详细的理论分析和实验对比。3. CayDHT的复杂搜索(盲目搜索)研究。和其他结构化P2P覆盖网络一样，基于分布式哈希表的CayDHT对于不限定搜索形式的复杂搜索缺乏支持，引入传统非结构化覆盖网络的基于广播/洪泛的盲目搜索方法是必要的。本文通过分析CayDHT拓扑的性质，结合凯莱图的点可迁特性，提出了一种基于虚拟搜索树的复杂搜索算法(VTCS)，无需额外维护树结构，具有良好的负载平衡特性，可以在O(logN)的时间复杂度内完成无冗余消息的搜索分发。4.结构化P2P覆盖网络的分区复杂搜索研究。基于复杂搜索和盲目搜索的资源定位都依赖于初始化TTL参数来控制搜索的范围和减少冗余消息，而很多研究显示这种控制方法还存在比较大的缺陷。本文通过借鉴了超节点混合对等网络的优点，使用图控制集理论及网络资源布局理论，基于CayDHT提出了一种分区盲目搜索模型，该模型在搜索时只需要通过小部分搜索分发节点进行TTL参数较小的洪泛式搜索。理论分析和实验表明这种方法可以较好的控制搜索范围，并且可以保证搜索的完全性。 陈浩[6]2004年在《基于超立方体的容错性组播及路由仿真系统的研究》文中研究说明随着互联网规模和应用的飞速发展，视频会议等应用越来越广泛，传统的单播通信已经无法满足这些应用的需求，基于互联网的组播研究正方兴未艾。人们提出了控制拓扑的概念，支持大节点数的应用。因此，研究性能稳定的组播控制拓扑及其协议也就成为了当今世界上最前沿也最热门的课题之一，而超立方体又是其中的代表。 因为以往的控制拓扑具有较大的局限性，近年来超立方体结构被提出并得到了广泛的研究。完全超立方体性能突出，但对节点数的严格限制使其实用性有限。为此，人们提出了LogCube、FullCube等逻辑超立方体结构，它们消除了HyperCube的局限性，提高了结构的性能，但仍存在较大的缺陷。针对这些不足，我们分析了一种新的结构一组合超立方体结构：ComCube，并从理论上说明了ComCube在继承发扬以往结构的优越性的同时，较好地克服了逻辑超立方体的一些缺陷。 根据研究需要，我们深入研究了公认的优秀网络仿真软件NS2。针对NS2以及超立方体结构的特点，开发了基于NS2的超立方体路由仿真系统。该系统能够根据实验对象和实验要求，自动构建Tcl脚本，运行模拟实验，分析统计实验结果以及显示实验的动态过程。该系统具有良好的通用性、易用性和扩充性，能够极大提高超立方体模拟实验的科学性和工作效率，使NS2能够被更广泛地应用于研究工作中。 目前在实验中模拟组播与超立方体结构的结合，研究其性能，具有前沿性的理论与实际意义。我们利用该仿真系统，对基于逻辑超立方体的组播通信进行了模拟实验，研究不同节点出错率及节点出错位置下，逻辑超立方体结构在组播通信中的性能。根据对统计结果曲线图的分析研究，我们得到结论：逻辑超立方体在组播应用中，确实具有良好的性能。该课题的研究展现了逻辑超立方体和ComCube的性能优势，并成功设计开发了超立方体路由仿真系统；为继续深入研究超立方体结构，使其更加完善和具有推广实用价值提供了有力的工具并打下了良好的基础。 姚冲[7]2009年在《并行系统互连网络负载平衡算法的设计与实现》文中认为在并行计算领域,互连网络的拓扑结构一直是国际上研究的热点。当前,人们已提出了多种互连网络拓扑结构,其中超立方体(hypercube)是最流行的互连网络拓扑结构之一。它已被应用于商用和研究用的并行计算系统中,不少学者对它进行了深入研究。近年来的研究发现,它并不是各方面拓扑性质最好的互连网络,它自身存在着许多性能上的缺点,例如网络直径比较大,随着维数增大规模增长过快等等。于是人们开展了对超立方体的变型的研究。Efe首次提出了超立方体的一个变种网络,即交叉立方体结构,Peter K.K.Loh等人提出了超立方体的又一个变种,即交换立方体。已经证明这两个变种在结构上都对超立方体自身某些缺点进行了改进。但是,基于这些互联网络拓扑上的负载均衡算法却还停留在超立方体的阶段。以前针对超立方体设计的负载平衡算法显然不能够直接应用于其变种互联网络。本文基于当前在高性能计算的互联网络领域的研究成果,并针对两种具体的网络拓扑结构的具体特征,设计适合二者应用的负载平衡算法。验证结果可以表明,给出的算法在允许的误差范围内能够使得多处理节点间的负载达到平衡,从而可以提高整个系统的性能。 张大坤, 黄翠, 宋国治[8]2016年在《叁维片上网络研究综述》文中研究表明叁维片上网络以其更短的全局互连、更高的封装密度、更小的体积等诸多优势,已引起国内外学术界和产业界的高度重视.对叁维片上网络的研究,将直接影响一个国家未来叁维集成电路和叁维芯片产业的发展,也关系到国家安全.近年来,叁维片上网络逐渐成为片上网络研究领域的一个重要方向,已取得了许多研究进展,但仍然存在许多挑战性的课题.对叁维片上网络的基本问题作了简介;分析了叁维片上网络在国内外的研究现状;讨论了叁维片上网络研究中的关键问题,归纳出网络拓扑结构、路由机制、性能评估、通信容错、功耗、映射、测试、交换技术、服务质量、流量控制、资源网络接口等12类研究课题;分类综述了关键问题的研究进展;分析了叁维片上网络存在的问题;指出,在叁维片上网络拓扑结构方面:个性化拓扑结构设计、仿真平台研究开发、基于新型拓扑结构的叁维芯片样片试制以及无线技术的引入等,在路由算法方面:适合3D Torus的路由算法、结合无关路由与自适应路由算法优点的新路由算法、适合各种新型拓扑结构的高效路由算法等,在性能评估方面:永久故障的容错、改进仿真程序增加对物理链路的建模、充分考虑通信的局部性等,在功耗方面:对拓扑结构/映射算法/路由算法和布局进行综合优化、动态和静态控制相结合、更为精确的3D No C功耗模型等,在映射方面:发热均匀性、动态路由策略下映射评估模型的优化、低功耗映射算法、基于优化算法的组合映射等,都将是叁维片上网络未来的重要研究课题. 王洪伟, 吴智博, 左德承, 刘宏伟, 董剑[9]2014年在《超立方体网络的不相交路径通信策略研究综述》文中研究表明超立方体是一类具有良好的拓扑性质的互连网络模型。不相交路径的实现是超立方体网络中容错通信的有效保证。介绍了超立方体网络的不相交路径路由策略中的主要研究内容和研究现状,对近年来该方面取得的研究成果进行分析和总结,并指出了其中存在的问题和该策略研究的方向。 杨君刚[10]2008年在《高速多级分组交换网络若干关键技术的研究》文中认为随着Internet业务爆炸式增长和光宽带传输技术的迅猛发展,网络结点逐渐成为网络宽带化的瓶颈。路由器(交换机)的内部交换网络作为网络结点的核心部件,是目前高性能宽带信息网络研究的热点之一。单Crossbar交换网络是目前核心路由器的主流交换结构,其研究成果十分丰富,但是,由于受工程实现的限制(机架供电、芯片体积等),单Crossbar交换网络容量无法做到很大。采用多级交换结构是构建大容量分组交换网络的常用途径。直接连接网络和间接连接网络是空分多级交换网络的两种主要拓扑类型。直接连接网络虽然具有良好的可扩展性,但是网络性能难以控制,只是在大容量分组交换网络研究初期得到应用;间接连接网络是目前多级分组交换网络研究的重点。目前对多级间接连接网络(如叁级Clos网络,并行分组交换和两级交换网络等)的研究是对单Crossbar交换网络研究的简单推广,从本质上说是一种集中式控制方式,这种方式会带来调度算法实现困难,交换网络性能难以控制和无法充分发挥多级交换网络拓扑优势等问题,本文针对这些问题对多级高速间接连接分组交换网络的若干关键技术进行了研究,主要工作和贡献如下:1.提出了多级间接分组交换网络分布式调度思想。按照交换网络各级交换单元在网络中的地位不同,将它们分为负载均匀级交换单元和调度级交换单元,分别通过负载均衡策略和交换单元内部调度策略来实现交换控制。这样将多级间接连接网络的调度问题分解为负载均衡和交换单元内部的调度两个子问题来处理,带来了以下优点:(1)实现了调度算法的完全分布式,便于多机架实现。由于在分布式调度思想中,通过负载均衡级来协调调度级交换单元的业务负载,不需要在交换网络的各级和级内交换单元间进行控制信息的交换,因此,这种调度算法是完全分布式的;(2)调度算法具有良好的继承性。在分布式调度多级间接连接分组交换网络中,调度级交换单元的调度就是单Crossbar内部的调度,可以完全借鉴现有单Crossbar交换网络的研究成果;(3)算法实现简单,算法性能便于控制和分析。2.分析了叁级Clos网络分布式调度保证性能的资源需求。研究表明在叁级Clos网络分布式调度中,保证性能的网络资源需求是Clos网络保证性能的最少资源。信元乱序是叁级Clos网络分布式调度采用定长信元机制面临的主要问题之一,本文提出了一种可以实现信元保序的叁级Clos网络分布式调度调度算法——LDVSA算法,通过分析表明该算法不仅具有较好的性能同时可以实现分组信元的完全保序。3.本文在一种实现简单的分布式调度算法——RRBSA算法下,对叁级Clos网络分布式调度的交换机制进行了研究。研究表明,定长信元交换机制和变长分组交换机制在叁级Clos网络分布式调度中都具有一定的局限性,为此,本文提出了一种结合定长信元和变长分组交换机制优势的混合交换机制。这种交换机制以变长分组为单位实现负载均衡,解决了信元乱序问题;通过采用一种新型的令牌机制实现了变长分组负载分配的公平性;在Clos网络的后两级采用定长信元交换机制,获得了良好的业务适应性,研究表明混合交换机制是一种适合叁级Clos网络分布式调度的交换机制。4.对叁级Clos网络的故障进行了分析,提出了叁级Clos网络分布式调度的故障模型,通过将网络故障归结为对输入级不同队列的影响,提出了叁级Clos网络分布式调度的容错算法。对算法的容错方式、容错能力进行了分析,研究表明,该算法具有较好的容错能力。5.将分布式调度思想应用到目前研究较多的两种多级交换网络结构——并行分组交换(PPS)和两级交换网络中,克服了这两种交换网络现有研究的不足。在两级交换网络中实现了在分布式调度思想下和叁级Clos网络的统一,使得叁级Clos网络分布式调度算法得到进一步简化。利用本文的研究成果构建超大(100Tb/s以上)容量分组交换网络,可以在现有成熟技术下实现最大容量为655.36Tb/s的交换网络,远远高于现有研究成果的水平。6.提出了一种具有良好可扩展性的交换网络拓扑结构——MR网络。该网络通过在交换网络中间级引入具有直接连接网络特点的环形网络和巧妙的级间连接关系,克服了传统间接连接网络可扩展性的不足。 [1]. 基于负载均衡的超立方体网络容错路由算法研究[D]. 肖晓麟. 中南大学. 2004 [2]. 超立方体网络中多播路由优化策略研究[D]. 王洪伟. 哈尔滨工业大学. 2013 [3]. K-Ary N-Cubes网络中离性能无死销多播路算法研究[D]. 章毅. 中南大学. 2011 [4]. 交换折迭超立方体网络结构的研究[D]. 李洋. 大连理工大学. 2014 [5]. 基于Cayley图的结构化P2P覆盖网络拓扑构造及资源定位研究[D]. 梁活民. 华南理工大学. 2012 [6]. 基于超立方体的容错性组播及路由仿真系统的研究[D]. 陈浩. 中南大学. 2004 [7]. 并行系统互连网络负载平衡算法的设计与实现[D]. 姚冲. 大连理工大学. 2009 [8]. 叁维片上网络研究综述[J]. 张大坤, 黄翠, 宋国治. 软件学报. 2016 [9]. 超立方体网络的不相交路径通信策略研究综述[J]. 王洪伟, 吴智博, 左德承, 刘宏伟, 董剑. 智能计算机与应用. 2014 [10]. 高速多级分组交换网络若干关键技术的研究[D]. 杨君刚. 西安电子科技大学. 2008 标签：互联网技术论文; 路由算法论文; 负载均衡论文; 立方体论文; 分布式算法论文; 网络节点论文; 分布式技术论文; 策略路由论文; 容错机制论文; 结构化方法论文; 网络结构论文; 分布式开发论文; 分组交换论文; 通信论文; 算法论文; 参考文献：