UCB CS168 lab2 Routing 小记

Posted on In Word count in article: 666 Reading time ≈ 2 mins.

简单记录一下我做下来的一些小坑。

Stage 2

正确的端口

事实上，handle_data_packet(self, packet, in_port) 注释说明了是 :param in_port: the port from which the packet arrived.，但这个其实没有作用。我们关心的是我们当前这个 router 要把收到的 packet 向哪个端口转发，所以其实是：

1
2
3
4
dst = packet.dst
...
dst_port = self.table[dst].port
latency = self.table[dst].latency

Stage 4

注意 latency 计算完整

我们在接收到邻居的广播后，注意他发送过来的 latency 只是他到目标 host 的 latency，而我们如果要通过它中转，还需要加上我们到它的 latency:

1
2
3
4
5
latency = route_latency + self.ports.get_latency(port)
new_entry = TableEntry(dst=route_dst, port=port,
                        latency=latency, 
                        expire_time=api.current_time()+self.ROUTE_TTL)

Stage 5

字典删除问题

由于 self.table 是一个字典类型，而直接在遍历中删除字典元素会引发错误：

1
RuntimeError: dictionary changed size during iteration

比较推荐的做法是先收集一个应当删除的 list:

1
2
3
4
5
6
7
8
9
10
11
12
expire_list = []
for dst, entry in self.table.items():
  if entry.expire_time <= api.current_time():
    expire_list.append(dst)

for dst in expire_list:
  if self.POISON_EXPIRED:
    new_entry = TableEntry(dst=dst, port=self.table[dst].port,
                            latency=INFINITY, expire_time=api.current_time()+self.ROUTE_TTL)
    self.table[dst] = new_entry
  else:
    self.table.pop(dst)

Stage 6&7

关于处理 Split Horizon 和 Poison Reverse 有一个更聪明的写法，我们在遇到 self.SPLIT_HORIZON 为 True 的时候选择直接 continue，这样就避免了大量繁琐的 if 语句。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for port in ports_update:
  for dst in self.table.keys():
    latency = self.table[dst].latency

    if port == self.table[dst].port:
      if self.SPLIT_HORIZON:
        # Split Horizon: don't send anything at all
        continue
      elif self.POISON_REVERSE:
        # Poison Reverse: send it as INFINITY
        latency = INFINITY

    if latency > INFINITY:
      latency = INFINITY

    route = RoutePacket(destination=dst, latency=latency)
    if force or self.history[port].get(dst, None) != latency:
      self.send_route(port, dst, latency=latency)
      self.history[port][dst] = latency
    else:
      pass

Stage 10A

题干提示了要使用一个 self.history 的数据结构来记录每个端口向每个目的地上一次转发的 packet 的信息。我一开始使用了一个元组 (port, dst)，然后使用 self.key: {(port, dst): RoutePacket} 这样的键值对来存储。

但这样有几个问题：

  1. 写起来很繁琐

  2. 有冗余的信息，我们不需要保存完整的 packet，因为我们的 key 已经有 dst 了（RoutePacket 本身有 latency 和 dst 两个信息）

综上，我们采用一个更良好的写法，即一个二重字典。

1
2
3
4
5
6
7
8
9
10
def __init__(self, ...):
  from collections import defaultdict
  self.history = defaultdict(dict)

# in send_routes
if force or self.history[port].get(dst, None) != latency:
  self.send_route(port, dst, latency=latency)
  self.history[port][dst] = latency
else:
  pass

defaultdict

对于一个普通的 Python 字典, 如果你访问一个不存在的键，它会直接报错 KeyError。 但 defaultdict(dict) 自带默认值：

当尝试访问 self.history[port] 时，如果这个 port 还没出现过，它不会报错，而是自动创建一个空的字典 {} 填在那里。

配套的，使用 dict.get(key, None) 可以安全的取出对应的值。