（信号与信息处理专业论文）基于pci总线的嵌入式设备的性能设计、仿真与优化研究.pdf

中文摘要 随着芯片集成度的提高，对于硬件开发人员而言，对芯片内部逻辑功能掌握 的要求越来越低，而同时因为网络技术的发展，接口的数据传输速率越来越高， 需要硬件人员熟悉芯片内部的机制来进行性能设计。 本文从对于基于p c i 总线的硬件设备接口卡和主板的硬件原理出发，结合目 前流量分析上的一些思路，尝试在设各上做性能分析，其目的是想通过模型和数 学计算，来设计一定网络流量环境下设备内部的一些硬件参数。 本文在模型层次和测试层次对于性能设计都做了开拓性工作。在研究算法和 模型的过程中，通过建立两个基本算法和一个修正算法，并且研究这些算法本身 的特点和使用场合后，再根据硬件机制、驱动方式和测试结果等方面的知识，把 基于p c i 总线的设备过程细化划分为几个排队过程，并且设计了基本算法和修正 算法对其进行仿真分析，得出一定数据流量情况下对于硬件设备各个排队阶段资 源的占用，从而可以估算出所设计设备的各种资源的大小和真正的性能瓶颈所 在。随后本文探讨了大流量的模型和基于此的计算分析方法，得出了硬件设计的 参考建议。 最后，把本文中所设计的算法用到芯片设计中去，实际上这是一种隔离某个 接口异常数据大流量的最佳方法。 本文所做的工作，对于设备前期的总体体系结构设计阶段、调试阶段和测试 阶段的性能设计分别指明了一套有效的方法，同时对于接口卡逻辑设计、驱动和 软件设计关于性能和资源占用方面都有借鉴意义。 关键词：设备性能设计流量分析p c i w i t ht h ei n c r e a s i n gs c a l eo f t h ei n t e g r a t e dc i r c u i t ，t h ek n o w l e d g er e q u i r e m e n to f m a s t e r i n gi ci n n e r1 0 9 i cf u n c t i o nf o rh a r d w a r ed e v e l o p e ri sr e d u c i n g m e a n w h i l e ， i n t e r f a c ed a t a 仃a n s m i s s i o nr a t ei sg e t t i n gm o r ea n dm o r ef a s td u et ot h ed e v e l o p m e n t o f n e t w o r kt e c h n o l o g y t h e r e f o r e ，i ti sn e c e s s a r ya n du r g e n tf o rh a r d w a r ed e v e l o p e rt o p e r f o r me f f i c i e n td e s i g na n a l y s i sb a s e do ni ci n n e rm e c h a n i s m i nt h i s p a p e r , t h eh a r d w a r ee q u i p m e n ti n t e r f a c ec a r db a s e do np c ib u sa n d h a r d w a r et h e o r yo fm a i nb o a r d ，c o m b i n e dw i t hs o m ei d e a sa b o u tc u r r e n t 锄c a n a l y s i si ss t u d i e da n dt h ee q u i p m e n tc a p a c i t ya n a l y s i si sp e r f o r m e d i na d d i t i o n ，t h e a u t h o ra i m e dt od e s i g ns e v e r a le q u i p m e n ti n n e rh a r d w a r ep a r a m e t e r su n d e rd e f i n i t e n e t w o r kt r a f f i cc o n d i t i o n st h r o u g hm o d e la n dm a t h e m a t i c a lc a l c u l a t i o n t h ep i o n e e rc a p a c i t yd e s i g nw o r ki nm o d e lh i e r a r c h ya n dt e s t i n gh i e r a r c h yi s u n d e r t a k e n i nt h ep r o c e s so fs t u d y i n ga r i t h m e t i ca n dm o d e l ，t w ob a s i ca r i t h n a e t i c s a n da na m e n d a t o r ya r i t h m e t i ca r ep r o p o s e d s u c ha r i t h m e t i c s c h a r a c t e r i s t i c sa n d a p p l y i n gs i t u a t i o na r ei n v e s t i g a t e d t h ep r o c e s so fe q u i p m e n tb a s e do np c ib u si s d i v i d e di n t os e v e r a l q u e u ep r o c e s s e sa c c o r d i n gt ot h ek n o w l e d g eo fh a r d w a r e m e c h a n i s m u t i l i z i n gs e l f _ d e s i g n e db a s i ca r i t h m e t i c sa n da m e n d a t o r ya r i t h m e t i ct o p u r s u es m u i a t i o na n a l y s i sf o rt h ed e v i c ed r i v e ra n dt e s t i n gr e s u l t , t h ee v e r yq u e u e s t a g er e s o u r c eo c c u p a n c ys t a t u so f h a r d w a r ee q u i p m e n ti so b t a i n e du n d e rd e f i n i t ed a t a t r a l f l cs i t u a t i o na n dt h e nv a r i o u sr e s o u r c em a g n i t u d eo fd e s i g n e de q u i p m e n ta n dr e a l c a p a c i t yb o t t l e n e c ka r ee s t i m a t e d ，t h e nt h et e s t e dg r e a tt r a f f i cm o d e la n dc o m p u t a t i o n a n a l y s i sm e t h o da r ei n v e s t i g a t e da n dr e f e r e n ts u g g e s t i o n sf o rh a r d w a r ed e s i g na r e p r o p o s e d a tl a s t ，t h es e l f - d e s i g n e da r i t h m e t i cf o ri cd e s i g ni su s e d ，w h i c ha l s oi sa k i n do f m e t h o di n s u l a t i n gs o m ei n t e r f a c ea b n o r m a ld a t af r o mg r e a tt r a f f i c i nc o n c l u s i o n ，t h ea l g o r i t h m sp r o p o s e di n t h i sp a p e ra r ee f f e c t i v ew a y sf o r p r o p h a s ec a p a c i t yd e s i g no fe q u i p m e n ts y s t e ma r c h i t e c t u r e ，d e b u g g i n ga n dt e s t i n g m o r e o v e r ，i th a sr e f e r e n c es i g n i f i c a n c ef o ri n t e r f a c ec a r dl o g i cd e s i g n ，d r i v e ra n d s o f t w a r ed e s i g n ，w h i c hi se s p e c i a l l yu s e f u lf o r c a p a c i t ya n dr e s o u r c eo c c u p a n c y k e yw o r d s ：d e v i c ep e r f o r m a n c ed e s i g n ，t r a f f i ca n a l y s i s ，p c i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：- 胞2 杰、 签字日期：埘年2 月i f 日 学位论文版权使用授权书 本学位论文作者完全了解墨洼盘翌有关保留、使用学位论文的规定。 特授权墨生盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：j 九卫废、 签字日期：加s 年2 月l8 日 导师签名 1 黼蠲 签字日期：洲年上月，广日 第一章绪论 1 1 课题提出背景及意义 第一章绪论 网络设备，例如路由器、a t m 交换机、接入服务器、三层交换机和i s d n 设备等，它们有很多共同的特点，并且一些新的技术在某种设备上取得成功后， 很快可以被其他设备引用【l2 1 。所以目前某些设备之间的界限已经很模糊。例如路 由器中就有a t m 交换机中的交换技术，a t m 技术和i s d n 技术，并且在三层交 换中的核心技术网络处理器也在第五代路由器中一样取得成功。 本人在读研前一年，在实际的产品测试中碰到一个关于性能方面的问题，当 时作为硬件测试人员，主要使用逻辑分析仪和s m a r t b i t s f 2 ”，组织一款路由器关于 性能方面的攻关，期间，提出了一些关于性能测试方面的测试用例，并且开始估 算性能测试，自始至终，关于性能方面的考虑获得了很大的成功。因为在产品设 计阶段，本人开始考虑性能方面的问题，并且根据估算对总体设计进行否定。在 实际产品设计出来之后，又始终推动性能问题解决的攻关，可以说在这期间，本 人积累了关于性能测试方面的较多项目经验，这些经历鼓舞着我进一步研究设备 性能设计技术。 本人坚信性能设计在产品设计中的作用巨大，而性能设计的前提，必须要求 开发人员熟悉系统、硬件和软件的设计。假如没有设计经验，性能设计是无从谈 起的。对于硬件而言，关于性能的设计最多的是在逻辑的设计中，于是在研究生 的一年级，研究了逻辑设计，主要是更深层次地了解硬件的机制。 在研究生二年级，开始考虑性能设计在项目中的运用，并且开始研究驱动程 序的设计技术。所以本课题实际上是链路层以下的考虑，并没有包括网络层及其 以上的内容。在研究生阶段的学习时间实际上是放在驱动部分的性能设计、体系 结构和模型算法设计方面的研究上的，而关于硬件性能测试分析的方案直接取之 于工作时候的独立设计。 直到最近的一年，终于完成性能分析的一整套的方法。该系统方法在设计的 基本算法基础上展开，建立了模型和数学计算仿真为主要手段的方法，并且使设 计方法往具体的设备设计方面靠拢。做到设计的算法和理论能在工程中有实际的 意义。 做产品中的性能设计，其实是产品设计的进一步的考虑，最好是有项目的支 第一章绪论 撑。但是目前即使在成熟公司的产品设计中，也没有这方面的职责，所以本人放 弃做项目的机会，而是专著于自己搭建平台，于是做了一个基于v x w o r k s 嵌入 式的平台，并且调试通了网卡的驱动程序。由于蓝牙是目前驱动程序中采用堆叠 技术比较好的例子，在研究过程中，研究了蓝牙的l i n u x 驱动技术。这两个关于 驱动的设计平台，特别前者是本文中研究性能设计在产品中运用的基础。 本课题是设备设计中的一个尝试，主要的意义是在产品的总体设计时候，从 模型上、体系结构上、硬件和底层驱动上，对性能设计进行全面的考虑。 1 2 国内外研究概况 在网络设备的研究中，国外的少数公司一直处于领先地位，可以说是垄断了 大部分的核心技术。关于性能设计技术在产品中的应用比较少见。国内部分的院 校在基于模型和排队论的基础上，对网络的性能分析做了较多工作，而设备性能 设计的研究比较少见。由于缺少实际的项目的支撑，往往性能设计是停留在理论 的理想的层面上。 国内通信公司在性能设计上作的前期的考虑比较肤浅，并且一些理论的判断 误差比较大，作者有幸作为国内最大的通信设备供应商的研发人员，主持了关于 路由器性能方面测试的项目。在此期间，提出一系列的测试概念和测试用例，例 如硬件开销测试和底层过程测试，均在性能测试方面填补了在产品分析审查上的 空白。从整体上来说，性能设计在国内公司的设计中，还刚刚起步，而性能测试 在少数测试人员的努力下，正处在探索阶段 3 h 。 造成上述情况的因素很多，主要原因如下：( 1 ) 国内技术领先的公司几乎都 比较年轻，所以很多公司在创业初期主要目的在于做出产品来，关于性能的前期 设计既没有经验也没有精力去考虑，而产品出现性能上的问题后，只有用性能测 试方案来解决。本人参与的项目几乎就是走了这样的路子，所以在产品项目上， 性能测试才刚刚起步，更不用说过多的性能设计的考虑了。( 2 ) 核，t l , 技术在少数 芯片制造公司手里，作为设备设计人员，无论是硬件还是驱动程序开发者，都是 无法跟芯片开发者和操作系统提供方相比拟的。( 3 ) 对稳定性要求普遍不够。 对于网络性能分析是目前的研究热点之一，但对于设备的性能设计的完整描 述，还没有见过，所以作者做了很多艰苦地创新工作。 第一章绪论 1 3 研究的理论基础与关键技术 排队论与随机过程概述o “，流量分析基础和性能评价在网络中的应用是研 究的理论基础，关键的技术包括硬件体系结构设计、底层设计、逻辑设计和测试 方法研究等等。 通过对上面的技术和理论的学习，加上本身有丰富的测试实践经验，本人逐 步想在一定的流量环境下( 直接采集或数学建立模拟流量) ，通过算法来估算所 设计设各资源的合理性。 1 4 论文作者所做的工作、难点和创新点 本课题是为网络设各的性能设计提供思路，但是实际的工作是基于v x w o r k s 和l i n u x 操作系统，设各接口卡涉及的主要是p c i 总线上的网卡、8 a s 卡和e 1 卡等等。另外对于诸多的接口卡、主扳和交换板的设计技术的熟悉及相关产品设 计技术的了解，都对设备性能设计的考虑帮助甚大。由于条件的限制，性能设计 的尝试在有限的几个板卡基础上展开，但是通过设计通用模型的建立，相信本尝 试能推广到其他的设备上，甚至是数据通信之外的设备。 研究生学习期间的工作包括：( 1 ) 研读与调试过的驱动程序有v x w o r k s 下 的r t l 8 13 9 卡的驱动程序，l i n u x 下的蓝牙驱动程序设计。( 2 ) 构造了基于 v x w o r k s 及x 8 6 的性能采集平台。( 3 ) 分析了测试得到的大量原始数据，找出 与性能参数之间的关系。( 4 ) 研究多类接口卡设计原理并且抽象出一个通用的模 型。( 5 ) 多个基本性能算法的设计及仿真，采用l i n u x 下的a w k 脚本语言实现( 6 ) 细化划分通用抽象模型为多级的模型，并且在各级模型中使用设计的多个基本算 法，同样采用a w k 脚本语言仿真。( 7 ) 研究了对于原始测试数据的分析方法， 建立满负荷大流量模型与分析方法。( 8 ) 研究了算法在芯片设计中的应用。 难点：必须在熟练掌握多种开发技术的基础上做分析和研究。由于对于某些 技术上的了解不深，例如协议软件和操作系统本身的机制，都制约了进步分析。 另外，本论文是在全新的领域进行设计尝试，在设备设计中没有找到直接的参考 文献，所以从建立基本算法开始，开创了一个平台设备上性能设计的系统方法， 在这个过程中曾经走过很多弯路，例如对于l i n u x 驱动源码的研读和总结i ”】， n s 2 仿真技术的学习，蓝牙协议栈源码 2 9 1 的研究，这些工作对本论文的系统方 法没有做出贡献或贡献很小。但是对于新技术的学习，也获得很多意外的收获， 例如n s 2 的学习使我掌握了a w k 语言的使用，最后发现设计的算法能很简洁地 使用该脚本语言仿真。 使用该脚本语言仿真。 第一章绪论 创新点：( 1 ) 独立地提出两个关于流量与硬件资源关系的基本算法及一个修 正算法。( 2 ) 把网络性能分析往设备内部引，创造性地细化硬件设备，建立p c i 平台的三级接收模型与四级发送模型。( 3 ) 创造性地建立大流量硬件数据流分析 模型及相关的分析方法。( 4 ) 深化了硬件测试方法，建立测试数据与算法参数之 间的关系，解决了实践与理论之间难于对应的问题。通过实测波形结合理论计算， 使参数的得来更合理。 而对于设计方法则吸收了很多人的总结和网络上朋友的文章。本课题是建立 在已有的多年硬件开发和测试的基础上，通过进步研究底层驱动技术和软件设 计技术，并且吸取目前网络性能分析的一些经验，构造自己的算法，形成套完 整的设备性能设计的思路，希望能在今后的工作中，树立一个性能设计的概念， 为设备的稳定性方面的研究作贡献。 第二章网络流量分析与设备设计 第二章网络流量分析与设备设计 对网络的性能参数进行建模和估计是现在高性能网络设计的关键i8 1 ，但是往 往因为无法直接通过分析的方法求解得到参数，所以一般是通过对流量行为的总 结，产生了流量分析的方法来求解参数【1 1 】。流量分析的难点在于很难描述现有网 络的流量模型。描述流量特性的指标归纳为如下：吞吐率特性( 平均速率、峰值 速率和速率变化) 和延迟特性( 传输延迟和抖动) 。 传统的分析方法是采用m y m j l ，后来随网络的发展和数据流量类型之间比例 发生变化，分析方法越来越复杂。本文的最终目的不是网络分析，而是设备设计。 设备设计的基本思路是根据流量特征或现实流量，设计与分析设备服务能力参 数，包括服务速率和缓存大小等。如图2 1 所示： p 4 试出来或+ 卜一作者的重点工作流量建模 图2 1 在本章中重点描述设计的两个核心基本算法及一个修正算法，这些算法直接 计算设备在所处的数据流下所需要的合理服务资源。下一章将作进一步的设备细 化划分，并且估算硬件参数设计。由于设备设计中的结果依赖于网络流量特征， 所以也讨论了一些网络流量到达分布的问题，以期进一步用流量建模替代设计设 备算法中的输入测试系列，获得更方便的设备设计评估方法。 2 1 传统流量分析概述 即使在获取网络流量参数的比较图后，模型的建立还常常不是一件容易的 事，但即使模型无法建立，也可以通过直观比较得出优化设计方案。 参数主要包括上面提到的五种 1 3 】： ( 1 ) 平均速率即为平均负载，它决定了分配资源的多少； 第二章网络流量分析与设备设计 ( 2 ) 峰值速率即为最大负载，它决定了预留的资源的多少； ( 3 ) 速率变化，即吞吐量的变化，它诀定预留资源被占用的快慢。 ( 4 ) 传输延时：指流量从信源到目的地，网络所施加的时延，这个包括传 输与设备交换( 即响应) 时间。一般传输时间大大小于设备响应时间。 ( 5 ) 抖动，即时延偏差，对于实时应用是一个重要参数。 上面的参数都对设备的性能分析意义重大，例如速度变化大时，突发流量瞬 时的预留资源占用很多，这也意味着一般时间内资源的浪费，解决速率变化造成 的资源的需求的变化的方法之一是采用共享资源的方式。 2 1 1 基本系统分析 在m m 1 中，顾客到达间隔是1 的指数分布，服务时间是1 u 的指数分 布，所以服务员的利用率p ： p = 平均服务时间平均到达间隔时间= ( 1 u ) ( 1 九) = x t t 。p 也称为系统的通信量强度( t r a f f i ci n t e n s i t y ) 。 令n ( t ) 表示t 时刻系统内顾客的数量，那么 n ( t ) ，t o 是一个生灭过程， 状态图如下图2 2 ： 2 丑工置 一! = ! 埘! u ! = ：k 图2 2 i s c 玑是该连续时间生灭过程在状态k 的稳定状态概率，该生灭链的平衡方 程为：j j 仇一t + 玎“2 a 仇+ 卢叩，2 1 即：仇+ l 一五仉= 町一a 仉一l = - = a t l - a r o = 0 得至o ：仇：互仇一。：f 三1 ，7 。：p 。叩。，t 1 又因为：仇= l 删2 索2 南 当p = 2 1 ，在这种情况下，服务时间集中在很短或很长的两个极端，也是使用m m 1 不安全的情况，应该使用m o 1 来分析问题。 上面分析的意义在于，对于设备设计者，应该分析或测试实际的设备服务的 时间分布，在彳o r s 1 的情况下，设计者可以使用指数服务时间来分析问题，从 而使分析简单有效，否则的话，必须用一般服务分布时间来分析问题。在这种情 第二章网络流量分析与设备设计 况下，分析或测试一下五和盯玷意义重大。这样在实际的设备设计中，服务时间 分布将通过测试得出，而l i t t l e 公式【】= 旭忸】在几乎所有的排队系统中均是有 效的假设。 2 2 设备性能设计估算方法 2 2 1 服务资源占用估计 上面的考虑主要是基于传输延时和输入缓存的，下面进一步研究吞吐率特性 对系统的影响，而数据流量本身的分布研究放在晟后节。 下面先粗略看速率变化的影响。考察以恒定速率v 到达数据和恒定速率处 理数据的理想系统中( d d 1 ) ，即使到达速率和服务速率接近，响应时间r 和 输入缓冲n 都是比较小的值，这个时候，服务的模型可以抽象成水管中的流水： v 图2 5 ：流水模型 n = v r 不幸的是，实际的系统根本不是上面的常数分布，所以输入缓冲和响应时间 都比水管模型大的多。 就象上文分析服务时间分布对系统影响时假设为泊松到达一样，在分析到达 时，假设服务是确定的分布，例如本文下面假设的常数分布。这个假设是符合等 长数据包的场合，例如a t m 系统中信元是等长的，可能具有常数服务时间。根 据上一节讨论，这个假设不适合其他系统，幸好，本节研究的是到达速率变化对 系统的趋势的影响，研究过程可以推广到指数时间服务情况，但是性能会更糟糕。 下面考察这样一个错误的命题，即设备服务的速率远远大于流量到达的平均 速率，这样缓存很少就可以的。我们在g x 1 的系统下分析这个历史上长期被忽 略的问题，并且该问题曾导致a t m 交换机的缓存设计普遍太小1 5 】。直观上讲， 流量过分集中到达时( 即使长对间流量速率不 大) ，数据包的绝大多数必须放在缓存中，这 样缓冲的容量还是比较大。 跟水管模型样，做了一个漏器模型。 该模型中，服务速率能力c 为固定大小， 即抽象为漏器中的底部，当容器底部有数据流 图2 6 第二章网络流量分析与设备设计 时，漏器输出的固定速率为c ，b ( t ) 是整个容器的容量，也即缓存的大小，而a ( t ) 是到达速率。假设b ( t ) 足够大时。旦在f 的时间内4 ( f ) 没有发生突变，则； 占( r + r ) 一b ( r ) = 一( f ) f c a t 可见a ( t ) 在f 时是一个大数据时，缓冲的增加将是很大的。 2 211 排队论在设备设计中的应用服务开关性分析 排队论的方法在计算机网络中得到过成功的应用，本节是把该方法在设备设 计中推广的概述。 图2 - - 7 中每个矩形对应的都是一个包的大小只= d x a t 。，d 是接口物理上 的最大速率it j 是到达的时刻；c 是服务的速度。 蟹 一量 且一 只 暑 暑“ c l + l 一 f l r t 。 图2 7 我们的设备一般都是以一个报文或数据包为单位进行服务的。下面考察该数 据包服务的时刻：( 1 ) 当缓冲为零的时候，显然，数据输入的每个比特不可能立 即得到c 的服务，如果更确切的话，这种情况应该：当f ，缓冲中数据为空的时候， 那么开启服务c 的时间为本数据包放在缓冲中后，也即：，+ f ，时刻；( 2 ) 考察 缓冲不为空，也即a 。 0 时，也不能断定在该序列时间，。到t 。+ a t ，之间一直是以 c 服务的，例如，较小时，在f 。的部分时间中，。即服务完毕，而此时新的 包没有输入完全的情况下，服务暂时挂起，开启服务c 的时间也为t ，+ a t ，；( 3 ) 考察缓冲不为空且序列时间f ，n t ，+ a t ，之间一直是以c 服务的，那么虽然实际开 启该包服务时间较晚，但是该包服务需求时间还是，+ f ，。 所以设备中的算法对于服务应该具有开关( o n o f f ) 特性。 同时假设数据在f ，+ f 。时需要缓冲最多是比较合理的，故需要在f ，+ r ，时刻 引入玑变量，表示缓冲的大小。 通过上面的分析，设备算法实际需要的时刻是每个数据包结束时刻r + a t ； 第二章网络流量分析与设各设计 与数据包的大小只构成一对有用参数。 2 2 1 2 基本算法一( b a s e 1 ) 设计该算法基于这样的考虑：流量到达分析( 下节讨论) 主要是根据长时间 ( 小时、天甚至年) 的统计特性来分析问题，但是对于设备而言，短时间内的到 达特性或许更值得分析。下面先从设备的特点来分析一( f ) 的一些出时间内固有 的特点。首先可以肯定，一f r ) 的瞬时突发容量不可能是冲激式的，即使网络上有 这样的需求，但是设备的接口处都有定的限制，也就是实际的突发不是无限的。 考察一块带有百兆以太网卡的设备，以6 4 1 5 3 6 字节的数据包到达的时候， 5 1 2 筇一1 2 2 8 8 心是此时的f 。对每个包的开始时刻和包的大小进行记录，这 样就可以画出图2 8 的示意图。因为目前网络数据报文的特点，一般在出内， 到达的流量是恒定速率d ，该值对应图中接收线的斜率。 图2 8 基本算法一( b a s e 1 ) 的一般式分成两个步骤： 第一部为预处理：本算法考虑的输入是接收结束时刻。假如输入序列为接收 开始时刻时，那么本步骤做个预处理，使输入序列是每个接收包的结束时刻： 咐鲁 这样第二步的第i 输入序列和p 是第i 包的接收结束时刻( 也即该包有服 务置盛的时刻，不一定等于服务开始时刻) 和数据包长度。 第二步是个递推过程： ( ” 当i = 1 时： i f r c l ( w 枷 只t h e n 。= b r c l m ) 咖 第二章网络流量分析与设备设计 e l s e a l = 0 e n d ( 2 ) 当i 2 时 i f r 只+ h i c t ( w ) d w t h e n 。= 只+ 。一r c ( w 枷 e l s e a ，= 0 e n d b a s e 一1 更有利于计算机仿真的算法是假设+ ：e ( w ) 在【w i ，w j + ，】是个常数值， 即假设每包服务时间内是恒定的速率c j ，该值是图2 - - 9 中服务线的负斜率，如 果c l 取恒定c ，l l l z , 图中的负斜率平行。 图2 9 算法递推改为： ( 1 ) 当i = 1 时： i f w 2 一w 1 ) c i - 8 , t h e n l = 只一w 2 - w 1 ) c i a l = 0 e n d ( 2 ) 当i 2 时 i f ( w j + i w f ) c l 2 时 i f l 一】w ，t h e n s t2 e l s e 占j = i 一1 e n d 第二章网络流量分析与设备设计 a s ，= q + ，化) = s ，+ 血， 这个算法得到_ 和，分别是服务开始时间和服务结束时间。 缓冲计算过程：这步的输入序列是：w i 、s ，和只。第i 递推过程是： i fw ， s ，t h e n s t a r t = w , ；e n d = s ， a f f i x ( s t a r t ，e n d ) e l s e q 。2p 。 e n d 其中a f f i x ( s t a r t ，e n d ) 又是一个递推过程，第i 步为： i fs t a r t w e n dt h e n q ，= q 。+ 只 e n d b a s e - 2 更有利于计算机仿真的算法是假设4 + ：a s 。= 日，+ 要( h ；和e 与时 间t 没有关系，只随i 的变化而变化到另一个常数值) 。 算法评估：因为有嵌套的递推，本算法的计算量相当大；能清楚的得出输出 序列的时刻，作为多步的排队分析中，前面排队使用该方法可以得出后继排队的 输入序列；a s ，= h ，+ 厂) 的考虑适合不同的硬件机制。 下面的仿真结果图2 1 2 是假设只是个常数h ，并且，( 只) = 占只： ( 1 ) h 卸时 第二章网络流量分析与设备设计 ( 2 ) h = 1 0 时 第二章网络流量分析与设备设计 ( 4 ) i i = 1 0 0 时 ( 5 ) h = 1 0 0 0 时 i 葫= 竺：= = = 一 j ，。 ， 。l。一一_- m e e 匿薹差三i 一一二_ 二二一 二z、 l j i 。引?铲。 图2 1 2 1 8 刊 一，；一 第二章网络流量分析与设各设计 上面的结果表明：在所使用的测试序列的情况下，相同条件下，随h 值的 增加而输入缓冲增加的关系图。在具体的工程中，可以判断出影响h 值的参数， 例如下文讲到的网卡的二级排队中，读写一次i o 都导致h 值的增加。这样可以 评估底层软件中读写i o 次数多寡与性能的关系。 2 2 1 4b a s e 1 算法与b a s e 2 算法的关系 算法相同点 b a s e 1 和b a s e - 2 有密切的关系：它们是对于一个数据包分别从服务时间 和服务速度这两个角度设计的算法，所以在一般式的情况下，两者是等同的。下 面分析的是b a s e l 在假设和b a s e 2 在假设一下的关系。 对于b a s e - 1 算法，每个序列的服务时间血，= 寻，下面把b a s e 2 往这个 l ，j 形式上靠拢。 记厶，：- i , + z ) ：要 u f 那死铲赢 假设，：纽1 ：占p ：旦，那么：g ： 墨 ： 墨：g 假设，( e ) = 最只2 苦那么：g l2 南。赫 可以看出在知；= q + 鲁( 只和c l 与时间t 没有关系，只随i 的变化而变化 l 到另一个常数值) 的假设下，修正量g 是个只与i 序列范围时间内的一些恒值有 关，故在这个i 序列服务时间内，修正量g 是个恒值。 图2 1 3 是在血，= q + 导假设下的示意图： t n 只 上 卜百刊e l 一二上叫 图2 一1 3 ( 1 )当i = 1 时 由示意图看出来，在假设的情况 下，b a s e 2 和b a s e 1 是相同的算法。 b a s e - 1 是b a s e 一2 在，( p ) 与i 序列的 固定值有确定函数关系( 保证g ，是个i 阶段恒值) 时，才等价，否则b a s e 2 算法更广泛。 所以，在假设的条件下，修正量g 值代替b a s e 1 算法中的c ，得到关于 1 需要只和4 = 参数的修正的 l 1 b a s e 一1 算法_ b a s e 1 一a m e n d ： 第二章网络流量分析与设备设计 g ： 墨：刍 1 c 1 目+ 弓 i f ( r 2 一t 1 ) g 1 只t h e n a 。= e 一( f ：一t 1 ) g 。 e l s e a l = 0 e n d ( 2 ) 当j 2 时 g：墨：鱼t c i h i + p ： i f o 一t ) g ， 只+ l - lt h e n a ，= 只+ 。一o 。一) g ， e l s e = 0 e n d 下面是b a s e - 1 一a m e n d 算法与b a s e 1 、b a s e 一2 算法来估计设备性能参 数的比较图如图2 一1 4 ： i i 霍i 一。万一一1 ，4 绺嚣1 。鳓材峨； ” l 。 一 坠山出一 图2 1 4 仿真结果表明在h 较小情况下各个算法结果是一致的；h 较大的情况下， 虽然结果有所差异，但是表明的趋势是一致的：其中b a s e 2 是个精确而运算量 大的算法，相对于这个算法，b a s e 一1 的估计输入缓冲的大小偏小，而 b a s e - 1 一a m e n d 的估计偏大。 第二章网络流量分析与设备设计 综上所述，工程计算中，b a s e 。1 a m e n d 由于在设计中有一定的设计预留， 而且计算复杂度小，推荐使用。 算法不同点 b a s e 1 算法：速度快；只得到一定服务参数下的缓冲的大小，无法为串接 排队的下级得出有用的输入序列。 b a s e 2 算法：速度慢：能在得出缓冲的同时得到串接排队的下级的输入序 列： 2 2 1 5 数据采集 在实际的设计中，可以通过测试的方法来得到网络实际流量。 在程序中加入代码一定影响性能，在设计设备中过多使用统计和计算的代码 不适合，不过因为主要是采集线路的序列，所以使用比设计的设备性能好的仪器 做采集分析是可以的。下面还有两种不影响性能的方法：根据自相似的原理，可 以测试长时间，再分析短时间内的流量；还有可以使用硬件方法，例如逻辑分析 仪的测试或f p g a 的实现。当然在为输入分布进行数学建模，也可以在仿真中得 到输入序列。 上面是基本算法介绍，下一章将讨论这些算法在实际设备设计中的使用。 2 2 2 设备资源的合理分配与设计 上面是从流量到达分布看某接口对于系统资源的占用，下面从设备系统角度 看接口卡设计。我们再考察一个实际的设备的情况，目前设备的服务的速率已经 开始落后于接口的速率，所以我们在设计具体的设备的时候，可能不能够仅仅通 过接口卡的性能来设计输入缓冲。市场上的中端路由器，例如q u i d w a y 3 6 8 0 ，设 备的八个接口卡中，仅仅一个百兆以太网卡工作的时候，达到的最大速率是4 万 包( 每包6 4 字节) ，丽6 4 x 8 4 x 1 0 4 = 2 0 4 8 m b i t s s ，也即设备使用一个百兆网 卡，也仅仅使用了该设备卡的2 0 的性能。本人分析过这个问题i ”j ，发现对于 这样的中端设备，并不是接口卡的缓冲达到瓶颈，而是设备的服务达到相当地饱 和。而这个设备的饱和，也并不是传统意义上讲的c p u 服务的饱和，在这个测 试设计中，测试评估了p c i 的承载能力，测试结果是p c i 在一个百兆网卡使用 2 0 的情况下，3 3 m 的3 2 位p c i 达到约6 8 ，硬件总线上的信号不可能接近 1 0 0 的，所以在中端路由器( 共享总线式设备) 服务端的p c i 总线、c p u 、内 存和体系结构都可能构成服务的瓶颈。在下面的章节中，再分析这方面的问题。 在数学的抽象中，我们必须正视这个现实，接口卡的物理速率即接受能力正 远远地超越服务卡的服务能力，所以真正拥挤的一个高速的接口卡设备，可能在 第二章网络流量分析与设备设计 较短的时间内，使服务的主板立刻无法正常工作，所以从这点上讲，有时候，我 们仅仅根据接口卡的物理速度和网络上的最大流量设计设备的输入缓存，可能得 到一个相当大的缓冲值，但是实际的意义却不大，反而相当于一个大的蓄水池， 往主板侧灌数据，导致主板中内存中的缓冲区溢出。从整体的性能角度看，一个 接口卡对应的网络发生风暴，接口卡应该为主板设备屏蔽这个风暴，而仅仅能够 最大限度地使用系统分给自己的资源。最常见的处理方式就是丢弃报文，断臂求 全是最好的策略。在第五章讨论该思路在设计中的实际应用。 所以本文认为，对于一些设备，输入缓冲的设计仅仅从数据流到达分布分析， 即使对于接口板是合理的，但是对于整个系统可能是个糟糕的事情。在优化的设 计中，硬件上作适当地预留资源：f i f o 的大小设定，驱动程序中缓存的分配等。 但是理论上的不丢包文的预留资源有时候大得惊人，所以必须考虑成本和整体资 源的合理分配，这样在协议上必须做好预留资源不足的准各，并且性能的得来也 离不开测试项目的设计，可以说最佳性能的得来是个系统工程。 2 3 网络流量到达分布分析方法 传统流量分析中，本文根据排队理论和网络性能分析，得出设备性能设计的 一些方法，其实做了一个假设，即到达是指数分布的：而在算法的实现中，本文 使用的是实际测试序列作为输入的，算法避开对数据序列的统计特点的分析，但 如果能得到确切的数学描述，那么就可以不用进行实际的测试，但实际上网络流 量到达分布是目前学术界十分复杂热点的难题。下面先回顾一些典型的方法，主 要目的是吸取方法的思路，来服务设备设计方法的研究上来。 合理的流量模型的建立是一件困难的事情，目前的方法主要分为两大类：一 类是以概率统计来建模；另一类是以非概率统计的方式建模。其中前者发展了三 十多年，经典的以泊松模型( 是短相关模型，相关函数按照指数形式衰减) 来描 述流量，最近十年发展了长相关模型，其中自相似传输模型是目前研究网络流量 的热点。而以非概率统计方式发展的模型，研究人员相对较少，以c r u z 在2 0 世 纪9 0 年代提出的突发性约束流量模型为代表 3 1 4 1 1 6 】 7 】。 本论文分析各种流量模型的特点是为了把网络为结点的分析方法推广到设 备内部去，建立设备中的流量分析方法，并且探讨流量特点对设备设计的影响。 同时也是基于这样的考虑：模型的更新反映了网络流量特征的发展，不同的模型 在不同的网络能得到成功的应用，所以对于设备设计者而言，在没有置身于网络 中的时候设计设备，必须想出一套针对该设各处于网络中的不同环境，做适当的 调整。 第二章网络流量分析与设备设计 2 3 1 马尔可夫和嵌入式马尔可夫模型 马尔可夫过程是具有无后效性的随机过程，所谓无后效性是指当过程在t 。时 刻所处于的状态为已知时，过程在大于f 。时刻所处状态的概率特性只与过程在r 。 时刻所处于的状态有关，而与过程在t 。时刻以前的状态无关。离散状态空间的马 尔可夫过程称为马尔可夫链。离散马尔可夫链( d t m c ) 和连续马尔可夫链 ( c t m c ) 定义参见口2 1 ，d t m c 的状态变迁发生在整数时刻，而c t m c 是连续的 时间。 马尔可夫模型主要有如下的几种【5 】：o n o f f 两状态模型、口p ( i n t e r r u p t e d p o i s s o np r o c e s s ) 模型、马尔可夫调制流体模型等等。 o n o f f 两状态模型 该方法是根据语音流量具有明显的开关特性( o n 和o f f 状态) 而提出，描述 单个语音源的时候，序列分为活动状态( a c t i v e ) 和寂静状态( s i l e n c e ) 序列， 活动状态的保持时间可以很好地描述为指数分布，而寂静态也可以描述为指数状 态。虽然该模型提出以语音源作为目标的，但是在突发的流量中也有所应用，即 使没有人验证过突发流量长度是否是指数分布【3 3 】。 i p p 模型 当只在a c t i v e 状态时以泊松过程到达建立的模型，即有效序列的到达时刻是 个指数分布。 马尔可夫调制泊松过程m m p p 与马尔可夫调制流体模型 马尔可夫调制过程( 也叫双随机过程) ，使用一个辅助的马尔可夫过程来调 制流量分布概率。m m p p 的参数可以很容易地从实验室数据中得来：量化到达 率为有限个数值，每个数值对应一个在马尔可夫链中的状态，设n 个状态的随机 过程，每个状态肇，1 s k 聍，则是的到达率服从均值为矗的泊松过程，状态之 间的转移构成一个连续时间的马尔可夫链。m m p p 模型可以对语音和数据的混 合流量建模。若在状态时，语音为五的泊松到达，而数据为乃的泊松到达， 那么状态鼠将是从以 + 九的泊松到达。 流体模型是当单独的业务量单元( 一个包或一个信元) 对系统排队性能几乎 没有影响时，把业务量特征化为连续流，以流的速率变化作为模型的参数的方式 来建模。因为流的速率的变化远远小于业务量到达，所以大大节约计算和内存资 源。马尔可夫调制流体模型是流模型中常见的一种 3 4 1 ”】。文献中建立了一个马 尔可夫调制恒定速率模型用来分析v b r ( v a r i a b l e b i t r a t e ) 视频信号源，该模 型在状