Sprout: Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular Networks

(1) 论文背景与核心问题

• 背景: 蜂窝无线网络(如 LTE, 3G)已成为主流, 但其链路速率随时间剧烈波动, 且经常出现数秒的中断.
• 问题: 现有的传输协议(如 TCP)和应用是反应式(Reactive)的. 它们在链路变差时无法及时降低发送速率, 导致数据包堆积在网络网关的深队列中(Bufferbloat), 造成巨大的延迟(可达数秒), 严重破坏交互体验.
• 挑战: 需要在链路速率剧烈波动的情况下, 同时实现高吞吐量和低延迟.

(2) 核心解决方案: Sprout 协议

Sprout 是一个端到端的传输协议, 专门针对交互式应用设计. 其核心思想从"反应式拥塞控制"转变为"预测性流量控制".

• 推断模型 (Inference Model):
  • Sprout 不依赖丢包或 RTT 来判断拥塞, 而是由接收端观察数据包的到达时间.
  • 它将链路建模为双重随机过程: 数据包的到达符合泊松过程(Poisson Process), 而该过程的速率 \(\lambda\) 自身也在随时间变化(布朗运动).
  • 接收端利用贝叶斯推断, 实时更新当前链路速率的概率分布.
• 随机预测 (Stochastic Forecast):
  • 基于上述模型, 接收端预测未来短时间内(例如 160ms)网络能传输多少字节.
  • 这种预测是保守的: Sprout 计算出有 95% 概率 能被传输的数据量(即取预测分布的第 5 百分位).
• 控制机制 (Control Loop):
  • 接收端将预测结果发回发送端.
  • 发送端根据预测结果计算发送窗口, 确保发出的数据包在队列中停留超过 100ms 的风险极低(<5%).

(3) 实验环境与方法

为了真实评估, 作者构建了一套基于痕迹(Trace-driven)的测试系统:

• 数据采集 (Saturator): 作者在美国波士顿地区驾驶车辆, 收集了 Verizon (LTE/3G), AT&T (LTE), T-Mobile (3G) 四家运营商的真实网络痕迹.
• 仿真器 (Cellsim): 开发了一个网络仿真器, 重放这些痕迹, 以确保所有协议在完全相同的网络条件下进行对比.

Sprout 在吞吐量和延迟的平衡上显著优于现有方案:

• 对比商业软件:
  • Skype: Sprout 将延迟降低了 7.9 倍, 吞吐量是其 2.2 倍.
  • Facetime: Sprout 将延迟降低了 8.7 倍, 吞吐量是其 1.9 倍.
  • Google Hangout: Sprout 将延迟降低了 7.2 倍, 吞吐量是其 4.4 倍.
• 对比 TCP 变种:
  • Sprout 的性能优于 TCP Cubic, TCP Vegas, Compound TCP 和 LEDBAT.
• 对比主动队列管理 (AQM):
  • Cubic-over-CoDel: CoDel 是一种需要部署在运营商基站侧的先进队列管理算法. 实验显示, 纯端到端的 Sprout 在延迟上甚至优于需要修改基础设施的 CoDel, 且无需运营商配合.

Introduction

Cellular wireless networks have become a dominant mode of Internet access. These mobile networks, which include LTE and 3G (UMTS and 1xEV-DO) services, present new challenges for network applications, because they behave differently from wireless LANs and from the Internet’s traditional wired infrastructure. Cellular wireless networks experience rapidly varying link rates and occasional multi-second outages in one or both directions, especially when the user is mobile. As a result, the time it takes to deliver a network-layer packet may vary significantly, and may include the ef- fects of link-layer retransmissions. Moreover, these net- works schedule transmissions after taking channel qual- ity into account, and prefer to have packets waiting to be sent whenever a link is scheduled. They often achieve that goal by maintaining deep packet queues. The effect at the transport layer is that a stream of packets expe- riences widely varying packet delivery rates, as well as variable, sometimes multi-second, packet delays.

For an interactive application such as a videoconfer- encing program that requires both high throughput and low delay, these conditions are challenging. If the appli- cation sends at too low a rate, it will waste the oppor- tunity for higher-quality service when the link is doing well. But when the application sends too aggressively, it accumulates a queue of packets inside the network wait- ing to be transmitted across the cellular link, delaying subsequent packets. Such a queue can take several sec- onds to drain, destroying interactivity (see Figure 1). Our experiments with Microsoft’s Skype, Google’s Hangout, and Apple’s Facetime running over traces from commercial 3G and LTE networks show the shortcom- ings of the transport protocols in use and the lack of adaptation required for a good user experience. The transport protocols deal with rate variations in a reactive manner: they attempt to send at a particular rate, and if all goes well, they increase the rate and try again. They are slow to decrease their transmission rate when the link has deteriorated, and as a result they often create a large backlog of queued packets in the network. When that happens, only after several seconds and a user-visible outage do they switch to a lower rate. This paper presents Sprout, a transport protocol de- signed for interactive applications on variable-quality networks. Sprout uses the receiver’s observed packet ar- rival times as the primary signal to determine how the network path is doing, rather than the packet loss, round- trip time, or one-way delay. Moreover, instead of the tra- ditional reactive approach where the sender’s window or rate increases or decreases in response to a congestion signal, the Sprout receiver makes a short-term forecast (at times in the near future) of the bottleneck link rate using probabilistic inference. From this model, the re- ceiver predicts how many bytes are likely to cross the link within several intervals in the near future with at least 95% probability. The sender uses this forecast to trans- mit its data, bounding the risk that the queuing delay will exceed some threshold, and maximizing the achieved throughput within that constraint. We conducted a trace-driven experimental evaluation (details in §5) using data collected from four different commercial cellular networks (Verizon’s LTE and 3G 1xEV-DO, AT&T’s LTE, and T-Mobile’s 3G UMTS). We compared Sprout with Skype, Hangout, Facetime, and several TCP congestion-control algorithms, running in both directions (uplink and downlink). The following table summarizes the average relative throughput improvement and reduction in self-inflicted queueing delay1 for Sprout compared with the various other schemes, averaged over all four cellular networks in both directions. Metrics where Sprout did not outper- form the existing algorithm are highlighted in red:

Cubic-CoDel indicates TCP Cubic running over the CoDel queue-management algorithm [17], which would be implemented in the carrier’s cellular equipment to be deployed on a downlink, and in the baseband modem or radio-interface driver of a cellular phone for an uplink. We also evaluated a simplified version of Sprout, called Sprout-EWMA, that tracks the network bitrate with a simple exponentially-weighted moving average, rather than making a cautious forecast of future packet deliveries with 95% probability. Sprout and Sprout-EWMA represents different trade- offs in their preference for throughput versus delay. As expected, Sprout-EWMA achieved greater throughput, but also greater delay, than Sprout. It outperformed TCP Cubic on both throughput and delay. Despite being end- to-end, Sprout-EWMA outperformed Cubic-over-CoDel on throughput and approached it on delay:

We also tested Sprout as a tunnel carrying competing traffic over a cellular network, with queue management performed at the tunnel endpoints based on the receiver’s stochastic forecast about future link speeds. We found that Sprout could isolate interactive and bulk flows from one another, dramatically improving the performance of Skype when run at the same time as a TCP Cubic flow. The source code for Sprout, our wireless network trace capture utility, and our trace-based network emulator is available at http://alfalfa.mit.edu/.

蜂窝无线网络已成为互联网接入的主流方式. 这些移动网络--包括 LTE 和 3G(如 UMTS 和 1xEV-DO)服务--给网络应用带来了新的挑战, 因为它们的行为模式截然不同于无线局域网(WLAN)以及互联网传统的有线基础设施.

蜂窝无线网络经历着链路速率的剧烈波动, 以及单向或双向偶尔出现的持续数秒的中断, 特别是在用户处于移动状态时. 因此, 网络层数据包的传输时间可能会发生显著变化, 其中可能包含了链路层重传的影响. 此外, 这些网络在调度传输时会考虑信道质量, 并倾向于在链路被调度时总有数据包等待发送. 它们通常通过维护深层的数据包队列来实现这一目标. 这对传输层的影响是, 数据包流会经历极不稳定的交付速率, 以及可变的, 有时长达数秒的数据包延迟.

对于像视频会议程序这样既需要高吞吐量又需要低延迟的交互式应用而言, 这些条件极具挑战性:

• 如果应用发送速率过低, 就会浪费链路状况良好时提供更高质量服务的机会;
• 如果应用发送过于激进, 就会在网络内部积累等待通过蜂窝链路传输的数据包队列, 从而延迟后续数据包
  • 这样的队列可能需要数秒才能排空, 从而破坏交互性

我们在来自商用 3G 和 LTE 网络的数据轨迹上运行了微软的 Skype, 谷歌的 Hangout 和苹果的 Facetime, 实验结果显示了当前使用的传输协议的缺陷, 以及缺乏提供良好用户体验所需的自适应能力. 这些传输协议以"反应式"(reactive)的方式处理速率变化: 它们尝试以特定速率发送, 如果一切顺利, 则提高速率并再次尝试. 当链路恶化时, 它们降低传输速率的速度很慢, 结果往往导致网络中出现大量排队数据包积压. 只有在这种情况发生数秒并出现用户可见的中断后, 它们才会切换到较低的速率.

本文提出了 Sprout, 一种专为变质(variable-quality)网络上的交互式应用设计的传输协议:

Sprout 使用 接收端观测到的数据包到达时间作为主要信号 来判断网络路径状况, 而不是依赖丢包, 往返时间(RTT)或单向延迟.

此外, Sprout 不采用传统的反应式方法(即发送端窗口或速率随拥塞信号增减), 而是由接收端利用概率, 推断对瓶颈链路速率进行短期预测(针对不久的将来).

基于该模型, 接收端预测在不久的将来的几个时间间隔内, 以至少 95% 的概率可能通过链路传输的字节数.

发送端利用这一预测来传输数据, 在限制排队延迟超过特定阈值的风险的同时, 在该约束下最大化实现的吞吐量.

我们使用从四个不同的商用蜂窝网络(Verizon 的 LTE 和 3G 1xEV-DO, AT&T 的 LTE, 以及 T-Mobile 的 3G UMTS)收集的数据, 进行了基于痕迹驱动(trace-driven)的实验评估(详情见第5节).

我们将 Sprout 与 Skype, Hangout, Facetime 以及几种 TCP 拥塞控制算法在双向(上行和下行)上进行了比较.

下表总结了 Sprout 与其他各种方案相比, 在所有四个蜂窝网络的双向传输中平均相对吞吐量的提升以及自致排队延迟(self-inflicted queueing delay)的降低情况.

Sprout 未能优于现有算法的指标已用红色高亮显示.

Cubic-CoDel 指的是运行在 CoDel 队列管理算法之上的 TCP Cubic, 若要部署该算法, 需要在下行链路的运营商蜂窝设备中, 以及上行链路的手机基带调制解调器或无线接口驱动程序中进行实现.

我们还评估了 Sprout 的简化版本, 称为 Sprout-EWMA, 它使用简单的指数加权移动平均(EWMA)来跟踪网络比特率, 而不是对未来数据包交付进行具有 95% 概率的谨慎预测.

Sprout 和 Sprout-EWMA 代表了在吞吐量与延迟偏好上的不同权衡. 不出所料, Sprout-EWMA 实现了比 Sprout 更高的吞吐量, 但也带来了更大的延迟. 它在吞吐量和延迟方面均优于 TCP Cubic. 尽管是端到端的方案, Sprout-EWMA 在吞吐量上优于 Cubic-over-CoDel, 并在延迟上接近后者.

我们还测试了将 Sprout 作为在蜂窝网络上传输竞争流量的隧道, 并根据接收端对未来链路速度的随机预测在隧道端点执行队列管理. 我们发现, Sprout 能够将交互式流与批量传输流相互隔离, 从而在 Skype 与 TCP Cubic 流同时运行时显著提高了 Skype 的性能.

Sprout 的源代码, 我们的无线网络痕迹捕获工具以及基于痕迹的网络仿真器均可在 http://alfalfa.mit.edu/ 获取.

Context and Challenges

This section highlights the networking challenges in de- signing an adaptive transport protocol on cellular wire- less networks. We discuss the queueing and scheduling mechanisms used in existing networks, present measure- ments of throughput and delay to illustrate the problems, and list the challenges.

2.1 Cellular Networks

At the link layer of a cellular wireless network, each de- vice (user) experiences a different time-varying bit rate because of variations in the wireless channel; these varia- tions are often exacerbated because of mobility. Bit rates are also usually different in the two directions of a link. One direction may experience an outage for a few sec- onds even when the other is functioning well. Variable link-layer bit rates cause the data rates at the transport layer to vary. In addition, as in other data networks, cross traffic caused by the arrival and departure of other users and their demands adds to the rate variability. Most (in fact, all, to our knowledge) deployed cellu- lar wireless networks enqueue each user’s traffic in a separate queue. The base station schedules data trans- missions taking both per-user (proportional) fairness and channel quality into consideration [3]. Typically, each user’s device is scheduled for a fixed time slice over which a variable number of payload bits may be sent, de- pending on the channel conditions, and users are sched- uled in roughly round-robin fashion. The isolation be- tween users’ queues means that the dominant factor in the end-to-end delay experienced by a user’s packets is self-interaction, rather than cross traffic. If a user were to combine a high-throughput transfer and a delay-sensitive transfer, the commingling of these packets in the same queue would cause them to experience the same de- lay distributions. The impact of other users on delay is muted. However, competing demand can affect the throughput that a user receives. Many cellular networks employ a non-trivial amount of packet buffering. For TCP congestion control with a small degree of statistical multiplexing, a good rule- of-thumb is that the buffering should not exceed the bandwidth-delay product of the connection. For cellular networks where the “bandwidth” may vary by two or- ders of magnitude within seconds, this guideline is not particularly useful. A “bufferbloated” [9] base station at one link rate may, within a short amount of time, be under-provisioned when the link rate suddenly increases, leading to extremely high IP-layer packet loss rates (this problem is observed in one provider [16]). The high delays in cellular wireless networks cannot simply be blamed on bufferbloat, because there is no single buffer size that will always work. It is also not simply a question of using an appropriate Active Queue Management (AQM) scheme, because the difficulties in picking appropriate parameters are well-documented and become harder when the available rates change quickly, and such a scheme must be appropriate when applied to all applications, even if they desire bulk throughput. In §5, we evaluate CoDel [17], a recent AQM technique, together with a modern TCP variant (Cubic, which is the default in Linux), finding that on more than half of our tested network paths, CoDel slows down a bulk TCP transfer that has the link to itself. By making changes—when possible—at endpoints in- stead of inside the network, diverse applications may have more freedom to choose their desired compromise between throughput and delay, compared with an AQM scheme that is applied uniformly to all flows. Sprout is not a traditional congestion-control scheme, in that its focus is directed at adapting to varying link conditions, not to varying cross traffic that contends for the same bottleneck queue. Its improvements over exist- ing schemes are found when queueing delays are im- posed by one user’s traffic. This is typically the case when the application is running on a mobile device, be- cause cellular network operators generally maintain a separate queue for each customer, and the wireless link is typically the bottleneck. An important limitation of this approach is that in cases where these conditions don’t hold, Sprout’s traffic will experience the same delays as other flows.

2.1 蜂窝网络

在蜂窝无线网络的链路层, 受无线信道波动的影响, 每个设备(用户)经历的比特率随时间呈现不同程度的变化; 这种波动往往因用户的移动性而加剧. 链路双向的比特率通常也存在差异. 即使一个方向运行正常, 另一个方向也可能经历数秒的中断. 可变的链路层比特率导致传输层的数据速率发生波动. 此外, 与其他数据网络一样, 由其他用户的加入, 离开及其需求所产生的交叉流量(cross traffic), 进一步增加了速率的不确定性.

大多数(事实上, 据我们所知是所有)已部署的蜂窝无线网络都将每个用户的流量置于独立的队列中

基站在调度数据传输时, 会同时考虑每用户的(比例)公平性和信道质量. 通常, 每个用户的设备会被分配一个固定的时间片, 在此期间发送的有效载荷比特数取决于信道条件, 而用户调度大致遵循轮询(round-robin)方式.

用户队列间的隔离性意味着, 数据包经历的端到端延迟的主要因素是"自干扰"(self-interaction), 而非交叉流量

如果用户同时进行高吞吐量传输和对延迟敏感的传输, 这些数据包在同一队列中的混合将导致它们经历相同的延迟分布. 其他用户对延迟的影响被显著削弱. 不过, 竞争性需求仍会影响用户获得的吞吐量.

许多蜂窝网络采用了相当大(non-trivial)的数据包缓冲区

对于具有少量统计复用的 TCP 拥塞控制而言, 一个通用的经验法则是缓冲区大小不应超过连接的带宽时延积(BDP). 然而, 对于"带宽"可能在数秒内变化两个数量级的蜂窝网络来说, 这一准则并不适用. 一个在特定链路速率下处于"缓冲膨胀(bufferbloated)"状态的基站, 可能在极短时间内因链路速率突然增加而变得缓冲区配置不足(under-provisioned), 从而导致极高的 IP 层丢包率(这一问题曾在某运营商网络中被观测到).

蜂窝无线网络中的高延迟不能简单地归咎于缓冲膨胀, 因为不存在一个始终适用的单一缓冲区大小

这也不仅仅是采用合适的主动队列管理(AQM)方案就能解决的问题, 因为选择合适参数的困难已有详实记录, 而在可用速率快速变化时这一问题尤为棘手. 此外, AQM 方案必须适用于所有应用, 即使是那些追求批量吞吐量的应用. 在第 5 节中, 我们将评估近期提出的 AQM 技术 CoDel 以及现代 TCP 变种(Linux 默认的 Cubic). 结果发现, 在我们测试的一半以上的网络路径中, 当链路被批量 TCP 传输独占时, CoDel 反而降低了传输速度.

通过在端点(而非网络内部)进行可能的改进, 与统一应用于所有流的 AQM 方案相比, 各类应用能更自由地选择其期望的吞吐量与延迟之间的权衡.

Sprout 并非传统的拥塞控制方案, 其核心在于适应变化的链路条件, 而非应对争夺同一瓶颈队列的交叉流量. 其优势体现在排队延迟主要由用户自身流量引起的情况下. 这在移动设备应用中非常典型, 因为蜂窝网络运营商通常为每位客户维护独立的队列, 且无线链路通常是瓶颈. 该方法的一个重要局限是, 若上述条件不成立, Sprout 流量将经历与其他流相同的延迟.

2.2 Measurement Example

In our measurements, we recorded large swings in avail- able throughput on mobile cellular links. Existing inter- active transports do not handle these well. Figure 1 shows an illustrative section of our trace from the Verizon LTE downlink, whose capacity varied up and down by al- most an order of magnitude within one second. From 15 to 25 seconds into the plot, and from 43 to 49 sec- onds, Skype overshoots the available link capacity, caus- ing large standing queues that persist for several seconds, and leading to glitches or reduced interactivity for the users. By contrast, Sprout works to maximize the avail- able throughput, while limiting the risk that any packet will wait in queue for more than 100 ms (dotted line).

It also makes mistakes (e.g., it overshoots at t = 43 sec- onds), but then repairs them. Network behavior like the above has motivated our development of Sprout and our efforts to deal explicitly with the uncertainty of future link speed variations.

2.2 测量示例

在测量过程中, 我们记录到了移动蜂窝链路可用吞吐量的剧烈波动. 现有的交互式传输协议未能很好地应对这一问题.

图 1 展示了 Verizon LTE 下行链路痕迹中的一个典型片段, 其容量在一秒内上下波动了近一个数量级.

在图表的 15 至 25 秒以及 43 至 49 秒区间内, Skype 的发送速率超过了可用链路容量, 导致了持续数秒的严重排队积压, 从而引起画面卡顿或用户交互体验下降. 相比之下, Sprout 在致力于最大化可用吞吐量的同时, 将任何数据包在队列中等待时间超过 100 毫秒(虚线所示)的风险控制在限度内.

尽管 Sprout 也会出现误判(例如在 t=43 秒时的超调), 但它能随后进行自我修正. 上述网络行为促使我们开发了 Sprout, 并致力于显式地处理未来链路速率变化的不确定性.

2.3 Challenges

A good transport protocol for cellular wireless networks must overcome the following challenges:

1. It must cope with dramatic temporal variations in link rates.
2. It must avoid over-buffering and incurring high de- lays, but at the same time, if the rate were to in- crease, avoid under-utilization.
3. It must be able to handle outages without over- buffering, cope with asymmetric outages, and re- cover gracefully afterwards.

Our experimental results show that previous work (see §6) does not address these challenges satisfactorily. These methods are reactive, using packet losses, round- trip delays, and in some cases, one-way delays as the “signal” of how well the network is doing. In contrast, Sprout uses a different signal, the observed arrival times of packets at the receiver, over which it runs an inference procedure to make forecasts of future rates. We find that this method produces a good balance between through- put and delay under a wide range of conditions.

一个优秀的蜂窝无线网络传输协议必须克服以下挑战:

1. 它必须应对链路速率在时间上的剧烈波动.
2. 它必须避免过度缓冲和产生高延迟, 但同时, 若速率提升, 又要避免资源利用不足.
3. 它必须能够在不过度缓冲的情况下处理中断, 应对不对称中断, 并在中断结束后平滑恢复.

我们的实验结果表明, 以往的研究(见第 6 节)并未圆满解决这些挑战. 这些方法均属于反应式(reactive)机制, 利用丢包, 往返延迟以及某些情况下的单向延迟作为衡量网络状况的"信号". 相比之下, Sprout 采用了一种不同的信号--即接收端观测到的数据包到达时间, 并利用该信号运行推断程序以预测未来的速率. 我们发现, 这种方法在广泛的条件下均能在吞吐量与延迟之间实现良好的平衡.

The Sprout Algorithm

1. 动机: 应对极度不稳定的蜂窝链路

• 背景问题: 蜂窝网络的链路容量波动极大, 这与传统有线网络完全不同
  • 现有的协议(如 TCP)反应迟钝, 当网络变差时不能及时减速, 导致数据堆积在队列中, 产生数秒的延迟
• Sprout 的目标: 在不牺牲吞吐量的前提下, 将延迟控制在极低水平
• 图表对应: Figure 1 展示了这一对比. 图中虚线(Capacity)剧烈波动
  • Skype(红色): 在网络变差时发送速率超过了容量, 导致延迟(下半部分红线)飙升至数秒.
  • Sprout(蓝色): 紧贴容量变化, 虽偶有误判, 但能迅速修正, 将延迟控制在 100ms 左右(下半部分蓝线)

2. 链路建模: 双重随机过程

为了预测网络行为, Sprout 将链路抽象为一个数学模型, 而不仅仅是简单的丢包检测

• 泊松过程 (Poisson Process): 假设数据包的到达符合泊松过程
• 布朗运动 (Brownian Motion):
  • 泊松过程的速率参数 本身不是固定的, 而是随着时间进行布朗运动(随机游走)
  • 这意味着网络速率是不确定的, 且随时间推移不确定性会增加
• 图表对应:
  • Figure 2 展示了这一假设的依据. 数据包到达间隔符合 噪声分布(Flicker noise), 虽然大部分包到达很快(<20ms), 但存在长尾效应(Outages), 说明速率极不稳定
  • 
  • Figure 3 是该模型的系统框图
    • Sender 发送数据进入 Queue
    • Receiver 接收数据
    • 中间的 \(\lambda\) 是控制"阀门", 它由底部的 \(\sigma\)(布朗运动噪声功率)和 \(\lambda_{z}\)(中断逃逸率)共同决定
  • 

3. 接收端推断: 贝叶斯更新

接收端不仅是被动接收, 还在实时计算当前速率 \(\lambda\) 的概率分布. Sprout 将时间切分为 20ms 的片段(tick), 并在每个 tick 执行以下三步:

1. 演化 (Evolution): 根据布朗运动公式, 扩散 \(\lambda\) 的概率分布(因为时间过得越久, 当前的估计越不准确, 不确定性越大)
2. 观测 (Observation): 统计这 20ms 内实际收到了多少字节. 利用贝叶斯公式, 提高那些"最可能产生此观测结果"的速率 \(\lambda\) 的概率权重

3. 归一化 (Normalization): 确保所有可能的 \(\lambda\) 概率之和为 1

4. 消除空队列歧义: 如果接收端没收到包, 是因为网断了(\(\lambda = 0\))还是发送端没发数据?

   • 方法: Sprout 在包头中加入 "time-to-next"(预计下个包的时间), 让接收端能区分这两种情况, 避免误判网络中断

4. 预测与发送控制 (Forecasting & Control)

这是 Sprout 的核心--不是基于当下的速率发送, 而是基于对未来的保守预测发送.

• 保守预测 (The Forecast):

  • 接收端将当前的概率模型向未来推演 160ms(8个 tick)
  • 它计算出一个累积交付曲线, 并取第 5 百分位 (5th percentile)
  • 这意味着: Sprout 有 95% 的把握, 未来实际能传输的数据量大于或等于这个预测值

• 发送窗口计算 (Using the Forecast):

  • 发送端收到预测后, 计算"安全发送窗口"
  • 图表对应: Figure 4 完美诠释了这一过程
  • 红色曲线: 接收端发来的 95% 置信度预测曲线(即未来能传多少包)
  • 黑色箭头 (Send 50 packets...): 代表当前已经发送但尚未确认的数据(Flight size)
  • 蓝色虚线 (100ms lookahead): 发送端向未来看 100ms
  • 计算逻辑: 找到红色曲线上未来 100ms 对应的点, 减去当前已发送的包数(y轴差值). 剩余的部分就是现在可以安全发送的包数(Window Size)

总结 Sprout 的核心逻辑:

它不看丢包(太慢), 不看 RTT(不准), 而是看到达时间. 通过 Fig. 3 的模型推断速率, 生成 Fig. 4 中的红色保守预测曲线, 从而指导发送端, 最终实现 Fig. 1 中那样紧贴容量且不造成数据堆积的效果

Experimental Testbed

We use trace-driven emulation to evaluate Sprout and compare it with other applications and protocols under reproducible network conditions. Our goal is to capture the variability of cellular networks in our experiments and to evaluate each scheme under the same set of time- varying conditions.

我们使用基于痕迹驱动(trace-driven)的仿真来评估 Sprout, 并在可复现的网络条件下将其与其他应用和协议进行比较. 我们的目标是在实验中捕捉蜂窝网络的可变性, 并在一组相同的随时间变化的条件下评估每种方案.

4.1 Saturator

Our strategy is to characterize the behavior of a cellu- lar network by saturating its uplink and downlink at the same time with MTU-sized packets, so that neither queue goes empty. We record the times that packets actually cross the link, and we treat these as the ground truth rep- resenting all the times that packets could cross the link as long as a sender maintains a backlogged queue.

Because even TCP does not reliably keep highly vari- able links saturated, we developed our own tool. The Sat- urator runs on a laptop tethered to a cell phone (which can be used while in a car) and on a server that has a good, low-delay (< 20 ms) Internet path to the cellular carrier.

The sender keeps a window of N packets in flight to the receiver, and adjusts N in order to keep the observed RTT greater than 750 ms (but less than 3000 ms). The theory of operation is that if packets are seeing more than 750 ms of queueing delay, the link is not starving for offered load. (We do not exceed 3000 ms of delay because the cellular network may start throttling or drop- ping packets.)

There is a challenge in running this system in two di- rections at once (uplink and downlink), because if both links are backlogged by multiple seconds, feedback ar- rives too slowly to reliably keep both links saturated. Thus, the Saturator laptop is actually connected to two cell phones. One acts as the “device under test,” and its uplink and downlink are saturated. The second cell phone is used only for short feedback packets and is otherwise kept unloaded. In our experiments, the “feedback phone” was on Verizon’s LTE network, which provided satisfac- tory performance: generally about 20 ms delay back to the server at MIT.

We collected data from four commercial cellular net- works: Verizon Wireless’s LTE and 3G (1xEV-DO / eHRPD) services, AT&T’s LTE service, and T-Mobile’s 3G (UMTS) service.5 We drove around the greater Boston area at rush hour and in the evening while record- ing the timings of packet arrivals from each network, gathering about 17 minutes of data from each. Because the traces were collected at different times and places, the measurements cannot be used to compare different commercial services head-to-head.

For the device under test, the Verizon LTE and 1xEV- DO (3G) traces used a Samsung Galaxy Nexus smart- phone running Android 4.0. The AT&T trace used a Samsung Galaxy S3 smartphone running Android 4.0. The T-Mobile trace used a Samsung Nexus S smartphone running Android 4.1.

我们的策略是通过同时使蜂窝网络的上行和下行链路饱和(使用 MTU 大小的数据包)来表征其行为, 从而确保两个队列都不为空. 我们记录数据包实际通过链路的时间, 并将其作为"基准真值"(ground truth), 代表只要发送端保持队列积压, 数据包实际上能够通过链路的所有时间点.

由于即使是 TCP 也无法可靠地保持高度可变的链路处于饱和状态, 我们开发了自己的工具. Saturator 运行在一台通过网络共享连接到手机(可在车内使用)的笔记本电脑上, 以及一台与蜂窝运营商之间具有良好, 低延迟(< 20 ms)互联网路径的服务器上.

发送端维持一个发往接收端的 N 个数据包的飞行窗口(packets in flight), 并调整 N 以保持观测到的 RTT 大于 750 ms(但小于 3000 ms). 其工作原理是, 如果数据包经历了超过 750 ms 的排队延迟, 链路就不存在供给不足(starving for offered load)的情况. (我们不超过 3000 ms 的延迟, 是因为蜂窝网络可能会开始限流或丢弃数据包.)

同时在两个方向(上行和下行)运行该系统存在挑战, 因为如果两条链路都积压了数秒的数据, 反馈到达的速度就会太慢, 无法可靠地保持两条链路饱和.

因此, Saturator 笔记本实际上连接了两部手机:

一部作为"被测设备", 其上行和下行链路处于饱和状态.

第二部手机仅用于传输短小的反馈数据包, 除此之外保持空闲. 在我们的实验中, "反馈手机"使用的是 Verizon 的 LTE 网络, 其性能令人满意: 通常回到 MIT 服务器的延迟约为 20 ms.

---

说的更明白点:

1. 移动端 (Mobile Client - Car):

   • Laptop (Saturator Client): 运行 Saturator 客户端软件, 负责生成流量并调整发送窗口
   • Phone 1 (DUT - Device Under Test):
     • 被测设备(如 Android 手机), 承载饱和流量 (Saturation Traffic)
     • 它的任务是负责"(实际被观测)数据层", 建立积压队列(Queues Full), 以测量链路的极限容量
   • Phone 2 (Feedback Phone):
     • 专用反馈设备(如 Verizon LTE 手机), 承载控制流量 (Feedback Traffic)
     • 由于主链路处于拥塞状态, 为了保证控制信号(ACKs)的低延迟(<20ms), 系统通过第二部手机回传反馈信息

2. 网络端 (Network & Server):

   • Cellular Network: 包括 Verizon LTE/3G, AT&T LTE, T-Mobile 3G 等商用网络
   • Server (MIT): 位于网络条件良好的节点, 运行 Saturator 服务端软件

3. 控制逻辑 (Control Logic):

   • 目标 (Goal): 保持链路饱和但不丢包
   • 算法 (Algorithm): 动态调整飞行窗口大小, 使得观测到的 RTT 保持在 750ms 至 3000ms 之间
   • > 750ms: 确保队列非空(链路未闲置)
   • < 3000ms: 防止触发运营商的丢包或限流机制

---

我们从四个商用蜂窝网络收集了数据: Verizon Wireless 的 LTE 和 3G (1xEV-DO / eHRPD) 服务, AT&T 的 LTE 服务, 以及 T-Mobile 的 3G (UMTS) 服务. 我们在波士顿大都会区的早晚高峰时段驾车行驶, 记录来自每个网络的数据包到达时间, 从每个网络收集了约 17 分钟的数据. 由于痕迹是在不同时间和地点收集的, 这些测量结果不能用于直接比较不同商业服务的优劣.

对于被测设备, Verizon LTE 和 1xEV-DO (3G) 的痕迹使用的是运行 Android 4.0 的三星 Galaxy Nexus 智能手机. AT&T 的痕迹使用的是运行 Android 4.0 的三星 Galaxy S3 智能手机. T-Mobile 的痕迹使用的是运行 Android 4.1 的三星 Nexus S 智能手机.

4.2 Cellsim

We then replay the traces in a network emulator, which we call Cellsim (Figure 5). It runs on a PC and takes in packets on two Ethernet interfaces, delays them for a configurable amount of time (the propagation delay), and adds them to the tail of a queue. Cellsim releases packets from the head of the queue to the other network interface according to the same trace that was previously recorded by Saturator. If a scheduled packet delivery occurs while the queue is empty, nothing happens and the opportunity to delivery a packet is wasted.

Empirically, we measure a one-way delay of about 20 ms in each direction on our cellular links (by sending a single packet in one direction on the uplink or down- link back to a desktop with good Internet service). All our experiments are done with this propagation delay, or in other words a 40 ms minimum RTT.

Cellsim serves as a transparent Ethernet bridge for a Mac or PC under test. A second computer (which runs the other end of the connection) is connected directly to the Internet. Cellsim and the second computer re- ceive their Internet service from the same gigabit Eth- ernet switch.

We tested the latest (September 2012) real-time imple- mentations of all the applications and protocols (Skype, Facetime, etc.) running on separate late-model Macs or PCs (Figure 6).

We also added stochastic packet losses to Cellsim to study Sprout’s loss resilience. Here, Cellsim drops pack- ets from the tail of the queue according to a specified random drop rate. This approach emulates, in a coarse manner, cellular networks that do not have deep packet buffers (e.g., Clearwire, as reported in [16]). Cellsim also includes an optional implementation of CoDel, based on the pseudocode in [17].

随后, 我们在一个名为 Cellsim 的网络仿真器中重放这些痕迹(图 5):

它运行在一台 PC 上, 通过两个以太网接口接收数据包, 将它们延迟一段可配置的时间(传播延迟), 然后将其加入队列尾部. Cellsim 按照 Saturator 之前记录的相同痕迹, 从队列头部将数据包释放到另一个网络接口. 如果预定的数据包交付时间到来时队列为空, 则不进行任何操作, 该次交付数据包的机会即被浪费.

根据经验, 我们测量到蜂窝链路每个方向的单向延迟约为 20 ms(通过在一个方向上, 即上行或下行, 发送单个数据包回到具有良好互联网服务的桌面电脑测得). 我们所有的实验均在此传播延迟下进行, 换言之, 最小 RTT 为 40 ms.

Cellsim 作为被测 Mac 或 PC 的透明以太网网桥. 第二台计算机(运行连接的另一端)直接连接到互联网. Cellsim 和第二台计算机从同一个千兆以太网交换机获取互联网服务.

我们测试了所有应用和协议(Skype, Facetime 等)的最新实时实现版本(2012 年 9 月), 它们运行在独立的较新型号 Mac 或 PC 上(图 6).

我们还向 Cellsim 添加了随机丢包功能, 以研究 Sprout 的丢包恢复能力. 在这里, Cellsim 根据指定的随机丢包率从队列尾部丢弃数据包. 这种方法以一种粗略的方式模拟了不具备深层数据包缓冲区的蜂窝网络(例如文献 [16] 中报道的 Clearwire). Cellsim 还包含一个可选的 CoDel 实现, 基于文献 [17] 中的伪代码.

4.3 SproutTunnel

We implemented a UDP tunnel that uses Sprout to carry arbitrary traffic (e.g. TCP, videoconferencing protocols) across a cellular link between a mobile user and a well- connected host, which acts as a relay for the user’s Internet traffic. SproutTunnel provides each flow with the abstraction of a low-delay connection, without modifying carrier equipment. It does this by separating each flow into its own queue, and filling up the Sprout window in round-robin fashion among the flows that have pending data.

The total queue length of all flows is limited to the re- ceiver’s most recent estimate of the number of packets that can be delivered over the life of the forecast. When the queue lengths exceed this value, the tunnel endpoints drop packets from the head of the longest queue. This algorithm serves as a dynamic traffic-shaping or active- queue-management scheme that adjusts the amount of buffering to the predicted channel conditions.

我们实现了一个 UDP 隧道, 利用 Sprout 在移动用户与连接良好的主机之间通过蜂窝链路传输任意流量(例如 TCP, 视频会议协议), 该主机充当用户互联网流量的中继. SproutTunnel 无需修改运营商设备, 即可为每个流提供低延迟连接的抽象. 它是通过将每个流分离到其独立的队列中, 并在有待发送数据的流之间以循环(round-robin)方式填充 Sprout 窗口来实现这一点的.

所有流的总队列长度被限制在接收端对预测周期内可交付数据包数量的最新估计值之内. 当队列长度超过该值时, 隧道端点会从最长队列的头部丢弃数据包. 该算法作为一个动态流量整形或主动队列管理方案, 根据预测的信道条件调整缓冲量.

Related Work

End-to-end algorithms. Traditional congestion- control algorithms generally do not simultaneously achieve high utilization and low delay over paths with high rate variations. Early TCP variants such as Tahoe and Reno [10] do not explicitly adapt to delay (other than from ACK clocking), and require an appropriate buffer size for good performance. TCP Vegas [4], FAST [12], and Compound TCP [20] incorporate round-trip delay explicitly, but the adaptation is reactive and does not directly involve the receiver’s observed rate.

LEDBAT [19] (and TCP Nice [21]) share our goals of high throughput without introducing long delays, but LEDBAT does not perform as well as Sprout. We believe this is because of its choice of congestion signal (one- way delay) and the absence of forecasting. Some recent work proposes TCP receiver modifications to combat bufferbloat in 3G/4G wireless networks [11]. Schemes such as “TCP-friendly” equation-based rate control [7] and binomial congestion control [1] exhibit slower trans- mission rate variations than TCP, and in principle could introduce lower delay, but perform poorly in the face of sudden rate changes [2].

Google has proposed a congestion-control scheme [15] for the WebRTC system that uses an arrival-time filter at the receiver, along with other congestion signals, to decide whether a real-time flow should increase, decrease, or hold its current bit rate. We plan to investigate this system and assess it on the same metrics as the other schemes in our evaluation.

Active queue management. Active queue management schemes such as RED [8] and its variants, BLUE [6], AVQ [14], etc., drop or mark packets using local indi- cations of upcoming congestion at a bottleneck queue, with the idea that endpoints react to these signals before queues grow significantly. Over the past several years, it has proven difficult to automatically configure the pa- rameters used in these algorithms. To alleviate this short- coming, CoDel [17] changes the signal of congestion from queue length to the delay experienced by packets in a queue, with a view toward controlling that delay, espe- cially in networks with deep queues (“bufferbloat” [9]).

Our results show that Sprout largely holds its own with CoDel over challenging wireless conditions without re- quiring any gateway modifications. It is important to note that network paths in practice have several places where queues may build up (in LTE infrastructure, in baseband modems, in IP-layer queues, near the USB interface in tethering mode, etc.), so one may need to deploy CoDel at all these locations, which could be difficult. How- ever, in networks where there is a lower degree of isola- tion between queues than the cellular networks we study, CoDel may be the right approach to controlling delay while providing good throughput, but it is a “one-size- fits-all” method that assumes that a single throughput- delay tradeoff is right for all traffic.

基于对论文 "Related Work" 部分的详细阅读, 以下是该部分核心内容的简要概括:

1. 端到端算法 (End-to-end algorithms) * 传统 TCP 变种 (如 Tahoe, Reno): 无法在速率剧烈变化的路径上同时实现高利用率和低延迟. 它们不显式适应延迟, 且依赖特定的缓冲区大小才能表现良好 * 基于延迟的 TCP (如 Vegas, FAST, Compound TCP): 虽然显式纳入了往返延迟 (RTT), 但其调整是反应式的 (reactive), 且未直接利用接收端观测到的速率 * 低延迟背景传输 (如 LEDBAT, TCP Nice): 虽然目标与 Sprout 一致(高吞吐且低延迟), 但 LEDBAT 性能不如 Sprout. 原因可能在于其选择的拥塞信号(单向延迟)以及缺乏预测机制 * 平滑速率控制 (如 TCP-friendly, Binomial): 虽然传输速率变化比 TCP 慢, 理论上可降低延迟, 但在面对速率突然变化时表现不佳 * Google WebRTC: 提出了一种使用接收端到达时间滤波器及其他信号的方案, 作者计划未来对其进行评估 2. 主动队列管理 (Active queue management, AQM) * 传统 AQM (如 RED, BLUE, AVQ): 通过在瓶颈队列处丢包或标记包来提示即将发生的拥塞. 但多年实践证明, 自动配置这些算法的参数非常困难 * CoDel: 为了解决参数配置难题和 Bufferbloat 问题, CoDel 将拥塞信号从队列长度改为数据包在队列中的停留延迟 * Sprout 与 CoDel 的对比: 实验显示, Sprout 作为纯端到端方案, 无需修改网关即可在恶劣无线条件下达到与 CoDel 相当的性能 * AQM 的局限性: * 实际网络路径中存在多个潜在的队列堆积点(如基带调制解调器, USB 接口等), 在所有位置部署 CoDel 难度很大 * CoDel 是一种"一刀切" (one-size-fits-all) 的方法, 假设所有流量都适用同一种吞吐量-延迟权衡, 而 Sprout 允许应用自主选择

Limitations and Future Work

Although our results are encouraging, there are several limitations to our work. First, as noted in §2 and §3, an end-to-end system like Sprout cannot control delays when the bottleneck link includes competing traffic that shares the same queue. If a device uses traditional TCP outside of Sprout, the incurred queueing delay—seen by Sprout and every flow—will be substantial.

Sprout is not a traditional congestion-control protocol, in that it is designed to adapt to varying link conditions, not varying cross traffic. In a cellular link where users have their own queues on the base station, interactive performance will likely be best when the user runs bulk and interactive traffic inside Sprout (e.g. using Sprout- Tunnel), not alongside Sprout. We have not evaluated the performance of multiple Sprouts sharing a queue.

The accuracy of Sprout’s forecasts depends on whether the application is providing offered load suffi- cient to saturate the link. For applications that switch in- termittently on and off, or don’t desire high throughput, the transient behavior of Sprout’s forecasts (e.g. ramp- up time) becomes more important. We did not evaluate any non-saturating applications in this paper or attempt to measure or optimize Sprout’s startup time from idle.

Finally, we have tested Sprout only in trace-based em- ulation of eight cellular links recorded in the Boston area in 2012. Although Sprout’s model was frozen before data were collected and was not “tuned” in response to any particular network, we cannot know how generalizable Sprout’s algorithm is without more real-world testing.

In future work, we are eager to explore different stochastic network models, including ones trained on empirical variations in cellular link speed, to see whether it is possible to perform much better than Sprout if a pro- tocol has more accurate forecasts. We think it will be worthwhile to collect enough traces to compile a stan- dardized benchmark of cellular link behavior, over which one could evaluate any new transport protocol.

(1) 局限性

• 无法控制外部竞争流量: 作为端到端系统, 如果瓶颈链路中存在共享同一队列的竞争流量(如传统的 TCP 流), Sprout 无法控制由此产生的排队延迟.
• 设计目标限制: Sprout 旨在适应变化的链路条件, 而非应对变化的交叉流量(Cross Traffic). 最佳性能通常通过将所有流量(批量和交互式)都封装在 Sprout 内部(如使用 Sprout Tunnel)来实现, 而非并行运行.
• 未评估场景: 尚未评估多个 Sprout 流共享同一个队列时的性能.
• 依赖链路饱和: 预测的准确性依赖于应用提供的负载是否足以使链路饱和. 对于间歇性或非高吞吐量的应用, Sprout 的瞬态行为(如启动时间)至关重要, 但本文未对此类非饱和应用进行评估或优化.
• 测试范围有限: 仅在基于波士顿地区 2012 年收集的 8 条蜂窝链路痕迹的仿真中进行了测试. 虽然模型未针对特定网络调优, 但在缺乏更多实际测试的情况下, 其普适性尚不可知.

(2) 未来工作

• 探索新模型: 计划探索不同的随机网络模型, 包括基于经验数据训练的模型, 以研究更准确的预测是否能进一步提升性能.
• 建立标准化基准: 认为收集足够的痕迹以建立蜂窝链路行为的标准化基准是非常有价值的, 可用于评估未来的新传输协议.

Conclusion

This paper presented Sprout, a transport protocol for real-time interactive applications over Internet paths that traverse cellular wireless networks. Sprout improves on the performance of current approaches by modeling varying networks explicitly. Sprout has two interesting ideas: the use of packet arrival times as a congestion signal, and the use of probabilistic inference to make a cautious forecast of packet deliveries, which the sender uses to pace its transmissions. Our experiments show that forecasting is important to controlling delay, providing an end-to-end rate control algorithm that can react at time scales shorter than a round-trip time.

Our experiments conducted on traces from four com- mercial cellular networks show many-fold reductions in delay, and increases in throughput, over Skype, Face- time, and Hangout, as well as over Cubic, Compound TCP, Vegas, and LEDBAT. Although Sprout is an end- to-end scheme, in this setting it matched or exceeded the performance of Cubic-over-CoDel, which requires mod- ifications to network infrastructure to be deployed.

本文提出了 Sprout, 一种专为跨越蜂窝无线网络的互联网路径上的实时交互式应用设计的传输协议. Sprout 通过对时变网络进行显式建模, 改进了现有方法的性能.

Sprout 包含两个核心理念:

1. 使用数据包到达时间作为拥塞信号

2. 利用概率推断对数据包交付进行谨慎的预测, 发送端利用该预测来调整其传输节奏

我们的实验表明, 预测对于控制延迟至关重要, 它提供了一种能够在小于一个往返时间(RTT)的时间尺度上做出反应的端到端速率控制算法.

我们在来自四个商用蜂窝网络的痕迹上进行的实验显示, 与 Skype, Facetime 和 Hangout, 以及 Cubic, Compound TCP, Vegas 和 LEDBAT 相比, Sprout 实现了延迟的数倍降低以及吞吐量的提升. 尽管 Sprout 是一种端到端方案, 但在该实验环境下, 其性能匹配甚至超过了 Cubic-over-CoDel, 而后者需要修改网络基础设施才能部署.