UCAS-Network-Lab-4-stp

Posted on Edited on

挺难理解的一次实验

0. 为什么我们需要生成树协议\text{0. 为什么我们需要生成树协议}

Copilot:

在一个网络中，如果有多个交换机，那么就会出现环路，这样就会导致广播风暴，因为交换机会把广播包发给所有的端口，这样就会导致广播包在网络中不断的传播，从而导致网络拥堵。

这一点我们在上一次的实验中已经验证过了，最简单的解决方法就是干掉网络中的环并且保持网络的连通性，那这自然就是一棵生成树。

不过不是所有的生成树都令人满意的，我们自然还是希望整个生成树的网络传输的代价尽可能的小。

传统的最小生成树算法在此是不适用的，因为整个网络中没有任何一个节点知道网络的全貌，这就需要生成树协议，通过各个节点之间的通讯来选举出最合适的生成树结构。

1. 代码实现\text{1. 代码实现}

对于每个节点，都会维护一系列的端口配置。

基本原则是，从哪个端口收到配置，就尝试着更新该节点所有端口的配置，如果无法更新，说明发送该配置的端口需要被更新（因为本节点保存的配置优先级更高），那么就向该端口发送自己的配置。

1
2
3
4
5
6
7
8
9
10
11
12
13
static void stp_handle_config_packet(stp_t *stp, stp_port_t *p,
                                     struct stp_config *config) {
  if (stp_config_prior(config, p)) {
    p->designated_root = ntohll(config->root_id);
    p->designated_switch = ntohll(config->switch_id);
    p->designated_port = ntohs(config->port_id);
    p->designated_cost = ntohl(config->root_path_cost);
    stp_update(stp);
    stp_update_ports(stp);
    stp_send_config(stp);
  } else 
    stp_port_send_config(p);
}

这里首先更新本端口的配置，端口配置改变以后尝试更新本节点的全局配置，最后再把全局配置用来更新所有端口的配置。

这里需要注意的是，配置信息是对方发送过来的，所以需要进行字节序转换。

对于节点配置的更新非常简单，找到优先级最高的非指定端口，然后把该端口的配置信息更新到本节点的配置中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

static void stp_update(stp_t *stp) {
  stp_port_t *root_port = NULL;
  for (int i = 0; i < stp->nports; i++) {
    stp_port_t *port = &stp->ports[i];
    if (!stp_port_is_designated(port)) {
      if (root_port == NULL || stp_port_prior(port, root_port))
        root_port = port;
    }
  }
  stp->root_port = root_port;
  stp->designated_root = root_port->designated_root;
  stp->root_path_cost = root_port->designated_cost + root_port->path_cost;
}

更新所有端口的过程稍微复杂一点儿，这里主要涉及到两种情况：非指定端口变为指定端口，指定端口信息更新。

指定端口只有在收到配置信息的时候才有可能变成非指定端口，本节点的配置更新并不影响，因此只需要更新指定端口的根节点配置和路径代价。

对于非指定端口而言，我们需要构造一个配置信息，然后和本端口已有的配置进行比较，如果构造的配置信息优先级更高，那么将该端口配置信息更新。

这个构造的配置信息就是假定该非指定端口能够成为指定端口的配置信息，因此根节点就是本节点的根节点，根路径代价就是本节点的根路径代价，交换机ID就是本节点的交换机ID，端口ID就是该端口的端口ID。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void stp_update_ports(stp_t *stp) {
  for (int i = 0; i < stp->nports; i++) {
    stp_port_t *port = &stp->ports[i];
    if (port == stp->root_port)
      continue;
    if (stp_port_is_designated(port)) {
      port->designated_cost = stp->root_path_cost;
      port->designated_root = stp->designated_root;
    } else {
      struct stp_config cfg = {
          .root_id = htonll(stp->designated_root),
          .root_path_cost = htonl(stp->root_path_cost),
          .switch_id = htonll(stp->switch_id),
          .port_id = htons(port->port_id),
      };
      if (stp_config_prior(&cfg, port)) {
        port->designated_root = stp->designated_root;
        port->designated_switch = stp->switch_id;
        port->designated_port = port->port_id;
        port->designated_cost = stp->root_path_cost;
      }
    }
  }
}

2. 测试脚本\text{2. 测试脚本}

我稍微魔改了一下课程组提供的脚本，这样就可以自动化运行网络并且和标准答案进行比较。

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
34
35
36
37
38
39
40
41
42

if __name__ == '__main__':
    check_scripts()

    topo = RingTopo()
    net = Mininet(topo = topo, controller = None) 

    for idx in range(4):
        name = 'b' + str(idx+1)
        node = net.get(name)
        clearIP(node)
        node.cmd('./scripts/disable_offloading.sh')
        node.cmd('./scripts/disable_ipv6.sh')

        # set mac address for each interface
        for port in range(len(node.intfList())):
            intf = '%s-eth%d' % (name, port)
            mac = '00:00:00:00:0%d:0%d' % (idx+1, port+1)

            node.setMAC(mac, intf = intf)


    net.start()
    for idx in range(4):
        name = 'b' + str(idx+1)
        node = net.get(name)
        node.cmd('./stp > %s-output.txt 2>&1 &' % name)
        node.cmd('./stp-reference > %s-output-ref.txt 2>&1 &' % name)
        print("Started stp on %s" % name)
    # sleep for 45 seconds
    os.system('sleep 45')
    # for all the hosts, kill the stp process
    print("Killing stp on all hosts")
    for idx in range(4):
        name = 'b' + str(idx+1)
        node = net.get(name)
        node.cmd('pkill -SIGTERM stp')
        print("Killed stp on %s" % name)
    net.stop()

# run command "./dump_output.sh 4" to get the output
os.system('./dump_output.sh 4')

我们需要在每个节点上运行两个程序，一个是我们自己写的stp，另一个是课程组提供的stp-reference，然后睡眠一段时间等待收敛再进行比较。

最终运行出来是符合预期的，我们自己写的stp和参考答案的stp-reference输出的结果是一样的，所有的端口配置都完全一致。

最优的生成树可能不是唯一的，但是按照我们这样写出来的stp,可以想到其结果是不受网络传输顺序的影响的。因为所有的可能的配置能够构成一个全序。

3. 总结\text{3. 总结}

这次实验初步体验了一下“分布式”的感觉。

我也简单查阅了资料，发现我们的生成树协议其实就是一种分布式的生成树算法，其特点就是每个节点只知道自己的信息，但是通过和其他节点的通讯，最终达成一致。