QoS技术中令牌桶算法实现方式比较

所需积分/C币:49 2018-04-24 14:00:07 2MB PDF
63
收藏 收藏
举报

QoS技术中令牌桶算法实现方式比较,关于QoS令牌桶应用的算法。
研究论文 李晓利等:QoS技术中令牌桶算法实现方式比较 ZTE COMMUNICATIONS 按照规定的速率向桶中存酸令牌 速率的比值:Te= CBS/CIR,每次添加 的令牌数为CBs个;(2)一次性添加, 常由此接口发送的报文 只有当令牌桶中没有令牌时才添加 发送的分组 令牌,如图6所示,添加令牌的数量是 △ Ix CIR(△t是当前时间与上次添加令 (0 pDD C 令牌楣 牌的时间之差),且是一次添加完毕, C 分类 队列 并不是按照一定速率添加。 图3 3.1.3报文处理流程 LR进行流量限制 入队媛存 示意图 般的报文处理方法如图7所 示:当报文到来后,直接与桶中的令 但是在实际应用中,令牌桶究竟是怎牌数相比较,如果有足够的令牌就转 么实现的?令牌桶中的令牌是怎么添发,如果没有足够的令牌则丢弃或缓 EBS CBS 加的?报文的处理流程又是什么样存。这种令牌桶处理方式在突发流量 的?下面就简单谈一谈令牌桶在业界的处理上没有优势,也就是说当存在 EBS 的实现方式 较大的突发流量时,令牌桶可能会由 于没有足够令牌无法处理报文,而且 CBS 3.1单速率三色标记算法的实现 在没有突发流量且报文到达速率较 cBs承诺突发尺可EBs超颐突发尺寸 大时,报文处理流程也不连续,有时 ▲图4单速率三色标记算法的令牌桶构成 1.1桶的构成 会因为令牌数量不足而造成丢包。 在令牌桶的构成上,目前业界有 为解决这种无谓的丢包问题,目 两种方式,如图4所示。 前业界采用了一种借贷机制的报文 可以由一个桶实现,即C桶是E桶处理方法,如图8所示。当报文到来 是否到是』添CBs个 中的一部分(图4上),最终桶的容量是后,只要令牌桶中有令牌,无论数量 加时间 令牌 由EBS决定的。不管有没有突发流量,是否足够,都可以转发报文。当令牌 EBS不能为0,必须大于或等于CBS。数量小于报文长度时,就可以欠债转 这种实现方式完全按照令牌桶的定发,即转发后令牌桶中令牌数目为 等待 义来实现,因为CBS和EBS都是令牌负;当下次添加令牌的时候,先还清 桶的参数,所以放入一个相同的桶实所欠债务,再继续转发报文。这种处 ▲图5单速率三色标记算法的令牌 添加流程一 现,通过突发计数器来进行区分。也理方法较前者在处理突发报文时有 可以由两个栢实现(图4下),即C桶和优势,能够保证报文发送的连续性。 E桶分开实现。如果不允许有突发流 量,EBS则设置成0。 3.I4实现方式比较 桶中是否是,源加C用×△ 假设令牌桶的总容量为1000k 育令牌 个令牌 3.1.2令牌添加 CIR为125kh,报文到达的速率为 令牌桶的添加完全依照 REC规定实现,按照恒定的速「报文长度和令牌中 等待 率CIR添加。即每隔1CIR时间 园数比较 添加一个令牌,添加顺序为先 ▲图6单速率三色标记算法的令牌 酒加流程二 添加C桶再添加E桶,当令牌 桶添加满的时候,再产生的令 令牌定? 减去令牌桶中相应的 令牌数并让报文遇过 列(WFQ)等来缓存报文。 牌就会被丢弃 实际中比较常见的有两 3令牌桶实现 种实现方式:(1)周期性的添 罟弃者缓存报文 上面介绍了RFC中定义的令牌桶加,如图5所示,添加的时间间 技术原理以及其在IQs中的应用,隔就是令牌桶的容量与添加▲图7单速率三色标记算法的报文处理流程 58 中兴通讯技术 李晓利等:QoS技术中令牌桶算法实现方式比较 ZTE COMMUNICATIONS 研究论文 由图10可知,对方式一来说,由 报文到达 察看楣中令牌数 于令牌桶总的容量只有1000kb,发 送完每条报文后桶中剩余令牌数都 为0。此时若有突发流量,则报文必然 令牌数是 被丢弃。而方式二令牌数可为负,当 否大于零? 丢弃报文 突发报文到达时即使令牌数不足仍 可通过欠债方式现将报文转发出去, 令牌数小于报 否」转发报又桶中牌数 后续再偿还债务 文长龊 减去报文长度 (3)大小包混合时:方式一可能 会造成大包始终得不到转发,而方式 二则不会。 转发报文桶中令牌数 减去报长度,变为负值 图8 如果发送一长度大于1000kh的 单速率三色标记算法 的报文处理流程二 报文,方式一中则始终会由于令牌不 足而丢弃报文,方式二则可以通过借 200kbs,报文长度为125kB(100kb)。第二条报文发送结束,累计欠债250kb。债方式现转发报文后偿还债务。 方式一:周期性添加令牌,只有这时若有报文到达,就不能继续欠 (4)数据流发送过程平缓程度:方 当令牌数足够时才转发报文。添加令债,而要注人新的令牌才能继续转式二数据处理的时阃较长,所以趋势 牌的周期为8s,而转发一条报文的时发。直到第15s第三条报文发送完毕明显比方式一平缓。 间为5s。 由于一次添加令牌不够还清所欠令 方式二:一次性添加令牌,当令牌,所以遣成了短暂的丢包现象,而3.2双速率三色算法的实现 牌数不足时采用借债机制。转发一条在前17内丢包率仅为117≈5.9%。 报文的时间是5s.但是添加令牌的时 (2)突发流量处理:方式二在突发3.21桶的构成 间是不一定的,每次添加令牌的数目流量处理方面优于方式一。 双速率三色算法的实现,目前业 为CIfx△t 图9至图是对这两种方式的令 牌桶中令牌数、报文转发速率和令牌 会牌中令牌数 1200 添加过程的比较。 1000 分析数据的处理流程得出以下 600 结论 1)数据包丢弃率:方式二的丢包 营200 令0 率远小于方式 200 方式一中,由于令牌添加周期与 图9 600 报文发送周期的不一致,导致第6s到 两种方式报文处理过 时间【s 第8s由于没有令牌不能转发报文。而 程中令牌桶中令牌数 的比较 上实现方式一实现方式三」 第8s到第16s虽然在不断添加令牌, 但令牌数不足以转发一个报文,所以 仍旧无法转发报文,那在这一段时间 按文转发速率比较 内到达的报文将被丢弃掉。在前16s 的时间内丢包率达到了1016 200 量量看量量量量量 625%,由于添加令牌和发送报文的 至 时间都是固定的,所以整个发送过程 中的丢包率也为625%。 方式二中,第5s第一条报文发送 结束令牌被消耗光,但第6s又立即加 1234567891011213141516171819 图10D 时间(s 入了550kb令牌,虽不够转发一条报两种方式报文转发速 文,但可以采用借债机制,直到第10s 率的比较 ●一:实现方式一一■一:实现方式二 中兴通讯技术 59 研究论文 李晓利等:QoS技术中令牌桶算法实现方式比较 ZTE COMMUNICATIONS 等原因,成为目前业界比较常用流量 今牌添加过程比较 标记方式。但不同的实现方式决定了 其具有一定的性能差异,合理的采用 600 500 借债方式可以弥补其在丢包率、突发 40 300 流量处理性能、大小包混合转发性 200 能、数据转发平缓程度等性能方面的 病100 不足,但当存在较大速率的突发流量 0L◆ 1234567891011121141516171819 时,单速率三色标记算法的借债机制 时间{s 图11 将不能较好的改善性能问题,所以单 一:实现方式 实现方式二 两种方式添加令牌过 程的比较 速率三色标记算法不能完全取代双 速率三色表算法。在实际应用中,应 V表1单、双速率三色标记算法比较 针对不同的流量特征选择恰当的标 单速率三色标记算法 双速率三色标记鼻法 记方式。 杯的结构 单桶或双桶 双桶 令障乔加方式简单单强和双的采用定速幸加牌,复你两福今的速不同别为利,5参考文献: 报文处理程简单将报文长度与桶中令牌数进行比较,复杂将搬文速率先与两桶透加今牌速率比较 何宝宏伊P网络的服务质星讲座:第4浒P网络 转发否则丢拜 个者 文为红色 流量与拥塞控制授术[.中国数据递信,2003 56):.96-99 关注报文尺寸上的突发当报文长度过长CBS桶 12] Heinanen J, Guerin A. IETF RFC 2697: A 优点 中令不 向精令牌若西都不 关注速率上的突发当报文速率过大时 single rate three color marker[RI. Philadelphia 时,还可采用前甄所说的售使方式。 可向F桶中惜令牌。 A, USA: University of Pennsyivania, 1999 [3] Heinanen J, Guerin R. IETF RFC 2698: A two rate three color marker[R]. Philadelphia, PA 界的实现基本上完全依照RFC的规以只会被标记为绿色报文。 USA: University of Pennsylvan a, 1999 定,用两个令牌桶来实现,两个令牌 当发送突发报文时,若突发流量 4]李建宝,桑海令牌算法在PQoS中的应用 J].华南金电脑。2006,14(4:9-99 桶的容量不同,第一个是CBS,第二个大于PBs,则超出部分统计为红色报 15]QS技术白皮书EBoL httpf/www.huawei-3oom,com.cn/ 是PBs 文;当突发流量大于CBS,但小于PBS 时,则超过CBs部分标记为黄色报文; 收稠日期:2007-04-03 3.2.2令牌添加 当突发流量小于CBS时,全部标记为 双速率三色标记算法中两桶添绿色报文。 加令牌的速率不同,CBS桶添加令牌 在流量控制中,用户可针对不同 的速率是CIR,PBS桶添加令牌的速率颜色的报文设定不同行为,如;允许 则是PR。添加令牌时先添加CBS桶,通过、丢弃、或重新标记优先级等。 CBS桶填满后再添加PBs桶 3.3单速率三色算法与双速率三色 3.2.3报文处理流程 算法的比较 错器 当发送连续流量时,先看报文速 单、双速率三色标记算法的比较 率是否超过PIR:当报文速率大于PIR如表1所示。 单速率三色标记算法釆用单桶 李晓利,北京交通大学电子 时,超过PBS部分流量无法得到令牌 德息工程学院通信与德息系 被标记为红色报文;未超过PS而从或双桶结构,令牌添加方式和报文处 统专业在溪镇士生。主楚研 究方向为通恺德思国绍。 PBs桶中获取令牌的报文标记为黄色理流程比较简单;双速率三色记算法 报文;从CBS桶中获取令牌的报文被采用双桶结构,令牌添加方式和报文 标记为绿色报文。当报文速率小于处理流程相对复杂。前者关注报文尺 PIR,大于CIR时,报文不会得不到令上的突发,后者关注速率上的突发 究宇春,北京交通大学电子 牌,但会超过CBs部分报文将从PBS两者各有优点。 信息工程茡院副教授,士 生导师,主茭研究领域为网 桶中获取令牌,被标记为黄色报文; 络測星与建模、拓扑、路由、 其他报文将从CBs桶中取令牌,被标4结束语 P2F网络和P网络服务质量 等,已发表论文2余篇。 记为绿色报文;当报文速率小于CIR 相对双速率三色标记算法而言 时,报文所需令牌数不会超过CBs,所单速率三色标记算法由于实现简单 60 中兴递讯技术 旧 万万据 WANEANE DATA文献链接 lISTIC

...展开详情
试读 6P QoS技术中令牌桶算法实现方式比较
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 签到新秀

  • 分享精英

关注 私信
上传资源赚钱or赚积分
最新推荐
QoS技术中令牌桶算法实现方式比较 49积分/C币 立即下载
1/6
QoS技术中令牌桶算法实现方式比较第1页
QoS技术中令牌桶算法实现方式比较第2页

试读结束, 可继续阅读

49积分/C币 立即下载