优游平台在哪里注册第33 卷 第6 期 电 子 科 技 大 学 学 报 Vol.33 No.6 2004 年12 月 Journal of UEST of China Dec. 2004 一种用于分组交换机的缓存管理算法 胡 冰， 李乐民 ( 电子科技大学 宽带光纤传输与通信网技术教育部重点实验室 成都 610054) 【摘要】提出了一种用于分组交换机中的缓存管理算法DT+SMA ，该算法把DT和SMA结合起来，具有两者的优点。 通过理论分析和仿真，得知在单优先级情况下DT+SMA 比SMA的公平性更好，在多优先级情况下SMA比DT更易于实现， 而且同时也能获得和DT相近的性能。 关 键 词 缓存管理; 仿真; 共享存储器; 分组交换机 中图分类号 TN 915.05 文献标识码 A A New Buffer Management Scheme Hu Bing ，Li Lemin (Key Laboratory of Brodband Optical Fiber Transmission and Communication Networks UEST of China, Ministry of Education Chengdu 610054) Abstract In this paper a new buffer management scheme called DT+SMA is presented. This scheme combines sharing with minimum allocation (SMA) and dynamic threshold (DT) arithmetic ，and we find it has the benefits of both DT and SMA. Through analysis the scheme in theory and simulation we can see that actually DT+SMA is better than SMA in fairness in single priority, and is easier to apply in multiple priorities model than DT when achieving the similar performance with DT. Key words buffer management; simulation; shared memory; packet switch 近年来，通信向分组化发展，在通信网络中需要有分组交换机。为了避免冲突，分组交换机采用了输入输出 排队等结构。将输出排队的各队列中的缓冲存储器合在一起，就成为共享缓存交换机，如图1所示。由于在给定 的丢失率的条件下共享缓存交换机所用的存储器容量最小，所以共享缓存交换机得到了广泛应用。由于在实际中 大部分交换机所交换的数据都为定长，所以考虑定长数据的交换情况。一个高效率的缓存管理算法对于共享存储 器交换机极为重要，缓存管理策略将会直接影响到一个交换机的性能。有两种经典的缓存管理算法：最小分配共 享(Sharing with Minimum Allocation，SMA)和动态门限(Dynamic Threshold，DT) [1，2] 。 输入端口1 输出端口1 输出端口队列1 共享存储器 … … 输入端口N 输出端口队列N 输出端口N 图1 共享缓存交换机模型 DT算法的核心是：在任何一个瞬时，输出队列的门限是交换机中当前未使用的缓存器大小的函数，当输出 端口的队列长度等于或者超过当前的门限，该端口就会被锁定不会接收新的数据。在t时刻，T(t)是受控的门限， Q (t) 是第i个队列的长度，在t时刻如果Q (t) ≥T(t) ，端口i就会被锁定，直到队列长度降低至低于门限或门限提高 i i 到高于队列长度( Q (t) T(t))之前，所有到达这个端口的信元都会被丢弃。 i 收稿日期：2004 − 07 − 06 作者简介：胡 冰(1980 − ) ，男，硕士生，主要从事交换机中缓存管理算法方面的研究. 第6 期 胡 冰 等: 一种用于分组交换机的缓存管理算法 657 在SMA算法中，存储器被分成了两个部分B 、B 。B 是用于交换机中的每个端口队列的非共享空间，每一个 1 2 1 队列都有一个只能被它自己使用的最小空间，当某个队列的长度超过分配给它的专用空间时，这个队列才开始占 用B 的空间，而B 在所有的端口队列中完全共享。 2 2 [3] DT具有很好的灵活性和很高的效率，但是当DT用于多优先级的时候 ，就变得比较复杂，得为每一个优先 级计算该优先级的总共的队列长度。SMA在用于多优先级的时候很容易实现，只要为不同的优先级队列提供不 同的自己使用最小空间就可以实现，但SMA的公平性(缓存管理中的公平性是指，在相同优先级下，带宽应该在 各个端口队列公平的分配)却无法很好的保证。本文提出一种新的缓存管理算法：DT+SMA 。 1 DT+SMA算法 在DT+SMA 队列中，缓存器也被分为两部分：B 、B 。 1 2 B = B 1 + B2 (1) 在数据占用B 的时候DT+SMA算法和SMA完全相同，可是在数据开始占用B 的时候中，要在B 中使用DT算 1 2 2 法，设q (t) 为每个队列超过专用的最小空间的队列长度，既q (t) Q (t) − V ，其中V 是为每个队列分配的专用 i i i i i 最小空间 N T (t) = α [B －∑ q (t)] (2) 2 i i 1 在这种方式下，DT和SMA被结合起来，得到了一种具有DT和SMA优点的缓存存储器管理算法。 2 性能比较和仿真结果 通过仿真来比较提出的算法和其他的算法的性能。选择一个8端口共享存储器的输出排队交换机作为仿真的 模型，每一个端口连接着一个单一的突发ON/OFF模型，每个ON/OFF模型的平均发送速率设为8 M /s ，其中ON期 持续时间服从均值为0.001 的重尾(Pareto)分布 ck c f (x) c+1 k ≤x ＜∞ (3) x 通过改变c可以改变函数的曲线形状也就是改变了源的突发性，而通过改变k可以改变函数曲线的位置。Pareto 分布的均值为 ck E (x) c ＜1 (4) c − 1 在不改变源平均速率的前提下(即保证Pareto分布的均值不变) ，为了得到丢失率随c变化(即源突发性变化) 的 曲线，就得必须相应的改变k值。初始化时c =1.9 ，由式(4)可得到k = 0.004 74 ，不断地变化c，同时由式(4)求出相 应的变化k值，就可得到丢失率随源突发性变化的曲线。OFF期的持续时间是服从均值为0.001 的指数分布，整个 的缓存存储器大小为160个信元。根据以上的参数设置，缓冲存储器很快就能达到稳态，所以把交换数据的虚拟 时间设为0.5 s进行仿线 单优先级 在单优先级的条件下，通过仿真来证明DT+SMA 的公平性要比SMA好。把DT+SMA和SMA中的B 都设为80 1 个信元，B 为80个信元。B 在8个端口内均分，每个端口的专用最小空间为10个信元。为简单起见，设DT+SMA 2 1 中的参数α为1，则可以由式(2)得到DT+SMA 的门限 N T(t)=B － (t) (5) 2 ∑ qi i 1 为了检验算法的公平性，令一个端口传输负载非常大，只要根据其他正常端口的丢失率大小就可以得到算法 的公平与否，所以令端口1传输负载很大，且端口1的ON期持续时间的pareto分布的c参数不断变大，使端口1的数 据的突发性越来越小。在这种条件下发现，r为丢失率如图2所示。DT+SMA算法中的正常端口的丢失率比SMA 要低，也就证明了SMA+DT 比SMA的公平性要好。 658 电 子 科 技 大 学 学 报 第33 卷 0.075 0.050 DT+SMA DT+SMA SMA 0.045 SMA 0.070 0.040 0.065 0.035 ) ) ) ) % % ％ ％ ( ( 0.030 ( / / ( / / r r r r 0.060 0.025 0.020 0.055 0.015 0.050 1. 5 1.3 1.4 1.5 1.6 1.7 1.8 1.80 1.82 1.84 1.86 1.88 1.90 1. 3 1.4 1.6 1. 7 1.8 c c 图2 端口7队列的丢失率变化曲线 高优先级端口队列的丢失率变化曲线 多优先级 在多优先级的情况下，DT根据文献[3]性能最好的是 Qi (t) α (B − Q(t)) (6) p p 式中 Qi (t) 是在t时刻端口i 中的p 优先级的信元的个数， 是优先级p 的参数。当i端口的p 优先级不满足式(6)的 α p p 时候，i端口对p 优先级的数据进行锁定，直到i端口的p 优先级重新满足式(6)之前所有到达i端口的p 优先级的数据 都会被丢弃。在不同端口不同的优先级也是如此，各个端口的各个优先级只需满足自己参数下的式(6)即可。仿 线个低优先级) ，对于高优先级的 =2 ，而对于低优先级 =1 。可以看出 α α p p DT在用于多优先级时必须计算Qi (t) ，即在一个端口的同一优先级信元的个数，在高速交换机中不易于实现的。 p 而对于多优先级下的DT+SMA ，只需在B 部分应用多优先级策略，而在B 部分用DT单优先级算法即可对整 1 2 体实现多优先级算法。在B 部分只需要令不同的优先级分配到不同的专用最小空间，设有2个优先级(1个高优先 1 级7个低优先级) ，设高优先级的专用最小空间为24个信元，低优先级为8个信元。这样在多优先级的高速交换机 中应用DT+SMA ，仅需分配到不同的专用最小空间即可，可见DT+SMA 比DT在多优先级条件下，更易实现。而 DT和DT+SMA 的性能比较如图3所示，DT和DT+SMA 中高优先级端口队列的丢失率相差不大。 3 结 论 通过仿真发现，本文提出的DT+SMA算法在单优先级的情况下确实比SMA具有更好的公平性，而在多优先 级的情况下，能获得和DT相近的性能，且比DT易于实现。所以DT+SMA具有DT和SMA两者的优点，在高速交 换机中的实用性更强。 参 考 文 献 [1] Kamoun F, Kleinrock L. Analysis of shared finite storage in a computer network node environment under general traffic condition[J]. IEEE Transactions on Communication, 1980, 28(7): 992-1 003 [2] Choudhury A K, Hahne E L. Dynamic queue length threshold for shared memory packet switchs[J]. IEEE/ACM Transaction on Networking, 1998, 6(2): 130-140 [3] Hahne E L, Choudhury A K. Dynamic queue length threshold for multiple loss priorities[J]. IEEE/ACM Transaction on Networking, 2002, 10(3): 368-380 编 辑 孙晓丹

　　2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。

　　3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。

　　4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

　　A11评价量规设计与应用-量规设计+反思【微能力认证优秀作业】.pdf

　　国家开放大学《中国古代文学(B)(2)》形考任务1-4参考答案 .pdf

　　2023年EXCEL版研究生考试考研英语考试词汇表字母顺序+乱序版（方便筛选背诵）.docx

　　原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者