基于遗传免疫粒群优化的网络拥塞控制方法.pdf

《基于遗传免疫粒群优化的网络拥塞控制方法.pdf》由会员分享，可在线阅读，更多相关《基于遗传免疫粒群优化的网络拥塞控制方法.pdf（56页珍藏版）》请在三一文库上搜索。

1、( 4 ) T h r o u g ht h ea n a l y s i so ft h ep a r a m e t e r so ft h en e t w o r kp a t ha n dt h ei n d e xo f t h ep a t ho p t i m i z a t i o n ，w ep r o p o s e dan e t w o r kc o n g e s t i o nc o n t r o lm e t h o db a s e do n h y b r i dg e n e t i ci m m u n ep a r t i c l es w a r

2、mo p t i m i z a t i o n T h em e t h o dp l a n st h ep a t ho f n e t w o r kl o a d ，w h i c hm a k e sn e t w o r kl o a db a l a n c i n ga n dr e s o u r c ec o n s u m p t i o na sa i m f u n c t i o nt oa v o i dn e t w o r kc o n g e s t i o nb yb a l a n c i n gt h el o a da n dm i n i m i

3、 z i n gn e t w o r k r e s o u r c ec o n s u m p t i o nt om e e t i n gm u l t i f o l di n d e x e so fb a n d w i d t ha n dd e l a y T h e r e s u l t so fs i m u l a t i o ns h o w st h ee f f e c t i v e n e s sa n dt h er e l i a b i l i t yo f t h i sm e t h o d K e yw o r d s ：n e t w o r

4、 kc o n g e s t i o n ；n e t w o r kq u a l i t yo fs e r v i c e ；Q o Sr o u t i n g ；I G A P S O ； p a t ho p t i m i z a t i o n I I I 目录 目录 摘要I A b s t r a c t I I 目录I V l 绪 仑1 1 1 引言1 1 2 网络拥塞与网络拥塞控制1 1 2 1 网络拥塞l 1 2 2 网络拥塞原因分析2 1 2 3 网络拥塞控制机制分析4 1 3 基于优化理论的网络拥塞控制方法概述。5 1 4 网络仿真工具N S 2 及其在网络拥塞控

5、制中的应用分析6 1 4 1 网络仿真软件N S 2 6 1 4 2 N S 2 在网络拥塞控制中的应用分析8 1 5 本文的主要工作1 0 2 网络拓扑与Q o s 路由算法分析1 2 2 1 引言。l2 2 2 网络拓扑及其分析1 2 2 2 1 拓扑模型。1 2 2 2 2 网络拓扑图分析1 6 2 3 网络Q o S 路由算法分析1 7 2 3 1 网络性能指标分析。1 7 2 3 2 路由算法分析l8 I V 目录 2 4 小结1 9 3 遗传免疫粒群优化算法及其应用分析2 0 3 1 引言2 0 3 2 粒群算法及其分析2 0 3 2 1P S O 算法原理2 0 3 2 2P S

6、 O 算法参数分析2 3 3 2 3P S O 算法早熟现象的判定2 3 3 3 遗传与免疫优化算法2 4 3 3 1 遗传算法。2 5 3 3 2 免疫算法2 8 3 4 遗传免疫粒群优化算法3 1 3 4 1 算法原理3 l 3 4 2 仿真及其应用分析3 5 3 5 小结3 7 4 遗传免疫粒群算法在网络拥塞控制的应用研究3 8 4 1 引言。3 8 4 2 路径参数和优化指标分析3 8 4 2 1 路径参数设置3 9 4 2 2 路径优化指标4 0 4 3 基于遗传免疫粒群优化的网络拥塞控制方法4 2 4 3 1 方法4 2 4 3 2 仿真结果及其分析4 3 4 4 ，J 、结4 5

7、 5 总结与展望4 6 5 1 总结4 6 5 2 展望4 7 V 目录 参考文献4 8 致谢51 个人简历、在学期间发表的学术论文与研究成果5 2 V I l 绪论 1 绪论 1 1 引言 近些年来，由于经济的迅速发展，已经带动了网络计算机技术的飞跃进步， I n t e m e t 作为近几十年来最大、最广泛、发展最快的计算机网络，在人类的生活 中有着不可代替的位置。人们现在不用出门就可以通过网络做到很多事，例如 通过网络进行信息交流，网上订餐订票，买生活用品，甚至可视电话，远程会 议，远程教学等有关人类生活的先进科学技术的出现，都可以通过网络得以实 现。I n t e m e t 已发展

8、成为全球性的信息基础设施。由于使用方便，网络用户数目 一直在快速增长，导致网络规模越来越大，网络环境也日趋复杂。在为人类的 生活带来便利的同时，网络拥塞问题也接踵而至。 在网络运行中，网络拥塞会造成吞吐量，延时等一些性能指标的降低，影 响网络运行的稳定性和网络服务质量( Q o S ) ，也是影响带宽、缓存等的网络资 源利用率的关键因素。为了能使网络资源得到合理的分配，提高服务质量，其 中比较有效且受到专家学者青睐的方法之一就是通过适当的方法去预防和控制 拥塞，从而保证网络的正常运行【。 1 2 网络拥塞与网络拥塞控制 1 2 1 网络拥塞 随着网络工作的范围不断扩大网络用户也越来越多，当过多

9、的数据包存在 网络中，而网络资源本身所具备的容量已经无法满足用户的需求时，就会造成 网络拥塞【2 1 。简而言之即指传输分组数目过多会导致网络传输性能下降。拥塞现 象的出现表明了网络工作正处在非正常的状态下，它直接导致了网络的整体性 能下降【3 】：加大分组丢失率，增大端到端延迟，降低网络吞吐量等。 图1 1 、图1 2 分别反映了当前负载与吞吐量、时延之间的关系：当网络负 载较轻时，负载与吞吐量之间呈线性关系，也就是吞吐量会随着负载的增加而 1 绪论 呈现增加趋势，此时时延增长比较缓慢；这种情况持续到负载到达膝点( K n e e ) ， 膝点以后吞吐量随着负载的增加而继续增加，但增量的逐步

10、减小使两者不再呈 线性关系，此时时延增长加快；直至负载增加到崖点( c l i f f ) ，崖点之后网络的 吞吐量随着负载的增加而呈现急剧下降的趋势，此时时延上升趋势最大【4 】。我们 通过K n e e 点、c l i f r 点把拥塞状态分为三个区间，分别为拥塞避免区间，拥塞恢 复区间和拥塞崩溃区间。拥塞避免区间在K n e e 点附近，由图1 1 可知，此时负 载与吞吐量之间呈线性，网络使用率最高【5 1 ；拥塞恢复区间介于K n e e 和c l i f f 之 间，虽然此区间吞吐量增加的较缓慢，然而还能确保网络一定的使用率；拥塞 崩溃区间处于c l i f f 之外，此区间为拥塞崩

11、溃状态，网络无法正常工作。 吞 吐 量 负载 图1 1 负载与吞吐量 1 2 2 网络拥塞原因分析 时 延 负载 图1 2 负载与时延 技术进步的同时也带领I n t e m e t 进入更加稳定、健全的发展时代，然而这不 能说明网络中不再出现拥塞现象。I n t e r n e t 作为一个非常复杂的系统，局部充足 的资源无法供给网络中所有的位置，这种资源相对短缺的现象是造成网络性能 下降的主要原因。 通过分析总结出产生拥塞的直接原因扣1 ： ( 1 ) 存储空间无法满足过多的数据流。假设有几个数据流共同经过某个输 入口，这几个输入流不能同时进入端口，剩下的输入流只能在端口按照顺序进 入，倘

12、若存储空间无法满足过多的数据流，数据包就会丢弃。假若有突发数据 流出现时，也会造成数据包丢失现象。这是造成网络拥塞的直接原因之一，针 对这个问题不能认为简单的增加存储空间就行了，加大空间只能轻微缓解拥塞 2 l 绪论 的程度，但是当路由器有无限存储量时，拥塞现象会加更严重。 ( 2 ) 没有足够的带宽容量。信道容量C = B 崦2 ( I + S N ) ，这里B 表示信道 带宽，S 表示信源最大功率，N 表示信道白噪声的平均功率。从理论上讲信源正 常输入的前提是任何信源发生的速率R 必须不大于信道容量C 。当高速数据流 通过低速链路输入时，如果不能满足要求也会造成网络拥塞。 ( 3 ) 处理

13、器不具备强大的处理能力。这个原因会直接造成路由器的C P U 无 法跟上高速链路，从而致使网络出现拥塞。 统计表明，由网络拥塞而造成性能下降的比例占一大半，因此在进行网络 工作时要确保Q o S 就必须及时解决已经发生的拥塞问题，通过对拥塞控制进行 分析研究，找到最适合的解决方法，因此要有高效的拥塞检测、预防和控制机 制，确保网络的鲁棒性。 I n t e m e t 作为一个非常复杂的分散控制系统，不能改变用户所需求的网络资 源，也不能根据资源的多少对用户数量进行限制，因此，出现网络拥塞的最根 本原因是不断上升的用户数量与有限的网络资源不能协调，即需要的多而提供 的少，但是又不能通过简单的增

14、加网络资源来解决，因此网络拥塞的发生是必 然的。 网络拥塞体现了I n t e m e t 分布的不均衡，它总是发生在网络资源相对短缺的 位置。分布不均衡分别体现在资源和流量上，如图1 3 ( a ) 中带宽分布不均衡：假 设某一数据流S 通过速率1 M b p s 发送数据到D 处，途径路由器R 时会出现网络 拥塞；如图1 3 ( b ) 中流量分布不均衡：假设两个数据流s 1 和S 2 通过相同的速率 1 M b p s 发生数据到D 1 处，途径路由器R 时也会出现网络拥塞。 ( a ) 带宽分布不均衡( b ) 流量分布不均衡 图1 3 网络的不均衡性意图 1 绪论 1 2 3 网络拥

15、塞控制机制分析 拥塞控制可以从两方面来实现：一个是避免拥塞的发生；另一个是对拥塞 的发生做出反应。它的算法也相应的分为两种不同的机制：一种是拥塞避免； 另种是拥塞控制【7 】。由图1 1 、图1 2 可以看出，前者是一种“预防”机制， 当网络运行在K n e e 点附近，在还没有出现拥塞前对这种现象进行预防，避免拥 塞的发生，它维持网络的高吞吐量、低延迟状态；后者则是一种虬恢复”机制， 能使网络运行在C l i f r 的左侧区域，当网络已经出现拥塞现象，就不能只用预防 机制了，要通过对拥塞的发生做出反应，使网络从拥塞状态中恢复。在使用的 大多数低速网络中，一般采用恢复机制对拥塞的发生做出反应

16、，使网络从拥塞 中恢复过来，进入正常的运行状态。 假若某个节点在低速网络中发生拥塞现象，在该节点恢复正常状态前，周 围的其它节点都会默认这种状态，且在单位时间内到达节点的信元数量不是很 大，因此该拥塞节点能通过减少传递报文的数量去缓解拥塞状态，直到消除拥 塞。但是假设某个节点在高速网络运行中出现同样的处境，就无法通过这种方 法缓解拥塞状态，并且能在极短的时间内将这种拥塞状态传给网络中其它的节 点，甚至造成拥塞崩溃。因此，对于高速网络来说恢复机制并不可靠，拥塞预 防才能从根本上解除拥塞状态。由上图1 1 、图1 2 说明，拥塞控制的目标就是 使网络在K n e e 附近工作，避免出现图中网络性能

17、严重下降的情况，合理的使用 网络资源，在控制效果更好的数据链路层进行拥塞控制，避免发生网络拥塞。 近些年来，网络拥塞现象已经无法避免，因此需要采取有效的策略控制拥 塞，且能保证网络工作的正常进行。拥塞控制作为改善网络系统性能、提高网 络服务质量的必要手段，从控制理论的角度来说可以两大类：分别是开环控制 和闭环控制【引。开环控制是一种很直接的控制拥塞的方法，适合使用于提前得知 某业务的特征和性能的情况下。反之则需要用闭环控制，该控制可以动态的适 应网络的变化，根据检测到拥塞的出现，进行反馈控制。但是开环控制和闭环 控制在使用中都有缺陷：由于开环控制的局限性，在确保网络资源利用率的基 础上，网络资

18、源无法做到过多的预留以保证服务质量；而闭环控制应用是建立 在反馈环路的基础上，易受反馈延迟的干扰。一般为了保证能适应网络变化会 使用闭环控制。 4 1 绪论 1 3 基于优化理论的网络拥塞控制方法概述 在以往的传统路由算法中，通常会为业务流择一条最近的途径，也就是从 源节点到目的节点路径最短，传统路由算法在进行运算的初衷是想降低网络中 的资源消耗，例如O S P F t 9 1 、I S I S t m 】等，提供为业务流找到最短路径的服务，保 证网络连接到接受方。然而这些传统算法在进行选择路径时忽略了其它问题： 业务流会不会在流经中间的路由器因为拥塞等原因造成丢失数据包，从而不能 最终传送到

19、接受方，或者在通过中间的路由器时排队缓存，影响数据包的传送 时间。在传统路由算法中，选择最短路径看似方便，然而当目的节点相同的业 务流选择的同一条途径时，也会产生两个问题，第一个问题是当很多业务流都 流经某一条链路时，会导致该链路发生拥塞；第二个问题是从源节点到目的节 点，当业务流过多易造成网络负载利用不均衡，较长路径被空置，最短路径出 现拥塞。 由于传统路由算法不能根据资源、业务流等己知元素的情况进行合理的分 配路径，只是依据业务流将要传送到的接受方进行最短路径选择，结果易造成 拥塞。而拥塞的发生会导致数据包的延迟或丢失，从而更加大了整个传输过程 的传输时延、时延抖动、丢包率等，降低了用户的

20、服务质量和网络服务的可预 见性。 通过提出等价多路径( E C M P ，E q u a lc o s tM u l t i p a t h ) 的方法【l ，对最短路径 造成的负载不均衡进行改善，但这种有限的调节作用还是无法改变传统算法在 应用过程中两条或者以上的最短路径只能选择一条的情况，容易造成这条路径 上的负载分配少。等价多路径在此基础上的改善是如果到目的节点有多条代价 相等的最短路径，这些最短路径在被选择的机率是相等的，不用担心只有其中 某条路径被选择，可以平衡负载的分配，从一定程度上E C M P 解决了业务流过 多易造成网络负载利用不均衡的问题。这里说的负载分配均衡的前提是代价相

21、 等的最短路径，并不是指每条路径，而且在代价相等的最短路径之间也不能根 据拥塞状况而动态的改变负载分配。当某条路径上传送多个业务流时，该路径 更容易造成拥塞。 在1 2 2 节中对网络拥塞原因进行了详细的分析和研究，对于由突发流量导 致生成的拥塞可以通过分析结果进行改善，而对于长时间的拥塞可以通过下面 两种途径进行解决： 5 1 绪论 ( 1 ) 扩大网络容量。这是最简单最直接的方法，通过采用更高带宽的传输媒 介，提高硬件设备，缺点是造价太高。 ( 2 ) 利用拥塞控制技术。例如路由器队列管理等技术。 由于负载的分配不均衡而导致的网络拥塞不能通过简单的增加网络容量来 解决，本文通过提出种新型的

22、路由算法，既能满足网络服务质量，又能优化 资源的利用。 到目前为止，国内外诸多专家学者通过探讨研究找出一些能解决Q o S 路由 问题的智能算法，效果较好。例如某些文献提出利用模糊逻辑方法解决Q o S 路 由问题的方法【1 2 1 ；还有些研究通过对优化算法进行揣摩研究，提出可以解决使 用这些优化算法时所遇到问题的方法【1 3 】【1 4 】【1 5 】：或者一些研究借鉴了蚂蚁算法的 自适应和随机性，找出一条当带宽被限制时遇到拥塞现象时的动态路由选择【l6 1 。 经过研究，遗传算法作为一种能够处理有关优化问题的方法【1 7 J ，被人们广泛应 用于网络工作中，有些研究提出了在遗传算法应用基

23、础上的路由算法【l 即；有些 研究提出一种优化网络资源利用的Q o S 路由选择的遗传算法【l9 1 。微粒群算法的 应用也很广泛【2 0 】，该算法通过对新粒子进行速度更新，同时采取了粒子的抗拥 塞新策略，成为了一种能解决多Q o S 约束路由问题的新型智能优化算法，微粒 群算法运算较简单，易于实现。 然而即使这些智能优化算法相比较传统优化算法已经有了很大的改进和优 势，我们还需要进一步研究通过何种途径才能使得这些智能优化算法之间进行 优势互补，从而得到更好的仿真效果。 1 4 网络仿真工具N S 2 及其在网络拥塞控制中的应用分析 1 4 1 网络仿真软件N S 2 近些年来，由于I n

24、t e r n e t 发展迅速，因此也会出现一些需求用来配合通信网 络的发展，多协议网络模拟器作为一个流通范围包括供那些不同领域通用的模 拟环境，如果能够开发一个通用的多协议网络模拟软件是很有实用价值的，既 能提高研究环境的质量，也能方便应用于网络研究中。N S 2 是N e t w o r k S i m u l a t o r - V e r s i o n2 的缩写。该模拟器是由U CB e r k e l e y 设计的，当时由V M P r o j e c t 团队进行维护，现在由S A M A N 和C O n s E R 负责。目前N S 2 是V I N T 6 1 绪论 P

25、 r o j e c t 的一部分，V I N TP r o j e c t 还设计一些工具，用于仿真结果的显示、分析和 转换。这些操作可以把N S 2 产生的N S 2 格式的拓扑结构转换成真正的网络拓扑 结构。 通常N S 2 是一个用C + + 和O T C l 这两种语言编写的、面向对象的、事件驱动 的网络模拟器。N S 2 可以分为编译层和解释层，在编译层用C 抖进行编译，这 样可以减少分组且能提高事件的处理效率；N S 2 的前端是一个O T c l 解释器，因 此解释层是用O T c l 进行编写。一个普通的N S 2 网络用户可以被想象站在图1 4 的左下角，通过使用O T c

26、 l 库中的模拟对象设计和运行模拟器，事件调度器和大 多数的网络组件在C + + 中实现并且通过O T c l 连接使其在O T c l 中有效。所有这 些就构成了N S 2 ，这是一个面向对象的带有网络模拟库的T c l 解释器。图1 4 是 N S 2 的基本结构。 图1 4N S 2 的基本结构 C + + 和O T c l 两种语言在运行中所做的具体工作不同，前者是强制类型的语 言，运行速度快，易实现复杂的数据类型跟算法，然而在修改、d e b u g 和重新编 译上会占用不少时间；相反后者不是强制类型的语言，运行速度慢，却能很容 易的在不需要编译的情况下交互修改。这两种语言各有优缺点

27、，因此我们可以 根据情况对C + + 和O T c l 进行选择：( 1 ) 以下选择C + + ：包括那些必须去解决的 某个数据流中各个分组的所有问题；或者那些已经存在但需要被修改的C + + 类 行为。( 2 ) 以下选择O T c l ：在建立、配置、模拟中只运行一次的程序；或者当 用O T c l 脚本就能很容易操作存在的C + + 对象而达到目的。 用T c l C L 工具包将C + + 和O T c l 两种语言中的对象及变量联系起来，形成了 7 1 绪论 图1 5 所示的分裂对象模型。N S 2 的构件库是一个层次结构，构件库中的构件由 两个类实现的，这两个关联的类分别在C +

28、 + 和O T c l 中，所以N S 2 中包含了两个 类的层次结构，一个C + + 类的层次结构，一个O T c l 类的层次结构，在图1 5 中 可以体现出来。 图1 5 分裂对象模型 1 4 2N S 2 在网络拥塞控制中的应用分析 N S 2 仿真软件进行仿真分两个层次：基于O T c l 语言编程的层次和基于两种 语言编程的层次。前者在不修改软件本身的前提下编写O T c l 脚本，通过软件已 经存在的网络元素进行仿真；后者首先了解N S 2 中是否存在仿真需要的网络元 素，如果存在，则进行仿真，如果不存在，则要扩展N S 2 ，添加必要的网络元 素。因此在进行仿真前，首先要明确仿

29、真的层次。模拟过程如图1 6 所示。 1 绪论 图1 6 N S 2 网络模拟过程 仿真步骤如下： S t e p1 ：开始编写O T c l 脚本。建立网络拓扑图，确定链路的基本特性，包 括有链路带宽、延迟时间等。 S t e p2 ：建立跟踪模型。包括网络传输协议以及通信业务量模型的建立。 S t e p3 ：对通信业务量模型参数进行配置，以确定网络业务量分布。 S t e p4 ：设置跟踪对象，模拟仿真过程中的特定类型事件通过记录在t r a c e 文件上进行保留的，模拟完成之后，对保留在t r a c e 文件的过程进行解析。 S t e p5 ：除了步骤四的模拟过程外，还需编写其他

30、辅助过程，对模拟结束时 间进行设定。 S t e p6 ：通过N S 2 仿真软件，对上述编写的O T c l 脚本进行解释执行。 S t e p7 ：分析跟踪文件，得出有用的数据。利用一些画图工具获得我们需要 的曲线，也可以利用N a m 等工具观看运行过程。 S t e p8 ：对模拟结果进行分析，修改O T c l 脚本和C + + 代码，返回重新模拟。 N S 2 软件在网络建模、拥塞控制的仿真中占有很重要的作用，通过了解该 软件的仿真过程，将该软件工具应用到网络拥塞控制中，可以对拥塞控制进行 分析研究，以便能更好的利用方法来解决网络拥塞问题。 9 1 绪论 1 5 本文的主要工作 通

31、信网络的快速发展已经带动拥塞控制研究成为网络拥塞方向的一个重点 研究领域。网络拥塞作为制约网络发展的一个重要因素，极大地影响了其它服 务质量( Q o S ) 机制的正常工作，无法确保网络的鲁棒性，网络性能遭受破坏。 因此设计一种可靠且稳定的网络拥塞控制算法是拥塞控制研究中的热点问题。 通过研究发现，由于网络的复杂性，同时在综合考虑一些已有算法的前提下， 本文提出了通过混合的优化策略来解决出现的网络拥塞现象一基于遗传免疫粒 群优化的网络拥塞控制方法，通过验证得出该方法能够有效预防和控制拥塞的 发生。所做的主要工作如下： 第1 章绪论。首先详细的分析有关网络拥塞和网络拥塞控制机制的内容， 引出利

32、用新型微粒群优化算法解决拥塞控制的思路；其次对仿真工具N S 2 进行 了详细的介绍，熟悉该仿真软件的功能；最后给出N S 2 在网络拥塞机制中的应 用分析。 ( 5 ) 第2 章网络拓扑与Q o S 路由算法分析。分析了拓扑模型及网络拓扑图， 继而对网络服务质量Q o S 路由进行了详细研究，包括算法及其网络性能指标等， 给出了Q o S 路由优化数学模型，为之后进行路由优化、网络拥塞控制打下基础。 通过这一系列的前提工作为本文最终实现网络拥塞控制奠定了基础。 第3 章遗传免疫粒群优化算法。将遗传算法( G e n e t i cA l g o r i t h m ，G A ) 和免疫 算法

33、( I m m u n eA l g o r i t h m ，I A ) 弓I 入到微粒群优化算法( P a r t i c l eS w a r mO p t i m i z a t i o n , P S O ) 当中，给出了遗传免疫粒群优化算法，简称I G A P S O 。引入遗传算法中交 叉和变异两个机制，通过一定的准则判断是否出现“早熟“ 现象，若有，则将 随机产生的个体与记忆库中保存的优秀个体通过两个机制产生新个体；同时利 用免疫算法的一些优点，将识别、选择两个思想引入P S O 进行判断个体能否被 选择到下一代群体进行运算操作，这个步骤是在利用两个机制前进行的，判断 选择的标

34、准是根据繁殖期望水平的大小。这样既可以维持新个体的优秀特性， 也能保证群体的多样性。 第4 章基于遗传免疫粒群优化的网络拥塞控制方法。本章节对网络路径参 数设置和路径优化指数进行了分析，给出了基于遗传免疫粒群优化的网络拥塞 控制方法。该方法与以往的传统方法不同，以负载均衡分布函数和资源消耗函 数作为优化目标，在进行优化前要先满足带宽、时延等多项网络指标，通过路 1 0 l 绪论 径参数和优化指标分析，对网络负载进行路径规划，达到网络资源消耗尽量少 与负载分配尽量均衡的协调，从而避免网络拥塞。仿真结果验证了给出方法的 有效性和可靠性，在完成网络拥塞预防的前提下，同时也使数据通信网络的运 作性能得

35、到了很大的改善。 第5 章总结与展望。对全文所做的主要工作进行了大致的总结，包括网络 拥塞机制和网络服务质量，网络拓扑与Q o S 路由算法，提出的新型P S O 算法、 新的拥塞控制方法等；展望也为该研究方向能在将来得到发展提出了两点要求。 2 网络拓扑与Q o s 路由算法分析 2 网络拓扑与Q o s 路由算法分析 2 1 引言 目前，I n t e m e t 已经发展到越来越多的地方，随着规模的增大也出现了很多 问题，在对如何合理分配资源等问题的研究上遇到很大的困难。由于I n t e r a c t 是 一个复杂分散的系统，它的动态变化会在解决运行中出现的问题时受到局限， 专家学者

36、无法将整个网络作为研究对象。因此我们可以利用建模的方式来代替 实际的网络，通过对该模的研究分析找到解决实际问题的途径。建模虽然可行， 但是由于网络是动态变化的，并且规模较大，实施起来也很艰巨，所以建模的 前提是要充分了解建模方法的差异，利用特定方法的优势随意选取模型。本章 节主要是对拓扑模型及网络拓扑图进行分析，继而给出网络Q o S 路由的算法解 析，包括算法分析和网络性能指标分析。这一系列的前提工作为本文最终实现 网络拥塞控制奠定了基础。由于I n t e r n e t 系统的复杂与庞大，在进行网络拥塞控 制时会遇到很多困难，因此需要建立能对所有拥塞控制方法进行研究分析的Q o S 路由

37、优化数学模型，通过优化Q o S 参数来实现网络拥塞控制的要求。当我们在 选择拓扑模型时，若有典型的拓扑结构和随机配置参数，选择模型很容易，但 是由于受到条件的限制，实现过程是困难的【2 I J 【z 引。 2 2 网络拓扑及其分析 2 2 1 拓扑模型 拓扑模型的存在对I n t e r a c t 的分析研究具有重要的意义，我们将网络拓扑模 型分成两种：一种是静态型拓扑模型，例如w a x m a n 模型【2 3 1 、T i e r s 模型【2 引、 T r a n s i t S t u b 模型【2 5 】和幂率【2 6 】，这些模型是用来描述网络拓扑特征的；另一种是 演化型拓扑

38、模型，包括有模型B A E 2 7 1 、模型E S F 2 8 】和模型G L P t 2 9 1 ，这类模型用 来描述拓扑特征形成机理的。本文是通过对静态型拓扑模型进行详细分析，利 用该类拓扑模型对网络拥塞控制进行具体的研究。 1 2 2 网络拓扑与Q o s 路由算法分析 由于拓扑模型会影响对整个网络的分析研究，在使用拓扑模型进行仿真时 的前提是必须保证所选模型与I n t e m e t 结构相似，下面几个度量( m e t r i c ) 参数可以 权衡判断前提条件能否满足： ( 1 ) 节点出度频率厶( n o d ed e g r e ed i s t r i b u t i o

39、 n ) 度作为能描述网络局部特性的基本参数，节点出度频率尼能反映网络中节 点度的分布，它是一个基本的判断依据一用来衡量所选的模型是否与I n t e m e t 结 构相似。 ( 2 ) 特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 特征路径长度也叫平均路径长度，反映了描述图的疏密，该值为图中每对 节点间最短距离的平均值，该度量参数是从“S m a l l w o r l d ”理论中提出的【3 0 1 。 ( 3 ) 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 聚类系数也

40、是从“S m a l l w o r l d 理论中提出的。描述图中的小集团就是由 该参数体现出来的，即与第三个节点连接的一对节点被连接的概率。 ( 4 ) 平均偏心度( a v e r a g ee c c e n t r i c i t y ) 一个节点到其它节点距离的最大值就是该节点的偏心度，而平均偏心度反 映的是全部节点偏心度的平均值，也可以用图的直径来表示。 ( 5 ) 最大团尺寸( m a x i m u mc l i q u es i z e ) 团是由网络中的节点进行两两相连而得到的图，最大团尺寸是指网络的核 心。 以上五个度量参数是以往专家学者研究总结的主要参数，在保证所选用

41、的 模型与I n t e r n e t 结构是否相似中占主导地位，而T a n g r n u n a r u n k i t 等人在2 0 0 2 年 又提出另外三个度量【3 ，包括有扩张度( e x p 口脚i o n ) 、弹性度( r e J 讲e n e e ) 和扭曲度 ( d i s t o r ti o n ) 。这三个度量同样用在拓扑模型的研究中。 作为网络拓扑模型几个度量参数中最重要的一个，节点出度频率厶的分布 不同导致了网络局部特性的不同，网络拓扑模型根据网络局部特性的不同分为 下面三大类： ( 1 ) 随机型拓扑模型 在随机型拓扑模型的建立中，有很多种随机建模方法，通

42、过研究分析总结 了四种： 1 ) 纯随机建模方法 该建模方法只能在网络互连中应用，是指在平面内的节点确定位置是随机 1 3 2 网络拓扑与Q o s 路由算法分析 的，不需要任何规则限制，且任意两个节点生成边的概率都用p 来表示。 2 ) W a x m a n 建模方法 作为最常用的一种建模方法，W a x m a n 建模相比纯随机建模来说更加如实的 反映出网络的真实特性和结构，该建模方法也是在平面内随意确定节点的位置， 然而概率P 却是服从泊松分布的。假设有节点“和1 ，则两节点生成边的概率为： 一d ( “，) p ( u ，) = 口e x p 矿 ( 2 1 ) 式( 2 一1 )

43、 中，d ( u ，v ) 是指两节点间的欧几里德距离，是指相距最远的两节点 之间的距离，P 的大小跟节点的距离有关。由此得知，在满足参数6 l 和取值 范围为I o ，1 I 的前提下，可以根据参数的变化来反映生成边的变化。这个概率公式 为版本尺G l ，对于尺G ：，只是将上述的概率公式中口取值改变为口 - 1 0 。 3 ) 指数分布建模方法 指数分布建模生成边的概率p ( u ，1 ，) 为： p ( u ，) = 口e x p _ - d _ ( u _ , v ) ( 2 2 ) 式( 2 2 ) 很直观的体现出概率p 0 ， ，) 与两节点间距离的关系：即d 越大， p 0 ，

44、，) 就越小，呈指数下降。 4 ) 局部分布建模方法 局部分布建模生成边的概率函数为： p ) = 悟缘二 ( 2 - 3 ) 该建模方法能通过边的长度不同而对其进行离散分类，函数中，设为临界 值。 局部分布建模方法不仅比纯随机建模方法更加简单，而且纯随机建模方法 的结果也能被局部分布建模法建成的模型采用。 ( 2 ) 分层型拓扑模型 分层型拓扑模型是除了随机型拓扑模型之外的另一种常用的模型，该模型 相比随机型模型更能反映真实的I n t e m e t 特性，我们通过以下两种层次的建模方 法来了解分层型拓扑模型【3 2 】。 1 ) N 1 e v e l 方法 第一种层次的建模方法是N 1

45、 e v e l 方法，该方法实现方便且能反映出网络的 1 4 2 网络拓扑与Q o s 路由算法分析 层次结构，生成过程可以分为三个小步骤，具体如下： S t e pl ：随机生成一张图； S t e p2 ：用连通的子图去代替图里的每一个节点； S t e p3 ：最后连接原图的边与新子图里的节点。 该方法的缺点是无法体现层次的差异性。 2 ) T r a n s i t s t u b 方法 第二种层次的建模方法是T r a n s i t s t u b 方法，该方法的实现过程是将组成 I n t e r n e t 的路由域分成两个域：S t u b 域和T r a n s i t 域。S t u b 域的特点是只对本域内 的消息流量进行流通，而T r a n s i