RDMA之路由算法介绍 （6）

1、自适应路由算法和非自适应路由算法之间的区别自适应路由算法非自适应路由算法自适应算法涉及用于交换和更新路由器表数据的路由器。非自适应算法涉及网络管理员手动将路由路径输入路由器。该算法根据网络条件创建路由表。而此算法创建一个静态表以确定何时发送数据包以及哪个节点。该算法用于动态路由。而此算法由静态路由使用。在自适应路由算法中路由决策是根据网络流量和拓扑结构做出的。而在非自适应路由算法中路由决策不是根据网络流量和拓扑做出的。就复杂性而言与非自适应路由算法相比自适应路由算法更为复杂。而非自适应路由算法在复杂性方面很简单。在自适应路由算法中路由决策不是静态表。而在非自适应路由算法中路由决策是静态表。自适应路由算法分为分布式、集中式和隔离式。而非自适应路由算法分为随机游走和泛洪。与非自适应路由算法相比自适应路由算法的使用更多。而非自适应路由算法的使用相对较少。动态协议用于更新路由表并确定源计算机和目标计算机之间的最佳路由。执行手动设置是为了在源计算机和目标计算机之间建立最佳路径。它主要用于-开放、复杂的网络拓扑它主要用于-简单、封闭的网络拓扑目的增强网络性能防止数据包传送失败帮助控制拥堵目的它可以对数据包路径进行细粒度控制。适用于负载稳定的可靠网络2、智算网络中不同负载均衡技术对比数据中心网络或智算网络的拓扑结构相对规整如Spine-Leaf架构所以在选路方面相对简单。但由于数据中心网络的服务器之间往往都存在多条等价并行路径比如在Fat tree网络中可能存在多达几十条因此如何在多条并行路径之间进行负载均衡路由是数据中心网络路由设计的关键。传统负载均衡用的比较多的是等价成本多路径ECMPECMP下一跳的路径是通过对数据包字段进行哈希计算并对可用路径数取模来选择的来自一个流的数据包总是映射到同一路径因此这些数据包将按发送顺序交付也就是通常的基于流的负载均衡Flow-based。然而研究表明在流量高度倾斜时ECMP无法平均分配负载到不同的路径如大象流场景。特别是对于当前HPC和AI场景普遍使用RDMA并且是大带宽场景这个时候传统ECMP很容易导致链路Hash不均进而导致某一个链路拥塞。在AI/ML的应用中GPU或其他类型的AI/ML计算单元之间他们有着非常简单的通讯关系流的数量非常少并且由于他们有着极高的计算能力导致一对通讯单元间的数据吞吐极高单个流很大所需的网络带宽极大这就导致在这样的应用中存在极端的负载分担不均衡而且这种不均衡一旦引发网络丢包就会对整体AI/ML的任务完成时间带来显著的负面影响。网络中的拥塞整体一般有两种一种是在端侧的拥塞常见于多打一的Incast场景这种情况通常用各种拥塞控制算法来使对应的发送端减速来解决。另一种是矩阵拥塞即网络因为Hash不均导致的拥塞。这里重点讨论矩阵拥塞的解决方案。解决矩阵拥塞主要有以下几种方式胖树架构设计增加汇聚链路带宽典型的就是采用Fat tree网络架构设计从输入到输出1:1的收敛比设计VoQVirtual Output Queueing技术是一种网络拥塞管理技术用于防止HoL阻塞的技术在传统的输入缓冲区排队方案中数据包先进入输入缓冲区然后根据目的端口的可用性从中选择出队。然而当多个数据包的目的端口相同时输入缓冲区排队会导致阻塞和拥塞。VoQ技术通过为每个输出端口创建虚拟的输出队列将输入数据包直接放入对应的虚拟输出队列中。这样在数据包进入路由器或交换机时就可以直接选择适当的虚拟输出队列而无需等待目的端口的可用性。因此VoQ技术可以避免输入缓冲区排队可能引起的阻塞和拥塞问题提高网络的吞吐量和性能负载均衡Load balance不同的负载均衡路由策略会对端到端的吞吐率造成很大的影响。流量Load balance按照粒度不同可以分为以下几种方式基于流Flow based、基于包Packet based、基于流片Flowlet、基于信元Cell based3、现有主流负载均衡技术现有主流负载均衡技术大体分为四种逐流的 ECMP 负载均衡(flow based)逐包负载均衡(packet based)基于子流Flowlet的负载均衡。基于信元Cell based3.1逐流负载均衡(Flow based)传统的 ECMP 路由通常采用逐流负载分担机制其核心是基于数据包的特征字段例如 IP 五元组等信息作为计算因子去进行哈希运算根据哈希值选择转发链路。1、不同的流由于特征字段不同会生成不同的哈希值从而分散到不同的链路完成转发在整网实现一定的负载均衡2、具有相同特征字段的流经过哈希运算后会分配到同一条转发路径由此保证了同一条数据流会按序依次到达对端。随着云计算的发展和智算业务兴起逐流负载均衡的缺陷愈加凸显。首先逐流的负载均衡无法解决流大小不均的问题当大小流平等、粗放地进行负载均衡的精细度有限带宽利用率也有所损耗其次它是一种静态的负载均衡机制无法实时感知链路的负载情况。当网络出现大象流静态负载均衡机制依旧会按照既定的路由算法去选路容易进一步加剧拥塞造成丢包尤其是智算集合通信场景下该机制还极易在 Clos 组网的 Leaf 上行链路出现哈希极化现象造成网络拥塞。3.2逐包负载均衡(Packet based)逐包的负载均衡技术则是将数据包均匀地负载到各条链路上又被形象地称为“数据包喷洒”Packet Spray。逐包负载均衡通常提供 Random 和 Round Robin 两种算法Random 算法将数据包随机分散到各条链路上Round Robin 算法能够将数据包逐一等量的分散到各条链路理论上均衡度最好。随机包喷洒Random Packet SprayingRPS是一种基于包级别的负载均衡策略。当交换机发现有多条等价路径指向同一目的地址时RPS会将数据包以单个包为单位分散到这些路径上。与ECMP不同RPS以数据包为单位进行操作将同一流中的不同数据包转发到不同的等价路径上。RPS的优点在于简单易实施通过细粒度的负载均衡可以在多条并行路径之间实现较为均衡的路由选择提升端到端的网络吞吐率可以将并行链路利用率提高到90%以上。缺点在于可能会造成同一个流的包乱序问题所以这种方式必须要很好解决乱序问题。例如英伟达的解决方案中就使用BlueField-3 DPU通过DDP直接数据放置处理无序数据从而形成端到端的完整解决方案。但由于实际组网中不同链路的负载情况和转发时延不一样逐包负载均衡无法保证报文依照原有时序到达接收端故其整体性能依赖于端侧的缓存容量和乱序重组能力。3.3基于子流Flowlet的负载均衡不同于传统负载均衡的逐流负载分担或逐包负载分担基于子流的负载均衡不光是对数据流进行分割以实现更精细均匀的负载分担而且保持了报文到达的时序性。Flowlet本质是利用TCP的流突发特性根据设置一定间隔将流分割为一个个Burst子流然后每次切换都是在这个间隔中间从而避免乱序。但是这个方式也有局限性首先Flowlet无法应对短连接场景试想如果一个Flow一共就一个Burst那Flowlet必然无法产生效果其次Flowlet是针对TCP的特性设计的而RDMA流量并不符合相关特征因此在上层应用为RoCE流量时Flowlet基本没有效果这也是在AI/ML等场景中不使用Flowlet的原因。Flowlet的实现原理如下对于TCP Flow通常假设Packet是平滑发送的然而实际不管是实际抓包还是从具体实现上看都会发现TCP Packet的发送其实是Burst的发送的如下图一般而言英文中的“-let”后缀代表“微小”的意思一个Flowlet代表的就是一条小流。如下图所示在宏观的观感上可以把一条flow看成是多个flowlet组成的负载均衡现在就是基于flowlet来进行了好吧又引入了一个中间层它既不是packet也不是flow而是大于packet小于flow的flowlet,那么到底如何定量去切分Flowlet呢已知两条链路的延迟分别为D1D2设一个数α当α满足下面的条件α |D1−D2|一条Flow便可以通过α来切割为不同的Flowlet。3.4基于信元Cell based在基于信元交换的网络级负载均衡机制下接收端设备接收到报文后会将报文拆分成的若干信元信元会基于目的端发送的调度信令选择空闲的链路进行转发到的目的后信元被重新拼装成报文发出设备。在这样的机制下不同于流转发一个固定的流仅能利用单条路径信元交换是动态的基于微观负载实时调整的均衡利用。信元交换的粒度比基于包的负载均衡还要细理论上带宽利用率可以更高。信元交换本身并不是一项崭新的技术在目前广泛应用的框式设备中线卡芯片与网板芯片之间的流量交换普遍都采用了信元交换的技术以实现机框内无阻塞交换。不过信元交换以前主要应用在框式设备系统内部往往都是各个交换机设备厂商自定义的信元格式和调度机制不具备跨厂商互通的能力此项技术可以进一步扩展应用到整个网络上。2019年ATT向OCP提交了基于商用芯片的盒式路由器规范提出了DDCDisaggregated Distributed Chassis的概念DDC使用的核心技术也是信元交换的方案。AI/ML网络支撑的业务其特征是流数量少单条流的带宽大同时流量不均匀经常出现多打一或者多打多的情况All-to-All和All-Reduce。所以极易出现流量负载不均、链路利用率低、频繁的流量拥塞导致的丢包等问题无法充分释放算力。信元交换将报文切片成Cells对比Packet based的负载均衡方案粒度更小并根据可达信息采用轮询机制发送流量负载会较为均衡的分配到每一条链路实现带宽的充分利用这样可以解决中大小流的问题仍然存在相当多的缺陷静态时延增加DDC的大缓存能力将报文缓存势必增加硬件转发静态时延。同时信元交换对报文的切片、封装和重组同样增加网络转发时延。通过测试数据比较DDC较传统ETH网转发时延增大1.4倍。显然不适应AI计算网络的需求。硬件依赖特定芯片实现封闭、专用大缓存设计增加网络成本3.5 总结基于上述分析可以看出以上几种负载均衡方案各有优劣从实际部署的角度看负载均衡的粒度从小到大的顺序是Cell based、Packet based、Flowlet、Flow based对应的带宽利用率则是从高到低但是由于Cell based自身的限制实际在智算领域基本没有应用。当前高性能计算、分布式存储、人工智能等应用均采用RoCEv2协议来降低CPU的处理和时延提升应用的性能。然而由于RDMA的提出之初是承载在无损的InfiniBand网络中RoCEv2协议缺乏完善的丢包保护机制对于网络丢包异常敏感。尽管可以使用PFC、ECN等流量控制和拥塞控制技术尽量实现无损网络特性但还是很难应对大象流/老鼠流分布不均的影响而网络负载均衡是一个绕不开的点。在这方面各厂家也在做各种努力尝试。比如在英伟达的RoCE解决方案中可以针对RDMA流和TCP流采用不同的策略如TCP使用FlowletRDMARoCE采用逐包的负载均衡策略。Spectrum可以通过网络侧交换机和端侧DPU的紧耦合联动做到实时动态监控ECMP各个链路的物理带宽和端口出口拥塞情况来做到基于每个报文的动态负载分担。Spectrum-4交换机负责选择每个数据包基于最低拥塞端口均匀分配数据传输。当同一流的不同数据包通过网络的不同路径传输时它们可能以无序的方式到达目的地。BlueField-3 DPU通过DDP处理无序数据避免了数据报文缓存和重组的困扰通过上述方案在超大规模系统和高负载场景下相对传统RoCE方案性能提升明显。再比如华为的智能无损网络通过ACCAutomatic ECN动态调整每个交换机的标记阈值以分布式方式工作并结合离线和在线训练以适应动态流量模式ACC在线速率下实现了老鼠流和大象流的低流完成时间优先调度小流的报文从而保障小流的转发时延提升整体吞吐性能。