这是 UESTC 网络算法基础课程的 Project 2 实现。

关于环境的搭建，请参考：Mininet + RYU SDN 开发环境搭建 - Nativus' Space (naiv.fun)
代码仓库：Nativu5/Network_AlgoLab (gitee.com)

项目目标

  1. 在 Project 1 的基础上配置一个广播通信业务，假设主机 1 向所有其它主机进行广播；
  2. 使用 Kruskal 算法计算广播使用的最小生成树；
  3. 将广播业务在可视化平台上进行展示；

注：我的理解和项目目标有些出入（可能就是这个原因没有获得最高分）。我的想法仍然和 基于 Mininet 和 RYU 的 DFS 寻路算法实现 - Nativus' Space (naiv.fun) 中实现 Project 1 时的想法类似，即贴近传统的、现存的网络设计。

在我看来，主机 1 的业务是广播与否应当取决于主机 1 本身，而不是交换机们。如果主机 1 想要广播，那应当是由主机 1 发送特殊的报文或者是由主机 1 获得网络内所有的主机信息然后逐一发送数据达成广播目的。换言之，主机 1 的数据包不应当一直被网络内的所有主机接收。

当然，做完这个项目之后我又有了新的思考。还是老样子，放在后记中讨论吧。

实现思路

按照我的理解，我们要实现广播业务，必须保证这个网络能够正常运行。回想起冗余链路导致的广播风暴问题，我们自然的想法就是运行生成树算法消除冗余链路，即通过 Openflow 协议实现对交换机端口的控制，进而屏蔽特定的链路。

拓扑存储、拓扑发现的基本思路和 Project 1 基本一致，这里只对不同的地方进行说明。

1. 拓扑存储

虽然交换机间的连接是双向的，但是由于我们在配置时需要使用链路连接到的交换机端口信息，所以在本项目中，我们将一条无向边表示为两条有向边，每条边额外记录本条链路的源端口和目的端口信息。

2. 拓扑发现

为了凸显最小生成树“最小”的特点，我们在拓扑发现时为每条链路随机赋予了权重。

 # 保存链路信息，加入双向边（两条单向边），边权随机指定
        all_links = copy.copy(get_link(self))
        for link in all_links:
            u = link.src.dpid
            v = link.dst.dpid
            weight = self.topo.edges[v, u]['weight'] if self.topo.has_edge(
                v, u) else randint(1, 10)
            self.topo.add_edge(
                u, v, **{"src_port": link.src.port_no, "dst_port": link.dst.port_no, "weight": weight})

3. Kruskal 算法计算最小生成树

在算法运行之前，我们建立一个列表（tree_edges）保存最小生成树中的边，建立一个并查集用于检查节点是否在生成树内。

首先，我们按权重对边进行从小到大的排序，然后开始从最小的边开始遍历，若边的两端点不在同一集合中，则将边加入树边列表。

在此过程中，我们使用并查集判断节点是否在同一集合：若用树形结构表示并查集，每一个集合都对应一棵树，只需检测两个节点的根是否一致，就可以知道二者是否在同一集合。合并时，我们只需要将一组的根与另一组的根相连即可。（见图 1 Kruskal 算法流程图）

图 1 Kruskal 算法流程图
图 1 Kruskal 算法流程图

使用的并查集：

class UnionFindSet():
    """
    并查集
    """

    def __init__(self, n: int) -> None:
        self.fa = [i for i in range(0, n + 1)]
        self.size = n

    def find(self, x: int) -> int:
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def union(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.fa[y] = x

Kruskal 算法主体：

    def Kruskal(self) -> list:
        """
        Kruskal 算法计算最小生成树
        """
        tree_edges = []  # 保存最小生成树中的边
        for e in sorted(list(self.edges(data=True)), key=lambda e: e[2]["weight"]):
            # 按边权从小到大遍历所有边，相连两点不在并查集内就加入 MST
            if self.set.find(e[0]) != self.set.find(e[1]):
                self.set.union(e[0], e[1])
                # 将边添加进 MST
                tree_edges.append((e[0], e[1]))

        # 绘制最小生成树
        self.draw_tree(tree_edges)

        return tree_edges

4. KruskalController 控制器

除了对 OFPT_PACKET_IN 消息和 OFPT_PORT_MOD 消息的处理不同之外，其他与 Project 1 中基本一致。完整的代码请参考代码仓库。

  • OFPT_PORT_MOD 消息：控制器通过发送OFPT_PORT_MOD消息，对特定交换机上特定端口进行修改。端口具有多种状态，例如OFPPC_PORT_DOWN 代表端口关闭。我们通过发送该消息将最小生成树之外的端口置为关闭状态，从而实现冗余链路的消除。

    OFPT_PORT_MOD 消息
    OFPT_PORT_MOD 消息

  • OFPT_PACKET_IN 消息：控制器从消息中解析出交换机无法匹配的数据包，判断其协议类型。若为 LLDP 帧，则丢弃（LLDP仅用于RYU内置的API发现链路，我们无需对其进行处理）；若为IPv6包，则丢弃（旧版本的Mininet中，即使网络中的主机都仅使用IPv4，网络中也会出现NDP 数据包，为避免不必要的麻烦，一律做丢弃处理）。

    对于其他的数据包，我们解析其源 MAC 地址 (src_mac) 和目的 MAC 地址 (dst_mac)，将源MAC地址和其对应的in_port加入交换机的MAC表。

    接下来，检查目的MAC地址是否在MAC表中，若目的MAC地址在MAC表中，则直接设置out_port；若目的地址尚未收入MAC表或本身就是广播地址，则需要设置out_port为泛洪，但此时拓扑中可能存在环，故需要检测生成树是否存在。生成树存在的情况下，可以正常泛洪。

    若最小生成树不存在，此时拓扑里存在冗余的链路，即存在环，一旦广播就会导致ARP风暴。为了广播业务正常运行，我们使用Kruskal算法建立最小生成树。然后发送Port_mod消息，将最小生成树之外的冗余链路全部禁用。由此，拓扑中的环全部被消除。

    最后，下发流表，避免下次Packet-in。需要验证是否存在有效的缓冲区ID，避免同时发送Flow_mod和Packet_out消息。设置out_port为当前交换机应该转发到的端口，避免丢包。

    流程图见图 3 处理 Packet-in 消息。

    图 3 处理 Packet-in 消息
    图 3 处理 Packet-in 消息

其他问题

关于拓扑可视化、常见故障的排除请参考 基于 Mininet 和 RYU 的 DFS 寻路算法实现 - Nativus' Space (naiv.fun)，这里只对测试方法中新的部分进行描述。

测试和验证

项目要求通过 Kruskal 算法计算生成树使广播业务正常运行，我们采用发送 ARP Request 的方式来测试广播业务。

搭建 Mininet 环境和启动控制器的命令已经在上篇博文中说明，不在赘述。

项目文件夹下的 ARPSender.py 为测试工具，使用方法见图 4 ARPSender.py 使用说明。

图 4 ARPSender.py 使用说明
图 4 ARPSender.py 使用说明

假设现在需要在主机 h1 上测试广播业务，只需待拓扑发现结束后，在 Mininet 命令行中输入：

h1 python3 ARPSender.py h1-eth0 h12

其中 h1 是发送 ARP 的主机名，h1-eth0 是 h1 上发送 ARP 数据包的网络接口 (Network Interface) 名称，h12 为 h1 要广播查找的主机名。

命令运行完毕后，最小生成树的图像会可视化展示出来，同时控制器会输出最小生成树上的边和被屏蔽的冗余链路。

命令行提示
命令行提示
可视化展示
可视化展示

后记

关于这个项目目标，我当时是有些疑惑的，为什么要求这个网络中的所有节点都能收到主机 1 的发送的数据包？只有主机 1 想要发送广播的时候才能让其他主机收到吧？这是基于现有的普通的网络的一种想法，联系到现实生活中比较熟悉的广播协议，我就想到了 ARP，所以选择了这个 ARP Sender 来测试。

SDN 网络的出现很大程度上是因为人们对现存网络的灵活性感到不满意。我理解的广播还是传统的场景，中规中矩，现有网络就可以实现。但是像老师的项目目标，可能离开 SDN 是很难实现的。这说明了 SDN 很有意思、非常灵活，可以通过自己的设计满足各式各样奇葩的需求。

参考资料：

一如既往地感谢队友的支持和帮助！