SDN实验（二）：动态变更转发路径

原计划一面实验，一面总结，然而直到七月底都杂务缠身，只好现在才腾出手来，做一点回忆式的记录。

这一篇在于实现软件控制数据包的转发路径，路径的动态变化由控制器决定，而不是由交换机决定。控制器控制转发路径的手段包括两个方面：一是处理 OpenFlow 的 Packet-In 消息，二是下发流表项。此处正好涉及 OpenFlow 协议下控制器和网络的交互方式（控制平面），即收发消息（Message）。

控制器与交换机的通信

SDN 中的控制器和交换机

从 SDN 网络的角度，控制器和交换机是一些独立的设备。其中控制器的可编程空间大，可以视作通用计算机；而交换机比较刻板，只能按规则首发一些固定的消息，并按照流表匹配的结果转发数据包。

在一个传统的网络中，典型交换机会固定地将 A 网口的数据转发到 B (C, D, ...) 网口，是二层设备；典型的路由器则维护有路由表，能部分或全局地感知网络的拓扑信息，按照数据包的目的端决定转发的端口，是三层设备， SDN 网络则不然。在 OpenFlow 协议中，“交换机”的称呼更多是沿用习惯，实际上它兼具传统网络中交换机和路由器的特性。从本文的视角看， OpenFlow 交换机的特点是：

• 不了解、不保存全局拓扑信息。
• 能够解读数据包的头部，获知其二层、三层协议的控制信息，决定转发端口。
• 存储有流表，每一项分为匹配域 Match Field 和动作 Action 两部分。转发行为依赖于数据包头的信息与流表项的匹配结果，对数据包执行最先匹配成功的流表项所记录的动作。

在 OpenFlow 协议中，逻辑交换机亦称 Datapath ，以 Datapath ID 作为唯一标识。

交换机启动时，流表是空的，控制器初始化时一般会向所有交换机下发一条流表项：发往控制器^[1]。这一项的所有匹配域都是通配 (wild card) ，因此最初交换机唯一会做的就是把数据包转交给控制器。

OpenFlow 的 Packet-In 消息

OpenFlow 协议下，控制器与交换机之间的交互都依赖消息传递，不同的消息代表不同的控制信息，可以携带不同的数据。当交换机将数据包发给控制器时，采用的形式就是一个 Packet-In 消息。对于 Ryu 控制器，这个消息的格式如下^[2]：

Attribute	Description
buffer_id	ID assigned by datapath
total_len	Full length of frame
reason	Reason packet is being sent. OFPR_NO_MATCH OFPR_ACTION OFPR_INVALID_TTL
table_id	ID of the table that was looked up
cookie	Cookie of the flow entry that was looked up
match	Instance of OFPMatch
data	Ethernet frame

本次实验中，只关注reason, match, data域。交换机上流表匹配失败，则reason域为 OFPR_NO_MATCH 。实验并不引入其他原因的 Packet-In ，进而可以直接认为只要是 Packet-In 就是流表匹配失败，不检查reason域。

Ryu 控制器消息处理

OpenFlow 的消息主要分成三类：

• 控制器到交换机消息 Controller-to-Switch Messages：这是控制器主动发送给交换机的消息，最常见的就是修改流表项的 Modify Flow Entry 。
• 异步消息 Asynchronous Messages：这是交换机发给控制器的消息。
• 对称消息 Symmetric Messages：可以互发的消息，例如 Hello, Echo Request/Reply 。

Packet-In 属于异步消息，此类消息是异步处理的。

Ryu 控制器将所有到来的消息放入消息队列，每次取出一个消息调用处理函数，处理消息时可以继续接收消息。每次ryu-manager加载一个 Ryu 应用，它就启动一个协程^[3]运行消息循环，开始接收消息。

继承RyuApp基类，后，对方法使用set_ev_cls装饰器可以注册其为消息的处理函数，这个方法只需要一个参数ev，即事件对象。

@set_ev_cls(ofp_event.EventOFPPacketIn, MAIN_DISPATCHER)
def _packet_in_handler(self, ev):
    msg = ev.msg
    datapath = msg.datapath
    ofproto = datapath.ofproto
    parser = datapath.ofproto_parser

ev.msg对应 OpenFlow 协议中的 Message ，不同在于多了描述交换机实例的datapath和描述 OpenFlow 协议的ofproto属性。如果希望控制交换机发送数据包，就要用datapath.send_msg方法。

实现切换路径

建立一个简单的拓扑：

从 H1 主机到 H2 主机，有两条路径：

• H1->S1->S2->S3->S5->H2
• H1->S4->S5->H2

实现路径切换的原理是：用新的流表项替换旧的，从而改变数据包的转发端口；对应到具体的实验上，还需要让控制器感知网络的某种变化，确定在何时下发新的流表项。

流表项的下发、修改都是通过发送 Flow Entry Modify 消息完成的，用 Ryu API OFPFlowMod 构造。构造一个 Flow Entry Modify 消息至少应该指定：

• 属于哪个交换机 (Datapath)
• 优先级（决定流表项匹配时的顺序，数值大者优先进行匹配）
• 匹配域（匹配何种内容的数据包头）
• 超时时间：流表项定时删除，分为软超时（一定时间没有数据包则删除）、硬超时（一定时间后删除）两种。
• 指令：完成何种动作

OFPFlowMod将返回一个包装好的消息对象，此时调用某个datapath实例的send_msg方法发送即可。

mod = parser.OFPFlowMod(datapath=datapath,
                        priority=priority,
                        idle_timeout=idle_timeout,
                        hard_timeout=hard_timeout,
                        instructions=inst)
datapath.send_msg(mod)

若这个交换机上之前存在匹配域一致的流表项，则此项将覆盖之，完成修改。

设定流表项超时实现周期性切换

下发流表项时设定相同的硬超时，例如 5s ，则整个路径上所有的流表项 5s 后全部删除，就会发生 Table-miss 使交换机发送 Packet-In 消息到控制器。

因此，周期性切换可以用 Packet-In 消息作为触发条件：当一个非 LLDP 的数据包^[4]被发送到控制器时，就意味着交换机上发生了 Table-miss ，之前的流表项已经失效了。检查逻辑大致如下：（ARP 数据包单独处理是为了记录 IP 地址、MAC 地址、交换机端口之间的对应关系）

pkt = packet.Packet(msg.data)
eth = pkt.get_protocols(ethernet.ethernet)[0]
pkt_arp = pkt.get_protocol(arp.arp)
pkt_ipv4 = pkt.get_protocol(ipv4.ipv4)
if eth.ethertype == ether_types.ETH_TYPE_LLDP:
	return
if pkt_arp:
    # Process the ARP packet, recording the corresponding IP, MAC address and tuple (datapath id, port id).
    return
if pkt_ipv4:
    # Find a new path from the source end to the destination end, install it.
    # Re-send the packet to the next hop on the new path.
    return

按照这个逻辑来写代码，然后就会出错此处应有狗头。

逻辑是理想的，我所设想的工作过程很美好：

1. 流表项失效，数据包发生 Table-miss ，Packet-In 消息发送到控制器
2. 控制器搜索路径、下发新的流表项、重新发送这个数据包到新路径上的下一跳
3. 下一个数据包正常发送

现实的冷水泼在脸上，三步中后两步都是没有保证的。

• 控制器想要修改流表项，并不像给变量重新赋值这样简单。

  • 构造 Flow Entry Modify 消息之后，调用send_msg时只不过将这个消息送入发送队列，不保证立即发送给交换机。
  • 从控制器发往不同交换机的消息途经网络链路，其到达时间是没有保证的，不一定先发送先到达。

  这意味着，Packet-Out 消息（用来重发数据包）可能比某些 Flow Entry Modify 消息到达更早。

• 交换机转发数据包动作迅速，不会等待流表项全部就位才转发。

上述设想的工作过程，实际上依赖于特定的时序保证，然而网络运作时并没有如此良好的时序规则。

用比较简单的办法：记录上次搜索路径的时间，认为在每次搜索新路径后，短时间内（比如 1s）的 Packet-In 都是流表项没有全部就位的问题，不重新搜索路径，只作转发处理。

if pkt_ipv4:
    current = datetime.datetime.now()
    if (current - self.last[(src_dpid, dst_dpid)]).seconds > 1:
    	# Find a new path from the source end to the destination end, install it.
        self.last[(src_dpid, dst_dpid)] = current
    # Re-send the packet to the next hop on the new path.
    return

寻找新路径很容易实现，我用了模拟栈实现非递归深搜来寻找路径，得到的结果和原先的路径比较是否相同即可。路径的存储格式是(dpid, port)二元组的list，依次表示数据包经过的每一个端口。

测试时，让 H1连续 ping H2 20次：

每次时延显著变长，就是流表项超时，控制器在下发流表项、进行转发。而在控制器端，也可以看到对应的路径切换：

路径失效即时切换

在 Mininet 控制台，可以执行link up/down命令，激活或禁用某条链路，模拟物理网络中链路的连接和断开。在 OpenFlow 的视角下，链路的连接、断开反映为端口 Port 的状态变化，这同样会导致交换机向控制器发送消息。 Ryu 对此的封装有两种形式：

• OFPPortStatus消息，直接对应于 OpenFlow 的同名消息。
• EventPortAdd/Delete/Modify事件分别表示端口的增加、删除、修改；EventPortStatus事件，表示端口状态的变化。

上述的消息和事件都可以用set_ev_cls装饰器注册处理函数。简单起见，本次实验中只要端口状态变化，就认为是链路失效，删掉之前的所有流表项。这只需要注册EventPortStatus事件，在处理函数中删除保存的路径对应的流表项即可完成。

删除流表项需要发送OFPFlowMod消息，指定command参数为ofproto.OFPFC_DELETE。需要注意的是，还必须指定out_port参数，否则消息可以被发送但删除并不会发生。这里直接令out_port=ofproto.OFPP_ANY表示删除任何满足条件的流表项。

类似地，流表项被删除后下一个数据包将导致 Table-miss ，进而导致 Packet-In ，此时用最短路算法找跳数最少的路径并下发新的流表项。测试时在 Mininet 控制台执行link s1 s4 down/up就可以看到控制器端输出的路径变化情况了。

说明

这是对校内实验的一些记录和想法，实验指导书、代码框架由老师和助教编写，涉及著作权问题，故不在此展示。这里附上自己编写的一部分代码，除此之外，至少还需要处理EventOFPSwitchFeathures和EventOFPPacketIn；并在拓扑发生变化时（Switch/Port/Link的Add/Delete/Modify事件）重新获取全局拓扑。

• 搜索并保存新路径

def get_new_path(self, src, dst):
    if src == dst:
        return []
    stack = []  # use this list as a stack for DFS
    visited = defaultdict(lambda: False)
    # record the children of a certain datapath when searching
    # {dpid: [dpid, ...]}
    children = defaultdict(lambda: list())
    # record the previous port of a certain datapath
    # {dpid: (prev_dpid, prev_port, dpid, port)}
    result = defaultdict(lambda: defaultdict(lambda: None))

    stack.append(src)
    while len(stack) > 0:
        current = stack[-1]
        visited[current] = True

        if current == dst and stack != self.pathnodes[(src, dst)]:
            break

        found = False
        for (temp_src, temp_dst) in self.src_links[current]:
            if visited[temp_dst] == False:
                temp_src_port = self.src_links[current][(temp_src, temp_dst)][0]
                temp_dst_port = self.src_links[current][(temp_src, temp_dst)][1]
                result[temp_dst] = (temp_src, temp_src_port, temp_dst, temp_dst_port)
                stack.append(temp_dst)
                children[current].append(temp_dst)
                found = True
                break
        if found == False:
            stack.pop(-1)
            for child in children[current]:
                visited[child] = False

    path = []
    if dst not in result:
        return None
    self.pathnodes[(src, dst)] = stack
    while (dst in result) and (result[dst] is not None):
        path = [result[dst][2:4]] + path
        path = [result[dst][0:2]] + path
        dst = result[dst][0]
    return path

• 处理链路状态变化

def delete_flow(self, datapath, priority, match, idle_timeout=0, hard_timeout=0):
    ofproto = datapath.ofproto
    parser = datapath.ofproto_parser

    mod = parser.OFPFlowMod(datapath=datapath, priority=priority,
                            idle_timeout=idle_timeout,
                            hard_timeout=hard_timeout,
                            match=match,
                            out_port=ofproto.OFPP_ANY,
                            out_group=ofproto.OFPG_ANY,
                            command=ofproto.OFPFC_DELETE)
    datapath.send_msg(mod)

@set_ev_cls(ofp_event.EventOFPPortStatus, [CONFIG_DISPATCHER, MAIN_DISPATCHER, DEAD_DISPATCHER, HANDSHAKE_DISPATCHER])
def _port_status_handler(self, ev):
    datapath = ev.msg.datapath
    ofproto = datapath.ofproto
    parser = datapath.ofproto_parser
    if self.path is None:
        return

    for i in range(len(self.path) - 2, -1, -2):
        datapath_path = self.datapaths[self.path[i][0]]
        # delete the flow entry from src to dst
        match = parser.OFPMatch(in_port=self.path[i][1],
                                eth_src=self.eth_src, eth_dst=self.eth_dst, eth_type=0x0800,
                                ipv4_src=self.ipv4_src, ipv4_dst=self.ipv4_dst)

        self.delete_flow(datapath_path, 100, match)
        # delete the flow entry from dst to src
        match = parser.OFPMatch(in_port=self.path[i+1][1],
                                eth_src=self.eth_dst, eth_dst=self.eth_src, eth_type=0x0800,
                                ipv4_src=self.ipv4_dst, ipv4_dst=self.ipv4_src)
        self.delete_flow(datapath_path, 100, match)

注释

[1]按照 OpenFlow v1.3 标准文档 5.4 Table-miss，所有流表必须至少包含一条 Table-miss 流表项（由控制器下发），优先级为最低（0），即指定数据包匹配失败时的处理动作。最常见的动作是发往控制器，这也是 Ryu 控制器下发的 table-miss 流表项。若为 OpenFlow v1.0/1.1/1.2 标准，则无需包含 table-miss 流表项（也不需要控制器下发），匹配失败会自动发往控制器。

[2]Packet-In Message, Asynchronous Messages, OpenFlow v1.3 Messages and Structures, Ryu documentation

[3]虽然经常叫作 Thread，但 Ryu Manager 启动的不是经典意义上的线程，而是第三方库 eventlet 实现的协程。二者主要差别在于协程不能抢占，必须等待其他协程主动让出 CPU 才能执行。这一点对本次实验并无影响。

[4]LLDP 数据包是用于发现交换机、探查网络拓扑的数据包，被设定为一跳之后转发给控制器，因此会引发大量的 Packet-In 消息。如果不需要主动处理拓扑信息，LLDP 数据包可以直接丢弃。本次实验中，Packet-In 的频率远远高于流表项超时的频率，大部分都是无用的 LLDP 数据包，须加以分辨。