概述
春暖花开的时候，大家都开着汽车外出旅游欣赏美丽的风景，却被堵在高速公路上，你是否为此感到痛苦？但如果有一种机制可以评估高速公路上的车流量、控制车流情况，确保进入高速公路的汽车都能在路上安全畅行，你是不是会觉得很开心？
与此相似，网络发生拥塞的时候，也是一件非常痛苦的事情，如图1和图2所示。
图1 网络拥塞场景1
图2 网络拥塞场景2
如果不限制用户发送的业务流量大小，大量不断突发的业务数据会使网络更加拥挤，严重时会出现网络拥塞，造成业务出现异常，同时也浪费网络资源，如图3和图4所示。
图3 网络拥塞造成资源浪费
图4 网络拥塞引起业务异常
那么，你是否很期待有一种机制可以在网络上通过监督进入网络的流量速率，以达到限制流量、提高网络资源使用效率的目的，从而保证有限的网络资源提供更好的网络服务？
流量评估
为了达到上述目的，我们需要对进入网络的流量进行监督，实现CAR（Committed Access Rate）。
CAR：将进入网络的用户流量的速率限制在约定的范围之内，从而避免引起网络拥塞。
要实现CAR，就需要对流量进行评估，然后根据评估的结果对流量采取相应的动作：
l 如果流量没有超速，设备会为报文奖励绿牌（将报文染色为绿色）。报文可畅通无阻，即被转发。
l 如果流量稍微超速，设备会发出黄牌警告（将报文染色为黄色）。通常报文会被降级，即修改报文的内部优先级，然后进行尽力而为的转发。
l 如果流量超速太多，设备会发出红牌将报文罚下（将报文染色为红色）。报文被禁止通行，即丢弃。
然而，报文不像汽车那样可以通过测速仪之类的仪器进行测速。那么，如何对报文的速率进行评估呢？——答案在这里：令牌桶。
令牌桶可以看作是一个存放令牌的容器，预先设定一定的容量。系统按给定的速度向桶中放置令牌，当桶中令牌满时，多余的令牌溢出。令牌桶是一种流量测量方法。
不得不说的令牌桶
接着上面高速公路的例子，假设进入高速公路的车辆需要在入口处领取到通行卡才能进入高速公路。为了节约人力成本，入口处放置自动出卡机。按照国家高速公路交通安全法的规定，在高速公路上行驶的车辆，车速超过100km/h时，应与同车道前车保持100米以上距离。为了保持最小安全行车距离100米，按车速100km/h计算，需要间隔至少3.6秒才能放行一辆车，因此出卡机每隔3.6秒出一张通行卡。在自动出卡机下放置一个盒子，自动出卡机按照3.6秒的间隔向盒子中投放通行卡。每辆进入高速公路的车辆，从盒子中领取通行卡之后才可以进入高速公路。
令牌桶算法与此类似。简单来说，令牌桶可以看作是一个存放一定数量令牌的容器。系统按设定的速度向桶中放置令牌。当桶中令牌满时，多出的令牌溢出，桶中令牌不再增加。在使用令牌桶对流量规格进行评估时，是以令牌桶中的令牌数量是否足够满足报文的转发为依据的。每个需要被转发的报文，都要从令牌桶中领取一定数量的令牌（具体数量视报文大小而定），才可以被正常转发。如果桶中存在足够的令牌可以用来转发报文，称流量遵守或符合约定值，否则称为不符合或超标。
按照系统向令牌桶投放令牌的速率和令牌桶的数量划分，令牌桶算法有三种模式：
l 单速单桶
l 单速双桶
l 双速双桶
下面我们以色盲模式为例详细介绍这三种模式。
单速单桶
假设有一套自动出卡系统，包括一台自动出卡机和一个盒子C。自动出卡机以固定的速率（3.6秒出一张通行卡）向盒子中投放通行卡。这个固定的速率，就相当于是单速单桶模式中的CIR参数。
CIR（Committed Information Rate）：承诺信息速率，表示向C桶（单桶模式中只有一个令牌桶，称为C桶）中投放令牌的速率，即C桶允许传输或转发报文的平均速率。
如果平均每3.6秒来了不止1辆车，通行卡很快就领完了。这时自动出卡机上的红灯亮起，新到的车辆禁止进入高速公路。这就起到了限定作用，将放行车辆的速率限制在放卡速率范围内。
如果平均每3.6秒来了不到1辆车，盒子里就会有一些积累起来的通行卡。这些累积起来的通行卡可以应付车队（比如车友俱乐部的车队）要进入高速公路这样的情况。我们规定每辆车都要领取通行卡，都由领队的车领取。
假设某时刻来了一个车队共8辆车，但盒子里只有6张通行卡，领队车拿起通行卡一数，发现不够，那么这个车队不允许进入高速，通行卡放回盒子中。
盒子中的通行卡不停累积，总有盒子装满的时候。这个盒子的容积，就相当于单速单桶模式中的CBS参数。
CBS（Committed Burst Size）：承诺突发尺寸，表示C桶的容量，即C桶瞬间能够通过的承诺突发流量。相当于盛放通行卡的盒子里最多可以放多少张通行卡，也就是说，该自动出卡系统允许通过的车队中最多可以有多少辆车。
在单速单桶模式中，系统按照CIR速率向C桶中投放令牌。
l 如果可用令牌的总数量（Tc）小于CBS，则令牌数继续增加。
l 如果令牌桶已满，则令牌数不再增加。
对于到达的报文（报文大小为B），
l 如果B ≤ Tc，报文被标记为绿色，且Tc减少B。
l 如果B > Tc，报文被标记为红色，Tc不减少。
假设设备端口的CIR设置为1Mbit/s，CBS为2000bytes，初始状态时C桶满。
说明：为方便计算，此处1Mbit/s按1*106bit/s计算。
l 假设第1个到达的报文是1500bytes时，检查C桶发现令牌数大于数据包的长度，所以数据包被标为绿色，C桶减少令牌1500bytes，还剩500bytes。
l 假设1ms之后到达第2个报文1500bytes。在此间隔内，C桶新增令牌 = CIR * 1ms = 1000bit = 125bytes，加上C桶原来剩余的令牌500bytes，此时C桶共有625bytes。令牌数量不够，报文标记为红色。
l 假设又过1ms后到达第3个报文1000bytes。在此间隔内，C桶新增令牌125bytes，加上C桶原来剩余的令牌625bytes，此时C桶共有750bytes。令牌数量不够，因此报文被标记为红色。
l 假设又过20ms后到达第4个报文1500bytes。在此间隔内，C桶新增令牌 = CIR * 20ms = 20000bit = 2500bytes，加上C桶原来剩余的令牌750bytes，C桶此时令牌数为3250bytes。而CBS = 2000bytes，因此溢出1250bytes令牌被丢弃。此时C桶令牌数大于报文长度，报文标记为绿色，C桶减少令牌1500bytes，剩500bytes。
报文处理过程汇总见下表。
| 2000 | 2000 | – | |||||
| 1 | 0 | 1500 | 0 | 0 | 2000 | 500 | 绿色 |
| 2 | 1 | 1500 | 1 | 125 | 625 | 625 | 红色 |
| 3 | 2 | 1000 | 1 | 125 | 750 | 750 | 红色 |
| 4 | 22 | 1500 | 20 | 2500 | 2000 | 500 | 绿色 |
单速双桶
在单速单桶模式中说到，如果平均每3.6秒来了不到1辆车，盒子里就会有一些积累起来的通行卡。如果一直没有车辆过来，盒子中的通行卡不停地累积。盒子的容量是有限的，当盒子中装满通行卡之后，不断投放的通行卡就溢出盒子，会造成浪费。
为了避免这种浪费，我们改进了这个自动出卡系统，在原来的基础上增加一个盒子E（改进后的系统对应单速双桶模式，盒子E对应单速双桶中的E桶）。自动出卡机首先向C盒中投放通行卡。当C盒满了，自动出卡机就向E盒中投放通行卡。
为了保证通行卡有序领取，我们规定先领取C盒中的通行卡。如果C盒中的通行卡不够用，就把卡放回C盒，再从E盒中重新领取通行卡。C盒和E盒中的通行卡不能同时取用。
按照通行卡的取用，可以分为三种情况：
l 如果C盒中的通行卡够用，绿灯亮，车辆领取C盒中的通行卡后通行。
l 如果C盒中的通行卡不够用但E盒中的通行卡够用，黄灯亮，从C盒中领取的通行卡领取的通行卡要归还，车辆领取E盒中的通信卡后通行。
l 如果E盒中的通行卡也不够用，红灯亮，车辆禁止通行，从E盒中领取的通行卡领取通行卡要归还。
和单速单桶模式一样，对于车队，有几辆车，就领取几张通行卡。当然，E盒的容量也是有限的。E盒的容量就相当于单速双桶模式中的EBS。
EBS（Excess Burst Size）：超额突发尺寸，表示E桶的容量，即E桶瞬间能够通过的超出突发流量。
假设某时刻来了一个车队有8辆车，但C盒里只有5张通行卡，而E盒中有9张通行卡，那么黄灯亮起，这辆长车从E盒中领取8张通行卡。
在单速双桶模式中，系统按照CIR速率向桶中投放令牌。
l 如果C桶中可用令牌的总数量（Tc）小于CBS，则C桶中令牌数增加。
l 如果Tc等于CBS且E桶中的可用令牌总数量（Te）小于EBS，则C桶中令牌数不增加，E桶中令牌数增加。
l 如果C桶和E桶中的令牌都已满，则两个桶中的令牌数都不再增加。
对于到达的报文（报文大小为B），
l 如果B ≤ Tc，报文被标记为绿色，且Tc减少B。
l 如果Tc < B ≤ Te，报文被标记为黄色，且Te减少B，Tc不减少。
l 如果B > Te，报文被标记为红色，且Tc和Te都不减少。
假设设备端口的CIR设置为1Mbit/s，CBS为2000bytes，EBS为2000bytes，初始状态时C桶和E桶满。
说明：为方便计算，此处1Mbit/s按1*106bit/s计算。
l 假设第1个到达的报文是1500bytes时，检查C桶发现令牌数大于数据包的长度，所以数据包被标为绿色，C桶减少令牌1500bytes，还剩500bytes，E桶令牌数量保持不变。
l 假设1ms之后到达第2个报文1500bytes。在此间隔内，C桶新增令牌 = CIR * 1ms = 1000bit = 125bytes，加上C桶原来剩余的令牌500bytes，此时C桶共有625bytes，检查发现C桶内令牌数量不够。检查E桶发现有足够令牌，因此报文标记为黄色，E桶减少令牌1500bytes，剩余500bytes，C桶剩余625byte保持不变。
l 假设又过1ms后到达第3个报文1000bytes。在此间隔内，C桶新增令牌125bytes，加上C桶原来剩余的令牌625bytes，此时C桶共有750bytes，检查发现C桶内令牌数量不够。检查E桶发现令牌数量也不够，因此报文被标记为红色，C桶、E桶令牌数不变。
l 假设又过20ms后到达第4个报文1500bytes。在此间隔内，C桶新增令牌 = CIR * 20ms = 20000bit = 2500bytes，加上C桶原来剩余的令牌750bytes，C桶此时令牌数为3250bytes。而CBS = 2000bytes，因此溢出的1250bytes添加到E桶，此时E桶有1750bytes。由于C桶中令牌数大于报文长度，报文标记为绿色，C桶减少令牌1500bytes，剩余500bytes，E桶不变。
报文处理过程汇总见下表。
| 2000 | 2000 | 2000 | 2000 | – | |||||
| 1 | 0 | 1500 | 0 | 0 | 2000 | 2000 | 500 | 2000 | 绿色 |
| 2 | 1 | 1500 | 1 | 125 | 625 | 2000 | 625 | 500 | 黄色 |
| 3 | 2 | 1000 | 1 | 125 | 750 | 500 | 750 | 500 | 红色 |
| 4 | 22 | 1500 | 20 | 2500 | 2000 | 1750 | 500 | 1750 | 绿色 |
双速双桶
前面说到的自动出卡机，都只有一个口可以输出通行卡。而这里说到的高级自动出卡机，有两个口可以出卡，一个口输出的是通行卡，一个口输出的是服务卡。当然，这里也有两个盒子用于盛放卡，分别是盒C盒和P盒。自动出卡机上的两个口分别以各自固定的速率向两个盒子中投放卡。（这个高级自动出卡机系统对应双速双桶模式，C盒和P盒对应双速双桶模式中的C桶和P桶。）
领取卡的规则和前面单速的情况有所不同。我们规定：
l 先领取服务卡。如果服务卡不够，把卡放回P盒，红灯亮，车辆禁止通行。
l 如果服务卡足够但通行卡不够，黄灯亮，服务卡可以取走，通行卡放回C盒。
l 如果服务卡和通行卡都足够，绿灯亮，车辆可以通行，服务卡和通行卡都取走。
自动出卡机向P盒投放服务卡的速率和P盒的容量，就分别相当于双速双桶模式中的PIR和PBS。
PIR（Peak information rate）：峰值信息速率，表示向P桶中投放令牌的速率，即P桶允许传输或转发报文的峰值速率。PIR的值应大于CIR（存在服务卡足够而通行卡不够的情况）。
PBS（Peak Burst Size）：峰值突发尺寸，表示P桶的容量，即P桶瞬间能够通过的峰值突发流量。
按照国家高速公路交通安全法的规定，在高速公路上行驶的车辆，最高时速为120km/h。前面领取的通行卡，保证车辆的时速为100km/h。而服务卡的作用，则是允许车辆时速可以达到120km/h。自动出卡机向P盒投放服务卡的速率就是允许的最高车速，相当于PIR。
在双速双桶模式中，系统按照PIR速率向P桶中投放令牌，按照CIR速率向C桶中投放令牌。
l 如果P桶中可用令牌的总数量（Tp）小于PBS，则P桶中令牌数增加。
l 如果C桶中可用令牌的总数量（Tc）小于CBS，则C桶中令牌数增加。
对于到达的报文（报文大小为B），
l 如果Tp < B，报文被标记为红色，且Tc和Tp都不减少。
l 如果Tc < B ≤ Tp，报文被标记为黄色，且Tp减少B，Tc不减少。
l 如果B ≤ Tc，报文被标记为绿色，且Tp和Tc都减少B。
假设设备端口的CIR设置为1Mbit/s，PIR设置为2Mbit/s，CBS为2000 bytes，PBS为3000 bytes，初始状态时C桶和P桶满。
说明：为方便计算，此处1Mbit/s按1*106bit/s计算。
l 第1个到达的报文假设是1500bytes时，检查发现报文长度不超过P桶也不超过C桶，所以数据包被标为绿色，C桶和P桶都减少令牌1500bytes，C桶还剩500bytes，P桶还剩1500bytes。
l 假设1ms后到达第2个报文1800bytes。在此间隔内，P桶新增令牌 = PIR * 1ms = 2000bit = 250bytes，加上P桶原来剩余的令牌1500bytes，此时P桶共有1750bytes，小于报文长度。C桶新增令牌 = CIR * 1ms = 1000bit = 125bytes，加上C桶原来剩余的令牌500bytes，此时C桶共有625bytes。报文标记为红色，P桶、C桶令牌数不变。
l 假设又过1ms后到达第3个报文1000bytes。在此间隔内，P桶新增令牌250byte，加上P桶原来剩余的令牌1750byte，此时P桶共有令牌2000bytes，大于报文长度。再检查C桶，C桶新增令牌250bytes，加上C桶原来剩余的令牌625byte，此时C桶共有750bytes，仍然小于报文长度。因此报文被标记为黄色，P桶减少令牌1000bytes，剩余1000bytes，C桶令牌不变。
l 假设又过20ms之后到达报文1500bytes。在此间隔内，P桶新增令牌 = PIR * 20ms = 40000bit = 5000bytes，超过P桶容量PBS，因此P桶令牌数 = PBS = 3000bytes，溢出的令牌丢弃。这样P桶有2000bytes，大于报文长度。此时C桶增加令牌 = CIR * 20ms = 20000bit = 2500bytes，超过C桶容量CBS，因此C桶令牌数 = CBS = 2000byte，溢出的令牌丢弃。C桶此时令牌数2000 bytes，大于报文长度。报文被标记为绿色，P桶减少令牌1500bytes，剩余1500bytes；C桶减少令牌1500bytes，剩余500bytes。
报文处理过程汇总见下表。
| 2000 | 3000 | 2000 | 3000 | – | ||||||
| 1 | 0 | 1500 | 0 | 0 | 0 | 2000 | 3000 | 500 | 1500 | 绿色 |
| 2 | 1 | 1800 | 1 | 125 | 250 | 625 | 1750 | 625 | 1750 | 红色 |
| 3 | 2 | 1000 | 1 | 125 | 250 | 750 | 2000 | 750 | 1000 | 黄色 |
| 4 | 22 | 1500 | 20 | 2500 | 5000 | 2000 | 3000 | 500 | 1500 | 绿色 |
三种令牌桶模式的区别和应用场景
由前文描述可以看出，三种令牌桶模式之间既有区别也有演进关系，具体见下表。
单速单桶 | 单速双桶 | 双速双桶 | |
| 关键参数 | CIR和CBS | CIR、CBS和EBS | CIR、CBS、PIR和PBS |
| 令牌投放 | 以CIR速率向C桶投放令牌。C桶满时令牌溢出。 | C桶满时令牌投放到E桶。C桶和E桶都不满时，只向C桶投放令牌。 | 以CIR速率向C桶投放令牌，以PIR速率向P桶中投放令牌。两个桶相对独立。桶中令牌满时令牌溢出。 |
| 是否允许流量突发 | 不允许流量突发。报文的处理以C桶中是否有足够令牌为依据。 | 允许报文尺寸的突发。先使用C桶中的令牌，C桶中令牌数量不够时，使用E桶中的令牌。 | 允许报文速率的突发。C桶和P桶中的令牌足够时，两个桶中的令牌都使用。C桶中令牌不够时，只使用P桶中的令牌。 |
| 报文颜色标记结果 | 绿色或红色 | 绿色、黄色或红色 | 绿色、黄色或红色 |
| 演进关系 | 单速双桶模式中，如果EBS等于0，其效果和单速单桶是一样的。 双速双桶模式中，如果PIR等于CIR，其效果和单速单桶是一样的 |
基于上述三种令牌桶模式之间的区别，其功能和使用场景也有所不同，具体见下表。
令牌桶模式 | 功能 | 选用场景 |
| 单速单桶 | 限制带宽 | 优先级较低的业务（如企业外网HTTP流量），对于超过额度的流量直接丢弃保证其他业务，不考虑突发。 |
| 单速双桶 | 限制带宽，还可以容许一部分流量突发，并且可以区分突发业务和正常业务 | 较为重要的业务，容许有突发的业务（如企业邮件数据），对于突发流量有宽容。 |
| 双速双桶 | 限制带宽，可以进行流量带宽划分，可以区别带宽小于CIR还是在CIR ~PIR之间 | 重要业务，可以更好的监控流量的突发程度，对流量分析起到指导作用。 |
参数设置有讲究
在令牌桶算法中，CIR的值越大，即令牌产生的速率越大，报文可以获取的令牌就越多，流向网络的流量也就越大。因此，CIR的值是控制流入网络中流量多少的关键。CBS也是一个重要参数。CBS的值越大，C桶中可以积累令牌的数目也越多，允许通过的报文尺寸就越大。
由于设备进行的是逐包转发，CBS的值不应该小于当前网络上允许传输的报文的最大长度。
例如，在单速单桶模式下，假设要把流量限定在10Mbit/s，而CBS值太小（如设置成1000byte）。如果某个时间段内流量的报文，每个报文大小都大于1000byte，那么这些报文全都被丢弃。这段时间内，没有报文被转发，报文的转发速率为0，导致网络资源被浪费，业务也出现异常。
那是不是CBS的值越大就越好呢？显然不是。CBS值太大，会失去限速的意义。例如，假设要把流量限定在10Mbit/s，CBS设置成7200Mbyte。某个时刻，令牌桶中的令牌已满，如果接下来1小时内流量的报文，其报文长度不一，但共计7200Mbyte，这些报文都能获得令牌并被转发，那么这段时间内的报文速率为16Mbit/s（7200M * 8 / 3600）而不是10Mbit/s，即没有实现限速。
同理，对于双速双桶模式，PIR和PBS的值也应设置在合理范围内。
说明：目前华为以太网交换机只支持单速单桶和双速双桶模式。
简单来说，带宽参数的设置取决于实际业务的限速需要。原则上，令牌桶容量需要大于等于网络中可能出现的最大的报的长度和业务流量的正常突发量。对于华为的以太网交换机，我们有总结的经验性公式：
l 带宽 ≤ 100Mbit/s时，令牌桶容量（Bytes） = 带宽（kbit/s） * 1000（s）/8
l 带宽 > 100Mbit/s时，令牌桶容量（Bytes） = 100000（kbit/s） * 1000 （s）/8
另外，华为的以太网交换机，不同系列的单板支持的CAR粒度不同。在进行流量监管和限速时，
l 如果配置的CIR、PIR是最小粒度的整数倍，则按照配置的速率进行监管和限速。
l 如果配置的CIR、PIR不是最小粒度的整数倍，则按照最小粒度的整数倍进行流量监管和限速。
例如，设备上的监管和限速粒度为64kbit/s，如果CIR值 ≤ 64kbit/s，按照64kbit/s处理；如果128kbit/s < CIR值 ≤ 192kbit/s，按照192kbit/s处理。
令牌桶原理应用之接口限速
令牌桶原理可以应用到设备的入方向和出方向。根据令牌桶原理在不同方向的应用，可以实现不同的功能，见下图。
流量监管、流量整形、接口限速与令牌桶算法之间的关系，见下表。
应用方向 | 单速单桶 | 双速双桶 |
| 设备入方向 | 基于接口，实现接口限速 | 基于流，实现流量监管 |
| 设备出方向 | 基于接口，实现接口限速 | 基于队列，实现流量整形 |
流量监管是一种通过对流量规格进行监督，以限制流量及网络资源使用的流控策略。如果这种流控策略应用到设备接口的入方向，也可以实现入方向的接口限速。与基于接口实现的入方向的接口限速相比，这种方式引入了MQC（Modular QoS Command-Line Interface），因此应用更加灵活。
通常我们所说的限速是广义上的接口限速，包括基于接口和基于MQC实现的入方向的接口限速。