（信息与通信工程专业论文）基于tdscdma网络监管的负载平衡算法研究.pdf

r es e a r c ho nt h el o a d b a l a n c i n g a l g o r i t h mi nt h et d s c d 【a l a 弋f u li n t e r c e p t i o ns y s t e m at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s i 够 f o rt h ea c a d e m i c d e g r e eo f m a s t e fo f 1 _ e n g m e e n n g b y y a n gq i u c e n s u p e r v i s e db y p r o f i e s s o rh u a n gj i e s c h o o lo fi n f o n n a t i o ns c i e n c ea n d e n g i n e e r i n g s o u t h e a s tu n i v e r s 埘 j a n u 哪2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：童：丛垒 日期：盟历 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：垄毯签导师签名：毒。 摘要 摘要 目前随着3 g 移动通信技术的飞速发展，移动通信已经深入渗透到人们生活的方方 面面，深刻改变着人们的生活方式。如何实现对3 g 移动通信网络中非法信息的有效监 管，确保移动通信的安全合法，已经越来越受到国家相关管理部门的重视和关注。为此， 需要研究新的技术和方法以满足3 g 移动通信网络的监管要求。 本文从t d s c d m a 网络监管系统入手，针对t d s c d m a 网络可移动性、高速数 据传输、业务种类丰富以及业务流量大等特点，研究采用分布式系统来对从t d s c d m a 网络中截取的海量数据进行协议解析。为了实现负载在节点间的合理分配，提高分布式 系统的处理效率，就必须采用负载平衡算法来对系统中的负载实施合理有效的调度。近 年来，研究人员对分布式系统的负载平衡问题进行了大量的研究，提出了一系列的负载 平衡算法。但这些算法并不满足t d s c d m a 网络监管系统的应用需求，因此，本文针 对t d s c d m a 网络监管系统的特点，对分布式系统的负载平衡算法进行了进一步研究。 ：本文首先阐述了负载平衡所涉及的相关技术知识，包括概念、分类、特点、算法、 策略等，重点研究分布式动态负载平衡算法。对经典的分布式动态负载平衡算法进行分 析，并指出它们各自的特点及应用于t d s c d m a 网络监管系统的缺陷。 然后，本文重点研究了一个考虑了随机时延的分布式动态负载平衡模型和负载分配 策略模型，阐述了它的算法原理及其中各参数的意义，并对现有负载分配策略的计算方 法进行了分析。 在上述研究的基础上，本文进行了一种适用于，i d s c d m a 网络监管系统的分布式 动态负载平衡算法的设计。主要研究了以下几方面内容： ( 1 ) 提出了一个局域网环境下计算分布式系统随机时延的模型，并将其应用到设计 的算法中； ( 2 ) 选用了发送者主动的负载转移驱动策略和超出阈值的负载平衡机制，以保证 在负载平衡时，减少系统开销，节省系统资源，提高分布式系统的工作效率； ( 3 ) 在分析现有多余负载量和转移多余负载百分比计算方法的基础上，对它们进 行改进，以满足算法高效性和稳定性的要求；， ( 4 ) 在设计的算法中研究了负载重组问题，以保证负载平衡时转移的负载是完整 的协议数据包，从而不会影响分布式协议解析系统的正常工作； ( 5 ) 分析了设计算法的稳定性； ( 6 ) 通过仿真研究和在t d s c d m a 网络监管原型系统中的测试验证了设计的负载 平衡算法的功能性、有效性和稳定性。 本文设计的负载平衡算法确实能够高效、平稳地解决分布式协议解析系统中的负载 平衡问题，适用于t d s c d m a 网络监管系统。 关键词：随机时延；负载重组；分布式动态负载平衡；网络监管：t d s c d m a a b s 仃a c t 晰m 也ek 吐s p e e dd e v e l o p m e n to f3 mg e n e r a t i o nm o b i l ec o m m u l l i c a t i o nt e c h n o l o 姒 0 l 】rl i f eh i 毽b e e nc 1 1 a n g e dm o r ea i l dm o r e n o wn o t0 1 1 l y1 0 t so fv a l u a b l ei i 西溉a 1 i o nb l na l s o m u c hp o m o 脚l l i ca n di l l l 咄幽册a t i o nn o o d st 1 1 em o b i l en e t w o r k s ot l l et e c h n o l o 翟锄d s 仃a t e 星o fl a w 自l li i l t e r c e p t i o nm u s tb er e s e 甜c h e dt op r o t e c tm em o b i l en e 咖r ks e c 嘶坶 a g a i l l s ta b u s i l l gn e 帆r o r kr e s o u r c e h lt h ep 印m em 血r e s e a r c hi so n eo fm ek e yt e c h n o l o 舀e so fd i s t r i b u t e dc o m l ) u t i l l gf - 0 r t d - s c d m al a 训i i l t e r c e p t i o n 一1 0 a db a l 锄c h l ga 1 9 0 r i 恤n b e c a u s em ec h 锄删厢s t i c s0 f 1 d s c d m an e 似，0 r ka r em o b i l i t y ，g r e a t 仃a 伍cn o wa l l da 删v a r i e 付o fs e r v i c e s ，i ti s n e c e s s a r yu s i l l gd i 嘶h 眦ds y 咖mt 0d e a l 谢t l lt l l em 嬲sd a 饥b u t ，i i ld i s t r i b u t e ds y s t e m ，h o w t or e a s o n a b l ya s s i 呈皿n l el o a d s 锄o n g 伍en o d e s ，慨i s ，l o a db a l a n c m g ，h 嬲m u c h 砌u e n c et o t h ep e r f b 册a i l c eo fs y s t 锄i nr e c e n ty e a r s ，m a n yr e s e a r c h e r sh a i v ee n g a g e di nt l l er e s e a r c h e s o fl o a db a l a n c i n gp r o b l e m sa n dp u tr 删a r das e r i e so fl o a db a l a n c i n ga l g o r i t h m s b u tt l l e s e a l g o r i m m sa r en o ts u i t a b l ef o rt h el a w m li 】吐e r c e p t i o ni l lt d s c d m a t h e r e f o r e ，w em 戚 d e s i 趴an e wl o a db a j a n c i i l ga l g o r i t i l i i lf o rl a 讲试i n t e r c e p t i o ns y s t e mi l lt d s c d m a a t 丘r s t ，w ed i s c u s st l l er e l 撕v ek n o w l e d g eo f l o a db a j a n c i i l g ，i 1 1 c l u d i i l gc o n c 印t ， c l a s s i f i c a ：t i o i l ，c h a r a u c t e r i s t i c s ，a l g o r i t l l m s ，蛐g y 锄ds oo n b u tr e s e a r c l l i n gt l l ed y n a 血c l o a db a l a n c i n ga l g o 商【t l ：mi s 也ek e y t h e nm a n yc l a s s i c 由m a m i cl o a db a l a r l c i n ga l g o 面 1 l ：m sa r e a n “y z e da n dc o m p a r e d ，a n dm e i rc h a i ：a c t e r i s t i c sa n dn a w sa r ei 1 1 u s n - a t e d n e x t ，w es t u d yad y n 枷ct i m ed e l a ym o d e la n dal o a da s s i 霉皿s t 砒霉m o d e lf 0 rl o a d b a l a n c i i l g ，锄dr e p r e s e n tn l e i rp 渤c i p l ea n dn l em e a i 血go ft l l ev a r i o u sp a r a m e t e r s t h e nn l e c x i s t i l l gc o m p u t i n gm e m o di s 删y z e d b a s e do n 也ea _ b o v es t u d i e s ，、m ed e s i 霉皿ad y l l 枷c1 0 a db a l a n c i n ga l g o r i t h n li nd i s t r i b u t e d s y s t e mf o ri i l t e r c e p t i o ns y s t e mi i lt h i sp a p e r t h em a i o rw o f i 【sa r e 雒f o l l o 、椭： ( 1 ) t bp r o p o s e dar 锄d o mt i n l ed e l a ym o d e li i ll a n ，w i l i c hi su s e di i l 廿1 ea l 擘r o r i t h m ； ( 2 ) t bs e l e c t 也es e n d e ri i l i t i a t e ds 仃a t e 譬了姐db e y o n dm r e s h o l dl o a db a l a n c i n gm e d l a 血s m i no m e rt 0r e d u c es y s t e mo v e r b e a d ，s a v es y s t e mr e s o u r c e s ，a n di m p r o v et l l ee m c i e n c yo f d i s t r i b u 锄s y s t e mw h e nl o a db a l a l l c i n gh a p p e n s ： ( 3 ) t oi i n p r o v ct 1 1 ec o m p u 血gm e 也0 do f 写( f ) 锄d 助t 0m e e tt h el l i 曲- e 衔c i e n c ya i l d 虹b i l i t ) rr e q u i r e m 锄如o f 也ea l 舒时山m ； ( 4 ) t 0r e s e a r c ht l l ep r o b l e mo ff e 嬲s e n 曲1 i i l gl o a di na j g o r i t l l i nt 0e n s u r et l l a t 也e 啪f e 阿e d l o a di sac o m p l e t e 纰p a c k e t s ； ( 5 ) t 0a n a l y 2 跫n l es t a b i l i 够o fm ed e s i g n e da l g o r i 也m ； ( 6 ) t 0v a l i d a 【t et 1 1 e 删。玛e 腩c t i v e n e s sa i l ds t a b i l i 锣o fm e s y s t e m i i lc o n c l u s i o i l ，t l l ed ) ，n a i l l i c1 0 a db a l a i l c i i l ga l g o r i t h mi n “sp 印e rc a i li n d e e ds o l v em e p r o b l e mo fl o a db a l a l l c i n gf o rd i s t r i b u t e ds y s t e me 伍c i e n t l ya n ds m 0 0 t h l y a n di ti ss u i t a b l e f o rn l el a 、) 茌试i n t i o r c e p t i o ns y s t e mi nt d s c d m a k e yw o i m s ：r 册d o mt i i i l ed e l a y ；l o a dr e 嬲s e m b l i n g ；d y 嫩l i cl o a db a j a i l c i n gi l ld i s t r i b m e d s y s t e m ；l a 、娟j li n t e r o e p t i o n ；t d s c d m a m 目录 目录 摘要i a b 蛐隅c t 一i 目录v 第l 章绪论。l 1 1 研究背景及课题来源1 1 2 国内外研究现状2 1 3 研究内容。2 1 4 论文结构安排4 第2 章分布式动态负载平衡算法5 2 1 负载平衡算法概述5 2 1 1 负载平衡的概念5 2 1 2 负载平衡的分类5 2 2 动态负载平衡算法7 2 2 1 动态负载平衡算法的步骤7 2 2 1 1 负载信息收集7 2 2 1 2 负载分配决策7 2 2 1 3 负载转移8 2 2 2 动态负载平衡算法的驱动策略8 2 2 3 动态负载平衡算法的负载平衡时刻选择9 2 3 经典的分布式动态负载平衡算法1 0 2 4 本章小结1 l 。第3 章一种随机时延的分布式动态负载平衡模型1 3 ? 一 3 1 应用环境假设1 3 3 2 随机时延的分布式动态负载平衡模型1 3 3 3 负载分配策略1 5 3 3 1 负载分配策略模型：。1 5 3 3 2 参数的计算方法1 6 3 3 2 1 多余负载量的计算方法1 6 3 3 2 2 转移多余负载百分比的计算方法1 7 3 4 本章小结1 9 第4 章分布式动态负载平衡算法的设计2 l 4 1 算法的设计要求2 l 4 2 算法设计中的随机时延2 2 4 2 1 随机时延概述2 2 v 目录 4 2 2 为算法设计的随机时延模型2 2 4 3 算法的驱动策略和负载平衡时刻2 3 4 3 1 负载转移驱动策略的选择。2 3 4 3 2 负载平衡时刻的选择。2 3 4 4 改进的负载分配策略2 4 4 4 1 增益因子2 4 4 4 2 多余负载量2 4 4 4 3 转移多余负载百分比。2 5 4 5 算法设计中的负载重组2 7 4 5 1p 分片包的重组。2 8 4 5 2 会话的重组2 9 4 6 设计算法的稳定性分析3 0 4 7 设计算法的流程3 7 4 8 本章小结3 7 第5 章算法的仿真研究3 9 5 1o p n e t 仿真平台介绍3 9 5 2 仿真环境4 0 5 3 对随机时延的仿真研究4 2 5 4 对负载分配策略的仿真研究4 4 5 4 1 对增益因子的仿真研究4 4 5 4 2 对多余负载量和转移多余负载百分比的仿真研究4 6 5 5 对负载平衡机制的仿真研究4 7 5 6 对负载重组的仿真研究4 8 5 。7 本章小结4 9 第6 章算法的实现。5 l 6 1 监管系统的体系结构5 l 6 2 负载平衡模块的设计与实现5 2 6 2 1 负载平衡模块的组件划分5 2 6 2 2 负载平衡模块中的通信协议5 3 6 2 2 1 负载量信息通信协议。5 3 6 2 2 2 负载转移通信协议5 5 6 2 3 负载重组组件5 6 6 2 3 1p 分片包重组的实现5 6 6 2 3 2m 分片包重组中重要的数据结构5 8 6 2 3 3 会话重组的实现5 8 6 2 3 4 会话重组中重要的数据结构5 9 6 2 4 负载量信息通信组件6 0 6 2 4 1s o c k e t 服务器端的实现6 l 目录 6 2 4 2s 0 c k e t 客户端的实现6 l 6 2 5 负载平衡计算组件6 2 6 2 6 负载转移组件6 3 6 3 算法的性能测试6 3 6 3 1 测试环境6 3 6 - 3 2 测试用例及结果分析“ 6 3 2 1 测试甩例1 6 4 6 3 2 2 测试用例2 6 6 6 3 3 结论6 7 6 4 本章小结6 7 第7 章总结与展望6 9 7 1 本文工作小结6 9 7 2 待完善的工作6 9 l 致谢7 1 参考文献。7 3 攻读硕士期间发表论文与其他科研成果7 7 v h 第l 章绪论 1 1 研究背景及课题来源 第1 章绪论 随着3 g 移动通信技术的飞速发展和普及，移动网络的扩张使世界变成一个“地球 村。同时，伴随着移动通信网和因特网逐步融合，人们将既可以用手机自由进行语音 交流，又可以随心所欲地浏览图文并茂的信息，欣赏电视节目甚至玩联机对抗游戏。据 统计，2 0 0 8 年全球3 g 用户继续稳步增长，新增用户1 4 亿，和去年同期相比增长6 7 ， 在全部移动用户中的占比达到1 1 1 。图1 1 显示的是2 0 0 6 年2 0 1 0 年( 预测) 欧洲3 g 年新增用户的情况。 础g 趼艄嬲1 钿 一3 g _ 用户娩囊 万+ 簟长摹 图1 12 0 0 6 年- 2 0 l o 年( 预测) 欧洲3 g 年新增用户的情况 与此同时，我国也迈开了3 g 商用化的步伐。在工信部、电信运营商、电信设备制 造商以及业务提供商的共同推动下，2 0 0 9 年1 月7 日，工信部正式发布了3 g 牌照，中 国移动同步发布中国移动3 g 标识g 3 ，启动了3 g 产品1 8 8 号段；中国电信“天翼计划”， 启动1 8 9 以及我的e 家，正式步入全业务；中国联通宣布与网通合并完成，中国3 g 时 代全面开启。 随着3 g 市场的不断扩张和相关技术的提升演进，各种业务种类不断丰富，新业务 层出不穷，业务的生活化、娱乐化趋势明显。同时，随着移动用户普及率的提高，移动 业务的个性化特征不断凸显，推动移动业务深入渗透到人们生活的方方面面，深刻改变 着人们的生活方式。 但是，我们也应该清醒地认识到，3 g 网络既是一个大宝藏，同时也是一个垃圾场。 若不对3 g 移动通信网络中的反动、暴力、色情和赌博信息进行有效监管和过滤，那么 这些非法信息将充斥网络，泛滥成灾，对国家和社会的稳定发展造成严重影响。许多社 会学家和教育学者都呼吁控制移动通信网络中不健康信息的泛滥，对移动网络中的信息 进行全面监管。国家管理部门也在研究采取相应手段对移动通信网络进行必要的监管与 审查。 以往针对互联网实施的监管，是通过固定网络i p 地址的定位来识别网络用户。但 在3 g 移动通信网络中，这一监管方法已不再适用。因为在3 g 移动通信网络中，每个 用户的m 地址是动态分配的，不会和固定的用户绑定。可作为用户唯一性标识的有电 一 一 一 一 蛐 舢 。 东南大学硕士学位论文 话号码( m d n ) 、国际移动用户识别号( i m s i ) 、电子串号( e s n ) 和网络接入标识( n a i ) 等信息。但当用户的上下行数据进入互联网后，这些特征信息将不再保留，因此，必须 研究新的技术和方法以满足3 g 移动通信网络的监管要求。 本课题在国家高技术研究发展计划( 8 6 3 计划) “t d s c d m a 大规模用户群的信息 监管关键技术研究”( n o 2 0 0 7 a a 0 l z 4 3 2 ) 项目的支撑下完成。该项目的主要任务是研 究t d s c d m a 核心网络，结合其结构特点，提出具有自主知识产权的能够对大规模用 户群信息监管和信息源追踪的系统模型，并在研究基础上，实现一个原型系统。 1 2 国内外研究现状 3 g 移动通信网络具有网络可移动、数据高速传输、业务种类丰富以及业务流量大 等特点1 1 1 。为了实现对网络中高速海量数据的线速处理，就必须采用处理能力很强的设 备。由于分布式系统在处理大流量数据时具有性价比高、可靠性高、扩展性强等诸多优 点【2 】，因此逐渐发展成为主流的计算模式。 在分布式系统中，由于存在各节点( 即处理单元，可以是一台计算机或处理机) 处 理能力不同，外来负载到达系统时间不确定、负载大小不同等诸多原因，各节点在处理 负载的过程中可能逐渐出现节点之间负载量不平衡的现象【3 】，即有些节点上的负载量很 大，而有的节点却没有任何负载。若系统中出现负载量不平衡的情况而不加以改进，负 载的完成就会被大大延迟，影响分布式系统的效率和性能。为了避免系统出现负载不平 衡的现象，必须采用负载平衡算法来对分布式系统中的负载实施合理有效的调度i 4 j 。 数十年来，分布式系统负载平衡相关方面的研究已经取得了不少进展，在负载平衡 的分类、策略、实施要素、模型、技术实现、基本研究方法等方面都已有了较多的理论 成果。在算法方面，研究人员已经提出一些可行且有效的算法【5 l 【6 】【7 】【8 1 【9 】，其中大都是采 用不同的技术手段对负载平衡的三个方面( 信息表示与获取问题【l o j 、负载转移问题【l 、 定位查询问题【1 2 】) 进行处理。这些算法都在某些方面对负载平衡进行了改进，提高了系 统的效率。但也存在着如下一些问题： ( 1 ) 有些算法本身过于复杂，在负载平衡时会带来较多的额外开销，实施起来也 比较困难； ( 2 ) 有些算法在负载平衡时会引发系统的“负载颠簸 ，造成分布式系统的不稳定， 影响负载的处理效率； ( 3 ) 未考虑分布式系统中的时延对负载平衡算法性能产生的影响； ( 4 ) 算法的通用性不够，一般只能应用于特定拓扑、特定规模、特定应用场合的 分布式系统中。 为了能够解决上述算法复杂，稳定性不够，算法应用场合较局限等问题，本文对负 载平衡算法进行了进一步的研究。针对t d s c d m a 网络监管系统的实际应用环境，设 计了一种适用于分布式协议解析系统【1 3 】的分布式动态负载平衡算法，以实现对3 g 网络 中高速海量数据的线速处理。 1 3 研究内容 本项目的研究主要是针对t d s c d m a 网络实现大规模用户信息的监管，研究的监 管对象是t d s c d m a 网络核心网分组域g g s n 和s g s n 两个网元之间的实时数据流， 2 墨! 皇堕堡 研究目标是：截取t d s c d m a 移动通信网中的用户通信业务数据，实时对其进行解析、 过滤。根据处理结果，监管设备或人员能够及时地阻断非法信息，同时还能设定或取消 被监管的对象。 设计的t d s c d m a 网络监管系统的架构如图1 - 2 所示。 图1 2t d - s c d m a 网络监管系统架构图 与集中式系统相比，分布式系统在处理大流量数据上具有以下几个优点【1 4 】： ( 1 ) 分布式系统性价比更高。与集中式系统相比，分布式系统只需要很少的花费 就可以获得高效能的计算： ( 2 ) 许多应用本身就是分布式的，这种场合采用分布式系统也很自然； ( 3 ) 分布式系统可靠性更高。与集中式系统相比，分布式系统具有高度容错机制， 并不会因为个别机器的崩溃导致整个系统无法运行； - 一 一 -一 ( 4 ) 分布式系统具有更好的可扩展性。集中式系统若想提高性能，就必须更换一 台性能更强劲机器，而分布式系统只需向系统中扩充几台计算机即可； ( 5 ) 分布式系统具有高度灵活性。分布式系统可以兼容不同硬件厂商的产品，同 时分布式系统中的计算机的配置也可以完全不同。 基于以上几点考虑，在项目中采用分布式系统来实现对t d s c d m a 网络中海量数 据的处理。然而在分布式系统中，各个节点如何能快速有效地处理负载，输出期望结果， 除了依赖于分布式系统本身，包括系统规模，各处理节点的计算能力，互连网络等因素 外，关键在于负载平衡算法的设计。 本文的主要研究工作就是针对t d s c d m a 网络的特点，为分布式协议解析系统设 计一种负载平衡算法，使得分布式系统中的各个节点能平稳、高效地解析用户业务数据， 满足t d s c d m a 网络监管系统的需求。 本文的主要工作包括以下几点： ( 1 ) 研究了一种考虑了随机时延的分布式动态负载平衡模型，阐述了它的算法原 理及其中各个参数的意义，研究了负载分配策略模型，对现有负载分配策略中各参数的 3 东南大学硕士学位论文 计算方法进行了分析； ( 2 ) 以随机时延的分布式动态负载平衡模型为基础，设计了一种适用于 t d s c d m a 网络监管系统的分布式动态负载平衡算法。主要内容包括：提出了局域网 环境下计算随机时延的模型；选用了发送者主动的负载转移驱动策略和超出阈值的负载 平衡机制：在分析现有多余负载量和转移多余负载百分比计算方法的基础上，对它们进 行改进，以满足算法高效性和稳定性的要求；研究了应用于分布式协议解析系统的负载 平衡算法所特有的负载重组问题；并对设计算法的稳定性进行了分析； ( 3 ) 利用o p n e t 网络仿真软件搭建了一个分布式协议解析系统的仿真模型，并在 其中对设计的算法进行了仿真研究； ( 4 ) 在分布式协议解析原型系统中实现了设计的负载平衡算法，并对算法的性能 进行了测试。 1 4 论文结构安排 本文分为七章，除了本章之外，其余各章内容如下： 第二章主要介绍负载平衡所涉及的技术知识：阐述了负载平衡的概念、分类及其特 点，重点分析了动态负载平衡算法的步骤、驱动策略及负载平衡时刻选择，最后对几种 经典的负载平衡算法进行了回顾，并指出将这些算法应用于t d s c d m a 网络监管系统 所存在的缺陷和问题。 第三章主要研究了一种考虑了随机时延的分布式动态负载平衡模型和负载分配策 略模型。详细阐述了现有负载分配策略模型中各个参数的计算方法，并分析了各自的优 缺点。 第四章主要是针对t d s c d m a 网络监管系统的应用需求，在第三章模型的基础上， 设计了一种随机时延的分布式动态负载平衡算法，对设计算法的特点、流程以及每项改 进和选择都进行了详细的阐述。 第五章简单介绍了o p n e t 网络仿真软件，重点阐述了其三层建模的特点。在完成 了网络、节点和进程建模的基础上，搭建了一个分布式协议解析系统的仿真平台。然后 对第四章中算法的每个设计和改进进行了一一仿真实现，并予以分析。最后通过对设计 的负载平衡算法的仿真，验证了该算法的性能。 第六章首先介绍了t d s c d m a 网络监管系统的架构和模块划分，对其中的负载平 衡模块进行了组件划分，阐述了核心组件的实现方法，最后介绍了在t d s c d m a 网络 监管原型系统中，对实现的算法进行测试的情况，并对测试结果进行了分析。 第七章是总结和展望，总结了本文所做的工作和进一步需要解决的问题。 4 第2 章分布式动态负载平衡算法 第2 章分布式动态负载平衡算法 为了提高分布式系统的性能和增加系统的吞吐量，就必须采取负载平衡算法来平衡 系统中各节点的负载量，从而提高整个分布式系统的资源利用率。近年来，如何为分布 式系统设计合适的负载平衡算法这个问题一直是人们的研究热点。在本章中，首先阐述 了负载平衡的概念、分类及其特点。接下来重点分析了动态负载平衡算法的步骤，负载 转移的驱动策略及负载平衡时刻的选择。在此基础上，对经典的分布式动态负载平衡算 法进行了回顾，并指出将这些算法应用于t d s c d m a 网络监管系统所存在的缺陷和问 题。 2 1 负载平衡算法概述 2 1 1 负载平衡的概念 分布式系统中的负载平衡问题是一个经典的组合优化难题，在过去的二十多年中， 各国研究人员对这个问题进行了大量的研究工作，提出了多种解决负载不平衡问题的算一、 法。具体来说，负载平衡就是将分布式系统中重载节点的负载转移到其它轻载节点上， 平衡各节点的负载量，从而提高系统的吞吐量，加强系统处理负载的能力。 通常对该问题的描述是：给定很大数量的一组负载，寻找一种合理的负载分配方法， 使得对于给定的一个目标函数( 如系统完成所有负载的时间) ，节点可以实现对负载的 最优化处理i l5 1 。具体来说，分布式系统的负载平衡问题可以描述如下： ( t 1 ，t 2 ，t m ) 是一组待处理的负载，( p 1 ，p 2 ，p n ) 是分布式系统的n 个节 点，通常m n ，如图2 1 所示。节点之间按照一定的拓扑形式进行通信，负载分配策略 s 把m 个负载分配给n 个节点。要求考虑如何在各个节点间实现负载的合理分配，从而 使得完成所有负载的代价最小。不同节点的负载量信息交换是通过节点之间彼此的通信 实现的。 2 1 2 负载平衡的分类 图2 1 负载平衡问题描述 通 信 网 络 目前存在许多负载平衡算法以满足不同应用场合的需求。根据不同的分类方法，可 以对负载平衡算法进行分类。 ( 1 ) 根据拓扑结构分类 根据分布式系统拓扑结构的不同，负载平衡算法可以分为扩散算法【1 6 】( d i 觚i o n 5 东南大学硕士学位论文 m e t h o d ) ，分层负载平衡算法【17 j ( h i e 眦1 1 i c a lb a l a n c i n gm e 怕d ) ，梯度模型算法【1 8 l ( g r a d i e n tb a s e dm e t h o d ) ，元交换模型算法【1 川( d i i i l e n s i o ne x c h a l l g em e t h o d ) 等。在这 些算法中，每个节点只能与其相连的节点进行通信和负载转移，通过多次循环迭代实现 分布式系统的负载平衡。 在扩散算法中，每个节点通过与周围节点进行信息通信来判定是否需要负载平衡。 若需要进行负载平衡，重载节点就将多余的负载向相邻的轻载节点进行转移，这样首先 在分布式系统一个区域中实现负载平衡，然后向周边区域逐步扩散，最终实现整个分布 式系统的负载平衡。 在分层负载平衡算法中，先将分布式系统中的所有节点组织成不同层次的树状子系 统，负载平衡先在低层节点之间进行，然后不断向上扩展，从而实现整个分布式系统的 负载平衡。 基于梯度的负载平衡算法有多种，其共同特点是用一个负载梯度图来描述整个系统 的负载情况。负载平衡时，负载向着梯度最陡方向的节点转移，当所有节点的负载梯度 为零时，分布式系统就达到了负载平衡。 元交换模型算法采用与分层负载平衡算法类似的方法，只不过它是一种全局同步的 负载平衡算法。 ( 2 ) 根据负载信息的管理方式分类 根据负载信息的管理方式的不同，负载平衡算法可以分为集中式负载平衡算法 ( c e 砷融i z e dm o d e ) 和分布式负载平衡算法( d i s t r i b u t c dm o d e ) 【2 u j j 。 在集中式负载平衡算法中，分布式系统专门利用一个节点来收集其它各节点的负载 量情况，并控制整个系统的负载分配过程。这个特殊节点并不进行负载处理，其地位高 于系统中的其它节点。集中式负载平衡算法的优点是简单、直接，适用于采用广播机制 或者集中监控的系统，但这个系统的首脑节点可能成为分布式系统的瓶颈，其一旦瘫痪， 整个分布式系统也将无法正常工作。 在分布式负载平衡算法中，分布式系统中所有节点的地位都是平等的，一同承担着 接收其它节点负载量信息，自主完成负载转移的任务。分布式负载平衡算法的扩展性、 鲁棒性都很优秀，适用的场合更加广阔，但实现起来比较复杂。 ( 3 ) 根据分配负载方式分类 根据分配负载方式的不同，负载平衡算法可以分为静态负载平衡算法( s t a t i c m e t l l o d ) 和动态负载平衡算法( d ) r n a 而cm e t l l o d ) 幽。 静态负载平衡算法是根据分布式系统中节点的性能和进入系统负载的特性，预先制 定一个负载分配策略，在系统运行的整个阶段都按照这个不变的负载分配策略将负载分 配到各个节点中去。由于静态负载平衡算法一旦制定好就不能改变，而在高度并行的多 计算机领域，特别是在多用户方式下，进入分布式系统的负载是动态产生的，不可能对 其特性做出准确的预测。因此，尽管静态负载平衡算法简单、容易实现，但适用范围很 窄，多用作理论研究和辅助工具。 动态负载平衡算法则是在系统运行时实时检测系统中各节点的负载量信息，自适 应、动态地将负载在各个节点中进行分配和调整，以实现分布式系统的负载平衡。相对 于静态负载平衡算法，动态负载平衡算法具有更大的灵活性和针对性，应用范围更广， 可根据当前系统的负载状况有目的地进行负载平衡。但动态负载平衡算法实现起来比较 复杂，虽然能得到比较好的平衡效果，但必然导致分布式系统增加一定的额外开销。不 过实验表明，如果调度得当，这些额外的开销对整个分布式系统性能的改善来说是值得 的】【矧。 6 第2 章分布式动态负载平衡算法 由于分布式动态负载平衡算法应用广泛，可靠性高，能实现较好的平衡效果，本文 主要研究的是分布式动态负载平衡算法。 2 2 动态负载平衡算法 2 2 1 动态负载平衡算法的步骤 为了在分布式系统运行过程中，实现动态分配、调整负载以达到各节点的负载平衡， 动态负载平衡算法一般包括负载信息收集、负载分配决策、负载转移三个基本步骤【2 5 1 。 2 2 1 1 负载信息收集 分布式系统中各节点的负载量信息是对各节点运行队列中负载量的描述和表征。若 分布式系统中的一个节点需要进行负载平衡，它需要先收集分布式系统中其它节点的负 载量信息。节点收集负载量信息的方法通常有以下三种【2 6 】： ( 1 ) 周期性收集策略：每隔一定的时间周期，每个节点就向其它节点报告( 或询 问) 本节点的负载量情况，以便各节点都能定时了解系统中其它节点的负载量信息。 ( 2 ) 命令驱动策略：该策略依赖于整个系统中各节点的状态，只当有了解其它节 点负载量信息的需要时，即该节点成为发送节点或接收节点时，才向其它节点发送获取 节点负载量信息的请求。 ( 3 ) 状态变化驱动策略：顾名思义，该策略是节点仅在负载量发生变化时，。才向 其它节点发送最新的负载量信息。 节点负载信息收集是动态负载平衡算法的第一步，它的效率会影响整个负载平衡算 法的性能，是分布式系统做出下一步负载分配决策的基础。 一 2 2 1 2 负载分配决策 i 当节点通过负载量信息收集获得了其它节点的负载量信息后，就要根据所收集的负 载量信息进行负载分配决策。决策的方式通常分集中式和分布式两种【2 7 】： ( 1 ) 集中式决策：分布式系统中有一个节点专门负责系统中各节点负载量信息的 收集和负载分配的决策。这是一种全局决策，但由于决策后，所有的负载转移都必须通 过该节点，容易造成该节点过度繁忙，从而降低系统