Route Finder

Route Finder

The Route Finder (or Route Finding Service) is responsible for finding and suggesting routes between two Skywire Nodes (identified by public keys). It is expected that an App Node is to use this service to find possible routes before contacting the Setup Node.

The implementation of Route Finder requires only a single REST API endpoint.

Graph Algorithm

In order to explore routing, the route finder creates a graph that represents the current skywire network, or at least the network formed by all the reachable nodes by source node.

For this purpose, we use the mark and sweep algorithm. Such an algorithm consists of two phases.

In the first phase, every object in the graph is explored in a Deep First Search order. This means that we need to explore every transport starting from route node, accessing the transport-discovery database each time that we need to retrieve new information.

In the second phase, we remove nodes from the graph that have not been visited, and then mark every node as unvisited in preparation for the next iteration of the algorithm.

Routing algorithm

Given the previous graph we can now explore it to find the best routes from every given starting node to destiny node.

For this purpose we use a modification of Dijkstra algorithm.

Route-finder modifies this algorithm by keeping track of all the nodes that reached to destination node. This allows the ability to backtrack every best route that arrives from a different node to destination node.

Endpoint Definitions

There is one endpoint:

GET/Routes

Further documentation on the endpoint can be inspected here.