计算机 · 2021年8月13日 0

TFRC

RFC5348,receiver based。sender based的要看RFC4343。

Introduction

  • TCP friendly: 速率在相同条件下TCP速率的2倍以内。
  • TFRC与TCP相比的优劣：带宽变化更平稳，但是因此对带宽的变化也没有那么敏感。
  • TFRC适用于固定包大小的场景，对于包大小不固定的，效果要差一点。

Protocol Mechanism

TFRC通过丢包事件(loss event)和RTT来计算发送速率，为了和TCP公平竞争，使用了TCP的发送速率计算公式。

丢包事件指丢包检测确认的丢包或者ECN(Explicit Congestion Notification)导致的丢包。
总的来说，TFRC工作原理如下：

  • 接收端检测loss event，并将结果(feedback)返回发送端；
  • 发送端利用接收端返回的feedback测量RTT；
  • 发送端用loss event和rate带入带宽计算公式，对得到的结果限制不超过2倍接收端接收速率来作为发送端的发送速率；

TFRC的带宽估计公式可以使用任何一种TCP的带宽估计公式，但是目前只有reno有推导出带宽估计公式，所以TFRC就使用了reno的带宽估计公式：

                                       s
X_Bps = ----------------------------------------------------------
        R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8)*p*(1+32*p^2)))

X_Bps is TCP’s average transmit rate in bytes per second. (X_Bps
is the same as X_calc in RFC 3448.)

s is the segment size in bytes (excluding IP and transport
protocol headers).

R is the round-trip time in seconds.

p is the loss event rate, between 0 and 1.0, of the number of loss
events as a fraction of the number of packets transmitted.

t_RTO is the TCP retransmission timeout value in seconds.

b is the maximum number of packets acknowledged by a single TCP
acknowledgement.

t_RTO计算时直接取4*RTT就好，b推荐取1。

对sender发的数据包的要求：

  1. 包含sequence number，每个包依次加1，位数要足够多，不要让接收端接收到sequence number回滚的包；
  2. 包含发包的毫秒级时间戳timestamp(如果sender有记录sequence和发包事件戳的映射，那么可以不包含时间戳)；

对receiver发送的feedback包的要求：

  1. 最后一个接收到的数据包的timestamp(用于测量RTT),t_recvdata；
  2. 从接收到最后一个包到发送这个feedback包所经过的延迟, t_delay；
  3. 接收端在过去一个RTT统计到的接收速率,X_recv；
  4. 接收端检测到的loss event rate p；

发送端的速率控制

发送端按照计算的发送速率发数据，当收到feedback包之后更新速率，当超过4个RTT还没有收到feedback包时，发送速率减半；
整个发送过程分为以下几部分：

  1. 测量平均包大小；
  2. 发送端初始化；
  3. 发送端对feedback包的处理；
  4. Oscillation prevention；
  5. Scheduling of packet transmission and allowed burstiness

1.测量平均包大小

在包大小经常变化的情况下，可以通过统计平均包大小来获取公式中的s。

2.发送端初始化

发送速率X和tld(the Time Last Doubled during slow-start, in seconds)一开始设为undefined或者无效值。当发送端需要发送数据但是还没有采集到RTT时，X设置为s字节每秒，nofeedback定时器设置为2秒。当采集到第一个RTT数据时，tld设置为当前时间，X设置为initial_rate，

initial_rate = W_init/R; W_init = min(4*MSS, max(2*MSS, 4380))

这里的MSS要使用发送包的最大大小，而不是TCP/IP协议中的MSS(应用层设置的最大包大小可能比协议层的MSS小)。

3.feedback包的处理

发送端需要维护当前的RTT估计值R，当前允许的发送速率X，以及X_recv_set(最近的接收速率X_recv值的集合)。
初始状态下，X_recv_set设置为包含一个无限大的值。
当一个feedback包在t_now时刻被sender收到时，进行以下操作：

  1. 计算新的RTT，R_sample = (t_now - t_recvdata) - t_delay；
  2. 更新RTT估计值：
   If no feedback has been received before {
      R = R_sample;
   } Else {
      R = q*R + (1-q)*R_sample;
   }

TFRC对q的取值不敏感，但是这里推荐取0.9。

  1. 更新RTO,RTO = max(4*R, 2*s/X)；
  2. 更新允许的发送速率X，
   If (the entire interval covered by the feedback packet
         was a data-limited interval) {
       If (the feedback packet reports a new loss event or an increase in the loss event rate p) {
           Halve entries in X_recv_set;
           X_recv = 0.85 * X_recv;
           Maximize X_recv_set();
           recv_limit = max (X_recv_set);
       } Else {
           Maximize X_recv_set();
           recv_limit = 2 * max (X_recv_set);
       }
   } Else { // typical behavior
       Update X_recv_set();
       recv_limit = 2 * max (X_recv_set);
   }
   If (p > 0) { // congestion avoidance phase
       Calculate X_Bps using the TCP throughput equation.
       X = max(min(X_Bps, recv_limit), s/t_mbi);
   } Else if (t_now - tld >= R) {
       // initial slow-start
       X = max(min(2*X, recv_limit), initial_rate);
       tld = t_now;
   }

t_mbi:the maximum backoff interval of 64 seconds.
recv_limit:the limit on the sending rate computed from X_recv_set.
data limited interval:在这一整个时间区间内sender都处于发送数据不足，不够填满发送速率的状态。
收到第一个feedback包对应的interval不是data limited interval。
接收端一般每个RTT发一个feedback包，这个feedback包cover的就是发出feedback包之前这一个RTT的interval。当前一个feedback包在传输过程中丢失或者接收端检测到loss event，发送端需要重新计算这个feedback包覆盖的interval。
在data limited interval内发生丢包的处理：即使是data limited interval，发送速率X也不能超过接收速率的2倍；而如果发生了丢包，则更要进一步减小x_recv_set中保存的接收速率。
Maximize X_recv_set()的实现：

   Add X_recv to X_recv_set;
   Delete initial value Infinity from X_recv_set, if it is still a member.
   Set the timestamp of the largest item to the current time;
   Delete all other items.

Update X_recv_set()的实现：

   Add X_recv to X_recv_set;
   Delete from X_recv_set values older than two round-trip times.

在检测到丢包之前，tfrc和TCP一样按照慢启动的方式增加发送速率。而s/t_mbi则保证在p>0的情况下，发送端至少还能够按照每64秒发送一个包的速率发送数据。

  1. 如果使用了oscillation reduction，那么按照4.5计算即时发送速率X_inst;
  2. 重置nofeedback timer超时时间为RTO;

4.nofeedback timer超时处理

如果从设置nofeedback timer开始，发送端一直处于idle状态，发送速率不会降到recover_rate(rfc5348将其设置为initial_rate)以下。
当nofeedback timer超时触发，发送端需要：

  1. 发送速率减半(但是同时需要满足上面说的idle状态下发送速率不能降到recover_rate以下)：
   X_recv = max (X_recv_set);
   If (sender does not have an RTT sample, has not received any feedback from receiver, and has not been idle ever since the nofeedback timer was set) {
       // We do not have X_Bps or recover_rate yet.
       // Halve the allowed sending rate.
       X = max(X/2, s/t_mbi);
   } Else if (((p>0 && X_recv < recover_rate) or (p==0 && X < 2 * recover_rate)), and sender has been idle ever since nofeedback timer was set) {
       // Don't halve the allowed sending rate. Do nothing;
   } Else if (p==0) {
       // We do not have X_Bps yet.
       // Halve the allowed sending rate.
       X = max(X/2, s/t_mbi);
   } Else if (X_Bps > 2*X_recv)) {
       // 2*X_recv was already limiting the sending rate.
       // Halve the allowed sending rate.
       Update_Limits(X_recv;)
   } Else {
       // The sending rate was limited by X_Bps, not by X_recv.
       // Halve the allowed sending rate.
       Update_Limits(X_Bps/2);
   }

s/t_mbi仍然限制最低发送速率为每64秒发送一个包。
Upper_Limits()的实现：

   Update_Limits(timer_limit):
       If (timer_limit < s/t_mbi)
           timer_limit = s/t_mbi;
       Replace X_recv_set contents with the single item
           timer_limit/2;
       Recalculate X as in step (4) of Section 4.3;
  1. 重启nofeedback timer，超时时间设置为max(4R, 2s/X)；

4. Reducing Oscillations

维护一个R_sqmean，即RTT平方根的一个统计值：

If no feedback has been received before {
R_sqmean = sqrt(R_sample);
} Else {
R_sqmean = q2*R_sqmean + (1-q2)*sqrt(R_sample);
}

q2推荐取值0.9。当最新的sqrt(R_sample)比这个统计值大时，表明链路上可能产生了queueing delay，此时需要用X_inst替换X：

X_inst = X * R_sqmean / sqrt(R_sample);
If (X_inst < s/t_mbi)
X_inst = s/t_mbi;

Reducing Oscillations只是RECOMMENDED，不是MUST。可以通过将q值取小来弱化Reducing Oscillations的作用。

5.scheduling of packet transmission and allowed burstiness

理想情况下TFRC应该按照发送速率实现pacing，但是如果定时器不够精准，或者发送端由于处于idle或者data limited状态，此时就需要使用按照pacing获取令牌的方式，即发送端按照pacing的间隔获取令牌，有发送数据包就消耗令牌，保存最近一个RTT内空闲的令牌，当有数据需要发送的时候，可以以burst的方式将累积的空闲令牌一次性消耗掉。 这里之所以限制只保存最近一个RTT内空闲的令牌是因为TCP也是限制一次性只能发送一个RTT内包数的burst。

Loss Event Rate(p)的计算

没有检测到丢包或者接收到ECN时，接收端在feedback包中将p置为0。

Detection of lost or marked packets

TFRC假设每个包的序列号是按加1递增的，而且重传的包必需要给一个新的序列号。如果传输协议不支持这样做，那么需要提供其他机制区分重传包和原始包以及检测到重传包的丢失。
如果接收端在收到NDUPACK(3)个序列号在S_lost之后的包，并且没有收到序列号为S_lost的包，那么S_lost被判定为丢包。
接收到带有ECN标记的包时，也将其统计为loss event。
接收端需要记录每个包的接收时间。

Translation from Loss History to Loss Events

TFRC需要按照RTT把丢包/ECN划分到不同的loss event。
首先需要估计丢失的包的接收时间：

T_loss = T_before + (T_after - T_before)
* Dist(S_loss, S_before)/Dist(S_after, S_before)
where
Dist(S_A, S_B) = (S_A + S_MAX - S_B) % S_MAX
S_MAX=2^b，表示序列号最多占b位。


其次，每个loss event里丢的包的时间跨度不能超过一个RTT。这个RTT由发送端放在数据包里发给接收端。比如假设上一个loss event里的第一个丢包对应的接收时间为T_old，那么当最新检测到的丢包的时间T_new > T_old + R，这个最新检测到的丢包就属于一个新的loss event了，否则属于上一个loss event。

the size of a loss interval

loss interval为一个loss event的第一个丢包的序列号，到下一个loss event的第一个丢包的序列号(不包含)。loss interval的大小为下一个loss interval的起始序列号减去当前loss interval的起始序列号。
当前loss interval I_0为包含最近一次loss event的loss interval。

Average Loss Interval

最多记录最近8个loss interval，权重取值如下：

Weights w_0 to w_(n-1) are calculated as:
If (i < n/2) {
    w_i = 1;
} Else {
    w_i = 2 * (n-i)/(n+2);
}
Thus, if n=8, the values of w_0 to w_7 are:
1.0, 1.0, 1.0, 1.0, 0.8, 0.6, 0.4, 0.2

w_0为当前loss interval的size的权重，w_1为上一个loss interval的size的权重。
Average loss interval I_mean的计算方式如下：

I_tot0 = 0;
I_tot1 = 0;
W_tot = 0;
for (i = 0 to k-1) {
    I_tot0 = I_tot0 + (I_i * w_i);
    W_tot = W_tot + w_i;
}
for (i = 1 to k) {
    I_tot1 = I_tot1 + (I_i * w_(i-1));
}
I_tot = max(I_tot0, I_tot1);
I_mean = I_tot/W_tot;

loss event rate p的计算公式为：p = 1 / I_mean。

History Discounting

由于上面的权重w_0值很小，为1/(0.75*n)，导致即使当前loss interval值很大，对average loss interval的影响也很小，因此这一节提出了一个可选的增加current loss interval size在计算average loss interval中权重的方法。因为这个机制是可选的，就等有空再细读这个机制了。

接收端的处理

接收端收到数据包时的处理

  1. 将该数据包加入packet history；
  2. 检查该数据包是否产生了新的loss event或者上次feedback timer超时时没有发送feedback包，如果是的继续运行第3步，否则处理结束；
  3. 保存之前的loss event rate p 位p_prev，计算新的loss event rate p；
  4. 如果p > p_prev，那么直接触发feedback timer；
    如果p <= p_prev，并且上次feedback timer触发时没有发送feedback包，那么需要触发feedback timer；
    如果p <= p_prev，并且上次feedback timer触发时有发送feedback包，那么处理结束；

feedback timer

如果自上次发送feedback包以来没有接收到新的数据包，那么feedback timer触发时不用发送feedback包，直接再次设置R_m秒的feedback timer。
如果有接收到新的数据包，那么假设这是第m次feedback timer的触发，接收端目前收到的最大序列号是S_m，S_m这个包里携带的发送端估计的最新RTT为R_m，接收端需要做的处理如下：

  1. 计算average loss event rate；
  2. 计算接收速率，X_recv，基于过去R_(m-1)秒内的接收数据进行计算；这个接收速率可能会被算小，因为这个定时器可能是因为新的loss event的产生而触发的，定时器并没有等待R_(m-1)秒这么长的时间；
  3. 发送feedback包，包含内容为前面所讲feedback必须包含的内容；
  4. 重新设置feedback timer，超时时间为R_m秒；

接收端的初始化

接收端在接收第一个数据包的时候进行初始化(假设其序列号为i)：

  • 设置p = 0；
  • 设置X_recv = 0；
  • 如果数据包中有携带发送端估计的RTT，R_i，那么就设置feedback定时器为R_i秒后触发；
    如果数据包中没有携带RTT，那么接收端就没收到一个数据包回复一次，知道发送端发送带有RTT的数据包；
    如果发送端采取每过1/4RTT将包的序列号加1的策略的话，那么接收端也可以完全不要定时器，只在检测接收到的最大包序列号增加4的时候发送一次feedback包即可。

在检测到第一次loss event后对Loss History的初始化

TFRC并不是把第一次Loss Event之前的包数作为初始的loss interval，而是按照之前的带宽计算公式去找一个p，使得计算出来的发送速率与X_target的误差在5%以内，然后用1/p作为初始的loss interval。这个X_target是loss event发生之前的最大X_recv。
如果第一个包就丢了，那么情况又不一样，那么TFRC的初始interval就是一个null interval，这个时候TFRC回去按公式找一个带宽估算为0.5 packets per RTT的p，然后用1/p作为初始interval的长度。这个0.5 packets per RTT的速率也是按照TCP在第一个包丢包时的行为估计出来的。

基于sender的变种

参考RFC4340和RFC4342描述的DCCP的CCID 3。基于sender的TFRC要求接收端发feedback包给发送端时走可靠传输，而基于receiver的TFRC允许feedback包在传输过程中丢失。

标签：

发表回复