Zsolt Haraszti | 6686203 | 2016-11-28 14:28:39 -0800 | [diff] [blame] | 1 | # |
Zsolt Haraszti | 3eb27a5 | 2017-01-03 21:56:48 -0800 | [diff] [blame] | 2 | # Copyright 2017 the original author or authors. |
Zsolt Haraszti | 6686203 | 2016-11-28 14:28:39 -0800 | [diff] [blame] | 3 | # |
| 4 | # Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | # you may not use this file except in compliance with the License. |
| 6 | # You may obtain a copy of the License at |
| 7 | # |
| 8 | # http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | # |
| 10 | # Unless required by applicable law or agreed to in writing, software |
| 11 | # distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | # See the License for the specific language governing permissions and |
| 14 | # limitations under the License. |
| 15 | # |
| 16 | |
| 17 | import networkx as nx |
| 18 | |
| 19 | from voltha.core.flow_decomposer import RouteHop |
| 20 | |
| 21 | |
| 22 | class DeviceGraph(object): |
| 23 | |
| 24 | """ |
| 25 | Mixin class to compute routes in the device graph within |
| 26 | a logical device. |
| 27 | """ |
| 28 | |
| 29 | def compute_routes(self, root_proxy, logical_ports): |
| 30 | boundary_ports, graph = self._build_graph(root_proxy, logical_ports) |
| 31 | routes = self._build_routes(boundary_ports, graph) |
| 32 | return graph, routes |
| 33 | |
| 34 | def _build_graph(self, root_proxy, logical_ports): |
| 35 | |
| 36 | graph = nx.Graph() |
| 37 | |
| 38 | # walk logical device's device and port links to discover full graph |
| 39 | devices_added = set() # set of device.id's |
| 40 | ports_added = set() # set of (device.id, port_no) tuples |
| 41 | peer_links = set() |
| 42 | |
| 43 | boundary_ports = dict( |
| 44 | ((lp.device_id, lp.device_port_no), lp.ofp_port.port_no) |
| 45 | for lp in logical_ports |
| 46 | ) |
| 47 | |
| 48 | def add_device(device): |
| 49 | if device.id in devices_added: |
| 50 | return |
| 51 | |
| 52 | graph.add_node(device.id, device=device) |
| 53 | devices_added.add(device.id) |
| 54 | |
| 55 | ports = root_proxy.get('/devices/{}/ports'.format(device.id)) |
| 56 | for port in ports: |
| 57 | port_id = (device.id, port.port_no) |
| 58 | if port_id not in ports_added: |
| 59 | boundary = port_id in boundary_ports |
| 60 | graph.add_node(port_id, port=port, boundary=boundary) |
| 61 | graph.add_edge(device.id, port_id) |
| 62 | for peer in port.peers: |
| 63 | if peer.device_id not in devices_added: |
| 64 | peer_device = root_proxy.get( |
Zsolt Haraszti | 91730da | 2016-12-12 12:54:38 -0800 | [diff] [blame] | 65 | '/devices/{}'.format(peer.device_id)) |
Zsolt Haraszti | 6686203 | 2016-11-28 14:28:39 -0800 | [diff] [blame] | 66 | add_device(peer_device) |
| 67 | else: |
| 68 | peer_port_id = (peer.device_id, peer.port_no) |
| 69 | if port_id < peer_port_id: |
| 70 | peer_link = (port_id, peer_port_id) |
| 71 | else: |
| 72 | peer_link = (peer_port_id, port_id) |
| 73 | if peer_link not in peer_links: |
| 74 | graph.add_edge(*peer_link) |
| 75 | peer_links.add(peer_link) |
| 76 | |
| 77 | for logical_port in logical_ports: |
| 78 | device_id = logical_port.device_id |
| 79 | device = root_proxy.get('/devices/{}'.format(device_id)) |
| 80 | add_device(device) |
| 81 | |
| 82 | return boundary_ports, graph |
| 83 | |
| 84 | def _build_routes(self, boundary_ports, graph): |
| 85 | |
| 86 | routes = {} |
| 87 | |
| 88 | for source, source_port_no in boundary_ports.iteritems(): |
| 89 | for target, target_port_no in boundary_ports.iteritems(): |
| 90 | |
| 91 | if source is target: |
| 92 | continue |
| 93 | |
| 94 | path = nx.shortest_path(graph, source, target) |
| 95 | |
| 96 | # number of nodes in valid paths is always multiple of 3 |
| 97 | if len(path) % 3: |
| 98 | continue |
| 99 | |
| 100 | # in fact, we currently deal with single fan-out networks, |
| 101 | # so the number of hops is always 6 |
| 102 | assert len(path) == 6 |
| 103 | |
| 104 | ingress_input_port, ingress_device, ingress_output_port, \ |
| 105 | egress_input_port, egress_device, egress_output_port = path |
| 106 | |
| 107 | ingress_hop = RouteHop( |
| 108 | device=graph.node[ingress_device]['device'], |
| 109 | ingress_port=graph.node[ingress_input_port]['port'], |
| 110 | egress_port=graph.node[ingress_output_port]['port'] |
| 111 | ) |
| 112 | egress_hop = RouteHop( |
| 113 | device=graph.node[egress_device]['device'], |
| 114 | ingress_port=graph.node[egress_input_port]['port'], |
| 115 | egress_port=graph.node[egress_output_port]['port'] |
| 116 | ) |
| 117 | |
| 118 | routes[(source_port_no, target_port_no)] = [ |
| 119 | ingress_hop, egress_hop |
| 120 | ] |
| 121 | |
| 122 | return routes |
| 123 | |