|
1
|
|
|
"""Main module of kytos/pathfinder Kytos Network Application.""" |
|
2
|
|
|
|
|
3
|
1 |
|
import pathlib |
|
4
|
1 |
|
from threading import Lock |
|
5
|
1 |
|
from typing import Generator |
|
6
|
|
|
|
|
7
|
1 |
|
from kytos.core import KytosNApp, log, rest |
|
8
|
1 |
|
from kytos.core.helpers import listen_to, load_spec, validate_openapi |
|
9
|
1 |
|
from kytos.core.rest_api import (HTTPException, JSONResponse, Request, |
|
10
|
|
|
get_json_or_400) |
|
11
|
1 |
|
from napps.kytos.pathfinder.graph import KytosGraph |
|
12
|
|
|
|
|
13
|
|
|
|
|
14
|
1 |
|
class Main(KytosNApp): |
|
15
|
|
|
""" |
|
16
|
|
|
Main class of kytos/pathfinder NApp. |
|
17
|
|
|
|
|
18
|
|
|
This class is the entry point for this napp. |
|
19
|
|
|
""" |
|
20
|
|
|
|
|
21
|
1 |
|
spec = load_spec(pathlib.Path(__file__).parent / "openapi.yml") |
|
22
|
|
|
|
|
23
|
1 |
|
def setup(self): |
|
24
|
|
|
"""Create a graph to handle the nodes and edges.""" |
|
25
|
1 |
|
self.graph = KytosGraph() |
|
26
|
1 |
|
self._topology = None |
|
27
|
1 |
|
self._lock = Lock() |
|
28
|
1 |
|
self._topology_updated_at = None |
|
29
|
1 |
|
self._links_updated_at = {} |
|
30
|
|
|
|
|
31
|
1 |
|
def execute(self): |
|
32
|
|
|
"""Do nothing.""" |
|
33
|
|
|
|
|
34
|
1 |
|
def shutdown(self): |
|
35
|
|
|
"""Shutdown the napp.""" |
|
36
|
|
|
|
|
37
|
1 |
|
def _filter_paths_le_cost(self, paths, max_cost): |
|
38
|
|
|
"""Filter by paths where the cost is le <= max_cost.""" |
|
39
|
1 |
|
if not max_cost: |
|
40
|
1 |
|
return paths |
|
41
|
1 |
|
return [path for path in paths if path["cost"] <= max_cost] |
|
42
|
|
|
|
|
43
|
1 |
|
def _non_excluded_edges(self, links: list[str]) -> list[tuple[str, str]]: |
|
44
|
|
|
"""Exlude undesired links. It'll return the remaning edges.""" |
|
45
|
|
|
|
|
46
|
1 |
|
endpoints: list[tuple[str, str]] = [] |
|
47
|
1 |
|
if not self._topology: |
|
48
|
1 |
|
return endpoints |
|
49
|
1 |
|
endpoint_ids = self._map_endpoints_from_link_ids(links) |
|
50
|
1 |
|
for edge in self.graph.graph.edges: |
|
51
|
1 |
|
if edge not in endpoint_ids: |
|
52
|
1 |
|
endpoints.append(edge) |
|
53
|
1 |
|
return endpoints |
|
54
|
|
|
|
|
55
|
1 |
|
def _map_endpoints_from_link_ids(self, link_ids: list[str]) -> dict: |
|
56
|
|
|
"""Map endpoints from link ids.""" |
|
57
|
1 |
|
endpoints = {} |
|
58
|
1 |
|
for link_id in link_ids: |
|
59
|
1 |
|
try: |
|
60
|
1 |
|
link = self._topology.links[link_id] |
|
61
|
1 |
|
endpoint_a, endpoint_b = link.endpoint_a, link.endpoint_b |
|
62
|
1 |
|
endpoints[(endpoint_a.id, endpoint_b.id)] = link |
|
63
|
|
|
except KeyError: |
|
64
|
|
|
pass |
|
65
|
1 |
|
return endpoints |
|
66
|
|
|
|
|
67
|
1 |
|
def _find_all_link_ids( |
|
68
|
|
|
self, paths: list[dict], link_ids: list[str] |
|
69
|
|
|
) -> Generator[int, None, None]: |
|
70
|
|
|
"""Find indexes of the paths that contain all link ids.""" |
|
71
|
|
|
endpoints_links = self._map_endpoints_from_link_ids(link_ids) |
|
72
|
|
|
if not endpoints_links: |
|
73
|
|
|
return None |
|
74
|
|
|
endpoint_keys = set(endpoints_links.keys()) |
|
75
|
|
|
for idx, path in enumerate(paths): |
|
76
|
|
|
head, tail, found_endpoints = path["hops"][:-1], path["hops"][1:], set() |
|
77
|
|
|
for endpoint_a, endpoint_b in zip(head, tail): |
|
78
|
|
|
if (endpoint_a, endpoint_b) in endpoints_links: |
|
79
|
|
|
found_endpoints.add((endpoint_a, endpoint_b)) |
|
80
|
|
|
if (endpoint_b, endpoint_a) in endpoints_links: |
|
81
|
|
|
found_endpoints.add((endpoint_b, endpoint_a)) |
|
82
|
|
|
if found_endpoints == endpoint_keys: |
|
83
|
|
|
yield idx |
|
84
|
|
|
return None |
|
85
|
|
|
|
|
86
|
1 |
|
@rest("v3/", methods=["POST"]) |
|
87
|
1 |
|
@validate_openapi(spec) |
|
88
|
1 |
|
def shortest_path(self, request: Request) -> JSONResponse: |
|
89
|
|
|
"""Calculate the best path between the source and destination.""" |
|
90
|
1 |
|
data = get_json_or_400(request, self.controller.loop) |
|
91
|
1 |
|
if not isinstance(data, dict): |
|
92
|
|
|
raise HTTPException(400, detail=f"Invalid body value: {data}") |
|
93
|
|
|
|
|
94
|
1 |
|
undesired = data.get("undesired_links", []) |
|
95
|
1 |
|
spf_attr = data.get("spf_attribute", "hop") |
|
96
|
1 |
|
spf_max_paths = data.get("spf_max_paths", 2) |
|
97
|
1 |
|
spf_max_path_cost = data.get("spf_max_path_cost") |
|
98
|
1 |
|
mandatory_metrics = data.get("mandatory_metrics", {}) |
|
99
|
1 |
|
flexible_metrics = data.get("flexible_metrics", {}) |
|
100
|
1 |
|
minimum_hits = data.get("minimum_flexible_hits") |
|
101
|
1 |
|
log.debug(f"POST v2/ payload data: {data}") |
|
102
|
|
|
|
|
103
|
1 |
|
try: |
|
104
|
1 |
|
with self._lock: |
|
105
|
1 |
|
graph = self.graph.graph |
|
106
|
1 |
|
if undesired: |
|
107
|
|
|
non_excluded_edges = self._non_excluded_edges(undesired) |
|
108
|
|
|
graph = graph.edge_subgraph(non_excluded_edges) |
|
109
|
|
|
|
|
110
|
1 |
|
if any([mandatory_metrics, flexible_metrics]): |
|
111
|
1 |
|
paths = self.graph.constrained_k_shortest_paths( |
|
112
|
|
|
data["source"], |
|
113
|
|
|
data["destination"], |
|
114
|
|
|
weight=self.graph.spf_edge_data_cbs[spf_attr], |
|
115
|
|
|
k=spf_max_paths, |
|
116
|
|
|
graph=graph, |
|
117
|
|
|
minimum_hits=minimum_hits, |
|
118
|
|
|
mandatory_metrics=mandatory_metrics, |
|
119
|
|
|
flexible_metrics=flexible_metrics, |
|
120
|
|
|
) |
|
121
|
|
|
else: |
|
122
|
1 |
|
paths = self.graph.k_shortest_paths( |
|
123
|
|
|
data["source"], |
|
124
|
|
|
data["destination"], |
|
125
|
|
|
weight=self.graph.spf_edge_data_cbs[spf_attr], |
|
126
|
|
|
k=spf_max_paths, |
|
127
|
|
|
graph=graph, |
|
128
|
|
|
) |
|
129
|
|
|
|
|
130
|
1 |
|
paths = self.graph.path_cost_builder( |
|
131
|
|
|
paths, |
|
132
|
|
|
weight=spf_attr, |
|
133
|
|
|
) |
|
134
|
1 |
|
log.debug(f"Found paths: {paths}") |
|
135
|
1 |
|
except TypeError as err: |
|
136
|
1 |
|
raise HTTPException(400, str(err)) |
|
137
|
|
|
|
|
138
|
1 |
|
paths = self._filter_paths_le_cost(paths, max_cost=spf_max_path_cost) |
|
139
|
1 |
|
log.debug(f"Filtered paths: {paths}") |
|
140
|
1 |
|
return JSONResponse({"paths": paths}) |
|
141
|
|
|
|
|
142
|
1 |
|
@listen_to( |
|
143
|
|
|
"kytos.topology.updated", |
|
144
|
|
|
"kytos/topology.topology_loaded", |
|
145
|
|
|
) |
|
146
|
1 |
|
def on_topology_updated(self, event): |
|
147
|
|
|
"""Update the graph when the network topology is updated.""" |
|
148
|
|
|
self.update_topology(event) |
|
149
|
|
|
|
|
150
|
1 |
|
def update_topology(self, event): |
|
151
|
|
|
"""Update the graph when the network topology is updated.""" |
|
152
|
1 |
|
if "topology" not in event.content: |
|
153
|
1 |
|
return |
|
154
|
1 |
|
topology = event.content["topology"] |
|
155
|
1 |
|
with self._lock: |
|
156
|
1 |
|
if ( |
|
157
|
|
|
self._topology_updated_at |
|
158
|
|
|
and self._topology_updated_at > event.timestamp |
|
159
|
|
|
): |
|
160
|
1 |
|
return |
|
161
|
1 |
|
self._topology = topology |
|
162
|
1 |
|
self._topology_updated_at = event.timestamp |
|
163
|
1 |
|
self.graph.update_topology(topology) |
|
164
|
1 |
|
switches = list(topology.switches.keys()) |
|
165
|
1 |
|
links = list(topology.links.keys()) |
|
166
|
|
|
log.debug(f"Topology graph updated with switches: {switches}, links: {links}.") |
|
167
|
|
|
|
kytos-ng /
pathfinder
