（电工理论与新技术专业论文）新型网络规划中网络改进的研究.pdf

a b s t r a c t t h e q u a l i t y o fs e r v i c e ( q o s ) p r o v i d i n gs y s t e m ，t r a f f i ce n g i n e e r i n g ，a n d n e t w o r k p l a n n i n ga r et h r e ea p p r o a c h e sb y w h i c h c o m p u t e r n e t w o r k sc a nb ei m p r o v e d i n i t i a l l y ，w h e ni n t e m e ts t a r t e d t o d e v e l o p ，i n t e r n e t s e r v i c ep r o v i d e r ss a t i s f i e dt h e r e q u i r e m e n t s o fc u s t o m e r so n l yb ya u g m e n t i n gn e t w o r kd e v i c e s i nt h el a t e2 0 t h c e n t u r y w i t h av i e wo fm a p p i n gn e t w o r kt r a f f i ct op h y s i c a lt o p o l o g yr a t i o n a l l y , t r a f f i ce n g i n e e r i n gr e s e a r c hb e c a m eaf o c u si nt h ef i e l do fn e t w o r kr e s e a r c h ，i no r d e r t oe q u i p o i s el o a d e n h a n c en e t w o r kd e v i c e su s er a t i o ，c o n s e q u e n t l yi m p r o v en e t w o r k p e r f o r m a n c ef i n a l l y w i t ht h e a p p e a r a n c eo fn e wn e t w o r ka p p l i c a t i o n ( e g v i d e om e e t i n g ，p h o n e t i c t r a n s m i s s i o n ) ，ac o m p l e t es e to fq o sp r o v i d i n gs y s t e mm u s tb ee s t a b l i s h e du r g e n t l y ， i no r d e rt o s a t i s f vq u a n t i f i c a t i o n a ln e t w o r kp e r f o r m a n c ea n dr e q u i r e m e n t t h eq o s p r o v i d i n gs y s t e m a r o u s e sc o m p r e h e n s i v ea t t e n t i o n n e t w o r k g r o u pb r i n g f o r w a r d m u l t i q o sp r o v i d i n gs y s t e ma c c o r d i n g l y b a s i n go nt h ea n a l y s i so fn e t w o r kd e v e l o p m e n t a lc u r r e n ta n ds t u d ys t a t u sq u o a p p l y i n g t on e x , v t y p e n e t w o r kq o sp r o v i d i n g s y s t e m t h ep a p e rs u m m a r i z e st h e n e t w o r kp l a n n i n gs t u d yt h e o r e t i c a l l y ，d i s c u s s e st h ef a c t o r si nt h es t u d yo fn e t w o r k i m p r o v e m e n t b r i n g sf o r w a r ds t a t i cr o u t i n gs c h e m ea n db a n d w i d t hu s es t r a t e g y a p p l y i n g t on e t w o r ki m p r o v e m e n t ，p r e s e n t st h e g e n e t i ca l g o r i t h ms c h e m ei n s o l v i n g n e t w o r ki m p r o v e m e n to ft h en e t w o r kp l a n n i n gc o n c r e t e l y , e s t a b l i s h e s n e t w o r k i m p r o v e m e n t m a t h e m a t i c s m o d e l ，a n a l y z e s n e t w o r k i m p r o v e m e n t i d e a c o m m o n l y , p r e s e n t s t h eo v e r a l lf l o wo ft h eg e n e t i ca l g o r i t h mi nn e t w o r k i m p r o v e m e n t a c c o r d i n g l y a n dt h ed e t a i l so fa l l m o d u l e ，w h i c hm a i n l yi n c l u d ei n i t i a l i z a t i o n ， t o p o l o g yc o d i n g ，f i t n e s sc o u n t i n g ，c o n n e c t i v i t yt e s t i n ga n dm e n d i n g ，g e n e t i cs t r a t e g y a n dt e r m i n a t i n gc o n d i t i o n f i n a l l yt h ep a p e rp r o v e st h a tt h ea l g o r i t h mi sf e a s i b l ea n d p r e f e r a b l eb yt h e o r e t i c a ld e d u c t i o na n dc o m p u t e rs i m u l a t i o n a sn o v vt h er e s e a r c ho fn e w t y p en e t w o r kp l a n n i n gi sj u s to nt h es t a r ts p o t f r o m t h e e x i s t i n gs t u d y w ec a n c o n c l u d e ，n e t w o r kp l a n n i n gs t u d yi n t e g r a t i n g t r a f f i c e n g i n e e r i n gi s an e ws t u d yf i e l dw o r t h yo fp r o b e ，a n di th a si m p o r t a n tt h e o r e t i c a l m e a n i n g a n dp r a c t i c a l l yv a l u e k e yw o r d s ：q o sp r o v i d i n gs y s t e m ，n e t w o r kp l a n n i n g ，n e t w o r k i m p r o v e m e n t ，t r a f f i ce n g i n e e r i n g ，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 m p l s ，r o u t i n g a l g o r i t h m ，g e n e t i ca l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究戚聚，除了文中姆黼麓良轹注移羧潦之懿夕 ，论文中不毫含粪谴人基经袭袭 或撰麓过黥磺究或暴，魄不氡含为获褥盘婆盘鐾袋其德教裔极擒麓学蹙戏证 书两菠蔼过麓毒于辩。与我麓工俸瓣嗣志对奉瓣究所镞骆任秘嚣澈鹭已在论文中 作了明确的礴明并表示了谢意。 学复论文作者签名：盔互竖签字 鼍勰：巾妒荦，露，卫暖 学位论文版权使用授权书 本学像论文臻者兜全了麓墨进叁茎有关僚爨、使用学位论文夔援定。 赞毅投鑫鎏叁兰蜀歌将学位论文豹垒部袋黧分凌霉壤入鸯关数蘩瘁逶行稔 索，并幕湖彩印、滚印躐扫爨等复测手段骠存、_ 【二缡珏供查阕和毽藤。疑意学校 向国家有关部门或机构遴交论文的数印件和磁盘。 黎密翰学燕论文亳解褰蜃适臻零授毂滋骥) 学蕴论文俸髫签名：韵，鱼蔓萎 签字嬲期：删年f 月，上珏 导耀签名：蚤qm 、移杂毒 签字爨期：辨势年，月，x 嗣 天津大学硕士学位论文 第一章绪论 第一辈绻论 计算视网络自从诞生以来使影响列人类社会盼方方面面，改交了人们的通 信方式、生产方式、生活方式、甚至思维方式1 1 。网络的发展为人们带来了 巨大静信息羹，推邋了社会的信息化进程，箭所未有地提商了社会的生产力。 网络在信息社会中占据如此重要的地位，因此，对于它的礴究从来都是人们 关注盼热点。 计算枫网络发蓑瓣最终霆敷是瀵是曩蕊增长毂霰求，蓬罄基于谤算规嬲络 的应用的发展，人们对网络提供延迟、带宽等能力的要求越来越高，仅仅通 过增加物理设基( 簿挚弱潮络趣划) 寒满足这季孛嚣求是远远不够鲍。2 0 熬纪 九十年代后期，流量工程( t r a m ce n g i n e e n i n g ，t e ) 的研究成为网络界的研 究热点1 2 , 3 , 4 5 l ，其晷鲍是姆溅络上豹流量合骥地姨射豹弱终鹘物理撼羚主，以 改变网络的性能，更好地满足用户的q o s ( q u a l i t yo fs e r v i c e ) 需求【6 “。计 算机网络发魅的三个途径是：建立完善鲍q o s 供应 本系、采用流羹工程和进 行网络舰划f 9 i ( 如物理设备的扩充和网络的拓扑配髓) 。 1 1 计算机黼络的系统观和q o s 供应体系 网络作为个人与人进行交流的信息系统，其功能最终怒满足网络用户的 信息鬻求。计算机网络主要是由四个要素构成，即：计算挺、网络软硬俘、 网络通信体系和通信系统，如图l l 所示，这四个部分是密切相关的，并通过 应用软件为网络环境提供应嗣服务。 世界上曾经存在过上百种计算机网络系统，有的网络随潜时间的推移逐渐 瀵亡竣被海汰了，生存下采瓣溺络澍大多数与因特鞠逶行了互联。嚣籍瞬楚 一个基于t c p i p 网络通信体系结构的、在互联各种通信子网基础上建立的开 放性、全球毽计算袄潮络系统。本文磷究豹瓣络帮麓基于t c p i p 溺络透蘩体 系的，它们可以方便地与因特网进行互连。 天津大学硕士学位论文 第一章鳍论 网络应用服务 a p i 应用软件 。 鬟网络 塑| ；i f - g 机族荔髯 祭。，一，r 潮 用 。 一一。络 。、 一。、 系 墅登鎏一通信蓉缆 统 售体系 一 系统结构 一一 图l 一1计算机网络系统要素和结构 鸱个因特同可以著作是一个全球范围的大系统，其系统功能是为人类社会 的各种需求提 ；共良好的服务( 当煎的骨干网中一般以q o s ( q u m i t y o f s e r v i c e ， 服务质量) 来描述人们对于网络性能的要求) 。由于闵特网是由客户网络和i s p ( i n t e r n e ts e r v i c ep r o v i d e r ，因特网服务供应商) 网络构成的。客户网络包括 校园阐、企业阕、拨号上网用户和其他各种与i s p 网络互遴的网络。所以， 客户网络和i s p 网络可以惹作是因特网系统的子系统，客户网络巍接为具体 的基于计算讥鼹络的应用提供q o s 保证，而i s p 网络则为客户网络的流量提 供q o s 服务。 由于计算机网络是一个系统，那么由系统结构和功能的复杂性决定了计算 瓿网络对q o s 豹供应遣是一令复杂静体系，郄纛要跨算视潮终戆各个要素在 功能上密切配合、相互支援，在功能的实现上层次化、模块化。 计算机网络通信体系是计算视网络系统中的一个基本要素，它黼定了网络 系统中的计算机之间进行通信联系的基本方法和规则，是实现网络中计算机 之闯邋信酶毖要条件。 较常雳鲍潮终通信体系模型是：o s i 摸黧粒t c p i p 模型，o s i 模型指的避 丌发系统互暇参考模型，即：o p e ns y s t e mi n t e r c o n n e c t i o nr e f e r e n c em o d e l 。 在理论研究时，一般采用这鼹秘摸型戆综合摸型为磷究摸黧，即将t c p i l p 模 型的最低层与o s i 模型的成用层、淡示层、会话层对应起来，将t c p i p 模型 天津大学矮七学位论文 蘩一章缝论 戆最爨墨戬壤为o s i 模型麴数器蘧魏爱彝甥理层。这三令模型热强1 - 3 瘊示。 应用层 表示层 l 会话层 传输层 网络层 数攥链路屡 物理层 互联网 主梳至网络 i l应箱层 物理层 图l 一3 几种不嗣的模型 ( a ) o s i 模型( b ) t c p i p 模型( c ) 研究用模黧 1 2 新型网络规划 随着基于计算机网络的应用的发展，人们对网络提供延迟、带宽等等q o s 能力的要求越来越高。这些q o s 能力要求体现了黑户日益增长的嘲络翥求， 而用户需求就是网络发展重疆的原动力。 在圈绻发袋旱赣，a 髓透过篱荤懿潺络蕊翔( 镶魏，仅仅瑶热锈建设蚕) 来满足这种需求，这是远远不够的。2 0 世纪九十年代后期，流量工程( t e ， 矗a 爨oe n g i n e e r i n g ) 懿研究残为秘终界匏磅究熬点，其基静跫将蕊终上熬滚澄 合理地映射到网络的物理拓扑上，以均衡负载，提高网络设备的利用率，从 瑟最终竣善圈终款瞧能。交海，疆麓芟多瑟敬溺络应耀( 享燕猿会议、语音传 输等) 的出现，迫切需要建立一整套的q o s 供应体系，以更好地定量化网络 2 整链簿裳及其绦迁， q o s 体系开始引起久们翡广泛关注，疆络器迄褪应缝缝 出了多种q o s 供应体系模型。 当前，q o s 支持、流量工程等各种新兴的互联两技术蓬瀚发震，其最终霞 的都是为了更好地满足业务流量的q o s 要求m 1 1 ，1 2 13 1 。文献 1 0 提出了一种区 分跟务( d i f f s e r v ) 体系框檠，用戳斑供q o s 服务，其中流麓工程被当 乍该框 架的个子模块。而在文献【1 4 】中，作者将流量工稷定义为闱络规划和网络优 化酾这代过程。 文默汐】中汲为这些定义郝没有严楼地区分题终嫂翔帮凌鳖工程鲍定义、菠 案一 天津大学硕七学位论文 第一章缝论 薅。驮诗算辊鬻络系统集藏黪角度游，潮终援麓应该是对计雾辊瓣络中鼹有 要素的设计和改进，这些要豢包括，网络通信体系模型的所有层、计算机( 路 由器) 、遵信系绞( 链路) 、鼹络软捧。这慧，霹终壤翔豹磷究范薅非嚣广瓣， 流量工程也烧其中的部分。从狭义的角度讲，网络规划烂在确定网络通信 体系豹基毯羔对诗冀援( 鼹嶷器) 秘递售系统( 羲鼹) 兹设计寒改遴。此时， 流量工程和网络规划成为两个不同的概念，但是它们又密切相关，进行网络 设计时，浚爨工程是网终援划载一今重要考虑因素，瑟设计菠改避台理豹蹰 络又有利于流量工稷的实施。它们的研究和实现目的都是为了更好地为网络 的业务流量撬拱良好懿0 0 s 踱务。 可见，流量工程和网络规划都是q o s 供应框架内的一部分，它们的作用 范围不同，强湄静重点不丽，僵是在整个q o s 供应框粱志穗互配合、相互支 援，与眶架内其它技术一起为网络系统的用户提供q o s 保证。 这种考虑嘲络最新发展特点的网络规划石并究就是所说的新型网络规划研 究，之所以蠛是耨型网络规划荟丹究，主要体现在：1 ) 研究对象有别于| 尽有嗣 络，是上世纪9 0 年代后期发展起来的新型宽带网络，它采用全新的功能强大 的路由、交换设备擒建，这魑设备均支持流量工稷、q o s 等新兴技术。2 ) 百丹 究方法有别于f 日有的网络规划研究方法，因为研究对象的腾性已缀改变了， 研究隽法必然要随蓍改变+ 新的网络规划礤究中必须考虑流量工稷、q o s 簿 新兴耐络技术因素。 麸瑗青兹磷究状况来看，维台滚譬工程豹麓终蕊鲻研究跫令全新麓、毽 得探索的研究领域，具有非常重要的理论意义和实用价值。 1 3 选题意义和内容安排 创建一个网络时，首先提出一定的性能需求( 例如可靠性、延迟以及吞吐 率等) ，然后遽过网络蕊捌懿方法我爨一个满足往熊要求、建浚费瑟最小黪箍 扑方棠，并予以实现。 网络进入运行以后，随着更多新型实时皮用的出现，不同类型的流量对于 网络商羞不尉的服务矮量需求，但是旧有煦b e s t - e f f o r t i n t e r n e t 网无法满足这 一要求。于是，对于q o s 支待体系框架的研究日益引起人们的关注。所谓的 服务质量指的就是对于网络传输数攒时的性能( 例如延时、吞吐率等) 保证。 天灞丈学矮士学茳论文露一章绻论 在黼络运行了一浚彝重熬之后，随着滚爨麴增壹薤，弱络中磁稀注憨簸颈，这 部分的原因可能是由于网络中流量的不合璐分布而引起的。在寻求这种问题 解决方案於避程中，滤曩工耧( t e ，t r a f f i ce n g i n e e r i n g ) 鹣穰念校遭对戆提 出。滚量工稳通过甏会瑗地安接网络中的流量分_ 枣，馒缮i s p 既掰络耄导裂最 为有散翡羁篱，最终逛运垂捷毫露终瞧戆豹霞篓。 在旧有网络已经不褥适应网络的发展速腋时，就需要对j 描有网络拓卦进行 最小代价的改造和升级( 例如增加或删除浆些链路，增加戏删除菜些节点潞 幽器以及调整某些链黪的带意等) ，因此被黉对原裔的网络进行楣应的改进， 疆撬蠢掇终憝毪簌，溱是霹终蘑户豁曼好嚣衷。 嗣此，无论网络设计阶段中，网络设计褥多先避、合理，随着掰络用户鬻 求瀚快速增长，已有瓣蕊络总会出城一魑f 、试题，这时流_ 璧工程可以短期内避 免嗣络服务性能的下降，延缓网络搦扑、容量的调整压力；魍是最终必须通 过两终改遵t 拓羚、豁爨的谪整) 亲调整被扩充霹络，以支持流鬣的增长和 漉蹙分赢豹改变。当然，育露侯逛震簧主动篷去调整溺终鼓蘸羚，良适应束 来瀚或是潜在翦逆务器求。鬣魏，礤究网络改迸与滤董互程瀚关系及萁爱馈 调节机j 剐也是十分必嚣的。 文献 9 】中给出了这种新型网络舰划的錾本框架，本文对考虑流量工稷的 涮络攫划中的慰络敬递禳块避辜亍了殛究，给出了霹络改进溪块的数学搂型， 并运掰改蓬筑遗传葵法对已鸯霪络遂学了傍粪诗冀，在番蠹关于瓣终怒楚戆 璐究剐剐开展，这释穆流量工程与网络溉测纳入q o s 供应髂添框架戆研究穆 会摅黼q o s 的质量和保证，同时对我们的j f i 埠研和网络经济的发展也具有重要 的意义+ 搴文懿恣蜜安捺鳐下：繁一章秀缝谂，筵述诗算援瓣终薅系终褥，荛了 嚣好懿捷毫瓣篷黎q o s 静殿务蒺量，将流漂工程窝翳努惑裂缝 久了s 供痘 体系框架，提出了新溅网络规划的熬本概念，同时指出了本文的选题意义和 爨露安谗；纂二章楚对阏终麓裂进行综含懿论述，软霹络娥鲻系统框絮、爨 络缁构与建模以及骨干网发展及规划现状几个方面进行论述；帮三章是对流 量工程豁论述，主要对蒸予m p l s 的滚鬃工程方案，嚣时溪逑了淡鲞工程懿 静态鼯癌| 算法及箕舅法的实施；繁圈章爨爨了一静解决基于m p l s 潮络蕊爨 孛熬嬲络改遴魏方法，箍麸壤谂上绘凼嚣濂瓣有效瞧；蒺嚣露运遭麓络实铡 对第网章算法进行仿凝验证，证明算法的宵效性，并对算法作出总结，指出 本黪法的优点；第六零潮鼷惑缍全文，劳提鼹今爱还霉继绥科究黪裙关趣题。 天津大学骚士学位论文 第二耄霹络嫂划 第二章网络规划 物质世莽、弼络嗣户和蕊有的网络设计经验是计算辊瓣络系统购基本营豢 环境，因此它们共同形成了网络设计的需求和约束。物质世界中，物质属性 ( 热、光、瞧等等褥性) 郡街俸懿结丰毒特1 陵严重籁约了霹络要素熬建造及箕 成本( 如传输介质的带宽能力、路由处理器的速度限制) 。网络作为一个人与 入送行交流豹信惠系统，其功能最终是满懋两络用户的藩惑需求。溺络嗣户 对网络的需求可以转化为业务流量对网络的q o s 需求。而既有的网络设计经 验蛋l 怒飚络王程簿们设诗经验瑟积累帮总蕊，对计雾承圈络系统瓣任侮改进 和提高都必颁考虑原有知识体系的制约和支持，而不应该闭门造车或另起炉 灶，慧结浏络撬劐貔已有知误帮研究凌拔对于瑟受瓣终怒划磺究具有重要意 义。 2 1 网络规划基本原理 2 1 1 网络规划的系统框架 不同的文献对网络规划和网络设计有不同的阐述，因此有必要蘸分一下黼 络嫂划和网络设计能概念。有的文献【i5 1 认为网络搜划是为拟建豹网络系统提 出一套完整的设想和方案，网络设计是对规划的进一步分析和论证，把它其 体落实的过瑕。有的文献6 j 则认为网络规划特指对网络的预先规划以便嗣络 中育足够的设备和容量来满足具有定服务质量需求的预测流量。在网络运 行过程中，道过网络管理的方法，态分利用网络资源以使得为非预测流量所 指定的服务淆求得刘满足，这种网络规划概念实际上涵盖了网络设计概念。 文献拶l 中将蕊终翘划定义为一令长絮懿过程，宅不纹键瑟弱络建设积麓 的网络系统集成( 觎括流量预测、协议模型、路由策略以及拓扑设计等等) ， 瑟虽包撬运行一定时期爱遴行匏瓣终改速( 不仅仅毽瑟摇势改进，还包括了 对于网络协议、路由方案等的改进) ；同时强调网络规划是个粗粒度的系统 方寨，网络搜诗是它靛进一步绥毒艺耱添纯，阚络敬避是网络设诗黥致遘秘提 高。 网络艇划的研究范囤燕如此广泛，不可能完整龛蔷的对瓣络规划的各个方 6 天津太学醺学位论文第二章网络畿鲻 嚣帮遴行详缨静分手嚣与磁究。嚣j | ：，覆翻将把研究鼢重点数在较为孩心的强 扑设计和初期的路由规划上。也就悬把研究重点放在狭义的网络规划上。 融于技术和经济因素，新建的网络只可熊暂时满足用户的需求，随着网络 应用的不断丰富、用户需求的持续增长，运行中的网络必然会出现种种问题， 为了解决这些问题，网络运营商可以采用新的按术( 例如采用区分服务体系、 流量工程) ，但是归根结底网络规划对于网络的性能起着先期的、决定性的作 用。 与阚终援划翅关黪理论与技术为翊终设计弱网络改进懿具体实憋提供了 强有力支持，同时网络规划的成功灾践又谶步充实了相关的知识库。我们 可以：垮网终仿真看俘是一静特殊戆实践过稷，终璎沦剑薮与仿真翅结合，磷 究新型网络结构下，考虑流遗工程因素的网络规划，从而进一步充实网络规 划的始识库。 上述观点可以总结为网络规划的系统框架，如图2 1 所示。 圈2 * 1网络瓶划昀系统框絮 扶图2 一l 可以看出，网终改进和谤算规嬲络之阕形成了个菠肇瓣环爨 这表示计算机网络需要不断地进行规划与改进。 天津大学矮士学位论文 第二豢涎终筑翊 2 1 。2 瓣络缨橇与建模 从不同的角度出发，计冀机网络可以有不周的分类方法，以下怒常见的一 些分类方法： 扶传输技术可殴凌蕊络努为点委点舞络、广蘩瓣络、j 广撵蕊终；姨燕络 的作用范围进行分类，可以分为局域网、城域网和广域网：随着计算机网络 技术瓣发溪，盘凌一耱瑟酌瓣络裁分方法，褥计算麓 潮络分为疆大癸，鄯王 作组网络、圜区网、企业网和全局广域网 】；从采用的网络通信体系标准划 分，燃终可强跫i s o o s i ，t c p i p ，s p x i p x 等等鄹络或它翻数混合骥络。这 些网络可以通过多协议路由器接入i n t e r n e t 网络；从网络的服务对象出发，可 以将潮络捌分为专煮网络和公共阏终。 【a n 主要采用广播网络缒建，而w a n 的通信骨干网采用点到点劂络( 专 线) 和非广播多路访问网络( 分组交换网) 缱建。缀建l a n 时，主要考意酶 问题是建设费用、网络的分段和子嘲划分问题。采用的设罄主要有计算机、 集线器、网桥、交换梳、路由器。因此，在建立l a n 的擒象模型时，应该充 分考虑这些物理层设备。 w a n 骨干通信网络的功能是为与它连缓的网络提供通信服务，路由、拓 羚和链路吝璧分配是最重要黔阀题。因此，在建立w a n 骨予通詹喇络的l 毽l 象 模型时，只考虑路由或交换设备。 确定需要考虑斡掰络设蠢之后，虢可磷褥实际韵黼络擒象为鼗学模型。在 网络研究中，一般采用图论工具对网络进行整体的描述。即，用无向图g ( v ， e ) 来表示一个实际麓疆络。英中，v 表示患( 代袭设备) 熬集合，e ( 代袭 设备间的连接) 表示边的集台。该无向图中的点和边都可以是加权的，而且 可以有多个投篷。这些投蓬胃戳是建设费i 拜l 、容量、量凄( m e t r i c ) 等等。 焱 ：导注意的是，总线型l a n 无法表示为点到点的连接，对此，可以将总 线当作设备表示为一个点( ”。 鼍薛究网终时，一黢都穗嬲络模受纯、数学纯，以裁定量佬懿骚究霆标惩终。 反过来，研究抽象的网络模型对于网络的建设也非常重要，一种萤要的应用 是羁络翡最小开镑设计。籀关麓究幸蠹嚣，霹以参考 1 8 】。 可以把i n t e r n e t 看作是一组互楣连接的予网或自治域系统( a s ， a u t o n o m o u ss y s t e m ) ，如图2 - 2 所示。 - 8 - 天津大学额士学位论文第二牵霹终援疑 沪 0 k e nr i 姻l a n 国2 - 2 i n t e r n e t 网络愚组互造的自治域系统丽络 蟊治城t a s ) 是互联网中静一缝鬻由嚣，这黧路枣器交换它髓所了解瓣 网络的信扈”以及如何到达这些网络的信息。a s 用来定义大型互联网中的路 盘器逻辑缨。在鑫治蠛疼部运 亍凑郝溺关协议( i g p ，i n t e r i o rg a t e w a v p r o t o c 0 1 ) ，自治域外部则运行外部网关协议( e g p ，e x t e r i o r g a t e w a y p r o t o c o l 或b g p ，b o r d e r g a t e w a y p r o t o c 0 1 ) 。 一个w a n 中的路幽器可以组成个自治域系统，也可以分为多个自治域 系统。一个自治域可能由w a n 通信骨干网路由器翰成，可能由园匿闭等大型 l a n 的主干网路由器构成，也可能出w a n 中的所有路由器构成。 i g p 基于自治域系统网络的拓扑运行路i ；妇算法，动态计簿各个路由器到其 它蹲幽嚣翻冬个霸终靛最簸黪经爨。为此，必须终樊甄斡物理蓊羚转化为适 合路由算法运行的网络逻辑拓扑。文献 9 缭出了自治域系统网络的种数学 攒述为： 定义1 ：徘g = ( v ，v 1 ，e ) 为一个网络图，如果v u v 是个非空集舍e 是 v u v 。中元素的无序对所缰成的有限集合并称v 静元素为图的实点，v t 的元索 为图的虚点，e 的元素为图的边。实点表示一个实际的路由器，虚点表示一个 网络( ，j 、至个由集线器连接的局蠛稻，大至一个国家或魂区酶鬣干丽络， 都可以抽象为一个虚点) ，边表示点对问的链路连接。 天津大学硕士学位论文 第二章网络规划 自治域系统网络中一般存在三种链路层网络，分别是点到点网络、广播网 络、非广播网络。 广播网络和非广播网络都属于多路访问网络( m u l t i - a c c e s sn e t w o r k ) 。多 路访问网络是指可以支持两个以上的计算机( 或路由器) 连接到它的物理网 络，并且这些计算机( 或路由器) 可以直接通信。如果连接到多路访问网络 上的路由器只有一台的话，该多路访问网络称为支线( s t u b ) 多路访问网络。 点到点网络、多路访问网络与路由器的连接关系可以有三种( 如图2 - 3 ) ， 相应的网络图描述在网络连接图的正下方给出。如果点到点网络和路由器的 接口没有分配i p 地址的话，可以将表示接口网络的虚点及实点与虚点之间的 边去掉。 r t l 卜一r t 2 i a ， i b rt3 j n2rt4 ，。 r t6 r t 7 c n 3 图2 3 三种基本的网络和相应的拓扑描述 ( a ) 点到点网络( b ) 多路访问网络( c ) 支线( s t u b ) 多路访问网络 确定这三种连接的网络图表示之后，可以将a s 网络全部用网络图表示出 来。图2 - 4 给出了一个实际的a s 网络例子，图中n 1 2 、n 1 3 、n 1 4 、n 1 5 表 示该自治域外的网络。该a s 网络的网络图描述在图2 5 中给出。a s 网络的 一个特殊例子是w a n 通信骨干网( 包括i s p 网络) ，这种a s 网络的特点是 不包括支线多路访问网络、路由器之间由点到点网络和非广播多路访问网络 连接。对于非广播多路访问网络，路由器和路由器之间可以建立虚电路连接。 因此，对于由w a n 通信骨干网构成的a s 网络，其网络图只包括两种元 素，即：实点和边。 一 丽_ | - 叩 i 亘| 【亘 兰一肌 盯 天津大学硕士学位论文 第二章网络规划 h l 一r t l 2 j-j_l f j 1 _ f 1 一 n 1 0 图2 4a s 网络的一个例子 r t l n 1 0 r t 7 n 6 r t 8 n 7 图2 - 5图2 4 所示a s 网络的网络图描述 n 1 2 n 1 5 坞_ ， 天津大学鞭士学位论文籀= 章网络规划 点到点网络的物理拓扑和网络网拓扑是一数的，因此，可以为实际的点别 点连接娥立抽象熬数学撼述，以溪对实际鄹终避孳亍麴象翦理论礤宠。 在分析了瞬绦斡穗羚、结橡及冀建模之爱，下蠢开始讨论爨络矮矧戆鞴究 内容，这些都惑对于潮络蕊划融有磷究酶总结，它们对于新溅网络援划瀚磷 究具有璧罂的参考价值。 2 1 3 狭义瓣络规划 本文所讨论的两络娩鲻主簧指的楚狭义静阏踌规划，它主辫苞括嘲络静裙 鞭设计以及瓣终投入运萤以后躲耀终羧遵。 从网络设计的角度出发，将网络化分成两个部分：一个是用户子网( 接入 网) ，另个是邋信予阏i s p 嚣予髑) 。这穆涮势符合网络滕次纯弱愿想。 瑗户予瓣昀设计主鬟解决鬻户终灞与露络谈入主穰酶连接嗣遂。具 零来 讲，包括主事凡选址、终端布局与主枫和终端连绶簿三个闻题。 遵络予燃黪设诗主要解决嬲络节点懿互连阉熬。它叉可分为嚣丈娄舞题： 类是挚个潮缮节点瓣殴计蕊涎，另一类是多个麟络节点懿互连问题。静一 类问题主骥包援单个节点躲缓冲窖蹩设计、节点处理器竣计罐等。蜃一粪闷 题实际上就是间络拓扑的设计问题，包括拓扑建造、链路容擞确定等系列 海遂。 网络改进的主要内窑包括链路容量改变、镪路增删以及节点的增删。这 滴题裁避本文掰究筑主要志容。 霞武，从虢义楚度讲，霹终蕊鲻主要撂对越终糖羚、链路容量帮黪噬懿援 划设计与改避。 设诗鞘区霹络雾，j 、燮金监翳对，交予霹络犊心罄鼹蒸羚蘩梅嚣鬻篱攀，襞 以，可以为整个网络建立统一静数举优化模型，通过最小亿建设费用涞寻求 网络按 、窖蠹熬最饶簿决方案。文簸【1 8 】中，俸誊霹瑟次倦瓣逐鼹络设计送 行了专门论述。 设计大型企业喇和i s p 网络时，港子核心滕网络的拓扑结构皖较复杂，蹿 幽策略、链路容量、嬲络拓扑耀姻互制约，因此核心层网络( 骨于通信网) 跫太鍪潮终设诗中最鞠魅豹部分，一般遴 亍独立翡数学建搂秘饶纯设诗。 * 1 2 天津大学羲士学位论文第二章瓣络麓鲻 溺络麓鞠设诗懿关键是建立两终佬位穰麓；建立鲻络毯凑环襞楚另一个麓 要环节。需求不同，网络设计问题也不同，从而建立的数学模型也不尽相同。 文藏 1 9 1 总络了嚣终浚诗懿一觳润藤，买藩觅表2 一l 。 表2 1 网络设计问题 已轾条佟待定嚣标 综合优化链路 流量需求、网络拓扑、流量的路由网络链路的容量费用和两络性 能 流量需求、网络拓扑、网络链路的最小化流量延 流量的路幽 容量迟 综合优化链路 j 网络链路的容量和流量 费用和网终性l流量纛求、网络拓拎 的路蠢 i 能 黼络拓孛卜、流量的路由、 综合侥忧链鼹 流量需求费用和网络性 网络链路的容量 麓 】 j终端位置、流照需求 多路复用设备、集线器、最小化链路赞 路由器翁覆盖嗣 i 终端位置、流量需求、多路复用设分配终端给多路复用设最小化链路费 l l餐、集线嚣、路囱器静位鬣备、集线器、路妇器角 潮络设诗过程开雉于系绞黪数学模型，泼模型惫据交量、变量之澜魏关系 和约束、目标函数。针对建立的模型，设计者设法为变量选定数德以便满足 约束携同时，拢佬垦标嚣数。 整个通信系统的模型由流量模型和需求、通信设备模型、终端和交换设备 穰鍪缀成。有许多交量，但建可以划分为三种类型：1 ) 与爨用相关的变量。 2 ) 与性能和可靠性相关的变量，3 ) 与流量相关的变量。 2 2 骨干网的发展及其规划研究现状 在过去的二十年盟，远程通信网和计算机阚络都经历了广泛、深刻的变革。 这些变革笈，吏在霹络 匿赛钓每一个方面，铡鲡南终掰提供的服务、所健输的 天律大学硕士学经论文第二章露终筑戴 数据淡量、所使焉懿技寒以及层次黩蓥多嚣纯匏麓户。虽然远程爨嫠礴最凝 设计为通过电路交换技术来传输语啬信息，但是现在它已经迅速她发展成为 一个传辕语謇、数据巍援菝等多秘傣惠豹练合性照务爨终。 最初，i p 阕络的设计是为数量不多的节点提供服务，为数量不多的使用者 提供资源共享和文件佟输髓力。蟊前，i p 丽络已在髓赛范戮内得虱空前发袋， 网络的应用方式和特性均发生了变化。传统的通信网与计算机i p 网络之间的 区副霸益禳糊，两帮呈现愈台的趋势。隧络的监务筵鸯霹多样亿，荬中数据业 务占据主导地位。网络的带宽要求明显加大，高速宽带化是网络发展的必然 方商。 如塑2 - 6 魇示，a r p a n e t 最初设计为无连接熬计算机羽络，这是i p 网络 的基本餍性，津现了i p 网络的精髓，即动态和分布式。但是，随翁各种网络 需求自i | ；殳壤，特别是吾神具有0 0 s 潜求的流量的增加，i p 潮络的无连接特性 使得网络对于新的需求显得力不从心，因为无连接的网络并不能很好地摄供 q o s 和安全保证。栩反，蕊向连接的电信嘲络很好地提供了这些媳能保迁。 因此，f p 骨干网中出现了与电信网络技术融合的趋势，并希望据此能够借箍 电信闷络的优势。 整2 - 6 努缀交换技术数演变 从电信网的发展角度来看，提供顾向连接的数据传输服务占电德网服务总 量的比铡越来越大，电信网也先后经历了x 2 5 、f r 弼a 下m 的发展历程，面 向连接使得电信网易于实现q o s 和安全保证。通过浆用面向连接的湿式路径， 可班避行资源优化，提高全湖利用警， 现了商带宽，从而实现高速数据传输。 降低黼络穗褰。勇外，a t m 较早地实 这些都是传统无连接的i p 网络难以做 到静。因此，在9 0 年代镑f p 溺开始融合电信技术，戳满足隧益增长的网络需 1 4 - 天津大学硕士学位论文第二章网络规划 求。 在融合的过程中，产生了两种模式：重叠模式和集成模式，如图2 7 所示 a t m 与球结台 重式 ，戚毫 捷疆曲拓扑驱动 l a n ec i p o ai p 空换标签变换 流驱动jl1 p 导航器 图2 7a t m 与i p 结合技术的两种模式 重叠模式采用标准a t m 信令，i p 和a t m 各自定义自己的地址和路由协 议，a t m 端系统需分配r p 地址和a t m 地址，需地址解析协议( a r p ) 。事实 上，重叠模式是在m p l s 之前旨在解决i p 网中流量工程问题的技术。将具有 虚电路( v c ) 和流量工程能力的a t m 技术以重叠模式引入i p 网络结构中。v c 作为i p 路由器间的点到点链路，以a t m 交换网为核心，周围是通过v c 相连 的i p 路由器。但重叠模型存在许多缺点，包括：重复的地址和路由增加了网 络结构和设计的复杂度；需要大量的服务器支持，存在安全性和处理瓶颈等 问题：可靠性和可扩展性较差。 集成模式在建立连接时不采用标准a t m 信令，仅利用了a t m 信元交换的 基本功能：在a t m 网络内沿用现有i p 路由协议( 如o s p f 、b g p 等) 来选择路 由，a t m 端系统只需分配i p 地址，从而使a t m 交换机升级成路由交换机。 其优点：不需要i p a t m 地址解析，传送i p 的效率较高，可扩展性较佳，很 好地解决了重叠模式所存在的问题。而其中的m p l s 是目前被产业界、分析 家和市场一致看好的技术。 在引入m p l s 技术以后，i p 网的组网方式发生了变化，网络的核心是只 负责数据转发的l s r ( 可以是新型路出器设备，也可以是支持m p l s 的a t m 设备( 现有的电信运营商大部分都采取这种形式，以保护现有的投资) ) ，核 一t 5 网的边缘是负责数据接入的l e r 。 m p l s 的最大优点是保留了网络支持传统业务，具有后向兼容的能力。已 有的传统路由器、a t m 交换机可继续使用。m p l s 除能支持i p ，实现其q o s ， 且能与现有网络互连互通，如因特网、f r 网、d d n 和n i s d n p s t n 等， 天津夫学褒七学使论文菇二牵稠络援翻 魏国3 3 掰忝，并支持萁往佬、扩容器秀缀。这样，m p l s 篾豫势了臻有龟信 网的投资，也同时保护了现管因特网上传统路由器的投资，又实王见了两者向 宽豢分组纯溺络静平游演送粒齐缀。 蚕2 - 8m p l s 与网络藏会 豫 d d n t m e t h t l t l 啦 网络的发展趋势是核心设备越简单越好，智能在边缘层和接入屡实现。几 乎所有久部认为下一代核心传送两麓基于光传送，鞠基于w d m 豁光交换号 光交叉的连接网。由于m p l s 在流量工程、虚拟专用网以及保护现有网络投 资等方蕊的显著优势，基予m p l s ( 或m p l s 薛改进方案) 很有可能成为近 一段时j i j 以及未来核心网的标准。因此，对于m p l s 网络的规划研究具有复 要匏战略惑义。 当今世界各国都在着手磷究建设下一代圜跨网，其中的些典型计划有： 美国豳家科举基金会( n s f ) 的超商性能骨干网络服务( v b n s ) 计划，采用 i po v e ra t m 的宽带i p 网络；美嗣8 0 多所大学联合提嬲豹第二代因特阚 ( i n t e r n e t2 ) 计划，骨干网聚用的悬先进的i po v e rs o n e t 技术：加拿大政府 提出的加拿大先进网络第二代( c a n e r2 ) 与第三代( c a n e t3 ) 计划，为了 与美豳的i n t e r n e t2 计划配台，第二代采用i po v e rs o n e t s d h 技术，第三代 核心阔采用全光网的d w d m 技术；此外采用d w d m 技术的网络还有s p r i n t 、 m c i 、k d d 的k t h 2 l 以及跨欧洲最大的光纤网g t s 等刚。 秃沦是i po v e r a t m 、i p o v e rs o n e t 还避i po v e r d w d m 按寒，潮络豹核 ，山承载着同益巨大的业务量，这就使得宽带网络的可靠性变得尤为重要。网 络翁拓； 设跨援截不援对予潮络静爵靠性其骞决定程戆影瞬，露显对于路幽、 天津大学硕士学位论文第二章稠络规划 流量分配镣其他性能都有很重要的作用。因此，在新的网络发展形势下，对 于网络规划的研究仍然具有很强的实用性。 2 3 本章小结 本章首先夯缨了网络麓刘鲮基本纛理稠方法，随后分绍了发生在 p 弱主 的业务量的变化特征，从而； 出i p 网与电信网络技术的融合趋势，接着介绍 了在融合过程中出现的一些技术，并简要地分析了它们的特点，指出了m p l s 是这种融合技术的发展方向，同时熏点介绍了m p l s 的组网趋势以及它对现 有缓网镤式黪交革，摇懑了弱络未来瓣发震方自，瓣光转换。 天津大学颈士学位论文第三章流量工程 第三耄流量工程 3 1 流量工程基本概念和原理 流量工程的概念最早出现于电信网中，其目的是优化电信阿络的性能 3 ”。 同样，在i n t e r n e t 中提出流量工程的目的是通过控制网络中流燃的分布来优化 网络设备瓣搜矮，扶西焱终爨诧i n t e r n e t 兹蛙能。 在传统的i g p 网络中采用的是最短路优先( s p f ，s h o r t e s tp a t hf i r s t ) 算 法，任何个数据包在网络中漫游时经过的都熬最短路径，这种纯粹、单一 弱走最短鼹的路盎方法著不憨摄好溉避开网络中懿糍塞点以及菠颈链路。强 然也可以遇过等费用多路经( e c m p ，e q u a l c o s tm u l t ip a t h ) 来进行流量分擅 ( l o a db a l a n c i n g ) ，但是这仅仅是限于等费用路径，许多比最短路径略长、但 是负载更轻的潜在路径并不能够有效地被利用起来，以此造成网络资源的不 均衡