（通信与信息系统专业论文）宽带复接芯片的仿真和缓存管理算法的研究.pdf

摘要 本文首先对种宽带复接芯片进行了仿真研究。该宽带复接芯片是一种高性 能、低成本、支持网络协议( i p 或者a t m ) 集成电路芯片。该产品主要应用于数字 用户线访问复用器( d s l a m ) 、第三代无线地面机站、及各类光接入系统等宽带综 合业务接入设备。由于该芯片具有组播功能，特别适合电话会议、远程教育、视 频点播等设备。由于该类型的芯片国内尚无人生产，可借鉴的经验和技术很少。 故在芯片j 下式投入生产之前。对其进行仿真，测试其基本性能并发现和解决相关 问题，是非常必要。 本次课题是在o p n e t 仿真环境下实现的。经过了仿真模型的研究和搭建，算 法研究和仿真模型具体实现，性能的详细测试和分析以及问题的发现和解决等四 个阶段的研究。得到芯片的相关性能参数，譬如，不同情况下的时延、时延抖动、 丢失率、速率等。着重研究了芯片存储空间相关问题，并提出了解决问题的具体 办法和建议。 由于宽带复接芯片要用到缓存，就要对缓存进行管理，接着我们对现有的缓 存管理算法进行了进一步研究，并提出了一种新的缓存管理算法d t + s m a ，该算 法把d t ( d y n a m i ct h r e s h o l d ) 和s m a ( s h a r i n go fm i n i m u ma l l o c a t i o n ) 结合起 来，具有两者的优点。通过理论分析和仿真，得知在单优先级情况下d t + s m a 比 s m a 的公平性更好，在多优先级情况下s m a 比d t 更易于实现，而且同时也能获 得和d t 相近的性能。 关键词：复接芯片，缓存管理算法，分组复接 a b s t r a c t i nt h ef o l l o w i n gid i ds o m er e s e a r c hi ns i m u l a t i o no fonek i n do f b r o a d b a n dm u l t i a c c e s sc h i p b r o a d b a n dm u l t i a c c e s sc h i p ，w h i c hs u p p o r t s i po ra t mp r o t o c o l ，i sa ni n t e g r a t e dc i r c u i to fh i g hp e r f o r m a n c ea n dl o w c o s t i ti sa p p li e di nd e v i c eo fb r o a d b a n di n t e g r a t e ds e r v i c ea c c e s s ，s u c h a sd s l a m ，w i r e l e s ss t a t i o no f3 g ，a n da l lk i n d so fo p t i c a laccesss y s t e m f o ri t sm u l t i c a s tf u n c t i o n ，i ti ss u i t a b l ef o rm a n yd e v i c e s ，s u p p o r t i n g s e r v i c e so fc o n f e r e n c ec a l l ，l o n g d i s t a n c ee d u c a t i o na n dv i d e o o n d e m a n d h o w e v e r ，f a c t o r yi nc h i n acann o tp r o d u c es u c hc h i p ，a n de x p e r i e n c ea n d t e c h n o l o g yo fp r o d u e i n gt h i sc h i pc a n n o tb ee a s i l yf o u n d s oi tis n e c e s s a r yt od os i m u l a t i o no ft h i sc h i pt oo b t a i ni t sb a s i cp e r f o r m a n c e a n dt os o l v es o m ep r o b l e m sb e f o r ei t sp r o d u c t i o n t h i sp r o j e c ti sd o n ei nt h eo p n e te n v i r o n m e n t i tc a nb ed i v i d e di n t o f o u rp a r t s ：s t u d y i n ga n dc o n s t r u c t i n gm o d e l ，s t u d y i n ga l g o r i t h ma n d i m p l e m e n t i n gm o d e li n t oo p n e t ，r u n n i n gs i m u l a t i o nm o d e la n da n a l y s i s r e s u l t s a f t e rt h a t ，w ec a ng e tt h ep e r f o r m a n c ep a r a m e t e r so ft h i sc hj p ， s u c ha st i m ed e l a y ，t i m ed e l a yj i t t e r ，l o s sr a t e ，v e l o c i t ya n ds oo n i n a d d i t i o n ，t h em e m o r yo ft h i sc h i pi sg r e a tc o n c e r ni nt h ep r o j e c t ，a n d s u g g e s t i o n sa n ds o l u t i o n sa b o u tm e m o r yp r o b l e m sc o m eo u t t h eb u f f e ri su s e di nt h ec h i p s ，s ow eu s eb u f f e rm a n a g e m e n t w ed o f u r t h e rr e s e a r c hi ne x i t i n gb u f f e rm a n a g e m e n ta n danewb u f f e rm a n a g e m e n t s c h e m ec a i l e dd t + s n ai sp r e s e n t e d t h i ss c h e m ec o m b i n e ss m a ( s h a r i n gw i t h m i n i m u ma l l o c a t i o n ) a n dd t ( d y n a m i ct h r e s h o l d ) a r i t h m e t i c ，a n dw ef i n d i th a st h eb e n e f i t so fb o t hd ta n ds m a t h r o u g ha n a l y s i st h es c h e m ei n t h e o r ya n ds i m u l a t i o nw ec a r ls e et h a ta c t u a l l yd t + s m ai sb e t t e rt h a ns m a i nf a i r n e s si ns i n g l ep r i o r i t y ，a n di se a s i e rt oa p p l yi nm u l t i p i e p r i o r i t i e sm o d e lt h a nb tw h e na c h i e v i n gt h es i m i l a rp e r f o r m a n c ew i t hd t k e yw o r d s ：m u l t i p l e x i n gc h i p s ：b u f f e rm a n a g e m e n t ：p a c k e tm u t i p l e x i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：塑! 壑 日期：2 e 。，年，月2 3 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 朝 ) 水 导师签名： 孝氏 日期：2 口o ，年，月2 ；日 主要符号表 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 ) 异步传输模式 c p ( c o m p l e t ep a r t i t i o n i n g ) c s ( c o m p le t es h a r i n g ) d s l ( d i g i t a ls u b s c r i b e rl i n e ) d s l a m ( d s la c c e s sm u l t i p l e x e r ) d t ( d y n a m ict h r e s h o l d ) 完全划分 完全共享 数字用户线 数字用户线访问复用器 动态门限 l v d s ( l o wv o l t a g ed i f f e r e n t i a ls i g n a l i n g )低压差分信号 p o ( p u s ho u t ) p o t ( p u s ho u tw it ht h r e s h o ld ) p q ( p r i o r i t yq u e u e ) r r ( r o u n dr o b i n ) s d r a m ( s y n c h r o n o u sd y n a m i cr a m ) 推出 以一定门限推出 优先排队 轮询 同步动态存储器的意思 s m a ( s h a r i n gw i t hm i n i m u ma 1 l o c a t i o n )最小分配共享 s t ( s t a t i ct h r e s h o l d ) w r r ( w e ig h t e dr o u n dr o b in ) 静态门限 加权轮询 电子科技大学硕士学位论文 1 1 宽带接入的发展 第一章引言 近年来电信业的网络结构已经发生了根本的变化，从原来的只支持语音通信 的网络转变为提供以数据业务为主的多媒体综合宽带业务网。宽带综合业务接入 是在电信设备市场中一直保持强劲成长的领域。宽带接入平台目前已经从异步传 输模式( a t m ) 为主发展为异步传输模式和网络协议模式( i p ) 混用共存的局面，并 显现出将进一步演变为以i p 为主的趋势。这个过度大约需要十年的时间。为此， 中国以及环太平洋地区的电信服务公司将继续对基础设施投入巨额资金采用各 种方法来解决“最后一公里”( 也称“最初一公里”) 的问题。据估计未来十年 内中国宽带接入将以平均每年2 1 0 0 万线的速度增长。在与此领域相关的技术中， 数字用户线( d s l ) 和第三代无线技术正得到高速的发展。从而对批量大、成本低 的通讯设备用的标准芯片和专用芯片的需求量也将持续增长。而目前国内还没有 企业能设计、生产这类芯片。 随着宽带业务的不断增加及丰富，它必将改变人类的生活方式。尽管前一段 时间美国及世界其它一些地区经济发展势头放缓，但互联网的发展和人们对带宽 的需求却丝毫没有减少。相反，网络业务平均每十二个月左右就翻一番。北京奥 运会和上海世博会更给信息行业带来巨大的商机，也势必增大对接入网技术的要 求。接入网可分为有线和无线两大类。有线分光纤接入，同轴电缆接入和双绞线 接入；无线分移动无线和固定无线接入。到目前为止，双绞线的d s l 技术将会在 段相当长的时间内作为主流的宽带接入技术之一而存在，它基本上解决了接入 信息安全、流量控制、网络管理和鉴权计费等困扰运营的问题。根据资料显示，中 国是全球d s l 应用增长最快的市场之一。目前，全国电话用户总数超过1 3 5 亿 户，并且还在不断增加( 全国电话普及率目前还不到1 5 ) ，而d s l 恰恰可以充 分利用现有的铜缆资源，对电话线路稍加改造，不仅可以运营现有的语音业务， 而且可以提供d s l 宽带接入增值服务。在美国，目前有大约两亿条电话线，而在 这两亿条电话线中，由于距离等因素的限制，目前只有不到5 0 的用户有可能使 用d s l 。而在这些有可能使用d s l 的用户当中，目前仅有极小的一部分( 大约占 用户总数2 左右) 真正安装了d s l 设备并使用该项服务。因此，在美国，d s l 也远未达到普及的程度。去年，由美国1 4 家设备商和运营商共同在d s l 论坛发 电子科技大学硕士学位论文 表的白皮书其标题为“d s la n y w h e r e ”，也就是说，d s l 在任何地方。不难想象， 无论在中国还是在美国，d s l 都有着极其巨大的市场潜力。从而对批量大、成本 低的通讯设备用的标准芯片和专用芯片的需求量也将持续增长。 带有组播功能的d s l a m 芯片在国内是空白。设备厂商开发支持组播业务的设 备多数采用f p g a 芯片，成本极为昂贵，一般每片需要数百至数千美元：虽然少 数国外公司提供a s i c 样片，由于设计生产不在本地，无法快速响应客户的需求。 所以上海普然公司合作开发了多业务宽带接入组播交换复用芯片，简称宽带 复接芯片，是一种高性能、低成本、支持网络协议( i p 或者a t m ) 集成电路芯片。 该产品主要应用于数字用户线访问复用器( d s l a m ) 、第三代无线地面机站、及各 类光接入系统等宽带综合业务接入设备。由于该芯片具有组播功能，特别适合电 话会议、远程教育、视频点播等设备。本产品采用0 1 8 u m 芯片技术，减小了i c 尺寸和功耗、降低制造成本，增强了其在国际市场上的竞争能力。因此本项目产 品研发成功不但满足国内市场对该类i c 的需求、又可以逐步打入国际市场。本 项目的实旄，将完成了在中国定义、设计、生产高水平通讯专用芯片的全过程， 一支高水平的企业管理和技术设计队伍得以形成。 由于该类型的芯片国内尚无人生产，可借鉴的经验和技术很少。故在芯片正 式投入生产之前，对其进行仿真，测试其基本性能并发现和解决相关问题，是非 常必要。所以上海普然公司委托我们对该芯片进行相应的仿真研究。 1 2 现有的缓存管理算法 由于该芯片要用到缓存，就要对缓存进行管理，现有的缓存管理策略主要有 c s ( c o m p l e t es h a r i n g ) ，c p ( c o m p l e t ep a r t i t i o n i n g ) ，s m a ( s h a r i n gw i t h m i n i m u m a l l o c a t i o n ) 1 ，p o ( p u s ho u t ) 2 ，p o t ( p u s ho u tw i t ht h r e s h o l d ) ，s t ( s t a t i c t h r e s h o l d ) 3 - 4 ，d t ( d y n a m i ct h r e s h o l d ) 5 - 7 。我们主要介绍所要采用的c s ， s t ，d t 和s m a ，而其他的缓存管理算法 8 1 5 在这里就不详细介绍了。 c s 是将整个缓存空间在所有的队列之间共享。只要未满数据就可以进入， 当缓存全部占满才开始丢弃，每个队列的最大长度为整个缓存的大小。c s 的优 点是缓存利用率高，缺点是公平性无法保证，即缓存可被某一数据流垄断性占用， 导致其他数据流无法进入，被丢弃。设整个缓存大小为b ，第i 个队列长度为q i ， 总共有n 个队列，c s 表示如下： 2 电子科技大学硕士学位论文 wn q ，b ( 丢弃接收的数据) q 联接收数据入列) ( 1 2 】) ，；1r = 1 s t 是严格限制每个队列的长度不能超过预先设定的门限制，当队列超过这 个门限，开始丢弃。s t 的优点是公平性好，缓存不会被某些个数据源占满，s t 的缺点是当数据不均匀到达时缓存利用率不高，且在缓存即使未满的时候也会丢 弃数据。设预先设定的门限为t ，s t 表示为： q ，丁( 丢弃接受的数据)q 7 1 ( 接收数据入列) ( 1 2 2 ) d t 的核心思想：在任何一个瞬时，输出队列的门限是交换机中当前未使用 的缓存器大小的函数，当输出端口的队列长度等于或者超过当前的门限，这个端 口就会被锁定不会接收新的数据，直到队列长度降低低于门限或者门限提高高于 队列长度之前，所有到达这个端口的信元都会被丢弃。d t 的优点是自适应能力 强，兼具公平。唯一缺点是，d t 总要在缓存中保留一部分空间，这部分空间无 法使用。d t 可以表示为： t ( t ) 2o ( b 一q j ( t ) )其中a 为常数 ( 1 2 3 ) j = l s m a 算法中，存储器被分成了两个部分b 1 ，b 2 。b l 是用于交换机中的每个 端口队列的非共享空间，每一个队列都有一个只能被它自己使用的最小空间，当 某个队列的长度超过给它所分配的专用空问时，这个队列才开始占用b 2 的空间， 而b 2 在所有的端口队列中完全共享。 1 3 本文结构 本文结构如下：第一章首先介绍宽带接入的发展和现有缓存管理算法；第二 章对宽带复接芯片的原理结构和功能做了详细的介绍；第三章是对芯片仿真模型 的建立和实现；第四章对该模型进行仿真和数据收集，发现问题并提出相应的改 进意见；第五章是对现有的缓存算法进行了研究，并提出一种新的缓存管理算法； 第六章全文总结。 3 电子科技大学硕士学位论文 第二章宽带复接芯片的基本信息 2 1 芯片的基本原理 普然公司的产品主要是两块芯片n m u x 和l m u x ，这两块芯片组成的系统基本 结构如图2 卜l 所示： l 一- ：丹丑 ：7 7 、 x , j j j露 ， 一l j 。 b a d , ：p l n n ef l v d sb a s e d ) 图2 卜1 两块芯片组成的系统基本结构 该系统由两部分组成，1 6 个l i n ec a r d 和1 个n e t w o r kc a r d 。n e t w o r kc a r d 有1 个n m u x 芯片和1 个p r o c e s s o r ( 处理器) 组成，l i n ec a r d 由1 个l m u x 芯 片和6 4 个p h y ( 物理接口) 构成。数据( a t m 或者i p ) 首先经过n e t w o r kc a r d ， 经过p r o c e s s o r 和n m u x 的相应处理，然后把数据送到用户所在p h y 的所在l i n e c a r d ，再经过l m u x 的处理，将数据送到相应的p h y 中，用户从p i p 中直接收到 数据。当然用户把数据传给外界，和刚才所述的过程相反。在此芯片中，一个 p r o c e s s o r ，控制n m u x 和1 6 个l m u x ，对l m u x 实行带内信号控制。n m u x 和l m u x 的通信是基于l v d s 传输。 4 电子科技大学硕士学位论文 2 1 1l m u x 的基本思想和结构 每个l m u x 支持6 4 个端口( p h y ) ，1 4 个端口用作管理业务。其余端口 用作用户业务。 对用户接口，支持标准的u t o p i a2 接口标准。每个接口支持速率大约为 2 0 0 m b p s - - 4 0 0 m b p s 支持a t m 或者i p 业务。 同时具有8 b i t s 的微处理器接口，用于支持对设备和业务量的管理。 两个2 0 0 m - - 8 0 0 m 的l v d s 信道。其中业务广播可以在两个通道内传输， 用户数据只能在活动信道接受。带内的控制信号可以在两信道内接受。同时可以 和n m u x 进行互操作。 标准的j t a g 端口 2 1 2n m u x 的基本思想和结构 1 6 个2 0 0 m - - 8 0 0 ml v d s 端口，可以l m u x 进行互操作。 对上一级的网络，使用标准的u t o p i a2 接口。 3 2 b i ts r a m 接口。 8b i t s 的微处理器接口。 方框图如下： 图2 卜2n m u x 逻辑结构图 5 电子科技大学硕士学位论文 上行业务处理包括：下行数据的反压机制( 用于防止由于拥塞而导致的数据 丢失) ，地址转换，上行队列调度机制( 包括设置对列的权重，使用w r r 轮询机 制等) ，控制业务路径( 控制从微处理器接口中提取数据的软件) 。下面是上行业 务处理模块示意图： 图2 卜3n m u x 上行业务处理示意图 下行业务处理包括：上行业务的反压机制，地址转换，下行队列调度机 制，和控制业务路径( 控制插入到微处理器的数据的软件) 。下面上下行业务处 理模块： d o w n s t r e a mt r a f f i cp r o c e s 。s i n gm o d e l 图2 1 4n m u x 下行业务处理示意图 6 电子科技大学硕士学位论文 2 2 芯片创新点： 2 2 1 本芯片同时支持a t m 信元交换和包( p a c k e t ) 交换功能 a t m 信元结构是固定长度的，而包( p a c k e t ) 长度是变化的。我们采用了多 种队列来实现多优先级的信元交换和包交换功能。用来处理包交换的队列长度和 数量是自动调节而动态伸缩的。包的大小可以为1 5 3 6 字节的以太网包也可以是 6 4 k 字节的i p 包。由于采用以包为单位的调度算法，视频包的传输质量可以得 到有效的控制并以此减少用户终端的视频抖动。 2 2 2 先进的带内信令功能 带内信令是指通过l d v s 通道的，不仅有一般的数据信元，还有控制信元。 简单带内信令仅仅是把控制信号从一个c p u 传输到另一个c p u 。本项目的作法是 把控制信号从一个c p u 传输到另一方的芯片内，并且在芯片内的控制模块中将控 制信元解码并实施完成控制。 更进一步，本项目的带内信令功能不仅能在传输码流内嵌入控制信号，还可 以嵌入统计数据，完全省掉了一片c p u 芯片。对一个机箱可以节省1 6 个c p u 。 如下图所示： 7 1 乜了科技人学坝卜学位论文 简竹带p - j 侍挣& e 模式 毹数带肉彳盍令控带攒式 图2 2 - 1 带内信令模式示意图 2 2 3 具有组播交换功能 特别的地址设置及分检逻辑使芯片具有组播功能，这样可以把1 1 0 0 个信息 源( 例如电视节目) 不用特别的交换器件直接送到不同的用户去。如下图所示： 8 电子科技大学硕士学位论文 图2 2 - 2 组播示意图 2 2 4l v d s 四种传输速率可选 由于d s l a m 使用范围很广，配置给不同用户的带宽是不同的。网络运营商希 望d s l a m 设备能有相应的配置灵活性，以减低成本。本项目芯片提供了这种灵活 性a 本项目芯片l v d s 的传输速率可以有四种，即8 0 0 m b p s 、4 0 0 m b p s 、2 0 0 m b p s 及1 0 0 m b p s 9 电子科技大学硕士学位论文 第三章宽带复接芯片仿真模型的建立和实现 3 1 仿真总体模型的搭建： 根据此芯片的基本情况，要完成对该芯片的仿真，需要建立四个模型：业务 源，n m u x ，l m u x ，和数据接收模块。业务源主要模拟实际中业务。业务源分为单 播源和多播源。单播主要模拟点对点业务，例如用户和i n t e r n e t 连接。多播主 要是模拟视频点播，视频会议等业务。n m u x 主要复制多播数据到相应的l m u x ， 转发单播数据到相应的l m u x 。n m u x 到l m u x 基于l v d s 传输。l m u x 主要是通过 u t o p i a 接口和用户相连接，并按照用户对多播数据的质量要求，复制多播数据 到相应的接口p h y 中，同时转发单播数据到相应的接口p h y 。数据接收模块s i n k 主要模拟用户的功能，接受数据。同时也要对这整个系统的数据进行相应的统计， 比如记录源发动数据的情况，整个系统的传输时延和计算时延抖动等等。 基本的设计思想如下图所示： 图3 卜l 模型基本结构 模型结构在o p n e t 中的实现如下图所示 1 0 电子料技大学硕士学位论文 3 2 业务源的实现： 图3 1 2 模型在o p n e t 中具体实现 3 2 1 业务源实现研究 对业务源的产生，我们采用0 n o f f 类型。如下图所示： s t a r tt i m e t h n ea x i s 图3 2 - 1o n o f 模型 当经历了一个s t a r tt i m e 之后，业务源开始了交替的o np e r i o d 和o f f p e r i o d o np e r i o d 和o f fp e r i o d 长短可以是不同随机分布。o np e r i o d 等间隔 的产生c e l l ，同一个o np e r i o d 产生的c e l l 组成了一个p a c k e t 一个p a c k e t 中，两个c e l l 之间的间隔时问就是一个c e l l 的传输时间。如果设o np e r i o d 电子科技大学硕士学位论文 的平均时间为t o i l ，o f fp e r i o d 的平均时间为t _ o f f ，c e l 】的长度为l ，整个 源传输的平均速度是r ，则可以求得在o np e r i o d 中，c e l l 的间隔时间为：t = ( l r ) 术( to n ( t o n + to f f ) ) 此外，如果限制了p a c k e t 的最大长度，也就是限制了o np e r i o d 的最大时 长。这样当o np e r i o d 超过了最大时长，则需要将一组o np e r i o d 分成多组。 其中每个o np e r i o d 都不会超过最大时长。如果根据分布产生的随机o n o f f p e r i o d 的时间小于一个c e l l 的时间间隔，将为其补足个c e l l 的时间间隔。 所以在一个o n o f f 模型的数据源，需要确定的数据的是： s t a r tt i m e ：业务源产生数据的工作时间，可以是随机分布。 o np e r i o di n t e r v a l ：o n 期的时间长度，可以是随机分布。 o f fp e r i o di n t e r v a l ：o f f 期的时间长度，可以是随机分布。 s o u r c er a t e ：业务源产生数据的整体速度，一个定值。 c e l ln u m b e r ：o n 期c e l l 的个数，同时也就限制了p a c k e t 的最大长度， 和0 n 期的时问长度，预先设定。 在源的模型中，除了单播源以外，还要有组播源，且组播源的数量由s e s s i o n 来决定，因为s e s s i o n 是1 1 0 0 ( 公司要求) 个所以组播源也为i i 0 0 个，而单播 源的数目是固定的为1 0 2 4 个( 1 6 6 4 ，每个p h y 都有一个单播源) 。 按照公司要求，每个单播源的发送速率为6 4 k b p s ，多播源的速率分为三部 分：1 0 0 个源的速率为2 m b p s ，5 0 0 个源的速率为7 0 0 k b p s ，5 0 0 个源的数据为 3 0 0 k b p s 各个源分别产生数据，然后共同进入个发送队列，出队列时采用先 进先出调度算法。基本结构如下图所示： 1 2 电子科技大学硕士学位论文 源发送的相关数据格式设置如下： 单播数据： 数据部分占4 2 4 b i t s ，5 3 b y t e s 。f l a g 主要用来标识单播还是组播，h e a d e r 用来标识此数据要到达的l i n k 和p h y ，e o f ( e n do fp a c k e t ) 表示一个0 n 期产 生的最后一个c e l l l i n k w e i 和p h y w e i 主要是用来表示此数据要到达的l i n k 和p h y 的权重，在数据产生时为空，到达n m u x 和l m u x 之后才添加相应数据。( 这 些头部在仿真中全部设置为o b i t ，只是起标识作用，没有数据量) 下图为单播数 据： 图3 2 - 3 单播数据c e l l 格式 1 3 电子科技大学硕士学位论文 多播数据： 数据部分占4 2 4 b i t s ，5 3 b y t e s 。f l a g 主要用来标识单播还是组播，h e a d e r 用来记录产生此数据的源和要到达的目的地。e o f ( e n do fp a c k e t ) 表示一 个o n 期产生的最后一个c e l l l i n k w e i 、p l t y w e i 和s u b q w e i 主要是用来表示此 数据要到达的l i n k 和p h y 和p h y 中子队列的权重，在数据产生时为空，到达 n m u x 和l m u x 之后才添加相应数据。l i n k 、p h y 和$ u b q 表示出数据具体到达的 目的，在数据产生时为空，经过n m u x 和l m u x 时，经过地址转换才加入相应的数 据，便于后面的统计。 图3 2 - 4 多播数据c e l l 格式 3 2 2 业务源在o p n e t 中的具体实现 在o p n e t 环境的具体实现中，业务源的n o d em o d e l 如下图所示： 图3 2 - 5s o u r c e 的n o d em o d e l 1 4 电子科技大学硕士学位论文 u n i 和m u l t i 是两个p r o c e s s o r ，分别用来产生单播和多播数据，g a t h e r 是一个q u e u e 用来存储单播或者多播数据。p t 一0 是一个点对点的t r a n s m i t t e r ， 负责发送数据。 下面分别介绍各个部分的实现 u n i t 部分 单播源数据的产生。其p r o c e s sm o d e l 由三个状态组成，i n i t ( 初始化) 状态， i d l e ( 空闲状态) p k g e n ( 数据产生状态) 状态。有两个事件驱动，s ”一g e n 事件 ( 自中断) 和d e f a u l t 事件( 除了自中断事件以外的任何事件) 如下图所示：绿色代表的是f o r c e d 状态，当完成本状态的工作后，马上转 入下一个状态，不需要任何事件驱动。红色代表的是u n f o r c e d 状态，当完成本 状态的工作后，不是马上转入下一个状态，面是继续停留在原来的状态，直到有 事件驱动，才进入下一个状态。在本p r o c e s sm o d e l 中，i n i t 和p k _ g e n 是 f o r c e d 状态，i d l e 是u n f o r c e d 状态。 图3 2 - 6u n i 的p r o c e s sm o d e l 在i n i t 状态中，首先从参数配置文件中分别读出6 4 个单播数据源的设置 情况，包括该源状态( 活动还是关闭) ，产生数据开始时间的分布情况( 指数分 布还是p a r e t o 分布) ，o np e r i o d 的分布情况，o f fp e r i o d 的分布情况，以及该 源产生数据的速率。如果该源是处于活动状态，则产生根据数据开始产生时间的 数学分布随机得到该源产生数据的开始时间。然后在这个开始时间产生一个 电子科技大学硕士学位论文 s l f g e n 事件( 自中断，中断号为该数据源的代号) 开始进入p k g e n 状态。 当进入p k g e n 状态时，首先根据中断号得到数据源的代号，进而得到l i n k 号( 也就是哪个l m u x ) ，和p y 号。然后根据在i n i t 阶段得到的源的o np e r i o d 和o f fp e r i o d 的分布，得到o np e r i o d 和o f fp e r i o d 的长度，在根据源产生 数据的速率得到产生一个c e l l 的时问一o n s o t 随后在o n p e r j o d 的时问长度内， 产生数据，并把相应的参数设置到头部文件中，并把数据发送出去。 当数据发送完毕之后，回到i d l e 状态，经过了o f fp e r i o d 长度时间之后， 又产生自中断，产生s l fo e n 事件，再次进入p k g e n 状态，产生数据。在i d l e 状态，无需实现任何功能，只是其一个等待的作用。如此循环，源源不断产生数 据。流程图如下所示： 其他意外事件发生 图3 2 - 7u n i 产生单播数据流程图 m u l t i 部分 完成多播数据的产生。其p r o c e s sm o d e l 由三个状态组成，i n i t ( 初始化) 状态，i d l e ( 空闲状态) ，p k g e n ( 数据产生状态) 状态。有两个事件驱动，s l f - g e n 事件( 自中断) 和d e f a u l t 事件( 除了自中断事件以外的任何事件) 。如图所示： 1 6 电子科技大学硕士学位论文 图3 2 - 8m u l t i 的p r o c e s sm o d e l 在i n i t 状态首先从参数配置文件中分别读出1 1 0 0 个组播数据源的设置情 况，包括该源状态( 活动还是关闭) ，产生数据开始时问的数学分布( 指数分布 还是p a r e t o 分布) ，o np e r i o d 的数学分布，o f fp e r i o d 的数学分布，以及该源 产生数据的速率。如果该源是处于活动状态，则产生根据数据开始产生时间的数 学分布随机得到该源产生数据的开始时间。然后在这个开始时间产生一个 s l f _ g e n 事件( 自中断，中断号为该数据源的代号) 开始进入p k _ g e n 状态。在 此状态时，还要读入多播配置文件( 此文件设置了组播源到达哪些目的地) 并记 录在相应的数组a d d m a p 中，然后将这些信息文本的形式输出，并由此计算每个 p h y 的组播数据输入速率。 当进入p kg e n 状态时，首先根据中断号得到多播数据源的代号。然后根据 在i n i t 阶段得到的源的o np e r i o d 和o f fp e r i o d 的分布，得到o np e r i o d 和o f f p e r i o d 的长度，在根据源产生数据的速率得到长生一个c e l l 的时间一o n s l o t 随后在o n p e r i o d 的时间长度内，产生数据，并把相应的参数设置到头部文件中， 并把数据发送出去。 当数据发送完毕之后，回到i d l e 状态，经过了o f fp e r i o d 长度时间之后， 又产生自中断，产生s l f g e n 事件，再次进入p k _ g e n 状态，产生数据。 在i d l e 状态，无需实现任何功能，只是起一个等待的作用。流程图如下： 1 7 电子科技大学硕士学位论文 其他意外事件发 g a t h e r 部分 图3 2 - 9m u l t i 产生多播数据流程图 实质上是一个队列，将源发出的数据汇总，然后按照f i f o 的方式将数据发 送出去。 下面是其状态转换图 图3 2 - l o g a t h e r 的p r o c e s sm o d e l 1 8 电子科技大学硕士学位论文 其p r o c e s sm o d e l 包含四个状态，i n j t ( 初始化) 状态，i d l e ( 空闲) 状态， p k a r r v ( 接收数据) 状态，p k s e n d ( 发送数据) 状态。三个事件：p k a r r v ( 新的 数据到来时产生) ，s l f _ g e n ( 自中断产生，以便不断的发送数据) ，d e f a u l t ( 除了 以上两种事件以外的任何事件) 。 在i n i t 状态时，获取设置的队列的最大长度和队列调度的速度，然后自中 断，产生s l f g e n 事件，进入p k s e n d 状态。 在p k s e n d 状态，首先检查是否为空，如不为空，则从队列的头部取走数据 发送，经过一个时隙( 等于c e l l 长度队列调度速率) 又产生s l f _ g e n 事件。如 为空，则略过发送数据这一步。这样循环往复，不停的向外界发送数据。 当有数据到达时，产生p ka r r v 事件，进入p k _ a r r v 状态，首先获取这个数 据，然后查看这个队列是否达到门限，如果没有达到，就将数据直接插在对列的 尾部。如果达到，则直接将此数据丢弃。每到达一个数据都要产生一个p k _ a r r v 这个事件。 在i d l e 状态，无需实现任何功能，只是起一个等待的作用。下面是实现 g a t h e r 的流程图： 把数据直 接放入队 列的尾部， 如超过门 限直接丢 弃 p ka r r v 事件产生 读取队列调 度速率和队 列门限值 进入i d i e 状态等待 事件发生 其他意外事件发生 s l fg e n 事件产生 图3 2 - 1 1g a t h e r 实现流程图 1 9 按照先前 获得调度 速率取队 列头部数 据直接发 送 电子科技大学硕士学位论文 p t 0 部分：点对点的t r a s m i t t e r ，负责把数据发送出去。 3 3 n i l l x 的实现 根据公司提供的关于芯片的要求，抽象出了n m u x 的仿真模型。如下图所示 n m u l t i e a s tq u e u e 1 6 + 2 = 3 2q u e u e s1 6 6 4 + 1 2 1 0 2 5q u e u e s 图3 3 - 1n m u x 基本结构 在n m u x 的s d r a m 部分，设置了1 0 2 5 个队列，一个队列储存多播数据，所有 的多播数据全部存在一个队列中。其余1 0 2 4 个队列用来储存单播数据，一个p r y 对于一个队列。同时设置了三级轮询机制，保证优先级。对于单播，每6 4 队列 ( 也就是一个l i n k ) 进行第一级轮询，然后1 6 个l i n k 进行第二次轮询。第三 级轮询是在单播和组播之间进行的。 电子科技大学硕士学位论文 在片内部分，设置了3 2 个队列，每个l i n k 2 个队列，一个储存单播数据， 一个储存多播数据，同时设置了轮询机制。 当数据进来时，首先判断其是否单播，如果是单播，则进入相应的s d r a m 中的队列中。然后通过三级轮询进入片内，进入相应的队列中，经过一级轮询， 然后发送到l m u x 中去。如果是多播数据，首先进入s d r a m 中的多播队列中去， 通过和单播数据的轮询进入到片内，然后确定此数据要达到哪些l i n k ，复制此数 据到相应的多播队列中去，最后经过一级轮询，发送到相应的l i n k 中去。 3 3 1l q - m l t x 实现的研究 通过以上的分折，发现实现n m u x 的算法核。t l , 就是如何实现w r r 轮询机制。 v r r ( w e i g h t e dr o u n dr o b i n ) 是一种队列调度机制。通过队列设置权重，该队列 所占出口的带宽就是其权重所占整个权重和的比重。同时，w w r 可以保证在每一 个轮询周期中，最低权重的对列有一次调度。如图所示： q0 权重4 q1 权重3 q2 权重2 q3 权重1 图3 3 - 2w r r 示意图 下面用流程图来说明w r r 是如何实现的： 2 1 电子科技大学硕士学位论文 图3 3 - 4w r r 实现流程图 在n m u x 中，各个w r r 的思路和上述w r r 完全一致于是，在s d r a m 的三级w r r 中， 定义c w r r s c h e rl e v l s c h e r ，l e v 2 s c h e r ，l e v 3 s c h e r 1 i n k n u m 来完成三级w r r ( 1 i n k n u m 为1 6 ) 。l e v 3 s c h e r 1 i n k n u m 完成第一级1 6 个w r r ，每个w r r 涉及至1 j 6 4 电子科技大学硕士学位论文 个单播队列( n u n i c a s tq u e u e ) ；l e v 2 s c h