Ryu

本文的Ryu 路由代码源于Ryu中通过DIjkstra计算最短路径博客,并且后续也可能在其上改进,现对其部分代码进行分析,文末为完整代码。

总览

路由APP分为地址查询、路由算法和流表生成三个步骤,路由算法部分纯粹计算,没有过于关注,详细关注了地址查询、流表生成部分。

数据结构

  • mac_map: ([(mac, dpid, in_port])的数据结构,即mac地址与dpid,in_port的对应关系,在SDN中,mac作为唯一标识地址,而dpid,in_port则可以确定主机的物理连接;
  • mac_to_port: ([(dpid, mac, port)])的数据结构,其实和上面一样,不过索引不一样,换为dpid;
  • p: ([dpid, in_port, out_port])的数据结构,该数据在路由计算后生成,用于安装流表;
  • adjacency: 存储全网的拓扑([dpid_src, dpid_dst ,port_src]),port_src为dpid_src->dpid_dst的源端口;
  • datapath_list: 所有交换机的列表;
  • path_map:(dpid_src, dpid_dst, (distance, dpid_inter))这个应该是启动之初建立的路由表,其中distance为两dpid的距离,dpid_inter为两dpid的路径间可能经过的中间节点dpid(这个中间节点是dj路由算法中得到的)

步骤流程

  1. 收到packet_in,更新维护mac_map(补充mac_map);
  2. 查找mac_to_port,mac是否在该流表中,若在其中,则调用install_path(src_dpid, dst_dpid, in_port, in_port),开始计算、安装路由;
  3. 路由计算(_get_path->_get_raw_path->_dijkstra_paths)的输入为(src_dpid, port)和(dst_dpid, port),输入出p,即为沿途交换机待安装的流表规则;
  4. 安装流表(_install_path): 为沿途每个dpid安装流表,match字段为in_port, actions字段为output: out_port,优先级为1,hard_time为0(永久)。

Dj算法

这里先贴出部分Dj算法,只含思想,源于最短路径—Dijkstra算法和Floyd算法博客,详细介绍可看他的博客。

Dj算法思想步骤

  1. 初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则正常有权值,若u不是v的出边邻接点,则权值为∞。,v>,v>
  2. 从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
  3. 以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。
  4. 重复步骤b和c直到所有顶点都包含在S中。

Ryu实现思想步骤

  1. 路由函数输入获取:由总览可知,一个packet-in消息收到之后,取出mac_src,mac-dst,然后可以通过mac_to_port 等确定源、目的主机的(dpid,port),然后作为输入(dpid_src, dpid_dst, port_src, port_dst),进行路由计算;
  2. 路由计算:这一步主要分为两步,1)获取路径,沿途的dpid,2)根据沿途dpid确定流表(in_port, output_port)。函数调用关系为install_path->_get_path->_get_raw_path->_dijkstra_paths,其中_get_raw_path和_dijkstra_paths为第一步,install_path和_get_path为第二步;
  3. 流表安装

Dj核心算法函数

下面依次介绍上述路由计算中的四个函数:

_dijkstra_paths

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
def _dijkstra_paths():
#clear everytime? no, only the first time
path_map.clear()

#初始化path_map(相邻的dpid距离为1)
for k in sws:
for j, port in adjacency[k].iteritems():
if port is None:
continue
path_map[k][j] = (1, None)
path_map[k][k] = (0, None)
print adjacency[k]

#dj算法,无需多介绍
for t in sws:
final_point = []
final_point.append(t)
for i in range(len(sws) - 1):
min_path = 999
for p in sws:
if p not in final_point:
if path_map[t][p][0] is not None and path_map[t][p][0] < min_path:
min_path = path_map[t][p][0]
temp = p
final_point.append(temp)
for m in sws:
if m not in final_point:
if path_map[t][m][0] is None and path_map[t][temp][0] is not None and path_map[temp][m][
0] is not None:
path_map[t][m] = (path_map[t][temp][0] + path_map[temp][m][0], temp)
elif path_map[t][temp][0] is not None and path_map[temp][m][0] is not None and path_map[t][m][
0] is not None:
if path_map[t][temp][0] + path_map[temp][m][0] < path_map[t][m][0]:
path_map[t][m] = (path_map[t][temp][0] + path_map[temp][m][0], temp)
print path_map
  • 最终得到:path_map:(dpid_src, dpid_dst, (distance, dpid_inter))这个应该是启动之初建立的路由表,其中distance为两dpid的距离,dpid_inter为两dpid的路径间可能经过的中间节点dpid(这个中间节点是dj路由算法中得到的)

_get_raw_path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def _get_raw_path(src, dst):
"""
Get a raw path (just a list of nodes to traverse)
"""
if len(path_map) == 0: _dijkstra_paths()
if src is dst:
# We're here!
return []

if path_map[src][dst][0] is None:
return None
#path_map的数据结构可知[src][dst][1]为路径上某中间节点dpid
intermediate = path_map[src][dst][1]
if intermediate is None:
# Directly connected
return []
#非常巧妙的运用了迭代
return _get_raw_path(src, intermediate) + [intermediate] +
_get_raw_path(intermediate, dst)
  • 可以看到末尾的迭代思想,最终返回的是沿途所有的节点的dpid

_get_path

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
def _get_path(src, dst, first_port, final_port):
"""
Gets a cooked path -- a list of (node,in_port,out_port)
"""
# Start with a raw path...
print src
print dst
if src == dst:
path = [src]
else:
path = _get_raw_path(src, dst)
if path is None: return None
path = [src] + path + [dst]

# Now add the ports
r = []
in_port = first_port
#非常巧妙的运用了zip函数
for s1, s2 in zip(path[:-1], path[1:]):
out_port = adjacency[s1][s2]
r.append((s1, in_port, out_port))
in_port = adjacency[s2][s1]
r.append((dst, in_port, final_port))
print 'R is %s' % r
return r
  • 这里找到上一步各个dpid之间连接的port(路径),主要是通过aj邻接矩阵获取,(见数据结构:adjacency: 存储全网的拓扑([dpid_src, dpid_dst ,port_src]),port_src为dpid_src->dpid_dst的源端口);另外,这里巧妙运用zip函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #zip 示例如下
    >>>a = [1,2,3]
    >>> b = [4,5,6]
    >>> c = [4,5,6,7,8]
    >>> zipped = zip(a,b) # 打包为元组的列表
    [(1, 4), (2, 5), (3, 6)]
    >>> zip(a,c) # 元素个数与最短的列表一致
    [(1, 4), (2, 5), (3, 6)]
    >>> zip(*zipped) # 与 zip 相反,可理解为解压,返回二维矩阵式
    [(1, 2, 3), (4, 5, 6)]
  • 最终获得每个途径dpid的in_port, output_port

    install_path

    有了上面的,安装流表就比较简单了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def install_path(self, src_sw, dst_sw, in_port, last_port, ev):
    """
    Attempts to install a path between this switch and some destination
    """
    p = _get_path(src_sw, dst_sw, in_port, last_port)
    self._install_path(p, ev)
    # Now reverse it and install it backwards
    # (we'll just assume that will work)
    p = [(sw, out_port, in_port) for sw, in_port, out_port in p]
    self._install_path(p, ev)

    def _install_path(self, p, ev):
    msg = ev.msg
    datapath = msg.datapath
    ofproto = datapath.ofproto
    parser = datapath.ofproto_parser
    for sw, in_port, out_port in p:
    match = parser.OFPMatch(in_port=in_port)
    actions = [parser.OFPActionOutput(out_port)]
    ID = int(sw[-1:])
    datapath = self.datapath_list[ID]
    self.add_flow(datapath, 1, match, actions)

这里就是我觉得有问题的地方了:

1
2
match字段为in_port;
action output为out_port;

这样的话显然就有问题了 match 中应该是 mac_dstand in_port

完整代码及代码出处

Ryu中通过DIjkstra计算最短路径博客
http://blog.csdn.net/xuchenhuics/article/details/44494249

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
# Copyright (C) 2011 Nippon Telegraph and Telephone Corporation.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
# implied.
# See the License for the specific language governing permissions and
# limitations under the License.

from ryu.base import app_manager
from ryu.controller import ofp_event
from ryu.controller.handler import CONFIG_DISPATCHER, MAIN_DISPATCHER, DEAD_DISPATCHER
from ryu.controller.handler import set_ev_cls
from ryu.ofproto import ofproto_v1_3
from ryu.lib.packet import packet
from ryu.lib.packet import ethernet
from ryu.lib.packet import arp
from ryu.lib.packet import ipv4
from collections import defaultdict
from ryu.topology.api import get_switch, get_link
from ryu.topology import event, switches

ARP = arp.arp.__name__
ETHERNET = ethernet.ethernet.__name__
ETHERNET_MULTICAST = "ff:ff:ff:ff:ff:ff"

adjacency = defaultdict(lambda: defaultdict(lambda: None))
path_map = defaultdict(lambda: defaultdict(lambda: (None, None)))
sws = []
switches = {}
mac_map = {}


def _get_raw_path(src, dst):
"""
Get a raw path (just a list of nodes to traverse)
"""
if len(path_map) == 0: _dijkstra_paths()
if src is dst:
# We're here!
return []

if path_map[src][dst][0] is None:
return None
intermediate = path_map[src][dst][1]
if intermediate is None:
# Directly connected
return []
return _get_raw_path(src, intermediate) + [intermediate] +
_get_raw_path(intermediate, dst)


def _get_path(src, dst, first_port, final_port):
"""
Gets a cooked path -- a list of (node,in_port,out_port)
"""
# Start with a raw path...
print src
print dst
if src == dst:
path = [src]
else:
path = _get_raw_path(src, dst)
if path is None: return None
path = [src] + path + [dst]

# Now add the ports
r = []
in_port = first_port
for s1, s2 in zip(path[:-1], path[1:]):
out_port = adjacency[s1][s2]
r.append((s1, in_port, out_port))
in_port = adjacency[s2][s1]
r.append((dst, in_port, final_port))
print 'R is %s' % r
return r


def _dijkstra_paths():
#clear everytime? no, only the first time
path_map.clear()
for k in sws:
for j, port in adjacency[k].iteritems():
if port is None:
continue
path_map[k][j] = (1, None)
path_map[k][k] = (0, None)
print adjacency[k]

for t in sws:
final_point = []
final_point.append(t)
for i in range(len(sws) - 1):
min_path = 999
for p in sws:
if p not in final_point:
if path_map[t][p][0] is not None and path_map[t][p][0] < min_path:
min_path = path_map[t][p][0]
temp = p
final_point.append(temp)
for m in sws:
if m not in final_point:
if path_map[t][m][0] is None and path_map[t][temp][0] is not None and path_map[temp][m][
0] is not None:
path_map[t][m] = (path_map[t][temp][0] + path_map[temp][m][0], temp)
elif path_map[t][temp][0] is not None and path_map[temp][m][0] is not None and path_map[t][m][
0] is not None:
if path_map[t][temp][0] + path_map[temp][m][0] < path_map[t][m][0]:
path_map[t][m] = (path_map[t][temp][0] + path_map[temp][m][0], temp)
print path_map


class SimpleSwitch13(app_manager.RyuApp):
OFP_VERSIONS = [ofproto_v1_3.OFP_VERSION]

def __init__(self, *args, **kwargs):
super(SimpleSwitch13, self).__init__(*args, **kwargs)
self.mac_to_port = {}
self.arp_table = {}
self.sw = {}
self.port_tx = {}
self.datapaths = {}
self.datapath_list = {}
self.topology_api_app = self

@set_ev_cls(ofp_event.EventOFPSwitchFeatures, CONFIG_DISPATCHER)
def switch_features_handler(self, ev):
datapath = ev.msg.datapath
ofproto = datapath.ofproto
parser = datapath.ofproto_parser
switches[datapath.id] = datapath

# install table-miss flow entry
#
# We specify NO BUFFER to max_len of the output action due to
# OVS bug. At this moment, if we specify a lesser number, e.g.,
# 128, OVS will send Packet-In with invalid buffer_id and
# truncated packet data. In that case, we cannot output packets
# correctly. The bug has been fixed in OVS v2.1.0.
match = parser.OFPMatch()
actions = [parser.OFPActionOutput(ofproto.OFPP_CONTROLLER,
ofproto.OFPCML_NO_BUFFER)]
self.add_flow(datapath, 0, match, actions)

def add_flow(self, datapath, priority, match, actions):
self.logger.debug("add_flow: match:%s, actions:%s", match,actions)
ofproto = datapath.ofproto
parser = datapath.ofproto_parser

inst = [parser.OFPInstructionActions(ofproto.OFPIT_APPLY_ACTIONS,
actions)]

# mod = parser.OFPFlowMod(datapath=datapath, priority=priority,
# hard_timeout=20,
# match=match, instructions=inst)
#


# mod = parser.OFPFlowMod(datapath=datapath,
# match=match,cookie=0,
# command=ofproto.OFPFC_ADD,hard_timeout=0,
# priority=ofproto.OFP_DEFAULT_PRIORITY, instructions=inst)

mod = parser.OFPFlowMod(datapath=datapath,priority=priority,
match=match,cookie=0,
hard_timeout=0,
instructions=inst)

datapath.send_msg(mod)

@set_ev_cls(ofp_event.EventOFPPacketIn, MAIN_DISPATCHER)
def _packet_in_handler(self, ev):
# If you hit this you might want to increase
# the "miss_send_length" of your switch
if ev.msg.msg_len < ev.msg.total_len:
self.logger.debug("packet truncated: only %s of %s bytes",
ev.msg.msg_len, ev.msg.total_len)
msg = ev.msg
datapath = msg.datapath
ofproto = datapath.ofproto
parser = datapath.ofproto_parser
in_port = msg.match['in_port']

pkt = packet.Packet(msg.data)
eth = pkt.get_protocols(ethernet.ethernet)[0]
# avoid broadcast from LLDP
if eth.ethertype == 35020:
return

dst = eth.dst
src = eth.src

# it is wrong , dpid is 64bit, not 48bit
loc = ('00-00-00-00-00-0' + str(datapath.id), in_port)
oldloc = mac_map.get(src)
if oldloc is None:
mac_map[src] = loc
elif src not in mac_map:
mac_map[src] = loc

dpid = datapath.id
self.mac_to_port.setdefault(dpid, {})

header_list = dict(
(p.protocol_name, p) for p in pkt.protocols if type(p) != str)
if ARP in header_list:
self.arp_table[header_list[ARP].src_ip] = src # ARP learning

# print type(src),src
if eth.ethertype != 35020 and ( src == '00:00:00:00:00:01' or src == '00:00:00:00:00:02'):
self.logger.info("packet in %s %s %s %s", dpid, src, dst, in_port)

# learn a mac address to avoid FLOOD next time.
if src not in self.mac_to_port[dpid]: # record only one in_port
self.mac_to_port[dpid][src] = in_port

if dst in self.mac_to_port[dpid]:
out_port = self.mac_to_port[dpid][dst]
temp_src = mac_map[src] # (dpid,in_port)
temp_dst = mac_map[dst] # (dpid,in_port)
self.install_path(temp_src[0], temp_dst[0], temp_src[1], temp_dst[1], ev)
self.logger.info("out_port: %s", out_port)
else:
out_port = ofproto.OFPP_FLOOD
print"flood!"

actions = [parser.OFPActionOutput(out_port)]

# install a flow to avoid packet_in next time
if out_port != ofproto.OFPP_FLOOD:
match = parser.OFPMatch(in_port=in_port, eth_dst=dst)

data = None
if msg.buffer_id == ofproto.OFP_NO_BUFFER:
data = msg.data

out = parser.OFPPacketOut(datapath=datapath, buffer_id=msg.buffer_id,
in_port=in_port, actions=actions, data=data)
datapath.send_msg(out)
print "A",adjacency
print "path_map",path_map

@set_ev_cls(ofp_event.EventOFPStateChange, [MAIN_DISPATCHER, DEAD_DISPATCHER])
def state_change_handler(self, ev):
datapath = ev.datapath
if ev.state == MAIN_DISPATCHER:
if datapath.id == 1:
self.datapaths[datapath.id] = datapath
if not datapath.id in self.datapath_list:
self.datapath_list[datapath.id] = datapath
elif ev.state == DEAD_DISPATCHER:
if datapath.id in self.datapaths:
del self.datapaths[datapath.id]

def install_path(self, src_sw, dst_sw, in_port, last_port, ev):
"""
Attempts to install a path between this switch and some destination
"""
p = _get_path(src_sw, dst_sw, in_port, last_port)
self._install_path(p, ev)
# Now reverse it and install it backwards
# (we'll just assume that will work)
p = [(sw, out_port, in_port) for sw, in_port, out_port in p]
self._install_path(p, ev)

def _install_path(self, p, ev):
msg = ev.msg
datapath = msg.datapath
ofproto = datapath.ofproto
parser = datapath.ofproto_parser
for sw, in_port, out_port in p:
match = parser.OFPMatch(in_port=in_port)
actions = [parser.OFPActionOutput(out_port)]
ID = int(sw[-1:])
datapath = self.datapath_list[ID]
self.add_flow(datapath, 1, match, actions)

@set_ev_cls(event.EventSwitchEnter)
def get_topology(self, ev):
switch_list = get_switch(self.topology_api_app, None)
global sws
# assign mac for swtich to easy read
sws = ['00-00-00-00-00-0' + str(switch.dp.id) for switch in switch_list]
links_list = get_link(self.topology_api_app, None)
for link in links_list:
sw_src = '00-00-00-00-00-0' + str(link.src.dpid)
sw_dst = '00-00-00-00-00-0' + str(link.dst.dpid)
adjacency[sw_src][sw_dst] = link.src.port_no