SDN实验（三）：构造生成树进行ARP广播

在传统网络中，如果存在环路，可以用生成树协议解决广播风暴问题。生成树协议运行在交换机上，各交换机平等协商产生生成树根和通往根的路径，该过程是分布的。

SDN 的控制器可以获得全局的拓扑信息，直接构造整个生成树，再通过流表改变交换机的（广播）转发行为，进而避免广播风暴。

识别广播

数据包的广播可以通过网络协议中的特定保留地址实现。ARP 协议建立在以太网协议之上，一个 ARP 请求包的目的 MAC 地址是 ff:ff:ff:ff:ff:ff 。

调用 Ryu API 构造 eth_dst 匹配域为广播 MAC 地址的流表项，即可规定交换机对 ARP 广播数据的转发行为。

改变广播行为

广播是将数据包传遍整个网络，朴素思路是每个交换机收到数据包后向所有其他端口转发，但存在环路就会产生广播风暴。若一个节点只将数据包转发给自己在生成树上的邻居，则转发过程不存在环路和广播风暴的问题。证明很容易：

规定首个发出数据包的节点为根（生成树是无根树），则整个转发过程等价于对生成树的一次广度优先遍历，因此必然是不重不漏的。

构建一个模仿 ARPANET^[1] 的网络：

在这个网络中，每个交换机上连接有一台终端，任意终端之间都可以通信。对于每个交换机，在生成树上进行广播的行为有两种：

• 若收到终端发来的数据包，则发给所有相邻的交换机；
• 若收到交换机发来的数据包，则发给所有其他相邻交换机。

实现这些行为需要控制器获取全局拓扑、构造生成树、下发流表项。

获取全局拓扑

这只是一个小实验，获取拓扑最简单的方法是直接用

hosts    = get_all_host(self)
switches = get_all_switch(self)
links    = get_all_link(self)

获得所有的终端、交换机和链路。以交换机作为节点、链路作为边^[2]建图，构造生成树。数据包的转发过程不涉及终端，因此终端并不在图中，但需要记录每个交换机连接终端的端口，以区别于连接交换机的端口。

new_g    = Graph()

for switch in switches:
    new_g.add_node(switch.dp.id)
    # map dpid to Datapath object
    self.id2dp[switch.dp.id] = switch.dp
for host in hosts:
    # record the port connected to host
    self.hostport[host.port.dpid] = host.port.port_no
    # map host's MAC address to the dpid it connected
    self.mac2dpid[host.mac] = host.port.dpid
for link in links:
    # an edge is described as (src_dpid, src_port, dst_dpid, dst_port)
    new_g.add_edge(
            link.src.dpid, link.src.port_no,
            link.dst.dpid, link.dst.port_no
        )

随着网络设备的增减，拓扑信息会发生改变，控制器维护的拓扑信息也应改变。直接的办法是：周期性获取拓扑，和消息处理相互独立。可以用 Ryu 提供的 ryu.lib.hub 类，它是对 eventlet 的封装，可以分出一个协程负责获取拓扑信息。具体实现分两部分：

• 类初始化时创建协程：

  def __init__(self, *args, **kwargs):
      self.topo_thread = hub.spawn(self._update_topology)
      # ...

• 周期性执行：

  def _update_topology(self):
      while True:
          # update topoloty information
          # generate spanning tree
          # add flow table entries
          hub.sleep(5)

运行_update_topology的协程和处理消息的协程是属于同一线程的。当更新拓扑信息的协程放弃执行（调用hub.sleep）时，应用才能处理消息。因此，执行间隔不能太短，否则更新拓扑信息将占用绝大多数执行时间，导致不能正常处理消息——比如处理速度低于到达速度，消息队列爆掉。

构造生成树

不考虑边权问题，那么生成树的构造就很随便了。这里用邻接表存图，用简化的 Kruskal 算法（不排序）来构造一棵生成树：

class Edge:
    # (from_node, from_port, to_node, to_port, weight)

class UnionFindSet:
    def __init__(self, nodes: list):
        # initialize each node's father as itself

    def find(self, x):
        # find which set that `x` belongs to
    
    def union(self, x, y):
        # union the two sets that `x` and `y` belong to

class Graph:
    def __init__(self):
        self.nodes = []
        self.edges = defaultdict(lambda: list())

    def add_node(self, node_id: int):
        self.nodes.append(node_id)

    def add_edge(self,
            from_node : int,
            from_port : int,
            to_node   : int,
            to_port   : int,
            weight    : float = 1
        ):
        self.edges[from_node].append(
                Edge(from_port, to_node, to_port, weight)
             )

    def spanning_tree(self):
        # spanning tree
        st = Graph()
        if len(self.nodes) == 0:
            return st
        ufset = UnionFindSet(self.nodes)

        for node in self.nodes:
            st.add_node(node)
        for node in self.nodes:
            for edge in self.edges[node]:
                if ufset.find(node) != ufset.find(edge.to_node):
                    st.add_edge(
                            node, edge.from_port,
                            edge.to_node, edge.to_port
                        )
                    st.add_edge(
                            edge.to_node, edge.to_port,
                            node, edge.from_port
                        )
                    ufset.union(node, edge.to_node)

        return st

表达为流表项

设一个节点（交换机）在生成树上有 $k$ 个邻居，则一共有 $k+1$ 条流表项需要下发到这个节点：

• 前 $k$ 条：任意邻居发来广播包时，转发给其余 $k-1$ 个邻居；
• 最后一条：终端发来广播包时，转发给所有邻居。

# here `node` means dpid
for node in self.st.nodes:
    if self.hostport[node] is None:
        return
    dp = self.id2dp[node]
    parser = dp.ofproto_parser
    for edge in self.st.edges[node]:
        # when a broadcast packet comes from a neighbor, send it to
        # all OTHER neighbors and the host
        match = parser.OFPMatch(
                    in_port  = edge.from_port,
                    eth_dst  = 'ff:ff:ff:ff:ff:ff'
                )
        actions = [
                    parser.OFPActionOutput(e.from_port)
                    for e in self.st.edges[node]
                    if e.from_port != edge.from_port
                  ]
        actions.append(parser.OFPActionOutput(self.hostport[node]))
        self.add_flow(dp, 1, match, actions)
    # when a broadcast packet comes from the host, send it to
    # all neighbors
    match = parser.OFPMatch(
                in_port  = self.hostport[node],
                eth_dst  = 'ff:ff:ff:ff:ff:ff'
            )
    actions = [
                parser.OFPActionOutput(e.from_port)
                for e in self.st.edges[node]
              ]
    self.add_flow(dp, 1, match, actions)

说明

这是我对实验的一点小改动，和老师给出的两种思路并不相同。另两种解决 ARP 广播风暴的方法是：

• 由控制器作 ARP 转发：控制器记录每个交换机连接终端的端口，让所有的 ARP 请求都触发 Packet-In ，再将这些请求一步发给上述端口。相当于不经过中间转发，直接广播到所有终端。
• 以(dpid, mac, dst_ip)作为键，port作为值维护 ARP 广播数据包的转发记录。每个交换机收到广播包时检查对应的键，若值不存在则记录值并洪泛，值存在则丢弃数据包。

注释

[1]^历史上第一个网络，今天互联网的雏形。

[2]^用get_all_links获取到的链路是单向链路，两台交换机之间的链路会以一来一去的形式出现两次。