2.3.3、DiffServ模型令牌桶算法

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法，依据测量结果对报文进行标记，以区分丢弃优先级。原理是基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。

令牌桶算法在能够限制数据的平均传输速率外，还允许某种程度的突发传输。令牌算法是以固定速度往一个桶内增加令牌，当桶内令牌满了后，就停止增加令牌。上游请求时，先从桶里拿一个令牌，后端只服务有令牌的请求，所以后端处理速度不一定是匀速的。当有突发请求过来时，如果令牌桶是满的，则会瞬间消耗桶中存量的令牌。如果令牌还不够，那么再等待发放令牌（固定速度），这样就导致处理请求的速度超过发放令牌的速度。

(1)、无突发令牌桶算法(单速单桶)
令牌桶可以看作是一个存放令牌的容器，预先设定一定的容量。单速单桶是设想在不出现超承诺速率的流量，通过一个令牌桶流量测量的方法。我们将令牌桶预先设定一定的容量。系统按设定的速度向桶中放置令牌，当桶中令牌满时，多余的令牌溢出。

令牌桶算法的2个主要参数：

CIR承诺信息速率：以承诺的每秒字节数据来衡量，单位：Kbps。
CBS承诺突发尺寸：以字节数衡量，值>0，至少应该大于等于最大分组长度，单位：bit。CBS 越大，表示所允许的突发量越大。

在这里插入图片描述
当数据流到达设备时首先会根据数据的大小从令牌桶中取出与数据大小相当的令牌数量用来传输数据（RFC 标准中定义的大小以 b/s 为单位）。也就是说要使数据被传输必须保证令牌桶里有足够多的令牌。

以CIR速率放入令牌，直到令牌数量达到CBS时，后续令牌被丢弃。
在这里插入图片描述
令牌桶的尺寸为CBS，用Tc表示桶中的令牌数量，Tc初始值等于CBS。如果某一时刻一个大小为N的报文到达，在对其进行评估时，当令牌数目足够转发报文，即Tc>N，则报文被标记为“CIR承诺信息速率内”；当令牌数目不够转发报文，即Tc<N，则报文被标记为“超出CIR承诺信息速率”。

举例理解，某大型景区限制进入人的流量，每一小时发放1000张票，那就意味得到票(令牌)的人可以进入景区，每一小时有1000人能进入出，在1小时内购票的人没有超过1000人，可以轻松的购到门票，当1小时内购票的人超过1000人后，超过1000的人只能等着下一个小时而不能进入。这样就控制住人流量，不会使景区在各个景点人满造成事故。

(2)、带突发的双令牌桶算法
IETF建议了两种带突发的双令牌桶算法——单速率三色标记（single rate three color marker，srTCM，RFC2697 定义，或称为单速双桶算法）算法，主要关注报文尺寸的突发；双速率三色标记（two rate three color marker，trTCM，RFC2698 定义，或称为双速双桶算法）算法，主要关注速率的突发。

两种算法的评估结果都是为报文打上红、黄、绿三种颜色的标记，所以称为“三色标记”。 QoS 会根据报文的颜色，设置报文的丢弃优先级，两种算法都可工作于色盲模式和非色盲模式。

srTCM在原来的基础上增加一个盒子E（改进后的系统对应单速双桶模式，盒子E对应单速双桶中的E桶）。

srTCM指定的三个参数：

CIR承诺信息速率：以承诺的每秒字节数据来衡量，单位：Kbps。
CBS承诺突发尺寸：单位为 bit，表示C桶的容量，即C桶瞬间能够通过的承诺突发流量。用来定义在部分流量速率超过CIR之前的最大突发流量尺寸，承诺突发尺寸必须不小于报文的最大长度；
EBS超额突发尺寸，单位为 bit，表示E桶的容量，即P桶瞬间能够通过的峰值突发流量, 用来定义每次突发所允许的最大的流量尺寸；

如何理解增加了一个令牌桶，前面的景区一小时1000张票在运行中出现一个问题，在一天中各时间段时间里，游客数量不等，在清早10点到下午2时后时间段里，游客人数最多，按原来的做法会成大量的游客放弃游玩，这时景区想到一个办法，在安全的条件下适当增加一部分游客，在原来票箱的基础上再增加一个的票箱，原票箱称为C箱、增加的一个称为E箱。当C箱的票为一小时内安全人数的1000张票出完后，使用E箱的票，E箱票数最多能超出人数1200张票。

单速率三色标记

在单速双桶模式中，系统按照CIR速率向桶中投放令牌。初始状态下，C桶和E桶都是满的。换成报文(报文大小为B)就是出现三种情形：

如果B ≤ Tc，报文被标记为绿色(承诺突发内)，且Tc减少B，Tc=Tc-B。
如果Tc < B ≤ Te，报文被标记为黄色(超额突发内)，且Te减少B，Tc不减少，Te=Te-B。
如果B > Te，报文被标记为红色，且Tc和Te都不减少。

在这里插入图片描述

当报文到来后，直接与桶中的令牌数相比较，如果有足够的令牌就转发（通常用一个令牌关联一个比特的转发权限），如果没有足够的令牌则丢弃或缓存。

如何理解，就是B相当于游客人数，当游客人数≤C箱内票数时，就从C箱内取出门票，卖一张少张。当游客人数>安全人数1000<最多能超出人数1200时，就卖E箱的票，卖完了，就不能放人进去了，这里减少的票是E箱的票，C箱的票没有动。如果来的人数超过了1200安全人数，那就不能卖了，等下一个小时再卖票。

案例：
假设第1个到达的报文是1500 bytes时，检查C桶发现令牌数大于数据包的长度，所以数据包被标为绿色，C桶减少1500 bytes，还剩500 bytes。

假设1ms之后到达第2个报文1500 bytes，先填充令牌，新增令牌=CIR时间间隔=1Mbps1ms=1000bit=125bytes，加上C桶原来剩余的令牌500bytes，此时C桶共有625bytes，令牌不够，报文标记为红色。

假设又过1ms后到达第3个报文1000 bytes，但C桶只有625 bytes，小于报文长度，因此新增令牌CIR*1ms=1000bit=125bytes，此时C桶共有750 bytes，依然不够，因此报文被标记为红色。

假设又过20ms后到达第4个报文1500 bytes，但C桶只有750 bytes，小于报文长度，因此C桶新增令牌CIR*20ms=20000bit=2500bytes，C桶此时令牌数3250 bytes，而CBS=2000bytes，因此溢出1250bytes令牌被丢弃，此时C桶大于报文长度，报文标记为绿色，C桶减少1500bytes，剩500bytes。
在这里插入图片描述

trTCM双速双桶采用RFC2698定义的双速三色标记器trTCM（A Two Rate Three Color Marker）算法对流量进行测评，根据评估结果为报文打颜色标记，即绿色、黄色和红色，关注速率上的突发。
4种流量参数：

CIR(Committed Information Rate)承诺信息速率：以表示向C桶中投放令牌的速率，即C桶允许传输或转发报文的平均速率；
PIR(Peak information rate)峰值信息速率：峰值信息速率，单位是 bit/s，表示向P桶中投放令牌的速率，即P桶允许传输或转发报文的峰值速率，PIR大于CIR；
CBS(Committed Burst Size)承诺突发尺寸：单位为 bit，表示C桶的容量，即C桶瞬间能够通过的承诺突发流量。用来定义在部分流量速率超过CIR之前的最大突发流量尺寸，承诺突发尺寸必须不小于报文的最大长度；
PBS(Peak Burst Size)超额突发尺寸，单位为 bit，表示P桶的容量，即P桶瞬间能够通过的峰值突发流量, 用来定义每次突发所允许的最大的流量尺寸。

trTCM
前面景区门票的采用两个票箱来解决人数上控制的问题，现在问题又来了，大家都集中在一个窗口买票，排队时间太长，游客们报怨。于是又改进方法，先网上购票，然后凭票领取通行证，解决速度问题。P桶是网上的售出的门票，C桶是通行证的票箱。PIR是网上售票速度必大于CIR领取通行证的速度。

采用以下办法就会出现几种情况：
①、网上要购票人数远多于网上售出门票的数量，这时暂不出票，等下一小时，这段时间内网上门票和景区通行证都没有减少；

②、当网上购票人数少于网上门票的数量时，开始网上售票，这时又分两种情况：

有门票的游客数量多于通行证数量时，这时如果再领取通行证会拖慢进入景区的时间，为了方便就让游客排队直接进入景区。这时减少的只是网上门票，而通行证没有减少；
有门票的游客数量少于通行证数量时，这种是景区的正常情况，这时游客用门票换取通行证进入，门票减少了通行证也减少了。

换成报文就是初始状态时C桶和P桶都是满的。

往C桶和P桶分别以CIR和PIR的速率填充令牌。因这两个令牌桶是相互独立的，当其中一个桶被填满时，这个桶新产生的令牌将会被丢弃，而另一个桶则不受影响，继续填充令牌。

在对到达报文（假设数据包大小为B）进行评估时，遵循以下规则：

如果报文长度超过P桶中的令牌数Tp，则报文被标记为红色，且Tc和Tp保持不变；
如果报文长度不超过P桶中的令牌数 Tp 但超过C桶中的令牌数 Tc，则报文被标记为黄色，且 Tp=Tp-B；
如果报文长度不超过C桶中的令牌数Tc，报文被标记为绿色，且 Tp=Tp-B， Tc=Tc-B。

(3)、三种令牌桶的使用场景
单速单桶的逻辑图
在这里插入图片描述

只使用了一个令牌桶，CIR承诺信息速率，CBS表示C桶瞬间能够通过的承诺突发流量。以CIR速率向C桶投放令牌，C桶满时令牌溢出。不允许流量突发。报文的处理以C桶中是否有足够令牌为依据。报文颜色：绿色或红色。

单速双桶的逻辑图
在这里插入图片描述
C桶满时令牌投放到E桶。C桶和E桶都不满时，只向C桶投放令牌。允许报文尺寸的突发。先使用C桶中的令牌，C桶中令牌数量不够时，使用E桶中的令牌。双桶可以有效的转发突发的流量。双桶单速率只是有效的解决了一次单位时间内的突发流量，如果出现每时每刻都是突发流量，会被丢弃。

双速双桶的逻辑图
在这里插入图片描述

以CIR速率向C桶投放令牌，以PIR速率向P桶中投放令牌。两个桶相对独立。桶中令牌满时令牌溢出。允许报文速率的突发。C桶和P桶中的令牌足够时，两个桶中的令牌都使用。C桶中令牌不够时，只使用P桶中的令牌。当某个流量以高于CIR速率进入，这时为了防止此流量被丢掉，采用双桶双速率的模式保证此连续的突发流量通过。

(4)、令牌桶原理应用之接口限速
在这里插入图片描述
单速单桶：设备入方向基于接口，实现接口限速；设备出方向基于接口，实现接口限速。
双速双桶：设备入方向基于流，实现流量监管；设备出方向基于队列，实现流量整形。

2.3.4、基于DiffServ模型的QoS组成

基于 DiffServ 服务模型的 QoS 业务可以分为以下几大类：

流分类和标记（Traffic classification and marking）：要实现差分服务，需要首先将数据包分为不同的类别或者设置为不同的优先级。将数据包分为不同的类别，称为流分类，流分类并不修改原来的数据包。将数据包设置为不同的优先级称为标记，而标记会修改原来的数据包。
流量监管和整形（Traffic Policing and Shaping）：是指将业务流量限制在特定的带宽，当业务流量超过额定带宽时，超过的流量将被丢弃或缓存。其中，将超过的流量丢弃的技术称为流量监管，将超过的流量缓存的技术称为流量整形。
拥塞管理和避免（Congestion Management and Avoidance）：拥塞管理在网络发生拥塞时，将报文放入队列中缓存，并采取某种调度算法安排报文的转发次序。而拥塞避免可以监督网络资源的使用情况，当发现拥塞有加剧的趋势时采取主动丢弃报文的策略，通过调整流量来解除网络的过载。
端口镜像和流镜像（Port Mirror and Traffic Mirror）：镜像是将指定端口的指定报文复制一份到镜像目的端口，镜像目的端口会与数据监测设备相连，用户利用这些数据监测设备来分析复制到目的端口的报文，进行网络监控和故障排除。

流分类和标记是实现差分服务的前提和基础；流量监管、流量整形、拥塞管理和拥塞避免从不同方面对网络流量及其分配的资源实施控制，是提供差分服务的具体体现。

QoS 几大类组成在网络设备上有着一定的处理顺序，一般情况下图的顺序处理：
在这里插入图片描述
原则上在业务接入端口入方向实施流分类/标记、流量监管；业务接入端口出方向实施流量整形（如果业务接入端口接入多个不同等级的业务，则业务接入端口出方向还要实施队列调度和丢包策略）；网络侧端口出方向实施拥塞管理和拥塞避免。