提高通信网络中延迟的巴蒂斯特·琼列兹引用此版本：巴蒂斯特·琼格莱斯。提高通信网络中延迟的端到端机制网络与互联网架构[cs.NI]。格勒诺布尔阿尔卑斯大学[2020-...]，2020.英语。NNT：2020GRALM048。电话：03120529HAL ID：电话：03120529https://theses.hal.science/tel-03120529提交日期：2021年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire论文要获得的等级格勒诺布尔阿尔卑斯大学博士专业：计算机科学部长令：2016年提交人巴蒂斯特·J·昂列兹论文由Martin HEUSSE指导由Bruno GAujal共同执导在格勒诺布尔计算机科学实验室编写在用于改善通信提高通信网络中延迟的端到端机制论文于2020年10月23日在评审团面前公开答辩，评审团成员包括：马丁·H·尤瑟格勒诺布尔INP大学教授，论文主任Bruno GAujalInria HDR研究总监，论文安德烈-吕克·B·埃洛先生图卢兹INP大学教授-ENSEEIHT，报告员纪尧姆·尤·鲁瓦-K·埃勒蓝色海岸大学大学教授伊莎贝尔·G·乌林·拉苏夫人里昂第一大学教授，校长安娜·B·伦斯特罗姆瑞典卡尔斯塔德大学教授，考官i摘要在过去的几十年里，支撑互联网的网络技术有了显著的发展，但网络性能的一个方面仍然相对不变：延迟。在过去的25年里，传输技术的典型容量或带宽增加然而，延迟是有严格限制的，例如传播延迟，其最终受到光速的限制。容量和延迟之间的这种不同演变对协议设计和性能具有深远的影响，尤其是在传输协议领域。这间接导致了缓冲区问题，其中路由器缓冲区持续满，增加了延迟甚至更多。此外，最终用户的需求也发生了变化，他们希望应用程序的响应速度更快。因此，需要新的技术来减少终端主机所经历的延迟与"基础设施"机制相反，本论文旨在通过使用端到端机制来减少所经历的延迟提出了两种端到端机制第一种方法是将多个消息或数据流多路复用到单个持久连接中。这允许更好地测量网络条件（延迟、分组丢失）;反过来，这允许更好的适应，如更快的重传。我将此技术应用于DNS消息，在数据包丢失的情况下，它显著提高了端到端延迟。然而，取决于所使用的传输协议，消息可能会受到Head-of-Line阻塞的影响：此问题可以通过使用QUIC或SCTP而不是TCP来解决。第二种提出的机制是利用多个网络路径（例如Wi-Fi、有线以太网、4G）。其思想是对延迟敏感的网络流量使用低延迟路径，而批量流量仍然可以利用所有路径的聚合容量。多路径TCP部分实现了这一想法，但它缺乏对多路复用的支持。添加多路复用允许数据流协同工作，并确保调度程序更好地了解各个数据流的需求 这实际上导致了最近在文献中才被确定为"流感知多路径调度"的调度问题。 我的第一个贡献是对这个调度问题进行建模。作为第二个贡献，我提出了一个新的流感知多路径调度程序，SRPT-ECF，它提高了小流的性能，而不影响大流。此调度程序可以作为MPQUIC（多路径QUIC）实现的一部分实现更一般地说，这些结果为工作流之间的协作开辟了新的机会，应用程序可以改进WAN聚合。iii摘要使互联网发挥作用的网络技术自诞生以来已经发展了很多，但网络性能的一个方面几乎没有发展：延迟。在过去的25年里，物理层的可用吞吐量增加了5个数量级，而延迟几乎没有改善一个数量级。 延迟确实受到诸如光速之类的强物理约束的限制。吞吐量和延迟的这种差异化演变对协议的设计及其性能有很大的影响，尤其是对TCP等传输协议特别是，这种演变间接地导致了"缓冲区膨胀"现象，这种现象填满了路由器的缓冲区，此外，用户对高响应应用程序的需求也在不断增长因此，有必要本论文的目的是通过使用端到端机制（而不是网络基础设施机制）来减少延迟。提出了两种端到端机制。第一种方法是在单个持久连接中多路复用多个消息或数据流。 这使得可以更精确地测量网络条件（延迟、分组丢失）并更好地适应它们，例如通过更好的重传。 但是，当使用TCP等协议时，可能会发生降低性能的联机阻塞现象。 可以使用QUIC或SCTP来克服这个问题。提出的第二种机制是利用多个路径，例如Wi-Fi、有线连接和4G。 多路径TCP在一定程度上实现了这一思想，但没有考虑多路复用。 集成多路复用为调度程序提供了对数据流需求的更大可见性，并将允许它们进行协作。最后，我们得到了一个最近才发现的调度问题，"流敏感多路径调度"。我的第一个贡献是对这个问题进行建模。我的第二个贡献是为这个问题提出了一个新的调度算法该算法可用于MPQUIC（多路径QUIC）的实现中更一般地说四这些结果为数据流之间的合作以及互联网连接的透明聚合等应用开辟了新的前景v谢谢你这篇论文在很大程度上要归功于我有幸与我的两位论文导师Martin Heusse和BrunoGaujal进行的丰富和建设性的交流他们给了我必要的时间定期与这三个人会面，然后让我把这些想法付诸实践。虽然他们不同的专业领域并感谢Sinan Birbalta，感谢Maciej Korczynski和Yevheniya Nosyk让"源地址验证"产生了很好的结果：我发现参与这个项目很有趣，我也很喜欢能够在我的主要论文主题卡住的时候从事另一个主题的工作在我的论文中，我花了近400个小时的教学时间，当然，我与Ensimag的同事们进行了大量的合作：除了Martin Heusse，还要感谢Roland Groz、Andrzej Duda、Olivier Alphand 、 Franck Rousseau 、 Grégory Mounié 、 Matthieu Moy 和Frédéric Wagner给了我合作的机会。更不用说Ensimag的行政服务以及我经常要求的IT服务了。我还要感谢巴黎狄德罗大学的Juliusz Chroboczek和Matthieu Boutier，感谢他们在同样，我也很感谢里昂高等师范学校的"通过和为研究"培训，并给了我机会继续这一学术冒险与在我的整个论文过程中，我的两个核心团队Drakkar和Polaris的同事对丰富的团队生活和对与我不同的研究课题的开放性至关重要 特别感谢Takwa、Ulysses、Henry、Timothy、Pierre和Etienne在这几年里进行了大量令人兴奋的讨论。也感谢vi感谢格勒诺布尔计算机实验室的管理人员最后，感谢我的家人在这个项目中支持我，尽管距离很远，也感谢Oriane这些年来一直陪伴着我，特别是在我写作的最后，她和一位博士生一起在禁闭中幸存下来。vii内容摘要I摘要三感谢v内容七1引言11.1现代通信网络中的11.1.1体验延迟21.1.2延迟对应用21.2减少延迟41.2.1提高延迟的基础架构机制41.2.2提高延迟的端到端机制51.3多宿主和多路径通信61.3.1通过多宿主减少延迟71.4方法论81.5贡献概述91.5.1通过更好的路由减少91.5.2持久DNS连接101.5.3流感知多路径调度111.6大纲122解析端到端延迟132.1网络中的终端主机延迟源132.2在连接上多路复用消息152.2.1对应用数据多路复用的152.2.2面向消息的语义16面向消息的语义中的多路复用2.2.3面向流的语义18流定向语义中的多路复用viii2.2.4混合语义：HTTP19HTTP/120中的多路复用HTTP/2中的多路复用212.3多路复用的性能影响212.3.1分摊费用212.3.2反应性和缓冲区管理222.3.3传输层23处的线路头端阻塞2.3.4消息捆绑242.4多宿主延迟的252.4.1导致延迟增加的多宿主挑战线路头端阻塞26接收窗口阻止26短流量262.4.2多路径调度提供的机会272.5结论282.5.1多路复用292.5.2多宿主303持久DNS连接313.1DNS：性能要求和传输协议313.2消息丢失极大地影响了DNS对UDP的延迟3.3通过持久连接改善DNS延迟353.3.1实验验证363.3.2相关工作433.3.3超越延迟453.4递归DNS解析器性能评估463.4.1对持久连接的需求3.4.2部署模型：大规模持久DNS连接。473.4.3实验设置和方法473.4.4方法：绩效指标483.4.5结果493.4.6方法的局限性53查询生成模型53DOT和DoH之间的差异53新TLS连接的流失和成本3.5结论54ix4流感知多路径调度574.1流多路复用和调度的背景574.1.1从单流到多流运输：历史视角4.1.2调度多路复用流614.2多流调度模型64SCTP66的适用性QUIC67的适用性HTTP68的适用性4.3流感知多路径调度694.3.1具有多个流的多路径调度流调度69路径分配714.3.2MPTCP调度程序的缩短71MPTCP调度的短消息：在发送方序列化71MPTCP交付的短消息：在接收方序列化724.3.3流感知多路径调度程序73<循环赛>-MinRTT>74<循环赛>-ECF>74<循环-单路径>75<粘性循环-单路径>75<顺序>-ECF>76-ECF>764.4ECF：单个消息的多路径调度4.4.1网络模型774.4.2ECF77的完成时间4.5SRPT-ECF：最佳流感知多路径调度4.5.1示例804.5.2SRPT-ECF81的特性4.6在线运行SRPT-ECF824.6.1在线SRPT-ECF算法834.6.2与离线算法的844.7SRPT-ECF85的基于痕量的评价4.7.1方法论854.7.2模拟代码864.7.3结果874.8实际考虑89x4.8.1处理网络可变性和不确定性894.8.2拥塞控制：起搏与 拥塞窗口..............................................................90起搏90经典拥塞窗口90起搏和调度914.8.3缓冲策略914.8.4流媒体用例和无限消息924.9结论925结论955.1前景975.1.1处理测量不确定性975.1.2细流和批量传输通信之间的更多合作985.1.3WAN聚合99改进WAN聚合1015.1.4多路径102的大规模影响参考书目105图117列表表列表1211引言11.1 现代通信网络多年来，互联网发生了重大变化：新服务的推出，移动和无线使用的爆炸式增长，公共技术的传输容量--Wi-Fi网络或互联网连接的带宽--在25年内增长了5个数量级。然而，延迟是通信网络的一个方面，由于强大的物理约束，它保持相对不变。已经进行了改进，但与容量的增长相比，改进的幅度要小得多：1987年，ARPANET网络的典型延迟大约是340毫秒的往返时间（RTT）。今天，穿越美国大陆的典型往返时间约为60毫秒：在这个特定的例子中，延迟在33年内的改善不到一个数量级。延迟有很大的限制，例如传播延迟，其最终受到光速的限制。由于延迟停滞导致容量和延迟之间的不平衡，因此出现了新的问题。带宽延迟产品（BDP）越来越大，基本上与网络容量的增加相匹配。因此，在小BDP环境中设计的传统拥塞控制算法难以适应高BDP环境，并且不能利用高容量路径的优势 这导致了用于TCP的更积极的拥塞控制算法的开发，例如Cubic [37]或BBR [14]。这些新算法可以在高容量路径上提供完全预期的吞吐量;然而，它们也会导致显著的拥塞量。 这种拥塞反过来会增加排队延迟，从而增加总的延迟量。事实上，立方体很可能是造成或至少暴露缓冲区的原因[2，48]。这促使人们努力减少延迟，这可以通过许多不同的方式来实现。本研究的重点是通过端到端机制减少延迟。10第一章引言1.1.1 体验到延迟在这项工作中，我主要对应用程序所经历的总体延迟感兴趣。应用程序在终端上运行，也称为终端主机（笔记本电脑、移动电话、连接设备）。... ... ）。它通过网络与远程应用程序通信：此远程应用程序通常在一个服务器上运行，但在使用对等协议时，它也可以在另一个终端上运行。总的来说，延迟包括由网络本身引起的延迟，以及在终端主机（缓冲区、传输协议、操作系统）中引起的延迟。近似总延迟的一种简单方法是测量往返时间（RTT）。这可以通过发送一个小数据包来完成，该小数据包将到达目的地主机，并立即触发一个小数据包作为响应。 这就是类似ping度量的工具。然而，这种技术测量忽略了来自传输协议、来自操作系统和应用程序之间的移动数据或来自远程主机上发生的数据处理的延迟。 为了获得更准确的测量，必须测量本地应用程序和远程应用程序之间的总体延迟。1.1.2 延迟对应用程序延迟正在成为许多应用程序的新性能这对于诸如虚拟现实（VR）之类的新交互式应用VR需要用户运动和相应视觉反馈之间的低端到端延迟，有时称为 如果此延迟太高，用户可能会体验到电机性能受损，甚至感到恶心或头痛。对于头戴式显示器，最大可接受端到端延迟范围为50-75 ms [1，106]至15-20 ms [24，70]。当通过通信网络远程完成图形渲染时，必须在如此紧的延迟预算内执行许多步骤：运动传感器采集、往返网络通信、图形渲染和显示更新。即使使用最先进的设备进行其他步骤，这也只为网络通信留下了14到40毫秒的延迟预算涉及批量数据传输的传统应用程序（如Web应用程序）也会受到延迟的严重影响 当通过高容量网络传输少量数据时，传输时间由两个因素控制：初始化阶段（例如，TCP的三方握手），以及用于探测可用容量和避免拥塞的慢启动机制。两个因素都直接31.1现代通信网络与端到端延迟相关：当延迟变高时，从连接的远程端接收反馈所需的时间更长例如，使用40毫秒的RTT和4380字节的初始窗口，TCP的慢启动算法在理想条件下需要10-11个往返才能爬升在前10个回合中，仅传输了4.3 MiB的数据，平均吞吐量为90Mbps。此示例表明，在存在中等延迟的情况下，几兆字节的独立传输无法实现1Gbps的吞吐量。更一般地说，应用程序的通信模式可以分为两类：[85]通过点绑定通信或"贪婪流"：在这一类中，应用程序几乎总是有更多的数据要发送。因此，吞吐量通常受到TCP拥塞窗口的限制这类通信的特征在于大分组大小和高分组速率。主要用例是批量数据传输，例如下载或上传文件。在此类别中，应用程序只能发送零星数据。 其特征在于小分组大小、宽分组到达间隔时间和低分组速率。 这包括在线游戏、即时消息、IP语音、DNS等应用程序，更一般地说，还包括通过一系列小消息或请求/响应进行通信的任何应用程序。这一区别对选择适当的指标来研究绩效具有重要意义 对于吞吐量绑定通信，主要度量是有效吞吐量，其可以替代地测量为每个批量传输的完成时间：平均吞吐量是总大小除以完成时间。即使这些应用程序是以吞吐量为导向的，完成时间仍然取决于延迟，正如我们在上面的小型计算中所看到的那样。 完成时间通常是RTT的倍数。在第4章中，我优化了可能传输大量数据的单个流的完成时间。对于细流通信，主要度量是每个单独消息（可以是请求、响应或具有任何其他语义的消息）的延迟。由于消息通常很小，因此传输时间通常可以忽略不计：在这种情况下，总延迟由来自网络的延迟源（如传播延迟或排队延迟）支配。例如，我使用第3章中的延迟度量来评估DNS的性能DNS显然是一个稀疏的流应用程序，因为它使用较小的请求和响应，并需要较低的数据包速率。4第一章引言100Mbps请注意，根据网络条件（容量、延迟），同一应用程序可能属于一个类别或另一个类别。例如，如果网络容量足够大，则发送大小为50 KB的常规消息可以被视为稀疏流。 在100Mbps链路和40ms RTT的情况下，假设完美的拥塞控制和无丢失，发送消息和接收确认需要44ms 1，这接近RTT。然而，在具有40ms RTT的1Mbps链路上，传输相同的消息将需要440ms。 由于它需要几个RTT，因此它成为一种基于路由的通信。总体而言，随着网络容量的增加，应用程序往往会受到更多延迟的限制。 因此，对于许多应用程序来说，延迟已成为具有挑战性的性能瓶颈。1.2 减少延迟此工作的目标是减少终端主机经历的总体延迟延迟的来源有很多，因此有很多可能的方法来减少延迟。 Briscoe等人在一项综合调查中总结了这些来源和可能的补救措施。[12] 根据本介绍，可以将减少延迟的可能方法松散地分为两大类：基础架构机制和端到端机制。下面将简要介绍这两个系列，而第2章将进一步详细介绍端到端机制。1.2.1 提高延迟第一个可以提高延迟的机制家族是基础设施机制，即终端主机无法直接访问的任何机制这包括对互联网结构或其支持技术的任何改进例如，改进Internet路由以提供更短的地理路由是可能的。 这可以通过仔细配置BGP路由策略或通过开发本地对等点（Internet交换点或IXP）来完成。 这影响了网络的结构。1传输延迟为4ms=50KB* 851.2减少延迟还可以通过缓存或CDN（内容交付网络）将内容更接近用户。即使在未来，也有人提议将计算能力更接近用户（边缘计算）。更好的技术可以更好地提高延迟：与冰冷的数字用户线（恶人线）相比，FTTH（光纤到户）提供了更低的本地环路延迟，因为它使用不太复杂的机制来克服噪声和干扰-例如，冰冷的通常实现了一种交错机制来减轻噪声突发，从而增加了传输延迟。作为另一个例子，低地球轨道卫星系统（LEO）提供比地球静止轨道上的通信卫星低得多的传播延迟。一个这样的低地球轨道系统StarLink最近在美国大陆证明了30毫秒的端到端延迟相比之下，通过地球静止卫星的典型端到端延迟约为600毫秒。考虑到端到端延迟的巨大差异和对较低延迟的普遍需求，低地球轨道卫星系统的部署速度很快就不足为奇了。最后，主动队列管理（AQM）可以在ISP管理的路由器中使用，以便在拥塞的情况下更好 这可以帮助避免缓冲区[42]。所有这些机制都必须由ISP或基础架构提供商部署一旦部署，它们就可以通过一次影响许多客户而产生重大影响。但它们往往需要大量的时间和资金来部署，这可能会限制它们的使用。1.2.2 提高延迟的第二类由端到端机制组成，即主要在终端（计算机、智能手机）中实现的机制... ... ）。这些机制可以通过软件更新或配置更改相对容易地部署，尽管实现大规模滚降可能需要相当长的时间。在终端主机的操作系统中可以找到许多可以减少延迟的机制：网络接口卡的驱动程序、缓冲区管理、传输协议实现或参数。... ... 应用程序还可以使用一些机制：例如，选择适当的传输协议或适当的传输协议选项，在不阻塞的情况下管理事件。... ... 最后，利用多宿主来降低延迟是一种横向机制，可以在操作系统或应用程序中单独完成。6第一章引言总的来说，这两个机制家族（基础设施和端到端）是互补的。例如，在当前的互联网中，更好的路由只能在基础设施中完成，而利用多宿主只能在端到端进行。利用端到端机制是本工作中采用的主要这些机制易于部署并与互联网的端到端模型相匹配在互联网中，大多数智能都位于网络的边缘1.3 多宿主和多路径通信由于连接选项的广泛可用性，多路径传输协议在过去几十年中已经出现。同时访问多个网络连接非常常见：家庭Wi-Fi、雪地Wi-Fi、移动连接、光纤、DSL。... ... 这被称为多宿主情况，如图1.1所示。终端主机设备物理连接到多个网络，并且可以利用这些连接点来使用多个路径与目的地通信。设备可以根据各种指标动态选择其将用于通信的路径：移动数据的货币成本、预期性能、测量的实时性能、物理信号电平等。当使用诸如Multipath TCP[88]或CMT-SCTP[49]之类的多路径感知传输协议时，甚至可以同时使用两个路径并在它们之间进行负载平衡以优化性能度量。图1.1多宿主情况下的终端主机设备（智能手机）71.3多宿主和多路径通信多宿主连接也可以从宿主路由器利用，如图1.2所示。在这种情况下，终端主机设备连接到单个家庭路由器，该路由器本身连接到多个网络。 这是IETF [4]特别是家庭网络组[17]中考虑的多宿主模型。在此模型中，本地网络使用由ISP委托的IP地址空间运行多个并行寻址方案，每个上游ISP一个。因此，设备可以通过在其传出数据包中设置适当的源地址来选择要使用的网络。或者，可以使用网络地址转换（NAT）将对要使用的路径的所有控制委托给家庭路由器：此设置称为SD-WAN（软件定义的广域网）。图1.2另一种多路径网络是一个更通用的概念。例如，多路径是现代数据中心网络的基本组件，用于在服务器对等体之间提供冗余路径类似地，大规模网络运营商利用其核心网络中的多个路径来实现负载平衡流量并应对故障。然而，由于这项工作主要集中在终端用户设备上，而不是在核心网络中，我将不考虑这些情况。1.3.1 通过多宿主多宿主提供的各种连接选项已在以下几种方式中得到利用：1. 通过聚合多个网络路径的容量来提高吞吐量;
