（计算机应用技术专业论文）现代通信网络中的带宽分配.pdf

硕士学位论文 摘要 作为一个连接大量计算机和信息的正在快速成长的巨型公用网络，英特网正 在改变我们学习，购物，共享文化成果，甚至我们与朋友和家人联络的方式。然 而，在现代通信网络中，为了有效地利用宝贵的带宽资源，预先配置大小的静态 分配算法已经不能适应快速发展的通信需要。根据流量变化的动态带宽分配算法 成为现在的研究重点。 在传统的a t m 网络巾，使用最为广泛的动态分配带宽的最优算法是二分法。 新近提出的步进式最优算法在时间上具有更大的优势。然而，步进式算法中用来 计算虚路径上的呼叫损失率的k a u f m a n 迭代公式非常的耗时。动态分配带宽的时 间很多都消耗在了计算呼叫损失率上。本文中，一种快速的基于准独立近似的计 算呼叫损失率的公式被推广到了资源非完全共享的情况，以替代k a u f m a n 公式。 同时，对步进式算法中的一步：对全网中呼叫损失率最小的虚路径做带宽减一操 作，本文解释了这个步骤的不合理性。然后，修j f 为：对全网中受限链路中的具 有最小呼叫损失率的虚路径做减一操作。仿真结果显示，以【二两个改进都进一步 提高了步进式算法的速度。另外，在参考文献中，有一个较复杂的证明步进式算 法最优性的数学证明。本文中，给出了一个更为简单的证明步进算法最优性的推 导。 在对步进式算法的分析过程中，引 ；了这样一个问题：对两条虚路径增减相 同的带宽，会不会改变它们呼叫损失率的大小关系。本文中推导证明了这个问题， 仿真也得出了相同的结论。 m p l s 是一种新出现的综合i p 和a t m 功能的网络结构。在m p l s 中，为了保 障费用昂贵的额外付费服务，如视频和语音的传输，出现了一种叫做“管道”的 概念。一种基于门限的“管道”带宽分配的预测动态算法能对管道带宽资源做简 单的管理。新近出现的基于定时器的算法能有效的解决业务流突发性强的问题， 提高链路资源的利用率。然而，这两种算法都有其局限性。本文中利用更为灵活 的定时装置，提出了一种改进的算法。仿真结果显示，改进的算法进一步地提高 了域内管道和域间管道的带宽资源利用率和降低流量损失率。 关键词：呼叫损失率；准独立；虚路径带宽分配；多协议标记交换；管道 现代通信网络中的带宽分配 a b s t r a c t t h ei n t e m e t ，w h i c hi sah u g ea n dg r o w i n gp u b l i cn e t w o r ko f1 i n k e dc o m p u t e r s a n di n f b r m a t i o n ，i s c h a n g i n g t h ew a yw es t u d y s h o p ，s h a r e o u rc u l t u r ea n d c o m m u n i c a t ew i t ho u rf r i e n d sa n d i l y h o w e v e r ，i nm o d e r nc o m m u n i c a t i o n s n e t w o r k ，i no r d e rt ou t i l i z ep r e c i o u sb a n d w i d t hr e s o u r c ee m c i e n t l y ，s t a t i ca l l o c a t i o n p o l i c i e s ，w h i c hu s u a l l vd i s t r i b u t eb a n 出i d t hi na d v a n c e ，c a nn o tm e e tt h ed e m a n do f f a s t g r o w i n gc o m m u n i c a t i o n s d y n a m i ca l l o c a t i o np o l i c i e s ， w h i c ha r eb a s e do n f l u c t u a t i o n si nt r a m c h a v en o wb e c o m et h ef b c u so fr e s e a r c h e s i nt r a d i t i o n a la t mn e t w o r k s ，t h em o s tw i d e l yu s e dd y n a m i cb a n d w i d t ha 1 i o c a t i o n a l g o “t h mi sk n o w na s “b i s e c t i o na l g o r i t i l m ”an e w l yp r e s e n t e d “s t e pa l g o r i t h m ” p o s s e s s e si t sa d v a n t a g ei na l l o c a t i o nt i m eo v e rt h ep r e v i o u so n e h o w e v e r r e c u r r e n t k a u t m a nf o r m u l au s e dt oc o m p u t ec a l lb l o c k i n gp r o b a b i l i t i e s ( c b p s ) o fv i r t u a lp a t h s i n “s t e pa l g o r i t h m i st i m e c o n s u m i n g a i t e m a t i v e 】y ，t o om u c ht i m ei nd y n a m i c a 1 1 0 c a t i o nj s s p e n to nc o m p u t i n gc a l lb l o c k i n gp r o b a b i l i t i e s i n t h i sp a p e r ，af a s t a p p r o x i m a t ea l g o “t h m ，w h i c hi sb a s e do nq u a s i i n d e p e n d e n ta n du s e dt oc o m p u t e c b p si sg e n e r a l i z e dt ot h ec a s eo fp r e s e r v i n gb a n d w i d t ht or e p l a c ek a u f h l a nf b r m u l a a l s o ，o n es t e pi n “s t e pa l g o r i t h m ”，w h i c ht a k e so f ro n eu n i to fb a n d w i d t ha w a yf r o m t h ev i r t u a lp a t hw i t hl o w e s tc b pi nm ew h o l en e t w o r k ，i se x p l a i n e dt ob ei m m o d e r a t e a n d “i sa m e n d e dt ob ea ss u b t r a c t i n go n eu n i tf o mt h ev i r t u a lp a t hw i t h1 0 w e s tc b p i nc o n s t r a i n e dl i n k s s i m u l a t i o nr e s u l t si n d i c a t et h a tt h es p e e do f “s t e pa l g o r i t h m i s g r e a t l yi n c r e a s e dw h i c hb e n e n t sf r o mt h et w om o d i f i c a t j o n s i na d d i t i o n ，i nr e f e r e n c e d o c u m e n t ，am a t h e m a t i cj u s t 讯c a t i o nv e r i f y i n gt h eo p t i m a l i t yo f “s t e pa l g o r i t h m ”i s p r o p o s e d ，h o w e v e r ，i ts e e m sab i tc o m p l e x i nt h i sd i s s e r t a t i o n ，as i m p l ed e d u c t i o ni s g i v e n ，w h i c hv e r i f i e st h eo p t i m a l i t yo f “s t e pa l g o r i t h m ” t h ep r o c e s so fa n a l y z i n g “s t e pa l g o r i t h m ”g i v e su sf o o df b rt h o u g h t t h a ti s ， w h e t h e re q u a li n c r e a s eo rd e c r e a s ei nt h eb a n d w i d t ho ft w ov i r t u a lp a t h sw i l lr e s u l ti n r e a r r a n g e m e n to ft h es e q u e n c eo fc b p so ft h e s et w o i nt h i sp a p e r ，ac o n c l u s i o ni s d r a w nb yr e a s o n i n ga n da l s oc o n n r m e db ys i m u l a t i o n m p l si san e w l y - e m e r g i n gn e t w o r ka b s o r b i n gm e r i t sb o t hf r o mi pn e t w o r ka n d a ，r mn e t w o r k f o rt h ep u r p o s eo fg u a r a n t e e i n ga n e x p e n s i v es o c a l l e d p r e m i u m s e r v i c e ”w h i c hi su s u a l l yu s e db yv o i c ea n dv i d e ot r a n s m i s s i o n ，an e wc o n c e p t i o n k n o w na s “p i p e ”i sb r o u g h tf o r w a r d a tt h es a m et i m e ，at h r e s h o l d _ b a s e dp r e d i c t i o n 硕士学位论文 a l g or i t h mi sp r o p o s e dt oa d m i n i s t r a t eb a n d w i d t ho f “p i p e ”i nas i m p l ew a y l a t e ro n ，a n e wa l g o r i t h mb a s e do nt i m e ri sp r e s e n t e d ，w h i c hp r o v e st ob ee f n c i e n ti nd e a l i n g w i t hp a r o x y s m a lt r a f t c ，r a i s i n gb a n d w i d t hu t i l i z a t i o nr a t i o h o w e v e r ，e a c ho ft h e s e t w oa l g o r i t h m sh a si t sw e a k n e s s i nt h i s p a p e r ，b a s e do nm o r en e x i b l et i m e r ，a n i m p m v e da l g o “t h mi sp u cf o r w a r d ，w h i c hi sc a p a b l eo ff u r t h e ri n c r e a s i n gb a n d w i d t h u t i l i z a t i o nr a t i oa n dd e c r e a s i n gt h el o s so ft r a j cb o t hi n p i p ew i t h i nd o m a j na n d b e t w e e nd o m a j n s k e yw o r d s ：c b p ；q u a s i i n d e p e n d e n c ；b a n d w i d t ha l l o c a t i o no fv i r t u a lp a t h ；m p l s “p e 现代通信网络中的带宽分配 图l 二分法流程图 图2 步进式算法流程图 图3 测试网络结构图 图4 截断处理示意图 图5 占用服务员数的概率 图6 带m p l s 功能的网络模搿 图7 区分服务域中的管道 图8 跨越域问的管道 图9 仿真拓扑图 图1 0 管道中的延时和抖动 图1 1 门限预测 插图索弓 j v 1 0 1 1 1 2 1 9 2 3 3 5 3 8 3 9 4 l 4 2 4 5 硕士学位论文 附表索引 表1 链路容量1 3 表2 算法性能对比1 4 表3 步进算法平均运行时间1 4 表4 各算例的输入数据及运行时间统计2 2 表5 分割优化过程中采用两种不同算法所得到真正最坏c b p 值的比较2 4 表6 新的链路容量2 5 表7 采用不同计算c b p 公式的运行结果2 5 表88 次计算的平均时间2 6 表9 应用k a u f m a n 公式的改进前后对比2 7 表1 0 应用k a u f m a n 公式的改进前后8 次运算对比一2 7 表1 1 应用快速计算公式的改进前后对比2 8 表1 2 应用快速计算公式的改进前后8 次运算对比2 8 表1 3 呼叫损失率对比表，3 l 表1 4 域内管道。4 7 表1 5 域间管道4 7 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：责r 1 晚帆日期：2 。- 6 年年月； = | 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位沧文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以匕相应方框内打“”) 作者签名： 导师签名： 童1 魄帆 凿吐叶 日期：2 。6 年年月弓曰 日期：一，绰月曰 硕士学位论文 1 1 研究背景 第1 章绪论 随着i n t e m e t 的发展，人们进入了网络时代。在这个信息时代中，大量的数 据、图像、视频都在网络上传输。其发展的速度远远超过网络带宽增加的速度。 并且，由于公用网络上的用户业务数据流量具有随机性与突发性，如何使各种业 务都尽量得到令顾客满意的服务是网络管理的一个根本任务。网络管理的一个重 要内容是资源分配，带宽资源是其中极其重要的一种资源。因而，合理分配带宽 资源成为现在研究的热点之一。早期的带宽分配策略都是静态的，即，带宽的大 小都是预先设置好的。显然这已经不能满足数据流量具有随机性与突发性的现实 情况。现在的研究都着眼于动态的分配带宽大小。构造更好的动态带宽分配算法 是人们努力的目标。 1 2 研究意义 随着i n t e m e t 的飞速发展，网上信息与日俱增，一方面信息急剧膨胀，而另一 方面由于带宽限制，用户不能及时得到所需的信息。为了让各种信息和数据合理 地在网络上传输，人们应该采取措施对网络的带宽资源进行合理分配。带宽分配 算法能够达到这个目标。 带宽分配算法通常分为两类：一类是传统的带宽策略，仅仅是基于繁忙时段 点到点的通信量( 设计通信量) 来对网络进行预先的设计( 设计带宽) ，以满足给 定的服务级别的要求。另外一类是动态地适应通信量的变化的动态带宽分配算法。 a t m 网络中，最常用的是二分算法。新近出现的步近式算法相比二分法在分配时 间上具有优势。然而该算法仍然存在着一些不足，限制了带宽分配速度的提高。 再m p l s 网络中，有一种特殊的专为额外付费用服务设计的“管道”，已有的对 “管道”带宽分配的算法各有其优点，但仍然存在一些不足。因而，有必要提出 一种更好的动态分配算法以提高费用昂贵的“管道”资源的利用率。 现代通信网络中的带宽分配 1 1 3 研究进展 a t m 网络中，遗传算法由于其广泛的适用性，在虚路径带宽分配中也有使用，但 因为其是在概率意义下的全局搜索，所以其收敛性及运行时间并不理想。有人对一 个7 个节点( 4 2 个有向点对) 的网络采用遗传算法进行虚路径带宽分配，其运行时间 超过了l o 小时。 希腊学者l o g o t h e t i s 博士与他的同事提出了一种将大规模网络带宽分配过程分 为3 个阶段的方法，其步骤是：在分解阶段把整个网络分为若干个小型子网：在分散 优化阶段对第一阶段分割成的各个子网进行内部带宽分配及优化：合并优化阶段 利用前2 个阶段优化分配的结果，逐渐将相邻子网进行合并及对合并后形成的新子 网内尚未分配带宽的端一端对进行虚通路带宽优化分配。 l 。g o t h e t i s 博士同时提出了一种集中式的虚路径带宽分配算法和一种基于测量 的中期集中式的虚路径带宽控制算法。虽然能够很好地做中长期的带宽分配，但 和分割法一样不能很好地适应流量的快速变化。 学者m e d h id 提出了一种多时、多业务流级别的虚路径动态带宽配置策略。 虽然考虑到了多服务级别的情况，但仍不能很好地解决流量实时快速变化的问题。 只能称为一种中长期的分配方法。 二分法是目前使用较多的一种动态带宽分配的最优算法。算法首先由起始的最 大及最小的呼叫损失率的估计值日和e ，开始，通常被分别设为1 和o 。求出上下 限的中间值e ，根据e 及各点对间通信量求出网络中各点对所需要的最小带宽， 然后在此基础上，将带宽分配到各点对间的虚路径上。这里，目标函数是最大化 所有虚路径带宽的和，所受限制条件为：( 1 ) 通过各个链路的虚路径带宽和不能 超过链路容量；( 2 ) 同一点对间的各条虚路径带宽之和不能低于所需最小带宽； ( 3 ) 各虚路径带宽必须大于等于零。此优化过程为一线性优化问题，一般可用割 平面法f 5 】来实现。在本文单虚路径的情况下，点对间带宽即为虚路径带宽，优化 过程只需要将多余带宽分配给容量未超限的链路。如果优化成功，则算法将e 值 赋予e 。，否则赋给日。这一过程不断重复从而不断产生新的估计呼损率e ，当 呼损率上下限之间的差值小于给定的一个小的正实数e 时，程序停止，占的大小 代表了程序搜索解所能够达到的精度。二分法的实质是将非线性的优化问题转化 为线性优化问题，然后用经典的线性规划方法来对转化后的线性问题求解。但是， 二分法存在运算时间长等缺点 新近提出的步近式算法主要特点是每次对虚路径的重新分配，都是对某条虚路 径增加或减少一个带宽单位，这里带宽单位代表一定大小的带宽强口1 带宽单位= 1 1 5 3 6 m b s ) ，这样可将带宽分配转化为整数规划。步进算法的步长就取一个带宽 2 硕士学位论文 单位的大小，从而以步进的方式逼近最优解。算法首先根据初始化的带宽分配及 所给出的通信量计算出网络中各个点对的呼损率，找出最小呼损率所在的点对， 然后将其带宽减去一个带宽单位，得到新的带宽分配。不断重复这一虚路径带宽的 递减过程，直到最后得到的带宽分配能够满足各链路容量的限制条件。在完成递 减操作之后。网络中会出现一条或数条满负荷的链路。算法随即将找出网络中最 大呼损率所在的虚路径，并将其带宽增加一个带宽单位，重复这一递增过程，直 到某条链路中各虚路径带宽和达到该链路容量限制。至此，一条或几条瓶颈链路 已经出现，而且最大呼损率所在虚路径通过了这些瓶颈链路。要达到最优解，还需 要对此带宽分配结果做最后的调整。 m p l s 网络中针对“管道”的带宽分配算法目前已经有两种。一种称为基于门限 预测( t l l r e s h 0 1 d b a s e dp r e d i c t i o n ) 的简单预测方法。这种方法的基本思想很简单： 如果我们使用单流更新方法，每当一个呼叫到达的时候，我们需要增加管道容量 一个带宽大小，反之，如果一个呼叫离开，则需要减少管道容量一个带宽大小。 这样就能保证管道有最高的资源利用率，但是会导致非常高的更新开销。然而， 如果每当一个新的呼叫达到的时候，我们增加管道容量不是一个带宽大小，而是 一个艿( 艿 1 ) 。这样一来，只要后续到达的呼叫没有超过管道容量大小，那么， 我们就没有必要再去更新管道的大小。通过保留比我们实际的、马上需要使用的 更多的管道带宽大小，我们损失了一些利用率，但是我们却能够减少很多更新次 数( 前提是：管道中的呼叫总数不会在一个短的时间内急剧地变化) 。占值的选取 基于开销和利用率之间的权衡分析。当管道中的呼叫数量跌到低于一个门限 ( t h r e s h 0 1 d ) ，为了增加利用率，我们可以减少管道容量。但是我们不把管道容量 减小到呼叫的实际数量大小。我们可以把管道容量设置得比实际呼叫需要大一些， 那么新到达的呼叫将不会触发一个新的管道容量更新。 基于门限的简单算法仍存在不足：一旦业务流的突发性很强，那么管道带宽值 将几乎维持在峰值附近，这并不利于提高链路资源的利用率。此外，它也不适合 于管理第二类管道资源，因为每一个域的资源调整都会同时引发下一个域内的相 同行为，频繁的域间调整并不切实可行。为此，有人提出了一种同样适用于第二 类管道的动态带宽分配算法。在该算法中引入了简单的定时机制，用来克服p s 业 务流的强突发性，同时在域内b b 处记录汇聚管道的富余带宽值，用于域内资源的 局部调整。 1 4 本文所做的工作 本文在现代通信网络中的带宽分配算法方面作了一些研究和探索，主要工作 3 现代通信网络中的带宽分配 总结如f ： 1 本文首先介绍了常用的a t m 下的虚路径带宽分配策略，对常用的二分算 法和新近出现的步进算法，进行了简单介绍和实验分析，为本文后续章节的研究 提供了理论和实验基础。 2 步进算法相比二分法虽能够加速动态带宽分配过程，但此算法本身仍然存 在一些不足之处。一个是其采用的用来计算呼叫损失率的k a u f a m a n 迭代公式 非常耗时，特别是在巨型资源系统中。针对这个不足，我们采用了文献【l o 】中的 基于准独立近似的计算呼叫损失率的快速算法，并把它推广到了非完全共享的条 件下，用来替代k a u f h l a n 公式。另外一个不足之处在于步进算法中的初始化带宽 分配的后一步：将全网最小呼叫损失率的虚路径之带宽减去一个带宽单位。本文 中将这一步改为直接找到一条或多条受限链路，对这些受限链路上的呼叫损失率 最小的虚路径减去一个带宽单位。分析与实验表明，改进后的步进式算法能进一 步加速动态带宽分配过程。同时，本文中提出了一种相较文献 4 中的步进算法最 优性数学证明更为简单的证明。 3 本文在考察步进式算法的过程中曾经试图进一步改进该算法。但改进需要 有一个前提，那就是：减去一个带宽单位对呼叫损失率不同的两条虚路径上的呼 叫损失率大小关系不会产生影响。然而，本文中证明了增加或者减少相同的带宽 都有可能使得两条虚路径上的呼叫损失率大小关系产生改变。最后，仿真也进一 步证实了这一点。 4 本文最后在m p l s 网络中的“管道”概念基础上，分析了两种“管道” 带宽分配算法的优缺点，并提出了一种改进的v b r 视频流在m p l s 网中的传输 的改进的动态带宽分配算法。实验结果显示，改进的分配算法提高了“管道”资源 的利用率并相应减少了视频流的损失率。 1 5 本文的内容安排 本文后续章节组织如下： 第二章：常用的a t m 下的虚路径带宽分配策略； 第三章：巨型资源非完全共享系统虚路径带宽分配新策略； 第四章：虚路径带宽增减对呼叫损失率的非线性影响： 第五章：v b r 视频流在m p l s 网中的传输的改进的动态带宽分配算法 4 硕士学伉论文 第2 章常用的a t m 下的虚路径带宽分配策略 2 1 引言 在现代电信网中，由于通信量的不可预测性和新服务的出现u j ，使得一种允许 对端到端连接( 虚路径) 的带宽进行重新分配的带宽供应策略成为一个必须的目 标。在传统的带宽策略中，仅仪是基于繁忙时段点到点的通信量( 设计通信量) 来对网络进行预先的设计( 设计带宽) ，以满足给定的服务级别的要求。显然，这 已经不能满足现代通信的要求。由于通信量的波动，使得在某些端到端连接中， 带宽分配过多，而在另一些连接中，带宽不足。理想的带宽分配策略应该能够实 现一个弹性的网络，这种网络能够动态地适应通信量的变化。本章专门介绍流行 的最优算法即二分法2 ，如和一种新的步进式最优算法”，并通过实验测试进行性能 对比及分析，为后而章节奠定了理论和实验基础。针对通信量波动而对虚路径进 行优化调整后，网络性能可由最大呼损率来评定。在本文的测试网络中采用了这 种评定标准。 2 2 符号和最优化问题模型 本文用到的参数符号如下： l ：网络中的传输链路集： c ：第i 条链路的容量，i l ： n ：网络中的有向端到端点对集； k ：服务级别数： 只：有向点对问的虚路径，n n ： k ：有向点对问虚路径上分配的带宽n n ： 4 。：有向点对间给定的通信量，k k ，n h ： c 睨。：有向点对间服务级别k 在给定通信量下的呼损率，k k ，n n ： z f 。：路由矩阵元素p 通过c 则取1 否则耿0 ： 带宽分配算法的目的是在给出通信量时，最小化阿络中出现的最大呼叫损失 率。在这里，每条链路上复用的虚路径带宽之和不能超过该链路的容量。因此， 此最优化问题可用下面的表达式来描述： 此最优化问题可用下面的表达式来描述： 胁 砌魄 舰( c 睨。t k ， ) ) ； ( 2 1 ) “ 互，。k ! q f 厶 ( 2 2 ) 现代通信网络中的带宽分配 其中，对呼叫损失率的计算采用了参考文献 8 】中提供的迭代公式，其中 g ( i ) 为训算中用到的一个迭代中间变量： f = o f - 1 ，2 ，k ( 2 3 ) 其他 第k 级服务的呼损率为： 缸一l吒 啷2 丢g - g ( k d其中g 3 善g ( f ) 2 4 ) 上两式中，4 为给出的第k 级别的流量，既是第k 级别的一个呼叫所需要的带 宽。k 即为前面定义过的所分配的带宽。为使不同级别的呼叫具有相同呼损率， 在每条虚路径中为k 服务级别的呼叫设立带宽预留量t ( k ) 。当虚路径剩余带宽小 于等于带宽预流量时，第k 级别的呼叫将被拒绝。通过恰当选取t ( k ) ，可以使得 通过同一虚路径( v i r t u a lp a t h ，v p ) 的不同级别的呼叫得到相同的呼叫损失率 ( c a b l o c k i n gp r o b a b i l i t y ，c b p l 。有了以上这些参数及设定，在带宽大小为 吒的虚路径中，第k 级别的呼叫的呼损率计算公式经修改后如下1 2 f ： g ( f ) f = o f = 1 ，2 ，圪 ( 2 。5 ) 其他 其中珥( f ) 的作用是当剩余带宽小于或等于带宽预留量时，停止g ( f ) 的叠代，从 而达到按减去预留量后的带宽来计算呼损率的目的： 一譬z 篙二黑 眩s ， 6 ，) g ，其中g f ：兰g ( f ) ( 2 7 ) )良 一 0 g ， 酢0 p 4 。“ l一z litllllll_-j1-_l 1 | 、，u g )阮 一 ( g )( ， 4 o 4 。 1一1 吒 g 脚 i i 哪 硕士学位论文 2 3 二分法 二分法是目前使用较多的一种带宽分配的最优算法【2 ，3 】，其流程图如图1 所 示。算法首先由起始的最大及最小的呼叫损失率的估计值日和e ：开始，通常被 分别设为l 和o 。求出上下限的中间值e ，根据e 及各点对间通信量求出网络中 各点对所需要的最小带宽，然后在此基础上，将带宽分配到各点对间的虚路径上。 这里，目标函数是最大化所有虚路径带宽的和，所受限制条件为：( 1 ) 通过各个 链路的虚路径带宽和不能超过链路容量；( 2 ) 同一点对间的各条虚路径带宽之和 不能低于所需最小带宽；( 3 ) 各虚路径带宽必须大于等于零。此优化过程为一线 性优化问题，一般可用割平面法p j 来实现。在本文单虚路径的情况下，点对问带 宽即为虚路径带宽，优化过程只需要将多余带宽分配给容量未超限的链路。如果 优化成功，则算法将e 值赋予e ，否则赋给e ，。这一过程不断重复从而不断产 生新的估计呼损率e ，当呼损率上下限之间的差值小于给定的一个小的正实数占 时，程序停止，占的大小代表了程序搜索解所能够达到的精度。二分法的实质是 将非线性的优化问题转化为线性优化问题，然后用经典的线性规划方法来对转化 后的线性问题求解。 但是，二分法存在运算时间长等缺点遗传算法由于其广泛的适用性，在虚路径 带宽分配中也有使用，但因为其是在概率意义下的全局搜索，所以其收敛性及运行 时间并不理想。 2 4 步进最优算法 步进式算法4 1 的前提是有网络的各向点对间只有一条虚路径，算法主要特点是每 次对虚路径的重新分配。都是对某条虚路径增加或减少一个带宽单位，这里带宽 单位代表一定大小的带宽( 如1 带宽单位= 1 5 3 6 m b i t s s e c ) ，这样可将带宽分配转 化为整数规划。步进算法的步长就取一个带宽单位的大小，从而以步进的方式逼 近最优解。算法可分为三个部分。其流程图如图2 所示。 2 4 1 带宽分配初始化 首先，算法根据给出的通信量对最优化的带宽分配给出一个估计值。从步进 算法的特点可以看出，起始估计值如果越接近最优解，则步进达到最优解的步数 就越少。因此，初始估计对此算法性能影响很大。本算法根据网络的设计通信量 和设计带宽为基准，按照通信量变化的比例对设计带宽作同比例变化，然后将其作 7 现代通信网络中的带宽分配 为初始带宽分配。 圪= 五咿屯屯咿 玎 ( 2 8 ) 其中，。和，为设计带宽和设计通信量，屯为点对n 间k 级别的通信 量， 为一正的调整系数，取值范围为( 0 1 5 ，1 1 5 ) 。 2 4 2 瓶颈链路的寻找 在得到初始化的带宽分配以后，算法第2 步是寻找容量不能满足虚路径带宽 需求的瓶颈链路。毫无疑问，最大呼叫损失率会出现在最拥挤的链路上，只有找 到这些链路，对其进行调整，才能将全网的最大呼损率降下来。因为初始化分配 是按照通信量变化的比例来进行的，而通信量的变化是随机生成的，所以不可避 免的，在某些链路上虚路径带宽之和会大于链路容量，超过了限制条件，而在另 一些链路上，容量却没有得到充分利用。 算法首先根据初始化的带宽分配及所给出的通信量计算出网络中各个点对的 呼损率，找出最小呼损率所在的点对，然后将其带宽减去一个带宽单位，得到新 的带宽分配。不断重复这一虚路径带宽的递减过程，直到最后得到的带宽分配能 够满足各链路容量的限制条件。在完成递减操作之后，网络中会出现一条或数条 满负荷的链路。但是递减操作是对具有最小呼损率的虚路径进行减带宽操作，无 法保证最大呼损率会出现在满负荷链路上。所以，算法随即将找出网络中最大呼 损率所在的虚路径，并将其带宽增加一个带宽单位，重复这一递增过程，直到某条 链路中各虚路径带宽和达到该链路容量限制。至此，一条或几条瓶颈链路已经出 现，而且最大呼损率所在虚路径通过了这些瓶颈链路。 2 4 3 解的调整 通过以上的递减而后递增的过程得到的最大呼损率虽然已经得到了优化，但 此时的带宽分配还不是最优，而只能是次优的解，因为根据算法流程还无法保证 它的最优性。要达到最优解，还需要对此带宽分配结果做最后的调整，调整过程如 下：算法首先按顺序( 路由矩阵行顺序) 找到第一条最后一次带宽递增后超限的链 路，再依次( 路由矩阵列顺序) 对通过其上的各虚路径的带宽减去一个带宽单位， 然后计算这些虚路径上的呼损率。如发现有任何一条虚路径经减1 操作后的呼损 率仍小于最后一次递增前的最大呼损率m c b p ，则算法重新跳转到递增操作，即 说明调整成功，要对新出现的最大呼损率虚路径进行加l 操作。从程序流程图可 以看出，在跳转到递增操作前，有一个判断是否超限的操作，这主要是为在多条 链路同时超限时，防止调整只对一条链路起作用。当减1 操作后，所得呼损率大 8 硕士学位论文 于或等于m c b p ，则将减去的带宽补回原处，然后对下一条虚路径进行操作。在对 超限链路所有的虚路径进行操作以后，如果没有发现任何可以调整的虚路径，则 算法结束，m c bp 为最小的最大呼损率，与之对应的最后一次递增操作前的带宽 分配即为最优化的解。最后，算法按路由矩阵列顺序对各条虚路径带宽加1 并判 断各链路是否超限，直到所有虚路径带宽不能再增加为止，程序结束。 2 4 4 算法最优性证明 文献 4 】中给出了步进算法最优性的证明。如下：该步进式算法根据通信量的 波动对虚路径带宽做出相应调整，优化目标是最小化最大呼损率，从以上算法的流 程可以知道，最终所得到的带宽分配满足这样两个条件： ( 1 ) 最大呼损率所在的虚路径通过了一条满负荷的链路； ( 2 ) 通过这条满负荷链路的它任何一条虚路径的带宽减去个单位都会导致其 呼损率大于等于最大呼损率根据这两个条件，可将对算法最优性的证明归结 为如下定理的证明 定理1 如果在网络中各有向点对间只取一条虚路径，且对各条虚路径做出的带宽 分配满足如下两个条件： ( 1 ) 最大呼损率所在的虚路径通过了一条满负荷的链路； ( 2 ) 通过这条满负荷链路的其它任何一条虚路径的带宽减去一个单位都会 导致其呼损率大于或等于最大呼损率。则在此带宽分配下，各虚路径 上的最大呼损率为最小。 证明( 反证法) 设出现最大呼损率的链路是第i 条，其链路容量是e ，通过它的虚路径是 a 1 ，a 2 a j 。共有j 条，所分带宽分别为圪，圪：，最大呼损率m c b p 就 出现在a 1 虚路径上，由前面给出的条件( 1 ) 可知，。+ 屹：+ + = c f 。现 假设有一种新的更优的带宽分配方案，使网络最大呼损率删2 低于m c b p ，第 i 条链路上的虚路径带宽分配为吃，圪：，吃，其中，a 1 虚路径上的呼损率为 c 配l ，显然有c 睨j 朋b p 。 ， 由左边两式可以推出第i 条链路中至少对于一条 i 圪l + 圪2 + + s 圪l + 屹2 + 。 虚路径a w ，有吃 肘尸，从而与更优的假设产生矛盾，假设不成立。 图1 二分法流程图 1 0 硕十学位论文 图2 步进式算法流程图 现代通信网络中的带宽分配 实际上，我们发现可以从另外一个方面简单地考虑最优性的问题。对于满足 条件( 1 ) ( 2 ) 的带宽分配方案，假设a l 虚路径上的呼叫损失率c 配为全网的最 大呼叫损失率m c b p ，如果这样的一个带宽分配方案不是最优的，可以进一步地 最小化全网最大呼叫损失率，使得新的全网最大呼叫损失率心口尸 朋巴卯，如果继续重复 减少其他虚路径带宽的办法以减少新出现的最大呼叫损失率，仍然不可能使得 嬲即 姗8 尸。因此，一个使得网络能够满足条件( 1 ) 、( 2 ) 的带宽分配方法 已经使得网络的最大呼叫损失率最小化，也即，没有别的方法可以在此基础上进 一步降低全网最大呼叫损失率。所以，这样的一个带宽分配方案已经是最优的了。 2 5 算法对比测试模型和实验结果 为了检验新算法的性能，文献 4 中采用了参考文献 2 给出的测试网络，如图 3 所示从图中可以看到，此网络具有层次结构。 整个网络包含有3 0 个节点，其中有2 0 个端节点及1 0 个中间节点。 这些节 点由3 3 条双向传输的链路连接。考虑2 0 个端节点之间的通信，2 0 个端节点共 组成焉= 3 8 0 对有向的点对，同时按照最短路径的原则，每个点对生成一条虚 路径，共3 8 0 条虚路径。网络中包含有两种不同的服务级别：每个呼叫6 4 k b s 的 语音服务和每个呼叫1 5 3 6 m b s 的视频服务。根据前面所述的带宽保留原则，令 两种级别服务的带宽预留量为t ( 1 ) = 1 4 7 2 m b s ( 语音) ，t ( 2 ) = 0 m b s ( 视频) 图3测试网络结构图 1 2 硕士学位论文 从而使得同一虚路径中的两种级别的服务具有相同的呼损率f 6 ，”。网络设计通信 量为：语音2 6 0 e r l ，视频2 6 e r l 。带宽以1 5 3 6 m b s 为一个单位来进行分配( 即1 带宽单位= 1 5 3 6 m b ，s ) 。这里需要指出的是，带宽单位过小，会导致每次分配后对 呼叫损失率的影响过小，导致过多的无意义的计算，而带宽单位过大，则会导致分 配不精确，引起带宽利用率下降。文献 4 】采用了参考文献 2 】中的网络模型，该模型 中，语音与视频呼叫具有相同的优先级，所以当带宽需求为1 5 3 6 m b ，s 的视频呼 叫通信量变化时，只有选择与之相同的带宽单位来对网络进行重新分配才能准 确、高效地降低拥塞链路中较大的呼叫损失率，因此文献【4 】选择了与参考文献【2 】 中相同的带宽单位1 5 3 6 m b s 。当需要带宽为起始状态时，每个点对间的呼损率 为2 6 6 ，占用带宽为6 7 5 8 4 m b s ，各个链路的容量按照通过其虚路径的起始带 宽之和来设计，表1 列出了各条链路的容量值。 表1 链路容量 、 为了比较采用两种不同的计算呼叫损失率的方法在步进式算法的差别，文献 4 考虑了通信量在三种不同范围内波动的情况。在这三种情况中，各点对间通信量 分别在设计通信的上下2 0 ，4 0 ，6 0 范围内随机波动。即每次给出的通信量按 照下式产生： 4 ( i ，j ) = 爿l o 幸 1 一 似+ 2 木a 正4 x 丰矗d 】( i ，j = 1 ，2 ，2 0 ) ( 2 9 ) m a x 分别取值为0 2 ，0 4 ，o 6 代表通信量波动的三种不同范围。r n d 为( o ，1 ) 间 均匀分布的随机数，4 。( k = l ，2 ) 为设计通信量，爿。= 2 6 0 e r l ，4 。为2 6 e r l 。 文献【4 】用c 语言对两种算法编程实现，并在p i i l 6 0 0 微机上运行程序。对于随 机生成的五种在不同范围内波动的通信量，两种算法运行结果见表2 。 1 3 现代通信网络中的带宽分配 由表2 可以看出，两种最优化算法得到的最大呼损率是相同的( 其中最大c b p 末位数的差别源于二分法的搜索精度) ，这说明步进式算法实现了其最小化最大呼 损失率这一最优化目标。从实验结果中还可以看到，步进式算法的运行时间远低 于二分法，而且在通信量波动幅度较小时尤为明显，运行时间仅为后者的十分之 一左右。而从平均呼损率水平来看，步进算法也远低于二分法，在通信量大幅度 波动时表现更为明显。鉴于步进算法运行时间起伏波动较大( 见表2 ) ，为检验其 实际性能，实验中随机生成通信量，每种波动范围对步进算法独立运行8 次，取 其平均运行时间如表3 所示。从表中可见，平均运行时间也处于较低水平。 表3 步进算法平均运行时间 对于运算时间相对二分法的大幅度缩短，可以从两种算法的运算过程做出分 析。由图1 可以看出，二分法涉及到由呼损率和通信量求所需带宽的运算，由于 无法通过对式( 5 ) ，( 6 ) ，( 7 ) 求逆来得到该运算的表达式，所以该运算也只能通 过二分逼近来实现。这样，二分法每分配一次带宽都要进行这样二重的二分逼近 计算，在一定的精确度要求下导致运算量非常大。而步进算法直接通过现有表 达式计算呼叫损失率，同时每次带宽重新分配只是某条虚路径增加或减少一个带 宽单位，计算量相对二分法大大减少。 1 4 硕士学位论文 2 6 小结 在各链路带宽容量的限制下，虚路径带宽分配的优化目标是在通信量变化的 情况下提高网络整体的性能，即最小化最大呼损率( 网络中所有有向端到端点对 的呼损率中的最大值) 。对这种优化问题，目前流行的最优算法即二分法，但其存 在运算时间长等缺点。遗传算法由于其广泛的适用性，在虚路径带宽分配中也有 使用，但因为其是