无丢失网络拥塞管理关键技术研究

(申请清华大学工学博士学位论文)二〇二二年五月inpartialfulfillmentoftherequirementforthedegreeofDissertationSupervisor:ProfessorRenFe清华大学拥有在著作权法规定范围内学位论文的使用权，其中包括1）已获学位的研究生必须按学校规定提交学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的学位论文2）为教学和科研目的，学校可以将公开的学位论文作为资料在图书馆、资料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内容；（3）根据《中华人民共和国学位条例暂行实施办法》及上级教育主管部门具体要求，向国家图书馆报送相应的学位论文。I近年来分布式存储、高性能计算和数据中心在线数据密集型应用等更多具有严格要求的应用场景涌现，展现出对网络无丢失特性的需求增强的趋势。主流的必要的，近年来获得了工业界和学术界很大关注。本论文针对拥塞管理的拥塞探测与识别问题、链路层流量控制与端到端拥塞控制的交互问题展开研究工作，取（1）提出了无丢失网络的三元拥塞探测机制。通过重新认识链路层流量控制的定义，通过建模得到状态转换条件，为主流无丢失网络设计了交换机三元拥塞确识别拥塞流以及仅受到逐跳流量控制影响的流。案例研究表明，现有的拥塞控（2）提出了基于三元拥塞探测的无丢失以太网拥塞控制机制。数据中心无丢失以太网拥塞控制需要满足的属性包括快速收敛、与PFC有良好的交互以及满足入源停止状态快速排空因超发而积压的队列，从而保持低排队时延而不牺牲吞吐量。实验结果表明，使用简洁有效的拥塞信号和针对性的调速策略，ACC能极大出了兼容InfiniBand拥塞控制框架的拥塞控制机制RRCC。核心思想包括接收端驱动的拥塞识别和接收端驱动的速率调节。接收端利用观察到的流量标记模式准确识别拥塞流和拥塞无关流，利用数据接收速率显式控制发送端的减速。实验结AbstractInrecentyears,moreapplicationscenarioswithstrictrequirementshaveemMainstreamlosslessnetwrlineblockingandunfairness.Therefore,congestionmanagementinlosslessnetworksisthesisstudiestheproblemofcongestionmanagementincludingcoidentification,theinteractionbetweenlink-layerflowcontrolandend-to-endcocontrolmechanism.Thisthesisachievesthefollowingcontrssnetworks.Byre-understandinrflowcontrol,wedefineternaryportstates(congestedstate,uncongesterminedstate)inlmodelingandproposeTernaryCongestionDetbylink-layerflowcontrol.CasestudiesshowtcancooperatewithTCDtoenhancerateadcompletiontimeperformance.PFC,andsatisfyingthedemandoflowlatencyandhighthroughputlightoftheabovepropertirivalrateofACKstodirectlyguidepropertythatdatapacketsandACKsareneverlostciseandeffectivecongestionsignalandtailorealleviatethehead-of-lineblockingproblem.ACCachievesbetterflowcompletiontimeperformancethantheexistinghighmentalproblemsthatleadtothepoorperformanceofIBCCandthedifficultyofprac-ticaldeployment.WeproposeacongestionccompatiblewiththeInfiniBandcongestionreceiver-drivencongestionidentificationandreceiver-drivenrateadjustment.Rutilizetheobservedmarkingpatternofflowstoaccuratefromcongestion-unrelatedflows.Receiversalsoexplicitlyisinthesenderbymeansofthereceivingrate.ExtRmessagecompletiontime.RRCCdoesnotneedtomodifyInfiniBandswitchegooddeployability.Keywords:Losslessnetworks;congestiondetection;congesti IAbstract X 1 1 1 2 3 4 4 5 6 7 7 8 9 10 10 10 12 13 13 14 16V 18 18 19 20 20 23 25 25 27 29 30 31 33 33 35 41 41 43 434.2无丢失以太网拥塞控制需要 44 46 51 51 51 57 60 60 61 61 62 66 69 71 71 72 72 73 74 74 76 78 78 78 79 82 83 84 85 85 86 88 90 90 91 93 102 103 104 106 107 3 5 6 16 19 20 21 22 24 25 27图3.8Ton随ε、Rd的变化 29 30 31 32 34 35 36 36 37 38 39 40 40 46图4.2F0为受害者流时各端口队列占用情况（减速函数为f1） 47图4.3F0为受害者流时各端口队列占用情况（减速函数为f2） 47图4.4F2为受害者流时各端口队列占用情况（减速函数为f1） 48 49 50 51 52 55 56 58 62 63 64 65 66 66 67 67 68 68 69 74 75 76 77 79 80 83 84 85 86 88 88 17 26 27 36 57 66 75XCEERDMA远程访问内存技术（RemoteDirectMemoryAccess）HPC高性能计算（HighPerformanceComputing）IBTAInfiniBand行业RoCE基于聚合以太网的RDMA（RDMAoverConvergedEthernet）DCB数据中心桥接（DataCPFC优先级流量控制（PriorityFlowCBFC基于信用的流量控制（CreditECN显式拥塞通知（ExplicitCongestionNotificatioINT带内网络遥测（In-bandNetworkTelemetry）CP拥塞点（CongestionPoint）NP通知点（NoRP反应点（ReactionPoint）CE经历拥塞态（CongestionUE经历待定态（UndetermQoS服务质量（QualityASIC专用集成电路（ApplicationSpecificBDP带宽时延积（BandwidthDelayProduct）VOQ虚拟输出队列（VirtualOutpuToRMPI消息传递接口（MessagePassingInCNP拥塞通知包（CongestionNotificationPacket）BECN后向拥塞通知（BackwardExplicitCongestionNotification）FECN前向拥塞通知（ForwardExplicitCongestion1近年来，更多具有严格要求的应用场景展现出对网络无丢失特性的需求。例长时间的超时可能导致iSCSI传输几乎停止[1]。在高性能计算（HighPerformance低延时也日益成为关键的性能指标，任何网络延时的增加都会直接转化为更长的应用完成时间。在数据中心中，数据包丢失会对应用程序性能造成严重损害。例如，丢失导致的超时等待时间会极大损害时延敏感业务的完成时间[3-4]；0.1%的丢包率会降低25%批量数据传输的吞吐量[5]。因此，无丢失网络逐渐兴起并成为重要的基础设施。在本文中，无丢失网络指在正常情况下数据包不会因网络中交换机缓存溢出而被丢弃的交换网络。目前两类主流的无丢失网络是应用于数据中心的无丢失以太网和高性能计算领域的InfiniBand。本节首先介绍这两类无丢失网络的相关背景，然后介绍无丢失网络以太网凭借成本低、操作简单和兼容性广的优点，一直是局域网的首选网络的理念也导致需要为一些具有更严格要求的应用单独设计专用网络。例如在多种业务需求下，通信基础设施就需要包括多个不相交的网络：使用以太网技术的局域网、使用FibreChannel技术的存储区域网和使用InfiniBand技术的高性能计算但是，现代数据中心已普遍采用了在传统互联网中占主导地位的以太网。鉴的能力使之成为一个统一的交换结构，从而取代传统的为特殊需求设计的各个独具有显著的性能、成本和管理优势。CEE在链路层开发了逐跳的优先级流量控制2交换机入端口在队列缓存溢出之前发送信令通知上游端口停止发送数据，在队列长度降低之后发送信令通知上游端口恢复数据包的发送，以确保不会因缓存溢出需要内核的参与，传输协议栈卸载到网卡上，数据直接从一个主机系统的存储区快速传输到另外一台远程主机的存储区。与基于软件的TCP/IP网络协议栈相比，RDMA硬件卸载和旁路内核的特性显著降低了CPU开销和整体延时。例如，使RDMA的数据传输只有在没有数据包丢失时才能达到其最佳性能[8]。因此，近年目前，可扩展的无丢失以太网具有很大的应用前景，是构建下一代数据中心集群中有70%部署了InfiniBan持了无丢失的特性，采用基于信用的链路层流量控制（CreditBasedFlowControl，共享单个物理链路的独立逻辑通信链路。下游交换机入端口VL的可用缓存大小以信用值的形式发送在信令中通知给上游端口，上游端口VL按照信令中的信用需要特殊的网卡通道适配器（ChannelAdapter，CA）和交换机，支持以子网为单3队头阻塞⽆辜流拥塞流队头阻塞79理想分配：四条流均为C/41346791无丢失以太网和InfiniBand均使用链路层的流量控制机制来保证网络的无丢失特性。但是，链路层流量控制也带来了一些附带损害。链路层流量控制工作在当均分瓶颈链路带宽，即各分得c/4。但是，由于链路层流量控制不能区分4进入停滞状态，极大降低传输性能[5,15-17]。由于在无丢失网络中仅使用链路层流量控制存在以上所述的问题，有效的拥塞管理是必要的。当输入流量速率超过链路容量时，网络中发生了拥塞。无丢失网络的拥塞管理旨在进行流级别的速率控制，缓解以及消除网络中的拥塞，避免链路层流量控制的持续触发。无丢失网络的拥塞管理近年来成为学术界和工业界了InfiniBand拥塞控制机制[14]；微软、谷歌和阿里巴巴等工业界公司都提出了适用于无丢失以太网的拥塞控制机制[7,18-19]。在拥塞管理架构中，首先需要拥塞探测探测到网络中拥塞的出现。探测拥塞的同时进行拥塞识别，确定造成拥塞的拥塞流。如果是网络内交换机负责实施拥塞探测与识别，还需要拥塞通知将拥塞相关的信息通知给源端主机。最终，源主拥塞探测问题：无丢失网络的链路层流量控制生效时，会对网络中交换机端口状态产生影响，给无丢失网络的拥塞探测带来了新的问题。当网络中突发流量到达产生队列累积时，链路层流量控制会被触发以避免丢包，上游的交换机端口比缓存溢出即丢弃数据包的传统网络，无丢失网络中的交换机端口产生队列累积5因此，无丢失网络的拥塞探测需要能够正确认识链路层流量控制机制影响下交换机的多种端口状态，给出明确的辨别规则，探测出不同状态的转换。不能正确探测出不同状态将直接导致拥塞流量的识别错误，进一步造成端到端拥塞控制拥塞流识别问题：在交换机端口存在多元拥塞状态的情况下，对于端到端拥1.2.2链路层流量控制与端到端拥塞控制的交互问题在无丢失网络中，端到端拥塞控制与逐跳的链路层流量控制二者之间的关系如图1.2所示。二者是相互依存、相互补充的。一方面，当发生瞬时拥塞时，端到显然，端到端拥塞控制与链路层流量控制之间会存在交互行为。二者交互的根本6①拥塞探测与识别基于交换机直接探测识别基于接收端统计间接识别②基于发送端的拥塞控制机制研究(无丢失以太网)③接收端驱动的拥塞控制机制研究(InfiniBand)①拥塞探测与识别基于交换机直接探测识别基于接收端统计间接识别②基于发送端的拥塞控制机制研究(无丢失以太网)③接收端驱动的拥塞控制机制研究(InfiniBand)拥塞探测拥塞探测与识别问题速率调节速率调节问题（1）端到端拥塞控制与链路层流量控制的控制周期不同。端到端拥塞控制的小于端到端的往返时间。例如，在现代数据中心中，单跳链路的往返时间通常只拥塞发生时，拥塞控制算法需要多个RTT才能收敛到合适速率。这二者的交互可能产生不良后果。一方面，当拥塞发生，交换机队列长度未快速降低时，链路层流量控制可能被持续触发，随着数据包的积压，链路层流量控制会沿着途经的交换机逐跳后压，导致了拥塞扩展，甚至会波及网络的大部分交换机和链路；另一方面，链路层流量控制被持续触发后，数据包在交换机队列中的堆积会对拥塞探测产生影响，交换机探测出的端口状态（或端主机感知到的拥因此，需要正确认识二者的动态交互过程以及产生的影响，合理设计端到端拥塞本文针对以上问题进行了三个方面的研究，具体的研究内容如图1.3所示。首先，针对拥塞探测与识别问题，分为基于交换机直接探测识别和间接识别拥塞流两大研究路线，基于交换机的直接探测识别旨在增强交换机的能力，实现准确的拥塞状态探测，进而通过拥塞通知直接将拥塞流信息通知给端主机；间接识别拥塞流旨在兼容已有交换机拥塞探测机制，端主机借助其他特征识别出拥塞流和拥7塞无关流，为端到端拥塞控制提供准确的拥塞识别能力。进一步针对端到端拥塞的拥塞探测与识别机制，进行基于发送端的拥塞控制机制研究和接收端驱动的拥针对交换机拥塞探测与识别问题，本文通过在单拥塞点场景和多拥塞点场景中，现有的拥塞探测机制因为没有正确认识到逐跳流量控制和交换机拥塞探测行为之间的相互作用，会造成错误的拥塞探测结果。本文重新认识和定义了无丢失的端口是受到了逐跳流量控制影响的端口，并不是当前拥塞真正发生的端口。本文通过构建模型给出了三元状态的转换条件，在此基础之上，为主流无丢失网络TCD利用端口发送模式和队长演化特征探测三元状态，仅需要交换机支持基试床和大量的仿真实验表明，TCD可以准确地探测出拥塞端口并识别出导致拥塞算法中的速率调节配合，以增强拥塞控制算法的决策。案例研究表明，现有的拥塞控制算法通过与TCD结合可以实现3.3倍更好的中值流完成时间放基于三元拥塞探测机制TCD，本文探索设计了适用于大规模无丢失以太网的包括快速收敛，在发生队头阻塞时与PFC有良好的交互，以及需要满足数据中心塞无关的受害者流：通过一系列实验发现，对受害者流限速的具体效果与受害者速3）如何处理网络中同时存在的多个拥塞点以保证公平合理的带宽分配：多8塞标记来捕获流状态、利用ACK的到达速率来指导拥塞流减速以及根据A列信息在发送端施加一个源停止状态。引入的源停止状态可以快速抑制拥塞流导拥塞流以新的速率恢复发送。ACC中ACK驱动的速率调节和源停止状态都充分效的交换机拥塞信号和更有针对性的速率调节策略，A基于传统信号ECN和RTT的拥塞控制算法，并且优于目前高精度和高代价的拥包的排队延时并损害了应用程序完成时间。IBTA组织制定的InfiniBand规范中提问题，并在一些商用交换机中得到支持。如今，HPC集群越来越多地通过共享的网络架构运行各种工作负载，导致不同应用的消息传输共存在网络中，为IBCC带来了很大挑战。本文通过在典型的混合流量场景下细粒度的实验观察，揭示了IBCC的几个基本问题，包括忽视链路层流量控制信用更新的周期性导致的拥塞流误识别，基于预设速率表的逐步调节导致的慢收敛和不灵活，以及增速过程需要大量参数调优。本文认为正是上述的基本问题使得实际系统中IBCC的性能不端点上的两个关键机制：接收端驱动的拥塞识别和接收端驱动的速率调节。采取间接识别拥塞流的思路，利用接收端视角下不同流量的标记模式特征，RRCC可以准确区分出拥塞流和拥塞无关流。借助于接收端观察到的数据接收速率，接收端显式发送控制信令指导发送端的减速过程。RRCC能够在一个控制周期内消除9全文总共分为6章，后续章节的组织结构如下：第2章对本文的相关工作进行了总结。第3章针对无丢失网络的拥塞探测与识别问题，为主流无丢失网络设计实现了三元拥塞探测机制TCD。第4章针对数据中心应用的需求，设地处理速率调节与PFC之间的交互等一系列问题，并且实现低延时和高吞吐量的制定的拥塞控制框架设计了接收端驱动的拥塞控制机制RRCC。最终，第6章对拥塞探测是拥塞管理中基础的研究问题。由于无丢失网络中现有的拥塞探测网络和主流无丢失网络的拥塞探测相关研究进行综述。在拥塞探测基础上，目前交换机根据平均或即时的队列长度探测拥塞的出现，并执行数据包丢弃或者标提出根据瞬时队列长度是否超过阈值探测拥塞和标记ECN。通常单比特的数据包标记旨在使端主机的传输层做出响应，但一些拥塞控制机制建议端主机可以根据有当标记数据包的比例超过某个参数时，端主机才认为其是拥塞流，对拥塞做出交换机拥塞探测需要对应的拥塞通知机制。广域网和数据中心普遍采用的做法是交换机标记数据包并传递给接收端后，接收端将拥塞信息捎带在确认包中返工作提出了由交换机直接发送通知信息给源端，例如探测到拥塞后交换机生成单独的ICMPSourceQuench[27]消息通知源端，但典的TCP及其后续的变体如TCPNew-Reno和TCPCubic等[22,28-30]利用丢包作为隐式的拥塞信号，认为丢包时出现拥塞。发生丢包的流量即识别为拥塞流。除了丢包信号，端主机还可以根据端到端延时来探测拥塞。因为当拥塞发生时，拥塞流观察到的端到端延时会因为网络中排队而显著增大。在广域网中，几种基于延时的拥塞控制算法使用RTT来推断拥塞的发生，对拥塞流调节发送速率[31-33]。近谷歌提出的BBR[34]不再将数据包丢失或延时增大作为拥塞的隐式信号，而是在数据中心中，DX[35]也提出直接利用RTT判断排队时延是否大于零来推小，网络拥塞正在缓解。较新的研究工作Swift[36]还区分了由网络拥塞引起的延时增加和由端主机拥塞引起的延时增加，提出要对不同种类的拥塞进行响应。由于数据中心的端到端传播延时目前达到了微秒级，基于端到端延时的拥塞探测通常需要网卡支持高精度的时间戳功能，以提供准确的延时测量，避免端主机处理时延抖动的干扰[19,25]。组合ECN信号和RTT信号，但本质上是利用交换机显式拥塞信号和端到端隐式拥塞信号适用于不同场景的特点进行结合，并没有设计新的拥塞探测机制。另外一些基于机器学习的拥塞控制研究工作[39-42]，不再使用明确的拥塞信号或者拥塞列大小来计算拥塞的度量，该度量值考虑了自上次采样时刻的队长增量以及采样时刻瞬时队列和期望队列的差值。但是由于现代数据中心交换机普遍支持的是基于队列长度探测拥塞并使用ECN标记，测机制是基于队列长度的拥塞探测。CP根据RED算法[21]标记ECN。单个比特机制。交换机探测拥塞时应该区分两种情况a）如果输出端口的队列长度超过选定的阈值并且有可用的信用发送数据包，那么它是拥塞点b）如果输出端口的队列长度超过选定的阈值并且由于信用不足而导致数据包被阻塞，那么它是受拥塞通知（ForwardExplicitCongestionNotification，FECN）标记数据包。单个比基于RTT梯度的拥塞探测应用于无丢失以太网。此外，文献[44]提出在高性能计算系统中使用分布式应用运行时间的梯度进行网络拥塞探测。但是，由于无丢失网络中存在特有的链路层流量控制，拥塞发生后，一旦链路层流量控制向上游生观察到延时的增加。因此，仅基于端到端的延时信息，端到端的拥塞探测方式将交换机和端主机协作的拥塞探测。最近无丢失以太网中的一些研究工作提出采用交换机和端主机协作的方式探测拥塞和识别拥塞流。PCN[45]提出了Non-的数据包的比例在一段时间内超过一个阈值（如95%）时，识别该流为拥塞流。HPCC[7]旨在获取最拥塞链路上已发送但还未确认的数据包数量并对其控制，即通过已发送但还未确认的数据包数量判断拥塞程度。这种方式需要依靠全网部署一个交换机，添加相应元信息字段来携带该交换机处传输的字节数和队列长度信息。发送端根据路径上所有交换机的信息来最终计算最拥塞链路上正在传输但还塞探测本质上根据交换机队列长度判断拥塞情况。无丢失以太网和InfiniBand中现有的交换机拥塞探测遵循了传统有丢失网络中的做法，同样通过队列长度探测用信息来探测拥塞。但是，无丢失以太网中的交换机拥塞探测直接使用基于队长机制对于CBFC影响下的交换机拥塞探测仍然没有更深一步的认识，如实际中周期性更新的CBFC机制本身对于交换机探测行为的干扰，以及受到流量控制影响下的真实端口状态是否一定是不拥塞的，缺乏对于无丢失网络交换端口状态的深增加导致的延时增加将不能明确指示网络中是否发生拥塞，不适用于作为无丢失综上所述，拥塞探测作为拥塞管理架构中的基石，我们需要为无丢失网络设无丢失以太网中的拥塞管理的主要手段是流级别的拥塞控制，通过调节每流发送端驱动的拥塞控制。这类研究工作的思想是先探测拥塞的出现，发送端获取拥塞信号后做出速率调节。IEEEDCB工作组提出的QCN[43]属于此类。在其拥塞控制框架中，CP负责拥塞探测，探测到拥塞后，交换机同时作为通知点（NotificationPoint，NP）产生显式拥塞通知信号直接发送给发送端，最后发送端BIC-TCP[47]的自增型二分速率增长算法。着QCN的思路，工业界后续基于商用交换机普遍支持的ECN功能发展了DC-送端如果在一个控制周期内收到拥塞通知信号，则降低流的发送速率，否则使用定时器和字节计数器决定流的增加速率，速率增长规则与QCN类似。DCQCN根据一个控制周期内收到的拥塞信号，采用启发式的逐步调节，因此可能需要多个计的流级别的拥塞控制，其算法本质上是去掉了慢启动阶段的DCTCP[25]。但是PCN[45]和HPCC[7]是两个较新的采用复杂拥塞探测的拥塞控制机制。HPCC牲了长流的吞吐量。此外每包携带INT信息也进一步损害了吞吐量性能。PCN使用接收速率指导发送端的部分速率调节，能够较快收敛，但是严重拥塞导致的积部署性较低，同时其交换机和端主机耦合的拥塞识别机制在不同网络配置下可能负责做出调速决策，发送端只负责执行限速。交换机使用一个PI控上述发送端驱动的拥塞控制本质上是被动拥塞控制，即先探测到拥塞的出现拥塞控制的主要思想是以“先请求再分配”方式运行的主动传输：显式分配瓶颈链路的带宽并主动防止拥塞[55]。因此能够达到较好的延时和吞吐量性能。这些方案通常让每条流在启动后的第一个RTT内线速传输数据包，后续的传输将显式分配带宽。在ExpressPass中，接收端收到新流数据包后，通过控制反馈的控制报文RTT数据的可用带宽，能够避免端点处以及网络内的拥塞。pHost、NDP和Homa采取类似的做法，但是假设拥塞仅发生在端点处而网络内部不是瓶颈，因此仅能处理端点处的拥塞。然而，这类主动拥塞控制中第一个RTT的数据包由于线速发送也可能导致网络内拥塞的产生[55]。接收端驱动的主动拥塞控制需要接收端能够在为大量发送端发送控制报文的同时保证线速的性能，实现代价高，尚未有在数据中心部署的案例。值得注意的是，接收端驱动的主动拥塞控制最早为传统数据中心提出，并不是专为数据中心无丢失以太网设计，但是这类工作通常被认为可以实现接近零的排队时延和数据包丢失。节。其中交换机依赖队长信息和信用值的有无来判断拥塞并识别拥塞流，但是在信用周期性更新的情况下可能会误识别。此外，发送端的速率调节依赖预设的速拥塞隔离。认识到链路层流量控制机制无法区分不同流而导致队头阻塞、不公平等问题的局限，一些研究工作提出了拥塞隔离的思想以从根本上解决链路层静态拥塞隔离的主要思路是根据提前获知的流量模式和网络拓扑结构定义流量类别到VL的映射[58-59]。随着网络规模越来越大，并且交换机支持的VL的数动态拥塞隔离的主要思路是交换机先探测出拥塞流再为拥塞流动态分配特定以及数据中心应用的拥塞隔离方案。理想的交换机动态隔离方案能够近似模拟每流的队列，能够很大程度上避免队头阻塞等问题。其机制的设计通常需要解决一总之，动态拥塞隔离需要较多的交换机资源实现一系列复杂的机制，尚未有硬件网络内拥塞发生时，将发生拥塞的链路上的流量分散到其他链路利用率较低的等价路径上，可以暂时缓解网络内的拥塞。因此一些研究工作提出使用先进的路由和流量模式，不同工作负载下需要重新计算。动态路由的解决方案会根据网络拥塞情况确定每个包走的路径。文献[68]提出了几种基于源端的动态路由方案。例如，当源端网卡因受到链路层流控影响而停止发送时（或者当被阻塞的数据包超交换机驱动接收端驱动的主动拥塞控制数据中⼼拥塞控制交换机驱动接收端驱动的主动拥塞控制基于ECN基于RTT基于INT专为⽆丢失以太⽹设计基于ECN基于RTT基于INT机制TCP-BoltTIMELY收敛速度慢慢较快较快较快快部署代价低低⾼延时和吞低延时低延时较低延时较低延时低延时路径前先发送探测包探测可选路径是否是拥塞的。基于源端的动态路由方案只有端点处的局部信息，无法保证快速将数据包分配到负载低的路径。因此，目前一些商用InfiniBand交换机支持直接根据端口负载状况选择等价路径[69]。只能短暂地缓解网络内部发生的拥塞，对发生在网络最后一跳处的拥塞（也称端端点主动拥塞控制。一些研究工作[70-72]提出采用主动拥塞控制的思想来避免由多对一流量模式导致的端点拥塞。使用轻量级的预留握手协议，发送端首先发送传输请求，接收端收到请求后返回授权发送方的发送时刻。同时为了降低协议内被丢弃。通常，由于该机制只能解决最后一跳端点处发生的拥塞，需要与其他图2.1总结对比了无丢失以太网拥塞控制相关研究工作。目前发送端驱动的拥路层流量控制的影响，其速率调节可能是混乱的；或者使用高精度高代价的拥塞信号，难以扩展到大规模无丢失以太网。交换机驱动的拥塞控制机制和接收端驱动的主动拥塞控制机制部署代价较高，需要对现有交换机和硬件网卡做复杂的修改，也难以适用于高速的可扩展的无丢失以太网。此外，数据中心时延敏感业务是是是是否是否是的流量和吞吐量敏感业务的流量同时存在于网络中，而已有方案都难以兼顾低延适用于可扩展的无丢失网络。自适应路由和端点主动拥塞控制机制由于其本质上端的拥塞控制机制在无丢失网络中是必要的，近年来受到了工业界和学术界的广泛关注[7,18,45,49,74-75]。工作组[43]和IBTA组织制定的InfiniBand规范[14]都定义了在各自网络中的拥塞管过深入观察和分析，本文发现由于未能正确认识到逐跳流量控制的影响，现有无丢失网络中的拥塞探测机制存在不当之处。在无丢失网络中，交换机端口可以在发送模式会对交换机的拥塞探测行为产生意想不到的影响，包括导致队列累积和根据一系列的观察和理解，本章定义了交换机端口的三元状态，并提出了无指拥塞态、不拥塞态和待定态。处于拥塞态的端口是发生拥塞的地方，其队列长度的增加不是由于端口被暂停传输引起的。本章将ON-OFF发送模式中的端口状态命名为待定态，因为其实际输入速率可能由于上游端口处于ON-OFF发送模式而被掩盖。本章详细阐述了三态之间的状态转换，特别是从待定状态到拥塞状态的转换，这是无丢失网络中拥塞探测的关键。本章为主流无丢失网络（即CEE和 优先级流量控制(PFC)PAUSE数据包优先级流量控制(PFC)XoffXonFCTBSFCTBS FCCL ++ABR基于信用的流量控制(CBPC)基于信用的流量控制(CBPC)发送模式和队列长度的演化特征来探测三元状态之间的转换。测试床和大量仿真实验表明，TCD可以准确探测出拥塞端口，并识别出拥塞流和受到逐跳流量控制表明，已有拥塞控制算法可以通过对拥塞流执行激进的速率调整和对待定流进行温和的速率调节获得更好的性能。采用真实工作负载的仿真实验表明，结合TCD采用了基于信用的流量控制机制CBFC，如图3.1所示。本小节具体介绍这两种流在PFC中，当端口入队列长度超过一个阈值xoff时，下游交换机向上游交消息[14,76]，消息内容是分配的缓冲区大小和ABR大小之和。上游交换机为每个记录已发送的块总数。收到FCCL消息后，可用信用的数量即是FCPFC在每个优先级队列上运行。CBFC在每个VS0S1S0S1S2A0A14T1S2A0A14InfiniBand交换机中，每端口支持的优先级队列数量和VL数量都是和暂停（OFF）之间交替。如果端口被暂停（OFF则到达的数据包将排队等待当逐跳的流量控制生效时（在无丢失网络中是不可避免的交换机端口在ON和OFF之间的交替可能会给交换机的拥塞探测行为带来意想不到的问题。本节通过在单拥塞点场景和多拥塞点场景中进行细粒度的仿真实验，来研究逐跳的我们采用如图3.2所示的拓扑，该拓扑也是目前数据中心网络多根树拓扑（如和FECN（IBCC[14]）分别是CEE和InfiniBand中的拥塞探测机制。拥塞控制算0000404000应被探测到发生了拥塞。然而，由于发生在端口P3处的拥塞扩展至上游交换机，只应在端口P3处被标记ECN/FECN。虽然F1的部分数据包在端口P2被标记为0000404000拥塞探测。在InfiniBand中，交换机根据队长信息以及信用信息探测拥塞。当队拥塞探测。受逐跳流量控制影响的端口也可以定期地收到一些信用。在新信用到在本场景中，端口P2成为端口P3之外的第二ON和OFF之间交替，并且产生了队列累积。同时，因为聚合输入流量速率超过恢复正常发送，表明端口P3处的拥塞得到缓解。之后，端口P2仍然有持久的队列累积。注意端口P2的队长演化与单拥塞点场景不同，单拥塞点场景中端口P2理想情况下，在多拥塞点场景中，当发送速率在ON和OFF之间交替时，交端口是否发生了拥塞可能是不可知的。如图3.3(a)和图3.4(a)所示，在CEE中，从用时，之前因暂停而积压的数据包会立即以线路速率发送。从交换机的局部角度总结：本节详细的观察和分析表明，现有的拥塞探测机制无法正确识别ON-OFF发送模式的影响，导致无丢失网络（如CEE和InfiniBand探测结果。对具有ON-OFF发送模式的端口的细粒度观察表明，一个端口可能有•不拥塞（0端口持续开启（ON）并且没有累积的队列。•拥塞（1端口处于持续开启（ON）的状态，输出速率为线速，其中队列待定状态是逐跳流量控制引入的ON-OFF调节导致的，该状态对于没有逐跳流量控制机制的传统网络来说是一种新的状态。假设一个交换机端口在开始时以包先出队传输。在待定状态期间，数据包可能随时到达。最后，端口恢复以持续为了进一步阐述端口离开待定状态后的状态，本节以不同拥塞树之间关系为 拥塞树的根节点拥塞树的叶⼦节点eee树b(a)分离(b)重叠(c)覆盖（1）分离：两棵拥塞树在网络中同时存在，并且没有重叠的叶子节点或根节点。拥塞树的根节点处于拥塞状态。如果其中一棵拥塞树消失，则叶子节点从待定状态过渡到不拥塞状态，根节点从拥塞状态过渡到不拥塞状态。在单拥塞点场持续ON，队⻓减持续ON，队⻓减拥塞树b的根节点都处于拥塞状态。如果一棵拥塞树先消失，则重叠的叶子节点无丢失网络拥塞探测的首要目标是探测交换机的拥塞端口。拥塞端口是拥塞树的根节点，通过它们的流量是拥塞的罪魁祸首，即拥塞流。拥塞树的叶子节点端口从待定状态解除后有可能立即形成新的拥塞树。因此，拥塞探测的关键是捕第3.4.1节首先介绍三元状态之间的转换条件。第3.4.2节给出了ON-OFF模型图3.6展示了交换机端口中三态之间的状态转换。总体而言，状态转换条件①和②与有丢失网络中类似，其中队列长度是主要的转换条件，但是端口是持续开ON发送模式和ON-OFF发送模式。到待定状态的转换(③和⑥)。一旦端口进入ON-OFF发送模式，端口就会从待定状态到非拥塞或拥塞状态的转换(④和⑤)。从待定状态到不拥塞状（1）离开待定状态的条件首先是端口从ON-OFF发送模式转换到连续ON模（2）离开待定状态后进入拥塞状态或不拥塞状态的条件需要考虑队列长度演积压的数据包。此时较长的队列长度不能反映该端口是拥塞的。如果从待定态释放后，队列长度减小，说明其实际输入速率没有超过线速，端口转换为不拥塞状态。如果从待定态释放后队列长度不减并且超过阈值，端口转换到拥塞状态。为了获得队列长度变化的趋势，交换机可以每个周期T检查队列大小。一旦队列长度在当前周期T增加并超过一个阈值，则当前状态转变为拥塞状态。如果任何一通过待定端口的流可能只是受害者流。通过提供待定状态的信息，交换机拥塞探测使得端到端的拥塞控制机制能够根据不同的要求对待定流和拥塞流进行不同的速率调节。如表3.1所示，交换机可以重用两比特ECN标记位支持三元拥塞通知。1ONONB1ONONOON数据包可能沿路径经过多个状态不同的端口，如果一个数据包首先通过一个待定基于三态之间的状态转换，本章提出了无丢失网络的交换机三元拥塞探测机它决定何时进入和离开待定状态，以及转换到拥塞状态。下面关键的问题是确定CB1/B0RiRdτε拥塞流的拥塞度，定义为(Ri−Rd)/C本节构建了一个如图3.7所示的概念性ON-OFF模型来描述无丢失网络中Ton在稳态下，该队列长度和ON-OFF发送模式的动态行为是不断重复的。主要的参端口发送后，需要一段时间后才能生效。假设τ是响应时间，即生成ON/OFF消息与下游端口感知到输入速率相应变化之间的时间间隔，那么实际的最大和最小Rd是拥塞流的平均输出速率，即拥塞流在拥塞的出端口分配到的带宽。在ON-OFF模式下，Ri总是大于Rd。这里定义ε来表示拥塞流所经历的拥塞程度，接收端发送数据的一般拥塞场景，由于最简单的情况是两个发送端竞争一条瓶颈链路，则相当于在所有拥塞场景中一条拥塞流可以分配的最大带宽是C/2。因此ε足以适应大多数情况，使得交换机能够区分出ON-OFF发送模式和连续ON模ε减小，触发逐跳流量控制的频率也降低。实际上，一个非常小的ε是不合适的，Rd(Gbps)TRd(Gbps)Ton(us)0是待定状态，则表示端口刚刚从ON-OFF发送模式中释放出来，交换机检查队列长度在最后一个T周期内是增大还是减小。在T周期并且LAST_STATE是待定状态，则不标记任何数据包。如果队列长度不减并且大于阈值，则交换机探测到拥塞状态的转换。一旦队列长度减小到低于阈值，或者在PFC中，交换机端口在收到来自下游端口的PAUSE帧时停止传输，并在到达排队的数据包也可能被传输。因为PFC是由端口入队列长度触发的，所以可发送⼀个数据包计算当前Ton是 是 Ton<Ton<max(Ton)？否否否否否LAST_STATE为不拥塞重置定时器/FCCLLAST_STATE是待定态?是标记CE；LAST是标记CE；LAST_STATE为拥塞否否收到是收到记录队⻓是RESUME帧记录队⻓是LAST_STATELAST_STATE为拥塞T时间内队⻓减？LAST_LAST_STATE为不拥塞参数设置。在PFC中，B1−B0即为xoff和xon的差值，推荐值为2MTU[18]。参数τ由几个部分组成。简而言之，当端口接收器准备好发出控制消息（PAUSE帧/RESUME帧）时，该消息不能中断端口上正在进行的数据包传输。在最坏的情况下，消息将延迟MTU/C时间。处理完控制消息后，发送方将输出速率更改为ON或OFF。在最坏的情况下，它需要等待另一个MTU/C。最后，τ也由两倍的传播延迟tp组成。可得τ=2MTU/C+2tp。对于从待定状态释放后检查队据包大小时恢复传输。FCCL消息中携带信用数量，该消息定期发送到上游端口。包被首先传输，然后新到达的数据包也可能被传输。由于流控消息FCCL是根据时间而不是入口队列长度触发的，所以在InfiniBand中不能直接采用式（3.3）中ONONON … PAUSERESUMEPAUSERESUMEPAUSE在RESUME期间到达和离开的数据包被PAUSE住的数据包ONONONONTcTcTcTc当前更新周期有credit的数据包上个更新周期没有credit⽽被延迟的数据包推导出的max(Ton)。实际的B1和B0在不同的拥塞情假设交换机的入端口VL的缓冲区大小是B，它必须大时间。注意符号时间在不同链路速度下不同。为4ns和1ns[14]。对于从待定状态释放后检查队列长度减小/增大的周期T，建议寄存器来完成其功能，而当今的商用交换机具有丰富的寄存器资源。例如，要计算当前Ton，端口的每个优先级队列/VL只需要一个寄存器来记录的结束时间。TCD还需要寄存器来记录LAST_STATE和队列长度。与传统的标记20304050(s)20304050(s)(s)与现在交换机检查队列长度的功能类似。max(Ton)可以预先配置，因为所有参数(ε、C、τ和Tc）都是预先知道的或在无丢失网络中可配置的。整体计算复杂度为O(1)。随着越来越多的交换机支持可编程和开放的数据平面，检查时间戳和队列长度减小/增大的操作可以在交换机数据平面以线速实现，而无需控制平面的参大小的元数据信息[46]。际的RESUME周期长度可能会出现波动。然而，优先级调度不会对TCD产生显或三个可用于数据传输的优先级队列[5,15-16]。在InfiniBand交换机中，InfiniBand我们构建了基于图3.2拓扑的一个紧凑拓扑（交换机T0直接与交换机T2连8259910G网卡，用作四端口交换机。基本的二层交换机实现参考块都绑定在单独的一个CPU核上。我们按照IEEE802.1Qbb[6]实在PFC下的TCD中，xoff设置为800KB，xon设置为770KB。参数ε值为0.04。本节将ε调整至0.04是由于软件DPDK的处理会引入不确定的延时。在DPDK实现中，PAUSE帧和RESUME帧的响应时间之间存在不可忽略的随机差定端口P0和拥塞端口。本实验关注端主机观察到的数据包的标记情况。图3.11展在单拥塞点场景下，端口P2和端口P1经历了从待定状态到不拥塞状态的转8006004002008006004002008006004002008006004002000.00.51.01.52.02.50.00.51.01.52.02.5800600400200800600400200C800600400200800600400200C低。因此端口P2被探测为拥塞状态，并且数据包被标记CE。由于端口P2TCD可以通过准确探测拥塞状态和待定状态来使队头阻塞发生时的受害者流使用图3.2中的拓扑来评估典型的队头阻塞场景中TCD的性能。链路<S0-T0>和不应被探测为拥塞流。如果一条流中标有CE的数据包数量大于零，则认为该流被错误地探测为拥塞流。对于CEE，主机S0~S1和A0~A14根据具有指数分布的到达间隔时间的重尾Hadoop工作负载[85]生成流量。主机A0~A14上的工作负载生成器同步生成流量以模拟并发的突发。默认的拥塞控制算法是DCQCN（CEE）MPI和I/O消息[86]。如表3.3所示，在两个网络中，都有被探测到经历拥塞的受害8006004002008006004002008006004002008006004002000.00.51.01.52.02.50.00.51.01.52.02.5800600400200800600400200800600400200800600400200max(Ton)过期后立即探测到待定状态的释放，太小的max(Ton)可能会导致将待定状态错误地探测为拥塞状态或不拥塞状态。另一方面，太大的max(Ton)也可能推迟对拥塞状态的探测。为了评估ε的参数敏感性，本小节使用不同的ε值重复上的主要目标不是提出无丢失网络中最佳的拥塞控制算法，而是强调准确拥塞探测的重要性。借助TCD，我们可以通过考虑不同的拥塞状态来增强现有的端到端拥6040200.20.150.10.756040200.20.150.10.750.050.0250CECE标记的数据包CECE标记的流(0,10K)[10K,100K)[100K,1M)[1M,+)ALL受害者流大小(Byte)((ms)UE标记的流突发流大小(Byte)0.80.60.40.20.0流可能是不应该降速的受害者流。另一方面，盲目增加待定流的速率可能会加剧交换机使用TCD后，接收端NP将CE/UE信息传送回RP。发送端在收到带有UE标记的CNP时将不更新发送速率开源项目[87]开发的。PFC的阈值xoff和xon分别为320KB和318KB。其余参数设置为文献[18]中的推荐值。 0.1K0.3K0.4K0.55K0.6K0.8K26K4.8M9.7M0.1K0.3K0.4K0.55K0.6K0.8K26K4.8M9.7M23K500K3.2M28M23K500K3.2M28M(Byte)(Byte)流完成时间主要得益于对拥塞流的激进减速，因为短流的速率难以受到端到端拥塞控制的调节。激进的减速带来更少的拥塞扩展，因此短流会经历更低的排队延DCQCN不会错误地让受害者流量降速。而如果没有TCD，一些受害者流被探测送速度，从而导致更多的队列累积和更大程度的拥塞扩展。结果，更多的受害者非常严重，简单地增加α对拥塞流激进减速不能够有效缓解此时的拥塞。总体而言，DCQCN与TCD相结合可以在突发短流引起拥塞时提高受害者流的流完成时我们调整流生成速率使得平均链路负载为60%。实验生成了4万条具有指数分布分位的流完成时间放缓比。流完成时间放缓比是通过实际的流完成时间除以理想512K1M2M4MALL消息大小(Byte)2K4K16K32K512K1M2M4MALL消息大小(Byte)DCQCN对于中等长度和短流实现了更好的流完成时间放缓比性能。结的流完成时间放缓比与DCQCN几乎相同，这是因为这些长流的性能瓶颈在于严1更改为2，以积极降低拥塞流的速率。仿真器是基于M开源项目[88]开发的，并且添加了对IBCC和TCD的支持来扩展此合成工作负载：本小节选择了典型MPI和I/O作业的合成通信模式来模拟多个作业共享网络的高性能计算场景[86]。该网络是一个具有1024个服务器的Fat-TIMELY(0,10K)[10K,100K)[100K,1M)[1M,+)ALL受害者流大小(Byte)TIMELYUE标记的流突发流大小(Byte)0.80.60.40.20.0于每个机架，随机选择四台服务器作为I/O服务器来接收来自I/O客户端的I/O流量。然后随机选择25%的服务器作为I/O客户端。其余服务器是MPI客户端和TCD还可以使基于延时的拥塞控制算法受益。TIMELY[19]使用RTT的变化于零并且Tlow<RTT<Thigh，数据包又同时被UE标记，则发送端不会更新发送时，受害者流的发送速率不会降低。图3.18(a)显示了图3.2拓扑下受害流的平均流性能，其中主机A0~A14生成不同大小的突发短流。图3.18(b)显示了受害者流的TIMELY+TCD(p99)TIMELY+TCD(p95) TIMELY+TCD(mid)TIMELY+TCD(p99)TIMELY+TCD(p95) TIMELY+TCD(mid)0.1K0.3K0.4K0.55K0.6K0.8K26K4.8M9.7M0.1K0.3K0.4K0.55K0.6K0.8K26K4.8M9.7M(Byte)TIMELY+TCD(p99)TIMELY+TCD(p95)TIMELY+TCD(mid)23K500K3.2M28M23K500K3.2M28M(Byte)40(Gbps)(Gbps)204402004平均流完成时间性能和待定流的比例。类似地，随着突发短流大小的增加，更多在突发短流开始时同时向R0发送四条长流。图3.20展示了速率调节策略下，四条流的速率将保持不变，因为它们只经过待定的端口P2。吞吐量的下降是因为逐跳流量控制开始生效，链路<L0-T2>发生了队头阻塞。结果口P3处拥塞解除后，端口P2变为拥塞端口。然后四条流转换为拥塞流，拥塞控是另一种探测状态转换的设计选择。TCD依靠预先配置的max(Ton)来决定是否进入和离开待定状态。根据构建的ON-OFF模型和实验评估，本章认为一个合适这种固定max(Ton)的方式只会有限地推迟间以一个很低的频率切换。为了整体设计和实现的简单性，TCD做出了在这些极与现有拥塞控制算法合作。积极降低拥塞流的速率并温和地调整待定流的速率是本章对在无丢失网络中将TCD与现有拥塞控制算法结合的初步建议。第3.5.2节中的案例研究只是验证上述见解的简单示例。然而，如果网络中没有触发PFC或CBFC，那么简单地对拥塞流采取比现有拥塞控制算法更激进的减速可能会损害链路利用率和吞吐量性能。鉴于在实际生产经验中，PFC或CBFC的触发是无法完全避免的[5,90-91]，本章认为针对拥塞流和待定流确定适当的速率调整本章重新认识了无丢失网络的交换机拥塞探测问题，并为主流的无丢失网络（无丢失以太网和InfiniBand）提出了三元拥塞探测机制TCD。本章定义了一种称为待定状态的新端口状态，给出了三元端口状态的定义，并通过构建ON-OFF模型确定了三元状态的转换条件。测试床和大量仿真实验表明，TCD可以准确地探测出拥塞端口，识别出拥塞流以及被逐跳流量控制影响的流。案例研究表明，现近年来，工业界和学术界都在努力开发专用的拥塞控制机制以促进无丢失以太网的大规模部署。按拥塞信号的来源划分，主要有两种技术路线：需要交换机辅助的拥塞控制和无需交换机辅助的拥塞控制。作为交换机辅助拥塞控制机制的的速率调整可能会导致速率收敛缓慢。更糟糕的是，一旦发生队头阻塞，基于队列长度的ECN信号不能提供正确的拥塞指示。HPCC[7]提出依靠交换机提供的高较高的数据包捎带开销，牺牲了长流的吞吐量性能。TIMELY[19]提倡发展么诉诸全新的技术来设计拥塞控制。然而，已有工作都在一定程度上忽略了无丢），各种问题。因此，本章提出的问题是：是否可以通过充分利用无丢失以太网的固受第3章提出的三元拥塞探测机制TCD[92]的启发，本章借助于为无丢失网以太网的拥塞控制机制。TCD能够捕获交换机中逐跳流量控制和拥塞探测行为之间的交互，因此可以准确地区分受逐跳流量控制影响的端口状态。通过重用ECN地处理受PFC影响的流以平衡拥塞扩散和高吞吐量是至关重要的。此外，本章观察到由于无丢失网络具有数据包守恒的固有特性，ACK驱动是一种指导拥塞流速生）永远不会被丢弃，所以发送数据包的接收速率以及网络中持有的过多的传输速，以及（3）利用ACK序列信息在发送端施加源停止状态。源暂停状态旨在准确快速地消除由于过多的拥塞流数据包而导致的队列堆积。ACK指导的拥塞流降行精细和有针对性的速率调节，并在发送端施加间歇性停止操作以排出交换机缓（3）在SoftRoCE[93]中实现了ACC并通过实验评估ACC。大规模仿真表明ACC可以同时实现低延迟和高吞吐量。在各种工作负载下，与高精度高代价的HPCC相比，ACC可将短流和长流的第99百分位流完成时间至多降低40%和超过了瓶颈链路带宽。因此，拥塞控制的主要目标是高效率，即快速使聚合流量速率匹配瓶颈链路带宽。事实上，由于几个特有的问题，无丢失以太网迫切需要所有拥塞流经过的路径成为拥塞树的主分支。当去往非拥塞点的拥塞无关流经过主分支时，后压效应可能会进一步诱发次生分支的产生，进而发生队头阻塞。在ACK也会被阻塞。如果端主机依赖返回的ACK来获取网络状态，则阻塞的ACK可能会推迟真实网络状态的感知，从而影响拥塞控制算法的决策。其次，PFC还可以直接与交换机中的拥塞探测行为交互。一旦发生拥塞扩展，队列的输入和输可能会突然增加。当拥塞已经蔓延到上游时，队列的输入流量模式可能被调节为ON-OFF模式。此外，在拥塞扩展消失后，由于先前的PFC触发而累积的队列可能指示的是陈旧的拥塞状态。简而言之，PFC会对所有基于队列的拥塞探测行为是一种适用于无丢失网络的