项目要求

  1. 利用网络中有限的流表测量网络中所有流的大小；
  2. 使用最大匹配算法求解测量方案；
  3. 将测量到的流大小在可视化平台上进行展示。

Ford-Fulkerson 算法

基本思想

最大流问题，一种组合最优化问题，就是要讨论如何充分利用装置的能力， 使得运输的流量最大，以取得最好的效果。而对于所有边的权重都非负的图来说，最大流问题需要解决的就是在每个边都对流量有所限制的前提下，最多能将多少流从起点输送到终点。

在图中有以下规则：除了源和终点以外，其他每个点的流入等于流出；所有边的流量都不超过运载值。

求出最大流的方法有很多。其中，Ford-Fulkerson 方法，即增广路方法， 简称 FF 方法是一种基础的求最大流方法。它的精髓就是加了一条反向边，加速了寻找最优路径的过程。哪怕一开始我们选择的路径是错误的，我们也可以通过后悔边不断去修正这个错误，以此达到最后正确的结果（把所有错误的情况修正了，就是正确的结果之一）。

其核心思路是：每次找出一条从源到汇的能够增加流的路径，调整流值和残留网络，不断调整直到没有增广路为止。简单来说就是，通过 DFS 或者 BFS 増广，直到不能増广为止。FF 方法的基础是：增广路定理——网络达到最大流， 当且仅当残留网络中没有增广路。

基本步骤

  1. 给每条有向边初始化一条容量为 0 的反向边。并且初始化设置起点为已经访问过
  2. 开始从起点进行 DFS，对和顶点相连的边进行检查，如果下个顶点未被访问并且此条边仍有流量就走这条边，记录此边容量并与之前的记录进行比较（没有比较就直接记录），取其中容量最小值，并以此顶点为起点进行下一轮 DFS，即进入（1）。
  3. 当 DFS 进行不下去，也就是到达终点时，对沿路的所有边容量，全部减去（2）中记录的容量最小值，并且给每条边的反向边容量增加同样大小的容量，并且将（2）中记录的容量最小值进行累加。
  4. 当整个循环过程完成，说明以源为起点无法继续找到可行的能到达终点的增广路径，则算法结束。（3）中累加所得的最终值即为最大流的量。

示例

示例拓扑图

对上图，设置 1 和 5 分别为源点和终点，进行 FF 算法。

  1. 以 sum 记录最大流的量，初始化 sum=0。以 flow 记录单次 DFS 中发现的最小容量，flow=0；
  2. 从 1 进行 DFS,先寻找到 1->2->3->5 这条路，flow=min(4,2,4),即 flow=2，让 sum 值加上 2，并且将 1->2 修改为 2，2->3 修改为 0，3->5 修改为 2，并且对应地增加反向边容量。
  3. 继续，接下来发现 1->2->4->5 这条路，flow=2,sum=4,同样减少正向边容量，增加反向边容量。
  4. 继续，接下来发现 1->3->5 这条路，flow=2，sum=6，同样减少正向边容量，增加反向边容量。
  5. 继续，接下来发现 1->3->2->4->5 这条路（这里走了反向边 3->2， 容量为 2），flow=1，sum=7，同样减少正向边容量，增加反向边容量。
  6. 此时图变为如下图，可以看出，此时没有正向路径能让 1 推送流到 5， 则算法结束，最大流大小为 7。

剩余网络图

算法实现

实现思路

EK 算法作为 FF 算法的一个特例，是在 FF 方法基础上，通过 dijkstra 选择跳数最短路来作为优先选择的遍历路径，以此来降低发现最大流所需的时间。故而主要的代码包括 dijkstra 跳数最短路的选取和 FF 的调用两部分，除此之外，要实现要求的功能，还需要计算最大流中流量最大的路径以及最大流的流量，以及当反向边上发生“反悔”事件时，还需要记录抵消的路径和打印真实路径。

代码实现

dijkstra 发现跳数最短路

（1）节点信息的初始化

1
2
3
4
5
6
7
8
9
10
11
def dijkstra(self, src_mac, dst_mac, rest): 2. 3. run = dst_mac #从宿点开始找
	nodeinfo = {}
    nodeinfo.setdefault(src_mac, {})
    nodeinfo.setdefault(dst_mac, {})
    #此处的源点和宿点均指相对于所要找的路径
    nodeinfo[src_mac].setdefault('height', 99999999) #源点距宿点的跳数设为无穷大
    nodeinfo[src_mac].setdefault('unchecked', 1) #源点初始化为未标记
    nodeinfo[src_mac].setdefault('father', -1) #父节点为空
    nodeinfo[dst_mac].setdefault('height', 0) #宿点离自己的跳数为 0
    nodeinfo[dst_mac].setdefault('unchecked', 0) #宿点初始化为已标记
    nodeinfo[dst_mac].setdefault('father', -1)#宿点父节点为空

（2）发现最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while run != src_mac: 
    for neighbor in self.adjacent[run]:
        nodeinfo.setdefault(neighbor, {})
        nodeinfo[neighbor].setdefault('height', 9999999)
        nodeinfo[neighbor].setdefault('unchecked', 1)
        nodeinfo[neighbor].setdefault('father', -1)
        for link in self.links: 
            if link['src_dpid'] == run and link['dst_dpid'] == neighbor: 
                if nodeinfo[neighbor]['height'] > nodeinfo[run]['height']+1 and rest[link['dst_dpid']][link['src_dpid']] > 0:#防止成环，以及发现路径
                    nodeinfo[neighbor]['height'] = nodeinfo[run]['height']+1#跳数加一
                    nodeinfo[neighbor]['father'] = run#更新父节点
                break #update 操作
                #寻找最短跳数
        min_height = 99999
        for new_run in nodeinfo.keys(): 
            if nodeinfo[new_run]['unchecked'] and nodeinfo[new_run]['height'] < min_height: 
                min_height = nodeinfo[new_run]['height']
                run = new_run 
        if nodeinfo[run]['unchecked']: 
            nodeinfo[run]['unchecked'] = 0
        else: 
            break

（3）跳数最短路重建，并返回跳数最短路和该路径上的流量

1
2
3
4
5
6
7
8
9
10
11
if nodeinfo[src_mac]['unchecked']: #到最后 src_mac 也没有被检查到，则说明已经没有增广路径了，返回值为空
    return [], 0
else: #有增广路径则按正序重建路径，并返回路径和路径上的流量
    father = src_mac 
    path = []
    while father != dst_mac: 
        path.append(father)
        father = nodeinfo[father]['father']
    path.append(dst_mac)
    path_bw = self.min_bw(path, rest) #调用函数，求路径上的流量
    return path, path_bw

FF 算法

（1）初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
def ford_fulkerson(self, src_mac, dst_mac): 
    flow = {}
    rest = {}
    cur_path = []
    bw = 0
    wid_path = []
    wid_bw = 0
    max_bw = 0

    rest = self.update_network([], 0, flow)
    for link in self.links: #建立剩余网络的框架
        flow.setdefault(link['src_dpid'], {})
        flow[link['src_dpid']].setdefault(link['dst_dpid'], 0)

（2） 循环增加流量，直到无法找到从源点到宿点的增广路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while True:
    cur_path, bw = self.dijkstra(src_mac, dst_mac, rest)
    if len(cur_path) == 0: 
        Break
    #无法找到从源点到宿点的增广路径时 cur_path 获取到的返回值为空，退出循环
    print("available path:{} bw:{}Mbps".format(cur_path, bw)) #打印参与到最大流的路径，注意，此时可能会发生 cancel，即反向推送
    max_bw += bw #求最大流
    rest = self.update_network(cur_path, bw, flow)#剩余网络更新
    
    if self.cancel_flag == 0 and wid_bw < bw:#如果全程没有发生反向推送，则此时的路径与现实情境下会发生的实际情况相同
        wid_path = cur_path
        wid_bw = bw 
        
print("max flow after detection:{}Mbps.".format(max_bw))#打印最大流的流量

（3）考虑到现实情境下，“反悔”现象不会发生，因此产生了路径抵消时需要 在总的路径上做一些修改，以得到最后的真实路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if self.cancel_flag == 1:
    print("Cancellations happened!")
    cur_path, bw = self.dijkstra(src_mac, dst_mac, flow)#在最终的流量网络上重新运行 dijkstra 算法，找最短路来进行路径增广
    wid_path = cur_path
    wid_bw = bw
    while True:
        if len(cur_path) != 0: 
            print("Real-path:{} {}Mbps".format(cur_path, bw))
            if bw > wid_bw:
                wid_path = cur_path
                wid_bw = bw
            for i in range(0, len(cur_path)-1): 
                flow[cur_path[i]][cur_path[i+1]] -= bw #更新流量网络
                cur_path, bw = self.dijkstra(src_mac, dst_mac, flow) #在更新后的流量网络上运行 dijkstra 寻找增广路径
        else:
            break
self.cancel_flag = 0
return wid_path, wid_bw

剩余网络更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def update_network(self, cur_path, cur_bw, flow): 
    p = cur_path
    for i in range(0, len(p)-1): 
        if flow[p[i]][p[i+1]] == 0 and flow[p[i+1]][p[i]] == 0:#尚未开始增加流量
            flow[p[i]][p[i+1]] = cur_bw#将所选择的路径流量加入流网络
        elif flow[p[i+1]][p[i]] > 0 and flow[p[i]][p[i+1]] == 0:#边上正向的流量为0，有反向的流量
            flow[p[i+1]][p[i]] -= cur_bw#发生流量抵消
            self.cancel_flag = 1#流量抵消的标记位
        else: 
            flow[p[i]][p[i+1]] += cur_bw#将所选择的路径上流量加入流网络
    rest = deepcopy(flow)
    
    for link in self.links:#构建剩余网络
        if flow[link['src_dpid']][link['dst_dpid']] == 0 and flow[link['dst_dpid']][link['src_dpid']] == 0:#边上没有流量，剩余容量即为边的带宽
            rest[link['src_dpid']][link['dst_dpid']] = link['bw']
            rest[link['dst_dpid']][link['src_dpid']] = link['bw']
        if flow[link['dst_dpid']][link['src_dpid']] > 0 and flow[link['src_dpid']][link['dst_dpid']] == 0:#边上反向有流量、正向没有流量
            rest[link['src_dpid']][link['dst_dpid']] = flow[link['dst_dpid']][link['src_dpid']]#添加反向边
            rest[link['dst_dpid']][link['src_dpid']] = link['bw'] - flow[link['dst_dpid']][link['src_dpid']]#边上反向的剩余容量为边的容量减去流量
    return rest

读取邻接点

1
2
3
4
5
6
7
def get_adjacent(self, links):
    adjacent = {}
    for link in links:
        adjacent.setdefault(link['src_dpid'], [])
        adjacent[link['src_dpid']].append(link['dst_dpid'])
        
    return adjacent

找到路径上链路容量的最小值，即能够容纳的最大流量

1
2
3
4
5
6
def min_bw(self, path, rest): 
    bw = 999999
    for i in range(0, len(path)-1): 
        if rest[path[i]][path[i+1]] < bw: 
            bw = rest[path[i]][path[i+1]]
    return bw

对 packet_in 模块的修改

（1）将主机和交换机之间的链路加入拓扑网络

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if src not in self.hosts:
    self.hosts.append(src)
    fd = open('./topo24.json', "r")
    
    topoinfo = json.load(fd)
    host_id = int(src.split(':')[-1],16)
    for edge in topoinfo['links']: 
        if (['h'+str(host_id), 's'+str(dpid)] == edge['vertexs'] or ['s'+str(dpid), 'h'+str(host_id)] == edge['vertexs']):
            self.links.append({'src_dpid':src, 'dst_dpid':dpid, 'dst_port_no':
in_port, 'delay':edge['delay'], 'bw':edge['bw']})

            self.links.append({'src_dpid':dpid, 'dst_dpid':src, 'src_port_no':
in_port, 'delay':edge['delay'], 'bw':edge['bw']})
            break

配置流量最大的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if dst in self.host_mac_to: 
    self.pathes.setdefault(src, {})
    self.pathes[src].setdefault(dst, [])
    self.pathes.setdefault(dst, {})
    self.pathes[dst].setdefault(src, [])#路径初始化
    
    if len(self.pathes[src][dst]) == 0: 
        self.pathes[src][dst], max_bw = self.ford_fulkerson(src, dst)
        self.pathes[dst][src] = self.pathes[src][dst][::-1]
        #调用 ford_fulkerson 得到返回值作为流量最大的路径
        print("Widest path:{} {}Mbps".format(self.pathes[src][dst], max_bw))
        print("================================================================")
        #读取正向和反向的端口信息，用于下发流表
    next_dpid = self.pathes[src][dst][self.pathes[src][dst].index(dpid)+1]
    for link in self.links:
        if link['src_dpid'] == dpid and link['dst_dpid'] == next_dpid:
            out_port = link['src_port_no']
            Break
     #流表配置
    actions = [ofp_parser.OFPActionOutput(out_port)]
    match = ofp_parser.OFPMatch(in_port=in_port, eth_dst=dst, eth_src=src)
    self.add_flow(datapath, 1,match, actions)

成果展示

拓扑的构建

（1）mininet侧

mininet侧拓扑构建

（2）RYU 侧

RYU侧拓扑连接

（3）二十四节点网络拓扑可视化

拓扑可视化

Ford-Fulkerson 算法实现

（1）mininet 侧：连通性良好

mininet侧连通性

（2）最大流路径展示（以 h1 ping h8 为例）

mininet侧带宽信息

（3）ryu 侧

RYU侧最大流路径配置

（4）最大流路径可视化

（黄色路径为最大流路径，黑色路径为未经过路径）

最大流路径可视化