《漏桶算法及其应用.doc》由会员分享，可在线阅读，更多相关《漏桶算法及其应用.doc（6页珍藏版）》请在三一文库上搜索。
1、漏桶算法及其应用周秋平在Quidway NE08和NE16路由器的工程开局过程中，经常会遇到路由器与ATM交换机的对接要求，由于ATM技术与TCP/IP协议之间存在着很大的差异，而且ATM本身也是一套非常复杂的体系，这对开局工作带来了一些困难。为此，本文简单地介绍一些与NE路由器ATM模块及与ATM交换机对接的相关概念，并重点介绍ATM论坛推荐并在实际中大量应用的ATM流量控制方法-漏桶算法。一、ATM网络业务ATM论坛根据网络应用定义了五种业务类型：CBR、rt-VBR、nrt-VBR、UBR及ABR。CBR：Constant Bit Rate 固定比特率对用户端即业务申请方来说，CBR业务
2、对业务数据流的时延抖动非常敏感，要求网络以恒定的速率发送数据。对网络端即业务提供方来说，必须在连接周期内为CBR业务分配固定的静态带宽，并提供最高优先级。CBR最大的特点在于业务数据流的稳定性，用户端以固定的周期发送数据，业务突发性很小，电路仿真、语音等业务是这一方式的典型应用例子。用户在向网络侧申请CBR业务时，必须提供峰值信元速率PCR参数。 rt-VBR：Real-Time Variable Bit Rate 实时可变比特率顾名思义，rt-VBR业务对数据流的时延和时延抖动非常敏感，语音和交互式视频是这一业务的典型应用，这一点与CBR有些类似。但是rt-VBR业务允许一定的突发性，不同时
3、段源端数据速率可以不同。此外，在网络端即业务提供方并不是为rt-VBR业务分配静态带宽，而是采用统计多路复用方式工作。用户在向网络侧申请rt-VBR业务时，必须提供峰值信元速率PCR、平均信元速率SCR和最大突发大小MBS等参数。nrt-VBR：Non-Real-Time Variable Bit Rate 非实时可变比特率与rt-VBR业务相比，nrt-VBR对业务的实时性要求不高，业务数据在网络端处理的优先级也比rt-VBR低，其它特点如突发性、统计复用和业务参数等与rt-VBR基本相同。ABR：Available Bit Rate 可用比特率ABR业务适于实时性要求不高，突发性较大的应用
4、场合。在ATM的五种业务中，唯有ABR业务的网络侧向用户侧提供反馈机制。当网络发生拥塞时，网络端通过资源管理（RM）信元向用户发送信息，要求降低发送速率。用户在向网络侧申请ABR业务时，必须提供峰值信元速率PCR和最小信元速率MCR参数，而且网络侧必须保证ABR业务数据的可用带宽不小于MCR。UBR：Unspecified Bit Rate 未指定比特率与ABR业务相似，UBR业务也适于实时性要求不高和突发性较大的应用场合。但是，UBR业务用户只要求网络侧尽最大努力为自己服务，申请业务时不附带任何服务质量参数。网络侧也不对UBR业务提供任何服务质量保证，当网络发生拥塞时，UBR信元首先被丢弃，
5、FTP、E-Mail等业务是UBR的典型应用。 二、ATM流量控制-漏桶算法从前面的概念介绍当中我们知道，用户在申请某项业务之前，首先必须向网络提供PCR、SCR及MBS等参数。这些参数的具体含义是什么？网络侧即ATM交换机如何利用这些参数进行流量控制？这些问题正是本文要介绍的ATM流量控制-漏桶算法的具体内容。首先需要指出，本文所讨论的流量控制和漏桶算法属于“Traffic Control”范畴，更准确地说，漏桶算法是用户参数控制UPC/网络参数控制NPC的内容，UPC/NPC的目的是根据事先约定好的流量参数对虚连接上收到的信元实施监控，避免可能的网络拥塞。如果网络发生拥塞，ATM交换机就必
6、须实施拥塞控制（Congestion Control）操作，这已不属于本文讨论的范围。漏桶算法的正式名称为一般信元速率算法GCRA（Generic Cell Rate Algorithm），其基本思想非常简单。假设用户设备和ATM交换机直接相连，当用户端发送信元的速率越大，则在相同的时间段内ATM交换机收到的信元也就越多。当用户发送数据的速率太大，造成交换机在短时间内收到的信元过多，超出双方事先达成的协议或超出交换机的承受能力，并导致网络拥塞，这时交换机就必须采取一些“惩罚”性的措施，要么将违约的信元直接丢弃，要么将其打上标记（将信元头的CLP位置1），当网络发生拥塞时优先丢弃这些被打上标记的
7、信元。从上述描述可以将漏桶算法用一句话概括，就是用户发送的信元到达ATM交换机的时刻，可以比该信元预期到达的时刻晚，也可以早一点，但是不能太早！关键问题在于：什么叫预期到达的时刻？什么是太早？如何定量。假设某用户向网络侧申请了一项业务，所申请的最大网络带宽为PCR（单位为信元/秒）。记T=1/PCR，则T值意味着用户每隔不小于T的时间，向网络发送一个信元。如图1所示，记初始时刻（交换机在该时刻收到用户信元1）为t1，图1（a）表示大多数的正常情况，后续信元2在信元1到达T时间后准时到达，而且信元3预期在t2+T（t1+2T）时刻到达。 图1（b）表示信元2迟到，信元2原预期在t1+T时刻到达，
8、但它实际到达交换机的时刻t2t1+T。需要注意的是，信元2迟到，信元3预期到达交换机的时刻为t2+T，而不是t1+2T。 图1（c）显示的情况为用户端发送的速率大于所约定的PCR值，导致信元2到达交换机的时刻早于预期时刻t1+T。虽然此时t2t1+T，但是t1+T-t2L，交换机认为用户所发送的信元2违约。图1 GCRA的基本思想在图1（c）所显示的例子中，如果用户端发送信元的速率大于PCR，或者说产生信元突发现象，造成信元2到达交换机的时刻比预期稍早，但由于t1+T-t2=L，系统还是认为信元2没有违约。如果这种情况只是一个信元突发，还算比较幸运；如果连续发生多个这样的信元突发情况，那么结果
9、就不一定再有那么幸运了，如图2所示。图2 连续突发信元在图2中，用户端连续以大于PCR的速率产生了4个突发信元。第一个信元到达交换机的时刻比预期的t0+T早了时间e，其中e=L/3。由于信元1提前的时间eL，结果造成信元4在漏桶中溢出，导致信元违约。从上述分析可以看出为什么漏桶的容量定为T+L。前面说过，漏桶算法的关键在于信元到达的时间不能太早，否则会被认为违约。现在可以看出，“太早”的概念是由时间容限L来衡量的。从漏桶的观点来看，信元到得太早，漏桶中还没有流尽的信元数L，导致该信元在漏桶中溢出，被认为违约。另外，上述漏桶分析中，我们说漏桶中装的是信元，漏桶中不停流出的也是信元。其实，更准确地
10、说，漏桶中所装的是“时间”，这一点不难理解。三、漏桶算法的实际应用为了方便讨论，本文以NE路由器与华为Radium 8750ATM交换机对接为例，其它厂商的ATM交换机在实现上可能会有一些区别，但其GCRA流控算法差别不会太大。当NE路由器与Radium 8750之间采用nrt-VBR互通时，需要设置PVC的PCR、SCR和MBS三个流量参数。在Radium 8750ATM交换机侧，还必须设定CDVT 参数（信元时延变化容限，单位是时间）。Radium 8750对于nrt-VBR和rt-VBR两种业务采用两级漏桶流控方式，每个信元依次到两个漏桶过滤。第一级漏桶控制PCR，第二级漏桶控制SCR。
11、根据前面所讨论的结果， GCRA算法的漏桶取决于T和L两项参数，在Radium 8750交换机侧，第一级漏桶的T=1/PCR，L=CDVT；第二级漏桶的T=1/SCR，L=(MBS-1)(1/SCR+1/PCR)。对于违约的信元，Radium 8750可以根据需求选择丢弃或打标记策略。四、工程指导从前面的讨论我们可以得出以下两个结论：1、从实施漏桶算法对到达的信元流进行监控的交换机角度看，L值越大，则漏桶的容量越大，信元越不容易违约，漏桶可以容纳更多的突发信元。这个结论比较容易理解，由于L值是一个时间容限，其值越大，意味着信元可以比预期时刻提前更早时间到达，对信元的监控也更宽松。在实际应用中，
12、L值一般远比T值大很多。例如，Radium 8750ATM交换机中，所有控制PCR的CDVT默认值是1024，代表102.4微妙。在以后的版本中，CDVT的默认值还将增大为10240。如果PCR为155Mbps，则T值不到3微妙。L值比T值大，对于刚接触GCRA算法的人来说也许觉得难以理解，因为这意味着图1中信元2比信元1提前到达，这显然不合理。其实之所以将时间容限L值定得比较大，主要是因为在实际中信元的突发一般都是连续多个一起产生，这样便会有连续多个信元比预期时刻提前到达，按图3所示，这将造成漏桶中信元数的累积越来越多，如果L值较小，则信元很快就产生溢出。另外一方面，由于ATM是一种面向连接
13、的技术，不保证信元不被丢弃，但是它严格地保证同一条VC上的信元按序交付。因此，只要系统运行正常，实际上不可能出现后发送的信元先到达的情况。退一步说，即使信元顺序发生错误，GCRA算法流程将错就错，将先到达的信元认为是对方先发送的，也不会影响算法的执行。因此，L比T大，并不是说允许后发送的信元先到达，而是为了允许连续多个的信元突发。2、在实施漏桶算法的交换机中，PCR或SCR参数值越大，即T值越小，则信元越不容易违约。从图3可以看出，T值其实也是漏桶容量的一部分。从表面上看，好象T值越小，则能容纳的信元数越少，信元也越容易违约。但在介绍漏桶算法时，我们曾提到漏桶算法的两个关键点之一就是信元的预期
14、到达时刻。显然，信元的预期到达时刻与T值有关。我们知道，信元不能到达得太早，但什么叫太早，怎么衡量，其实就是将信元的实际到达时刻和预期时刻相比较，看有没有超过容限值L。因此可以看出，L值和T值之间有着密切的关系，虽然两者意义不同，好象两者是构成漏桶容量的两个部分，但实际上前面所说的漏桶容量等于T+L只是一个形象的说法，严格说来，漏桶的真正容量并不是两者简单的相加关系。模糊一点来看，T值越小，则信元预期到达的时刻越早，那么漏桶算法的“太早”因素就越难以满足。很显然，上述两条结论对于工程开局具有很大的指导意义。在实际网络流量中，NE路由器ATM接口的信元突发量有时可能比较大，从而可能在ATM交换机
15、中产生大量信元违约，造成丢包现象。对于这种情况，可通过增大L值和减小T值的方法来放宽对信元的监管。在ATM交换机侧要么提高PCR值，要么增大CDVT，或者增大SCR、MBS值。此外，还有一个重要因素就是设置ATM交换机对违约信元所采取的策略是直接丢弃还是打标记。显然如果ATM交换机采用打标记的方式，则即使NE路由器信元突发度比较高，也不会对业务造成太大影响。笔者曾经做过这样的实验，两台NE路由器，中间经过一台Radium 8750交换机跑IPOA协议。将NE路由器配置为UBR，Radium 8750配置为VBR，并将PCR值设定得很小，如果对违约信元采用打标记的策略，则即使NE侧通过多个窗口连续PING对方大数据包（8100字节），也没有发生一起丢包现象，同时在Radium 8750侧观察到大量的违约信元。而如果在Radium 8750侧采用丢弃策略时，则几乎连一个数据包都PING不通。