快速轻量级的软件云负载均衡器CONSTRUCTION的设计与评估

179一种快速轻量级的软件云负载均衡器史守谦sshi27@ucsc. 加州大学圣塔分校克鲁兹李欣谷歌叶宇宇谷歌李小舟赛勒网络陈倩qian@ucsc. 加州大学圣塔分校克鲁兹谢明浩加州大学圣克鲁兹颖张Facebook摘要负载均衡器（LB）是云服务在资源之间平衡负载的重要网络功能。在商用服务器上运行的有状态软件LB提供了灵活性、成本效益和数据包一致性。然而，当前的设计具有两个主要限制：1）状态被存储为缓存，这可能由于数据冲突而导致分组不一致; 2）数据平面需要针对每个新连接进行更新，并且频繁的更新损害吞吐量和分组一致性。 在这项工作中，我们提出了一个新的软件有状态LB称为CONSTRUCTION，这是第一个解决这些问题的解决方案。Conclusion的关键创新点是提出了一种新的方法来维护频繁连接到达的大型网络状态，该方法内存开销简洁，在网络变化时保持一致，更新开销低评估结果表明，CONCLUSION算法提供了4倍的吞吐量和消耗更少的内存相比，其他LB算法，同时提供加权负载平衡和假命中自由，为真实和合成的数据中心流量。我们实现了Contrast并对其进行了评估余烨和李欣分别在肯塔基大学和加州大学圣克鲁兹分校攻读博士学位期间从事该项目允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。SoCC© 2020计算机协会。ACM ISBN 978-1-4503-8137-6/20/10。. . 15美元网址：//doi. org/10. 1145/3419111。3421279两个真实的网络。它在100GbE的廉价台式机上实现了67.2 Gbps的单线程吞吐量CCS概念·网络→中间盒/网络设备;云计算。关键词负载均衡;软件负载均衡器;云计算;数据中心;移动边缘计算ACM参考格式：Shouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang ，and Chen Qian.2020年。 Conclusion ：一 个快速、轻量级的软件云负载均衡器。在ACM云计算研讨会（SoCC '20），2020年10月19日至21日，虚拟活动，美国。ACM，纽约州纽约市，美国，14页。网址：//doi. org/10. 1145/3419111。34212791引言负载均衡器（LB）是提供互联网服务的数据中心的基本网络功能 为了适应大规模流行服务的高需求，例如搜索引擎、电子邮件、照片共享/存储或消息发布和交互，数据中心维护多个后端服务器，每个后端服务器携带直接IP（DIP）。 对于特定的服务，客户端将其请求发送到一个公共可见的IP地址，称为虚拟IP（VIP）。每个VIP都映射到一个DIP池。LB使用不同的DIP来替换服务请求上的VIP，并在服务器之间平衡负载，这样就不会有服务器过载而中断服务。LB通常在层4上或层4之上操作。传统的基于硬件的LB [8，10，11]在可扩展性、可用性、灵活性和成本效率方面存在限制[23]。因此，主要的网络服务，如谷歌[23]，微软[32]和Facebook [7，22]已经开始依赖于SoCCShouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang，andChen Qian180有状态软件LB，通过使用在商用服务器上运行的分布式数据平面进行扩展，提供高可用性、灵活性和成本效益。一个数据包是有状态的意味着它属于一个连接，并且该连接的前一个数据包已经被转发到一个DIP。否则，数据包是无状态的。有状态LB的关键功能包括以下内容。1）对于可以被发送到支持其VIP的任意DIP的无状态分组，LB算法应该基于后端服务器的当前容量充当加权随机发生器。2）对于有状态分组，LB将其转发到接收到先前分组的特定DIP，从而保持分组一致性。有状态LB算法的主要挑战是在网络动态下保持数据包的一致性，包括由于服务器故障或更新而导致的新连接到达和DIP变化。大多数现有的LB算法使用哈希表来存储连接状态作为数据平面解决方案[23，32]。这些有状态LB经历存储分组状态的大存储器成本或分组处理的低容量他们需要大量的商用服务器来向外扩展，例如，据Mi- crosoft[25]和Google [23]报道 ，最 多可 达数 据中心 规模 的3.5%-10%因此，一些LB使用连接列表（例如，连接的5元组的散列值）而不是完整的连接状态（例如5元组），以减少内存成本并提高吞吐量[23]。 这种设计有两个主要的缺点：1）使用长缓存可能仍然需要大量的内存，而使用短缓存会由于摘要冲突而导致数据包一致性的破坏; 2）大量的新连接导致高度频繁的数据平面更新，现代集群可能很容易每秒经历数千个新连接[28]，这严重损害了数据包处理吞吐量，并可能违反数据包一致性。现有的方法依赖于对哈希表的快速和并发读取和写入[24，26]，不能容易地应用于LB算法，因为它们只使用完整的状态键而不是哈希表。最近的工作是在可编程交换机上使用ASIC进行快速查表[28]，但进一步增加了基础设施成本。我们提出了第一个有状态的LB算法，解决了目前的限制，称为CONTENT。 1它的关键创新和贡献是一种新的方法，用于维护具有大量新到达连接的大规模网络状态，该方法在内存成本方面简洁，在网络变化下保持一致，并且很少发生数据平面更新。 这种方法可能适用于许多有状态的网络功能，如NAT和LTE演进的分组核心，但本文只关注LB。[1] Concordia这个名字来自Concordia，罗马的平衡与和谐女神，以及Mercury，罗马的信息/通信和旅行者之神，以他的速度而闻名。与 现 有 的 有 状 态 LB[7 ， 23， 25 ， 28 ，32]相 比 ，Conclusion提供了两个主要优点。1）我们认识到，软件LB目前的局限性来自于状态维护和查找的算法设计：哈希表存储索引。为了降低存储器成本，当前LB存储状态列表而不是整个状态标识符（例如，>100位的5元组）[23，28]。缺点包括：1）由于摘要冲突导致的错误表命中[28]，以及2) 由 于 拆 卸 消 化 器 困 难 而 导 致 的 工 作 台 爆 炸 。Conclusion使用数据结构以简洁的方式表示所有数据包状态（只有两个小数组），通过利用最小完美散列的理论基础[18，20，21，27，39]。 Conclusion的设计方式 ， 它 发 现 有 状 态 的 数 据 包 的 特 定 目 的 地 和 simul-randomizer作为一个加权的无状态的数据包与小内存成本和数据包的一致性。然而，应用理论上的奥赛罗哈希并不简单。有几个系统构建挑战需要克服：支持高效和快速查找，在有限资源下管理连接，以及没有错误命中。2）现有LB上的数 据 平 面 更 新 针 对 每 个 传 入 连 接 发 生 。Connected包括数据平面和控制平面之间的协调，使得Connected不需要为每个传入连接更新其查找表。相反，每次后端服务器更改（DIP更改）时都会更新一次Con数据平面，这比新状态到达的频率要低得多。Connected中的状态 维 护 和 更 新 比 现 有 解 决 方 案 简 单 得 多 ， 这 使 得Connected能够保持高查找吞吐量和一致性。此外，Conclusion可用于复杂的互联网应用和新兴的边缘云[33，34，37，38]。1) 它符合通常具有受限资源的边缘云的条件，边缘LB可以仅由一个服务器托管，并且可以与服务器上的其他服务协同定位[34，38，41]。2）传统的云LB考虑每个TCP连接的状态。在现代云或边缘中，状态可以用于多连接并且处于设备级或过程级[34，38，41]，即，属于单个设备的分组例如，用户设备可以继续将其视频数据卸载到边缘服务器，让服务器处理数据，并且稍后从服务器请求分析结果[34]。整个过程由多个TCP流和UDP伪流组成，所有这些都应该发送到一致的DIP。与以前的设计不同，Connor的本质可以轻松支持多连接状态。3)现代云和边缘服务器可能在计算，存储和带宽方面具有异构能力[34，38]。由于服务器的故障或负载动态变化，Conventional可以快速响应重量变化我们做出了几项重要的智力贡献：一种快速轻量级的软件云负载均衡器SoCC181(1) Conclusion的工作流程旨在实现内存效率、高吞吐量、负载平衡、一致性和无错误命中。(2) 我们提出了一种新的方法来维护控制平面中的动态状态集，并可以立即产生新的查找结构来更新数据平面，根据DIP池的变化。(3) 在LB的基础上增加了加权随机发生器和海量连接状态维护(4) 我们使用DPDK [2]实现了Contrast，并在两个实际网络中展示了其高性能。我们还建立了一个P4原型，以显示其兼容性可编程开关。 源代码可以在这里访问[14]，我们的结果可以重新生成。与现有的有状态LB相比，Conclusion实现了文献中报告的最高数据包处理吞吐量（在廉价台式计算机上使用单线程67.2Gbps（<800美元，不包括100 GbE NIC））和低内存成本，0错误命中。 我们认为Conclusion是一项重大改进，因为它实现了三个方面的最佳效果：性能、成本效益和一致性（正确性）。它适用于新的应用程序和系统。它还包括一个理想的解决方案，lution的动态状态维护，是有用的其他网络功能。本文件的其余部分安排如下。第二节介绍了相关的工作。 我们在第3节中正式建模LB算法。第四节介绍了一些背景算法。我们在第5节中介绍了混凝土的详细设计。 系统实施和评估结果见第6节。 我们在第7节中结束这项工作。这项工作不会引起任何道德问题。2相关工作LB是数据中心网络的重要组成部分，它将传入流量分配到不同的后端服务器或其他网络功能[7，23，25，32，36]。传统的硬件负载均衡器昂贵且不灵活。因此，许多大型云服务选择使用软件负载均衡器[7，12，23，25，32]。此外，LB还这对于边缘数据中心很重要[17，34，35，41]，它允许通往远程云的路径上的异构设备提供存储和计算资源。有状态负载平衡器。 Ananta [32]是一个三层架构的软件状态LB，包括运行ECMP的数据中心路由器，商品服务器上的许多软件多路复用器（SMuxes），以及每个后端服务器上的主机代理。然而，每个Ananta实例提供非常慢的数据包处理速度，如[25]所示Duet[25]使用了在通用交换机上的转发和ECMP表来存储VIP-DIP映射。在频繁更换DIP池的情况下，Duet可能无法维持PCC [28]。Maglev [23]是GoogleMa- glev的核心算法是使用一个哈希表来存储连接作为负载平衡的哈希表，以及一个新的一致性哈希算法来适应DIP池的变化。SilkRoad [28]在最先进的可编程交换ASIC上实现LB功能，这需要超过50MB的SRAM。它支持低延迟的高容量流量，并保持一致 性 。 部 署 SilkRoad会 带 来 额 外的 硬 件 成 本 ， 每 个SilkRoad交换机的成本为6.5K美元，每个群集需要多个此外，Maglev和SilkRoad在连接查找过程中可能会包含错误的命中，这是由于使用了查询器而不是完整的状态信息。错误命中导致两个主要问题。1）分组可能被转发到不提供其VIP的正确服务的DIP，然后失败。2）多个状态可以共享表中的摘要。很难决定何时删除摘要。删除已完成状态的摘要可能会终止活动状态，如果它们的摘要发生冲突。因此，表的大小可能会随着时间的推移而爆炸，或者某些活动状态可能会终止。在上述方法中，可用于维护状态的 典 型 数 据 结 构 是 Cuckoo Hashing[31]。 Bonomi等人提出了使用近似并发状态机（ACSM）来维护动态网络状态[19]，但该方法不能用于LB。 我们在表1中比较了Conclusion与现有的有状态LB，其中实验值基于6.2中的DIP-V 16 M状态网络。无状态负载均衡器。 Beamer [30]和Faild [17]是最近提出的无状态LB。它们的转发逻辑不存储连接状态，而是使用简单的映射算法（静态或一致性哈希）。它们在每个数据包报头中写入一个新字段来携带其DIP。 终端服务器需要检查每个数据包报头，以确保数据包与此服务器上的状态一致。 如果不是，则服务器执行覆盖重新路由到正确的DIP。 这种方法需要对每台服务器的网络堆栈进行内核修改，以添加额外的网络处理。因此，计算和存储器开销被转移到服务器侧并且基于每个分组。当状态是短期的时，覆盖重新路由可能不是一个重要的问题。然而，对于长期的多连接状态，无状态LB可能导致大多数有状态分组的重新路由，因为在一段时间之后，映射将变得非常不同。与这些方法相同，Conclusion只要求每个服务器在应用层运行一个轻量级的状态跟踪程序，这不会改变网络堆栈。有状态LB和无状态LB的性能比较是完全一样的，因为开销发生在不同的地方。我们不打算宣布有状态和无状态LB之间的明显胜利这项工作的目的是提高SoCCShouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang，andChen Qian182LB算法存储器加权假数据包类型Extra更新表1：有状态LB算法与示例结果之间的比较。数值来自使用1M并发连接的微基准测试。更多结果可以在费用6中找到。具有不同DIP的服务器图1：有状态LB的一般模型有状态LB设计，并将有状态和无状态LB之间的选择留给网络运营商。3系统模型和假设云/边缘数据中心提供的服务由公共可见的IP地址标识，称为虚拟IP（VIP）。客户端向VIP发送服务请求。LB在云/边缘服务器之间平衡负载，因此没有服务器过载并中断服务。 每个后端服务器由一个直接IP（DIP）标识。因此，LB的核心功能是基于分组的报头信息（例如，其5元组或其它状态标识符）。每个VIP与其DIP池相关联，该DIP池包括提供由VIP标识的服务VIP的DIP池可能会因服务规模和环境（云或边缘）而异如果服务器维护数据包的状态，则必须将数据状态可以是正在进行的连接或多连接。实现费用1中所述的LB的所有要求是挑战。简单的无状态算法（如这是因为当DIP池或权重发生变化时，分发算法需要改变，然后有状态的数据包可能会映射到另一个服务器。最近的有状态LB设计[23，28]需要存储连接状态，并确保所有与状态匹配的数据包一致地映射到同一DIP。我们总结了有状态LB的一般模型（如图所示）1）分析了该模型的组成部分，并指出了设计目标。1. LB数据平面（LB-DP）。LB-DP处理分组并为携带VIP的每个分组找到DIP。DIP应从VIP后面的DIP池中选择，代表提供此VIP服务的服务器集核心算法应该提供两个 功 能 ： i ） 为 每 个 有 状 态 分 组 找 到 对 应 的 服 务 器（DIP），以及ii）基于每个无状态分组的给定权重分配可用服务器（DIP）LB-DP的设计目标是实现高分组处理吞吐量和存储器成本的效率，因为高速存储器在商品服务器（缓存）和硬件交换机（ASIC）上都是宝贵的此外，LB-DP应该基于反映每个服务器的当前容量的权重来平衡无状态分组，其可以是异构的和动态的。例如，如果一个服务器正在为许多大型连接提供服务，那么在不久的将来，它必须比其他服务器接收更少的新状态。因此，我们将“权重”确定2. LB控制平面（LB-CP）。LB-CP从服务器接收状态改变，包括新的状态建立和状态移除。许多现有设计使用TCP SYN分组作为新状态的指示符，并且允许LB-DP直接通知LB-CP [23，28]。但是，它不适用于UDP或多连接状态。LB-CP的设计目标是有效地维护传入分组的所有状态，并且一旦需要LB-DP更新，则快速构造新的LB-DP以反映分组一致性。确保连接的所有数据包都传递到同一台服务器对于LB至关重要，因为恢复断开的连接通常需要很长时间，并且会严重损害用户体验。 在没有统一数据管理层的边缘或云中，来自单个设备的不同流的数据包应该被发送到同一台服务器。实现设备级一致性可以避免许多新兴应用（如媒体卸载）的3. 更新. LB-CP将通知LB-DP在某些网络动态下进行必要的更改，例如DIP池和权重更改。更新过程的设计目标是降低更新频率，因为它将中断LB-DP上的分组处理。2. LB控制平面维护状态并计算数据平面3. 更新1. LB数据平面将DIP确定为每个数据包都有目的地的数据包（百万分之一秒）（MB）LB安打硬件中断ECMP+哈希表（Ananta[32]）低高不清楚没有任何类型没有频繁哈希表w/ digest（Maglev[23]）14.6318.63是的存在仅TCP没有频繁多HTs w/ digest（SilkRoad[28]）16.114.36没有存在仅TCPASIC频繁一种快速轻量级的软件云负载均衡器SoCC183布卢米耶结构ℎ���������ℎ������111分10秒=01���1ℎ���������ℎ���00美元？你说呢？���6图2：Bloomier过滤器(a) 查找构造过程中已知的键：指定结果(b) 查找构造过程中未知的密钥：确定性随机虽然Conventional需要服务器发送状态通知，但服务器不需要像现有的有状态LB那样维护任何状态 在其他设计中，服务器到LB消息对于加权负载平衡是必要的[25]。4背景算法我们建议使用最小完美散列的数据结构和算法[18，20，21，27，39]用于ConclusionLB。一种众所周知的基于完美散列的数据结构是Bloomier过滤器[20，21]。最近提出的奥赛罗散列[39，40]利用Bloomier过滤器来支持可编程网络中的转发信息库，包括Bloomier过滤器的变体作为其数据平面，其控制平面中的构造程序，作为两个平面的交互协议。Othello发现了一组Bloomier过滤器，以实现动态网络环境的良好时间/空间权衡。虽然Othello不是为LB设计的，但它非常适合LB，原因有三：1）Othello数据平面的查找速度超快，内存效率高;2）查找无冲突，尽管数据平面中没有存储完整的密钥;3）我们设计了控制平面到数据平面之间的简化更新算法，同时始终保持PCC和加权负载平衡。 我们在本节中说明了前两点，第三点在费用5中详细说明。Bloomier过滤器不是用作过滤器，而是一组键值对的映射。 设S是键的集合，并且n= |S|. 每个键的查找返回映射到该键的l位奥赛罗控制平面中的Bloomier过滤器结构。我们使用图2中的一个例子来展示一组五个键值对的Bloomier过滤器。密钥k1到k5中的每一个具有对应的l位值。两个数组A和B分别由ma和mb元素构建，其中ma=n，mb= 1。33n.数组的每个元素都是一个l位值.在该示例中，l= 2，并且为了更好地说明，假设m=ma=mb=8。 对于A中的每个值i，我们放置一个顶点ui，对于B中的每个值j，我们放置一个顶点wj。两个散列函数ha和hb用于计算[0，m -1]中所有键的整数散列值。然后，对于每个键，我们在对应于其哈希值的两个顶点之间放置一条边例如，ha（k1）=6和hb（k1）=5，因此放置一条边以连接u6和w5。对于密钥k及其对应的值v，Bloomier的要求为：图3：Bloomier过滤器两个连通元素A[ha（k）]<$B[hb（k）]=v，其中，k是逐位异或（XOR）。对于该示例中的密钥k1，u6w5=012=1。灰色的顶点表示不关心的元素。请注意，在为所有键放置边之后，称为图G的二分图需要是非循环的。证明了如果G是非循环的，则找到一个有效的元素赋值使得所有键的值都满足是平凡的[39]。如果找到一个循环，则构造需要找到另一对散列函数来重新构建G。 证明了在构造n个密钥的过程中，期望的重散列总数为<1。51当n = 0时。75米 [39]。构造n个键的G的预期时间成本是O（n），删除或更改键的时间是O（1），添加键的时间是摊销O（1）。该设计可以简单地扩展到l>2。在奥赛罗数据平面中查找Bloomier过滤器。 奥赛罗查找结构只是一个包含两个位图A和B的Bloomier过滤器，如图所示第3（a）段。为了查找k1的值，我们只需要计算ha和hb，它们映射到A的位置6和B的位置5（从0开始）。然后，我们计算两个位的逐位XOR并得到值012。因此，查找结果是τ（k）=a[ha（k）]b[hb（k）]。查找是内存高效和快速的。1）数据平面只需要维护两个数组。 键本身并不存储在数组中. 因此，空间成本很小（每个键2 m/n）。2）每次查找仅花费两个存储器访问操作来从A和A中的每一个读取一个元素，B. 它适合可编程网络架构：数据平面只需要存储查找结构，两个数组，而控制平面存储键值对和无环二分图G。当有任何变化时，控制平面更新两个数组，并让数据平面接受新的数组。当一个Bloomier过滤器在构造过程中查找一个不存在的键时，返回任意值。例如图3（b），k6gS并且其结果可以是任意值。我们将利用这个性质来构造一个加权随机发生器。应该注意的是，更新可能需要重新散列，尽管发生的概率很低（O（1/n）），但仍然需要O（n）时间，并且可能会给控制平面响应时间带来显著的延迟。因此，我们提出了一个先进的������ ������ ������ ������ ������ ������ ���������������4���2������53���1���������������������������������������������������6���值a（刚果（金）���10165���21010���31112���400130100110100110100111110 01101110 01101110 0110SoCCShouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang，andChen Qian184数据包的VIP索引：iVIP阵列存储VIP索引到BAS地址BAS-1控制平面更新一组钥匙S。在Conclusion中，每个键都是状态的标识符，即，五元组与键对应的值是DIP代码（Dcode），它最终将转换为DIP地址，即持有状态的后端服务器的地址注意VIPvi的BAS的内存地址5-分组元组BAS-2…BAS-i…l位DcodeDIP阵列2D阵列DA：DA[i][Dcode]=DIPBloomier滤波器提供状态到DIP映射，并不真正存储密钥。因此，存储器成本显著降低。有两种可能的方法来构造CONSTANT的状态到DIP查找结构1）所有VIP共享一个图4：Conclusion数据平面的工作流程称为OthelloMap的数据结构，它始终在控制平面中维护最新的查找结构，以将响应时间限制在微秒级，如费用5.4中所述。5并发设计5.1系统概述符号。设M为网络中VIP的数量。每个VIPvi被分配索引i，并且其DIP池包含ti个DIP。VIPvi的状态数是ni。连接遵循费用3中介绍的DP模型，包括数据平面和控制平面。Concury-DP数据平面（Concury-DP）的输入是其目的地地址是VIP的分组，并且输出是其目的地已经被DIP替换的相同分组在每个后端服务器（由DIP标识）处，存在跟踪该服务器处的当前状态的轻量级应用层程序，其已用于现有数据中心LB [25]。状态跟踪程序将向Concurry控制平面（Concury-CP）报告新的和终止的状态。Concury-CP仅在VIP的DIP池发生变化时才更新Concury-DP，即，服务器故障/添加和服务器权重更改。该更新仅适用于Convention-DP的一小部分 设计目标已在费用3中讨论。设计concept的挑战。Conclusion的一个关键创新是放弃了现有LB设计中传统的先查找再分发的工作流程，而采用了一种同时实现“查找”和“分发”的新方法。然而，布鲁米尔和奥赛罗最初并不是为LB设计的。应用Bloomier的挑战包括：1）如何针对活动状态查找和加权随机发生器两者调整Bloomier; 2）如何设计数据平面以最小化存储器成本并最大化吞吐量; 3）如何在不修改服务器网络栈的情况下解决错误命中问题;以及4）如何放宽对数据平面中的每个新状态的更新的要求5.2连续数据平面Conclusion使用Bloomier滤波器作为表示状态到DIP映射的查找结构和加权随机化器。如费用4中所介绍的，Bloomier过滤器基于以下内容构建：lookup结构2)每个VIP都有一个单独的Bloomier过滤器作为查找结构，称为Bloomier数组集（BAS），它只存储该特定VIP的状态到DIP的映射。这需要M个基础。 我们使用这种方法而不是单个和统一的BAS，因为：1）在VIP的DIP池改变时，仅需要更新该VIP的Dcode。其他人保持不动。2）分离不同的VIP进一步确保分组不被转发到另一VIP池中的DIP3）实验结果表明，分离查找结构比统一查找结构的查找速度快5%注意，维护每个VIP的结构也可以由其他有状态的LB（如Maglev [23]）使用，以避免交叉贵宾的问题。但是，它仍然不能解决费用2中提到的摘要删除问题. concept是独一无二的，因为它可以处理这两种类型的问题。Conclusion数据平面的工作流程如图所示。4，包括三个主要步骤。查找操作简单而快速，只包括四个读操作和哈希计算。步骤1. 当Connected接收到数据包时，它首先使用数据包报头中的VIP vi通过查找表或计算来获得VIP索引i。由于VIP由边缘/云运营商确定，因此可以简单地为所有VIP分配单个前缀，例如，22位前缀，则VIP的最后10位可用作VIP索引，支持1K VIP。Conclusion使用索引为VIP索引的静态数组维护一个VIP数组，该数组存储不同BAS的内存地址步骤1的结果是VIPvi的BAS的存储器地址。数组很小，而且是静态的。步骤2. 使用来自步骤1的存储器地址，Conclusion找到VIP v i的BAS，表示为BAS-i。BAS-i仅包括两个数组A和B以支持查找结果τ（k）=A[ha（t）]<$B[hb（t）]的计算，其中t是k的4元组，与5元组相比没有目的地IP地址结果是称为DIP码的l位值，表示为Dcode。每个DIP码将在步骤3中映射到实际DIP，并且它是多对一映射。 两个不同的DIP代码可以被映射到单个DIP。步 骤 3. 此 步 骤 使 用 l 位 Dcode 查 找 实 际 DIP 。Conversion维护一个称为DIP数组的2D数组，用DA表示。元素DA [i][Dcode]是VIP v i的Dcode的DIP。 这个2D数组与当前状态的数量无关，并且不需要太多内存。假设有一种快速轻量级的软件云负载均衡器SoCC185512个VIP，l=12。内存成本约为2MB。注意，Dcode的任何1位值的DA[i][Dcode]是VIPvi的有效DIP。为了进一步降低存储器成本，DA[i][Dcode]可以是DIP索引，其可以通过一个或多个静态表查找被转移到DIP。数据平面复杂度分析与比较。1) 时间成本。Concury-DP非常简单和快速。每个查找都是O（1）的，包括最多6个静态数组的读操作，2个哈希计算（每个32位）和一个XOR计算。这个成本小于Cuckoo+ digest，一种常用的LB表设计[23，28]，它需要更多的读操作和有状态和无状态数据包的哈希计算。2) 空间成本。设n是总状态的数量，ld是Dcode的长度，并且lv是DIP表中的DIP索引的长度。Concury-DP的总内存开销为2。33ldn+ 64m+ 2ldlvm+ 48·2lv bits，在实际系统中比Cuckoo+digest小得多5.3加权负载平衡使用DIP代码的原因 人们可能会注意到，为了处理新状态的第一个数据包，Conclusion获取Dcode，然后将其转换为DIP，而不是直接将DIP作为BAS的查找结果。我们的方法降低了存储成本，因为DIP是32位长，而DIP码可以短得多，例如，10位。不同DIP码的总数2ld可以大于DIP的数量，例如，超过一个数量级，以便为加权随机发生器提供粒度Dcode到DIP的映射由LB想要如何在该VIP的DIP之间分配权重来确定例如，如果Dcode具有4个比特并且存在4个DIP并且所有DIP具有相等的权重，则我们可以将[0000，0011]中的Dcode映射到DIP1，将[0100，0111]中的Dcode映射到DIP2，将[1000，1011]中的Dcode映射到DIP 3，并且将[000，011]中的Dcode映射到DIP3。Dcodein [1100，1111] toDIP4.我们可以把Dcode看作一个球，把每个DIP看作一个bin。如何实现加权负载均衡。我们首先表明，对于一个未知的状态，BAS将返回一个特定的Dcode的概率是均匀分布在所有可能的值的Dcode。对于新的状态c，BAS的查找结果是Dcode=τ（c）=A[ha（c）]B[hb（c）]，其中A[ha（c）]和B[hb（c）]都是1比特值。假设A[ha（c）]（B[hb（c）]）是数组A（数组B）中的任何元素的概率相等，如果ha和hb是均匀散列，则为真。A或B中的每个元素可以是“确定的”或“自由的”。确定的元素对应于如图1B的示例中的白色顶点2，其值在构造期间应该是固定的，以提供对当前状态的A ‘free’ ele- ment我们为每个自由元素分配均匀随机值结果，如果A[ha（c）]和B[hb（c）]都被确定，则D代码被确定。如果A[ha（c）]和B[hb（c）]之一是自由的，则Dcode是随机的。我们知道A和B都有m个元素，A [ha（c）]和B[hb（c）]有m 2个可能的对。 其中只有n对产生确定的Dcode值，其比例为n/m2<1/n.因此，只有一小部分的结果是确定的，其他的可以被认为是均匀随机的。我们使用实证结果来验证这种一致性。图 五是典型的例子。我们让值的长度l=10。因此，存在1024个可能的D码。我们列举了A和B的索引的所有可能的组合，并计算 得 到 的 D 码 。 Conclusion 中 使 用 的 哈 希 函 数 是CRC32。 我们观察到，使用Conclusion，组合（无状态数据包）非常均匀地分布到不同的Dcode，最小值、10%、平均值、90%和最大值分别为925、980、1024、1066和1120。 其他实验的结果也类似。我们比较了MD5和SHA256。虽然MD5和SHA256不是严格统一的，但它们在实践中被认为是足够统一的 我们表明，CONCENTRAL是可比的，他们的均匀性，是足够好的，在实际系统中使用。 我们进行了两个著名的统计检验 ， 卡 方 检 验 和 Kolmogorov-Smirnov 检 验 ， 以 比 较CONSTRUCTION，MD5和SHA 256与均匀分布。如图6和7，它们中的每一个都失败了大约或少于10%的测试，因为它们不是严格一致的。Contrast并不比MD5或SHA256，特别是当Id>11（Dcode count> 2048）时。在在我们的实现中，我们设置ld=12。 我们将在费用6.4中进一步评估DIP的负载分布。基于均匀Dcode分布，我们可以使用Dcode-DIP映射来实现加权随机发生器。Dcode的数量应该大于一定规模的DIP，例如>8倍。然后，DIP的重量由表DA中的条目数反映。例如，如果DIPd1的权重为1.0，而DA拥有100个指向d1的条目，那么对于权重为2.0的DIPd2，DA应该拥有200个指向d2的条目。如果d2接近满，这是不太可能的，那么d2的权重应该降低以反映其当前的剩余容量，新连接以较小的概率转到d 2。 这种权重变化将导致Conclusion的控制平面和数据平面之间的完全同步，详见费用5.5。5.4连续控制平面Concurry控制平面（Concury-CP）的任务是双重的：1）跟踪现有状态;以及2）当需要数据平面更新时，生成新的数据平面结构，主要是新的BS一个简单的解决方案是使用哈希表来存储一组状态DIP对。update时SoCCShouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang，andChen Qian186孔塞Sha-256MD5孔塞Sha-256MD5失败率（%）失败率（%）DP施工时间（ms）我500050 5050400040 404030002000100000256512Dcode索引768102430201001024 2048 40968192Dcode数量30201001024 2048 40968192Dcode数量30201008K16K32K64K 128KVIP的状态列表图5：Dcode的无状态数据包分发图6：卡方检验图7：Kolmogorov-Smirnov检验图8：Concury-DP配置的响应时间������（电子元件C[n]中的元素，比如说C′，DIP′，到C[j]。然后将BASO中c′对应的值从n修改为j。 这个过程需要O（1）时间。Concury-CP的内存开销分析。让我成为���OthelloO获取C更新Othello以添加/删除元素数组C用于存储状态-DIP映射索 引 i 和 lk 的 长 度 是 每 个 状 态 DIP 对 信 息 的 长 度 。Concury-CP的内存开销为2。33 lin+（lk+ ld）n +64 m+2 ld lvm +48·2 lv，其中2. 33lin图9：OthelloMap的更新/更新需要时，新的BAS从该集合构造。我们的创新的想法是设计一个新的数据结构，称为OthelloMap，维护所有当前状态的状态DIP对和BAS注意，如果网络包括M个VIP ， 则 控 制 平 面 具 有 M 个 OthelloMap 。 使 用OthelloMap的目的是在网络动态发生时快速生成新的OthelloMap的组件。如图9所示，VIPv的OthelloMap包括两个部分。1)一个大小为n的数组C，其中n是VIPv的当前状态数。C的每个元素存储一个状态DIP对。2）使 用当 前 状态 的 集合 构 造的 BAS0 使 用状 态 标识 符（ID）c的O的查找结果是索引i，使得C[i]存储c的状态DIP对。注意i的长度不小于2n位的将查询设置为OthelloMap。 集合查询是OthelloMap的一个基本功能。输入是一个可能的状态IDc′，输出是相应的DIP或为了进行集合查询，OthelloMap使用c′查找BASO并获得值i。 如果状态存在，则C [i]包括DIP。否则，存储在C [i]中的连接不匹配c ′。因此，它可以返回“不存在”。这个过程需要O（1）时间。添加/删除OthelloMap。为了向OthelloMap中添加一个状态DIP对，DIP，我们首先应用一个集合查询c。如果c存在，则将C[i]修改为c，DIP。如果c不存在，我们将存储c，DIP，到C[n+1]。然后我们把BASO加上n+1，n + 1。这个过程需要O（1）时间。 为了从OthelloMap中删除一个状态-DIP对c，DIP，我们应用一个集合查询c。如果c不存在，我们什么也不做否则，c及其DIP存储在C[j]中。我们将它们从C[j]中删除，并将是BASO的开销，（1k+1d）n是阵列C的开销，剩余的用于需要更新到数据平面的VIP阵列和使用OthelloMap提高性能。我们比较的时间来构建一个 新 的 DP 和 没 有 OthelloMap 。 结 果 如 图 8 所 示 。OthelloMap将Conversion更新期间控制平面的响应时间了50%以上。