硕士论文-kary ncube网络中的死锁及负载均衡研究

1、西安电子科技大学硕士学位论文k-ary n-cube网络中的死锁及负载均衡研究姓名：刘俊辉申请学位级别：硕士专业：计算机软件与理论指导教师：王长山20080101，（），；，（），谢，、（，），：创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签再褫一、

2、日迎丛关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后遵守此规定）本学位论文属于保密，在一年解密后适用本授权书本人签名：导师签名：日期日期第一章绪论第一章绪论研究背景及价值作为一种流行的拓扑网络，互连网络（）【】已经应用于电话网，多处理器系统等诸多领域。互连网络按拓扑主

3、要分为直接互连网络（）和间接互连网络（）两种主要的拓扑形式。其中，直接互连网络又称为静态网络或者基于路由器的网络（）【】；间接互连网络又称为动态网络或者基于交叉开关的网络（）。直接互连网络中的结点直接相连。每一个结点都是具有完整路由器功能的自治系统，既可以是业务的源和宿，又可以是转发业务的中间结点。相对的，间接互连网络是根据连接要求动态实现各种通信模式的互连网络。在间接互连网络中，单个结点并不具有完整的路由器功能，只能实现源、宿或者转发中的一种功能。在控制信号的作用下，通过交叉开关的设置来建立输入、输出端口之间间接的、可变的连接通路。直接互连网络【的应用非常广泛，从传统并行计算机系统等，到现在

4、的太比特交换机路由器【】以及无线通信域网络【】，应用于网络的结构】网络还在化学领域【】以及无线网络【中得到了应用。网络作为直接互连网络中最重要的一种网络拓扑，由于具有拓扑结构规整，结点度低和在单芯片上容易实现等特点，已得到了广泛的应用。如【引，【，】，全球第一台太比特路由器【，以及目前全球运算最快的超级计算机等都采用了该结构作为系统的互连网络。最近又有研究人员将其引进到微电子与通信的交叉领域片上网络（，）】中，用于解决芯片上因系统芯片（，）中的总线结构带来的时钟同步】等问题，同时实现网络中各口核（，等之间的高速互连，最终实现芯片上芯片间通信的高吞吐，低延迟，低能耗，以及占有较少的芯片面积等。在

5、信息化高速发展的今天，信息技术的先进程度已经成为衡量一个国家的综合实力一个重要的标准。不论是互连网络的核心路由器，乃至太比特路由器，还是在国际上刚处于研发阶段，而国内刚处于起步阶段的片上网络等都需要网络的技术支撑。可以说，对网络的研究具有直接的现实价值和战略意义。网络中的死锁及负载均衡研究网络研究基础及现状网络的关键技术主要包括拓扑结构的定义，交换机制的研究，路由算法研究等。而拓扑结构的定义主要是针对网络的网络拓扑外观设计进行的，力图做到较小的网络直径，较高的对分宽度带宽，以及实现规则形，对称性，路经多样性等。交换机制主要定义了分组通过交换结构的方式，也即路由器内部所采用消息传递方式。路由算法

6、主要任务是完成分组的路径选择。本部分针对网络的几大关键技术，简要介绍这些技术的理论基础及研究现状。拓扑结构网络作为直接互连网络的一种，直接进行点与点之间的连接。每个开关元件固定与一个结点相连，以建立该结点与邻结点之间的连接通路。这种网络一旦构成就固定不变，控制简单，便于分布式管理，具有良好的可扩展性。网络以结点集合的方式组织起来，每一个结点都有自己的处理机、本地存储器，及其它辅助装置。结点之间通过收发信息实现相互通信。网络中每个结点仅连接少量的其它结点以实现整个网络的互连，而这些结点即为他们的邻结点。哪些结点为邻结点是由网络的拓扑结构来定义的。与非邻结点进行通信时，需要通过邻结点来转发消息。为

7、了解决网络中的路由消息的复杂性问题，每个结点通常由一个路由控制器进行控制。路由控制器负责控制连接它与本地装置的本地输入输出通道，和连接它与邻结点路由器的网络输入输出通道。为便于探讨网络各方面的性能，及该网络的拓扑特点，有必要把，网络等直接互连网络的网络性能指标参数作一简单介绍。网络性能指标参数直接互连网络的拓扑结构对网络的性能有很大的影响，主要的性能参数【有：距离和直径：网络中，任意两结点间沿最短路径通信所经过的边称为这两个结点间的距离，整个网络距离的平均值为平均距离，记为。任意两结点间距离的最大值称为该网络的直径，记为。度：结点度指与结点相连节的边数（链路或者通道数），表示结点所需的端口数，

8、模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以迸一步表示为：结点度入度出度。其中入度表示进入结点的通道数，出度表示从结点出来的通道数。网络中个结点度的最大值为网络的度。第一章绪论网络规模：在直接互连网络中，网络的总结点数和总边数称为网络的规模，它反映了网络的大小及实现成本，也反映了该网络所能连接的部件的多少。对分宽度和对分带宽：当网络被切成相等或者相近的子网络时，所要移除的最小边数称为网络的对分宽度。如果每一信道的带宽都为，则对分带宽为。对分带宽是衡量一个网络吞吐量的一个重要参数。规则性与对称性：规则性是指网络结点连接所遵循确定的规则。在一个规则网络中，各结点连接的相邻结点数是相等

9、的。任意两个结点间通信的路径算法比较规则和简单。规则性还可以用对称性来描述。在全对称性网络中，每个结点在图中的地位是等同的：局部对称性网络中只有部分结点在集合位置上和其余部分结点对称。路径多样性：是指网络中任意两点之间都具有多条等价的不相交的路径，一个具有路径多样性的网络可以提供容错能力和负载均衡能力。连通性：它指的是当网络被分为两个不连通的网络时，所需去除的最小的边的数量。该参数用来衡量网络发生故障时网络的抗毁性（）。成本：一般由边的数量决定。可扩展性及平面性：可扩展性是指网络拓扑性能保持不变的情况下，扩充。结点的能力；平面性是指网络拓扑在平面上能否实现。这两个参数直接关系到直接互连网络实现

10、的经济性和适应性，是设计时必须要考虑的问题。拓扑结构定义拓扑结构指结点以何种方式互连，及结点间的链路配置。拓扑结构形式化描述常采用图的形式，将网络结点称为图中的点，连接结点的物理链路称为图中的边。首先简要介绍一下直接互连网络的一些拓扑结构。直接互连网络除了包含结构的网络外，还有结构网络，结构网络等。维网格埘。由毛吒一。个结点组成，毛表示维上的结点数。每一个结点由维坐标（，而，毛一。）唯一标识，其中薯也。若两个结点（，而，一。）和（，乃，以一）满足以下条件则称它们是邻结点：存在使得以咒其中，（，（），（），（）。一般当时，将该网格结构称为结构。该结构为网格结构中最常用的拓扑结构之一。下文所提的结

11、构均指该类型的结构。网络中的死锁及负载均衡研究图（）网格结构如图为的结构图。它有两个维度（维与维），在维上有个结点，在维上有个结点。其中由结点（，），（，）的坐标可知，在维上，结点的该维坐标大小与结点：的大小相同；在维上，结点的该维坐标大小比结点的该维结点坐标小。故知，与为邻结点。元网格（）。若维网格瓯满足岛吒，则称其为元网格（）。其中元网格常称为超立方结构（），如图所示为超立方结构。图超立方结构维网络鳞由向吒一。个结点组成，毛表示维上的结点数。每一个结点由维坐标（，一）唯一标识，其中薯也。若两个结点（，）和（。，一）满足以下条件则称它们是邻结点：存在使得薯（）且其中，（，（），（），（）。由

12、结构定义可知它有取模运算，因而比具有更多的边，这些边通常称为环回信道（）。如图箭头所指链路为环回信道。这些环第一章绪论回信道的作用就是使网络中结点不再有位于中心或者边缘的区别，各结点在每一维度上均有两个邻结点，故共有个邻居，亦即网络具有全网对称性。图（）一结构如图为（）结构，即维结构的网络，共有两个维度，其中一个维度（一般称之为维）有个结点，另一维（称之为维）有个结点。（元立方）网络。若维网络满足岛也吒，则称其为（元立方）网络。可以看出，网络是维网络的一种特例，也即当维网络中的所有维度上的结点数目都一样时，便成为了网络；该网络也有环回信道，在下文中也被称之为同维环。如图，（）图（），即网络的拓

13、扑结构。该网络共有两维，每维的结点数目为。图（）为网络的拓扑结构，也即为（）一结构，共有个维度，每个维度都有个结点。国一铲入一圆留钍一）卜甚卜甚卜上（）（）图（）结构图（）（）一结构图网络拓扑结构网络中的死锁及负载均衡研究在网络基础上，最近还有一些人提出一些类似的结构，如羽，】以及【】等。很明显，理想的拓扑结构是全连接结构，即每个结点都与网络中的所有其它结点相邻，所以消息传递不用经过任何中间结点。网络规模为的全连接结构中，每个路由器需要（）条链路，当网络规模较大时，网络的成本非常的高。另外，一个结点物理连接的数量由于受到硬件技术的限制也可能很大。这些工程和可扩展性方面的困难排除了使用全连接的实

14、用性。为此研究人员提出并研究了大量的网络拓扑结构，目标是在网络成本和网络性能方面找到一种平衡。在表中汇总了一些直接互连网络拓扑结构的重要特性以及它们之间的比较，其中为结点数，刀为维度数目。各种网络结构各有特点与优势，当在高性能与价格做适当权衡时，具有较好拓扑结构性（如结点度低、直径较小等）、算法容易实现以及容错性好的网络是较合适的选择。因此，具有较好的扩展性，较低的网络直径等性能的网络正是本文研究所选择的拓扑结构。表直接互连网络拓扑性能参数表网络结点度直径链路数目对分带宽对称性网络规模和说类型，明线形阵列一一非个结点环形网是今结点全连接一是个结点（一）（）二叉树（一）非树高非一（万一）（一打）

15、捆（瓶瓶）个结点晦是厨（届届）个结点星型一一非个结点超立方刀拧是网，是个结点络第一章绪论交换机制交换机制决定着分组从源结点到目的结点之间路由时，通过各结点交换结构的方式，直接影响着网络的性能，以及路由算法的设计。它同时还决定了内部开关连接路由器的输入和输出端口的时机和方式等。网络中比较常见的交换机制有电路交换（，）存储转发交换（，）虫孔交换（，），虚切通交换（，）等【。还有一些人提出了比较有特点的交换方式，如管道式电路交换（，），以及将虫孔交换与虚切通交换相结合的交换方式【】等各种交换方式。、电路交换（）该交换方式是早期采用的一种交换方式。它要求每次传输消息前都要在源结点与目的结点之间先建立一

16、条专用链路。链路的建立通过向网络注入一个头片（），利用该头片探测网络来完成。首先，源结点向网络中注入一个头片，该头片一边朝目的结点前进一边建立链路。若头片在中间结点受阻，它便产生一个释放片（）并发回源结点，同时释放已占链路。一旦头片到达目的结点，等它便产生一个应答片（）并发回源结点。当源结点收到应答片时，源结点便知链路已成功建立并开始发送数据片（），传输结束后释放所占用链路。电路交换中，每次传输数据前都要在源结点与目的结点之间建立一条专用的通信线路。一旦进入数据传输阶段，消息就不会阻塞。因此电路交换的优点是可靠性高，几乎没有抖动，能够很好的保证服务质量（，）。同时，当消息传送次数不是很频繁且消

17、息很长，即消息传输时间远远大于路径建立时间的时候，电路交换也是有优势的。但是由于它的独占性，链路带宽得不到复用，有可能阻塞其它的消息，所以链路利用率低。因此，在数据网络中一般不考虑采用电路交换的方式。存储转发交换（）在电路切换中，只有电路建立后才开始进行整个消息的传输。因此该交换中对消息进行固定带宽分配的方式，严重影响了网络资源（链路等）的利用率，为此，储转发交换相继被提出了。该交换机制将消息进行切割，分割为各个较小的分组，因此也经常将这种交换称之为分组交换（）。每个分组的前几个字节包含路由和控制信息，可以独立从源结点到目的结点独立路由，绕开各种故障或者拥塞区域等。中问结点在接受到分组后，首先

18、将整个分组接收下来放在当前中间结点的缓冲区内，然后读取分组头部受携带的路由信息进行查表路由。如果当前结点不是该分组的目的结点，则按照所查的路由表将分组转发出去，否则分组被提交到网络的高层处理，完成存储与转发的整个过程。一网络中的死锁及负载均衡研究采用该交机制的路由算法具有一定的容错性与负载均衡性；同时，由于该交换机制相对电路交换的固定带宽分配来说，它的带宽是动态分配的，这样就使得通信链路的带宽资源利用率大大提高了，因此，非常适合应用在一些含有的突发性业务的网络，如计算机网络等。当然，该交换机制也具有一定的缺陷性。该机制将报文分成多个分组进行传输，各分组头所携带的控制信息必然要引入额外的开销；另

19、外，分组交换的端到端时延与结点对之间的距离成正比，随着网络规模的扩大，网络时延也会越来越大，不适合应用于大规模的网络中。虫孔交换（）该交换机制是受虫子，蚯蚓等动物的前行过程启发而设计的一种相对智能型的交换机制。蚯蚓等动物的身体分为很多结状部分，在前行过程中，头部首先向前探路，而身体的其它结状部分随着身体的前行，慢慢前行。直至到达目的地。在虫孔交换机制的设计时，将整个分组分割为更小的片（）。这些片可分为头片（与数据片（）两类。头片含有路由信息，可进行路径的选择，数据片不具有选路功能。整个分组的路由是由头片带路，数据片紧跟头片向目的结点路由来实现的。而该交换机制特别设计时强调每个信道只有一个片大小

20、的缓存。该交换机制下的传输时延可粗略计算为：其中为源目的结点间的跳数，三为消息长度，形为信道带宽。由上式可以看出，当时，时延对距离不敏感，因此适合于大规模网络结构的应用。正是由于这个优点，虫孔交换机制被广泛应用于当前的商用并行计算机，太比特路由器等中。但是，它也存在自身克服的缺点，当输出信道繁忙而导致头片受阻时，尾随其后的数据片也不能前进，都停留在网络中各结点的缓存中等待，这进一步阻塞了其它头片，造成网络拥塞，性能下降。虚切通交换（）虚切通交换的提出正是为了弥补虫孔交换的不足，两者的不同之处在于虚切通交换的结点缓存设为个或几个分组大小。当头片受阻时，虚切通交换允许后续数据片继续前进到头片受阻的

21、结点，并释放它们所占的资源，从而减少了进一步阻塞的可能。它与虫孔交换一样，其平均时延对距离也不敏感，并且由于它增加了信道中缓存的大小，使得后续的数据片可以进入该结点的缓存而非停留在中途路径上的各个结点中，因而其阻塞概率小，可以达到比虫孔交换更大的吞吐量。管道式电路交换（）管道式电路交换综合了电路交换与虫孔交换的特点。它将分组进行分割成片，并像虫孔交换一样，用头片来探测路径。头片在探测路径以及受阻释放路径的过程，是运用电路交换机制的方法进行的。比较特殊的是，管道式电路交换机制下，在头片到达目的地发挥反馈之前，源结点中的数据片和尾片都不得发送。这样相。第一章绪论当于为每个分组建立了端到端连接，从而

22、确保时延上界，而且在头片探路过程中，绕开了故障区域，后续分组可以在存在故障区域的情况下到达目的地。因而该交换机制具有一定的容错性。同时也保证了数据的可靠传输，比较适用于传输质量要求高的业务。当然，该交换机制也具有一定的缺陷性，如建立连接开销过大，很容易造成网络饱和，吞吐能力差等。由于电路交换，管道式电路交换等交换方式都需要进行链路的建立，使得这些额外开销过大，而存储转发交换等中端到端的时延与结点对之间的距离成正比，不具有扩展性。所以，相对比较普遍适用的，而且优异的交换机制就要算冲孔交换与虚切通交换了。这两种交换方式均采用流水线式的消息传输模式，使得端到端的时延对距离不敏感。与虚切通的大缓存需求

23、不同，虫孔交换要求信道的缓存只有一个片的大小，这就减少了交换结构设计的复杂度，同时减少了硬件设计的成本。但是，虫孔交换机制与虚切通交换机制相比，它的最突出的缺点就是，由于它要求信道的缓存只能为一个片的大小，所以分组在向前路由时，其数据游被分散在头片后面的众多中间结点中，并占用着这些中间结点的相应信道的缓存资源，从而易于阻塞其它分组的前行。特别是在高负载下，分组之间的相互阻塞最终导致网络中出现大面积拥塞区域，严重降低了网络的整体性能。故此，在本文后面的所有仿真中，均采用虚切通交换机制进行。路由算法路由算法主要职责是确定分组由源结点向目的结点路由时的路经选择，决定着分组在网络各结点中进行路由决策时

24、转发端口的选择。并在很大程度上决定分组的端到端时延和整个网络的吞吐，乃至路由器结构的硬件设计等。在一个实际的路由器设计中，路由决策处理应尽可能的快速，以减少网络时延。一个好的路由算法还应具有很好的硬件可行性。而且，路由决策通常不应该要求网络全局状态信息。提供这些全局状态信息增加了额外的网络流量并要求每个路由器额外的存储空间。下面是一个好的路由算法法设计时首先要考虑的一些因素：连通性：分组在任意两结点间都可以路由的能力，即保证网络中任意两结点之间的可达性。自适应性：存在竞争和故障部件时，通过其他可选路径路由分组的能力。死锁和活锁的解决性：确保分组不会永远阻塞或者永远在网络中游荡而到达不了目的结点

25、的能力。容错性：在存在故障部件时对分组进行路由的能力。均衡性：网络中业务的不均衡性要求路由算法能够具有均衡负载的能力。负载均衡算法可以使交换网络中的各种资源能够得到充分利用，避免网络网络中的死锁及负载均衡研究中某些部分资源充足，而其他部分资源紧张的现象。服务质量保证：由于网络中很多业务对服务质量（）有要求，因此路由算法设计中除传统参数外还要考虑一些参数，如链路剩余带宽等。网络路由算法（本文指单播路由算法）可按照多种方式进行分类。为便于研究，一般将其分为确定路由算法和自适应路由算法。确定性路由算法指，分组在从其源结点向目的结点的路由过程中，只选择某一条路径。不管网络状态是否拥塞，确定性路由算法都

26、不会改变它的路径选择。维序路（，）是一种常用到的确定性路由算法。它是指每个分组在一段时间内只在同一个维度空间内传送。这种路由算法设计简单，易于实现，设计成本较低。但是由于它没有适应性，不能提供多条可选路径，所以无法适应网络负载的变化，不具有负载均衡能力；以及在网络出现故障的情况下，使得某些分组无法到达目的结点，没有容错性。针对确定性路由算法的这些缺陷，适应性路由算法被提出了。适应性路由算法可以细分为部分适应性路由算法与完全适应性路由算法。按照路径的长度又可以将适应性路由算法分为最短路径适应性路由算法和非最短路径适应性路由算法。部分适应性路由算法是指分组在其可进行路由的路由区域内，只能选择该区域

27、内的一部分路径进行适应性路由。比较典型的部分适应性路由算法主要有转弯模型（）【中的三个路由算法：西优先路由算法（），北最后路由算法（），以及负优先路由算法（）。这些算法在第三章有具体介绍，在此就不加以赘述。相对于前两类算法，完全适应性路由算法可在允许的区域内的任何路径上路由。分组从源结点向目的结点路由过程中，可根据网络的负载状况，选择负载较轻，路径较短的区域进行路由。这样就可以绕开故障或者热点区域进行路由，所以具有较强的负载均衡性与容错性。最短路径适应性路由算法比较有代表性的算法有】算法等，该算法允许分组在最短路径区域内适应性路由，相比维序路由算法等确定性路由算法，提高了网络的吞吐、时延等性能

28、。非最短路径适应性路由算法主要指分组既可以在最短路径适应性路由，也可以在非最短路径路由区域适应性路由，典型的算法有】算法，算法【】，算法【】等算法。在网络中，这些算法基本都是以区域（）进行路由的。不同之处主要在于它们对衡量网络负载的参考因子的选择不同；相同之处是它们都将将网络进行区域划分，并只允许分组在某一区域进行适应性路由。由于死锁、活锁、饿死是路由算法设计时，首先要解决的问题。它们的产生会对路由算法的设计产生极大的影响，所以下，节专门对这三种研究课题的相关技术基础与现状作一简单介绍。第一章绪论死锁、活锁、饿死自适应路由算法设计不好将会导致路由死锁，活锁，饿死，因此，这三者的解决，是路由算法

29、，特别是适应性的负载均衡路由算法设计时首先要考虑的。死锁是由于分组争用网络中的缓冲区资源，得不到前进所需的空闲缓冲空间造成的。路由芯片或开关需要一定的缓冲空间来存储部分分组或整个分组，但是缓冲器的容量是有限的。对于那些还没有到达目的结点的分组，一方面请求缓冲区，另一方面又占用当前缓冲区，就可能产生死锁。当某些分组因为请求的缓冲区己满而不能朝着它们的目的地前进时，死锁发生了。处于死锁配置内的所有分组将永远被阻塞。路由过程存在相互依存的环形信道依赖结构是死锁产生的必要条件。死锁的解决主要有两种方式：死锁避免，死锁检测与恢复。死锁避免中，只有当申请的资源不破坏全局状态安全时，分组才可以获得它所申请的

30、资源。这种策略应该避免发送额外的分组来更新全局状态，否则这些分组既消耗网络带宽，也可能会导致死锁。比较常用的死锁避免方法有转弯模型以及提出的虚信道模型邛。转弯模型主要是针对网络提出的死锁避免解决方案。它是通过禁止分组在路由时的部分转弯来打破环形依赖关系来解决死锁的。虚信道模型生要是将一条物理信道分为几条逻辑信道，在分组路由时，根据分组所在位置不同等不同情况，限制分组对一部分逻辑信道的使用，从而解决死锁的。可以将整个死锁检测与恢复策略的过程分为两个阶段检测过程与恢复过程。由于该策略要求网络在资源分配时不进行任何检查，所以可能出现死锁。因此必须提供某种检测机制进行死锁的检测。如果检测到死锁，就必须

31、释放该死锁分组所占用的某些资源并分配给其它分组，用以解除死锁。为了释放资源，通常就需要将检测的分组移出其所占用的缓冲资源，并对该死锁分组进行处理，也即要进行恢复的过程。因此，整个检测过程与恢复过程都直接影响着死锁的解决效率以及准确率。一些比较有代表性的死锁检测与恢复算法有算法【，算法【，算法【】，算法【】等。算法为“丢弃重传”型算法，它要求在检测到分组为可能的死锁分组时，要将该分组整体销毁，并释放所占的资源，来解决死锁，并从该分组的源结点重传；算法采用超时机制，算法采用输出信道处于忙状态的时间长短来检测死锁；算法采用生成树来检测资源之间的依赖关系来检测死锁以及只处理较少的死锁分组而达到整个环中

32、死锁处理的目的。死锁避免策略比较保守，在分组请求时，为了避免产生死锁，限制了分组对一部分资源的使用。死锁恢复策略则比较乐观，但是只有在死锁很少出现而且死锁的后果可以容忍时才可以使用它。活锁、饿死的解决相对比较单一，简单。活锁是指在无死锁的情况下分组总也到不了目的结点的情况。只有允许分组沿非最短路径发送时才会产生这种情况。网络中的死锁及负载均衡研究因此通过利用最短路径就可以避免活锁的产生。饥饿是指分组在某结点始终等待调度却总轮不到输出，这通常是由于调度算法的资源分配不合理而导致的。因此采用公平的调度算法是解决饥饿问题的有效途径。如简单的轮询机制，如果存在业务等级划分，那设计算法时应该为低优先级业

33、务预留一定的资源。论文研究内容及结构安排网络是一种有着广泛应用的网络。本文从网络的拓扑结构、交换机制等几大关键技术着手，根据该网络的拓扑特性，综合考虑交换机制等对网络性能的影响，针对路由算法中的死锁与负载均衡等进行深入研究。本文的内容及结构安排如下：第一章首先介绍了研究的价值，研究基础及现状；第二章介绍了网络中的死锁及负载均衡相关理论知识，以及现有与之相关的解决方案及路由算法；第三章在综合分析现有死锁理论及分析对比已有死锁检测策略的基础上，提出了一种死锁检测能力较强，受网络业务分布影响较小的死锁检测算法死锁检测算法（），并给出一些中肯的意见；第四章在对比分析已有的负载均衡路由算法基础上，提出了

34、一种适应性更高，负载均衡能力更强的跨区域适应性路由算法（）算法；第五章对全文进行了总结。第二章已有死锁与负载均衡技术研究第二章已有死锁与负载均衡技术研究死锁死锁是路由算法设计时首先要解决的技术问题之一。死锁的解决程度，以及解决方式，直接影响到算法在网络中的实施，乃至影响到整个网络的性能。如果算法未能很好的解决死锁，将会使得分组因为其对资源的请求受阻而导致相互僵持，无法继续路由，出现整个网络瘫痪的局面。故，死锁问题的解决是非常重要的。死锁定义死锁是指分组在网络中路由时，因对网络中的资源（信道缓存等）申请而形成的环形依赖关系。环中的各分组因无法打破这种关系，形成一种僵持状态。使得各分组都被锁定在各

35、自位置，无法继续向前路由。本文所有环、死锁环均指信道依赖图（下，节，即节有定义）中的环。信道依赖图中如果存在环形依赖，则该环中的分组必死锁（参见下，节的推论），故本文称这种依赖环为死锁环。环的形成方式有两种，逆时针环的形成与顺时针环的形成。这两种环的成因与解决方式等都是一样的。因此，研究时，只要研究一种，另一种就可以相应的推出。如图中，图（）为顺时针死锁环，图（）为逆时针死锁环。以图（）为例，分组、矛分别在结点、和中的信道，信道尺，信道恐与信道飓的缓存（指环内部的信道缓存，下同）里。而肋、：所申请的信道缓存资源分别为信道，信道飓、信道飓与信道中的缓存资源。由于这些信道的缓存资源又分别被其它分组

36、占用，这样就使得四个分组都申请不到下一结点的缓存资源而僵持下来，因而都无法继续前进，形成死锁。：堂：一且：（）（）图死锁举例网络中的死锁及负载均衡研究死锁理论基础年，在文献【】中，给出了无死锁的充分与必要条件等死锁相关的理论。下面对该理论进行简要的介绍，为下一章的死锁检测算法设计做理论支撑。相关符号定义）一个互连网络仁“是一个强连通的有向图。图的顶点表示结点集合，弧表示信道集合。任一条信道。都有一个容量为（的队列与之相关联。信道，的源结点和目的结点分别表示为毋和西。）自适应路由函数：（），其中尸是信道的集合，它提供一组可选的，从当前结点向目的结点发送分组的输出信道。（。，矽，叫。因为结点不能通

37、过网络向自己发送，所以（，刀），。）给定互连网络，路由函数是连通的，当且仅当：（，少），吼（九一，），纡，即，用以尺提供的信道建立一条从到的路径是可能的。）给定互连网络，路由函数尺，相邻信道对，巳，至之间存在着直接依赖，当且仅当：，（，），并且，（盔，），即当发往结点的分组使用完后可直接请求巳。相邻意味着。）信道依赖图（，）是给定互连网络，和路由函数的一个有向图。的顶点是网络的信道，弧是从，到间存在的直接依赖对（，）。）对于给定路由函数和路由子函数蜀，它是在与相同的域上定义的路由函数，同时提供了路由函数提供的信道子集：。（，）（，），提供的信道集为：忱胙墨（，）。第二章已有死锁与负载均衡技术研

38、究相关定理无死锁定理：互连网络，的启适应路由函数是无死锁的充要条件是：存在一个路由子函数尺，它是连接的，而且它的扩展信道依赖图中没有环路。该定理对确定性路由和自适应路由都是有效的。当然对于确定性路有算法来说，扩展信道依赖图与信道依赖图是一样的。根据该定理可知，如果其扩展信道依赖图中有环路，则必定存在死锁。下一章中，运用本节相关理论知识，根据信道依赖图中的是否会导致环路（下文称之为环形依赖，或者环）对死锁进行检测。死锁解决相关技术由于死锁的出现将会严重降低网络性能，乃至瘫痪网络，所以死锁解决技术一直以来都是网络的研究热点之一。总的来说，可以将现有的死锁解决技术分为两大类：死锁避免技术与死锁检测恢

39、复技术。死锁避免技术主要是在路由算法设计时，对分组的路由决策作一定的限制，打破死锁形成的重要条件一环的形成，进而使得分组在网络中路由时，不会出现环形依赖现象；最近几年，有研究表明，除了在饱和状态下，死锁发生的概率很小【】。因此，就如文所指出的，为了极少出现的死锁而去限制分组路由的适应性（也即设计死锁避免算法）那是一种无谓的浪费。这也就促使一种新的死锁解决技术死锁检测与恢复技术】的产生。死锁检测与恢复技术的主要思想是首先根据特定路由算法的思想，允许分组用所有可以用到的资源，而一旦检测到出现了死锁情况，则对死锁分组进行处理，进而来解除死锁，最终解决因网络中出现死锁而使分组相互阻塞，最终导致性能严重

40、下降的问题。下面分别描述这两种技术的现有研究成果。死锁避免技术死锁避免技术主要是限制分组在路由决策时对部分资源（缓存等）的利用，来达到网络中的无死锁。由于网络自身在每一维中都存在一个环，所以在避免时，不但要避免不同维度之间形成的环形依赖，还要避免同一维度内部形成的环形依赖。故网络的死锁解决基本以虚信道模型为解决框架，再辅助以转弯模型来设计多种类型的死锁避免算法。为了描述简便起见，将转弯模型与虚信道模型分开进行描述。在网络中，在具体进行死锁避免时，只需将转弯模型与虚信道模型结合即可。网络中的死锁及负载均衡研究转弯模型该模型首先是针对结构的网络提出的，主要是指分组在特定路由器中时，通过限制分组的转向，进而限制其对部分链路资源的利用来达到死锁的避免。该部分的主要现有技术有维序路由算法【】，以及和提出的三种死锁避免算法（，）等。维序路由算法维序路由是一种最短路径的确定性路由算法，也是一种无死锁路由。所谓维序路由，是指按既定的维度顺序校正自己的位置，只有本维校正完成之后，才能进行下一维度的修正。如图为网络中维序路由举例，其中表示坐标原点，表示分组的源结点，现表示分组的目的结点。该网络中，分组从其源结点昂向其目的结点见进行路由。首先分组进行维的路由，当的坐标偏转完之后，也即到达结点瓦后，再进行维的路由，最终到达