（计算机应用技术专业论文）业务量矩阵估算算法的设计与实现.pdf

摘要 摘要 随着互联网的飞速发展和网络业务的丰富，网络规模和业务量急速增长， 而目前的i n t e m e t 只能提供尽力而为的服务，在不支持q o s 的网络中多媒体等 高带宽要求的业务性能会下降，网络业务提供者面i 临越来越大的压力，因此实 施业务量工程就显得十分重要。本论文主要的研究内容就是业务量工程中业务 量矩阵的估算算法。该系统以n e t w o r ks i m u l a t o r2 作为实验系统的网络拓扑结 构和数据的生成环境和后期算法验证环境，根据现有的理论和实验依据搭建实 验框架，运用j a v a 语言实现离线的业务量矩阵的估算算法，通过大量的仿真实 验验证、比较、改进算法的有效性，为进一步的研究提供实验数据支持。 本论文分析了当前本领域的研究现状，对业务量工程的产生、发展、意义 以及理论知识进行了介绍，对现有的业务量工程中业务量矩阵估算算法进行了 研究，有针对性的对重力模型和其他实验模型进行了分析，根据实验环境和相 关理论研究的论文为基础，用n e t w o r ks i m u l a t o r2 搭建实验背景，把获得的网 络拓扑结构和链路流量数据作为输入数据，用离线的业务量矩阵估算算法估计 网络业务量矩阵，根据不同的网络结构和数据比较、改进算法，提出进一步的 实验设想。 关键词：业务量工程业务量矩阵最短路径 a b s t r a c t a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fi n t e m e ta n dt l l ea b u n d a n c eo fn e t w o r kt r a f f i c t h e s c a l eo fn e t w o r ka n dt r a f f i ca r ei n c r e a s i n gv e r ym u c h b u tt h ec u r r e n ti n t e m e t p r o v i d e sb e s t e f f o r ts e r v i c e so n l y , t h ep e r f o r m a n c eo fs o m ek i n d so fm u l t i m e d i a t r a f f i c t r a n s f e r r i n go nn op r o v i d i n gq o sn e t w o r kw i l ld e s c e n d t h ep r o v i d e r so f n e t w o r kt r a f f i cf a c em o r ea n dm o r ep r e s s u r e ，s ot h et r a f f i c e n g i n e e r i n gi sv e r y i m p o r t a n t t h i sp a p e ri sw r i t t e no nt h ep r o j e c to f t h ea l g o r i t h mo ft r a f f i cm a t r i x e s t i m a t i o n ”i nt h et r 棚ce n g i n e e r i n g t h es y s t e mi sb a s e do nt h en e t w o r ks i m u l a t o r 2 ，t og e tt h en e t w o r kt o p o l o g ya n dd a t ab e f o r e t h ee x p e r i m e n t s ，t ov a l i d a t et h e a l g o r i t h ma f t e rt h ee x p e r i m e n t s ；ib u i l dt h ee x p e r i m e n ts t r u c t u r et h r o u g ht h ec u r r e n t r e s e a r c ha n ds o m et h e o r i e sa b o u ti t ；t h e nc o m p l e t et h eo f f - l i n ea l g o r i t h mo ft r a f f i c m a t r i xe s t i m a t i o nu s i n gj a v a ；a f t e rm a n ys i m u l a t i n ge x p e r i m e n t siv a l i d a t e ，c o m p a r e a n di m p r o v et h ea l g o r i t h m ，a n dg i v es o m es u p p o r tt ot h ef l r t h e rr e s e a r c h t h i sp a p e ra n a l y z e st h ec u r r e n tr e s e a r c ha c t u a l i t y i n t r o d u c e st h ea p p e a r i n ga n d d e v e l o p i n go ft r a f f i ce n g i n e e r i n g ，t h em e a n i n go fi t ，a n ds o m eb a s i ct h e o r i e sa b o u ti t m a k e ss o m er e s e a r c ho nt h e e x i s t i n ga l g o r i t h ma b o u tt r a f f i cm a t r i xe s t i m a t i o n a n a l y s et h eg r a v i t ym o d e la n ds o m eo t h e rm a t hm o d e l s b a s e do nt h ea c t u a l e x p e r i m e n te n v i r o n m e n ta n dr e l a t e dt h e o r e t i cr e s e a r c h , u s et h en e t w o r ks i m u l a t o r2 t ob u i l dt h ee x p e r i m e n ts t r u c t u r e i n p u tn e t w o r kt o p o l o g ys t r u c t u r ea n dl i n kl o a dd a t a , u s et h ea l g o r i t h mo f 锄cm a t r i xe s t i m a t i o nt oc o m p u t et h et r a f f i cm a t r i x t h r o u g h d i f f e r e n tn e t w o r ks t r u c t u r ea n dl i n kd a t a , c o m p a r ea n di m p r o v et h ea l g o r i t h m ，t h e n g i v et h ef u r t h e rr e s e a r c hp l a n k e yw o r d s ：t r a f f i ce n g i n e e r i n g t r a f f i cm a t r i xs h o r t e s tp a t h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得 的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得苤鲞盘茎或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 郑讳 签字日期：m年土月j g 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘鲎有关保留、使用学位论文的规定。 特授权苤盎盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 郑伟 签- 7 日期：耐年- 月旭日 导师签名：移矿嚅 签字日期：百年月f 黟日 第一章绪论 第一章绪论 近年来，随着i n t e r n e t 的高速增长和快速普及，网络同人们的生活和工作 已经密切相关。与此同时，i p 业务也得到了快速增长和多样化。特别是随着多 媒体业务的兴起，对计算机互联网络也就相应地提出了更高的要求。而且，网络 上需要传输的数据几乎以与网络发展速度相同的速度增加，甚至超过网络发展的 速度，因此网络资源总是相对有限的，瓶颈问题仍然存在。受到网络资源的限制， 对那些有带宽、延迟、延迟抖动等特殊要求的应用来说，现有的尽力而为( b e s t e f f o r t ) 的服务难以提供相应的服务质量( q u a l i t yo fs e r v i c e s ，q o s ) 保证。 而传统的i p 网络路由体系不具有全网资源利用的能力，会导致一部分网络资源 过渡利用，而另一部分被闲置。因此，网络上的业务量工程研究越来越引起人们 的关注。 本章简要论述了业务量工程的发展和研究现状，并对相关的理论内容进行了 简单的介绍，最后介绍作者的工作。 1 1 项目研究领域介绍 1 1 1 网络中的q o s 和资源充分利用问题 随着互联网的飞速发展和网络业务的丰富，互联网已成为承载多种业务、服 务于多类用户群体的公共信息传输平台。但是由于i p 协议固有的无连接特性和 传统i p 网络尽力而为的服务原则，传统互联网无法向用户提供有效的服务质量 保障，也不能实现网络资源的有效监控和管理。这种状况严重阻碍了互联网向纵 深方向发展。近十年来，针对 服务质量，研究人员提出了一系列理论和解决 方案。但是由于i pq o s 问题的复杂性，至今还没有一个q o s 方案能在大型商用 网络中全面推行。当前，“i p 电信网”已经成为各国电信主管部门和网络运营商 追求的目标，为了提供电信级的业务( 如v o i p 、视频和多媒体流传播、未来3 g 的无线应用、可视电话等) ，就必须面对和解决i p 网络的q o s 问题。目前对通信 网络q o s 的研究集中在i pq o s 体系结构、i pq o s 的资源管理机制及i pq o s 对 业务可管理性、可运营性的支持机制等问题上；特别是各大电信服务提供商，正 在积极开展电信级业务对i pq o s 的需求分析，研究i pq o s 的关键实现技术，以 及i pq o s 在现有i p 网络上的部署和实施技术。四】 i pq o s 的研究目标是有效地为用户提供端到端的服务质量控制或保证。q o s 就是网络单元( 例如，应用程序，主机或路由器) 能够在一定级别上确保它的业 第一章绪论 务流和服务要求得到满足。q o s 并没有创造带宽，只是根据应用程序的需求以及 网络状况来管理带宽。 业务的需求是动态变化的，而传统的i p 网络路由体系只能提供数据传输的 可达性服务，不具有全网资源充分合理利用的能力，这在很大程度上会导致网络 中传输的数据流可能会汇集到同一条链路上或同一个节点的同一个接口上，从而 导致网络的阻塞。阻塞的发生，并非全是网络资源不足，而是一部分资源被过度 利用，而另一部分资源被闲置。并且该阻塞主要发生在流量较大的骨干网中，而 在边缘网络中一般不会发生这种情况。 1 1 2 业务量工程 对于上面的问题可以通过业务量工程来解决。业务量工程( t r a f f i c e n g i n e e r i n g ，简称t e ) 是一种能将业务量映射到实际物理通路上，同时又可以 自动优化网络资源以实现特定应用程序服务性能要求的、具有宏观调节和微观控 制能力的网络工程技术。业务量工程对于大型网络来说是必不可少的，为了提高 竞争力和网络运营收益，获得网络最大操作效率是非常重要的。业务量工程使网 络运营商能够有效、可靠的控制网络内部的业务流量，充分利用网络资源，优化 网络性能。业务量工程的一个主要目的就是有效管理网络资源，优化网络资源的 利用，使得网络中的资源都得到全面合理的利用，尽量避免出现一部分被过度利 用而另一部分资源却没有被充分利用的问题。另一方面，网络资源如果能够预留， 则可以完成一定的流量控制的功能，从而满足用户提供端到端的服务质量控制或 保证。 1 1 - 3 业务量矩阵 在业务量工程的研究中，一个重要的内容就是关于网络业务量的测量，这同 时也是目前业务量工程研究过程的难点。在业务量测量中，实时、动态的获取 i p 网络中的业务量分布状况，即业务量矩阵( t r a f f i cm a t r i x ) 是非常重要的。 业务量矩阵反映了网络中源目的节点对之间的业务流量，它对于许多i p 网络的 管理任务十分重要，如：网络负载规划、业务量工程和网络可靠性分析。但是， 直接测量业务量矩阵是非常困难的，所以从链路负载统计数据或其他更简单的测 量数据中估算业务量矩阵是现在主要的方法。 1 2 课题背景 本论文的课题背景是基于m p l s 的流量工程的研究，研究内容主要包括m p l s 协议在网络服务质量保证、资源预留、准入控制等流量工程方面的研究，基于 m p l s 的流量工程和现有的o s p f 协议的流量工程的比较。 第一章绪论 其中本论文的主要内容是基于0 s p f 协议的业务量工程的研究，以0 s p f 协议 为基础，根据实际可以测得的网络数据估算业务量矩阵。 1 3 作者的工作 查阅研究现有的业务量矩阵估算算法的相关资料，根据现有的实验环境提出 一个估算和验证业务量矩阵的框架。 用n e t w o r ks i m u l a t o r2 仿真软件产生网络拓扑结构和网络流量数据。 用j a v a 语言编写业务量矩阵的估算算法，根据网络拓扑和链路流量数据估 算业务量矩阵。 将估算的业务量矩阵返回n e t w o r ks i m u l a t o r2 仿真环境检验算法的有效 性，并改进。 1 4 论文结构 论文第二章介绍了业务量工程的基本概念和相关理论知识；第三章论述了业 务量矩阵的知识和现有的几种业务量矩阵估算算法：第四章搭建了实验的框架， 使用n e t w o r ks i m u l a t o r 2 产生实验的网络拓扑结构和链路传输数据，并作为进一 步实验的输入数据；第五章设计、实现业务量矩阵估算算法，根据几种网络拓扑 结构和网络数据进行仿真实验，在数据结果基础上分析改进算法：第六章是全文 的研究结论，并对以后的研究和工作进行了展望。 第二章业务量工程 第二章业务量工程 2 1 业务量工程的定义和重要性 随着i p 网络的进一步发展，新出现的业务要求i p 网络不仅能可靠地传输信 息，而且要能对信息传输的过程具有可预见性。这就迫使i s p 改善网络基础设施， 使用更先进的交换机实现业务处理，采用宽带光纤介质满足高速数据传输的需 要。但是这只能在一定程度上缓解用户数据传输带宽和q o s 保证的压力，因为传 统i p 网络的路由体系，如内部网关协议( i g p ) 的o s p f 与r i p 、外部网关协议 ( e g p ) 的b g p 4 等，只能提供数据传输的可达性服务，不具有全网资源利用的调 节能力。这些算法的使用很大程度上导致了网络中传输的数据流可能聚到同一链 路上或者同一节点的同一接口上去。从而引起网络局部严重阻塞和网络资源利用 率大大下降。因此，当前采用这些算法的互联网根本没有动态的路由调整和灵活 的网络控制能力，更不用说对用户提供可预见的q o s 传输服务。业务量工程 ( t r a f f i ce n g i n e e r i n g ) 就是一种可用来控制网络资源、提高网络性能的技术。 2 1 1 业务量工程定义 业务量工程是一种能将业务量映射到实际物理通路上，同时又可以自动优化 网络资源以实现特定应用程序服务性能要求的、具有宏观调节和微观控制能力的 网络工程技术。它由网络拓扑结构、资源属性及可用性数据库、业务流量测量模 块、业务流量分布数据库、算法模块、调度控制模块组成，他们的关系如图2 1 所示。 其工作原理是：根据网络拓扑结构可以得到该网络的各条链路上可用资源数据 库，通过业务流量测量模块对网络拓扑各条链路进行测量得到业务流量分布数据 库，算法模块在特定时刻调用两个数据库的数据进行计算得到网络的运行情况， 如果阻塞就激活调度控制模块，根据一定规则对网络拓扑中的业务流量进行调度 第二章业务量工程 来排出网络阻塞。 1 8 】 业务量工程的研究主要涉及4 个方面的内容：对网络性能进行测量 ( p e r f o r m a n c em e a s u r e m e n t ) ；提取网络状态特征，对网络性能进行评价 ( p e r f o r m a n c ee v a l u a t i o n ) ；对网络性能进行优化( p e r f o r m a n c e o p t i m i z a t i o n ) ；阻塞控制( c o n g e s t i o nc o n t r 0 1 ) 。 实际上，业务量工程的提出是电信和计算机界要求网络不但要适应如w e b 那 样一般的数据传输服务，更要能应用于实时数据流的传输，尤其是音频和视频传 输。互联网业务量的指数增长迫使网络运营商提高网络资源利用率，新的应用则 要求网络提供具有o o s 保证的服务。就当前业务量工程的应用来说，它有两个关 键：负荷均衡与网络恢复。而i p 业务量工程的目的就是要解决如何有效地实现 尽力而为的传统i p 服务与q o s 的统一。 到目前为止，i p 网络只能提供可达性，而新应用要求的是高服务质量，例 如要在某域的入口和出口间建立一条符合q o s 要求的通路：当q o s 有保证的情况 下，可以同时应用尽力而为服务和q o s 业务服务方式，并且保证尽力而为服务质 量等级不会下降。而业务量工程也正是一种满足承诺的q o s 请求和高链路利用率 的控制技术，即通过平衡q o s 与网络中非q o s 资源的使用来实现网络性能的优化。 本质上说，业务量工程是一种网络控制技术，控制方法可分为两类：微层控 制与宏层控制( m i c r o l e v e lc o n t r o l ， 设备的功能是控制数据流层( f l o w m a c r o l e v e lc o n t r 0 1 ) 。微层控制网络 l e v e lc o n t r 0 1 ) ，主要包括准入控制 ( a d m i s s i o nc o n t r 0 1 ) 、策略控制( p o l i c i n gc o n t r 0 1 ) 、质量控制和阻塞控制。 宏层控制则是网络级的控制，用以解决微层控锖4 无法解决的问题。 2 1 2 业务量工程性能指标 业务量工程的主要性能指标可以分为两种： 1 面向流量 2 面向资源 面向流量的性能指标包括了增强流量q o s 功能的各个方面。在单一q o s 等级，尽 力而为的i n t e r n e t 流量模型中，面向流量的性能指标包括：对分组丢失的最小 化、对时延的最小化、对吞吐量的最大化以及对服务等级协定的增强等。在这一 流量模型中，使分组丢失最小化是最重要的性能指标。而在未来的区分服务的因 特网中，一些与统计数据有关的面向流量的性能指标( 如时延峰值变化、丢失率 等) 也将会越来越重要。面向资源的性能指标包括了优化资源利用的各个方面。 高效的网络管理是达到面向资源性能指标的重要途径。通常我们都希望能够确保 在其他可选路径上还有可用资源时，一条路径上的网络资源不会被过度的使用。 第二章业务量工程 带宽是当前网络上的一种非常重要的资源。因此，业务量工程的一项中心任务就 是对带宽资源进行有效的管理。无论是面向资源的还是面向流量的业务量工程， 它们首要的性能指标都是拥塞的最小化。这里所关心的拥塞主要是长时间的拥 塞，而不是由突发的流量所造成的短时间拥塞。 发生拥塞的情况主要有以下两种： 1 当网络资源不足以满足负载的要求时所发生的拥塞。 2 当业务流量与可用资源之间的映射效率不高时，导致一部分网络资源被 过度使用，而另一部分资源却未被充分利用时所造成的拥塞。 第一种类型的拥塞可以用以下方式解决：( 1 ) 对网络进行扩充，或( 2 ) 应用经 典的拥塞控制技术，或( 3 ) 同时使用以上两种方法。经典的拥塞控制技术是试 图对业务请求进行控制，从而保证业务能够和可使用的资源相匹配。用于拥塞控 制的经典技术包括：速率控制、窗口控制、路由器队列管理、流程控制以及一些 其他的技术。第二种类型的拥塞，即由于资源的不合理分配而引起的拥塞，通常 可以用业务量工程来解决。般来说，不合理的资源分配所造成的拥塞都可以通 过负载均衡来缓解。这类策略是通过有效的资源分配，减轻拥塞或者是减少资源 的使用，使得拥塞最小化，或资源利用率最大化。当拥塞最小化时，将减少分组 丢失，也将缩短传输时延，同时吞吐量将增大。这样，终端用户所感觉到的服务 质量将会有显著提升。显然，负载均衡是优化网络性能的重要策略。然而，提供 给业务量工程的策略必须是足够灵活的，以便网络管理员可以实现兼顾普遍成本 结构和效用、税收模型的其他策略。 2 1 - 3 业务量工程的重要性 业务量工程的一个主要目的就是在促进有效、可靠的网络操作的同时，优化 网络资源的利用率和流量的性能。由于网络资源的昂贵和因特网激烈的商业竞争 的本质，业务量工程已经成为大型自治系统中一个不可缺少的功能。这些事实都 说明有必要最大限度的提高运行的效率。 现在互联网上使用的复杂的控制功能已从网中移到终端，从而简化网络复杂 度，这种技术就是t c p ( 传输控制协议) 。t c p 是一种基于窗口策略的微层阻塞控 制法，它的基本观点是有了t c p 之后，网络不再参与质量控制，而只是完成简单 的传送功能。但随着互联网成为全球必不可少的通信基础设施之后，传统的t c p 已无法满足q o s 要求和业务量工程要求。 业务量工程是宏层控制技术，但它与电信业务量理论的网络工程又不相同。 业务量工程不依赖于特定的第二层技术。从应用的观点来说，当开发、设计和维 护一个网络时，为了保证网络设备数量和配置能满足性能要求，传统的电信网络 第二章业务量工程 工程利用通信工程理论去实现上述目的。 业务量工程对于大型网络来说是必不可少的，为了提高竞争力和网络运营收 益，获得网络最大操作效率是非常重要的。业务量工程使网络运营商能够有效、 可靠的控制网络内部的业务流量，充分利用网络资源，优化网络性能。业务量工 程的一个主要目的就是有效管理网络资源，优化网络资源的利用。要是网络中的 资源都得到全面合理的利用，尽量避免出现一部分被过度利用而另一部分资源却 没有被充分利用的问题。另一方面，网络资源如果能够预留，则可以完成一定的 流量控制的功能，从而满足用户提供端到端的服务质量控制或保证。 2 2 现有网络对业务量工程的要求 现有的因特网内部网关协议簇并没有提供业务量工程的能力。因此，很难针 对网络的性能问题实现有效的策略。事实上，基于最短路径算法的i g p s 是造成 a s 网络中的拥塞的主要原因。最短路径算法是简单的基于附加值的优化算法。 这些协议都是拓扑驱动的，因此它们都不考虑网络可用的带宽和流量的特征。当 出现以下情况时，就会发生拥塞： 1 多个业务流的最短路径汇聚到一条特定的链路或者路由器接口上时， 2 某条业务流的最短路径将通过某条带宽不足以支持该业务的链路或接口 时。 在这两种情况下，即使存在着拥有充足带宽的其他路径，拥塞仍然会发生。 这种拥塞问题( 资源未合理分配的症状) 正是业务量工程所要避免的。对于第二 种原因造成的拥塞，可以用“等开销路径负载分摊”技术来解决，但是对于由第 一种原因造成的拥塞，特别是对于拥有复杂拓扑结构的大型网络，这种技术就没 什么帮助。目前，解决i g p 协议簇的上述缺陷的较流行的方式是使用重叠模型技 术，例如i po v e ra t m 、i po v e l ”f r 等。重叠模型在网络的物理拓扑结构上提供 了一个自由的虚拟拓扑结构，从而扩展了网络设计的空间。这种虚拟拓扑结构由 虚电路构成，在i g p 路由协议看来，这些虚电路就相当于过去的物理链路。重叠 模型还提供了许多其他重要的业务来支持流量与资源控制，它们包括：( 1 ) v c 级的约束路由，( 2 ) 可由网络管理人员进行配置的显式路由，( 3 ) 路径压缩，( 4 ) 呼叫允许控制功能，( 5 ) 流量整形和流量策略功能，以及( 6 ) v c 的生存功能。 依靠这些功能可以实现许多业务量工程策略。例如，可以很容易的将过度使用的 网络资源上的业务流量转移到较为空闲的网络资源上。 业务量工程的使用目标是有效地映射数据流到现有的网络拓扑上去，达到网 络资源使用的最优化。为达到此目的，一种方法是增加网络的自适应功能，例如， 网络能适应其拓扑变化、负荷变化、故障等。另外，网络还能满足网络管理员定 7 第二章业务量工程 义的一些策略要求。业务量工程就是要实现网络操作的性能优化、网络使用的简 易性和可靠性，并满足用户的q o s 要求。 要实现有效的业务量工程，网络必须具有下面一些基本属性：简单性、可靠 性、可扩展性、互通性。 网络的性能优化本质上是一个控制的问题。在业务量工程中，由一位业务量 工程师或一台控制设备来充当一个自适应控制系统的控制者。该系统包括一系列 相互连接的网络元素，一个网络性能监测系统以及一整套网络配置与管理工具。 业务量工程师制定出一整套控制策略，利用网络性能监测系统对网络的状态进项 观察，然后对业务流量进行描述，最后通过控制措施使网络达到与控制策略相符 的、理想的状态。这一过程可以针对网络的现有状态实时进行，或者，借助预报 技术对网络状态的发展加以预测并采取相应的措施来提前进行。而后一种技术可 以提前避免网络产生不良状况。理想情况下，上述控制措施应包括： 1 对各种业务量管理参数的修改， 2 对与路由有关的参数的修改， 3 对与资源有关的属性与约束条件的修改。 如果可能的话，业务量工程的过程中应尽量避免手工参与。上述的控制措施 可以以一种分布式的，可扩展的方式自动完成。【2 4 】 2 3 基于路由控制技术的业务量工程 在9 0 年代初期，网络由一些路由器通过租用线路，如t l ( 1 5 m b s ) t 3 ( 4 5 m b s ) 链路互连起来。随着i n t e r n e t 爆炸性的增长，带宽需求和i s p 所能 提供的带宽之间的矛盾越来越突出，业务量工程对i s p 来说也就变得更加重要。 起初在核心路由网中，因为核心网路由器的数量并不多，业务量工程是靠调节路 由的度量来实现的。图2 2 给出了这种基于路由度量的业务量工程操作方法。 图2 2 图2 2 中，假设网络a 有大量的数据要传送到网络c 和d ，根据图中所示的 度量，链路a c 可能会发生阻塞，因为网络a 到网络c 和网络a 到网络d 的数据 都将在这个链路上传送，如果链路a d 上的度量改为2 ，那么从网络a 到d 的数 据将移到链路a d 上传送，但是从网络a 到c 的数据仍将从链路a c 传送，从而在 8 第二章业务量工程 不中断网络运行的情况下解决了通信链路的瓶颈。 2 4 基于i p a t m 叠加模型的业务量工程 基于传统路由器的业务量工程在扩展方面有很大的局限性： 1 ) 基于软件的路由器在负荷较大时有着潜在的流量瓶颈，因为它的带宽和 分组处理能力是很有限的； 2 ) 基于度量操作的业务量工程是不可扩展的； 3 ) i g p 的路由计算是拓扑驱动的，是基于简单的度量，比如跳数或管理员 赋予的一个值。i g p 并不根据业务量的属性给链路分配带宽或其它特性。因此转 发表中的链路仅仅表明有条通路可达对方，而通路的属性却无法确定。结果是 网络资源不会得到有效利用。 目前解决i g p 不完备所引起的问题较好的办法是使用叠加模型，如基于a t m 的i p 或是基于帧中继的i p 。叠加模型根据底层提供的实际物理拓扑，通过任意 的虚拟拓扑延伸了设计空间。虚拟拓扑是由虚电路建立的，这些虚电路对i g p 路 由协议来说，就像真实的物理链路一样。叠加模型还可以提供其它一些重要的服 务，以支持面向业务和面向资源的控制，主要有： 1 ) 在v c 级上基于约束的路由： 2 ) 支持显式v c 的管理配置； 3 ) 通路压缩； 4 ) 呼叫接受控制功能； 5 ) 业务调整与流量策略功能； 6 ) v c 的生存性。 这些新增的能力使各种业务量工程策略有可能实现。例如，虚电路可以容易 地重选路由，以便将一个过负荷网络的业务量转移到负荷较轻的网络上去。 1 9 9 4 1 9 9 5 年间，通信业务量的增长迫使i s p 不得不大规模提升主干网络 带宽，幸运的是，那时o c 一3a t m 接口已经达到商用化程度，i s p 于是重新设计 它们的网络，使得他们能使用由a t m 或帧中继交换机所支持的速度。一些i s p 在 d s 一3 点对点链路的网络中开始采用具有0 c - 3a t ms a r 接口的路由器，网络主干 则由a t m 构成。经过6 9 个月后，a t m 间的链路速率又提升到o c 1 2 。另一些 i s p 开始增加d s 一3 帧中继网络的互连密度，从帧中继转到a t m 时，他们依靠边 缘的o c 一3 ，但是到核心以后迅速采用0 c - 1 2 交换链路互连。 当i p 运行于a t m 网络时，a t m 边缘是路由器，每个路由器通过a t m 网的p v c 与另一个路由器进行通信。这里p v c 就是一条逻辑电路，连接任意两个路由器， 但路由器并不知道提供p v c 的a t m 基本物理拓扑信息如何，路由器所能知道的仅 第二章业务量工程 仅是每条p v c ，对它们来说就像是两个路由器间的点对点连接。 对一个大的i s p 来说，可能整个a t m 都是它自己建设的，因此它对整个网拥 有完全的使用权利，它就没必要做业务分类、业务整形、峰值率限制或流量控制 等。每条p v c 的实际物理通路由管理员按需配置，主要依据是链路容量和各链路 历史流量，最后的结果是在全网形成一个全网格状p v c 连接。 通过每条p v c ，任意两个路由器根据i g p 协议建立对等层关系，并相互交换 路由信息，同时也对每条p v c 按i g p 加上路由度量。 9 0 年代中期，a t m 为i s p 提供了解决日益增长的业务量负荷的带宽需求问题， 采用a t m 可以对网络流量进行控制。i s p 现在越来越依赖a t m 这种高速率的接口、 确定的性能，可见的p v c 操作管理。与传统的基于软件的路由器相比，a t m 交换 能提供更高速的接口和更大的带宽聚合能力，在一定程度上消除了核心路由器的 瓶颈。由于a t mp v c 事实上是一种显式路由，基于a t m 的核心网可作一定程度的 业务量工程调节。 a t m 曾经为i s p 带来了很大的效益，但是今天，它的很多功能都可以用高性 能路由器来实现。最新的路由技术让i s p 重新评价他们的网络，以确定他们采用 什么设备为用户提供服务。叠加模型在管理费用、设备费用和操作稳定性和扩展 性上都不如意。因为基于a t m 的叠加模型要求管理两个不同的网络：底层的基础 a t m 设施和重叠在其上的逻辑i p 网。两个叠加的网增加了网络管理的复杂性， 主要是由于路由的计算和流量的调节处在不同的网络环境中，两个不同的网络有 效协同操作也较难。另外，a t m 路由器接口与最新的光纤带宽的增长也不能保持 一致。其次，面向分组的协议要转换到a t m 信元传输，将引入约2 0 的信头开销， 于是，对2 4 9 9 g 的0 c 一4 8 接口，只有1 9 9 g 传送数据，而4 9 9 m 用在信头开销上， 这几乎是一条0 c 一1 2 的带宽! 还有，全格状网的p v c 配置带来了传统的n 平方问 题。总之，最初使用i p o v e r a t m 的条件现在已逐渐消失。于是人们又去寻找新 的办法来解决网络业务量工程问题。由于路由算法是实现客户数据流正确传输的 基础，所以新的业务量工程方法要求必须是基于路由算法。| 2 4 j 2 5 基于肝l s 的业务量工程 i n t e r n e t 主要由两种类型的计算机网络构成：基于i p ( i n t e r n e tp r o t o c 0 1 ) 的网络和基于a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) 的网络。a t m 网络的主要优 点在于它的高性能和业务管理能力，而高可扩展性和灵活性是i p 网络的主要优 点。但这两种网络中的任何一种都无法提供另一种所具备的全部优点。为了实现 这两种类型网络优势的融合，i e t f 建立了m p l s 标准化组织来实现这一目标。 m p l s 引入了一种基于固定长度标记的面向连接的转发方式。这种固定长度 第二章业务量工程 的交换概念与a t m 和帧中继网络相似，但也有区别。m p l s 目前应用于基于i p 的 网络。在o s i 网络七层参考模型中，m p l s 处于数据链路层和网络层之间的位置。 帅l s 在将面向连接的概念引入无连接的i p 网络的同时，也提供了在这些网络中 进行业务量工程和业务量管理的新方法。a t m 网络中的电路交换( 虚电路) 模型 拥有带宽预留、性能管理以及业务量管理等优点。m p l s 为i p 网络提供了电路交 换模型的这些优点，同时保持了i p 网络中固有的可扩展性和灵活性。 业务量工程是m p l s 最重要的应用之一。在m p l s 网中，对给定l s p 路由的建 立过程有两种方法：h o p - b y h o pl s p 和显式路由e r l s p 。 m p l s 能提供灵活的网络操作能力，它使用严格的和松散的显式路由去管理 网络数据流的传输。对于要求高的业务流，它可以使用严格路由方法保证数据的 有效传输。松散路由则提供传输路由和重选路由的灵活性，并减轻了对网络配置 的要求。 w a n 连接对一个i s p 来说是很昂贵的，业务量工程使i s p 能控制网络业务量， 使得它们在时延和吞吐量方面提供最好的服务。m p l s 业务量工程提供了一种能 达到叠加网模型相同效果的业务量调节方法，而不需要对网络分开运行，也没有 全连接的无扩展能力的路由器的局限性。 业务量工程在网络中的应用范围取决于该技术的成熟程序以及用户应用程 序的要求，它即可用在内部域中，也能在几个i s p 间联合使用。采用域问的业务 量工程时可使它发挥最大的效果。田1 第三章业务量矩阵估算算法 第三章业务量矩阵估算算法 3 1 业务量矩阵介绍 业务量矩阵在现在的i s p s 网络的业务量工程中有十分重要的意义，业务量 矩阵对于预测未来客户的带宽需求、发现目前网络状态下的带宽瓶颈，网络协议 的设计和规划、网络路由重新生成和发现网络资源滥用都有重要的作用。 一个业务量矩阵表示了网络中源目的节点对之间传输的业务量，在现在的 网络中，源目的节点对可以是p o i n t s t o p r e s e n c e ( p o p s ) ，路由器或者链路。 业务量矩阵、路由矩阵和链路负载可以用下面的线性公式系统表示： y = 删， 其中y 表示链路负载向量，x 表示业务矩阵向量，a 表示路由矩阵( a 矩阵中：如 果源目的节点对j 的传输路径上包括链路i ，则a 矩阵元素a ，等于1 ，否则等 于o ) 。【l 】 3 2 业务量矩阵计算方法 业务量矩阵的计算可以分为直接测量和数据估算两种。 3 2 1 业务量矩阵的直接测量 最直接的方法就是直接测量所求的网络节点间的业务量，但是由于网络规模 的日益扩大，没有统一的测量基础设施，收集、存储、同步和处理相关的大量的 信息有困难，直接测量的方法只适合于小型的简单的网络，对于大型的、全球性 质的网络环境在近一段时间内还不适用，因此研究者们转向数据统计技术来获得 网络的业务量矩阵。 3 2 2 业务量矩阵的数据估算 业务量矩阵估算就是根据可以获得的网络数据信息，通过一定的算法估计推 算出网络的业务量矩阵。如前面的业务量矩阵公式y = 丘z 中，在今天的网络环 境中y 和a 是可以测量获得的，链路负载y 可以通过标准的s n m p 测量数据获得， 路由矩阵a 可以通过网络拓扑结构信息和i g p 链路权值在一定路由协议下计算， 则根据公式就可以估算出业务量矩阵了。 3 3 业务量矩阵估算协议选择 这一节介绍一下路由协议的选择，在现有的研究工作中，大致有两种协议 第三章业务量矩阵估算算法 传统的最短路径协议o s p f 和多协议标记交换m p l s 。下面详细的介绍一下这两个 协议及其在业务量矩阵计算中的应用。 3 3 10 s p f 协议 o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 是一个内部网关协议( i n t e r i o rg a t e w a y p r o t o c o l ，简称i g p ) ，用于在单一自治系统( a u t o n o m o u ss y s t e m ，a s ) 内决策路 由。与r i p 相对，o s p f 是链路状态路有协议，而r i p 是距离向量路由协议。在 这样的路由协议中，每条链路设置了一个正的链路权值，将一条路径上所有链路 的权值的总和定义为这条路径的长度，业务量会选择路径长度最短的路径传输。 传统的o s p f 网络路由协议和路由算法所提供的控制能力不能胜任流量工程 的要求。这是因为这些拓扑驱动协议在进行路由时没有考虑资源约束状况以及业 务流量的特性。基于链路权值的流量控制在网络规模和用户的迅猛增长下，难以 应付网络中巨大的数据流传输的要求。【7 】 基于o s p f 路由协议的业务量工程中的获取业务量分布状况的业务量矩阵是 目前研究的一个难点和热点问题。由于动态地或直接地测量获取业务量矩阵的困 难，一些业务量工程采取业务量预测的方法来生成长期性的业务量矩阵，再采用 某些测量技术对其进行一定的修正。但是通常基于预测的业务量矩阵不能准确地 表征网络中实际的业务量分布情况，以此为基础的修正也就难以保证其结果的准 确性，再实施业务控制和负载平衡时就可能造成误差。还有人提出不需要了解网 络拓扑结构和路由信息，而是选用h a s h 采样函数，生成测量数据包，进行业务 量矩阵的测量，但是准确选取一个能够代表所有网络中传送的业务流的数据包子 集和一个合理的h a s h 函数十分困难。还有一些系统采用基于流的测量方式，在 i p 网络的接入边界进行业务量级的测量，然后根据测量结果估算出网络业务量 矩阵，但是这样做测量量和所耗资源是巨大的，在保证提取的路由信息实时性和 准确性上有困难。1 2 知 虽然在o s p f 路由协议上进行业务量工程有很大的困难，但是研究者们还是 在现有的网络上想到了很多办法，取得了一定的成绩。如：c i s c o 路由器的默认 设置是把链路的权值设为链路带宽的倒数。 3 3 2 - 删l s 协议 m p l s ( m u l t i p r o t o c o ll a b e ls w i t c h ) 最初是用来提高路由器的转发速度 而提出的一个协议，但是由于m p l s 在流量工程( t r a f f i ce n g i n e e r i n g ) 和v p n 这一在目前i p 网络中非常关键的两项技术中表现，m p l s 已日益成为扩大i p 网 络规模的重要标准。m p l s 协议的关键是引入了标签( l a b e l ) 的概念。它是一种 l3 第三章业务量矩阵估算算法 短的易于处理的、不包含拓扑信息、只具有局部意义的信息内容。l a b e l 短是为 了易于处理，通常可以用索引直接引用。只具有局部意义是为了便于分配。 基于m p l s 协议的业务量矩阵生成应该属于基于路径的测量方式。这里的路 经指的是m p l s 的l s p 。由于m p l s 支持显式路径，因此可以从每个l s p 上测量业 务流量，而只需要在网络边界进行，然后得到网络拓扑结构和e r l s p s 路径信息 进行计算，从而得到网络中任意一个节点对之间的业务量，而整个网络的业务量 矩阵。但是目前 l f i p l s 协议的应用不够普遍，大部分的网络还是o s f p 路由协议， 这就是它的局限性。 3 4 业务量矩阵估算算法研究 业务量矩阵对于业务量工程十分重要，但是基于现有的网络技术直接测量计 算业务量矩阵几乎是不可能的，所以研究者们针对利用尽量少的网络测量数据来 估算业务量矩阵进行了大量研究，得到了很多成型的技术和算法。 3 4 1 重力模型( g r a v i t ym o d e l ) 重力模型是最简单一种计算业务量矩阵的方法，它的名字来源于牛顿的地球 重力定律，通常被社会科学家用来模型化地区地域间人口、货物或者信息的流动， 在牛顿的地球重力定律中，两个物体之间的力，与两个物体的重量的乘积比上它 们之间的距离的平方成一定的比例关系，则简单的城市之间的重力模型就是，两 个城市之间的交互作用强度可以模型化与两个城市人口数量的乘积成一定的比 例关系。通常的重力模型公式如下： 弘半， 其中x 。代表了矩阵元素中f 到，的力，r 。代表了和“离开”舛目联系的排斥因素， 一，代表了和“去向”j 相联系的吸引因素，f ，代表了从i 到，的摩擦因素。【2 在业务量矩阵估算研究中，通常把工。解释为从i 点进入网络，从f 点离开网 络的业务量；把排斥因素胄