（通信与信息系统专业论文）宽带通信网中valiant负载平衡技术研究.pdf

中文摘要 中文摘要 v a l i a n t 负载平衡技术来源于多处理器领域，其实质为每个结点将分布式系统 赋予的任务均匀分配给其他所有结点处理，使锝整个系统的负载趋于平衡，从而 提高了整个系统的效率。近年来，随着i n t e r a c t 数据业务量的爆炸式增长以及服 务质量( q o s ，q u a l i t y o f s e r v i c e ) 要求的不断提高，十分有必要对宽带通信网的整体 架构、选路算法以及核心节点的实现方式等方面进行改进创新，以满足网络业务 的高速增长和动态变化。相应地v a l i a n t 负载平衡技术应用于宽带通信网中，为宽 带通信网的相关研究产生了新的思想和新的方法。本文研究了v a l i a n t 负载平衡技 术在宽带通信网中的应用问题，主要围绕以下两个方面展开：( 1 ) v a l i a n t 负载平衡 的两级交换机；( 2 ) w d m 光网络中v a l i a n t 负载平衡的鲁棒选路算法。 v a l i a n t 负载平衡交换机分为两级交换结构，第一级交换结构连接输入和中间 输入，起分散负载的作用，第二级交换结构连接中间输入和输出，将负载最终送 到输出端口。v a l i a n t 负载平衡交换机具有良好的扩展性；同时可以提供1 0 0 吞 吐量保证。但是，v a l i a n t 负载平衡交换机的基本结构会出现分组乱序的情况，这 将导致网络交换性能的下降。在第二章中，作者提出了一种在两级v a l i a n t 负载平 衡交换机中保证分组顺序到达的b p s ( b l a n kp a c k e ts t u f 0 算法。b p s 算法通过向输 入队列中填充分组从而形成满帧，使得分组顺序通过交换机。b p s 算法具有良好 的交换特性均时延及吞吐量) ，同时也是一种分布式算法，各个端1 2 1 可以独立 地进行操作。 在w d m 网状网中，静态动态条件下传统的选路和波长分配( r v 峨) 算法适用 于光路业务量，速率矩阵确知的情况，然而在实际应用中往往难于估计。第三章研 究了w d m 网状网在单粒度光路连接请求( 即连接请求的带宽等于一个波长的带 宽) 的h o s e 不确定业务模型下v a l i a n t 负载平衡的鲁棒选路问题。本章的研究共分 以下三个方面。( 1 ) 针对静态h o s e 不确定业务模型下全网总代价最小的优化设计 问题，作者在整数线性规划( i l p , i n t e g e rl i n e a rp r o g r a m m i n g ) 的基础上，提出了 m r u f ( m a x i m i z i n gr e s o u r c eu t f l i z a i t o nf i r s t ) 的启发式算法。m r u f 算法从最大化 资源利用率的角度出发计算负载分配向量，从而有效地在w d m 网状网中建立了 全连接的虚拓扑，使得该虚拓扑能为静态h o s e 不确定业务模型下所有的业务量 矩阵都能提供1 0 0 的网络吞吐量。( 2 ) 针对v a l i a n t 负载平衡的鲁棒选路算法下的 中文摘要 w d m 网状网的抗毁设计问题，作者基于专用通道保护( d e d i c a t e dp a t hp r o t e c t i o n ) 的方式，提出了t m r u f ( t w o s t e pm r u f ) 的启发式算法。计算机仿真表明t m r u f 算法在提供鲁棒性保护的同时具有较小的全网总代价。( 3 ) 针对逻辑全连接的光交 换网络在动态h o s e 不确定模型下的鲁棒选路问题，基于v a l i a n t 负载平衡机制， 作者提出了l b a d f ( l o a db a l a n c i n gw i t ha d j u s t a b l ed i s t r i b u t i o nf r a c t i o n ) 算法。 l b a d f 算法根据网络中当前各条链路上空闲光路的数目对v a l i a n t 负载平衡机制 中的分配系数进行即时动态地调整，从而达到了优化网络性能的目的。 在w d m 网状网中，传统的业务量疏导( t r a f f i cg r o o m i n g ) 算法适用于不同粒 度连接请求的业务量矩阵确知的情况，然而在实际应用中往往很难估计业务量矩 阵。第四章研究了w d m 网状网在多粒度带宽连接请求( 即连接请求的带宽不尽相 同，都小于一个波长的带宽1 的h o s e 不确定业务模型下v a l i a n t 负载平衡的鲁棒选 路问题。本章的研究共分以下两个方面。( 1 ) 针对多粒度连接请求条件下的全网总 代价最小的优化设计问题，考虑到网络中存在多种不同粒度的连接请求并且连接 请求不可再分的情况，作者提出了h o s e 模型分解( h o s em o d e ls e p a r a t i o n ) 的方法， 将h o s e 不确定业务模型分为不同粒度的h o s e 子模型，并且分别为它们计算负载 分配向量。作者提出了i m r u f i i m p r o v e dm r u 功的启发式算法，并通过计算机仿 真验证了算法的有效性。针对o c - 1 连接请求条件下的h o s e 模型吞吐量最大的 优化设计问题，作者提出了s b r & m r u f ( s h o r t e s tb a l a n c e dr o u t i n g m r u f ) 的启 发式算法。s b r & m r u f 算法对于短距离路径的节点对采用最短路径的方法，对 于长距离路径的节点对采用平衡选路的方法，因此s b r & m r u f 算法具有较优的 网络性能。 第五章研究了基于口的光网络在h o s e 不确定模型下的网络规划问题，其目 标为在保证h o s e 不确定模型鲁棒选路的前提下建立最小代价网络。作者考察了 几种适用于h o s e 不确定模型鲁棒选路的基本网络结构，包括传统的以电路交换 为基础的单跳选路的网络结构，以点到点电路连接为基础的多跳选路的网络结构， 和最新的v a l i a n t 负载平衡的两跳选路的网络结构；并针对v a l i a n t 负载平衡的两 跳选路的网络结构提出了新的n s r l b ( n o n u n i f o r ms e l e c t i v er a n d o m i z e dl o a d b a l a n c i n g ) 算法。n s r l b 算法拥有较好的时延和时延抖动特性，同时与单跳结构 的v p n 树，多跳结构的v p n 树以及两跳结构的随机负载平衡算法和选择性随机 负载平衡算法相比，具有较小的网络代价。 为验证、评估本文所提各种算法的性能，作者自行开发了相关软件仿真平台 n 中文摘要 软件，并利用这仿真平台考察了各种算法的性能。第六章介绍了在研究v a l i a n t 负载平衡技术在宽带通信网的应用问题时开发的仿真软件平台，给出了重要数据 结构以及伪码。最后是全文总结。 关键词v a l i a n t 负载平衡，交换机，w d m 光网络，保护，整数线性规划 i 玎 a b s t r a c t a b s t r a c t t h ea p p r o a c ho fv a l i a n tl o a d b a l a n c i n gi sf i r s tp r o p o s e di n m u l t i p r o c e s s o r i n t e r c o n n e c t i o nn e t w o r k s i nt h e a p p r o a c ho fv a l i a n tl o a d b a l a n c i n g , e a c hn o d e s p r e a d st h et a s ka s s i g n e db yt h ed i s t r i b u t e ds y s t e mt oa l lt h en o d e s t h et r a f f i cl o a df o r t h es y s t e mi sb a l a n c e da n dt h ee f f i c i e n c yi sg r e a t l yi m p r o v e d i nr e c e n ty e a r s , w i t ht h e e x p l o s i v ei n c r e a s eo fi n t e r a c tt r a f f i ca n dt h ee n h a n c e m e n to fq u s ( q u a l i t yo fs e r v i c e ) d e m a n d s ，f o rb r o a d b a n dc o m m u n i c a t i o nn e t w o r k si ti sn e c e s s a r yt oi m p r o v ea n d i n n o v a t et h ef r a m e w o r k , t h er o u t i n ga l g o r i t h m sa n dt h er e a l i z a t i o no fc o r es w i t c hn o d e ， e t c c o r r e s p o n d i n g l y , t h ea p p r o a c ho fv a l i a n tl o a d b a l a n c i n gi sa p p l i e di nb r o a d b a n d c o m m u n i c a t i o nn e t w o r k s ，t h e nn e wi d e aa n dn e wm e t h o di s p r o d u c e d t h i s d i s s e r t a t i o ni n v e t i g a t e dt h ep r o b l e mo ft h ea p p l i c a t i o no fv a l i a n tl o a d b a l a n c i n gi n b r o a d b a n dc o m m u n i c a t i o n n e t w o r k s ，i n c l u d i n gt w op e r s p e c t i v e s ：o ) t h ev a l i a n t l o a d b a l a n c e d t w o s t a g es w i t c h ；( 2 ) t h e v a l i a n tl o a d - b a l a n c e dr o b u s t r o u t i n g a l g o r i t h mi nw d m ( w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ) o p t i c a ln e t w o r k s t h ev a l i a n tl o a d b a l a n c e ds w i t c hc o n s i s t so ft w os t a g e s t h ef i r s ts t a g ec o n n e c t s t h ei n p u t sa n dt h ei n t e r m e d i a t ei n p u t s ，s p r e a d st h et r a f f i cu n i f o r m l ya m o n gt h e i n t e r m e d i a t ei n p u t s t h es e c o n ds t a g ec o n n e c t st h ei n t e r m e d i a t ei n p u t sa n dt h eo u t p u t s ， f i n a l l yt r a n s m i t st h et r a f f i ct ot h eo u t p u t s t h ev a l i a n tl o a d b a l a n c e ds w i t c hi ss i m p l e t ob es e a l a b l ea n dh a sb e e np r o v e dt op r o v i d e1 0 0 t h r o u g h p u t h o w e v e r , i ni t sb a s i c f a b r i c , t h ev a l i a n tl o a d - b a l a n c e ds w i t c hr e i s - s e q u e n c e st h ep a c k e t a i nc h a p t e r2 t h e a u t h o rp r o p o s e sa l la l g o r i t h mc a l l e db p s ( b l a n kp a c k e ts t u f f ) , w h i c hm a i n t a i n sp a c k e t o r d e rb ys t u f f i n gt h eb l a n kp a c k e t st ot h ef u l lf r a m ei nt h et w o - s t a g ev a l i a n t l o a d - b a l a n c e ds w i t c ha n dh a se x c e l l e n ts w i t c h i n gp e r f o r m a n c e ( i nt e r m so fm e a n d e l a ya n dt h r o u g h p u t ) t h i sa l g o r i t h mi s d i s t r i b u t e da n de a c hp o r tc a l lo p e r a t e i n d e p e n d e n t l y i nw d mm e s hn e t w o r k s ，t r a d i t i o n a l s t a t i c d y n a m i cr o u t i n ga n dw a v e l e n g t h a s s i g n m e n t ( r w a ) a l g o r i t h m sa l eb a s e do na ne x p l i c i tk n o w l e d g eo ft h et r a f f i c d e m a n d t r a f f i cr a t em a t r i x ，b u ti np r a c t i c ei ti sd i f f i c u l tt op r e d i c tt r a f f i cp a t t e r no fe a c h s o u r c e d e s t i n a t i o np a i ra c c u r a t e l y i nc h a p t e r3 ，t h ea u t h o ri n v e s t i g a t e st h ep r o b l e mo f a b s t r a c t v a l i a n tl o a d - b a l a n c e dr o b u s t r o u t i n ga l g o r i t h mu n d e rt h em o d e lo fp o l y h e d r a l u n c e r t a i n t y ( i e ，h o s em o d e l ) o ft h es i n g l e - g r a n u l a r i t yl i g h t p a t hc o n n e c t i o nr e q u e s t s ( j c ，t h eb a n d w i d t ho ft h ec o n n e c t i o nr e q u e s t si se q u a lt ot h a to fo n ew a v e l e n g t h lf o r w d mm e s hn e t w o r k s t h er e s e a r c hi n c l u d e st h r e ep e r s p e c t i v e s ( 1 ) f o rt h es t a t i ch o s e u n c e r t a i n t ym o d e lo fw d m m e s hn e t w o r k s ，c o n s i d e r i n gt h eo p t i m i z a t i o np r o b l e mo f m i n i z i n gt o t a ln e t w o r kc o s t ，t h ea u t h o rp r e s e n t st h em a t h e m a t i cf o r m u l a t i o n ( i l p , i n t e g e rl i n e a rp r o g r a m m i n g ) ，a n dp r o p o s e sm r u f ( m a x i m i z i n gr e s o u r c eu t i l i z a i t o n f i r s t ) h e u r i s t i ca l g o r i t h m ，m r u fa l g o r i t h mc a l c u l a t e st h et r a f f i cd i s t r i b u t i o nf r a c t i o n b a s e do nt h em a x i m i z a t i o no ft h er e s o u r c eu t i l i z a t i o n ，a n dc o n s t u r c t st h ef u l l - m e s h v i r t u a lt o p o l o g yo nt h ep h y s i c a ln e t w o r k a l lt r a f f i cm a t r i c e su n d e rt h es t a t i ch o s e u n c e r t a i n t ym o d e lc a nb ee f f i c i e n t l yr o u t e do nt h ev i r t u a lt o p o l o g y ( 2 ) c o n s i d e r i n gt h e p r o b l e mo fv a l i a n tl o a d b a l a n c e dr o b u s tr o u t i n gi nr e s i l i e n tw d m m e s hn e t w o r k s ， t h es t r a t e g yo fd e d i c a t e d - p a t hp r o t e c t i o ni su s e d t h ea u t h o rp r o p o s e st m r u f f f w o s t e pm r u f lh e u r i s t i ca l g o r i t h m s i m u l a t i o nr e s u l t ss h o w st m r u fa l g o r i t h m h a st h el o w e rt o t a ln e t w o r kc o s tw i t ht h er o b u s tp r o t e c t i o n ( 3 ) t h ea u t h o rc o n s i d e r st h e p r o b l e mo fr o b u s tr o u t i n gu n d e rt h ed y n a m i ch o s eu n c e r t a i n t ym o d e lf o rt h ef u l l - m e s h l o g i co p t i c a ln e t w o r ka r c h i t e c t u r e t h ea u t h o rp r o p o s e san o v e ld y n a m i cr o u t i n g a l g o r i t h m l b a d f ( l o a db a l a n c i n gw i t ha d j u s t a b l ed i s t r i b u t i o nf r a c t i o n ) b a s e do n v a l i a n tl o a d - b a l a n c i n g l b a d fa l g o r i t h mc a l li n s t a n t l ya d j u s td i s t r i b u t i o nf x a c t i o n a c c o r d i n gt ot h en u m b e ro ft h es p a r ew a v e l e n g t h so nt h el i n k st oo p t i m i z et h e p e r f o r m a n c eo ft h en e t w o r k l b a d fa l g o r i t h mh a st h el o w e rb l o c k i n gp r o b a b i l i t yf o r t h ew h o l en e t w o r kt h a nt h a to fv l b ( v a l i a n tl o a db a l a n c i n g ) a l g o r i t h m , w h i c hh a st h e f i x e dd i s t r i b u t i o nf r a c t i o n a n dt h em a x i m u mb l o c k i n gp r o b a b i l i t yf o ra l lt h en o d e p a i r si nt h en e t w o r kc a na l s ob er e d u c e dc o r r e s p o n d i n g l yi nl b a d fa l g o r i t h m i nw d mm e s hn e t w o r k s t r a d i t i o n a lt r a f f i cg r o o m i n ga l g o r i t h m sa b a s e do na l l e x p l i c i tk n o w l e d g eo ft h et r a f f i cd e m a n dm a t r i x ，b u ti np r a c t i c ei ti sd i f f i c u l tt op r e d i c t m u l t i g r a n u l a r i t yt r a f f i cp a t t e r n so fe a c hs o u r c e d e s t i n a t i o np a i ra c c u r a t e l y i nc h a p t 盯 4 it h ea u t h o ri n v e s t i g a t e st h ep r o b l e mo fv a l i a n tl o a d b a l a n c e dr o b u s tr o u t i n g a l g o r i t h mu n d e rt h em o d e lo fp o l y h e d r a lu n c e r t a i n t y ( j c ，h o s em o d e l ) o ft h e m u l t i g r a n u l a r i t yc o n n e c t i o nr e q u e s t s ( i e ，t h eb a n d w i d t ho ft h ec o n n e c t i o nr e q u e s t si s n o ti d e n t i c a l a n di sl e s st h a nt h a to fo n ew a v e l e n g t h ) f o rw d mm e s hn e t w o r k s t h e r e s e a r c hi n c l u d e st w op e r s p e c t i v e s ( 1 ) f o rt h es t a t i ch o s eu n c e r t a i n t ym o d e lo fw d m v a b s t r a c t m e s hn e t w o r k s ，t h eo b j e c t i v ei st om i n i m i z et o t a ln e t w o r kc o s t c o n s i d e r i n gt h e r e e x i s t sm u l t i - g r a n u l a r t yc o n n e c t i o nr e q u e s t si nt h en e t w o r ka n dt h ec o n n e c t i o nr e q u e s t i sn o td i v i d e di n t os e r e v a ll o w - s p e e dc o n n e c t i o nr e q u e s t s ，t h ea u t h o rp r o p o s e sh o s e m o d e ls e p a r t i o nm e t h o dt os e p a r a t et h eh o s eu n c e r t a i n t ym o d e li n t os e v e r a ls u b - h o s e m o d e l sa c c o r d i n gt ot h eg r a n u l a r i t i e so ft h ec o n n e c t i o nr e q u e s t s ，a n dc a l c u l a t et h e t r a f f i cd i s t r i b u t i o nf r a c t i o n sf o rt h es u h - h o s em o d e l so fd i f f e r e n t g r a n u l a t i e s , r e s p e c t i v e l y t h ei m r u f ( i m p r o v e dm r u nh e u r i s t i ca l g o r i t h mi sp r o p o s e da n d e v a l u a t e d 。( 2 ) c o n s i d e r i n gt h eo p t i m i z a t i o np r o b l e mo fm a x i m i z i n gh o s em o d e l t h r o u g h p u t ，t h ea u t h o rp r o p o s e ss b r & m r u f ( s h o r t e s tb a l a n c e dr o u t i n g & m r u f ) h e u r i s t i c a l g o r i t h m s b r & m r u fa l g o r i t h m s e l e c t st h es h o r t e s t p a t h f o rt h e s h o r t - d i s t a n c en o d ep a i r s ，a n ds e l e c t st h eb a l a n c e dr o u t i n gp a t hf o rt h el o n g - d i s t a n c e n o d ep a i r s t h e r e f o r es b r & m r u f a l g o r i t h mh a sg o o dn e t w o r kp e r f o r m a n c e i nc h a p t e r5 ，t h ea u t h o rc o n s i d e r st h ep r o b l e mo fb u i l d i n gc o s t e f f e c t i v em e s h n e t w o r k sw h i c hr o b u s tt ot h eh o s eu n c e r t a i n t ym o d e l t h eo b j e c t i v ei st os e e kt h e m i n i m u mc o s tn e t w o r k st h a tc a nc a r yt h ec l a s so fh o s ed e m a n dm a t r i c e s t h ea u t h o r c o m p a r e ss e v e r a la r c h i t e c t u r e st h a ts u p p o r tt h eo b l i v i o u sr o u t i n gf o rt h eh o s e u n c e r t a i n t ym o d e li n c l u d i n gt r a d i t i o n a ls i n # e - h o pa r c h i t e c t u r eb a s e do nac i r c u i t s w i t c h e dc o r ei n f r a s t r u c t u r e , m u l t i - h o p ( p a c k e t - s w i t c h e d ) a r c h i t e c t u r eb a s e do n p o i n t - t o - p o i n tc i r c u i t s i nt h ec o r e a n dn e wv a l i a n t sl o a db a l a n c e dt w o - h o p a r c h i t e c t u r e ；a n dp r o p o s e st h en s r l b 州o n u n i f o r ms e l e c t i v er a n d o m i z e di o a d b a l a n c i n g ) o b l i v i o u sr o u t i n ga l g o r i t h mf o r t h ev a l i a n t sl o a db a l a n c e dt w o - h o p a r c h i t e c t u r e t h en s r l b a l g o r i t h mh a st h ea d v a n t a g ei nt e r m so fd e l a ya n dj i t t e r , a n d a c h i e v e st h ec o s tr e d u c t i o no v e ra l la r c h i t e c t u r e s , i n c l u d i n gs i n g l e h o pv p nt r e e m u l t i - h o pv p n t r e e a n dt w o - h o pr a n d o m i z e dl o a db a l a n c i n ga n ds e l e c t i v er a n d o m i z e d l o a db a l a n c i n g t ov e r i f ya n de v a l u a t et h ep r o p o s e da l g o r i t h m si nt h i sd i s s e r t a t i o n ，s i m u l a t i o n p l a t f o r ms o f t w a r eu s i n gd i s c r e t ee v e n ts i m u l a t i n gm e t h o d si sd e v e l o p e d a n db a s eo n p l a t f o r m t h ep e r f o r m a n c e so fa l lp r o p o s e da l g o r i t h m sa r ee v a l u a t e d i m p o r t a n td a t a s t r u c t u r e sa n ds o m ep s e u d oc o d e sa r eg i v e ni nc h a p t e r6 c o n c l u s i o n sf o l l o wa tt h ee n d o ft h i sd i s s e r t a t i o n a b s t r a e t k e yw o r d s v a l i a n tl o a d - b a l a n c i n g ，s w i t c h ，w d mo p t i c a ln e t w o r k s ，p r o t e c t i o n ， i n t e g e rl i n e a rp r o g r a m m i n g v n 简略字表 a s o n a s 榭 a w g r g s r g m p l s i l p l s p m p l s n n i n u i n p c o a d m 洲 o v p n 0 x c q o s r w a s d h s f t s r 简略字表 a u t o m a t i cs w i t c h e do p t i c a ln e t w o r k a u t o m a t i cs w i t c h e dt r a n s p o r tn e t w o r k s a r r a y e dw a v e g u i d eg r a t i n gr o u t e r g i g a b i ts w i t c ha n dr o u t e r g e n e r a l i z e dm p l s i n t e g e rl i n e a rp r o g r a m m i n g l l b e ls w i t c h e dp a t h m u l t i p r o t o c o ll a b e ls w i t c h i n g n e t w o r k - t o - n e t w o r ki n t e f f a c e n e t w o r k u s e ri n t e r f a c e n o n d e t e r m i n s t i ep o l y n o m i a l o p t i c a la d d d r o pm u l t i p l e x e s o p t i c a lt r a n s p o r tn e t w o r k o p t i c a lv i r t u a lp r i v a t en e t w o r k o p t i c a lc r o s sc o n n e c t o u a l t i yo fs e r v i c e r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t s y n c h r o n o u sd i g i t a lh i e r a r c h y s w i t c hf a b r i c t e r a b i ts w i t c ha n dr o u t e r 自动交换光网络 自动交换传送网 阵列波导光栅交换机 g 比特级交换机路由器 通用多协议标记交换 整数线性规划 标记交换路径 多协议标记交换 网络网络接口 网络用户接口 完全多项式复杂程度的非 确定性 光分插复用器 光传送网络 光虚拟专用网络 光交叉连接器 服务质量 选路与波长分配 同步数字系列 交换结构 t 比特级交换机路由器 简略字表 t d m t i m ed i v i s i o nm u l t i p l e x i n g 时分复用 u n i v c v p n u s e r - t o n e t w o r ki n t e r f a c e用户网络接口 v i r t u a lc h a n n e i虚通道 v i r t u a lp r i v a t en e t w o r k s 虚拟专用网络 v o q v m u a lo u t p u tq u e u e虚拟输出通道 w d m w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g波分复用技术 w i x c w a v e l e n g t hi n t e r c h a n g i n gc r o s s c o n n e c t 波长转换交叉连接器 w s x c w a v e l e n g t hs e l e c t i v ec r o s s c o n n e c t 波长选择交叉连接器 算法缩略字表 b p sb l a n kp a c k e ts t n f f 空白分组填充 m p c f m i n i m i z i n gp a t hc o s tf i r s t 最小路径代价优先 m r u f m a x i m i z i n gr e s o u r c eu t i l i z a t i o nf i r s t 最大资源利用率优先 o m r u fo w o - s t e pm r u f t m r u f t w o - s t e pm r u f l b a d f d i s t l o a d 枷l j o 】1 b a 譬：患n 一阶段m r u f 两阶段m r u f w i n l a d j “8 t a b l 。分配系数可调的负载平衡 h m sh o s em o d e ls e p a r a t i o n 软管模型分解 i m r u f i m p r o v e dm r u f s p r b r s b r n s r l b 改进的m r u f s h o r t e s tp a t hr o u t i n g 最短路径选路 b a l a n c e dr o u t i n g平衡选路 s h o r t e s tb a l a n c e dr o u t i n g 最短平衡选路 n o n - u n i f o r ms e l e c t i v er a n d o m i z e dl o a d 非均匀选择性随机负载平 b a l a n c i n g衡 x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 日期：争旷叼年7 月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名彳、气 导师躲李乐民 日期：2 0 0 7 年7 月2 日 第一章绪论 第一章绪论 对于一个分布式的计算机系统，由于任务到达的随机性以及各结点处理能力 的差异，当系统运行一段时间之后，一部分结点分配的任务可能较多( 即为重载) ， 而另外一部分结点分配的任务可能较少或者空闲( 即为轻载或空载) 。此时，系统一 方面希望使重载结点尽可能快地完成任务，另一方面让某些结点空闲也是一种浪 费。为了避免这种空闲与忙并存的情况，从而有效地提高系统的资源利用率，减 小任务的等待时间，负载平衡技术相应地被提出1 1 3 j 。负载平衡技术设法对已经分 配给各个结点的任务进行重新调度，并通过进程迁徙，使各个结点的负载大致相 等。在分布式计算机系统上实现负载平衡，是分布式系统领域从7 0 年代初至今的 热门课题。1 9 8 0 年，lg v a l i a n t 针对多处理器的分布式系统提