SDN实验(三):构造生成树进行ARP广播

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

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

识别广播

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

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

改变广播行为

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

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

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

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

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

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

获取全局拓扑

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

1
2
3
hosts    = get_all_host(self)
switches = get_all_switch(self)
links = get_all_link(self)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 的封装,可以分出一个协程负责获取拓扑信息。具体实现分两部分:

  • 类初始化时创建协程:

    1
    2
    3
    def __init__(self, *args, **kwargs):
    self.topo_thread = hub.spawn(self._update_topology)
    # ...
  • 周期性执行:

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

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

构造生成树

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

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
43
44
45
46
47
48
49
50
51
52
53
54
55
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

表达为流表项

设一个节点(交换机)在生成树上有 kk 个邻居,则一共有 k+1k+1 条流表项需要下发到这个节点:

  • kk 条:任意邻居发来广播包时,转发给其余 k1k-1 个邻居;
  • 最后一条:终端发来广播包时,转发给所有邻居。
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
# 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获取到的链路是单向链路,两台交换机之间的链路会以一来一去的形式出现两次。