那么,你是否很期待有一种机制可以在网络上通过监督进入网络的流量速率,以达到限制流量、提高网络资源使用效率的目的,从而保证有限的网络资源提供更好的网络服务? 流量评估
为了达到上述目的,我们需要对进入网络的流量进行监督,实现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> 在单速单桶模式中,系统按照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。
报文处理过程汇总见下表。 包序号 时刻 (ms) 包长 (bytes) 与上次添加令牌的间隔 本轮增加令牌 令牌增加后C桶令牌 报文处理后C桶剩余令牌 报文标记结果
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> 假设某时刻来了一个车队有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桶不变。
报文处理过程汇总见下表。 包序号 时刻 (ms) 包长 (bytes) 与上次添加令牌的间隔 本轮增加令牌 令牌增加后各桶令牌 报文处理后各桶剩余令牌 报文标记结果 C桶 E桶 C桶 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(存在服务卡足够而通行卡不够的情况)。