LEDBAT是Bittorrent客户端上使用的一种拥塞控制机制。它的设计理念是:不给当前的网络制造麻烦;保证数据流的带宽公平性,不恶意竞争带宽。简直就是一只小绵羊啊!!
LEDBAT是一个已经商用的后台应用程序传输协议,当前MAC OS和iOS在内核TCP中集成了LEDBAT,用于应用市场的下载业务,苹果已将其开源。目前Linux、Android和iOS都默认使用TCP CUBIC,而iOS可以根据不同的应用选择不同的算法,比如后台的应用市场采用LEDBAT,前台程序仍然使用CUBIC。
LEDBAT有以下三个目标:一是在瓶颈链路没有其他流的情况下,能够占满带宽,充分利用网络。二是在没有其他数据流的时候,保证较低的排队时延;因CUBIC流的窗口增加,引入排队时延的情况下,尽量不要增加排队时延。三是当CUBIC竞争带宽的时候,LEDBAT主动出让带宽,降低窗口 (The LEDBAT considers itself to be junior to TCP)。
LEDBAT是一个基于窗口的、基于排队时延的算法,CUBIC是一个基于窗口的、基于丢包的算法。从测试结果和原理上来看,ledbat比CUBIC更适用于无线场景,时延更低。但是基于时延的算法竞争性特别弱(这就是为什么它只能用于后台程序)。如VEGAS, FAST TCP, COPA. 当然,COPA还增加了一种激进模式,主动检测到网络上有CUBIC之类的流量后,从友好模式进入激进模式。
LEDBAT采用单向时延(one way delay, owd)来衡量网络的拥塞状况,单向时延相比RTT的优势,就是不用考虑ack返回时经历的回路时延。这一点非常有意思,与我们即将发布的FillP2.0具有异曲同工之妙!不过,不同之处在于,FillP2.0在接收端计算单向时延,而LEDBAT在发送端计算。
单向时延的测量具有一个通用的难题,就是收发端时钟不同步。但是,凡是涉及两个单向时延的差值变量,都不需要进行时钟同步!!
例如,排队时延可以通过前后的两个owd的差值来表示,这样时钟同步的问题就不存在了。FillP2.0和LEDBAT都采用了这个原理。这里我们不展开FillP2.0的原理介绍,只介绍LEDBAT的基本原理:
LEDBAT的单向时延是这样计算的,接收端接收到数据,回复ack,ack中携带时间差,ack.delay=localtimestamp(接收端收到数据时的本地时间)-remotetimestamp(f发送端在发送时的时戳)。将数据包传输过程中的最小的ack.delay作为base_delay,排队时延queue_delay=current_delay-base_delay,这个差值,就解决了sender、receiver之间的时钟不同步问题。具体的接收端窗口变化如下:
current_delay = acknowledgement.delay
base_delay = min(base_delay, current_delay)
queuing_delay = current_delay - base_delay
off_target = TARGET - queuing_delay
cwnd += GAIN * off_target / cwnd
解释下,TARGET就是一个设定的参数值,GAIN为1/TARGET,在queue_delay较小时,第四个是窗口变化公式,保证窗口增长,快速逼近瓶颈链路带宽。GAIN的存在保证LEDBAT不比TCP的窗口了增长速度快。在最好的情况下(queue_delay=0),LEDBAT也是每个RTT,cwnd的大小增加1。LEDBA相比基于丢包的的TCP拥塞控制机制,对于网络的拥塞感知要早。在queue_delay=2*TARGET时,每经一个RTT,cwnd减少1。就是说在队列时延增加的情况下,但是还未到达路由器的队列丢包阈值,TCP还处在拥塞避免阶段,tcp每个RTT,窗口增1,LEDBAT窗口减1。LEDBAT向TCP出让带宽。
LEDBAT论文:https://www.kth.se/social/files/5527dbf2f276543890e0c409/LEDBAT.pdf
LEDBADT的实现非常简单,可以作为module加载到linux系统里,源码地址:https://github.com/silviov/TCP-LEDBAT
LEDBAT是一个已经商用的后台应用程序传输协议,当前MAC OS和iOS在内核TCP中集成了LEDBAT,用于应用市场的下载业务,苹果已将其开源。目前Linux、Android和iOS都默认使用TCP CUBIC,而iOS可以根据不同的应用选择不同的算法,比如后台的应用市场采用LEDBAT,前台程序仍然使用CUBIC。
LEDBAT有以下三个目标:一是在瓶颈链路没有其他流的情况下,能够占满带宽,充分利用网络。二是在没有其他数据流的时候,保证较低的排队时延;因CUBIC流的窗口增加,引入排队时延的情况下,尽量不要增加排队时延。三是当CUBIC竞争带宽的时候,LEDBAT主动出让带宽,降低窗口 (The LEDBAT considers itself to be junior to TCP)。
LEDBAT是一个基于窗口的、基于排队时延的算法,CUBIC是一个基于窗口的、基于丢包的算法。从测试结果和原理上来看,ledbat比CUBIC更适用于无线场景,时延更低。但是基于时延的算法竞争性特别弱(这就是为什么它只能用于后台程序)。如VEGAS, FAST TCP, COPA. 当然,COPA还增加了一种激进模式,主动检测到网络上有CUBIC之类的流量后,从友好模式进入激进模式。
LEDBAT采用单向时延(one way delay, owd)来衡量网络的拥塞状况,单向时延相比RTT的优势,就是不用考虑ack返回时经历的回路时延。这一点非常有意思,与我们即将发布的FillP2.0具有异曲同工之妙!不过,不同之处在于,FillP2.0在接收端计算单向时延,而LEDBAT在发送端计算。
单向时延的测量具有一个通用的难题,就是收发端时钟不同步。但是,凡是涉及两个单向时延的差值变量,都不需要进行时钟同步!!
例如,排队时延可以通过前后的两个owd的差值来表示,这样时钟同步的问题就不存在了。FillP2.0和LEDBAT都采用了这个原理。这里我们不展开FillP2.0的原理介绍,只介绍LEDBAT的基本原理:
LEDBAT的单向时延是这样计算的,接收端接收到数据,回复ack,ack中携带时间差,ack.delay=localtimestamp(接收端收到数据时的本地时间)-remotetimestamp(f发送端在发送时的时戳)。将数据包传输过程中的最小的ack.delay作为base_delay,排队时延queue_delay=current_delay-base_delay,这个差值,就解决了sender、receiver之间的时钟不同步问题。具体的接收端窗口变化如下:
current_delay = acknowledgement.delay
base_delay = min(base_delay, current_delay)
queuing_delay = current_delay - base_delay
off_target = TARGET - queuing_delay
cwnd += GAIN * off_target / cwnd
解释下,TARGET就是一个设定的参数值,GAIN为1/TARGET,在queue_delay较小时,第四个是窗口变化公式,保证窗口增长,快速逼近瓶颈链路带宽。GAIN的存在保证LEDBAT不比TCP的窗口了增长速度快。在最好的情况下(queue_delay=0),LEDBAT也是每个RTT,cwnd的大小增加1。LEDBA相比基于丢包的的TCP拥塞控制机制,对于网络的拥塞感知要早。在queue_delay=2*TARGET时,每经一个RTT,cwnd减少1。就是说在队列时延增加的情况下,但是还未到达路由器的队列丢包阈值,TCP还处在拥塞避免阶段,tcp每个RTT,窗口增1,LEDBAT窗口减1。LEDBAT向TCP出让带宽。
LEDBAT论文:https://www.kth.se/social/files/5527dbf2f276543890e0c409/LEDBAT.pdf
LEDBADT的实现非常简单,可以作为module加载到linux系统里,源码地址:https://github.com/silviov/TCP-LEDBAT