tkorays|言剑 Write code every day...

流量整形以及路由器漏桶、令牌桶算法

1. 背景

在很多网络应用中,网络数据流量是不均匀的,经常存在流量突发。持续较大对流量突发超出了路由器限制会对网络服务造成影响,因此很多情况下需要对这种突发作出限制。流量整形就是一种解决流量突发的方法。

流量整形(traffic shaping)是一种限制流出网络的数据速率和突发,使数据较为均匀发送的技术。流量整形可以有效地消除流量突发,减少网络拥塞。流量整性有两个常用算法:漏桶算法(leaky bucket algorithm)和令牌桶算法(token bucket algorithm)。下面,我们将介绍这两种算法,以及这两种算法的实际应用。

2. 漏桶算法和令牌桶算法

2.1 漏桶算法(leaky bucket algorithm)

我们可以想象这样一个桶,它的底部有一个洞,只要漏桶里面有水,该桶的水就会以恒定速率R流出(向网络中发包);如果漏桶中没有水,则出桶的速率为0。此外,如果桶内的水达到桶的容量B,此时任何进入桶的水则沿着桶壁流失。这些流失的水对应超出发送容量的报文,可能被丢弃(网络监管),而流量整形中将这些报文缓存起来,等到漏桶有余量是继续进入漏桶。

因此漏桶算法严格限制了流量的上限,在使用中存在一定局限性。

2.2 令牌桶算法(token bucket algorithm)

和漏桶类似,你可以想象这样的一个令牌桶:水龙头以速度R往桶里面灌水,桶的容量为B。为了发送一个数据包,需要从令牌桶中取出一个令牌,令牌总量为B;如果令牌桶是空的,则需要等待可用的令牌到达。和漏桶一样,令牌桶可以通过限制一个流的长期速率,但是允许短期内某种程度的突发传输,这是相对漏桶算法改进的地方。大量的突发将被平滑,以减少网络拥塞。

如上图所示,这里桶内装的是令牌而不能认为是要发送的报文,令牌释放后要以速度R入桶,入桶后才能被使用。应用产生的数据包需要拿到令牌后才能发送,否则只能进入发送队列等待令牌。当缓冲队列满时,只能将报文丢弃。而发送完的报文释放完令牌后,不能立即入桶,而是以速度R,这样可以避免过度的瞬时超发。

假设存在一个场景,某个应用突发产生1000Mbps的数据,并持续时间s以这个速度生成。那么这个时候可以认为是流量突发,明显是需要控制网路发送速率的。假设路由器可以在很短时间内接受峰值速率的数据,直到缓冲区填满,假设缓冲区为9600KB,远小于突发流量,缓冲区很快被占满导致包被丢弃。这里我们假设路由器最佳的工作速率为200Mbps,如果想要达到理想的工作状态,发送端的平均发送速率应该控制在200M以下。

为了避免流量突发导致的丢包,我们可以在发送端用一个令牌桶对其进行流量整形。假设数据流入速度R为200M,桶容量B为9600KB。应用产生了M=1000Mpbs的数据,最开始应用可以以1000Mpbs的速率全速发送一段时间,直至桶被填满;桶被填满后,我们需要将其发送速率削减到200Mpbs,直到突发数据被发出去。最终效果是突发量被分散到一段时间内。我们可以通过下面的共识计算允许的突发时间:

\[B + RS = MS\]

即:

\[S = B/(M-R)\]

因此只要知道了突发速率M、流出速率R、桶容量B,就可以算法最大允许的突发流量时间。

假设令牌桶的容量B=0,那么流量将被完全平滑,不允许任何突发。在使用过程中,我们可以串联两个令牌桶,第一个令牌桶允许突发,第二个令牌桶的容量B=0,通过这种方式可以达到限制峰值的目的。因为使用了令牌桶,遇到突发流量时,最开始会以最大速率M发送直至填充满令牌桶。但是人们通常希望降低峰值,并不想峰值如此高。使用这种串联方式,第一个桶的输出可以在第二个桶中继续整形,可以进一步限制发送速率。比如第一个桶开始以M=1000Mbps突发发送,桶填满后,开始以R=200Mpbs发送,第二个令牌桶B=0,R=500Mpbs,因此此时突发流量被限制到500Mpbs。因此第一个桶描述流量的平均速率,并允许突发,第二个桶限制了突发流量峰值。

2.3 缺点

引入了流量整形,势必会带来时延的增加,因此兼顾减少拥塞和减少时延是一个需要关注的挑战。

3. 单桶单速和双速双桶,srTCM和trTCM

上面介绍的是一个简单的令牌桶模型,在实际使用中,我们还常用到另外两种更高级的桶。上面的令牌桶我们称之为单桶单速,下面我们将介绍单速双桶和双速双桶,分别对应这RFC2697中的srTCM(single rate Three Color Marker)和RFC2698中的trTCM(two rate Three Color Marker)。这里我们将详细介绍这两种算法。

3.1 srTCM

srTCM即单速率三色标记法,对应单速双桶算法,该算法在RFC2697有详细介绍。该方法使用了两个令牌桶C和E,这里的单速率是指C桶和E桶拥有相同的令牌入桶速率。

srtCM定义了3个参数:

  • CIR,Commit Information Rate,承诺信息速率,对应着令牌入桶的速率。
  • CBS,Commit Burst Size,承诺突发尺寸,对应着令牌桶C的容量。
  • EBS,Excess Burst Size,超额突发尺寸,对应着令牌桶E的容量。

CIR表示IP报文的字节数(包括IP报文头部),CBS和EBS也是按照字节计算,必需满足其中一个值不为0,且需要大于等于MTU。根据这三个参数,将报文标记成3个颜色,即红色、黄色、绿色。如果当前报文大小不超过CBS,则包被标记成绿色;如果超出了CBS但是低于EBS,则被标记成黄色;否则被标记成红色。报文被标记成这三种颜色后,就可以根据不同的策略进行发送,举个例子:

红色报文超出CBS和EBS限制,被系统丢弃;黄色报文,系统尽力转发;绿色报文系统以极低丢包转发。

根据报文是否被预先染色,Meter(限速器)可以工作在两种模式,即色盲模式(Color-Blinde Mode)和非色盲模式(Color-Aware Mode)。色盲模式假定所有进入的包都是没有被标记颜色的,而非色盲模式中,所有进入的包都被标记了红黄绿三种颜色。下面将介绍如何给报文标记颜色:

假设t时刻,C桶和E桶的令牌数分别为tc(t)和te(t)。最开始令牌桶是满的,因此tc(0)=CBS,te(0)=EBS。tc和te每秒内更新CIR次:

  • if \(tc \leq CBS\), \(tc++\)
  • else if \(te \leq EBS\), \(te++\)
  • else do nothing

更新完tc和te后需要对报文B进行标记颜色,色盲模式中:

  • if \(tc(t) \geq B\),标记为绿色,且\(tc-=B\)至0
  • else if \(te(t) \geq B\),标记为黄色,且\(te-=B\)至0
  • else 标记为红色

非色盲模式中:

  • if 报文标记为绿色,且 \(tc(t) \geq B\),则标记为绿色,且\(tc-=B\)至0
  • else if 报文被标记为绿色或黄色,且\(te(t) \geq B\),则标记为黄色,且\(te-=B\)至0
  • else 标记为红色

3.2 trTCM

trTCM即双速率三色标记法,对应双速双桶算法,该算法在RFC2698有详细介绍,该方法使用了两个桶,分别被命名为C和P,这里的双速率是至C桶和P桶拥有不同的令牌入桶速率,即CIR和下面提到的PIR。

该算法相对srTCM引入了两个新的参数:

  • PIR,Peak Information Rate,峰值信息速率,表示向P桶投放令牌的速率,即P桶允许传输或转发报文的峰值速率。PIR总是大于CIR。
  • PBS,Peak Burst Size,峰值突发尺寸,表示P桶的容量,即P桶瞬间能够通过的峰值突发流量。

最终该算法使用了4个参数,PIR、PBS、CIR、CBS。PIR和CIR表示每秒的IP报文字节数(包括IP报文头部)。PBS和CBS也是按照字节计算,必需满足两个值均不为0,且需要大于等于MTU。

在trTCM中,一个报文如果大小超过PIR,则被标记为红色;否则根据是否超过CIR被标记成黄色或者绿色。trTCM也有两种模式,即色盲模式和非色盲模式。

其中色盲模式:

  • if \(tp(t) \leq B\),标记为红色
  • else if \(tc(t) \leq B\),标记为黄色,且\(tp-=B\)
  • else 标记为绿色,\(tc-=B, tp-=B\)

非色盲模式中:

  • if 报文标记为红色,且 \(tp(t) \leq B\),则标记为红色
  • else if 报文被标记为黄色,或者\(tc(t) \leq B\),则标记为黄色,且\(tp-=B\)
  • else 标记为绿色,\(tc-=B, tp-=B\)

3.3 总结

这两种方法都可以允许流量突发,但是:

  • srTCM方式的单速双桶中,先往C桶投放令牌,C桶满时才向E桶投放。优先使用C桶总令牌,令牌不够再使用E桶的。因此特点是允许报文尺寸突发
  • trTCM方式中,同时以速率CIR和PIR向C桶和P桶投放令牌,C桶和P桶都足够时,则都使用,C桶不够时使用P桶都,允许报文速率突发

由于着色模式的存在,可以区分重要业务和非重要业务,根据重要性进行转发。

4. 总结

从上面的介绍中可以看出,流量整形的优点和缺点,可以用在我们的应用中适当使用。特别是哪些网络流量冲击比较大的应用,比如音视频会议、高并发服务系统等,通过这种削峰填谷,在控制流量的同时允许少量突发,兼顾了业务的可靠性和低延迟性。


如果您觉得文章对您有用能够解决您的问题,欢迎您通过扫码进行打赏支持,谢谢!