2. 清华大学 网络科学与网络空间研究院, 北京 100084
2. Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China
人工智能和云计算等技术逐渐兴起，其应用领域也在不断扩展。这些新兴技术的应用通常要求集群内多台服务器协同完成某一计算任务，因此数据中心的计算资源开始以池化形式呈现，服务器之间频繁地传输计算数据资源，使得数据中心东西向的流量明显增加，原有的3层树形网络拓扑架构的通信限制问题日渐突显[1]。为了更好地满足日益变化的网络需求，一些新型的网络拓扑架构被提出，但从其被提出到真正落地需要经过多重检验，以确保符合相应的场景需求。实际铺设相应网络设备来搭建实验床的方式存在成本较高、检验相对复杂等问题，不适用于大型的生产网络环境。因此，搭建一套高保真且操作简便的拓扑仿真模拟和性能评估系统是非常有必要的。目前的网络拓扑模拟仿真工具通常可分为以NS2[2]、ns-3[3]、NS4[4]、OMNet++[5]等为代表的网络模拟器和以Mininet[6]、BNV[7]为代表的网络仿真器。
网络模拟器利用CPU的计算能力对真实的网络和流量进行建模，通常支持灵活定制，可以很容易地拓展到大型的网络拓扑结构。NS3是一种目前主流的离散事件驱动网络模拟器，NS4则是在NS3的基础上引入了对P4的支持，可对包含P4设备的网络拓扑进行模拟。但网络模拟器受到CPU的限制，在功能和性能上不能完全代表真实的网络和流量。网络仿真器在CPU上运行与真实设备相同的代码，像网络模拟器一样支持定制拓展，并且在功能方面实现了较高的保真度。网络仿真器同样受限于CPU的运算能力，无法提供高保真的性能仿真。Mininet是目前常用的一种网络仿真器，基于进程的虚拟化和网络命名空间创建虚拟网络，可以在单台机器上仿真包括主机、链路、交换机在内的完整网络。CrystalNet[8]则是一种云规模的网络仿真器，在网络容器和虚拟机中运行真实的网络设备固件，但由于缺乏数据平面的仿真支持，无法实现真实的硬件转发行为。BNV则受限于OpenFlow交换机[9]的弱灵活性，难以适应当前新型网络协议的需要。
当网络拓扑较小时，搭建真实的网络设备实验床的方法可以满足需要；但当网络拓扑较大时，该方法的成本通常较高，且不同设备需要进行的相应调试也会非常复杂。此时可以选择使用一些公共的大型实验床，例如GENI[10]是由美国国家科学基金会支持的一个分布式共享实验床，可用于大型网络的探索和研究；中国的CERNET主干网则是全球最大的国家学术互联网，由清华大学等多所高等院校共同承担建设、管理和运行工作，联网超过2 000所大学、教育机构和科研单位。然而，在网络拓扑设计的过程中需要不断地调整实际的网络设备连接关系，这些公共的大型实验床通常不支持对网络拓扑和节点转发行为等进行定制。
近年来，交换机、网卡等网络基础设施逐渐具备了可编程性。P4语言[11]的出现使数据平面的编程更为简单，可编程交换机[12]的可编程性和高带宽优势使功能和性能高保真的网络拓扑仿真成为可能，TurboNet框架[13]就是具有代表性的成果之一。目前，受限于单台可编程交换机的物理端口数量，TurboNet框架可以进行网络拓扑仿真的交换机数量有限；若将TurboNet框架拓展到使用多台可编程交换机进行仿真的场景，又很难满足不同可编程交换机之间的物理链路带宽约束。因此，如何在满足不同可编程交换机之间的物理链路带宽约束的前提下，使用多台可编程交换机对更大的网络拓扑进行仿真，是一项具有挑战性的研究工作。此外，TurboNet框架本身只具备端口转发功能，无法感知到网络的故障、延迟等情况，因此在对网络拓扑，特别是较大的网络拓扑进行仿真时，引入相应的遥测功能也十分重要。Netview框架是一个可以根据需要支持各种遥测应用程序和遥测频率的网络测量框架，通过主动发送专用的探针包监测相应的网络设备[14]，但受限于可编程交换机对包头长度的限制，该框架目前很难直接应用于大型网络拓扑的遥测任务。
本文基于非线性整数规划的方法进行约束建模，实现了在满足物理链路带宽约束的情况下，利用多台可编程交换机进行网络拓扑仿真。为了赋予TurboNet框架以网络遥测的能力，本文结合网络拓扑仿真场景的特点，将Netview框架的探针格式进行修改，利用可编程交换机的匹配—动作表的表项记录探针转发路径，从而在仿真的网络拓扑上实现网络遥测，并可支持较长的探针转发路径。
1 问题分析 1.1 TurboNet框架的求解目标及端口映射约束依据文[13]，TurboNet框架是利用可编程交换机进行网络拓扑仿真的新型网络仿真框架，其将拓扑的仿真分为2部分：一是交换机的仿真，定义了仿真交换机的处理逻辑；二是链路的仿真，通过配置可编程交换机的环回(loopback)端口实现仿真交换机之间的连接。TurboNet框架会使用约束进行虚拟端口到可编程交换机的物理端口之间的映射，TurboNet框架的求解目标是使得虚拟拓扑最终占用的物理端口组总数最少，其函数表达为
| $f_{\text {min }}=\sum\limits_{q=1}^Q\left(x 1_q+x 2_q+x 3_q+x 4_q\right)$ |
其中：q表示物理端口组编号；Q表示单台可编程交换机上的物理端口组总数；端口组可以根据需要被配置为1个100 G(1×100 G)、2个40 G(2×40 G)、4个25 G(4×25 G)或者4个10 G(4×10 G)的子端口，x1q、x2q、x3q、x4q分别表示端口组q是否被配置为上述4种类型的子端口，是则取值为1，否则取值为0。
基于单台可编程交换机的TurboNet框架需考虑4项约束。约束C1—C3保证了输入的虚拟端口到可编程交换机的物理子端口之间的一一映射关系，约束C4保证了可编程交换机上被映射的物理端口带宽不小于输入虚拟拓扑的虚拟端口带宽。
| $\begin{gathered}\mathrm{C} 1: x 1_q+x 2_q+x 3_q+x 4_q \leqslant 1 , \\ \forall q \in\{1, 2, \cdots, Q\} , \\ \mathrm{C} 2: \sum\limits_{p=1}^P y 1_{q p} \leqslant x 1_q, \sum\limits_{p=1}^P y 2_{q p} \leqslant 2 x 2_q , \\ \sum\limits_{p=1}^P y 3_{q p} \leqslant 4 x 3_q, \sum\limits_{p=1}^P y 4_{q p} \leqslant 4 x 4_q , \\ \forall q \in\{1, 2, \cdots, Q\} , \\ \mathrm{C} 3: \sum\limits_{q=1}^Q\left(y 1_{q p}+y 2_{q p}+y 3_{q p}+y 4_{q p}\right)=1 , \\ \forall p \in\{1, 2, \cdots, P\} , \\ \mathrm{C} 4: \sum\limits_{q=1}^Q\left(100 y 1_{q p}+40 y 2_{q p}+25 y 3_{q p}+10 y 4_{q p}\right) \geqslant b_p , \\ \forall p \in\{1, 2, \cdots, P\}.\end{gathered}$ |
其中：p表示输入的虚拟拓扑中的端口编号；P表示输入的虚拟拓扑的端口总数；y1qp、y2qp、y3qp、y4qp用于判断端口组q中是否有一个物理子端口被映射到虚拟拓扑中的端口p中，且被对应配置为上述4种类型的子端口，是则取值为1，否则取值为0；bp表示输入虚拟拓扑的端口带宽。
1.2 多台可编程交换机实现更大的网络拓扑仿真问题尽管文[13]考虑了TurboNet框架对多台可编程交换机的支持，但仅是简单地将多台可编程交换机进行串联，并没有考虑到可编程交换机之间的物理链路带宽约束。当虚拟链路带宽超过物理链路带宽上限时会造成排队延迟，影响仿真性能；如果考虑带宽约束，又有可能延长求解时间。
如何使用多台可编程交换机实现更大的网络拓扑仿真的问题，可看作是将较大的仿真交换机虚拟拓扑映射到较小的、由可编程交换机组成的物理拓扑的过程。一种直观的解决思路是将多台仿真交换机分配到不同的可编程交换机上，然后在每台可编程交换机上根据其分配到的仿真交换机数，逐一使用TurboNet框架进行端口映射，由此将问题的难点转化为如何对虚拟拓扑进行划分，即如何将仿真交换机分配到可编程交换机上。如图 1所示，实线外框表示真实的1号和2号可编程交换机，仿真交换机sw1—sw6之间的连线表示虚拟链路，假设所有的虚拟链路带宽均为10 Gbps；映射关系是sw1、sw2、sw3映射至1号可编程交换机，sw4、sw5、sw6映射至2号可编程交换机。跨可编程交换机的虚拟链路带宽为90 Gbps，而1号和2号可编程交换机之间的物理链路带宽仅为40 Gbps，这种情况容易造成较高的排队延迟甚至丢包。为了保证仿真性能的保真度，本文拟引入一个约束：映射后的跨可编程交换机虚拟链路带宽不能超过可编程交换机之间设定的带宽上限。
|
| 图 1 虚拟拓扑划分映射示意图 |
对虚拟拓扑进行划分的问题与传统的k划分问题[15]类似，传统的k划分问题是一个NP-Hard问题，求解起来非常困难，而本文的划分问题还需要在此基础之上兼顾割边的带宽上限约束，如果不考虑该约束，则需要根据划分的映射结果重新调整可编程交换机的物理拓扑连接，使其满足映射要求的带宽约束；且在拓扑设计初期，需要映射的虚拟拓扑可能需要频繁变动，每次重新设计网络拓扑时都需要重新调整物理拓扑。因此，求解该划分问题存在一定难度。
1.3 支持较长转发路径长度的网络拓扑仿真遥测问题TurboNet框架本身不具备对仿真的网络拓扑进行网络遥测的能力；且目前的可编程交换机受限于探针包的包头长度，很难将较长的转发路径编码进包头中。本文利用Netview框架对TurboNet框架本身进行拓展，使其具备一定的网络遥测能力。同时对Netview框架进行相应的调整，利用可编程交换机的匹配—动作表表项而不是探针包包头中的转发栈进行记录，以支持较长的转发路径。
Netview框架探针包的包头结构如图 2所示，其中转发栈用于探针包在网络拓扑中的灵活转发，遥测栈用于网络状态的监测和遥测信息的收集。Netview框架可借助源路由技术[16]将转发路径编码至转发栈中，从而在任意的路径上进行转发并实现拓扑的全覆盖。但目前的可编程交换机对Netview框架的转发栈大小有一定限制，当需测量的网络节点距离发送探针的服务器较远时，Netview框架很难满足测量需要。因此，如何对Netview框架进行相应的修改，使其适应转发路径较长时的网络拓扑仿真性能评估是亟需解决的问题。
|
| 图 2 Netview框架探针包的包头结构 |
2 基于多台可编程交换机的网络拓扑仿真与评估方案 2.1 基于约束的虚拟拓扑划分求解算法
针对1.2节中的问题，本文提出直接划分算法和多级划分算法进行分析。
2.1.1 直接划分算法本文提出的直接划分算法通过3个约束条件将划分问题转化为非线性0—1整数规划问题，如式(1)—(3)所示。式(1)确保了虚拟拓扑上的每一台仿真交换机只会被分配到某一台可编程交换机上，式(2)确保了当前划分不会使得占用的物理子端口数量超过可编程交换机的最大上限，式(3)确保了划分后的子拓扑之间的带宽不会超过可编程交换机之间的物理链路带宽。
| $\sum\limits_{k=1}^K v_{i k}=1, \forall i \in\{1, 2, \cdots, S\};$ | (1) |
| $\begin{array} {c} \sum\limits_{p=1}^P v_{f(p) k} n_p \leqslant m_k, \forall k \in\{1, 2, \cdots, K\}, \\ n_p= \begin{cases}1, & w_{i j}=10 \text { 或 } 25 ; \\ 2, & w_{i j}=40 ; \\ 4, & w_{i j}=100 ;\end{cases} \end{array}$ | (2) |
| $\begin{array} {c} \sum\limits_{i=1}^S \sum\limits_{j=i+1}^S\left(v_{i k_1}+v_{i k_2}+v_{j k_1}+v_{j k_2}-1\right) \\ \left(v_{j k_1}-v_{i k_1}\right)\left(v_{j k_2}-v_{i k_2}\right)\left(-w_{i j}\right) \leqslant c_{k_1 k_2}, \\ \forall k_1, k_2 \in\{1, 2, \cdots, K\} \text { 且 } k_1 \neq k_2 .\end{array}$ | (3) |
其中：k和K分别表示可编程交换机的编号和总数；i和S分别表示虚拟拓扑上的仿真交换机的编号和总数；f(p)是一个映射函数，表示第p个虚拟端口属于第f(p)台仿真交换机，vf(p)k用于判断第f(p)台仿真交换机是否映射到第k台可编程交换机上，是则取值为1，否则取值为0；np表示当前映射的子端口类型所占用的子端口数量；mk表示第k台可编程交换机的最大子端口数量(以Tofino2型可编程交换机[17]为例，其每个端口组可以分别配置1个100 G、2个40 G、4个25 G、4个10 G的物理子端口)；vik和vjk分别表示第i台和第j台仿真交换机是否映射到第k台可编程交换机上，是则取值为1，否则取值为0；wij表示第i台和第j台仿真交换机之间的带宽大小；ck1k2表示第k1号和第k2号可编程交换机之间的物理链路带宽。
2.1.2 多级划分算法基于式(1)—(3)约束的直接划分算法虽然可以确保得到相应的解，但当问题规模比较大时很难在短时间内完成求解。因此，本文进一步提出了基于Metis[18]的多级划分算法。Metis是一种用于求解传统图k划分问题的多级图划分求解框架，可在较短时间内划分规模较大的图，使得每个子图的节点数量尽可能一致，且子图之间的总割边权重尽可能小。多级划分算法首先使用Metis框架将虚拟拓扑中的节点进行合并以实现节点数的缩减，再使用直接划分算法进行求解。如图 3所示，黑色圆点表示节点，虚线矩形框表示Metis框架合并后的大节点，实线矩形框表示实际的1号和2号可编程交换机，为简化表达，图中省略了虚拟拓扑中的链路连接。由图可知，合并后的大节点组成的图的规模显著缩小，可大大缩短算法的求解时间。
|
| 图 3 多级划分算法节点合并示意图 |
多级划分算法的伪代码如图 4所示。具体步骤如下：
|
| 图 4 多级划分算法的伪代码 |
步骤1 利用Metis框架对虚拟拓扑上的节点进行合并，得到合并后的大节点以及合并前后的节点之间的映射关系(伪代码第2行)；
步骤2 使用直接划分算法划分大节点拓扑图，得到大节点的拓扑划分关系(伪代码第3行)；
步骤3 遍历步骤2得到的划分关系，以及步骤1得到的映射关系，得到合并前的原始节点的拓扑划分结果(伪代码第4—9行)；
步骤4 遍历所有划分后的子拓扑，并对每个子拓扑单独使用TurboNet框架的约束进行物理端口的映射(伪代码第10—15行)。
多级划分算法的输入是网络拓扑的仿真交换机列表IDList、相应的链路列表EdgeList，以及可编程交换机总数K；算法的输出是可以将仿真交换机的虚拟端口映射为可编程交换机物理端口的Physic PortMap。Metis框架的输入是虚拟拓扑的仿真交换机列表IDList、相应的链路列表EdgeList，以及所设定的合并后的大节点数量s；算法的输出是合并降维后的节点列表NewIDList、NewEdgeList以及节点合并前后的映射关系IDToNewIDMap。使用直接划分算法对合并降维后的拓扑图进行划分，得到合并后节点对应的可编程交换机划分结果NewIDToPartitionMap。SubTopoList用于记录每个划分结果中所包含的仿真交换机列表，也即每台可编程交换机最终应该仿真的交换机列表。TurboNet框架输出的PhysicPortMap则用于记录每台仿真交换机的虚拟端口与对应可编程交换机的物理端口之间的映射关系。
为了使TurboNet框架支持虚拟链路进行跨可编程交换机的数据包转发，需在可编程交换机上增加相应数量的中转端口，同时，在数据平面上增加相应的跨可编程交换机转发映射表。如图 5所示，假设1号可编程交换机的33/0和2号可编程交换机的1/0分别为各自的中转端口，1号可编程交换机的4/0端口用于仿真13号交换机(sw13)的1号端口，2号可编程交换机的2/0端口用于仿真sw6的5号端口。而在虚拟拓扑中，sw13的1号端口和sw6的5号端口存在链路连接。
|
| 图 5 跨可编程交换机数据包转发示意图 |
为了实现该链路上数据包的正常转发，需要实现相应的跨可编程交换机转发映射逻辑。该逻辑通过转发映射表实现，转发映射表会匹配当前数据包进入可编程交换机时的物理端口，以及当前仿真交换机编号和仿真交换机端口编号，然后根据匹配结果将数据包转发到对应的物理端口。具体来说，当数据包从1号可编程交换机的中转端口33/0进入时，如果此时仿真交换机编号为13，端口号为1，则1号可编程交换机会将数据包转发到13号仿真交换机的1号端口所对应的物理端口4/0。而当数据包从物理端口4/0进入1号可编程交换机时，如果此时的仿真交换机编号为6，端口号为5，则1号可编程交换机会将该数据包转发到33/0端口，使得数据包可以从1号可编程交换机发出，然后进入2号可编程交换机的中转端口1/0。而具体的表项下发，是由控制器通过拓扑划分得到的割边信息计算得到，因为划分得到的割边信息对应的即是跨可编程交换机转发映射表所需的表项信息。
2.2 基于可编程交换机表项的探针转发方案传统的遥测方案会把转发路径编码在探针包的包头上，如Netview框架会将探针在每个转发节点的转发端口记录在包头的转发栈中，当探针包经过每个转发节点时，转发节点会从包头的转发栈中读取当前节点的转发端口进行相应的转发。由于可编程交换机受限于包头长度，这种编码方案很难适应转发路径较长时的网络拓扑需求。本文中不同的仿真交换机可以共用同一台可编程交换机上的表项资源，因此考虑利用可编程交换机的匹配—动作表表项而不是探针包的包头来记录探针的转发路径。然而，如果只记录可编程交换机的转发路径，则可编程交换机无法区分不同探测任务对应的转发任务，每次只能进行单一的网络测量任务，若希望同时进行多项不同的网络遥测任务，可编程交换机还需要通过一个标识任务的ID，用以区分不同的任务转发路径。
为此，本文在可编程交换机上设计了记录探针转发路径的匹配—动作表。如表 1所示，可编程交换机会根据匹配—动作表匹配探针的当前跳数和对应的遥测任务ID，再使用表项匹配得到对应测量任务当前的转发端口，从而进行相应的转发。应注意的是，每次发送新的探针时，需要根据探针转发路径通过控制平面添加相应的转发表项。
3 实验结果分析 3.1 划分算法效率分析
使用包含261个网络拓扑的Internet Topology Zoo网络拓扑数据集[19]，对提出的2种划分算法进行效率分析。实验环境为Win10操作系统，CPU型号为Intel(R) Core(TM) i5-12 400F；Metis框架使用Python第三方库Pymetis[20]实现，非线性规划求解器使用SCIP库[21]实现。
TurboNet框架主要用于虚拟端口到物理端口的映射，因此需要关注虚拟拓扑中的虚拟端口数量。Internet Topology Zoo网络拓扑数据集中绝大多数网络拓扑的总端口数量小于500个，使用直接划分算法便可在数秒内得到解，因此需选取数据集中最大的网络拓扑Kdl以实现对2种算法的对比分析。Kdl拓扑包含754个网络节点和899条虚拟链路，总计1 798个端口。假定使用8台具有64个端口组的Tofino2型可编程交换机，交换机之间的物理链路带宽均设置为100 Gbps。使用直接划分算法后，求解器经过1 d时间仍然没有得到可行的解；使用多级划分算法的结果如表 2所示，能够得到可行解，且求解时间会随着合并后节点数的减少而缩短。这是由于每个合并后的大节点包含了更多的小节点，算法可以尝试的求解空间随之缩小，由式(3)产生的约束数量也会大幅减少，从而缩短了算法的求解时间。当节点数增多时，多级划分算法会逐渐退化为直接划分算法，算法的求解空间变大，问题的求解难度增加。因此，针对大的网络拓扑，利用多级划分算法进行划分的优势更加明显。
为了明确多级划分算法对数据中心常用拓扑的划分效果，尝试对16阶FatTree拓扑进行求解，该拓扑包含320台仿真交换机和2 048条链路，总计4 096个虚拟端口，假设所有的链路带宽均设置为10 Gbps。该实验只对仿真交换机端口进行仿真，而不考虑FatTree所挂载的服务器。假定使用20台具有64个端口组(最多可使用20×64×4=5 120个物理子端口)的可编程交换机，且可编程交换机之间的物理链路带宽为300 Gbps，将这些作为约束使用直接划分算法进行求解，求解时间为793 s。使用多级划分算法将节点数缩减至128个，对应的求解时间为206 s。对比2种算法的求解结果可知，多级划分算法对16阶FatTree拓扑进行求解时的优化效果并不明显，这是因为FatTree类型的拓扑的仿真交换机较少，而虚拟端口较多，意味着所需的可编程交换机较多，这会导致由式(3)产生的约束数量大大增加，从而延长多级划分算法的求解时间。此外，多级划分算法的效果依赖于节点数的减少，而FatTree类型的拓扑中的单台仿真交换机具备较多的虚拟端口，本身就具备类似的节点缩减效果，如果进一步缩减则很容易导致合并后的单个节点占用过多的物理端口，排除较多潜在的可行解，最终可能无法找到合适的可行解。
3.2 基于表项的探针转发方案的时间开销分析使用CPU型号为Intel(R) Xeon(R) Gold 6230R CPU@2.10 GHz的Linux服务器和Tofino2型可编程交换机进行该小节的实验测试，其中Linux服务器用于下发探针转发路径对应的匹配—动作表表项。本实验在TurboNet框架的基础上引入了对Netview框架探针包的转发支持，结果表明，在保证TurboNet框架正常运行的情况下，Netview框架的探针包转发路径长度最多只能达到十几跳的量级，否则会导致程序无法通过Tofino2型可编程交换机的系统编译；如果采用可编程交换机的匹配—动作表表项记录探针转发路径的方案，则可以轻松支持数千甚至数万跳数的转发路径长度。探针转发路径的上限仅受限于可编程交换机的内存资源，假设表 1中的任务ID、当前跳数、转发端口各占用8 b的空间，则每条探针转发路径只需占用24 b的空间，具体每个字段占用的空间大小可根据需要进行调整。但该方案在每次发送探针的同时需要控制平面下发相应的转发路径表项，因此会带来一定的时间开销。如图 6所示，转发路径带来的时间开销和总转发路径长度基本呈正比关系；当总转发路径长度为100跳时，下发表项所用的时间开销仅为4.1 s。
|
| 图 6 下发表项所用时间与总转发路径长度的关系 |
3.3 多可编程交换机网络拓扑仿真与性能评估方案的可行性验证
为了验证基于多台可编程交换机进行网络拓扑仿真的可行性，使用2台具有64个端口组的Tofino2型可编程交换机以及CPU型号为Intel(R) Xeon(R) Gold 6230R CPU@2.10 GHz的Linux服务器对Internet Topology Zoo网络拓扑数据集中的Ion拓扑进行仿真测试。实验平台搭建如图 7所示，T1和T2分别表示1台具有64个端口组的Tofino2型可编程交换机，二者之间的物理链路带宽为40 Gbps；Linux服务器与T1、T2各自的物理端口相连，物理链路带宽为10 Gbps，主要用于表项的下发和探针的发送、收集；通过设置合理的探针转发路径，最终的探针也会回到服务器。Ion拓扑包含125个网络节点和150条虚拟链路，总计300个虚拟端口。本实验中，Ion拓扑网络节点之间的链路带宽统一设置为10 Gbps。由于此处虚拟拓扑的规模较小，使用直接划分算法即可在1 s内完成求解。此外，通过在Tofino2型可编程交换机终端设置相应物理端口的UP/DOWN状态可以仿真相应交换机的故障行为，设置为DOWN状态后，可以观察到对应的丢包情况。此外，可以通过Netview框架的探针收集到相应虚拟端口的排队、延迟等信息，对相应的链路进行网络遥测，验证了本文提出的使用多台可编程交换机进行网络拓扑仿真与性能评估方案的可行性。
|
| 图 7 多台可编程交换机进行网络拓扑仿真的可行性验证实验示意图 |
4 结论
为了能在考虑物理链路带宽约束的情况下，基于多台可编程交换机使用TurboNet框架进行高保真的网络拓扑仿真，本文利用非线性0—1整数规划的方式进行了约束建模，提出了基于Metis框架的多级划分算法，对仿真交换机数量进行缩减，大大缩短了算法的求解时间，提高了求解效率。针对可编程交换机受限于包头长度导致的Netview框架的探针转发路径长度有限的问题，本文基于网络拓扑仿真的特定场景，提出利用可编程交换机的匹配—动作表表项记录探针转发路径，使得Netview框架的探针可以在较长的转发路径上对仿真的网络拓扑进行网络测量及性能评估。
| [1] |
蒋炜, 钱声攀, 邱奔. 数据中心网络拓扑结构设计策略研究[J]. 中国电信业, 2021(S1): 73-78. JIANG W, QIAN S P, QIU B. Research on design strategies for data center network topology structure[J]. Journal of China Telecommunications Trade, 2021(S1): 73-78. (in Chinese) |
| [2] |
ISSARIYAKUL T, HOSSAIN E. Introduction to network simulator 2 (NS2)[M]//ISSARIYAKUL T, HOSSAIN E. Introduction to Network Simulator NS2. Boston: Springer, 2009.
|
| [3] |
ns-3[EB/OL]. [2023-08-01]. https://www.nsnam.org/.
|
| [4] |
BAI J S, BI J, KUANG P, et al. NS4: Enabling programmable data plane simulation[C]//Proceedings of the Symposium on SDN Research. Los Angeles, USA: ACM, 2018: 12.
|
| [5] |
VARGA A, HORNIG R. An overview of the OMNeT++ simulation environment[C]//Proceedings of the 1st international Conference on Simulation Tools and Techniques for Communications, Networks and Systems & Workshops. Marseille France: ICST, 2010.
|
| [6] |
Mininet Team. Mininet: An instant virtual network on your laptop (or other PC)[EB/OL]. [2023-08-01]. http://mininet.org.
|
| [7] |
KANNAN P G, SOLTANI A, CHAN M C, et al. BNV: Enabling scalable network experimentation through bare-metal network virtualization[C]//Proceedings of the 11th USENIX Conference on Cyber Security Experimentation and Test. Berkeley, USA: USENIX Association, 2018: 1-8.
|
| [8] |
LIU H H, ZHU Y B, PADHYE J, et al. Crystalnet: Faithfully emulating large production networks[C]//Proceedings of the 26th Symposium on Operating Systems Principles. Shanghai, China: ACM, 2017: 599-613.
|
| [9] |
MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: Enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74. DOI:10.1145/1355734.1355746 |
| [10] |
BERMAN M, CHASE J S, LANDWEBER L, et al. GENI: A federated testbed for innovative network experiments[J]. Computer Networks, 2014, 61: 5-23. DOI:10.1016/j.bjp.2013.12.037 |
| [11] |
BOSSHART P, DALY D, GIBB G, et al. P4: Programming protocol-independent packet processors[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 87-95. DOI:10.1145/2656877.2656890 |
| [12] |
BOSSHART P, GIBB G, KIM H S, et al. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 99-110. DOI:10.1145/2534169.2486011 |
| [13] |
CAO J M, LIU Y, ZHOU Y, et al. TurboNet: Faithfully emulating networks with programmable switches[J]. IEEE/ACM Transactions on Networking, 2022, 30(3): 1395-1409. DOI:10.1109/TNET.2022.3142126 |
| [14] |
LIN Y S X, ZHOU Y, LIU Z Z, et al. Netview: Towards on-demand network-wide telemetry in the data center[J]. Computer Networks, 2020, 180: 107386. DOI:10.1016/j.comnet.2020.107386 |
| [15] |
Menegola B. A study of the k-way graph partitioning problem[D]. Porto Alegre: University of Rio Grande Do Sul, 2012.
|
| [16] |
SUNSHINE C A. Source routing in computer networks[J]. Sunshine, 1977, 7(1): 29-33. |
| [17] |
Barefoot Networks, Tofino[EB/OL]. [2023-08-01]. https://www.barefootnetworks.com/products/brief-tofino/.
|
| [18] |
KARYPIS G, KUMAR V. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices[EB/OL]. (1998-09-20). http://mirror.its.dal.ca/freebsd/distfiles/gmsh/manual.pdf.
|
| [19] |
KNIGHT S, NGUYEN H X, FALKNER N, et al. The internet topology zoo[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1765-1775. DOI:10.1109/JSAC.2011.111002 |
| [20] |
PyMetis[EB/OL]. [2023-10-24]. https://pypi.org/project/PyMetis/.
|
| [21] |
SCIP[EB/OL]. [2023-10-24]. https://www.scipopt.org/.
|