（计算机应用技术专业论文）基于负载均衡的超立方体网络容错路由算法研究.pdf

摘要 超立方体网络是迄今为止最为重要和最具吸引力的网络拓扑结 构之一。本文通过对当前网络中的拥塞控制、流量控制和负载均衡等 问题的深入研究，提出和设计了基于负载均衡的超立方体网络中的单 播容错路由算法。 本文研究了超立方体网络中容错路由算法的有效性及其保障机 制。现有的超立方体网络中的容错模型和容错路由算法存在着安全性 和有效性方面的欠缺，因而不能避免网络路由中出现的死锁、冲突、 消息拥塞等现象的发生。而以前对负载均衡等技术的研究很少针对超 立方体网络。本文在全面了解了当前网络上的流量控制、拥塞控制和 负载均衡等技术的基础上，重点挖掘出这些技术在超立方体网络及其 容错路由算法上的适用性。 本文在引入了负载均衡梳制的基础上，对原有的基于局部连通性 容错模型的超立方体网络上的单播容错路由算法进行了改进。改进后 的算法既是简单的同时又是高效的。首先，不管所给定的超立方体网 络是否满足要求的条件，算法都能适用：在满足要求的条件时，算法 将成功地构造一条满足负载均衡的路由路径；在不满足要求的条件 时，如果算法不能成功地构造一条路径，则算法将正确地报告出给定 的超立方体网络不满足要求的条件。其次，这些算法是分布式的和基 于局部信息的：网络中的每一个结点只需要知道其邻结点的状态而不 要求知道网络的全局信息。更重要的是，路由算法的有效性得到了进 一步的提高。模拟实验结果表明，改造后的算法不仅成功地达到了负 载均衡的目的，所成功发现路由路径的概率得到了提高。 关键词：互联网络，超立方体网络，负载均衡，容错路由算法，局 部连通性 a b s t r a c t h y p e r c u b en e 似o r kl s o n eo f l em o s t 姗p o r t a n ta n da t t r a c t l v e n e t w o r k t o p o l o g i e s s of l a tb a s e do na m o r o u g hi n v e s t 蟾a t i o n o n c o n g e s t i o nc o n 仃o l ，日o wc o n 仃i 胡a n dl o a db a l a n c i n gp r o b l e n l so nc u e n l n e 铆o r k s ， w e d e s i g i l a n d d e v e l o p u i l i c a s tf 砌tt 0 1 e r a n t r o u c i l l g a l g 嘶t h m s o n h y p e r c u b e n e t 、) l ，o r l ( sw i ml o a d b a l a i l c i r 培s u p p o r t w es t u d y v a l i d i t y a n d s a f e g u a r d o nf a u nt o l e r a n t r o m i i l g o n h y p e r c u b e n e 帆o r k s n e e x i s t m g f l a l j i tt o l e r a n tm o d e l sa n df a u i tt 0 1 e r a n t r 0 1 n i n ga l g o r i l i n s o nh y p e f c u b en e 铆o r k sa r es h o r to fs e c 嘶t ya n d v a l i d i t y ， s o m e y c a l ln o ta v o i dd e a d l o c k ，c o n n i c ta i l d m e s s a g e c o n g e s “咖o nr o u t i l l g 。m o r e o v e r ，v e r yf e w r e s e a r c h e so nl o a db a l a n c 血g c a nb ef o u n do n 也e h y p e r c u b en e t w o r k s b a s e do n l ec o m p r e h e n s i v e 1 1 1 1 d 盯s t 跚d i n go f b o w c o n 仃o l ，c o n g e s t i o nc o n 乜o la n dl o a db a l 撇c m g o n c u r r c i n tn 咖o r k s ，w ec o n c e n 拄a t eo nm e a p p l i c 曲i l 时o f m e s e t e c h n i q u e s o nm es 仃u c n l r e sa i l df 剐tt o l e r a i l t r o u t i n ga l g o r i n l l _ i l s o nh y p e r c u b e n e t 、v o r k s b a s e do nl o a db a l a n c i i l g ，w e 妇p r o v e dm e 耐g i n a lu n j c a s tf a u l t t o l e r a n tr o u 妇ga l g o r i t so nl o c a l l y c o 锄e c e dh y p e r c u b en e 觚o r k s t h en c w a l g o r i 舳l sa r es i m p l ea n de m c i e n t f 破l y ，m e s ea l g o m m s a r e 印p l i c 曲l en om 蚍e r w h e m e rt 量l e g i v 跚h y p e r c u b en 酿o r ks a t i s f i e st l l e r e q u i f e m t s o rn o t ：j 1 1c a s et l l en e t w o r ki s l o c a l l yc m m e c t e d ，t h e a l g o r i 肌 i l ss u c c e s s f i l l l yc o n s 饥l c tm em u t i i l gp a mw i m l o a db a l a n c i n g s u p p o r t ，w e 访c a s e o u r a l g o r i m m sf a i li l lf m d i n gam u t i n gp a m ，t 圭1 e y 1 1 e p o r tc o r r e c t l y 也m 仳1 en e 撕o r k i sn o tl o c a l l yc o 蛐e c t e d s e c o n d l y ，0 u r r o u t m ga i g o f i t l l m s a r ed i s t r i b u t e da i l dl o c a l i 芏l f o r m a t i o n - b a s e di 工lt h e s e n s e 也a te a c hn o d ei n 也en e 帆o r k i m o w s 础y i t sn e i g h b o r s 蛐s8 i l d n o g l o b a l i 1 1 f o n 】1 a c i o no fm en e t w o r ki s r e q u 眈db yt h ea l g o r i m m s ， a b o v ea l l ，v a l i d i 够i si n l p r o v e dm o r ei i lo u rr o u t 协g 如o r i t h m s 1 1 1 e s i n l u l a 士i o nr e s u l t ss h o wt l l a t ，n o t o i l l y l o a db a l a n c i l l gi s r e a c h e d ，t h e p r o b a b i l 竹o fs u c c e s s m u yf m 曲玛r o u t i i l gp a m s i sa l s oi f l c r e a s e d k e yw o r d s ： i i l t e r c o 蛐e c t i o n n e t 、v o r k s ，h y p e r c u b en e 觚o r k s ， l o a d b a l a i l c i i l g ，f a u l tt o l e r a n tr 棚恤ga l g 谢t h r n s ，l o c a l c o 曲e c t i v 埘 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在在论文中作了明确的说明。 作者签名： 日期：斗年4 月望曰 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根 据国家或湖南省有关部门规定送交学位论文。 作者签名 导师签名罐三日期：垒竺虹年旦月纽日 硕十学位论文笫一章绪论 第一章绪论 本章首先介绍什么是超立方体网络，然后介绍本课题的研究意义，然后分析 超立方体网络容错模型和容错路由算法的研究现状，然后介绍本课题的研究内容 和本文的主要创新点，最后是本文的组织结构。 1 1 超立方体网络结构及其表示 本节给出n 维超立方体网络峨和其中的维子立方体网络的定义，它们是 本文研究的基础。 定义1 1 维超立方体网络) n 维超立方体网络风( 或简称为n c u b e ) 是具 有下述性质的一种网络拓扑结构：( 1 ) 它由2 ”个结点和m 2 州条边构成；( 2 ) 每 一个结点可由一个不相同的n 位二进制串6 1 6 2 k 进行编号；( 3 ) 结点编号的规 则为，当且仅当风中两个结点的二进制串恰有一位不同时，两个结点是相邻的， 即这两个结点之间有一条边相连。 图1 1 是3 维超立方体网络的图例，图中有2 3 = 8 个结点和3 2 z 1 2 条边，图 中还标识出了结点的编号( 分别从0 0 0 到1 】1 ) 。 e 0 0 图1 13 维超立方体网络 7 f 0 硕+ 学位论文第一章绪论 许多文献皿1 在看待超立方体时，往往将每个结点称为一个处理器，那么 个”维的超立方体由2 ”个处理器组成。由一个处理器甥成的系统称o 维超立 方体，二个处理器组成的系统称1 维超立方体，四个处理器组成的系统称2 维超 立方体，以此类推。而在超立方体系统结构中，把处理器称为结点( n o d e ) 。也 有的文献【0 】i ” 0 50 6 1 还用图的概念来表示超立方网络的。 图1 2 是4 维超立方体网络的图例，图中有2 4 = 】6 个结点和4 2 4 。= 3 2 条边， 图中还标识出了结点的编号( 分别从0 0 0 0 到1 1 1 1 ) 。很明显，4 维超立方体网络 可看作由两卜3 维超立方体网络通过将对应结点用一条边连接起来构成，以这种 方式来看待4 维超立方体网络时也很容易对各个结点进行编号。 0 d 7 0 0 ，7 do 77 d 7 7 图1 24 维超立方体网络 图1 3 是5 维超立方体网络的图例，图中有2 5 = 3 2 个结点和5 2 5 - 1 = 8 0 条边， 图中还标识出了结点的编号( 从o o o o o 到1 1 1 1 1 ) 。很明显，5 维超立方体网络可 看作由两个4 维超立方体网络通过将对应结点用一条边连接起来构成，以这种方 式来看待5 维超立方体网络时也很容易对各个结点进行编号。为清晰起见，图中 只画出了两个4 维超立方体之间对应结点之j 训的1 6 条边中的一条边。 在个”维超立方体结构中，每一个结点与另外 个结点直接连接。当用2 个”维系统构成一个m + 1 维系统时，系统中各结点的标弓增加一位。其方法是， 在其中一个n 雏超立方体的各结点地址前加上一位“0 ”，而在另一个n 维超立方 体各结点地址前加上一位“1 ”。也就是说，n 维超立方体网络可以看成由两个 1 维超立方体网络通过将对应用一条边连接起来构成。以这种方式来理解和看待n 维超立方体网络时很容易对各个结点进行编号。这样就得到下面的子立方体网络 的定义。 硕十学位论文 第一章绪论 0 0 7 7d 0 0 7 d 7 ，0 f 77 d 7 7 7 7 df f 7 7 f 图】35 维超立方体网络 定义1 2 维子立方体网络) n 维超立方体网络h ，的”位二进制串6 1 6 2 巩 中长度为n t 的二进制串6 1 6 2 “七对应于风中的一个具有2 。个结点和t 2 条 边的子图，称为”维超立方体网络风中的个尼维子立方体网络峨( 或简称为 尼一s u b c u b e ) 。 很明显，这里定义的膏维子立方体网络总中的结点的二进制串具有 自- 岛晚嘏，一，坼的形式，其中每一个乃要么为o 要么为l 。本文有时也将斤雏 予立方体鼠记作麒= 6 岛玩。料。很容易看出戌的每“_ 个由维子立方体与肛c u b e 是同构的。门维超立方体鼠也包含其它与肛c u b e 同构的子图。但是，本文只考 虑形式为6 如玩。 的“基本的”厅维子立方体。为简单起见，如不特别申明 本文将“基本的”膏维子立方体简称为斤维子立方体。 超立方体网络有隐含子结构的特性0 7 】。图1 ，4 表示的是一个4 维超立方体， 它中间隐含了3 维子超立方体。图l 一4 表明，一个4 维超立方体网络是由两个基 本的3 维子立方体构成的。当然，每一个基本的3 维子立方体还可以进一步划分 为两个基本的2 维子立方体( 图中每个3 维子立方体的一个面) ，每一个基本的 硕十学位论文 第一章绪论 2 维子立方体还可以进一步划分为两个基本的1 维子立方体( 图中每个2 维子立 方体的一条边及两个相关的结点构成) 。往上扩展，一个5 维超立方体网络还可 以看作由4 个基本的3 维子立方体构成等。实际上，每一个”维超立方体都可以 由完全相同的两个”1 维予立方体合成，方法是将两个一一1 维子立方体中具有相 同编号的结点连接起来，然后将其中个子立方体的编号均加上2 ”一。这称为超 立方体的递归构造过程f 0 7 08 1 。依照递归方法，可用子立方体构造任意多维的超立 方体。 0 j | d 图1 4 1 2 课题的研究意义 e 舍子结构的4 维超立方体网络 采用大量低廉的处理机构成高性能的计算机系统是近年来研究人员极感兴 趣的一个课题。高性能计算机发展的历史，从1 9 7 2 年世界上首台巨型机i l l i a c i v 问世算起，已经发展了近3 0 年。但巨型机这个高性能计算领域的曾经的杰出 代表现在已被并行计算机取代。而对并行计算机来说，无论是在并行计算机体系 结构方面还是在并行算法方面，其发展水平都还相对比较低。所以许多研究都致 力于提高计算机系统的并行性，分布式计算机系统已成为发展的必然趋势。 这种高性能的计算机系统采用的多处理机闻的数据传输必须借助网络来完 成，数据传输网络和多处理机一起组成并行计算机系统。并行计算机体系结构是 对通常意义上的计算机体系结构的扩展，即扩展了通信体系结构。通信体系结构 是并行计算机体系结构的核心，通信体系结构的核心则是并行计算机互联网络。 分布式计算机系统也是在通信的基础上，把多台计算机连接起来，实现系统内资 源共享并使进程在物理层上并发执行成为可能。并行计算机互联网络的研究，主 要包括并行计算机互联网络的拓扑结构、基本通信操作、容错路由算法、交换方 式和流控机制等。并行计算机互联网络的研究是当今的一个研究热点，随着它和 v l s i 以及硬件技术的迅速发展，多机系统中并行处理机的数目已越来越多，如 硕+ 学位论文 第一章绪论 果仍采用简单的互连结构，已不能满足用户的要求，于是人们提出了用超级的互 连拓扑结构来进行设计。 国内外现已对各种主要的并行计算机互联网络拓扑结构如r j n g ( 环型) ，t r e e ( 树型) ，s t a r ( 星型) ，m e s h ( 网孔型) ，t o r u s ( 环型) 和h y p e r c u b e ( 超立方 体型) 等进行了大量研究，并且对其中的一些拓扑结构已研制出了相应的商用和 研究用的并行计算机系统。在这些商用和实验性多处理机系统中，通常采用直接 互联网络连接系统中各个结点( 处理机) ，其中最典型的网络拓扑结构就是超立 方体。研究表明，超立方体网络拓扑结构由于其正规性、对称性、可靠性、强容 错性、直径短、可嵌入性和网络通信能力的可扩展性等优点，深受研究者和实践 者的欢迎，引起了人们对该结构在不同方面的研究兴趣叫、0 9 j 0 】。而且，一些商用 的多计算机体系结构如i n t e li p s c 2 叭1 “、n c u b e l o1 1 如、c m 2 、s g i c r a v o r i g i n2 0 0 0 副等都采用了超立方体网络拓扑结构作为处理机之间的互联网络结 构。所以，本课题集中对具有许多优良性能的超立方体网络进行研究。 同时，由于网络的规模迅速增长，网络上的供需矛盾同益凸现。用户提供给 网络的负载大于网络资源容量和处理能力，表现为经常在网络中出现拥塞现象。 这是由于网络资源和网络流量分布的不均衡所导致的。传统上认为，随着网络容 量的不断增加，拥塞便会降低。但近期的研究表明，网络容量的持续增加反而使 拥塞控制的稳定性问题越来越严重，当网络容量增大到一定极限时，现有的拥塞 控制系统将不稳定。因此，拥塞不会随着网络处理能力的提高而消除。同时，网 络的各个核心部分随着业务量的提高、访问量和数据流量的快速增长，其处理能 力和计算强度也相应增大使得单一设备根本无法承担。列这些问题，如果不佳 用某种机制加以协调和控制，必然会导致网络路由出现死锁等问题，网络上业务 的安全和有效性得不到保障。因此，拥塞和流量控制、负载均衡等机制及算法便 应运而生。 有效的拥塞控制方法是保证路由稳定运行的关键，也是提高网络服务o o s 的基础。同时，在超立方体网络中流量分布的不均衡也是可能存在的，也可以旱 成“资源”的相对短缺。因此，在超立方体网络路由中使用捎塞和流量控制及负 载均衡技术也具有非常重要的意义。而当前在针对诸如超立方体网络等高性能的 并行计算机互联网络上的拥塞、流量控制和负载均衡技术的研究还是很欠缺的。 因此，本课题无论从理论上还是从实践上都具有很好的研究意义。 1 3 国内外研究现状与分析 在并行计算机系统中，c p u 、存储器、i o 设备、网络接口等不同组成部分 雯堂焦笙皇 釜二兰丝 都要通过互联网络彼此连接起来。互联网络根据网络距离可大致分为并行计算机 互联网络、局域网络、广域网络等。对称多处理机( s m p ) 、大规模并行处理机 ( m p p ) 、分布共享存储多处理机( d s m ) 和工作站机群( c o w ) 等几种主要的 并行计算机，其核心都是并行计算机互联网络。随着并行训算机互联网络规模的 不断扩大，并行计算机互联网络的容错性及其研究变得越来越重要。 结点错误模型和链路( 也称为边) 错误模型是考虑并行科。算机系统中最常用 的两种错误模型0 2 1 。结点错误模型是指系统中出现错误的是结点，一个结点出现 错误会导致它的所有邻接点都不能通过它束传递消息。而在链路错误模型中，系 统中发生错误的是链路，一条链路出现错误仅导致该链路的两个端点不能通过这 链路通信。因此有的容错模型的设计只考虑结点的容错性，有的容错模型只考 虑边的容错性，有的容错模型则同时考虑结点和边的容错性。实际上，在结点容 错模型中，边的错误可用连接该边的两个结点中的任何一个出错进行模拟；在边 容错模型中，结点的错误可用与该结点相关的所有边出错进行模拟l 】纠。更进一步， 根据结点和或边错误的错误行为的不同，还可以区分最常研究的两种错误类型： 其一称为f a i l s t o p 类型( 也称为c r a s h 类型) ，即错误结点或错误边不能传输任何 信息；其二称为b y z a n t i n e 类型，即错误结点或边可能对传输经过该结点或边的 信息进行任意的改变，甚至于捏造错误的信息。容错模型在考虑对错误进行分类 时，另一个很重要的特征是错误持续时间的长短，根据此特征可将错误分为静态 ( 或永久性) 错误类型和动态( 或瞬态) 错误类型两类。在国内外的研究者已经 提出的超立方体网络容错模型中眦挑，1 2 7 l ，大部分的容错能力都还相当有限。因 为这一系列容错模型的研究事实上仍然假定n 维超立方体网络中错误结点的数 目是o ( n ) 。而文献 1 6 提出的两种容错模型：局部k 维子立方体连通性模型和局 部子立方体连通性模型陋2 8 、29 1 ，它们的容错性与超立方体网络的结点数成比例， 即可容许大量的错误结点而仍能确保正确结点的连通性。另外，基于这样的容错 模型而设计出的路由算法也是简单和高效，所以本文选择该容错模型做为研究的 出发点。 由于现在的网络规模越来越大，网络中结点和或边出错的可能性也越来越 大。因此，在研究超立方体网络路由算法时非常有必要研究路由算法的容错能力。 一些研究者现已对超立方体网络上的各种路由算法进行了大量的研究，主要包括 单播( u n i c a s t ) 、广播( b r o a d c a s t ) 、并行( p a r a l j e 】) 、多播( m u l t i c a s t ) 等路由 算法“”1 。下面这些算法都是考虑超立方体网络中出现结点和或边错误的情况下 的一些容错路由算法，它们都基于上述容错模型，因此容错能力都很小。 1 9 9 8 年童明生、刘长河和范天佑研究了一般化超立方体网络的容错路由算 法 3 0 】。但是他们只研究了结点错误数少于结点度的情况和结点错误数不少于结点 硕十学位论文 第一章绪论 度但少于m ( d l n l 十1 ) 的情况( d 为结点度) ，因而算法的容错能力很有限。1 9 9 8 年孙轶卿等给出的n 维超立方体网络的容错路径选择算法，具有自适应性，可以 防止死锁和活锁现象的发生，并可求出一条基于安全优先策略的可行最短路径 o ”】。2 0 0 0 年高峰和李忠诚基于“最优通路矩阵”容错模型实现了超立方体网络 中的容错路由算法f o ”。基于最优通路矩阵的路出算法所选的通路的长度不超过两 结点问的海明距离加2 。模拟结果表明该算法搜索最优通路的能力比安全向量强 得多。2 0 0 0 年高峰、李忠诚、闵应骅和吴杰基于扩展安全向量衅韵概念设计了 超立方体网络中的容错路由。2 0 0 0 年朱晓锋等基于路由选择能力的概念，建立 了一个具有较强容错性的路由算法，并可用在不连通的故障立方体或含有故障边 的立方体上【j “。2 0 0 2 年罔绍槐基于扩展安全向量和最优通路矩阵提出了扩展最 优通路矩阵l u 驯的概念并进一步改进了超立方体网络中的容错路由。2 0 0 2 年王国 军提出了基于局部k 维子立方体连通的n 维超立方体的单播路由算法和基于局部 子立方体连通的n 维超立方体的单播路由算法【1 6 2 8 1 2 ，这些算法是基于局部信息 的，因而具有很好的实际意义，也是本文研究的基础。阱l 列举的都是超立方体 网络上的单播容错路由算法，国外还有大量的有关超立方体网络上的广播、并行、 多播等容错路由算法，这里就不再列举了。 值得说明的是，不少国内的文献将容错路出算法称寻径算法1 3 0 3 ”，单播容错 路由算法也常被简称为容错路由算法。当然，早先也有一些不考虑网络容错情况 的路由算法，如1 9 9 6 年霍红卫和庄心谷提出的超立方体中所有点对之间的最短 路径算法【3 4 j 和0 1 背包问题的并行算法【3 5 】；1 9 9 5 年杨波、庄心谷的超立方体计 算机上求平面点集最近点对的算法曙“。1 9 9 9 年陈固龙等提出两种基于海明距离 的确定性寻径算法e 1 一c u b er o u t i n g 和e 2 一c u b er o u t i n g ，并综合这两种算法提出了 自适应寻径算法e 3 一c u b er o u t i n 2 刚；都是2 0 0 1 年陈玉坤在的面陈国龙等人的三 种算法的基础上提出的新的寻径算法【3 ”，该算法始终以最佳路出方式从当前结点 到达邻接点并最终到达目的结点：姚闻庆等根据f t h 结构开发的优化路径选择 和广播算法【3 圳；还有文献 0 5 ，0 6 等。这些不考虑错误结点的大都是单播算法，讨 论算法正确性时只考虑是否死锁，它们许多都是为了避免通道的死锁而设计的。 但是这些算法的存在为本文如何在具有错误结点的超立方体网络上进行流量控 制和负载均衡，避免拥塞和死锁等提供了参考。 另外，不少研究人员还对广义超立方体【4 0 4 ”、扭立方体和超级交叉立方体 蚌列刊的结构和容错路由算法进行了研究，它们是近年提出的超级立方体的变种。 因为这里研究一般意义上的超立方体网络结构，所以不再赘述。 第一章绪论 1 。4 课题的主要研究内容 本课题主要从两个方面进行了研究。第一个方面是超立方体网络及其容错路 由算法和负载均衡、流量控制和拥塞控制等技术的关系，第二个方面是基于负载 均衡的超立方体网络中的容错路由算法。 ( 1 ) 超立方体网络及其容错路由算法和负载均衡、流量控制和拥塞控制等 技术的关系的研究。随着互连网的飞速发展，负载均衡、流量控制和拥塞控制等 技术已经逐渐成为当前网络中的研究热点问题。为此，人们对负载均衡、流量控 制和拥塞控制在不同网络环境下的发生原因、实现机制和常用策略进行了大量的 研究。但是这些在负载均衡技术等方面进行的研究很少有针刺超立方体网络的。 所以，本文试图通过对拥塞控制、流量控制和负载均衡技术的系统研究和比较， 来努力发掘上述技术在超立方体网络及其容错路由算法研究方面的适用性和意 义。为负载均衡目标在超立方体网络容错路由上的实现打下了基础。 ( 2 ) 超立方体网络容错路由算法的研究。现已提出各种超立方体网络容错 模型，如：结点容错模型( 典型的是肛s a f e 模型) 、边容错模型、同时考虑结点 和边的容错模型、c l u s t e r 容错模型和能容许超立方体中存在大量错误结点的局 部连通性容错模型l 】q “o 。人们基于这些容错模型已经提出了大量的单播 ( u n i c a s t ) 、广播( b r o a d c a s t ) 、并行( pa 1 a l l e l ) 、多播( m u l t i c a s t ) 等容错路由 算法，其中尤以基于局部连通性容错模型的单播容错路由算法表现出色2 3 】。但 是这些算法很少运用负载均衡机制，从而在路由过程中不可避免的会出现死锁、 冲突、消息拥塞等现象。因此，本文最重要的研究内容是要在局部连通性容错模 型上的超立方体网络中实现负载均衡的功能，设计和提出基于负载均衡的具有大 量错误结点的超立方体网络中的容错路由算法。这些算法必须具有一定的合理性 和有用性。并且本文将通过模拟实验证明设计出的容错路由算法具有很好的理论 价值和实用价值。 1 5 论文的结构 论文共分五章。第一章是论文的绪论部分，第二章到第四章是论文的主体部 分，第五章是论文的结束语部分。 第一章为绪论。首先介绍什么是超立方体网络，然后介绍本课题的研究意义， 然后综述超立方体网络容错模型和容错路由算法的研究现状和水平，然后介绍本 课题的主要研究内容，最后是本文的组织结构。 硕杠学位论文第一章绪论 第二章研究和探讨超立方体网络及其容错路由算法和负载均衡、流量控制和 捌塞控制等技术的关系。与ip 路由类似，在具有大量错误结点的超立方体网络 上寻找路径时往往会遇到死锁、冲突、消息拥塞等现象。同时，要大限度发挥高 性能计算机的并行度，很重要的技术之一就是充分使用流量控制、捌塞控制和负 载平衡等技术。这一章首先围绕这几种技术的方方面丽展丌，详细阐述有关的概 念，应用和实现策略等，然后重点挖掘出他们与超立方体网络及其路由算法的必 然联系，说明负载均衡等技术在超立方体网络上应用的合理性和适用性。 第三章研究和设计基于负载均衡的超立方体网络容错路由算法。文献 1 6 ，2 8 ，2 9 中提出的基于局部连通性的容错模型的超立方体网络容错路由算法是 我们的研究基础，但是它同样缺乏网络寻径中的安全性和有效性方面的控制机 制。我们对这些路由算法进行了进一步的探讨和改造，引入了负载均衡机制，讨 论和设计了具有大量错误结点的超立方体网络中的单播容错路由算法。本章所设 计的算法既是简单的，又是高效的。他们不仅保持了原路由算法的基于局部信息 的优秀性质，同时又实现了负载均衡的目标，而且在路由的稳定性和有效性方面 更胜一筹，具有很好的实用价值。 第四章设计和实施基于负载均衡的超立方体网络容错路由算法的模拟实验， 并通过对实验结果的分析来证明本文提出的算法的性能。通过观察，我们发现， 改造后的具有负载均衡功能的路由算法的成功发现路由路径的概率相应的提高 了，达到了负载均衡的目的；同时也是基于局部信息和分布式的，便于检测和维 护。实验结果说明所设计的算法基本达到了预期的效果，具有一定的实用价值。 第五章是结束语。在结束语中对本文的研究工作进行了总结，并对迸一步的 研究工作进行了展望。 硕十学4 奇论文 第一章负载均衡技术剖析 第二章负载均衡技术剖析 随着网络规模迅速增长，网络资源的竞争闩益激列，给网络的稳定和安全性 带束很大的冲击和挑战。与1 p 路由类似，在具有大量锗误结点的超立方体网络 上寻找路径时往往会遇到死锁、冲突、消息拥塞等现象。同时，要大限度发挥高 性能计算机的并行度，进一步减小并发程序的执行时问，在使用高性能计算机时 往往要对所执行的任务做一定的调度，其中很重要的技术之就是充分利用结点 间的通信，使用流量控制、拥塞控制和负载平衡等技术。当前超立方体网络中的 容错路由算法，对网络寻径中的安全性和有效性的考虑还有所欠缺，而这是寻径 算法必须考虑的。正是基于这些思想，我们着手研究和探讨负载均衡及其相关技 术在超立方体网络及其容错路由算法中适用性，为超立方体网络中不具备负载均 衡功能的路由算法的改造做好准备。本章首先围绕拥塞控制、流量控制和负载均 衡技术的方方面面展开，然后挖掘出他们与超立方体网络路由中的必然联系。在 下一章中我们将详细的阐述基于流量负载均衡的超立方体网络容错路由算法的 思想并进行分析。 2 1 概述 网络中的路由问题是网络路由中的最为基本的问题。无论具体的结构如何， 网络中路由往往会遭遇资源冲突等问题，从而导致死锁和搠塞等现象的发生。单 单靠从硬件上扩大网络规模，增加网络容量是无法完全避免和解决这些问题的。 所以人们近来对依赖拥塞控制、流量控制和负载均衡等技术来规避这些问题的研 究显的格外的热门。相关研究表明，在超立方体网络容错路由中也可能发生死锁 和拥塞等问题。根据我们的研究，在当前对超立方体网络及其容错路由算法的研 究中，很少考虑和运用过负载均衡及其相关机制。m a h a m e d 和h 啪i d 在1 9 9 9 年 研究了存在热点( h o ts p o t ) 通信量的超立方体网络上的自适应虫洞f w o h i l h o l e ) 路由的问题【4 5 4 。热点的存在表示这个超立方体网络中通信流量的不均衡，他们 的研究主要是寻求解决因过分争用网络结点进行通信而出现的死锁等问题的方 法。尽管存在类似的研究，但他们研究的超立方体网络往往是没有考虑容错性的 4 4 ，4 54 6 ，4 9 1 一 为了在超立方体网络及其容错路由算法中实现负载均衡，本章首先对拥塞控 1 0 硕十学位论文 第一章负载均衡技术剖析 制、流量控制和负载均衡技术的基本概念、策略和常用的实现方法进行描述和总 结，然后努力地从中挖掘出与本文研究的超立方体网络容错路幽算法的关联，为 下一章在超立方体网络上设计和实现具有负载均德功能的容错路由算法打下了 理论基础。在本章中介绍的一些负载均衡及其相关的技术、策略都具有很好的通 用性，可以很好的移植到超立方体网络上。 2 2 拥塞控制技术 当前的计算机网络一般都具有网络资源共享的优点。但网络规模的不断增加 会加重网络上业务流的不可预测性和突发性，容易在瓶颈处引起资源冲突，从而 导致网络拥塞。拥塞发生时，网络资源处于饱和状态，信息传送时延变长，丢失 率上升，系统吞吐率急剧下降，严重的可能导致网络崩溃。随着网络互连和应用 特别是连续媒体应用的增长，网络拥塞问题会越来越引起人们的关注。 要解决拥塞问题必须在共享资源管理的基础上控制源端的数据发送率，合理 使用瓶颈处的资源，避免网络拥塞或将网络从拥塞状态恢复至正常工作状态。这 就是网络拥塞控制的基本思想。经过二十多年的研究与发展，人们提出了多种拥 塞控制方法，如“窗口式流控制”、“源控制”、“慢启动”、“二元反馈”、 “基于速率的控制”及“自适应拥塞控制”等阳，其中部分控制机制已经成功 地运用在网络中。而通过结合作者的大量调查和研究发现，当前对拥塞控制研究 大致集中在对i m e m e t ( 互联网) ，t c p i p ，路由器网关，a t m 网，控制理论反 馈方面的研究上。其中，又尤其是对i n t e m e t ，t c p i p ，a t m 网络的研究最为热 门。研究者近年来在这些问题上提出了许多方法，取得的研究成果也颇多。流量 控制和拥塞控制有着尤其紧密的关系，所以大致的研究情况也差不多，将在下一 节中详细阐述。 尽管拥塞控制已有了相当的发展。由于网络规模扩大速度很快，网络拥塞仍 然是个十分严峻的问题。特殊的网络应用，包括超立方网络中的路由，也需要 不同寻常的拥塞控制技术支持。因而拥塞控制技术研究对于将来的网络设计、协 议设计及网络应用均有着十分重要的意义。 2 2 1基本概念 在计算机网络中，如果某时刻网络负载超过了可用资源或者网络出现故 障，那么拥塞就会发生【4 8 。此时会有数据包丢失，传输延迟增大，网络吞吐量 下降等现象。直观上，解决网络拥塞应当从两方面入手：一是尽量避免拥塞发生； 硕十学 ：f 7 _ 论文 第一章负载均衡技术剖析 一是在拥塞发生时采取措施消除搠塞。前者是为了预防，力图使网络维持在最佳 状态，不发生网络拥塞，称为避免拥塞( c o n g e s t i o l la v o i d a n c e ) 。后者是为了 补救，当拥塞发生后，使得网络复原至正常的工作状态，称为捌塞恢复( c o n g e s t i o n r e c o v e r y ) 。没有捐 塞恢复机制，当搠塞发生时网络有可能崩溃。要真正避免网 络捌塞是可能的，但这样做必然会牺牲网络的资源利用率。在追求公平、高速、 高利用率的环境下，采用这种保守的方法显然是不适宜的。因此，简化拥塞避免 算法着重拥塞出现时的。陕复处理更为合理。即便使用了洲塞避免策略，仍然需要 拥塞恢复技术来保持吞吐率，因为网络每个源结点发送数据的起始时间、数据率 及大小具有不可预测性和突发性，有可能会引起网络拥塞。可见，拥塞控制应包 括拥塞避免和搠塞恢复两者。 2 _ 2 ，2 拥塞控制机制 从整体上看，拥塞控制可分为两类，一类是“基于网络系统的拥塞控制”， 另一类是“基于应用的j j = j 塞控制”。早期的拥塞控制算法大多是基于系统的。 ( i ) 基于网络系统的拥塞控制 这类拥塞控制是网络系统居主动地位的控制方式。在这种方式下，网络动态 地管理其资源，如带宽、缓冲区、队列长度、时钟等，根据资源的占用情况标识 拥塞并将拥塞信息反馈至源端，驱动派端调节输入业务流。控制系统的模型如图 2 1 所示。其中，时间片t 内第i 个用户的负荷为xi ( t ) ，瓶颈处的总负荷就为 x i ( t ) ，系统的状态可用n 维向量来表示：x i ( t ) = 。1 ( t ) ，。2 ( t ) ，x 。( t ) ，其 中xi ( t ) 表示第i 个用户的需求及系统资源的分配。在此时间间隔内系统根据负荷 级发送反馈信息y ( t ) 。整个控制过程涉及到四个控制因素：包调度、缓存管理、 信息反馈及端调节。 图2 1n 用户共享网络的控制系统模型 第章负载均衡技术剖析 其中，反馈机制是指网络提供给源端状态信息，用以调节源的业务输入流。 反馈既可以是前向的也可以是后向的。在前向反馈中， | j 塞标志在跳结点上被标 记后发往目的结点，由目的结点再返回源结点；而后向反馈中的拥塞标志信息则 直接由中间跳结点按流的逆向返回至源结点。“二元反馈方法”使用的即是前向 反馈。在该算法中，每个数据包的包头中均含有一一位拥塞指示位( 为1 时表示拥 塞，为0 时表示非拥塞) ，当某个路由器的平均队列长度大于或等于1 时，路出 器在网络层将该位置1 ，继续向前传送。数据包到达目的站后、捌塞指示位被复 制到传输层的反馈包包头中，然后发回源站。源站根掘拥塞指示位的统计数字来 决定发送窗口的大小，当5 0 的位被设置时，发送窗口减少为当的窗口的8 75 ， 否则窗口增1 。也就是说，算法采用的是“加性增乘性减”策略。在“二元反馈 方法”的基础上进一步发展的算法有“可选择二元反馈算法”、“0 位方法”等， 前者将统计平均排队时间间隔内每个用户的数据包并保存下来，只拥塞那些过量 发送数据的源标识，要求其减少负荷；后者的每个数掘包中除了拥塞位外，增加 了排队位，以标识交换结点中数据包排队的情况。当一个包被迫在队列中等待时， q 位置位。源结点根据拥塞和排队信息来调节输入的流率。 除了使用队列长度和排队时问作为搁塞度量对象外，还可以使用其它对象如 资源利用串、丢包串、绥存占用量、业务流量( 输入和输出流量) 等。在“b b n ” 算法i 47 j 中，每个交换结点计算出其资源利用率，加到路由器的更新包内以扩散 方式传播至整个网络。各个源端点据此调节自己的流率，在“丢失负荷曲线算法” 中，每个交换结点监视局部的业务负荷，提供一个丢失负荷曲线，反馈至源端。 源端根据此曲线导出大致的吞吐率曲线，然后对吞吐率和丢包率进行权衡折衷， 决定自己的传送率。著名的“t c p 慢启动”算法以源结点到目的结点的r t t 作 为测试对象进行拥塞决策，反馈至源结点的捌塞信息决定发送窗口的增减( 线性 增乘性减) 。 ( 2 ) 基于应用的拥塞控制 基于应用的拥塞控制是针对待殊应用的，和具体的应用程序结合起来并包含 于应用程序中。这类控制机制一般不关心网络的具体结构，而是将整个网络看成 一个黑匣子，由端结点通过对网络状态参数的测试来获取拥塞信息，再根据拥塞 信息按某种策略控制端结点曲输入流。最常用的测试参量一般是r t t 和丢包率。 基于应用的拥塞控制模型可表示成图2 2 形式。其中，s 表示源结点集；d 表示 目的结点集； ( t ) = f 】( t ) ，x2 ( t ) ， 。( t ) ，表示不同源的业务率；，( t + t ) 表示 d 所发送的反馈信息矢量，t 表示来回时延：实箭头表示正常业务流的传输路径 和方向；虚箭头表示反馈信息的传输路径和方向。 硕扣学佗论文第一章负载均衡技术剖析 圈2 2 基于应用的拥塞控制模型 因为这种凡是不关心网络的具体结构，所以也适合于包括超立方体网络在内 的网络。和具体应用结合起来的拥塞控制算法定程度上继承了“基于网络系统 的拥塞控制算法”的思想。 单播实时通信中的搠塞控制：对单播实时通信中的拥塞控制的研究一般集中 在视频通信中。视频通信中拥塞的判别基于目的端返回至源端的关于视频质量的 反馈信息，包括所接收的最大包长、丢包数、估计的包抖动间隔、邮戳等。可以 简单地只使用丢包率来判定网络状，如当丢包率大于所没定的阈值时拥塞标志置 位，低于某个闽值时欠负荷标志置位；也可以使用综合信息来识别网络是否拥塞。 组播实时通信中的拥塞控制：组播l m u l t i c a s t ) 方式下，网络的异构性决定 了其拥塞控制不同于单播方式。一个接收者通过反馈向源报告了丢包信息，源如 果简单地限制业务流就会影响整个组内的那些未拥塞结点的业务质量。当拥塞发 生在源端或靠近源端时，组内所有接收者检测到拥塞并向源反馈拥塞报告包，这 样有可控在源或瓶颈结点处发生“信息内爆”【4 ；】。因此，组播下的拥塞控制必 须很好地解决这些问题。 一种方法是将网络状态分成“欠负荷”、“满负荷”和“拥塞”三类，由接 收者根据丢包率来决定其属于哪一类并将状态信息反馈到源端，源端对来自不同 接收者的状态信息进行统计，根据统计值调节发送的码率。另一种方法是应用分 层。即将应用分成多个层次，不同的层对应不同的业务质量。拥塞支路上的接收 者对应于拥塞组，只接收基本层数据。当拥塞恢复后加入到非拥塞组，除接收基 本层数据外还接收增强层数据，以提高业务质量。 基于以上应用和方法现在都已经有了一些比较成熟的算法。但是目前在针对 超立方体网络及其容错路幽算法的拥塞控制技术的研究上，基本还是一片空白。 所以在这方面结合拥塞控制等思想在超立方体网络上继续对路出方法进行研究 也是很有实际价值和意义的。 2 2 3 拥塞控制算法的概况 拥塞控制的算法设计有一定难度，其设计困难体现在以下几方面： 硕十! 学位论文 第章负载均衡技术剖析 ( 1 ) 算法的分布性。搠塞控制算法的实现分布在多个网络结点中，必须使 用不完整的信息完成控制，并使各结点协调工作、还必须考虑某些结点工作不j 下 常( 即可能出错) 的情况。 ( 2 ) 网络环境的复杂性。i n t e r n e t 中各处的网络性能有很大的差异，算法必 须具有很好的适应性。 ( 3 ) 算法的性能要求。拥塞控制算法对性能有很高的要求，包括算法的公 平性、效率、稳定性和收敛性等。某些性能目标之削存在矛盾，在算法设计时需 要进行权衡。 ( 4 ) 算法的开销。拥塞控制算法