2023-03-30

FLash-2

字数统计: 4.2k字 | 阅读时长: 15分

Flash-解决更新风暴、长尾到达的最新数据平面验证-学习3

本次是Flash实验评估

评估

回答四个关键问题
（1）在具有大量更新的真实世界大型网络中，Flash的性能如何？Flash在不同设置下的性能有多强？（§5.2）
（2）根据真实路由的FIB更新的到达模式，Flash的性能如何？（§5.3）
（3）每种优化技术如何有助于整体性能的提高？（§5.4）
（4）就计算需求而言，Flash的开销（成本）是多少？(§5.5)

实验设置

快速IMT命名方式：A-B，其中A代表网络拓扑，B代表FIB生成
示例：LNet-apsp
<1>该设置使用LNet拓扑，这是一种基于Fabric网络架构的专有网络
<2>FIB规则是通过运行全对最短路径算法生成的。
CE2D命名方式：A-B-C[-D]，其中A表示网络拓扑，B表示FIB生成，C表示要验证的属性（所有对可达性和环路自由度），可选的D（如果存在）表示存在长尾到达。
示例：I2-OpenR/1buggy-loop-lt
<1>使用Internet2拓扑
<2>FIB规则是由真正的OpenR软件生成的，除了一个交换机，它正在运行一个有缺陷的OpenR实例
<3>所述验证器被配置为检查所述循环自由度要求
<4>存在长尾到达
所有的设置如下图（包含数据集信息）

实验环境设置
8个vCPU(2.5GHz)和32GB内存的Ubuntu云服务器上进行的。
操作系统是Ubuntu（x64）18.04。
安装了OpenJDK v17.0.3的LTS

代码配置(已开源)
https://github.com/snlab/flash 
大约4000行java代码

Flash设备代理实现
设备代理（如果需要一致的早期检测功能）可以通过修补现实世界生产网络中采用的开源模块化路由平台来实现。特别是，在评估中以开源路由软件OpenR[33]为平台。
OpenR：https://github.com/facebook/openr
OpenR是一种状态同步协议，它将其状态变量（即Adj、Prefix）存储在K-V存储中，并使用决策和Fib模块计算路由。
扩展有大约150行C++代码。通过扩展，从相同的网络状态计算的规则更新被封装到带有标签的Thrift[46]消息中，并被发送到验证系统。

Flash也实现了Delta-net、APKeep、APKeep*进行实验对比

评估基准

评估1：在大规模网络(LNet-ecmp和LNet-smr)中评估

作者通过将所有交换机的规则插入放在一个序列中来生成更新，将更新序列提供给验证器，并测量执行时间和内存消耗来构建反向模型。如果执行时间超过10小时，我们将终止JVM。
实验结果图：如下图6所示
我们很容易看到：
LNet-ecmp和LNet-smr的Flash(绿色)分别在19秒和4秒内完成，而Delta-net*(蓝色)和APKeep*(橙色)都无法在10小时内完成。
因此，对于LNet-smr，Flash的性能优于Delta-net*和APKeep*9000倍（10小时除以4秒）。
Flash（绿色）的内存消耗也大大降低（在两种设置中都高达2个数量级）。虽然设置看起来很极端，但当验证器正在引导或按需运行时（例如，用于网络规划或虚拟私有云的可达性分析），确实会发生这种情况。
因此，我们得出结论，Flash对于大规模网络中的数据平面验证来说是快速且高效的。

评估2：快速IMT的优势和稳健性。

作者分析了快速IMT作为一种独立的模型构建方法的好处，通过将子空间划分思想应用于大型网络中的Delta-net*和APKeep*，因为子空间划分可以广泛有效地用于大型网络。
除了执行时间和内存消耗外，作者还计算了每个评估设置的断言运算数量.
实验结果表：如下表3所示
我们很容易看到：
名为“LNet-smr子空间”的行显示了将子空间分区应用于LNet-smr中的所有子空间时的结果。
我们观察到Delta-net*和APKeep*的模型更新时间更长，分别是LNet-ecmp中Flash的1.4倍（26s/19s）和1895倍，以及LNet-smr中的71倍（285s/4s）和251倍。
在这两种设置中，Flash的内存占用空间也较小。Flash在LNet-smr中使用15MB，而Delta-net*和APKeep*分别使用6792MB和31MB。
除了LNet-apsp子空间设置外，Flash还大幅减少了断言运算的数量（LNet-ecmp中的Delta-net*和APKeep分别为20倍和681倍，LNet-smr中分别为26倍和4倍）。

完整性评估
作者使用较小的网络，并报告文献中广泛使用的三种设置的结果：Airtel、Stanford跟和I2。
表3的最后3行显示了结果。我们可以看到，APKeep*的模型更新时间是Flash的4.8-6.5倍。
在这种较小的网络中，Delta-net*表现最好，模型更新时间仅为Flash的30-90%。对于一些大型网络也是如此，例如LNet-apsp子空间。
然而，我们看到Delta-net*的断言运算数量高于Flash（在Airtel跟踪中高达141倍）。
可能原因
Delta-net*的效率来自于其简单、高效的数据结构，它可以有效地处理基于前缀的规则。然而，如LNet-smr和LNet-ecmp结果所示，对于非前缀规则，这种表示可能遭受显著的性能退化

评估3：与CE2D合作时块大小阈值的影响。

由于更新可能在实际中不断到达，Flash可以选择更新反向模型，并在处理所有规则更新之前执行CE2D。
此行为由块大小阈值（BST）参数配置B, 这迫使Flash在处理等于或大于B规则更新。
为了了解此参数如何影响Flash的性能，作者改变了BST值，并测量了表3中使用的设置的模型构建时间。
实验结果图：如下图7所示
x轴表示BST值和FIB量表的比例，因为FIB量值决定了我们评估中的更新次数，并且在每个设置中变化很大。
y轴是归一化的模型更新速度，计算为T基线/Tx，它对模型更新速度与基线相比的速度进行分类，其中BST值是无限的，并且在处理所有更新之后更新模型。
作者观察到：
<1>随着阈值的增加，总体趋势是模型更新速度将增加并保持在相对较高的水平。
<2>在x≈0.04的情况下，大多数设置可以达到基线的60%以上和>100%（LNet-apsp、LNet-ecmp和I2-trace）效率。
<3>唯一的例外是LNet-smr子空间，当x≈0.04时，它仅达到～0.2，当x≈0.5时，它才达到＞0.8。
<4>由于Flash在LNet-smr子空间中的加速大于70倍，因此Flash的速度仍然可以达到最先进的14倍以上。
因此，我们得出结论，快速IMT在具有更大的块大小阈值的情况下更有效。然而，当阈值不小于FIB规模的4%时，仍然可以获得性能改进。

评估4：CE2D评估，证明其在极端环境下的有效性、性能优势和稳健性。

实验设计：
<1>首先进行评估，以验证CE2D可以提供一致的早期检测结果。具体来说，我们使用I2OpenR循环设置运行模拟。我们使用Mininet来构建具有Internet2拓扑结构的网络。一个真正的OpenR实例在每个交换机上运行，并通过主机网络连接到Flash。
<2>通过在Mininet中连续关闭两个链路（chic-alta和chic-kans）来触发FIB计算。
作者将CE2D与两种策略进行了比较：
<1>每次更新验证（PUV），它在处理单个规则更新后检查属性
<2>块更新验证（BUV），其在处理更新块后检查性质。
作者在验证器上记录每个交换机的FIB更新时间，以及验证器报告确定性结果的时间。
实验结果图：如下图8所示
结果分析：
交叉点（x，y）表示在时间x接收到交换机y的FIB更新，因为链路断开事件被触发，并且颜色指示epoch标记。点（x，y）表示验证器策略y在时间x报告确定性结果，其中橙色表示有循环，蓝色表示没有循环。
<1>两个同时发生的链路故障在每个交换机上多次触发FIB重新计算。对于PUV和BUV，验证器报告两个瞬态循环（橙色点），这与最终验证结果不一致。
<2>Flash不会报告假阳性错误，并保证验证结果是一致的。

评估5：CE2D对长尾到达的好处。证明当长尾到达发生时，CE2D可以提高多少性能。

实验设计：
<1>在发生循环的两种设置中评估了CE2D的效果：I2-OpenR/1buggy-loop-lt，I2-track-loop-lt。
<2>对于每个设置，我们运行50个独立的随机试验，在每个试验中，我们通过配置一个随机节点在发送更新之前延迟60秒来模拟长尾效应。
<3>测量Flash报告确定性结果的时间。
实验结果图：如下图9所示
结果分析：
x轴是报告时间，y轴是累积分布函数（CDF）。将x轴的范围限制为[0ms，1000ms]：如果曲线在1000ms时没有达到y=1，则在60s时，即在接收到来自阻尼节点的更新后，会获得结果。
<1>点(153.7ms,0.68)位于I2-OpenR/1buggy-loop-lt的曲线上，这表明Flash在68%的试验中可以在不到153.7ms的时间内检测到环路，这比60s的基线要小得多（>390×）。
<2>在I2-track-loop-lt中，Flash可以在所有试验中在760ms内早期检测到环路，从而实现79倍的加速。
因此，我们得出的结论是，在长尾到达时，CE2D的改善可能相当普遍（68%至100%）和显著（79至>390）。

评估6：多重阻尼交换机的影响。即研究了当存在多个阻尼交换机时对CE2D的影响。

实验设计：
<1>作者使用I2-track-loop-lt设置，该设置使用来自Internet2数据集的真实网络拓扑和更新序列。
<2>作者列举了阻尼设备的数量D从1到7。对于每个D，作者将Flash配置为使用CE2D检查循环，并运行50个独立的随机试验。
实验结果图：如下图10所示
结果分析：
<1>在72.5%（即145/200）的情况下，Flash可以在800ms内检测到一致的环路，其速度是完整验证的75倍。
<2>阻尼设备D随着时间的增长，成功的一致性早期检测的概率变得更低。例如，当D≤3时，CE2D在超过90%的情况下仍能在800ms内检测到误差，D=7约20%的情况下，即77.8%的交换机被阻尼。
因此，我们得出结论，即使在数据平面的有限和部分知识的情况下，CE2D也可以早期检测到错误。

评估7：大规模网络中PAT的影响。

实验设计：
通过分析表3中的结果，我们展示了持久行动树（PAT，见§3.4）的效果。总的模型更新时间包括创建和删除等价类的时间（表示为Tec，由Flash中的持久操作树（PAT）处理，与断言操作的数量无关），以及处理断言的时间（称为Top）。
结果分析：
在表3中，我们看到，在前3个大规模网络设置中，模型构建时间的改进大于Flash对APKeep*的#断言运算的改进，例如，LNet-apsp分别为15x和5x。
原因是在较小的网络中，模型构建时间由Top主导，性能增益主要来自于#断言运算的减少。同时，在大型网络中，Tec在整体性能方面占据主导地位，Flash从PAT的性能增益中获益更多

评估8：MR2的影响。即为了更好地理解MR2（§3.2）如何对Flash的整体性能增益做出贡献

实验设计：
<1>作者对模型构建中的3个阶段进行了细分分析：计算原子覆盖（Map）、覆盖聚合（即Reduce I/II）和应用覆盖。
<2>作者测量APKeep*、Flash和Flash变体（称为Flash（逐条规则更新模式））每个阶段的总时间，其中块大小阈值设置为1。
实验结果图：如下图11所示
结果分析：
图11显示了APKeep*、Flash（每次更新模式）和Flash在I2-track中的时间细分。
<1>虽然Flash引入了一些覆盖聚合的开销（0.42s），但与APKeep*相比，计算原子覆盖（3.85倍）和应用覆盖（12.30倍）的速度加快了。
<2>在Flash（每次更新模式）中应用覆盖所需的时间（4.84s）比APKeep*（4.55s）更长，因为交叉乘积计算并没有针对单个规则更新进行优化。
因此，我们得出结论，通过覆盖聚合，MR2使Flash能够通过大幅减少计算无原子冲突模型覆盖和应用聚合覆盖的时间来提高性能。

评估9：递减验证图的效率。即展示了使用递减验证图方法（§4.2）对基于正则表达式的需求执行一致早期检测的效率

实验设计：
<1>作者使用LNet-apsp子空间设置并检查所有对ToR到ToR的可达性。
<2>Flash总共生成5376个验证图，每个子空间验证器生成48个验证图。每个交换机的规则插入都打包为一个batch。
<3>作者在处理每个batch次后验证可达性，并使用（1）递减图查询（DGQ，见§4.2）方法和（2）模型遍历（MT，即使用深度优先遍历从每个源ToR遍历模型）来测量单个子空间验证器的验证执行时间。
实验结果图，如下图12所示
结果分析：
图12显示了验证时间的CDF。
<1>DGQ（蓝色）比MT（橙色）更靠近y轴。DGQ和MT的中位数、平均值、99%和最长时间分别为0.58/0.84/4.74/19.57ms和772.98/1522.22/5513.76/7466.87ms。
<2>与MT相比，Flash将99%的执行时间提高了~1163×（4.74ms vs.s.5513.76ms）。
因此，我们可以得出结论，递减验证图方法大大提高了基于正则表达式的需求的验证性能，并实现了高效一致的早期检测。

评估10：计算开销

实验设计：
两种部署
<1>部署专用服务器以进行持续验证的设置
结果分析：
对于LNet-ecmp，Flash为每个pod划分一个子空间，因此总共有112个子空间。
每个子空间验证器需要1 (v)个CPU，211MB内存用于反向模型，336MB内存用于验证图，以检查所有对ToR可达性，并且每台机器需要<4GB内存来运行JVM并存储规则。
因此，总计算开销为112 (v)个CPU，<62GB（61.26GB）（用于模型和验证图）+4GB（用于规则和JVM）内存。
如果子空间验证器部署在k个具有专用资源的机器，每台机器需要112/k (v)CPU和62/k + 4GB内存。
为了了解数据中心的资源成本，我们在2022/7/1应用了AWS EC2（美国俄亥俄州）[52]的可用性和定价，以获得Flash需要4个c6g.8xlarge（32 vCPU和64GB内存）实例。估计费用为2.74美元/小时。
<2>一次性部署设置，其中操作员使用按需计算资源来验证LNet-ecmp
结果分析：
<1>选择4个c6g.8xlarge（32个vCPU和64GB内存）实例，Flash在21秒内完成一次性验证：1秒用于接收规则更新，19秒用于模型构建，939ms用于可达性检查。
<2>假设每个实例运行1分钟并使用WS定价数据，则系统成本为4.352美元/小时或0.07美元/次