（电磁场与微波技术专业论文）智能光网络中的rwa算法研究.pdf

北京邮电大学硕士学位论文 摘要 智能光网络中的r w a 算法研究 摘要 智能光网络是未来骨干传送网发展的方向。由于在网络中引入了包括 信令、路由以及生存性机制在内的智能化网络控制技术，因此，智能光网 络能够支持动态的连接建立、灵活地调度网络资源，并能够根据用户的需 求提供多样化的带宽服务。 本论文的工作将从分析智能光网络的业务入手，并提出一种周期性可 预测的业务模型。该模型的提出主要是针对光虚拟专网0 ) n 业务，研究 这类业务模型的意义在于实现波长资源的时间复用性。 论文第二章主要研究了优化策略与优化算法，由于静态础a 问题本身 也是一类优化问题，故而可以采用传统优化算法进行求解。文中详细论述 了三种常用的建模方法，并按照算法复杂度由大至小的顺序分析比较了八 种常用的优化算法。结合周期性可预狈i 的业务模型，本文提出了基于遗传 算法和一般性启发式方法的路由解决方案。 论文第三章主要研究了i po v e rw d m 对等模型下的多层联合路由问 题。围绕着各种不同的生存性策略，本文提出了基于专有通道子通道保护、 基于共享风险链路组s r l g 的共享恢复、以及基于无保护策略下的多种联 合路由算法。通过对自相似业务模型下的模拟仿真，比较并验证了各种算 法的优化性能。 论文的第四章只要研究了光网络规划中的相关问题，具体包括一般性 规划流程、业务的梳理、传送网络设计、路由算法选择、规划结果分析等 技术性问题。针对由现有光传送网向智能光网络过渡这个问题，本文进一 步讨论了a s o n 网络规划的种可行性方案。 关键词 智能光网络r w a 算法周期性可预测业务模型优化策略及优 化算法联合路由光网络规划 北京邮电大学硕士学位论文abstract r e s e a r c ho nr o u t i n ga n d ( a v e l e n g t ha s s i g n m e n tp r o b l e m s i ni n t e l l i g e n to p t i c a ln e t w o r k s a b s t r a c t i n t e l l i g e n to p t i c a ln e t w o r k s2 u r et h em o s tp r o m i s i n gc 锄d i d a t ef o rt h e r e b a c k b o n et r a n s p o r tn e t w o r k s i n 血ei n t e l l i g e n to p t i c a ln e t w o r k s ，c o n n e c t i o n s c a nb es e tu pa n dr e l e a s e dd y n a m i c a l l y ，t h en e 研o r kr e s o u r c ec a nb ea s s i g n e d a n dr e c o n f i g u r e de 虢c t i v e l y ，趾dd i 艉r e n t i a t e d b a n d w i d t hp r o v i s i o n i n gs e r v i c e s a r ep r o v i d e d i nt h i sd i s s e r t a t i o n w ee n t e ro nt h er e s e a r c ha t 也et r a f j f i cm o d e lo f i 1 1 t e l l i g e l l to p t i c a ln e 觚o r k s w eb 咖gf o l w 盯da 虹n do ft r a m cw h i c hi sc a l l e d t h es c h e d u l e d 钉a f j f i cm o d e lf o rt h ef l r s tt i m e ，a n dm i sm o d e l i sd e r i v e d 矗o mt h e 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 s ( o v p n ) t r a 伍c w bw a n t t og e tm o r el ( i l o w l e d g e a b o mm em u l t i u s eo f t h et i m er e s o u r c eb yt h i sk i n do f t r a f j f i c c h a p t e ri i s t u d i e st h eo p t i m i z a t i o ns t r a t e g i e sa n da l g o r i n u n s t h i sc h 印t e r i n c l u d e sad e s c r i p t i o no fs e v e r “m o d e l l m gt e c h n i q u e sa 1 1 do p t i m i s a t i o n a l g o r i t h m sn o m a l l yu s e df o rs 0 1 v i n gt h eo p t i m i s a t i o np r o b l e m sw h e np l a r m i n g t h ec 1 - l r r e n t 仃a n s p o r tn e t w o r k s d u et ot h en a ：t u r eo ft h ep r o b l e m s ，i ti se x p e c t e d m a tm e s et y p e so ft e c h n i q u e sm i g h tb eu s e d ，a sw e l l ，f o rt h eo p t i m i s a t i o n p r o b l e m si n v o l v e di nt h eo p t i c a ln e 押o r kp l a n n i l l g c h 印t e ri i ir e s e a r c ht h em t e g r a t e dr o u t i i l gp r o b l e m sb a s e do n 也ep e e r m o d e li ni po v e rw d mn e t w o r k s c o n s i d e r i n gd i 位r e n ts u r v i v a ls t r a t e g y w e g i v eo u ts o m er v m 。a l g o r i t l l m s a c c o r d m gt ot h es i n m l a t i r 培，w es t u d i e da n d c o n l p a r e d a l lt h e s ea l g o r i t h m s p e r f i o r m 矾c e c h a p t e r s t u d i e st h ep l a n n j n go fo p t i c a ln e t w o r k s ，w l l i c hi n c l u d e st h e c o m m o nn o w 、t r a f 6 cg r o o m i n g 、t h ed e s i g no fm e 仃a n s m i s s i o nn e t 、v o r k s 、t h e r w r aa l g o r i t h m sa n da n a l y s eo fm er e s m t be s i d e s ，w ed i s c u s st h ep 1 眦l i n go f t h ea s c nn e t w o r k sb v 虹锄s i t i o n 舶mt h es d h w d mc o r en e t w o r k s k e yw o r d s ： i n t e l l i g e n to p t i c a ln e t w o r k s 、r o u t i n g a n dw a v e l e n g ma s s i g m e n t 、s c h e d u l e d t r a m cm o d e l 、0 p t i m i z a t i o ns t r a t e g i e sa n da l g o r i t l u n si n t e g r a t e dr o u t m g 、 p l a n 血n go fo p t i c a ln e t w o r k s i i 一 p 、 - j 、 - 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除 了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：墨监连日期：兰型矗每墨岔! 兰鱼 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论 文。( 保密的学位论文在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： 日期： 2 堡牟圭壁塑 日期：兰型：至：竺 -卜lr-liiiliilil i|卜一ir 北京邮电大学硕士学位论文第1 章光网络业务模型分析 第1 章光网络业务模型分析 1 1 业务驱动的光网络 1 1 1 电信市场的现状与挑战 在经过了近1 0 年的飞速发展之后，全球的电信市场出现了大幅度下降，受之影响， 中国电信业务和网络发展的速度在一定程度上有所放缓。在南北拆分、并购重组之后， 中国的电信运营商出现了新的竞争格局。由于各大运营商所面对的是垄断后重新划分的 市场，需要在对手的范围内渗透并争夺客户，因此只有通过不断发展业务种类、改善服 务方式、增强网络性能以适应用户的需求，才能够在新的市场站稳脚跟、在激烈的竞争 中求得生存。 经过前些年的快速发展，用户的普及率已经达到一定程度，用户规模的增长率已经 趋于合理化。如何将在这一增长率在相当的时间内保持下去，这就需要不端地开发出新 的可赢利的业务模式，以吸引更多的用户进行消费。将“粗放型”的规模膨胀转向“精 细型”的网络建设；将市场从单一的增加用户数变成如何保持平均用户营收率( a r p u ) 的增长川。而提高a r _ p u 的重要因素是如何满足用户的需求，包括不断增长的容量需求、 不断变化的业务模式、多协议的网络环境，并要求网络运营商能为用户随时随地的提供 特殊服务。在提高营收的同时，运营商还需要在维护管理网络和降低维护成本上加强力 度。 | 垄jl - l 运雷成本分析 图1 1 所示为网络运营成本分布情况。由于操作、管理和维护费用约占整个成本支 出的4 9 ，因而在降低网络运营成本时，要着重考虑减少这一部分的成本。为满足这一 需求，提供强劲的网络功能和相对低廉的成本费用以及灵活的操作维护手段，建设业务 驱动的光网络是一个重要的途经。 1 1 2 业务驱动的光网络 所谓“业务驱动的光网络”就是其建设更加具有计划性，能反映市场的需求和变化， 北京邮电大学硕士学位论文第l 章光弼络业务模型分析 根据需求扩展网络而无需改变网络的基本结构和运维模式。能够快速灵活地配置高速光 业务网络，可满足用户的业务需求。运营商和最终客户可以进行业务选择、建立、修改 和拆除业务连接。 建立业贫驱动的光网络，需要网络具有智能性，使得电信运营商可以满足广大用户 提出的各种业务需求。这包括多业务平台的建立，端到端业务的建立、拆除和改动，动 态网状网和逻辑环网的混合应用等一系列基于业务的网络特征。 根据目前中国电信业发展的过程分析，建立基于业务的智能光网络应从城域网的核 心开始，进而带动城域网的边缘，最后引发各骨干网的智能性。这是由城域网本身的复 杂性、灵活性和多样性所决定的。 1 2 智能光网络的业务 1 2 1 传统光网络的智能化演进 正如本文前面所述及的，当前的传送网络必须要向下一代能提供多种服务及应用的 具有智能性的业务驱动型网络发展。而一个智能的业务驱动型光传送网络，必须是一个 能够支持动态带宽调配，易于管理维护并具有高度灵活性的、具有统一传送核心以及支 持多功能适配层的光传送网。 目前，传送平面技术的发展虽然降低了运营商在基础网络建设方面的投入，但这种 成本的降低还不足以充分保证运营商收入的提高。更重要的是，传输网络规模的不断扩 大，电路数量的不断增加以及数据业务对传输需求的突发性要求都造成基础骨干网络管 理维护上的极大困难。尽管电信网络管理技术一直是备受关注的问题，但由于网络结构 本身的限制，单纯依靠管理平面的技术进步难以从根本上消除传统光网络带宽配置固 定、资源利用率不高、管理维护复杂等缺点【2 】。 因此，智能光网络的概念应运而生，其主要特点是除传送平面和管理平面以外，在 光网络中引入控制平面，从而实现光层的交换、路由和其它智能功能。随着控制平面技 术的发展成熟，网络的智能化和自动化的程度越来越高，使得网络运营商能够更加灵活 和高效地新增或改变业务服务。 1 2 2 智能光网络体系架构特点 i t u - t 的g 8 0 8 0 和g 8 0 7 定义了一个与具体技术无关的智能光网络体系架构( 如 图l 一2 所示) ，它包括三个独立的平面，即控制平面( c p ) 、传送平面( t p ) 和管理平 面( m p ) 3 】，三个平面通过d c n 相连，d c n 是一个负责路由、信令、链路资源管理 以及网络管理信息传送的信令通信网( s c n ) 。 北京邮电大学硕士学位论文第l 章光网络业务模型分析 客 设 理 面 图l - 2 智能光网络的体系结构 与传统的光传送网相比，智能光网络最大的突破点在于加进了具有智能特性的控制 平面，它的引入使得光网络能够在信令的控制下完成网络连接的自动建立、资源的自动 发现、网络拓扑信息的自动更新以及故障的自动定位及上报等功能。 传送平面由一系列的传送实体组成，用来为不同的用户传递业务信息、以及部分控 制信息和网络管理信息。管理平面用来对传送平面和控制平面进行管理并对各平面的操 作进行协调。通常，管理平面的在智能性上不如控制平面，其部分的管理功能被控制平 面所取代。 正是由于智能光网络控制灵活、管理有效等特点，使得其可以从光域( 波长) 提供 多种新型的高速率、高附加值的业务。以波长业务为基础，业务提供商构思了多种增强 业务( 如波长批发，波长出租，带宽运营、光虚拟专网等) ，这些业务都能根据现有的 和将来以数据为中心的组网应用而扩展，在满足最终用户多重需要的同时，为电信运营 商带来可观的经济收益 4 】。可见，智能光网络正是建立“精细型”、“业务驱动型”下 一代光传送网络的发展方向。 1 2 3 智能光网络业务 由于以a s 0 n 为代表的智能光网络是构造在各种传送技术之上的，也就是在传送 平面s d h 、光传送网w d m 之上增加了独立控制平面，因此它支持目前传送网可以提 供的各种速率和不同信号特性( 如格式、比特率等) 的业务。智能光网络可以在两个客 户网元之间提供具有固定带宽的传输通道，通道界定在光网络的输入接入点和输出接 入点之间。常见的业务有： 1 ) s d h 业务，g 7 0 7 定义的s d h 连接颗粒v c _ n 和v c - n v x 。 2 ) o n 4 业务，支持g 7 0 9 定义的o t n 连接颗粒0 d u k 和o d u k - n _ v x 。 3 ) 透明或不透明的光波长业务。 4 ) 1 0 m b s 、l o o m b s 、1 g b s 和1 0 g b s 的以太网业务。 5 1 基于光纤连接( f i c o n ) 、企业系统连接( e s c o n ) 和光纤通道( f c ) 的存储 域网络( s a n ) 业务。 北京邮电大学硕士学位论文第1 章光网络业务模型分析 智能光网络对新业务类型具有可扩展性，可以支持多种类型的业务模型，每种业务 模型都有自身的业务属性、目标市场和业务管理需求 5 】。 为了支持增强型业务( 如按需带宽分配，多样性电路指配和捆绑连接等) ，智能光 网络应支持呼口q 和连接控制的分离。呼叫和连接控制的分离可以减少中间连接控制节点 过多的呼叫控制信息，去掉解码和解释消息的沉重负担。智能光网络支持的连接拓扑类 型包括：双向点到点连接、单向点到点连接和单向点到多点连接。 由于呼叫和连接分离，一个呼叫可以对应多个连接，目前双向点到点连接是最主要 连接方式。智能光网络支持3 种业务网络连接类型：永久连接( p c ) 、交换连接( s c ) 、 软永久连接( s p c ) 。p c 和s p c 连接都是由管理平面发起的对连接的管理。p c 和s p c 的区别在于光网络内建立连接是利用网管命令还是实时信令，这两种方式都是由运营商 发起建立的业务连接。s c 连接通过u n i 信令接口发起，用户的业务请求通过控制平面 ( 包括信令代理) 的u 】发送给运营商，即由用户直接发起建立业务连接。 目前的传输网不能按照服务等级制定相应的资费政策，造成资源配置的浪费，而智 能网络可以方便地对业务电路的优先级进行划分，从而提供有服务品质协议( s l a ) 的 传输业务电路。客户对不同连接的可靠性有不同的要求，这些要求可以采用“业务等 级”来表述。在智能网络中，业务等级主要是通过映射到不同恢复、保护选项和相关 连接的优先级来实现的，例如建立优先级，保持优先级( 是否可以预空闲) ，恢复优先 级。 建立优先级主要是指业务的建立响应时间，分别为在天、小时或分钟内建立业务连 接。保持优先级( 是否可以预空闲) 主要是指在出现其他系统故障时系统是否会被空闲 出来承载更重要的业务，业务连接本身有没有保护。恢复优先级则是考虑系统出现故障 时的恢复时间和恢复等级( 如恢复业务百分比) 。 将单个业务等级映射到一系列保护、恢复选项，每个运营商有着不同的选择。控制 层面支持基于每个连接链路优先级的设定，并支持将带宽资源预留作为恢复目的和失效 修复后路由归一化。一般支持如下业务连接等级：专用连接( 1 + 1 和l ：1 ) ；共享保护 ( 1 ：n 和m ：n ) ；不保护( 在主用电路上传送) ；不保护业务( 在保护电路上传送) 。 从安全角度，网络资源应该避免没有授权的接入，业务接入控制就是限制和控制实 体企图接入到网络资源的机制，特别是通过u n i 和外部网络节点接口( e 删) 。连接 接纳控制( c a c ) 功能应支持以下安全特征： 1 ) c a c 适用于所有通过u n i ( 或者e n n i ) 接入到网络资源的实体。 2 ) c a c 包括实体认证功能，以防止冒充者通过假装另一个实体欺骗性地使用网络 资源。已经认证了的实体将根据可配置的策略管理被赋予一个业务接入等级。 3 ) u n i 和网络节点接口n n i 上应提供机制来保证客户认证和链路信息完整性，如 链路建立、拆除和信令信息，以用来连接管理和防止业务入侵。l n 虹和e - n n i 北京邮电大学硕士学位论文 第1 章光网络业务模型分析 还应包括基于c a c 的应用计费信息，防止连接管理信息的伪造。 4 ) 每个实体可以通过运营者管理策略的授权利用网络资源。 1 2 4 智能光网新业务实例模型 目前运营商网络大多只支持p c 专线永久连接，但是智能光网络可以提供更加丰富 的业务模型，如加强型专线业务( p b s ) 按需带宽业务( b d s ) 和光虚拟专网( 0 v p n ) 业务模型。每个运营商都可以根据其商业策略和环境定义自己的业务模型。 1 加强型专线业务 加强型专线业务模型提供增强的租用线专线业务，此业务是由p c 或s p c 的业务 管理接口( m i ) 指配的。这种指配可以是实时的或近实时的。它具有以下特性： 1 1 连接请求需要经过管理接口。 2 1 客户和光网络之间是客户服务的关系。 3 1 光网络对客户是不可见的，光连接的建立依赖于网络智能。 智能光网络网管平面与控制平面配合实现s p c ，s p c 可以快速提供业务。客户只需 要告诉运营者在哪个地方需要什么样的业务，运营商就会通过网管平面和控制平面近乎 实时地建立符合用户需求的业务连接，而且可以迅速改变业务的属性( 在用户到运营 商的线路满足条件的情况下) 。 2 按需带宽业务 按需带宽业务模型通过u n i 信令接口提供按需分配带宽的自动连接，连接指配是 实时的，使用s c 光连接。它具有以下特性： 1 ) 用户或其代理可以直接通过u n i 发起连接请求。 2 ) 根据所使用的互连模式和网络管理策略不同，光网络对客户可以不具有或者具 有有限的可见性。 3 ) 根据控制平面互连模型的不同，连接依赖于网络或客户智能。 在u n i 发起业务建立时，传送网可以按要求建立和删除业务连接。客户设备必须 具有从用户网络接口网络侧( u n i n ) 获得传送网业务信息的业务发现能力。在连接建 立过程中，必须确定业务属性信息。属性包括：成帧方式、信号类型、透明方式、级联 方式等。通过u n i 包括用户在u 岍上请求业务的模式有直接请求和间接请求两种。对 直接请求模式而言，用户网络接口客户侧( u n i c ) 功能在客户设备中实现，客户端可 以直接请求传送网业务。而对间接模式来说，u n i c 独立于客户设备，代表一个或多个 客户执行u n i 功能( 如图l 一3 所示) 。 北京邮电大学硕士学位论文 第1 章光网络业务模型分析 i s i ：网内互联接口 u n i ：用户网络接口 。r u n i 犁小、 厂 s i i l u n 卜n 1 _ j 厣七# 、厂 l 自动邻居发现传送网元 ( a ) 直接请求方式 ( b ) 间接请求方式 图1 3 直接请求方式和间接请求方式 b d s 实现了真正的按需分配带宽。可以根据用户动态提出的连接申请配置连接， 真正实现智能化。智能光网络在对用户进行适当的呼叫控制( 例如一定的认证和鉴权机 制) 后，对客户开放核心网络中的连接服务和地址编码。 3 光虚拟专用网 随着电信市场的放开= 租用电路和网络资源越来越普遍，网络运营者可以将一些网 络资源及其许可权力分配给客户，这一部分网络资源构成虚拟专用网( v p n ) ，如何对 客户租用的波长或通道进行有效管理就成了人们关心的问题。o ) n 模型在光层为特定 的用户组提供虚拟专用网业务。它具有以下特性： 1 ) 客户签约特定的网络资源( 如光连接端口、波长等) 。 2 ) 像v p n 一样，支持封闭用户组( c u g ) 概念。 3 ) 根据指配模式的不同，光连接可以是p c 、s p c 或s c 。 4 ) 一个0 v p n 站点可以请求动态重新配置其在同一封闭用户组c u g 内的站点之 间的连接。 5 ) 在客户业务合同允许的范围内，客户具有对网络资源的可见性和控制能力。 可以将传送网划分为多个v p n ，但每一部分网络资源只能属于一个v p n ，虚拟专 用网的用户终端可以根据网络的授权对相应的资源直接进行管理。 1 3r l w a 算法巾的常用业务模型 随着智能光网络的引入，传送网所支持的业务类型愈加丰富。业务种类的划分方法 有很多，这里主要针对r w a 算法的特点归类和建立业务模型。在以往的研究中，通常 将业务分为静态业务( 采用静态r w a 算法) 和动态业务( 采用动态r 鼢算法) 两种。 针对光网络中某些业务( 如o v p n ) 流量持续时段的周期重复特性提出了一种周期性可 预测业务模型，它不同于传统的静态，动态业务，这类业务的研究焦点集中于它们的时 间相关性与资源复用性。 北京邮电大学硕士学位论文 第l 章光网络业务模型分析 1 3 1 静态业务流模型 静态业务流是指所有节点对之间的连接请求是预先给定，且在相当一段时间内不会 有所变化的( 包括连接请求的源目节点和业务量) 。当为所有连接请求分配好带宽资源 之后，连接将保持不变，此时网络既不会建立新的连接，也不会拆除己建好的连接。 在网络的中长期规划时，要解决的就是静态业务流的路由与波长分配问题。业务一 般以节点之间的连接请求容量表示( 电路资源容量) 。此时r 、a 算法的目标是实现网 络资源配置的最优化。通常问题分为两类，一类是用最少的网络资源满足全部静态业务 流量请求，而另一类则是利用有限的网络资源尽可能多的实现业务需求。本质上讲这两 类问题是相同的，都是最优化问题，加之规划通常为离线进行，实时性要求不高，静态 r w a 问题往往采用传统的最优化算法予以解决。在第二章中，将结合传统的优化算法， 给出静态r j w - a 问题的解决方案。 在以往的研究中，节点设备通常为光层上的o a d m 和电层上的a d m 、s d h ，规 划问要解决的是链路资源总量和节点端口配置问题。随着智能光网络的引入，网络部分 的配置了a s o n 节点，这种依靠信令的灵活资源调度和保护能力，使得路由算法大大 区别于传统电路资源规划配置时所采用的静态r w a 算法。此外，传统光网络向智能光 网络的过渡也成为运营商在规划建设期急需解决的问题。在第四章，将会结合规划实例 具体阐述如何在现有传送网基础上引入部分a s o n 节点，并就此进行a s o n 建网经济 性分析。 1 3 2 动态业务流模型 动态业务流量是指节点对之间的连接请求不是预先给定的，而是随着时间变化动态 到来的，当连接建立好并保持一段时间后又会被拆除。这类业务的实时性要求较高，目 标是为连接请求进行快速的资源配置，并通过合理的路由策略尽量降低网络阻塞率。对 动态业务流而言，由于新的连接不断被接纳，而目前有效的连接不断被释放，网络的状 态在时间上也是动态变化的。因而，我们无法对整个观察时间内的路由波长配置进行全 局的优化。同时考虑到实时性限制，通常要求算法简单高效。通常采用分解法解决动态 刖队问题，即先路由再分波，路由时一般采用最短径算法d i j k s t r a 。值得注意的是，在 不同的优化目标下，最短径算法的权重设置有很大差别，而这些不同的权重设计方案正 是我们研究动态r 、a 问题的关键所在。 常用的动态业务流模型包括泊松业务模型和自相似业务模型两种。 1 泊松分布模型 2 自相似业务模型 自上世纪九十年代以来，大量的网络实际测量与分析证明，真实的网络业务具有统 计上的自相似性业务流的特性，它们的间隔时间是服从重尾衰减的，随机过程的功率谱 北京邮电大学硕士学位论文第l 章光网络业务模型分析 在原点是发散的。而且，不论网络的拓扑结构、用户数量、服务和利用类型如何变化， 这种自相似性始终存在。 自相似随机过程是一个具有长相关性的随机过程，这种特性体现在在不同时间单位 的聚集或不同业务数目聚集的情况下，随机过程仍然不能消除其突发性。这种特性是同 以p o 沁。玎过程为代表的短相关过程大相径庭的，p d 沁d ”过程在经过多个时间尺度或者 多个复用数目的聚集之后总是可以极大地削减其突发性。 对自相似业务量的建模目前仍然是研究的热点和难点问题所在，迄今为止人们还没 有提出一个既有明确的物理含义且易于理论分析和推导的模型。在多种建模方法中，利 用o n o f f 过程合成自相似业务是当前建模研究的一个方向【”，在我们的研究中，采用 o n o f f 模型来进行自相似业务的建模。 1 3 3 周期性可预测业务模型 随着光网络设备的不断成熟，网络结构标准化的日益深入，光虚拟专网( 0 v p n ) 得到了广泛的应用。对租用带宽的用户者来说，这种需求常常具有时段性和周期性。图 1 4 和图1 5 所示为美国“a b i l e n c 骨干网”丹佛州堪萨斯州段的单日各时刻的业务量 状态以及一周内的业务量状态嘲。 图l - 4 a ：一日业务量状态 图l - 4 b ：一周业务量状态 上面两图中，该链路段上一天的业务量分布出现了明显的高、低峰时间段划分，而 一周内每日的业务量总体趋势却极为相似( 周六、日除外) 。这种明显的时段性和周期 性完全不同于传统的静态动态业务，因此我们将这类业务划分为一个新的类别可 预测的业务。对这类业务，若能够按照高低时间段分别进行带宽配置，则可大大提高资 源利用率。 由于可预测业务在时间特性上更倾向于传统的静态业务，因此仍可采用静态r w a 算法解决这类问题。不同的是，这种突出的流量周期特性是这类问题的研究重点，算法 要能够解决资源的波长域与时间域共享问题。在第二章中，本文将结合传统的优化算法 对这类业务模型下的r 、a 问题予以详述。 北京邮电大学硕士学位论文第l 章光网络业务模型分析 1 4 本论文的主要工作 本人在攻读硕士学位期间，参加了以下项目： 国家自然科学基金重大项目“下一代光网络中联合路由与生存性机制的研究”； 国家8 6 3 计划“多粒度光交换技术与系统应用”，研究多粒度路由算法； 中国联通技术部北邮光通信中心联合合作项目“a s o n 建网经济性分析”； 信息产业部电信规划院横向合作项目“w d m 网络规划和优化软件”。 依托以上项目的资助，本文以智能光网络的r w a 算法为研究对象，详细分析了智 能光网络的业务模型，以及基于该业务模型下r w a 算法的相关问题。本文提出了一种 不同于以往传统的动态静态r 、 强业务的周期性可预测业务模型，该模型是基于智能光 网络的o v p n 业务所提出的，研究的重点在于实现资源的波长域与时间域的共享。 本人在攻读硕士学位期间，对传统优化理论和优化算法进行了大量的研究工作，并 将这些算法与静态r w a 问题相结合，设计了相应的路由解决方案。此外，本人对i p o v e r w d m 多层联合路由和联合生存性问题也进行了大量的研究，设计出基于多种生存性策 略的路由算法，本文的第二章和第三章对这些算法进行了详细的阐述和仿真说明。 在第四章中，结合这几年所参与的网络规划项目所获得的经验，总结了光网络规划 问题的一般性方法。文章最后针对智能光网络问题，简要分析了从现有s d 矿d m 传 送网络向a s o n 光网络过渡的规划流程。 参考文献 【1 】商哲民，“业务驱动的电信网”，电信网技术，2 0 0 2 年1 2 月第6 期。 【2 】a k j a i n ，“i n t e l l i g e n c ei 1 1o p t i c a ln e 铆o r k s ”，i e 髓c o m m l l i l i c a t i o n sm a g a z 妣，v 0 1 3 9 ，p p 6 9 7 0 ，s e p 2 0 0 1 3 i t u tr e c g 8 0 8 0 y 1 3 0 4 ，“a r c h i t e c t u r eo ft h ea u t o m a t i c a l l ys 丽t c h e d0 p t i c a l n e t w o r k ( a s o n ) - a m e n d m e n tl ，”2 0 0 3 【4 】s s e n g u p t a ，vk u m 甄d s a h a ，“s 、v i t c h e do p t i c a ib a c k b o n ef o rc o s t e 髓c t i v es c a i a b i e c o r ei pn e t w o r k s ，”i e e ec o 1 m u m c a t i o n sm a g a z i 工1 e ，v o l u m e4 1 ，i s s u e6 ，p p 6 0 一 7 0 j u n e2 0 0 3 【5 张成良，“自动交换光网络业务”，中兴通讯技术，2 0 0 3 年第5 期。 6 】j o s u k u r i ，n i c o i a sp u e c h ，m a u r i c eg a g n a i r e ，e m m a n u e ld o t a r o ，r i c h a r dd o u v i l l e “r o u t i n ga n dw a v e l e n g t ha s s i g i l m e n to fs c h e d u l e dl i g h t p a md e m a l l d s ” m e e j o u r n a i v o l 2 1 ，n o 8 ，o c t o b e r2 0 0 3 7 l ac o r t e ，a ，l o m b a r d o ，“m o d e l i n gs u p e 叩o s i t i o no fo n 0 f fc o r r e l a t e dt r a m cs o u r c e s i nm u l t i m e d i aa p p l i c a t i o n s ，”p r o c e e d i n g so ni e e ef o u r t e e n t ha n n u a lj o i n tc o n f e r e n c e o f 也ei e e ec o m p u t e ra n dc o m m u n j c a t i o n ss o c i e t i e s p p 9 9 3 1 0 0 0 ，2 - 6a p r i l1 9 9 5 北京邮电大学硕士学位论文第2 章传统优化算法与静态r ，a 问题 第2 章传统优化算法与静态r w a 问题 2 1 静态r w a 问题描述 在w d m 光传送网络中，r 仉a 问题主要实现在有光通路建立请求时，计算如何在 网络的物理层中选择一条从业务源节点到目的节点的路由，并为路由经过的光纤链路分 配波长。这意味着不但要发现一个光纤通道( 路由r o u t i n g ) 而且还要寻找一个可用的 波长( 波长分配w a v e l e n g m a s s i g m e n t s ) 。对于静态业务，就是要在已知网络的物理拓 扑连接情况和节点设备配置状态的条件下，或是在逻辑连接已确定的前提下，对一组预 先已知的、需要建立的光通道选择路由并分配波长，其实质是通过使用各种各样的成本 函数来对网络资源进行的扰化问题。众所周知，r w a 问题是一种n p 完备问题r 1 】，若统 筹解决难度较大，尤其当网络规模较大时，问题更加突出。因而，一般将r w a 问题分 为路由问题和波长分配问题两个子问题来分别研究，其中每一个子问题又是一种n p 完备问题，且二者密切相关。在解决静态r 1 讯，a 问题时，常见的有两种方式： 1 ) 结合法 将路由选择和波长分配同时加以考虑，在解决路由选择问题的同时波长分配问题也 得到了解决。这些研究或者将其归结为整数线性规划( i l p ) 问题【2 】，或者依赖启发式 算法以最小化需要的波长数为目标建立给定光路集合。由于i l p 问题是n p 完备问题， 计算比较复杂，因此只适用于小规模网络，对大规模网络，必须采用启发式算法1 3 1 。结 合法资源优化效果较好，但在解决大型网络问题时耗费时间较长，算法本身的复杂度也 较高。 2 ) 分离法 这类算法将路由选择和波长分配两个子问题分别予以处理，一般是先解决路由选择 子问题，再解决波长分配子问题。虽然这种分离方法所获得的路由结果一般不会满足绝 对的全局最优化目标，但它易于实现而且也能满足一般工程要求。 2 2 优化策略与算法 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。网络优 化是运筹学( o p e r a t i 。1 1 sr e s e a r c h ) 中的一个经典和重要的分支，所研究的问题涉及经 济管理、后勤管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术、 控制论及军事运筹学等诸多领域州。由于静态r 、a 问题本质上是一类限制条件下的最 优化问题，因而可采用各种传统的优化算法予以解决。值得注意的是，在对算法进行数 北京邮电大学硕士学位论文第2 章传统优化算法与静态r w a 问题 学建模时，比须要考虑到r w a 问题的实际物理意义。通常，我们希望优化解就是为某 一业务需求所指定的一条物理路由，此时，该优化解必须能够完整而连续的反映路由的 连接情况，且要满足网络中实际物理连接状态与可用波长资源情况等限制。 优化算法种类很多，以下将主要针对现有传输网规划时( 解决静态r 、a 问题) 的 优化问题提出一些常用的建模技术和优化算法。 2 2 1 优化问题建模 在单层或多层网络中，大多数的优化问题都可以用线性或非线性的数学公式进行描 述。由于问题的内在本质和其所涉及的知识领域不同，问题的公式化方式也会有所区别， 因而我们无法对所有优化问题给出通用的建模标准。此外，这种公式法中的大多数问题 较为复杂，目前甚至是近期内都无法找到最优解，因而常常考虑在建模时尽量使问题简 化，且避免对问题寻找全局最优解。实际中，常常采用启发式或贪婪算法求解，当让这 类算法会使最终解产生误差，但只要这种误差在工程上可以接受就可以了。 优化问题建模的方法与算法的选择受到问题本身条件的限制，要考虑的因素包括： 变量的类型( 二进制、整型、实数等) 和数量；限制( 线性或非线性) 的种类和数量； 开销函数的类型( 线性或非线性) 。传统网络规划与优化问题中常用的模型包括用以解 决多商品流问题的流量方程、路径流方程和路径方程等。 1 流量方程 电信网的优化问题常常用多商品流模型来描述，公式如下： 磐，f ( y ) + g ) = 丘( 儿) + 。( x 。) 式( 2 1 ) ” ee d 其中： t d = rl 业务流d 正向经过边8 o业务流d 不经过边p l 一1 业务流d 反向经过边e 式( 2 2 ) 对所有边e ： 儿= ； 式( 2 3 ) d 对所有节点玎和所有连接请求d ： 口。x 。= c 。 式( 2 4 ) 对连接请求d 来说，c 。表示节点h 的流量需求，对源节点该项为负值，对目的节 点该项为正值。口。是节点对的概率矩阵。 方程正( 石) 和g 。( z ) 分别描述了网络本身边e 的开销和业务流在d 边e 上所产生的 开销。通常假定开销方程为六( o ) = g “( o ) = o ，五是单调非递减的，g d 在x o 时是单 调非递减、上凸对称的，即g 。( 一z ) = 占。( x ) 。 北京邮电大学硕士学位论文第2 章传统优化算法与静态r w a 问题 公式2 1 适用于无向网络，但如果通过开销方程中的g 。抑制掉反向业务流，该方 程就可以用以解决有向网络问题了。因此我们可以将一个标准状态的节点分解为一个入 口节点和一个出口节点，并用一个有向弧连接始末节点。对这个节点的业务流，该有向 弧应用了一个呈中凸分布的开销函数譬。同样的，每个边也可以分解成两条相反方向的 弧，每条弧都是从一个端节点的出口指向另一端节点的入口。最短增广径算法【5 】就常将 一个边分解成两个有向弧，若网络中有1 个节点和2 i e i 条边，此时实际处理的将会 是2 l 1 个顶点和2 五f + f i 条弧。 有一个问题就是最短径算法可能会遇到逆向环，一个解决方法是引入一个二元变量 节点位势w 。，为每一个需求哦的流量提供一个局部判别标准。将边e 的终节点记 为n 。、起始节点记为”。一，并且有： x 毗= ，y 。= m ，_ y 。= k j + m 式( 2 5 ) 若考虑所有边e ，流量要在l 占i 范围内进行修正，占可正也可负。此时需求玩的流 量是优化的。 六( y 。) + g 。如( x 。山) 一五( y 。) 一0 。如( z 。如) 占( m ，一w 。一。) 式( 2 6 ) 商品流公式也适用于给定的业务流有多条疏导路径的情况，一个典型的例子就是， 在两个网关间建立两个或多个完全不相关的路径；此时，可以通过流量增广路径算法得 以实现，但该算法仅适用于，为线性开销方程的情况。如果正是呈下凹形分布的，我 们可以在解空间边缘上得到一些改善的结果。令为一个可行解，工为线性方程， 工( ) = f ( ) ，对所有可行解集合x x 来说三( x ) f ( x ) 。如果我们为目标方程+ g 重 新优化部分或全部独立的业务流时，所得到的结果会好于前者。如果开销方程中疋既 非线性也非下凹分布时，用流量增广算法实现边缘上的改进就存在一些问题。该算法不 断扩大优化流量的范围，因此不适合现存流量有变化的情况。 2 路径流方程 在这种模型中，为每一个连接请求预先确定一组可用路径。主要变量是每条路径上 的流量( 非负) 。该模型主要用于研究不必考虑可靠性的网络设计问题。 一个典型的例子【6 】是一种用于解决传输网短期规划问题的模型，它包含了各种限制 条件以充分考虑各边的故障可能产生的影响。为限制问题规模的大小，采用了一种混合 的整线性规划的方法，即纵向改进、横向改进和有序的线性规划相结合。若函数疋和g 。 都是都呈中凸状分布且分段线性，这种方法也可应用到流量方程之中。 预先确定的备选路由集将直接决定结果的好坏。可以肯定的是，在一个结构待优化 的网络中寻找一系列较好的路径将比在一个现存网络中寻找要困难得多。 3 路径方程 路径流方程以流量规模为变量，路径是预先确定的，而在路径方程中，流