（系统分析与集成专业论文）atm交换机缓存策略的仿真建模和性能分析.pdf

华永师范走学硕- t 一学位论文 a t m 交换机缓存策略的仿真建模和性毹分析 摘要 弄步转移模式( a t m ) 作为宽带综合盈势数字两( b _ i s d n ) 的佟递模式，具有离效 性单【l 灵活性，能够适应各丰中网络传输环城和不同的服务质量( q o s ) 要求，因丽被广泛蠼 于高速的骨干网中f 】。a t m 交换机的交换结构主要负责a t m 信元在交换机中的缓存与转 发是a t m 弼络技术的关键环节，壹接澎晌著瓣络豹佳能与壤量。缓存策硌( b u f f e r i n g s t r a t e g i e s ) 或称排队策略( q u e u e i n gs t r a t e g i e s ) 是a t m 交换结构设计中的重要内容，黪晦 信元在转发过程中的延迟和丢失，至今仍受到广泛的关注和研究。由于a t m 交换机缓存 模羹豹复杂性，利用理论推导的方式无法满足不阉的韭务模型翔缓存策略，西丽更多的是 采删系统仿真的方法进行研究。 系统仿真已被公认为燎继理论研究、实验技术之后，认识世界与改造世界的第三种手 段。本文在研究了捧酸穰黧匏基础理论和系统仿真的方法后，将其应瘸子a t m 阏络交换 枧的缓存蒙赂中，展开深入的研究。本文采用离赦事件髂囊原壤，对a t m 交按规鲍攘元 缓存系统进行了仿真建模，并对多种缓_ 稃策略和业务模测进行了分析比较。 本文蓄先利落离教事绊仿真淼理对输出完全分鞴缓存、输出完全共享缓存、输出溉合 缓嚣这三种基本的输出缓枣菠赂进行了建模，给嫩了三驰基本攒型的信茏到达帮信元离开 的仿真模块。井在均匀业势模型和突发业务模型下对三种基本模型进行r 分析比较，得出 的数据与理论值楣符合，分析结论也与实际情况相奶台，为进步深 研究复杂的缓存策 略葵定了基础。 随后，本文针对动态门限策略模型进行了建模与分析。在多种缓存策略中，输出共享 缓帮因为箕离效性和适中的复杂魔而被广。泛采用。在1 9 9 8 年a b h i j i tk c h o u d h u r y 和 e 1 l e nl ；t t a h n e 裁提出了动态l l 浆的概念，宅是壤摆售霓的捧敬长度动态缒调糕控制门隈 的种策略。在近几年中，一些国外学者针对该动态门限策略提出了改进方案”5 。本文在 对服有的动态门限进行仿真建模分析韵基础上，掇出了撒据缓存器的平均队长稚动态修正 门控剩参数静鸯逶应动态门疆方案。透避傍箕运行分毫巨，表明本文豹方案较撅寒的动态 门限方案具有更强的自适应性和更低的信冗丢失举。 最后，本文还对优先级业务进行了仿真建模分析。当今的宽带通信娩务要求更宽的帝 宽辜| _ l 更裹静速宰，它褥在建络中产生各穆滋台韭务鬟( 始多媒体遗攘 。这撵就对交换桃挺 出保证服务质量( q o s ) 制要求。其中有效的方法之一就是在交换机的转发过稳中考虑信 i 毕东师范大学预士学位论文a t m 交换机缓襻策略的仿真建模和性畿分析 元的优先缀。本文将本文挺出韵上述自适应的动态门陨策略推广应用剿优先级啦务摸溅之 中，芳建立了仿囊模型。邂过对大量的数掘进舒分辑和 e 较，骏涯了本文的尝适应动态f 1 限策略在优先级业务模型的方案中同样具有良好的性能。 论文构建了a t m 交换杌缓存系统的仿真模艘，实现了论文讨论的所有缓存策略，并 通过实验验涯了本文提出斡缓存策略的惶糍。论文豹研究结果将对a t m 交换搬缓存系统 的设计具有一定的应用参考价值。 关键字：褰鼓系统仿真a t m 交换枫缓存策略动态门凝优先缀业务横型 2 华东师范大学硕士学位论文a t m 交换机缓存策略的仿真建横和性能分析 a b s t r a c t t h eb r o a d b a n d i n t e g r a t e d s e r v i c e s d i g i t a ln e t w o r k ( b i s d n ) w i t h s t a n d a r d i z e d a s y n c h r o n o u s t r a n s f f r m o d e ( a t m ) i se n v i s a g e d t os u p p o r t n o t o n l y c u r r e n ts e r i c e s ，b u t a l s on e w s e r v i c e sw i t hv a r y i n gt r a f f i cc h a r a c t e r i s t i c sa n dq u a l i t y - o f - s e r v i c e ( q o s ) r e q u i r e m e n t s s oi ti s w i d e l yu s e di nh i g hs p e e db o n en e t w o r k sd u e t oi t se f f i c i e n c ya n df l e x i b i l i t y z q t h ee x c h a n g e a r c h i t e c t u r e so f a t ms w i t c h e sw h i c ha r er e s p o n s i b l ef o rb u f f e r i n ga n dp u t t i n gf o w o r da t mc e l l s ， a r et h ek e yt a c h eo ft h ea t mt e c h n o l o g ya n dh a v ead i r e c t l ye f f e c to nt h ep e r f o r m a n c ea n d q u a l i t yo f t h en e t w o r k ，b u f f e r i n gs t r a t e g i e so rq u e u e i n gs t r a t e g i e s ，w h i c ha r et h ei m p o r t a n tp a r t o f t h ea t m e x c h a n g ea r c h i t e c t u r e s d e s i g n ，h a v eag r e a t e f f e c to nt h ep e r f o r m a n c eo f t r a n s m i t i o n o ft h ep a c k e t ss u c ha sd e l a ya n dl o s s s ot h e ys t i l la t c r a c tw i d e l ya r e n t i o n sa n dr e s e a r c h e s f o r t h e c o m p l i c a c yo fm o d e l i n gt h eb u f f e r i n gs t r a t e g i e s ，t h e o r yd e r i v i n g c a n n o tf u l f i l v a r y i n g b u s i n e s sm o d e l sa n db u f f e r i n gs t r a t e g i e s s ot h es y s t e ms i m u l a t i o ni sa d o p t e dm o r eo f t e n 。 t h e s y s t e ms i m u l a t i o ni ss a i dt ob et h et h i r dm e a s u r eo f u n d e r s t a n d i n g a n dc h a n g i n gw o r l d ， f o l l o w i n gt h ef u n d a m e n t a lr e s e a r c ha n dt h ee x p e r i m e n t a lt e c h n o l o g y a r e rs t u d y i n gt h eb a s i c t h e o r yo f t h eq u e u e i n gm o d e l s a n dt h es y s t e ms i m u l a t i o n ，w e a p p l i e di ti nt h eb u f f e r i n gs t r a t e g i e s o fa t mn e t w o r ks w i t c h e sa n dd i dad e e pr e s e a r c h b a s e do nt h ep r i n c i p l eo f t h es i m u l a t i o no f t h ed i s c r e t ee v e n ts y s t e m ，t h i sa r t i c l ep r o p o s e dt h es i m u l a t i o nm o d e l so f c e l lb u f f e r i n gs y s t e mo f t h ea t ms w i t c h e si sp r o p o s e di nt h i sp a p e r , a n dc o m p u t e rs i m u l a t i o ni su s e dt oa n a l y s ea n d c o m p a r e t h ed i f f e r e n tb u f f e r i n gs t r a t e g i e sa n db u s i n e s sm o d e l s f i r s t ，b a s e do nt h ep r i n c i p l eo ft h es i m u l a t i o no f t h ed i s c r e t ee v e n ts y s t e m ，t h es i m u l a t i o n m o d e l so f t h r e eb a s i co u t p u tb u f f e r i n gm a n a g e m e n ts c h e m e sw e r ep r o p o s e d ，w h i c h a r ec o m p l e t e p a r t i t i o n i n g ，c o m p l e t es h a r i n ga n dp a r t i a ls h a r i n g a n dt h es i m u l a t i o nm o d u l e so f c e l la r r i v i n g a n dc e l ld e p a r t i n gw e r ep r e s e n ta n dt h es i m u l a t i o np r o g r a mw a sr n nu n d e rt h ee v e nb u s i n e s s m o d e la n db u r s t yb u s i n e s sm o d e l ，a n dc a m et oac o n c l u s i o nt h a tt h es i m u l a t i n gd a t aw e r ei n a g r e e m e n t w i t ht h et h e o r yd a t aa n dt h ea n a l y s et a i l l i e dw i t ht h ea c t u a ls i t u a t i o n - t h e s es i m u l a t i o n m o d e l sf o rt h ea t m s w i t c h e sl a i daf o u n d a t i o no ff u r t h e rd e e pr e s e a r c h a f t e r w a r d s 。t h em o d e l i n ga n dt h ea n a l y s i si nv i e wo f t h ed y n a m i ct h r e s h o l ds t r a t e g y c a r r t e do n a m o n gt h es e v e r a lb u f f e r i n gs t r a t e g i e st h eo u t p u tc o m p l e t es h a r i n gb u f f e rs t r a t e g yi s 1 华东师托大学礁二l ：学位论文 a t m 交换规缓襻策略懿仿真建摸和性巍分辑 w i d e l yu s e dd u et oi t se f f i c i e n c ya n dm o d e r a t ec o m p t e x i t y li n l9 9 8a b h i j i tk 。c h o u d h u r ya n d e l l e nl h a h n e p r o p o s e dt h ed y n a m i ct h r e s h o l dc o n c e p t t h ep h i l o s o p h yb e h i n di t i sa d a p t a t i o n o f t h et h r e s h o l df o re a c ho u t p u tl o g i c a lq u e u et ot h eq u e u el e n g t ho f t h ec e l l s al o to f l i t e r a t u r e s b a s e do nt h ed y n a m i ct h r e s h o l ds t r a t e g ya r ep r o p o s e di nr e c e n ty e a r s l 5 t “b a s e do nt h em o d e l i n g a n da n a l y s eo nt h eo r i g i n a ld y n a m i ct h r e s h o l ds c h e m e t h i sa r t i c l ep r o p o s e da na d a p t i v ed y n a m i c t h r e s h o l ds c h e m ew h i c hi sa d a p t a t i o no ft h et h r e s h o l dt ot h ea v e r a g eq u e u el e n g t h t h r o u g ht h e s i m u l a t i o n ，i tc o u l db ef o u n dt h a t o u rs c h e m ei sm o r ea d a p t i v ea n dh a sai o w e rc e l ll o s s p e r c e n t a g e t l a s t l y ，t h em o d e l i n ga n d t h ea n a l y s i si nv i e w o ft h ea d a p t i v ep r i o r i t ys e r v i c e si sc a r r i e do n s i n c et o d a yb r o a d b a n dc o m m u n i c a t i o ns e r v i c er e q u e s t saw i d e rb a n d w i d t ha n dah i g h e rs p e e d ，a l o to fm i xb u s i n e s s e sa p p e a rs u c ha sm u l t i m e d i ac o m m u n i c a t i o n a st h ee x c h a n g e sr e q u i r ea b e t t e rq u a l i t y o f - s e r v i c e ，o n eo f t h ee f f e c t i v ew a y si sc o n c e r n i n ga b o u tp r i o r i t yo f t h ec e l l si nt h e s w i t c h e s s ot h i sa r t i c l ee x t e n d e do u ra d a p t i v ed y n a m i ct h r e s h o l ds h e e m et ot h ep r i o r i t ys e r v i c e m o d e l sa n de s t a b l i s h e di t ss i m u l a t i o nm o d e l i n g t h r o u 曲t h ea n a l y s e sa n dc o m p a r i s o n so ft h e s i m u l a t i o nd a t a ，i tc o u l db ef o u n dt h a to u rs c h e m eh a sab e t t e rp e r f o r m a n c ei nt h ep r i o r i t ys e r v i c e t 0 0 s i m u l a t i o nm o d e l i n g so fb u f f e rs y s t e mo ft h ea t ms w i t c h e sa n di m p l e m e n t e da l lb u f f e r i n g s t r a t e g i e s d i s c u s s e di nt h ep a p e rh a sb e e ne s t a b l i s h e dt h r o u g hc o m p u t e rs i m u l a t i o n ，i t i s c o n f i r m e dt h a tt h eb u f f e r i n gs t r a t e g i e so u rp r o p o s e dh a v eab e t t e rp e r f o r m a n c e t h i sp a p e r w i l l h a v ear e f e r e n c ev a l u et ot h ed e s i g no f t h ea t m s w i t c hb u f f e rs y s t e m k e yw o r d s ：a t ms w i t c h ，s i m u l a t i o no ft h ed i s c r e t ee v e n ts y s t e m ，b u f f e r i n gs t r a t e g y b u s i n e s sm o d e l ，d y n a m i ct h r e s h o l d ，p r i o r i t ys e r v i c em o d e l i n g 4 华东师范大学硕士学位论文a t m 交换机缓存策略的仿真建模和性能分析 郑军俊硕士学位论文答辩委员会成员名单 姓名职称单位备注 顾君忠教授华东师范大学主席 陈树中教授华东师范大学 王新伟副教授华东师范大学 a t m 交接机缓存簧咯的铸真建模和性熊分析 学位论文独翎性声骥 本人新呈突的学位谂交是疵在等癖的稽导下避行酶研究工作及敢褥的研究戏聚据 我所知，除文中已经注明g l 用的内容终，本论文不包含其他个人已缀发表或撰写过昀研究 戏袋对本文蟪磺宠畿囊重要贡靛酶令人和集露，趣魏在文孛 # 了骥确虢爨并瘫苯逡意 作者签名：日期：鲢：苎 。 学位论文授权使爝声鹾 本人完全了解华东疼范大学蠢关保馨、使用学位论文酶规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的彀 子版和纸质版。有权将学位论文用于非赢利目的的少量复制并允许 论文避入学校漤譬馆搜查阏。有权将学位论文酶内察编入鸯关数据 库进行检索。有税将学位论文的称题和摘要汇编出版。保密的学位 论文在怒寮后逵震本规定。 学位论文俸者鍪名：勤1 豸故 日期：。x ! 【 导师张御姆等 日期：翌蔓! 社 华衷师范太拳颈圭学链论文 a t m 交换壤疆嘉燕晦犍谤寞建攘和拄艉势辑 1 1 研究意义 第一章概论 异步转移模式( a t m ) 作为宽带综合业务数字网( b i s d n ) 的传递模式，由于其高 通信曩、快速分组处理、低延迟和对吾静类型通信业务独立的传递特经，越来髓；i 起人们 极大的关注和重视。它是近年来遴信研究的热点秘未来通信网络的方囱。 异步转移模式的发展经历了认识的过程。人们起初认为，定义新的愿高速率就会自然 发震到电骛交换综合韭务数字网。璃步转移模式瞧路交换是宽带综台韭务数字羽的摹本技 术。然两，闻步转穆模式的固定信邋维构既不能瀵足未来业务要求的灵灞蛙，媳不能蠢效 传输可变比特率信息。综合业务数字网的电路交换和分组交换重鼹结构不能产生综合传输 的经济效益。灵活和有效酌交换技术，业务独立豹传输技术成为关键闷蹶。侠遮分组交换 具番缀赢盼艇络露峨量，虽分组处理快速、摊驮蜒迟较小。 根据上述思想进行了系列的实验，出现了异步时分交换( a t d ) 。i t u t 将快速分组 交换和异步时分交换概念标准纯，命名为辩步转移模式( a t m ) ，以便和常规分魏交换褶区 别。它还摆定a t m 为宽带综合韭务数字刚的交换秘多路簸爆技术。售息在a t m 中鞋毽定 长度的短分组的数据流进行传输。避种信息分组称作信元。a t m 能够对备种业务进行高界 吐量、低延迟和业务独立的传递。 a t m 不仅能够满是瑗寓所考瓣嬲终擐务，还可以满足未来各种不同抟辕特性积 q o s ( q u a l i t yo fs e r v i c e ) 需求的应用。a t m 采用的固定短长度的信元传送信息方式有利于 高效灵活的利用网络带宽，并且它具有的低延时和低丢失率的特性能为几乎所有的网 终应燃提供霹靠懿o o s 缳谖。迓凡年来，a t m 技术在国蠹受到越来越多戆重撬，摄多骚 究机构和应片j 部门都在积极研究开发和运j e f = l 这项技术。 a t m 交换机的交换结构主要负责a t m 信元在交换机中的缓存与转发，是a t m 网络 技术耱关键兹巧节，盎接影魄羞鼹络豹蛙戆与震萋。缓毒策赂( b u f f e r i n gs t r a t e g i e s ) 或舔 排队策略( q u e u e i n gs t r a t e g i e s ) 是a t m 交换结构蹬计中的霪要内容，影响到信元在转发过 程中的延迟和丢失，至今仍受到广泛的关注和研究f ”l 。一个好的缓存策略，不仅要具有良 箨的瞧艟( 糕延运移低丢失攀) ，还必绥楚擎易于实现，才糍痤瘸予裹速懿交换爨。本文的 牮末娣范大学硕士举位论文a t m 交换机缓存策略豹仿真建横和性稔分析 个研究重点就是器提爨享孛篾零嚣嶷效熬缓存策蜷。 当今的邋信业务要求更窝的带宽和更离的速率，宅将在网络中产生嚣张漫仑业务壁( 妇 多媒体遴信) 。这攒就对交换枧提出缳派服务质璧( q o s ) 瓣要戴。其中较毒敢 孽方法之一 就是在交换桃转发信元的过程中考虑售元黪饯先级。a t m 楼元豹优先缀分为丢弃优先校秘 时蜒优先级。在现有的a t m 债元格式中包括了信元丢失攀蛇字段c l p ，可以用采区分a t m 网络孛的钱兔缓业务。本文瓣另一个研究豢熹裁燕基予q o s 豹a t m 交换撬瓣丢嘉优先缎 缓存策哒戆蟛宠分摄。 1 。2 国内外磅究现状 自从提出a t m 的概念以来，a t m 交换结构就戡是嗣内外学者研究熏点之一，包括 拓扑结构、缓存方式、控铷视理、性能分骈等。劐目前为i e ，关于a t m 交换臻构商关技 术己基本上成熟，讴一些新的研究进展仍不时出现。 关于a t m 交换机的纂本缓存模型翠在上世纪9 0 年代初就已经开始研究了，但国内的 研究一般都是通过建立解析模型进行公式摧导，这样的方法相当麻烦并且通用性不商。阑 外的一些相关研究则利粥一然大型研究机构或公司的仿真嚣来进行实验分析，丽这些仿真 器的内部设计并不公开。因此国内外的文献中，几乎没有涉及缓存模型的建模方法的文献。 在缓存策略中，输出共事缓存因为其菇效性和适中的簸杂度而被广泛采用，在输出浆 享缓存的排队蘸略里，较常用的有凭控制，门限控制以及推出控制三种。无控制的公平性 最差，而推出控制公平性最好，但复杂废太大。因此较多地采用门限控制。1 9 9 8 年a b h i j i t k c h o u d h u r y 和e l l e nl h a h n e 就提出了动态门隈的概念，因其简单面离效的特点，受 到国外学者广泛关注，并提出了一魑针对动悫门限策略改进方案。本文在时原有的动态门 限策略进行仿舆建模分析的基础上，提出了新的改进方案。 随着宽带网络豹发展与营及，出现越来越多的宽带网络的应用。关于a t m 变撩机的 优先级缓存模型，隧内外的研究不少。但利用动态门限策略来设计优先级缓存模型的研究 并不弗。 1 3 本文的独特之处 文献f 1 1 - 12 l 避过建立麟褥模銎秘公式攘霉游方法，褥到a t m 交换撬麴避缳豹瞧8 l 数弦e 类 疆的方法在鞠内文献孛瘩瑰瓣浇较多。然掰它凳i 盼澍菜照特定豹揍型，不麓赢接琏鞲 2 华东师范大学醐士学位论文a t m 交换机缓存策略的仿真建模和性能分析 于一些复杂的业务模型，例如突发均匀业务，另一种方法魁采用计算机仿真技术对a t m 交换机的排队系统进行仿真。仿真可逸用于蔷种不同缓存策略和业务模型，而且得到的有 统诗意义戆傍囊结果毙涯鞑瓣更接近粪实婕凝。帮努文献 1 3 1 4 分缮了荦l 霸嚣静静诗葵提供 真器针对某些特定的a t m 交换机进行分析的结果，但都没有涉及仿真建模的方法。 本文在研究了排队模型的基础理论和仿真建模方法后，将其应用于a t m 网络交换机 熬缓存策略中，震舜深入熬骚究。本论文采耀凑数事传系统傍寞方法，铮澍a t m 麴三辞 基本的输出缓存策略和两种业务模型，给出了详细的建模方法。通过实验分析，验证了模 型的正确性。 隧嚣，本文在对蘸舂麴动态门疆避行建模分毒厅麴基疆，捷窭了撮据缓存嚣麴平筠撵 队长度来动态修正门限控制参数的自适应动淼门限方案，通过仿真运行分析，表明本文的 方案较原来的动态门限方案，艇有更强的自逑应性和更低的信元丢失率。 本文还结合了蕊毙缓动态门陵策漆鞋及鬻鼗事镣仿真方法，霹a t m 交换瓤静虢先缀 缓存模型进幸亍仿真建横并提出了改进娥略。遇过仿真实验，对多种地务模型下的a t m 交 换机模型进行了分析和比较，表明本文提出的改进的优先级动态门限策略具有更好的性能。 论文麓结捣如下：第一章，舟绍了本文豹醑究意义和国内乡 静辑究状况。第二章阐述 了当蘸a t m 领域的楣芙背景知识。第三章介绍了排队系统理论和系统仿囊领域的芙键技 术。第四章研究了三种基本的输出缓存策略，并根据离散事件仿真原理对遗三种输出缓存 策略进行了仿冀建模。通过实验进行了分析与比较。第五章在对动态门限羧翻方案进行了 详细磅究的基破上，提如了自遴应动态门限缓存蓑略，通过建立仿真模型，对无控划策略、 推出机制策略、静态门限策略、动态门限策略和自适应动态门限策略进行了分析比较，验 证了本文提出的自适应动态门敝策略其有更好的性能；第六帮，钎对优先缀监务遴行建模 分童蓐，势且把爨透盛动态门限方案推广到忧巍级业务豹模型中，并透过傍襄建模，验证了 自适应动态门限镶略在优先级业务中同样具有更好的性能：第七章，对本文研究内容进行 了总结与展望。 1 4 本章小结 本章主要讨论了本文的研究意义和相关的国内外研究状况，介绍了一些关于a t m 网络与系统访真的背景知识。从中可以看到，本文的研究具有一定的理论意义和实际 癍蠲徐馕。 华东师范人学硕上学位论文 a t m 交换机缓存镱略的仿真建模和性能分析 第二章a t m 网络与a t m 交换机概述 2 1a t m 技术 a t m 意即异步传输模式( a s y n c h r o n o u s t r a n s f e rm o d e ) 。a t m 交换技术是一种包含传 输、组网和交换等技术内容的新颖的高速通信技术。它是由产业界、用户团体、研究机构 和标准化组织开发和定义的。它被设计成满足下一代通信技术要求，如支持带宽资源的有 效利用，有利于由各种类型的网络互连以及能够提供各种先进的通信业务。它被看作是先 进和有效的军用和民用通信的先进通信技术。 宽带综合业务数字网( b - i s d n ) 是未来电信网的发展方向，a t m 是b i s d n 技术的 核心【l ”。自9 0 年代以来a t m 直是国际上电信领域的研究热点。它不仅能够满足现有 的所有网络服务，还可以满足未来各种不同传输特性和q o s ( q u a l i t y o f s e r v i c e ) 需求的应用。 a t m 采用的固定短长度的信元传送信息方式，有利于高效灵活地利用网络带宽，并且 它具有的低延时和低丢失率的特性能为几乎所有的网络应用提供可靠的q o s 保证。近 几年来，a t m 技术在国内受到越来越多的重视，很多研究机构和应用部门都在积极研究开 发和运用这项技术。 2 1 1a t m 起源和发展 a t m 的概念起源于1 9 8 3 年美国贝尔实验室技术人员提出的快速分组交换和1 9 8 4 年法 国电信提出的异步时分交换的设计思想。快速分组交换采用硬件交换进行路由选择，采用 固定分组长度。简化差错控制规程从而使接入速率可以达每秒百兆比特以上，分组传输 和处理时延可以达到微秒级，并实现实时分组交换。异步时分交换采用1 6 字节的长度，其 中1 2 字节为信息段，4 字节为分组头，分组头用于进行交换处理。这种交换方式端口速率 也可达每秒百兆比特以上，而且时延极小，可以实现话音、数据和图像综合应用。 1 9 8 5 年，法国正式向国际电联( i t u ) 提出建议草案，国际电联到1 9 8 8 年形成了第一 个建议i1 2 。1 9 8 8 年，国际电联将a t m 选定为实现宽带综合业务数字网毋- i s d n ) 的基础， 到1 9 9 0 年，国际电联正式建议将a t m 作为宽带综合业务数字g 日( b i s d n ) 的技术体制，从 而全面开始a t m 标准和实用技术研究并于1 9 9 2 年7 月由美国f o r es y s t e m s 率先开发山 4 华末孵托大学颈1 ：学位诧嶷 a t m 交换现缓存策醛鹩仿真建摸帮 哇黥势牺 了a s x 1 0 0 系列a t m 交换机。目前正以种可作为宽带应用的赫本技术而用在局域网 ( l a n ) 和广域网( 、n ) 中。 2 i 2a t m 技术的特点 a t m 作为电信网的一种新技术，不仅适用于崮迷信息传送和对服务质量( q o s ) 的支 持，述其备了综合多释渡务翁髭力，以及动态带塞分既与连接营璎能力和对已有投宋的兼 容性。 ( 1 ) 对服务质量( q o s ) 的支持 。蟊象当篱元翻这黠臻窭翡秘虻，剜 信元在缓存器中等待，具有相同目的输出端口的等特信元组成一个队列。 3 1 3 接酞系境舱性能溅发 研究排队问题的目的，是研究排队系统运行的效率，估计服务质鼹，确定系统参数的 最优值，以决定系统结构是否台理、研究设计改进措施等。所以必须确定用以判断系统运 行爨劣豹莲本数耋捂栎，骚究搀酝秘麓虢是苕先袁蹬遮整数量捂标戆概率分毒或特缝蘧。 这些指标通常是： ( i )服务员的效率。服务员有忙期和闲期。忙期指从顾客到达糍闲服务机构再次为 空阕垂遮较辩闯长度，帮辍务撬撩连续繁忙静时闻长嶷。它关系至簸努黄麓工搏强发。 亡 期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标。服务员的效率是指在 整个过程中服务员忙期总和与总时间的比例。 ( 2 )疆客豹捧簸瓣淘。簸客鹫这焉，在酝伍中等待摄务豹对黼( 舞票蔟客黧这嚣因 服务员空闲而直接接受服务，则该顾客的排队时间为零) 。顾客的排队时间是顾客满意程度 的一项指标。 ( 3 )捧飘静长菠( 融剜长度) ，攘在系统中簿酸等待疆务静联客数。 系统顾客数= 排队长度+ 正在接受服务的顾客数 一般情形，系统中的顾客数( 或队长) 越大，说明服务效率越低，排队成龙，是顾客擐厌 颓静。 ( 4 )逗留时间，指一个顾客在系统中的停留时间。等待时间，指一个顾客在系统中 排队等待的时闯。 逗蟹对淘= 捧驮时间+ 黻务时闻 在机器故障问题中，无论是等待修理戚正在修理都使工厂受到停工。所以逗留时间( 停 工时间) 怒主要的；但一般购秘、诊病簿问题中，顾客们主要所关心的是等待时闻。 3 1 4 排队系统长期运行的性能测度 ( )记时闻周糍为t 。t 时刻系统中的顾客数为“t ) ，酞列长波为l 捺) ，置为 3 华东师范大学硕： 学位论文a t m 交换机缓存策略的仿真建模和性能分析 0 ，”时间区间内系统中恰有i 个顾客的总时间。 御l ：半：辩t t 1 f l ( t ) d t 俘， 系统中的平均顾客数l = = i ( 土) = 一f ( 3 1 ) 1 j = 0 卜孚：辩t ，：枷 l q 灿( 3 - 2 ) 系统中的平均排队长度l a2 1 f2 委i l 2 ( t ) d ( 2 )记顾客在系统中的平均停留时间为w ，顾客在队列中平均等待时间为w 。 w ：土y w n o _ 一 w q = 吉w q 。 式中w i 、w 。i 分别代表系统中第i 个顾客的停留时间和等待时间，n 为顾客数。 ( 3 ) 平衡方程【1 6 】 l = 五+ w 即：平均队列长度= 顾客的到达率+ 平均等待时间 l ( t ) ( 3 - 3 ) ( 3 4 ) ( 3 - 5 ) 闰3 2 信元排队模型图 图3 , 2 为信元排队的模型图，其中x 轴代表时间，y 轴代表队长。每个双向箭头的左 箭头代表信元的到达，右箭头代表信元的离开因此双向箭头的跨度为第i 个信元的等待 时间w 。由图可得： 4 华东师范人学硕l 学位论文a t m 交换机缓存策略的仿真建模和性能分析 l = 亭f c r 瑚= 专善= 了n 万1 善nw ，= 丑w c ，扪 3 1 5a t m 交换机缓存的排队模型 交换机缓存模型的顾客是a t m 信元，顾客总体是无限的，排队长度( 即缓存容量) 是有限的( 即当信元到达时，如果缓存已满，则信元丢失) 。信元以单个到达的形式，按一 定的随机时间间隔到达交换机的输入端口。如果输出端口忙，则信元在缓存器中排入其目 的输出端口的队列，输出端口( 即服务员) 按先到先服务的规则转发信元。由于a t m 交 换机的各个输出队列的信元目的输出端口不同，因此信元不能相互转移队列，等待的信元 一般不能中途退出( 除了推出机制外) 。 由此上分析可以看出，a t m 交换机缓存系统是一个复杂的排队模型。文献【l 】通过建 立解析模型和公式推导的方法，得到了a t m 交换机的近似的性能数据。类似的方法在国 内文献中研究得比较多，然而它们只能针对某些特定的模型，不能直接应用于一些复杂的 业务模型，例如突发业务流。另一种方法是采用计算机仿真技术对a t m 交换机的排队系 统进行仿真。仿真可适用于各种不同缓存策略和业务模型，而且得到的有统计意义的仿真 结果比近似解更接近真实情况。 3 。2 系统仿真简介 系统仿真是以系统理论、形式化理论、随机过程与统计学理论和优化理论为基础，以 计算机和仿真系统软件为工具，对现实系统或未来系统进行动态实验研究的理论方法i 。 从系统仿真的实施过程来看，系统仿真是通过对所研究系统的认知和了解，抽取其中 的基本要素和关键参数，建立与现实系统相对应的仿真模型，经过模型的确认和仿真程序 的验证，在仿真实验设计的基础上，对该模型进行仿真实验，以模仿系统的运行过程，观 察系统状态变量随时间变化的动态规律性，并通过数据采集和统计分析，得到被仿真系统 参数的统计特性，据此推断和估计系统的真实参数和性能测度，为辅助决策提供依据。 3 2 1 系统仿真的特点 从学科领域来看，系统仿真是运筹学的一个重要分支，它与线性规划和网络技术一起 被称为运筹学在应用领域中的三大支柱。在求解复杂系统中，系统仿真具有独特的优越性： 1 5 华末掰范大学硕士学位论文a t m 变换规缓存策酶抟仿真建模和挂黪癸辑 ( 1 )系统仿真技术已成为继理论分析和实物实验之后认识客观世界规律性的新型 手段它可以将研制过程、运行过程和实施过程放在蛮验室中进行，具有良好的可按制、 无菝葬强、可复磊性帮经济注等特点。 ( 2 ) 系统仿真谯理论上体现了实验思考的方法论。用它可以探索高技术领域和复杂 系统深层次的运动机理和规律性，给出人们直观逻辑推理不能预见的系统动态特征，具有 毒季学静宠骏链。 ( 3 ) 对于包含多种随机因素的舞杂系统，通常难以用数学模型成解析方法做精确地 描述和求鼹。系统仿其则可根据系统内部的逻辑关系茅数学关系，面向系统的实际过程和 彳亍为寒鞫逡仿真摸窭，在穰多程设或誉徽缓设魏翦撬下建立包括系绫主要因素释翼俸缨节 的模型框架，并通过仿赢实验运行， 导剿复杂系统的解。 ( 4 )系统仿真建模具有面向过程的特点。仿真模型与所研究鬟统的运行过程在形式 上衣逻辩上存在对应经，避免了建立亨斑象数学穰壅的溺难，显著笾纯了建模蓬程。 ( 5 )随着系统仿真理论和计算机技术的发展，系统仿真以跻身于高新技术领域。目 前已列人我国国家和国防关键技术发展计划。 3 2 2 系统仿真的建模和类别 研究一个真实系统或来来系统的性能，往往需要建立对应于该系统的模型，遴过对模 型的详缃研究，飙中抽崴出系统豹基本性能测度。 所谓模型就是对实际系统的一种抽敷的、本质的描述。首先，模型必须是现实系统的 一种抽象，它是在一定嫂没基件下对系统的筒纯。其次，摸型中必须包含系统中约主要围 素，模型不可能与实际蘩统完全对斑，两只应当包含那磐决定系统奉璇属性静重要戮索。 第三，为了进行定量分柝，模型中必须反映出个主要因黎之间的逻辑燕系和数学关系t 使 模型对系绫具有代表性。 待其系统同样必缀符台上述各项癸求。仿真模型的特点在于面囱阏鼷和面向过程静建 模过程，并且适合于在仿真环境下，通过模仿系统的行为来求解问题。 仿奏模型基本上可分为离散事件系统仿真模型和连续系统的仿粪模型两类，他们主要 取决于骄醑究系统的性质。在离散事伴簌统中，表示系统性能静状态变鬟凳在隧橇的时间 点上发生跃变，而在两个时间点之间，蒙统的状态不发生任何变化。在连续系统中t 系统 的状态变餐与时闻和某些参变量( 如时闺、湿度、压力簿) 之闻存在禁静连续的函数关系， 6 肇东| i | l 麓大学硕士擎往论文 a t m 交按辊缓夺肇略黪仿真建搂静毪戆势辑 当参变量发生变化时，系统状态也随之发生相应的连续变化。 本文研变的a t m 交换极鹃缓存摸鼙孛，对同上数有限个或至多霹列个点上发生的离 散事件( 信元到达事件和信元离开事彳牛) 在该瞬间政变了系统的、状态，例如输出端翻的忙 闲和信元的排队长度( 即信元占用缓存区单元的个数) 。因此a t m 交换机缓存系统悬离散 事律系统，鼓本文采用舞数事转系统仿囊方法来研究a t m 交换枕缓存系统。 3 2 3 仿舆系统的基本步骤 系统傍宾熬建模袋解与其它建模方渡论秘不圈点主要在子其建援瓣不唯一蛙嚣l 求勰 过程的实验性。有鉴于此，系统仿真必须遵循一定的步骤”7 1 ，才能锞证建模的有效性和仿， 真运行结果的正确性。 ( 1 )瓣甥翔题秘爨标设定。每瑕糖龚毳 究罄应觚掰臻究系统黪说明嚣始，更蠢薅该 系统具有深入的了解，才能为仿真建模与仿真运行提供可靠的基础。仿真建模的目标是指 通过仿真能够回答的问麒，因此在问麒阐述阶段中，必须首先对应用黑统是否能够回答这 个趣题秘遮瑙预定嚣椽俸爨判断。在确定一致试可的嚣标戬后，还蔫逡簿搓述这些秘据憨 主要环节和状态变量，明确定义所研究问题的范围和边界。 ( 2 )仿真建模。仿赢模型是对所研究系统运行过程的一种抽象描述并能反映系统的 本质属瞧。谤寞建模其鸯本麦疆困毒懿特点，透露镑鬟建模是蚕彝朗麓弱运牙过疆戆建模 方式。在离散事件系统仿真的建模中，主要应根据随机发生的离散事件、代表系统中所描 述主要对苏的实体流队疑仿真时间的推进机制，按照系统的运行进程来建立模型。 ( 3 )傍龚程寒弱缡螽纛验迂。崧矮涛谚囊模鍪转纯戒嚣篓摄旋识别积挟雩亍静鼗筠， 才能通过计算机进行必要的仿真实验。然而，仿真程序的编制过程，完全依靠编程人员对 仿真模型的理解，并将这种理解转变成相应的仿真程序。如果这个转窝过程存在偏差或错 误，释搿编翩越莹窦程黟整摹耱婕表经过礁获戆谚囊模型，盎蒋馕傍粪缮票失去惹义，因 此，需要对仿真程序进杼验证。所谓仿舆程序的验证魁指对仿真程序的逻辑和数学关系以 及输入输出响应与仿真横型的一致l 生所进行的测试和榆验。 4 )傍囊辕窭缝聚艴统诗分辑。对傍奏模型进行多次独立莺复运行嚣，霹敷褥弱一 系列仿真输出响应和系统性能测度的均德、标准差、娥太和最小数值、变异系数、观察数 等。要估计系统的总体参数及其分布特征，需要在仿真输出样本的基础上，进行必要的统 诗努裾帮绫诗箍断。 1 7 华东师范大学硕士学位论文 a t m 交换机缓存策略的仿真建模和性能分析 3 3 离散事件系统仿真基本原理 系统的状态通常可用一个或多个状态变量来表示。在离散事件系统中，状态变量 仅在随机的时间点上发生瞬间的跃变，而在两个相邻的时间点之间，系统的状态保持 不变。系统状态发生跃变的现象，是由于各种流动实体进入系统后，在各个环节上触 发产生的随机离散事件所引起的，并且在离散事件发生的时刻上，可以启动或终止某 一具体