CrystalNet

发表于 分类于 阅读次数：
Faithfully Emulating Large Production Networks.

Faithfully Emulating Large Production Networks

Please read the https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/p599-liu.pdf (you can focus on S1-S5), and try your best to finish the following three tasks:

Task #1: Reading & Writing: 

1. What problem is this paper solving?

对于云服务和 online service 的大型网络而言，可靠地运行是一项挑战。这些网络往往包含数以万计的异构的设备，且一直在动态变化中。这使得哪怕是一些小问题，诸如硬件故障，软件bug，配置错误和人为的小错误（如输错命令），也会导致严重的后果，譬如网络中断。SLA 的不可靠继而导致用户的流失，这对服务提供商来说是灾难性的。

一个可行的思路是，在高保真的网络仿真器中验证所有网络操作，然后再在生产网络中执行。以往的技术并没有办法实现这种思路。

  1. Small hardware testbeds，如 Cloudlab/ Emulab，只能对新设备进行单元/压力测试，但无法模拟复杂网络拓扑结构中的相互关系。
  2. Network verification tools，例如 batfish，是根据设备配置和拓扑，来模拟理想状态下的路由的。但它无法揭示设备固件 bug 和诸如不同供应商对同一路由协议的实现差异带来的问题，且无法防止人为错误（因为其工作流程与生产网络截然不同，无法方便地起到预演的作用）。
  3. Small-scale network emulator，如 MiniNet/GNS，拥有许多缺陷（如不支持异构的设备固件，不识别安全的仿真边界），且无法扩展到如大型云网络的规模。

因此，本文提出了 highly-scalable/high-fidelity network emulator: CrystalNet.

2. What is the key idea?

CrystalNet 首先需要建立物理网络的模拟。

对于异构的网络设备，CrystalNet 将设备运行在 Docker 容器中，部署在云上的 VM 里。另外，实现一个 PhyNet 容器层，包含 virtual interface，设备容器与 PhyNet 连接，而网络拓扑通过 PhyNet 之间的互相连接实现。因此不用针对每个设备软件 image 的黑箱一一实现 API，而只要实现统一的 API；设备软件像与物理 interface 交互一样与 PhyNet 中的 virtual interface 交互。

对于只提供 VM image 而不提供容器 image 的设备，CrystalNet 将 VM image 等打包到一个新的容器 image 中，再在云 VM 中运行该 image（云需要支持嵌套虚拟机）

CrystalNet 也支持真实硬件的耦合，硬件交换机与 PhyNet 相连（经过 fanout 交换机），就可以与其他仿真设备交互。

对于 CrystalNet 的数据平面虚拟链路，仿真设备将其视为以太网链路。且使用 VXLAN 协议，模拟以太网链路(L2-L3，添加 UDP 报头，可连接 IP 网络)，使数据在真实网络中传播，而这对仿真设备透明。

对于 CrystalNet 的控制平面虚拟链路，CrystalNet 部署了一个 Linux Jumpbox，与所有仿真设备相连。通过 Jumpbox，操作者可以像在生产环境中一样操作所有仿真设备。

任何仿真网络都需要有边界，一则没有那么多的资源，二则无法获知控制范围之外的网络设备的信息。CrystalNet 定义了安全静态边界的概念(safe static boundaries)，指当内部的仿真设备发生各种变动时，外部网络可以视作始终保持静态。模拟外部网络时，CrystalNet只模拟与内部设备直接相连的设备，称为 speaker device，这些设备是静态的，只通过基本的活动（如 ARP）与边界设备保持连接，且可以发送任何路由信息。CrystalNet 针对 BGP/OSFP/SDN，提出了安全静态边界成立的一些充分条件。并对于 Clos-like & BGP 的数据中心网络(其拓扑可以视作 multi-root tree)提出了一种搜索安全静态边界的算法。经过实验，计算安全静态边界降低了 90% 以上的成本。

通过以上设计，CrystalNet 实现了以下目标： 1. 可以运行在公有云上，易于 scale out（container） 2. 可以透明地模拟物理网络（PhyNet, VXLAN） 3. 可以透明地模拟外部网络（安全静态边界，speaker device）

3. Any idea to improve the proposed solution?

  1. 当前 CrystalNet 的用法还是一种网络的验证工具，那是否有可能将 CrystalNet 作为生产环境与实际操作之间的缓冲层？CrystalNet 与生产网络同构，每当执行一个操作，首先自动化地在 CrystalNet 上执行，然后经过一段时间的验证后，再从 CrystalNet 导向实际生产网络。另外 CrystalNet 应当对操作者透明，除了报错时，操作者应当意识不到他们操作的究竟是 CrystalNet 还是真实网络。
  2. 模拟数据平面的内容，诸如丢包率，延迟，带宽。
  3. 支持除 Ethernet 网卡外的其他设备和除以太网之外的其他链路层协议。
  4. 改进仿真设备在云上的部署算法，考虑延迟等度量的同构性。 (2-4 详见问4中所述)

4. Ask three questions you don’t understand about the paper.

  1. 此处说到的可以扩展到其他设备，包括其他类型的硬件接口吗？譬如 InfiniBand 版的 RDMA 实现就重构了链路层，但前文中提到 CrystalNet 只支持 Ethernet 网卡。其他的譬如各式 SmartNIC，DPU 之类的可以与之兼容吗？（这似乎不只是软件层面的问题，还有硬件的异构）CrystalNet 可以支持不同的链路层协议吗？
  2. 数据平面的丢包率，延迟，带宽等为什么难以模拟呢？如 Linux 提供的 tc-netem，就可以模拟丢包率，延迟，带宽等等。
  3. 在公有云上部署 VMs，这些 VMs 的实际物理位置是不可知的（甚至会跨越多个公有云），这会导致实际上被部署在一起、相互之间延迟极低的设备，在云上可能相距极远、延迟极高。（云上容器的实际拓扑与生产环境中设备的拓扑不相符）进一步导致诸如 OSPF 等对 time cost 敏感的路由协议在更新路由表、计算路由路径时与实际可能发生的情况不相符。如何处理这种情况，直接写死路由吗？或许可以有部署算法的改进可能？

Task #2: Math formulation: 

1. Could you mathematically formulate the problem discussed in Sec 5?

Define the global network topology as an undirected graph \(G=(V,L)\), where \(V\) is the set of device nodes, and \(L\) represents the links between devices (also the undirected edges in the graph).

Define emulated devices \(D\), external devices \(E\), where \(G=D \cup E \wedge D\cap E=\emptyset\).

Define boundary devices \(B :=\{u|(u\in D) \wedge (\exists v\in E,s.t. \space (u,v)\in L)\}\), which are emulated devices directly connected to external devices.

Define internal devices \(I:=\{u|(u\in D)\wedge(\forall v\in E, (u,v)\notin L)\}\), which are emulated devices whose neighbors are all emulated devices. Thus, \(B\cup I=D \wedge B\cap I=\emptyset\).

Define speaker devices (speaker device) \(S:=\{u|(u\in E)\wedge(\exists v\in D,s.t. (u,v)\in L)\}\), which are external devices directly connected to emulated devices.

Define the boundary \(B\) as a safe static boundary: all behaviors of emulated devices are consistent with the real network. Since CrystalNet implements speaker devices as static, this statement is equivalent to the fact that the behavior of speaker devices in the real network cannot affect devices inside the boundary (including boundary devices).

Define an impact function \(f: V\times P(V\times V) \to P(V)\), where \(P(V)\) is the power set of \(V\). \(\forall u\in V\), \(f(u, R)=Next_{u,R}\subseteq V\), and for all \(v\in Next_{u,R}\), \((u,v)\in L\). This means that if \(u\) wants to send information, this information can propagate to devices in \(Next_{u,R}\), and these devices will continue to apply the function \(f(v,R\cup \{ <u,v>\})\) to send information. Here, \(R\) records the path that the information propagation has traversed.

We apply the following algorithm to determine whether \(B\) is a safe boundary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
global V,L,D,E,f # given
def transmitt(u,R)->bool:
    Next_u_R=f(u,R)
    for v in Next_u_R:
        if u in E and v in D:
            return False
    if transmitt(f,v,R.append(<u,v>))==False:
            return False
    return True
    

def isSafeStaticBoundary()->bool:
    for begin in D:
        if transmitt(begin,[])==False:
            return False
    return True

This problem may not be Turing-decidable because it may produce loops, and \(f\) is a function that may behave differently based on past path information, making it impossible to determine when duplicates will occur. Therefore, the algorithm may not stop. Of course, if a deterministic \(f\) is provided, the result can be determined through constraints.

2. Given your problem formulation and notations, could you formally express the Lemma and Propositions in Sec 5?

BGP

For networks using BGP protocol, we need to add AS information. Let \(ASes:= \{AS_{n_i}\}\), \(ASN=\{n_i\}\), where \(\cup_{i}AS_{n_i}=V\), and \(\cap_{i}AS_{n_i}=\emptyset\).

We can simplify \(R\) as an ordered set of nodes in the path.

Define \[inSameAS: V\times V\rightarrow \{true,false\}\]

\[inSameAS(u,v)= \exists i,s.t.\space u\in AS_{n_i} \wedge v\in AS_{n_i}\]

The propagation function is given by: \[f(u,R)=Next_{u,R}=\{v|((u,v)\in L)\wedge (\nexists w \in R,s.t. \space inSameAS(w,v))\wedge (!inSameAS(u,v))\}\]

Subsequently, \[\forall v \in Next_{u,R} \text{, call } {f(v,R\cup \{ u\})}\]

\(RV\) records the paths that appear in the propagation.

The problem then transforms into the following algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
global V,L,D,E,ASes # given

RV=[] # route vectors

def transmitt(u,R)->bool:
    Next_u_R=[]
    RV.append(R.append(u))
    for v in Neighbor(u):
        flag=False
        if inSameAS(u,v):
            flag=true
    for w in R:
        if inSameAS(v,w):
            flag=True
            break
        if flag==True
            continue
        if u in E and v in D:
            return False
        Next_u_R.append(v)
    for v in Next_u_R:
        if transmitt(v,R.append(u))==False:
            return False
    return True

    

 def isSafeStaticBoundary()->bool:
    for begin in D:
        if transmitt(begin,[],V,L,D,E)==False:
            return False
    return True

\(\text{Lemma 5.1: A boundary is safe if and only if }\forall R \in RV, \nexists i\text{, s.t.}R[i] \in E \wedge R[i+1] \in D.\)

\(\text{Proposition 5.2: If }\exists i,\text{ s.t. }B \subseteq AS_{n_i} \wedge (\nexists u,v \in S , u\not ={v}\text{, s.t. }inSameAS(u,v))\text{, the boundary is safe.}\)

\(\text{Proposition 5.3: If }\forall R \in RV, \nexists i<j<k\text{, s.t. }(R[i] \text{ and } R[k] \in B) \wedge (R[j] \in E)\text{ the boundary is safe.}\)

OSPF

Let \(S,B,L,D,E\) all be time series.

Let \(Links(S_{t_i},B_{t_i}):=\{(u,v)|(u,v) \in L_{t_i} \wedge u \in S_{t_i} \wedge v \in B_{t_i}\}\)

\(\text{Proposition 5.4: If }\forall i, Links(S_{t_i},B_{t_i})=Links(S_{t_0},B_{t_0}) \text{ and }DR,BDR \in D\text{, the boundary of the OSPF network is safe.}\)

Task #3: Programming: Could you implement and test Algorithm 1 with a sample network?

Please refer to the file algorithm.ipynb. The search algorithm is implemented based on a multi-root tree.

Generate multi-root tree

将 Clos-like 的数据中心网络拓扑结构看作 multi-root tree，随机生成 DAG G。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import matplotlib.pyplot as plt
import networkx as nx
import random

def generate_multi_root_tree(num_roots:int, depth:int)->nx.classes.digraph.DiGraph:
    G = nx.DiGraph()

    # 添加根节点
    roots = ([f"root_{i}" for i in range(num_roots)])
    options={"depth":0}
    G.add_nodes_from(roots,**options)
    upper_layer=roots
    for d in range(1,depth+1):
        num_nodes=random.randint(3,8)
        nodes = ([f"node_{d}_{i}" for i in range(num_nodes)])
        options={"depth":d}
        G.add_nodes_from(nodes,**options)
        for node in nodes:
            n_links=random.randint(0,len(upper_layer))
            rand_parents=random.sample(upper_layer,n_links)
            edge_list=[(node,parent) for parent in rand_parents]
            G.add_edges_from(edge_list)
        upper_layer=nodes

    return G

G = generate_multi_root_tree(3, 5)
pos = nx.layout.multipartite_layout(G,subset_key='depth',align="horizontal")
nx.draw(G, with_labels=True,pos=pos)

Generate must-have device

从 G 中按比率 p 随机 sample 一些点，作为必须要仿真的设备。在图中用绿色标识。

1
2
3
4
5
6
7
8
9
10
11
12
13
def genarate_must_have_device(G:nx.classes.digraph.DiGraph,p=0.2)->list:
    D=[]
    for node in G.nodes():
        r=random.randint(0,100)
        if r<100*p:
            D.append(node)
    return D

D=genarate_must_have_device(G)
pos = nx.layout.multipartite_layout(G,subset_key='depth',align="horizontal")
nx.draw(G, with_labels=True,pos=pos)
nx.draw_networkx_nodes(G, pos, nodelist=D, node_color='green')
plt.show()

Search static safe boundary of datacenter

搜索保证边界安全静态要仿真的所有设备，在图中用黄色标识。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_safe_dc_boundary(G:nx.classes.digraph.DiGraph,D:list)->list:
    D_=set()
    D=set(D)
    while len(D)!=0:
        d=D.pop()
        D_.add(d)
        depth=G.nodes[d]['depth']
        
        if depth==0:
            continue
        upper_devs=list(G.neighbors(d))
        
        for ud in upper_devs:
            if ud not in D.union(D_):
                D.add(ud)
    return list(D_)

D_=find_safe_dc_boundary(G,D) 
pos = nx.layout.multipartite_layout(G,subset_key='depth',align="horizontal")
nx.draw(G, with_labels=True,pos=pos)
nx.draw_networkx_nodes(G, pos, nodelist=D_, node_color='yellow')
plt.show()