（通信与信息系统专业论文）forces通道传输方案及性能模型研究.pdf

f o r c e s 通道传输方案及性能模型研究 摘要 f o r c e s 架构的路由器是实现了控制件和转发件分离的路由器， 它可以很好地适应了下一代网络对路由设别的需求。为了提高网络的 总体性能，本文研究了f o r c e s 路由器系统的端到端通信性能用以指 导f o r c e s 路由器的设计。 本文首先研究了f o r c e s 的传输通道t m l ( 传输映射层) 的通信 结构，在确立s c t p 作为f o r c e s 系统内部传输协议的基础上，建立 了一个通过两级调度实现c e 和f e 数据转发控制的端到端的性能参 考模型。针对该模型，我们基于网络演算获得了作为输入源的 o no f f 马尔科夫调制过程的数据包络，然后采用先纵向后横向的分 解方法成功分解了这个两级调度系统，并从单级s p 调度和p g p s 调 度系统性能得到了两级调度系统的总性能，接着我们通过合理的假设， 得到了s c t p 拥塞避免控制算法a i m d 的流量模型。最后，我们依次 求解发送端，网络以及数据接收端的性能，并得到了系统的端到端性 能。 最后通过对理论计算结果的研究，来指导f o r c e s 路由器系统的 设计及规划。 关键词：f o r c e s ，网络演算，两级调度，服务曲线，a i m d f o r c e sc h a n 1 姬lt r a n s m iss i o ns c h 匝m e a n d1 p e r f o r 【a n c em o d e l a b s t r a c t f o r c e sb a s e dr o u t e ri st h er o u t e rt h a th a v ea c h i e v e dt h es e p a r a t i o n o fc o n t r o la n df o r w a r d i n gc o m p o n e n t s ，i tc a np e r f e c t l ys a t i s f yt h en e x t g e n e r a t i o nn e t w o r k i no r d e rt oi m p r o v et h eo v e r a l lp e r f o r m a n c eo f n e x t g e n e r a t i o nn e t w o r k s ，t h i sp a p e r s t u d i e dt h ef o r c e sr o u t e r e n d - t o - e n dc o m m u n i c a t i o ns y s t e mp e r f o r m a n c et o g u i d et h ed e s i g no f f o r c e sr o u t e r s t h i s p a p e r s t u d i e dt h et r a n s m i s s i o nc h a n n e lf o r c e st m l ( t r a n s p o r tm a p p i n gl a y e r ) c o m m u n i c a t i o ns t r u c t u r e a f t e rg e t t i n gs c t p a si t st r a n s p o r tp r o t o c o l ，ar e f e r e n c ee n d t o e n ds y s t e mw a se s t a b l i s h e di n w h i c hat w o s c h e d u l i n gs y s t e mw a sd e s i g n e d t oc o n t r o lt h ed a t a f o r w a r d i n gb e t w e e nc ea n df e a sf o rt h em o d e l ，w eo b t a i nd a t a e n v e l o p eo fa ni n p u to fo n o f fm a r k o vm o d u l a t i o nb a s e do nn e t w o r k c a l c u l u s t h e nw e g e tt h ep e r f o r m a n c eo ft h et w os c h e d u l i n gs y s t e mf r o m t h ep e r f o r m a n c eo fs i n g l es pa n dp g p ss c h e d u l i n g s y s t e mu s i n gt h e v e r t i c a lh o r i z o n t a l d e c o m p o s i t i o nm e t h o d t h e nw eg e tt h ed a t a f l o w m o d e lo fs c t pc o n g e s t i o na v o i dc o n t r o l a l g o r i t h mu n d e rar e a s o n a b l e a s s u m p t i o n a tl a s t , w eg e tp e r f o r m a n c eo fe n d t o e n ds y s t e mt h r o u g h s o l v i n gt h et r a n s m i a e r , t h en e t w o r ka n dt h er e c e i v e r f i n a l l y ，w es t u d i e dt h et h e o r e t i c a lr e s u l t st og u i d ea n dp l a nt h e d e s i g no ff o r c e sr o u t e rs y s t e m k e y w o r d s ：f o r c e s ；n e t w o r kc a l c u l u s ；t w os c h e d u l i n g ；s e r v i c e c u r v e ； a i m d 4舢8删0 舢0702肼y 符号对照表 s p 级调度的到达曲线和服务曲线分别为( ，) 和( ，) 五是信号源从o n 状态转移到o f f 状态的概率 是信号源从o f f 状态转移到o n 状态的概率 s p 级调度的数据积压和传输延迟分别为和 p g p s 级调度的到达曲线和服务曲线分别为叫( f ) 和犀删( f ) p g p s 级调度的数据积压和传输延迟分别为和， 分解模型后的各s p 队列的p g p s 级调度的数据积压和传输延迟为彬和 每个队列的到达过程是a 。( f ) ，五和是到达过程o n o f f 的状态转移概率 每个s p 队列的数据到达总量为4 两级调度总的数据积压和传输延迟为岛和岛 v l i 1 1 课题研究背景及意义 1 绪论 f o r c e s 路由器是基于f o r c e s 协议的新一代路由器，它是基于开放式体系架 构设计的。它与目前路由器的最大区别在于它的转发件与控制件的分离，开放式 架构的模块化设计，通过加速模块设计的分工，降低模块之间的耦合度，为业务 的可重构提供了重要的技术保障【l 】。作为网络中转的主要节点，路由器内部通道 的传输性能，关系着整个网络的传输性能，由此可见合理的f o r c e s 通道传输方 案是发挥网络整体性能的关键。目前各f o 疋e s 工作组对f o r c e s 通道内和各通道 间的数据调度算法都有了一定的研究，这些调度算法基本上是从传统的调度算法 改良而来的，当然也有一些算法是根据具体的应用场景而设计的，但其中的大部 分算法都比较复杂，以至于它们很难被使用。目前针对于这些调度性算法的性能 研究只局限于仿真，都还没有进行深入的理论研究，仿真也只局限于单层调度算 法，不能很全面地反应出整个f o r c e s 路由器传输通道的整体性能，所以我认为 从实际的f o r c e s 通信模型出发，建立一个全局的两级调度模型，并对其端到端 通信模型进行性能分析是很有必要的。 网络演算是网络通信领域取代传统排队论分析方法的新兴的网络性能分析 方法，是最小加代数和最大加代数在网络性能分析中所取得的有用的研究结论的 集合。网络演算是“奇异代数”( e x o t i c a l g e b r a s ) 的最新发展成果。这些代数主 要应用在以下这么领域：多处理器的并行计算、队列消息传递的并发、传输网络 中的数据调度。与传统排队论的分析方法相比，采用网络演算理论所建立的模型 具有与实际业务模型更高的拟合度，能更好的反映出业务模型的特性，它比排队 网络模型更简洁明了，也能得到实用性更强的分析结果【2 】。特别是在端到端网络 性能的分析中，网络演算有着传统的排队网络分析不可比拟的优势，所以我认为 采用网络演算理论对f o r c e s 通道方案进行建模是很有指导意义的。 f o r c e s 传输通道方案可以认为是一种两级调度，我们可以利用网络演算理 论的分析结论来指导我们进行传输映射层传输协议的选取和各级调度算法的确 定，以达到系统的性能要求，在硬件方面，我们可以通过网络演算理论的分析得 i 到的基本性能参数，最小缓存，时延抖动，最大延时来选择合适的硬件，尽可能 提高系统资源利用率和方案性价比。 1 2 国内外研究现状 1 2 1t m l 通道传输方案研究现状 自从2 0 0 1 年第一个f o r c e s 工作小组成立以来，越来越多的学者开始了从控 制和转发分离的角度对新一代分布式路由器的标准协议和各种技术进行研究。到 目前为止，工作组的研究任务已基本完成，除了已经通过的8 个r f c ，还有多个 在研草案。这8 个已经通过的r f c 分别为r f c3 6 5 4 ，r f c3 7 4 6 ，r f c 5 8 1 0 ，r f c 5 8 1l ，r f c5 8 1 2 ，r f c5 8 1 3 ，r f c6 0 4 1 和r f c6 0 5 3 ，本课题组参与制定了其中 的多个r f c 标准，并且还为其它的r f c 的修订提供了许多宝贵的意见【3 】。 随着作为f o r c e s 需求的r f c3 6 5 4 和作为框架的r f c3 7 4 6 标准的最终确立， k 2 0 0 4 年初，本课题组向i e t f 提交了g r m p ( g e n e r a lr o u t em a n a g e m e n tp r o t o c 0 1 ) ， 与此同时i n t e l 和n o k i a 联合提交了f a c t ( f o r w a r d i n ga n dc o n t r o le l e m e n t p r o t o c 0 1 ) ，z y n x 和i b m 则共同提交了n e t l i n k 2 ( n e t l i n k a sf o r c e sp r o t o c 0 1 ) ，经 # 过多次会议讨论，i e t f 最终决定通过整合这三个候选协议来形成了最终的 f o r c e s 协议，并决定成立一个7 人协议工作小组( 其中有两人属于本课题组) 来进行协议的整合及完善工作。设计小组经过多次提交协议草案，并多次修改完 善，使得f o r c e s 协议草案在2 0 1 0 年3 月被正式批准成为标准类r f c5 8 1 0 。这 是大陆学者完成的仅有几个标准类r f c 之一，对中国在国际互联网标准制定方 面具有重要意义。 2 0 1 0 年3 月，标准类r f c5 8 1 l 正式通过，并确定使用s c t p 传输f o r c e s 内的协议消息，其最初草案是由j h a d is a l i m 和n t t 的k o g a w a 等人在2 0 0 4 年提交的，其中详细分析了使用s c t p 的原因。 随着f o 疋e s 相关的r f c 标准的不断通过，以及f o 厄e s 协议运用的巨大潜 力彳i 断展现，越来越多的国内外研究机构和企业开始了对相关技术的研究，这有 利地促进了f o r c e s 架构路由器的产业化进程。 f o r c e s 通道传输方案由两部分组成，其中第一部分就是t m l 采用的传输协 议，t m l 的协议类型确定了单f e 内的通道模型，第二部分是f e 各通道间和各 2 f e 之间的调度策略，这两部分起就构成了整个f o r c e s 通道传输方案。t m l 是f o r c e s 路由器内部数据传输的主要通道，它是c e 和f e 之间协议消息的传 输的唯一通道，而t m l 所采用的传输层传输协议，一直都是相关研究机构研究 的核心问题。t m l 通道采用的传输协议一直跟随着f o r c e s 的发展而不断变化着， 而f e 各通道间的调度策略却一直比较简单，这和调度策略简单，易行的要求有 一定关系。 r f c5 8 1 1 描述并分析了使用基于s c t p 协议的传输架构p 】，除此之外，t m l 还有曾经有过以下几种传输架构： 1 1 由k h o s r a v i h ，c h a w l a s 等人提出的基于t c p 协议和d c c p 协议的传 输架构，该架构分别采用t c p 协议和d c c p 协议，来传输控制通道消息和数据 通道消息。 2 ) 由m h i d e l i 等人提出的基于t c p 和u d p 的t m l 传输架构，这是他们 在研究了t c p + d c c p 传输架构的基础上提出的，该传输架构使用t c p 和u d p 来传输控制通道消息和数据通道消息。 3 1 在2 0 0 4 年，j m a l o y 提出的使用t i p c 作为t m l 中的传输架构，他还对 该架构如何保证t m l 的性能做了详细的论证。 1 2 2 网络演算的研究现状 网络演算是针对网络流量问题的研究所取得的有用结论的集合，它为网络模 型性能的定性和定量研究提供了一种全新的方法，目前该理论还处在不断完善的 阶段。基于概率论，排队论的传统建模分析方法，其所得到的网络传输性能与通 信量的到达过程的流量特性和节点的配置参数有着强关联性，这严重阻碍了研究 者对网络模型进行精确的性能分析。网络演算理论就是为了解决这个问题而产生 的，它用一定的规则约束来描述一个节点的数据到达特征，也就是说它使用一个 确定的数据包络替代了以往存在概率因子的随机到达过程，并且在网络节点概念 的基础上研究了数据包调度算法延迟，最小缓存需求以及带宽利用率等多项性能 的上界，并给出了以上几个参数的确定性解，它与使用排队论分析方法所得到的 近似解是不同的，该理论为q o s 控制理论的发展提供了全新的思路。1 9 9 0 年， c r u z 等在文献【4 e p 提出- j 务曲线的概念，随后，由规则约束变化而来的到达 曲线和农述节点服务能力的服务曲线成为了网络演算理论的两个基本工具。l e 3 b o u d e e 等人在分析解决实际问题的过程中，把最小加代数理论引入到了网络演算 理论，发展和扩充了网络演算这一概念。 网络演算理论最能有效的进行网络模型性能分析，它能推导出当网络处于极 端情况下，缓冲区内的数据积压和数据传输延迟的上界，从而为用户提供严格的 q o s 保证服务。这就是发展比较早的确定性网络演算，但是，在实际的网络环境 中，被考察的网络对象很少能处于这种极端状况下，尤其是在一些调度比较集中 的网络中，这种情况几乎不会出现，因为相互独立的数据流之间存在着的统计复 用的现象，而该现象会平滑突发概率的出现，反之，确定性网络演算却会使得概 率的突发性增加。这使得研究者进一步发展了网络演算，他们把传统概率论融入 到确定性网络演算中，在保留确定性网络演算基本元素的基础上又利用了统计多 路复用技术来分析网络，这就是统计网络演算【5 j 。统计网络演算中，有效到达曲 线和有效服务曲线都是一定概率下的规则约束。随着网络演算理论的不断扩展， 网络演算在实际中的运用也逐步深入，它主要运用在虚拟交换网络，保证服务网 络和汇聚调度网络领域中的保障q o s 控制，调度与缓存分配策略等方面。网络演 算的研究主要集中在各种业务模型，网络整流元素的建模和性能分析方面。 文献 6 】【7 基于网络演算研究了通信景整形器的一般模型，获得了贪婪无损 整形器，无缓冲整形器和固定缓冲整形器的数据流量模型和输出流量特性，给出 了流量整形器的分组丢失数、分组传输延迟与数据积压之间的关系，给出了这些 量在最小加代数中的关系式，得出了在一些特殊情况下，贪婪整形器可以用来改 善网络的服务质量。文献【8 】比较了在t c p u d p 环境中，基于传统数据流模型， 数据包模型以及网络演算模型在仿真中的执行时间，错误发生率等的差异，确立 了网络演算模型在仿真中的优势。文献【9 】归纳了网络演算基本理论的一些基本 定理和性质，推导了了使用漏桶调节器的通用处理器共享系统模型，并基于该模 型求解了该系统模型的数据积压，数据传输延迟以及有效带宽的性能边界的解。 实例分析的结果表明，利用嘲络演算理论分析提供保证服务的网络性能边界问题 时，有很好的拟合度和实用性。文献【l o ul 】基于网络演算推导出任意拓扑无损 网络使用加速转发每跳行为的端到端延迟抖动和节点的数据积雎。文献【1 2 】基于 网路演算推导了两个网络的联接处节点的最佳缓冲区大小。文献【1 3 采用幂等矩 阵的理论描述了到达曲线和服务曲线，演算的过程成为矩阵运算，通过结合矩阵 4 双子理论和余理论的研究结果，得出了矩阵演算的基本定理研究表明，幂等矩 阵理论为网络演算提供了很好的理论解释。文献【1 4 】得出了服务曲线存在瓶颈效 应、端到端延迟的理想与近似确定性上界、提供保证服务网络节点的服务曲线需 求等结论，计算了服务曲线以速率等待时间及p g p s 形式表示的保证服务端到端 延迟确定性上界。文献【1 5 】基于网络演算扩展了受限流的分析方法，得到了更一 般的聚集调度数据流的特性以及相应的q o s 性能界限。 文献【1 6 】得到了以指数边界流量模型作为输入的网络模型的性能上界。文 献【1 7 】基于网络演算，通过对数据进行基于优先级的调度和在源节点对非周期数 据进行通信量整形，推导了交换机等网路节点的服务特性，并在一个实际的以太 网环境中，求得了网络中实时数据的最大传输延迟。文献【l8 】则从一个具体的控 制网络拓扑出发，基于网络演算推导了各种不同网络拓扑下，网络节点间的点到 点的传输延迟。 此外，研究者们还基于网络演算求解了数据传输延迟和数据积压的性能上界， 利用随机排序的概念，求得了f i f o 调度网络中数据流的网络传输延迟和数据积 压上界，基于网络演算给出了输出突发特性和传输延迟的概率分布，同时也对队 列延迟和端到端延迟进行了研究，其中的一些结果使用在e d f 、g p s 以及其他调 度算法中【5 1 。 1 3 本文的研究内容 在r f c 5 8 1l 中，f o r c e st m l 中的标准传输协议是流控制传输协议s c t p ， 本文基于单c e 和多f e 交互的实际场景，确立了f o r c e s 通道的传输方案，并 建立了一个f o r c e s 路由器的端到端参考模型，用网络演算的方法对端到端系统 的性能进行深入研究，文中主要研究了以下内容： 1 ) 研究了f o r c e s 传输通道t m l 通信模型结构 t m l 通信模型是研究f o r c e s 路由器内部通道流控技术的基础，针对具体的 s c t p 协议，本文根据各个通道的传输需求，确立了f o r c e s 通道的传输方案。 2 ) 研究了s c t p 协议拥塞避免机制的流量模型 与传统t c p 协议类似，s c t p 协议中拥塞避免的丰要机制是a i m d ，本文从 该机制出发，通过对网络环境的合理假设，求解得到了a i m d 算法在网络处于 拥塞状况下的流量模型。 3 ) 研究了基于数据包的s p 调度和p g p s 调度算法的流量模型 在端到端的参考模型中，发送端c e 内部是一个基于数据包的s p 和p g p s 的两级调度系统，本文从数据流调度系统出发，通过数据流调度模型和数据包调 度模型的比较，得出了基于数据包调度的s p 和p g p s 算法的流量模型。 4 ) 研究了两级调度系统的分解 发送端c e 内部的两级调度系统并不能直接用网络演算理论进行分析，所以 采用适当方法对这个两级调度系统进行分解是必须的。本文采用先纵向再横向的 方法成功分解了系统，并使用网络演算理论从两个单级调度系统的性能分析得到 了两级调度系统的整体性能。 1 4 本文的组织结构 本文共分为六章，内容安排如下： 第一章为绪论，首先介绍了本课题的研究背景，然后介绍了f o r c e s 及其通 道传输协议的研究现状，网络演算的研究现状，在此基础上，提出了本文的研究 内容和组织结构。 第二章对网络演算的基本理论知识，最d , ；0 i 代数，最大加代数进行了介绍， 并对网络演算理论中一些常用的概念进行了介绍，具体包括了确定性网络演算和 基本工具以及网络演算中的两种常用模型，输入源和网络模型。 第三章先研究f o r c e s 路由器的体系结构，然后对其中的t m l 通信结构进 行了研究，在此基础上，我们对t m l 中采用的通信协议s c t p 的特性以及它的 拥塞控制机制进行了详细的介绍，并得出了慢启动算法a i m d 拥塞避免算法的 流量模型。 第四章先介绍了基于数据流的g p s 和s p 调度算法的流量模型，通过实际例 子分析了g p s 和s p 基于数据流调度和数据包调度的区别，并在此基础上获得了 基于数据包的s p 调度和p g p s 调度算法的流量模型。 第五章基于一个实际应用场景建立了端到端的参考模型，对每个通道的输入 源进行建模，通过分解两级调度系统和求解嘲络环节，f e 接收端的传输性能， 完成了端到端性能的计算，并进行了数据分析。 6 望。 第六章先总结了当前研究情况，并对有待进一步加深的研究t 作做了一些展 2 1 概论 2 网络演算理论基础 在高速网络领域，经常需要定性或定量估计网络拓扑变化以及负载变更对当 前网络性能产生的影响，或者通过对当前网络情况作推广以预测未来网络的情况。 以往，概率论、随机过程以及排队分析模型等理论和应用工具是比较常用的方法， 这些传统理论在实际运用中取得了一系列良好的成果，同时也暴露出很多不足之 处。网络q o s i h - j 题的研究随着网络确保服务的提出曰趋活跃，为了满足不断变化 的网络q o s 需求，研究者们提出了许多数据包调度算法和队列管理算法来实现 q o s 控制，由此网络q o s 理论不断发展扩充，而网络演算理论也就是在这种形势 下f l t c h a n g 以及c r u z 创立并由l eb o u d e c 和a g a w a l l 等人进一步发展起来并期待完 善的q o s 理论。 网络演算是近年来研究者用最小加代数和最大加代数来对网络通信流问题 进行深入研究所取得的一些有用结论的概括。网络演算是奇异代数( e x o t i c a l g e b r a s ) 中的一种，它的应用范围主要是多处理器的并行计算、共享通道的消息 调度以及通信网络中的消息传递等。根据其理论基础的不同，网络演算可以分为 确定性网络演算和统计网络演算这两类。下面是它们之间的一些异同点：确定性 网络演算使用到达曲线和服务曲线求解网络的性能边界，其中的到达曲线和服务 曲线都是基于确定性的函数曲线，它适合用来求解性能边界的精确值( 单通信流 的传输延迟和数据积压上界) ；而统计网络演算主要用来解决网络性能的概率或 统计边界问题，它所使用的有效到达曲线和有效服务曲线是基于一定概率的函数 曲线，相对于确定性网络演算，它有利于数据流的统计复用开发，以提供网络节 点的资源利用率。 作为一门新兴的学科，目前网络演算的研究主要集中在网络演算理论以及网 络演算应用的研究这两大方而。在网络演算理论方面，文献【1 9 x , j 确定性网络演 算进行了全方位地阐述，介绍了网络演算的一些理论知识，以及它们的适用场合。 文献 2 0 ! j ! t j 在文献【1 9 】的基础上对确定网络演算一些最新的分析结论进行了概括 和总结。文献【2 l 】成功地在l g e n d r e 域中使用了确定网络演算，扩展了它的使用域。 虽然确定性网络演算成功替代了传统排队分析方法，但确定例络演算有着很强的 8 局限性，它只能求解处于一些特殊情况下的网络传输性能，但是网络出现这种情 形的概率很低，尤其是当网络上传输的是相互独立的数据流时，概率的突发性会 不断被平滑，如果在这种情况下使用确定性网络演算，那会导致过我们过高估计 资源的需求，进而浪费网络资源。因此，文献【2 1 】基于传统的概率论，提出了有 效到达曲线和有效服务曲线的概念，并由此衍生出了统计网络演算。网络演算的 应用研究主要在以下几个方面，虚拟交换网络、服务保证网络和调度集中网络领 域中的q o s 控制、数据传输延迟计算、数据调度以及缓存分配策略等方面。 上述是前人对网络演算的一些研究，为了本文的研究和论述之便，本章重新 归纳了网络演算理论的一些基本性质和基本定理，这其中包括了以下三方面主要 内容l 、网络演算理论的数学基础。2 、确定网络演算的基本工具。3 、基于确定 性网络演算的基本性能模型等，扩展的网络通信流体模型及其属性【5 1 。 2 2 最小与最大加代数 2 2 1 最小加代数 最小加代数是专门用于数字电路、通信网络以及制造工业等离散事件系统 ( d i s c r e t ee v e n ts y s t e m s ) 建模的一个数学分支。后来，许多研究者不断地丰富与 扩充它的内容，使它有了今天这样的广泛运用。相比传统代数结构，它使用了一 些特有的概念和符号。传统代数的代数结构为( r ，+ ，) ，其中尺表示实数域，“+ ” 和“”分别表示加法运算和乘法运算；而最小加代数的代数结构为 ( r u + ，a ，+ ) ，其中“ ”和“+ ”分别表示求最小运算“i n f ”和加法运算，并 且满足( 厂 g ) ( f ) = m i n f ( t ) ，g ( f ) = i n f f ( t ) ，g ( ，) ) 采1 ( 厂+ g ) ( f ) = ( f ) + g ( f ) 。 也就是说，在最小加代数中求最小运算“a ”替代了传统代数的加法运算，而乘法 运算“”变成了加法运算“+ ”，并且其适用域从实数域r 扩展到了r u + o o ) 。为 了方便研究，下面罗列了最小加代数中的一些函数及其性质： 定义2 1 ( 递增函数) ：对于v s ，t e r u + o o ) ，且s o 定义2 8 ( 水平偏差) ：对于w ，g f ，函数( f ) 和函数g ( f ) 之间的水平偏差办 的定义如下 h ( s ，g ) = s u o p i n f d o ；厂( f ) g ( ，+ d ) l o 定义2 1 0 ( 垂直距离) ：对于w ，g f ，函数( f ) 和函数g ( f ) 之间的最大垂直 距离定义如下 v ( s ，g ) = s u p ，( f ) 一g ( f ) ) s o 从定义2 9 和定义2 1 0 我们可以知道，水平偏差是用来表示函数厂( ，) 和函数g ( f ) 之间的最大水平距离的，而垂直距离是用来表示这两个函数之间的最大垂直距离 的。下图中的h ( s ，g ) 和1 ，( ，g ) 所表示的就是两个函数间的水平偏差以及垂直距 离。 幽2 - 1 函数之l - 甘j 的水、卜偏差和垂亘跑离 为了便于文章的分析，下面归纳了网络演算中比较常用的最小加卷积运算“0 ”， 最d , d n 反卷积运算“o ”以及求最小运算 ”一些基本属性。 1 交换律：对于w ，g f ，“ ”满足f o g = g 圆f 。 2 结合律：对于w ，g f ，“o ”满足( g ) o 办= 厂 ( g 办) 。 3 分配率：对于w ，g f ，“ 满足( g ) oj i l = ( f o h ) a ( g h ) 。 4 合成性：对于w ，g f ，“o ”满足( 厂o g ) 厅= 厂( g o 厅) 。 5 传递性：对于w ，g f ，v d ，d ：0 ，“o ”满足厂圆以= f ( t - d ) ， f 固5 0 = f ，6 n 园6 d 2 = 6 n 。d 2 q 2 2 2 最大加代数 最大加代数的代数结构为( 尺u 一o 。 ，v ，+ ) ，其中“v ”为求最大运算“s u p ) ”， 并且它满足( v g ) ( ，) = m a x f ( t ) ，g ( ，) = s u p ( ，) ，g ( 讲。最小加代数的代数 结构的求最小运算 ”在这里变成了求最大运算v ，而其中的求下确界运算 “i n f ) ”变成了求上确界运算“s u p ) ”，并且运算域也从r u + ) 变成了 尺u 一o 。 ，注意最大加代数保留了最小加代数的加法运算“+ ”，所以最大加代数 和最小加代数中的函数和性质是基本一样的，只要把对应得替换运算符就可以了。 下面是最大加代数中最大加卷积运算“西”和最大加反卷积运算“西”的定义。 定义2 1 1 ( 最大加卷积) ：对于w ，g f ，f ( t ) 和g ( f ) 的最大加卷积可以定 义为 ( 西) ( ，) = s 圳u p f ( ) + g ( s ) 2 3 通信流体模型 网络溟算理论的主要研究对象是网络通信流，网络演算就是对该领域问题进 行研究的所取得的成果的有机集合。在网络通信领域巾，通信流的一个重要特征 就是它的数据流量，而数据流量可以用一个时间段内数据流被传输的数据量来描 述。定义2 1 2 给出了一个可以描述通信流的数据累积函数。 定义2 1 2 ( 数据累积函数) ：数据累积函数尺( ，) 表示一个通信流在时间间隔 o ，】 内所传输的数据颗粒的总和。 由定义2 1 2 可知，数据累积函数尺( f ) 是一个随着时间不断增长的函数，并且 我们约定r ( f ) = o ，v t 0 。在实际的网络系统中，累积函数r ( r ) 是用时间间隔 o ， 内网络所传输的数据颗粒数目( 数据颗粒根据具体要求可以取位、字节或 数据包) 来表示的。图2 2 给出了一个累积函数尺( f ) 。累积函数r ( f ) 在丁时刻的 值为r ( t ：) 一r ( ) o ，即数据流在时间段 o ，f 】内所传输的数据颗粒数目，这个 时间段内的平均数据传输速率为6 0 0 t ( b i t s s ) ：累积函数尺( f ) 在时间段 o ，2 t 】 ( 即丁和3 r ) 内的值为r ( 2 t ) = 6 0 0 ( b i t s ) ，即在时间段 o ，2 t 内所传输的数据颗粒 数目为6 0 0 ( b i t s ) 。数据流在时问段 丁，2 t 】内没有进行数据传输，所以该时间间 隔内数据平均传输速率为零。由此可知，一个通信流的累积函数可以用于求对应 通信流在任何时间段内的数据平均传输速率。 图2 - 2 累积函数r ( f ) 定义2 1 3 ( 通信流体模型) ：对于一个具体数据流的数据累积函数r ( t ) ， f f o ，+ ) ，如果它是连续的，则称累积函数尺( r ) 为该数据流的通信流体模型。 通信流体模型就是用累积函数r ( f ) 表示的，它是在时间域上对数据传输速 率进行积分的结果。基于通信流体模型研究网络通信流问题( 如网络性能) ，可 以简化从速率角度来研究网络问题所必经的相对复杂的求解过程。 2 4 确定性网络演算 确定性网络演算主要用于求解网络节点的数据积压、数据的传输延迟、数据 包丢失率和有效传输带宽等一些网络性能上界。到达曲线和服务曲线是网络演算 的两大基本工具，到达曲线控制了进入网络节点的数据流量，描述了数据到达行 为的特征，在具体的应用中，一般会使用到达曲线来描述受制于通信量规约的数 据流。而服务曲线则是网络节点提供给通信流的确保服务的函数表示，速率等待 时间形式函数是最常见的服务曲线形式。下面将介绍确定性网络演算的基本工具 以及相关的定理【l 引。 2 4 1 基本工具 定义2 1 5 ( 到达曲线) ：对于任意一个函数a ( f ) ，a f ，t 0 ，如果数据累积函 数r ( f ) 对任意时刻s 和f 都能满足以下两个等价条件中的一个，那么我们就称 口( ，) 为通信流r o ) 的到达曲线： ( 1 ) r ro a ；( 2 ) 尺( f ) 一r ( s ) 口( f s ) 。 1 3 定义2 1 6 ( 服务曲线) ：对于一个通信流的数据累积函数r ( t ) ，如果有函数( ，) ， p ( o ) = 0 ，若通信流的输出函数r ( f ) 满足r + 尺q ，则称该系统为数据流提 供了服务曲线p ( o 。 该定义中的服务曲线是针对单个网络节点的情况而言的，为了解决多跳的网 络环境中的服务曲线求解问题，我们引入了串联服务曲线概念。 定理2 1 ( 串联服务曲线) ：如果一个通信流依次通过服务曲线分别为届( t ) 和 ：( f ) 的网络节点，则这两个网络节点提供的总服务曲线称为串联服务曲线 ( ，) ，且满足= 届p ：。 2 4 2 基本性能确定模型 在网络性能分析中，运用到达曲线和服务曲线可以得出确定性网络演算中的 几个基本性能确定模型。其中，网络节点缓存区中的数据积压上界由到达曲线与 相应服务曲线之间的最大垂直距离所决定，网络节点传输延迟上界由到达曲线和 服务曲线之间的最大水平偏芹所决定，而网络节点的输出特性由到达曲线和服务 曲线的最小加反卷积所决定。下面我们将详细介绍以上这3 个性能参数。 定理2 2 ( 数据积压上界) ：一个到达曲线为a ( 1 1 的通信流穿过一个嘲络节点， 如果该节点为数据流提供的服务曲线为( f ) ，则任意时间f ，该网络节点中的数 据积压q ( f ) 满足如下关系式 q ( ，) = r ( t ) - r ( f ) s u p 反( s ) 一( j ) ) 5 0 其中r ( ，) 和r ( f ) 分别表示通信流的输入函数和输出函数。 定理2 3 ( 传输延迟上界) ：一个数据到达曲线为仅( ，) 的通信流穿过一个服务曲 线为( r ) 的网络节点，那么任意时刻，该通信流在该网络节点中的传输延迟 j d ( ，) 满足如下关系 d ( t ) sh ( a ，声) 定理2 4 ( 输出特性) ：一个数据到达曲线为仅( f ) 的通信流穿过一个服务曲线为 1 4 p ( o 的网络节点，则该节点的输出函数满足如下关系式 2 5 网络演算模型 口= ao 本节介绍本论文中所采用的网络演算分析模型，包括数据源的输入包络、s p 调度网和p g p s 调度策略以及s c t p 协议a i m d 算法的分析都是基于这个分析模型 的基础之上。 2 5 1 输入源模型 在传统的排队分析方法中，输入源模型都是基于随机过程和概率论的，其中 应用比较广泛的有：描述普通数据的泊松模型( p o i s s o nm o d e l ) ，描述语音数据的 开关模型( o n o f fm o d e l ) 以及描述更为复杂的视频数据的马尔可夫模型( m a r k o v m o d e l ) ，文献 2 2 】提出了应用于语音和视频数据的概率模型( p r o b a b i l i s t i cm o d e l ) 瞪】。 本论文中所采用的输入源模型就是比较常用的o no f f 马尔科夫调制过程，这类 输入源模型的特点是它们使用包络函数来描述输入的特征，而不是确切地描述输 入源的细节。 2 5 2 网络模型 本论文所采用的网络模型是由任意的网络节点和数据链路所组成，其中的每 个网络节点都包含一个数据整形器和一个数据调度器，该网络环境可以是单跳的 也可以是多跳的，并且我们假设网络节点都是非阻塞的，也就是说分组旦到达 网络节点，调度器会根据调度原则调度，并把数据包递交给相应的输出缓存。 3f o r c e s 通道传输方案及s c t p 模型 3 1f o r c e s 路由器体系结构 f o r c e s 架构路由器的核心是转发件( c e ) 和控制件( f e ) 的分离。如图3 1 是标准的f o r c e s 架构路由器的基本架构，它是定义在f r c 3 7 4 6 中的。 f 1 f f 臣三三三 f o 疋e s 网络件 f p f i f f i f 图3 lf o r c e s 网络件架构图 在基于f o r c e s 架构的路由系统中，可以有一个或者多个控制件( c o n t r o l e l e m e n t ，c e ) ，它们分别被作为主c e 和备份c e ，如果主c e 发生故障，系统 会自动切换到备份c e ，以保证路由系统的正常运作。路由系统件中也可以有一 个或多个转发件( f o r w a r d i n ge l e m e n t ，f e ) ，它们存物理上和c e 都是分离的。 它们之问的接i - - 1 都是标准化了的f o r c e s 接l ，它们之问的信息交互严格遵循 f o r c e s 协议，c e 通过f o r c e s 协议来实现对f e 功能的配置和管理，而f e 则负 责数据层面的数据包转发，并通过上报机制产生事件消息。 f e 有两种接口类型外部接口和内部接口，外部接口用束实现内部和外部网 络互连，内部接口则用来实现内部各f e 之间的互联，外部数据从某个f e 的外 部接口进入，并根据该数据包请求的服务类型，转发数据包到指定的f e ，或者 通过本f e 的外部接u 回到外部网络。在该模型中，c e 管理器( c em a n a g e r ， c e m ) 是负责管理c e 的功能模块，它的丰要功能是f e 的拓扑发现，它根据配 置文件实现了c e 对f e 的访问控制，在f e 试图建立链接的时候，决定c e 是接 1 6 受链接还是拒绝该连接。f e 管理器( f em a n a g e r ，f e m ) 是负责管理f e 的功 能模块，它的主要功能是c e 的拓扑发现，它根据配置文件，在建链阶段确定主 c e 和相应的备份c e ，该过程也可能包含f e 管理器对c e 能力的学习。 f o r c e s 路由系统隐藏了内部结构，屏蔽了内部实现的细节，相当于路由器 或者交换机，对于用户来说，它只是一个简单的路由管理节点。 图3 1 中，f e 的外部接口用f i f - 表示，c e 管理器和f e 管理器之间接口用f l 表示， f e 管理器和f e 之间的接口用f 儇示，c e 管理器和c e 之间的接口用f c 表示，c e 之间接口用f r 表示，f e 之问的接口用f i 表示，c e 和f e 之间的接口用f p 表示， f o r c e s 协议对这些接口的通信标准都做了详细的论述。 3 2f o r c e st m l 通信结构 根据f o r c e s 路由器各种消息的传输需求，f o r c e s 协议定义了控制消息，事 件消息和重定向消息这3 种不同优先级的协议消息。在图3 - 2 基于s c t p 协议的 t m l 中它们由对应的控制通道、事件通道和数据通道来传输。控制消息是由 f o r c e s 内部的c e 或者f e 产生的，用来在c e 矛i f e 之间查询以及配置c e 参数或f e 参数的协议消息，事件消息是特定事件发生时所产生的消息，这里的特定事件是 指在事件分配模块注册过的事件。当有消息到达控制通道时，会有控制通道到达 事件消息，对应的还有重定向通道到达事件消息、监听连接的一系列事件发生时 所产生的消息。各个通道的消息都自己的传输性能的需求，t m l 通信结构的设 计需求就是要在3 个通道的传输效率以及高优先级通道数据的优先性之间取一 个最优的解。 1 7 s c t p 网络 图3 2s c t p - t m l 通道结构 t m l 是一个隔离应用层和传输层的中间件，它分布在控制平面，也分布在 数据平面。如图3 3 所示，这是一个c e 和多个f e 进行交互时，底层上由t m l 所 构建的通信