（1）Dijkstra算法

1 class Dijkstra(Algorithm):
2 """Dijkstra algorithm for unicast route calculation.
3 """
4 def __init__(self, delay_coefficient=5000, cost_coefficient=0.02, bw_load_coefficient=50):
5 if not hasattr(self, 'cost_coeffieient'):
6 super(Dijkstra, self).__init__()
7
8 self.delay_coefficient = delay_coefficient
9 self.cost_coefficient = cost_coefficient
10 self.bw_load_coefficient = bw_load_coefficient
11
12 def __new__(cls, *args, **kwargs):
13 if not hasattr(cls, '_instance'):
14 orig = super(Dijkstra, cls)
15 cls._instance = orig.__new__(cls, *args, **kwargs)
16 return cls._instance
17
18 def get_link(self, src, dst, link_type=None):
19 dst_num = self.switch_queue.index(dst)
20
21 links_in_num = None
22 for num, link in enumerate(self.links):
23 if dst_num == link[len(link)-1]:
24 links_in_num = self.links[num]
25 break
26
27 # handle algorithm failure mode
28 if links_in_num is None:
29 logger.error("links_in_num is None")
30 return None, None
31 elif len(links_in_num) < 2:
32 # such as when no path from switch A(number:1) to switch B(number:2)
33 # the result will be [2]
34 logger.error("destination switch unreachable in graph.")
35 return None, None
36
37 self.link_cache[links_in_num[0], links_in_num[1]] = links_in_num
38 links_in_dpid = []
39 for l in links_in_num:
40 links_in_dpid.append(self.switch_queue[l])
41
42 link_cost = 0
43 for i in range(0, len(links_in_num)-1):
44 for e in self.edges:
45 if links_in_num[i] == e[1] and links_in_num[i+1] == e[2] or \
46 links_in_num[i] == e[2] and links_in_num[i+1] == e[1]:
47 link_cost += e[4]
48 break
49
50 return links_in_dpid, link_cost
51
52 def init_algorithm(self, switches, links):
53 """
54 called when topo changed.
55 both switch enter/leave or link add/delete.
56 """
57 self.switch_queue = []
58 self.edge_queue = []
59 self.switch_neighbors = {}
60 self.edge_collection = {}
61 self.vertexs = []
62 self.edges = []
63 self.links = []
64 self.fitness = []
65 self.link_cache = {}
66
67 # update switch/edge queue
68 self.switch_queue = switches.keys()
69 self.edge_queue = links.keys()
70
71 # update switch neighbors
72 for dpid, sw in switches.items():
73 num = self.switch_queue.index(dpid)
74 neighbors_in_dpid = sw.neighbors.keys()
75 neighbors_in_num = []
76 for n in neighbors_in_dpid:
77 neighbors_in_num.append(self.switch_queue.index(n))
78 self.switch_neighbors[num] = neighbors_in_num
79
80 # update edge collection
81 for dpids, edge in links.items():
82 src_num = self.switch_queue.index(dpids[0])
83 dst_num = self.switch_queue.index(dpids[1])
84 ev = edge.values()[0]
85 self.edge_collection[(src_num, dst_num)] = ev
86 self.edges.append([0, src_num, dst_num,
87 float(ev.delay), float(ev.cost),
88 ev.available_band, float(ev.total_band)])
89
90 # update self.vertexs
91 for src_num, neighbors in self.switch_neighbors.items():
92 self.vertexs.append([len(neighbors), neighbors, []])
93 for dst_num in neighbors:
94 for num, edge in enumerate(self.edges):
95 if (edge[1], edge[2]) == (src_num, dst_num) or \
96 (edge[1], edge[2]) == (dst_num, src_num):
97 self.vertexs[src_num][2].append(num)
98
99 def update_link_status(self, links):
100 self.edges = []
101 for dpids, edge in links.items():
102 src_num = self.switch_queue.index(dpids[0])
103 dst_num = self.switch_queue.index(dpids[1])
104 ev = edge.values()[0]
105 self.edge_collection[(src_num, dst_num)] = ev
106 self.edges.append([0, src_num, dst_num,
107 float(ev.delay), float(ev.cost),
108 float(ev.available_band), float(ev.total_band)])
109 logger.debug("src_dpid:%s, dst_dpid:%s, available band:%s Mbits, total band:%s Mbits, usage:%s",
110 dpids[0], dpids[1],
111 float(ev.available_band)/Megabits,
112 float(ev.total_band)/Megabits,
113 1.0 - float(ev.available_band) / float(ev.total_band))
114
115 def run(self, src_dpid, dst_dpid, min_bandwidth):
116 src_num = self.switch_queue.index(src_dpid)
117 self.links = self.calculate(src_num, self.vertexs, self.edges)
118
119 def calculate(self, sou_vertex, vertexs, edges):
120 """
121 return paths list from source vertex to all the other destination
122 vertex, such as:
123
124 when source vertex number = 5
125
126 paths = [[5, 6, 7, …, 1], [5, …, 4], [5, 8], …, [5]]
127 """
128 tag = [0 for i in range(vertexs.__len__())]
129 previous_vertex = [-1 for i in range(vertexs.__len__())]
130 paths_length = [10000 for i in range(vertexs.__len__())]
131 paths = []
132
133 vertex_selected = sou_vertex
134 tag[sou_vertex] = 1
135 paths_length[sou_vertex] = 0
136
137 for i in range(vertexs.__len__() - 1):
138 for j in range(vertexs.__len__()):
139 if tag[j] == 0:
140 min_length = paths_length[j]
141 record = j
142 break
143 for j in vertexs[vertex_selected][1]:
144 if tag[j] == 0:
145 temp = self.use_available_bandwidth_mark_weight(vertex_selected, j, edges)
146 if paths_length[vertex_selected] + temp < paths_length[j]:
147 paths_length[j] = paths_length[vertex_selected] + temp
148 previous_vertex[j] = vertex_selected
149 for j in range(vertexs.__len__()):
150 if tag[j] == 0:
151 if paths_length[j] < min_length:
152 min_length = paths_length[j]
153 record = j
154 vertex_selected = record
155 tag[vertex_selected] = 1
156 for i in range(vertexs.__len__()):
157 paths.append([i])
158 j = i
159 while not previous_vertex[j] == -1:
160 j = previous_vertex[j]
161 paths[i].insert(0, j)
162 return paths
163
164 def use_available_bandwidth_mark_weight(self, vertex1, vertex2, edges):
165 for i in range(edges.__len__()):
166 if vertex1 == edges[i][1]:
167 if vertex2 == edges[i][2]:
168 rval = (self.delay_coefficient * edges[i][3] +
169 self.cost_coefficient * edges[i][4] +
170 self.bw_load_coefficient * (1-edges[i][5]/edges[i][6]))
171 return rval
172 if vertex2 == edges[i][1]:
173 if vertex1 == edges[i][2]:
174 rval = (self.delay_coefficient * edges[i][3] +
175 self.cost_coefficient * edges[i][4] +
176 self.bw_load_coefficient * (1-edges[i][5]/edges[i][6]))
177 return rval
178 return 2 * (self.delay_coefficient * 1 +
179 self.cost_coefficient * 100 +
180 self.bw_load_coefficient * 1)
181
182 def param_to_dict(self):
183 body = json.dumps({"delay_coefficient": self.delay_coefficient,
184 "cost_coefficient": self.cost_coefficient,
185 "bw_load_coefficient": self.bw_load_coefficient})
186 return body
187
188 def param_to_json(self):
189 r = json.dumps({
190 "communication_mode": "unicast",
191 "algorithm_type": "Dij",
192 "delay_coefficient": str(self.delay_coefficient),
193 "cost_coefficient": str(self.cost_coefficient),
194 "bw_load_coefficient": str(self.bw_load_coefficient)
195 })
196 return r
197
198 def update_param(self, data):
199 if data["algorithm_type"] != "Dij":
200 return False
201
202 def update(s, k, p):
203 if k in p: return float(p[k])
204 else: return s
205
206 self.delay_coefficient = update(self.delay_coefficient, "delay_coefficient", data)
207 self.cost_coefficient = update(self.cost_coefficient, "cost_coefficient", data)
208 self.bw_load_coefficient = update(self.bw_load_coefficient, "bw_load_coefficient", data)
209 return True

（2）遗传算法