Flash-解决更新风暴、长尾到达的最新数据平面验证-学习1
预先知识
首先介绍一下更新风暴的概念与示例
更新风暴：短时间内发生大量数据平面更新
长尾到达：有些交换机的更新需要很长时间到达
更新风暴示例
在之前的研究工作中，互联网中单个故障可能出发BGP撤销，从而导致域内网络FIB变化
如上图所述，考虑图a中的网络，假设它从AS-1和AS-2接收10K前缀，10K前缀的最佳路径是通过边界路由器A
如图b所示。在A与Internet链路断开后，前缀从AS-1中撤回，新的最佳路径是通过路由器B转发数据包
如图b所示。对于3节点拓扑，更改将触发30K FIB更新。域内的链路改变也可能触发大量的FIB更新
考虑图c中的网络，当从C到B建立新的链路时，最佳域内路径从C-A-B更改为C-B。因此，它将触发所选前缀的10K更新。
作者使用FRR评估了第一个图的场景，第二个图显示了当我们触发链接事件时更新的累积分布。
当链接A-Internet失败时，我们在0.48秒内收到来自A的10K突发更新，而在链接B-C建立后1.36秒内，我们在0.58秒内收到C的10K突发更新.
将这些条目馈送到数据平面验证器会导致长的验证时间和大的内存消耗，即使对于增量数据平面验证器来说，大量的更新也可能具有挑战性。
虽然可以采用分而治之的方法，但成本取决于分区方法和数据平面的复杂性，并且仍然可能非常大
首先介绍什么是Fat树
Fat-Tree特点
是以交换机为中心的拓扑
支持在横向拓展的同时拓展路径数目
且所有交换机均为相同端口数量的普通设备，降低了网络建设成本
Fat-Tree结构共分为三层：核心层、汇聚层、接入层。
一个k元的Fat-Tree可以归纳为6个特征：
每台交换机都有k个端口
核心层为顶层，一共有(k/2)^2个交换机
一共有k个pod，每个pod有k台交换机组成。其中汇聚层和接入层各占k/2台交换机
接入层每个交换机可以容纳k/2台服务器
k元Fat-Tree一共有k个pod，每个pod容纳k×k/4个服务器，所有pod共能容纳k×k×k/4台服务器；
任意两个pod之间存在k条路径
下图是k=4的胖树结构
考虑下图中所示的场景，假设网络具有K-ary胖树拓扑结构，每个POD都有P个前缀。什么时候K=32和P=32，其中有1310720个FIB规则和71680个FIB改变是在向数据中心网络添加新的pod时通过BGP模拟生成的。下图中四个参数分别代表：胖树参数、每个pod的前缀、修改后规则总数、修改的规则数
我们可以看到，在经过网络故障后，会产生大量的FIB更新
