Path Computation Element

Path Computation Element, also called PCE, is a component of Atlanticwave SDX project.

The problem PCE aims to solve is this: given a network topology and a set of connection requests between some nodes in the topology that must satisfy some requirements (regarding bandwidth, latency, number of hops, packet loss, etc.) how do we find the right path between the given nodes?

Using PCE

PCE's API is still evolving. With that caveat, and omitting some details, the general usage is like this:

from sdx.pce.load_balancing.te_solver import TESolver
from sdx.pce.topology.temanager import TEManager

temanager = TEManager(initial_topology, connection_request)
for topology in topologies:
    temanager.add_topology(topology)
    
graph = temanager.generate_graph_te()
traffic_matrix = temanager.generate_connection_te()

solution = TESolver(graph, traffic_matrix).solve()

Note that PCE requires two inputs: network topology and connection requests. For testing, a random topology generator and a random connection request generator is available.

In the intermediate steps, network topology is generated by NetworkX and the traffic matrix computation is executed by Google OR-Tools Solver.

Network Topology

The Network Topology should be in the format of NetworkX graph. For each link, three attributes need to be assigned: cost, bandwidth and latency. The current unit of each attribute is abstract, but the unit in the Network Topology should be consistent with the unit in Connections.

Connection Requests

Format of a connection request is in the form of [[Source node, Destination node, Bandwidth required, Latency required],..]. Here is an example of a random connection request:

[[1,10,8,20],[2,9,10,15],[15,10,6,22]]

There are three queries in this connection request. The first one is [1,10,8,20], and it means this connection query is to route traffic from Node 1 to Node 10, requring a bandwith of 8 and maximum latency of 20.

Working with PCE code

Working with PCE in a virtual environment is a good idea, with a workflow like this:

$ git clone https://github.com/atlanticwave-sdx/pce.git
$ cd pce
$ python3 -m venv venv --upgrade-deps
$ source venv/bin/activate
$ pip install .[test]

Please note that editable installs do not work currently, due to the shared top-level sdx module in datamodel.

PCE can read topology data from Graphviz dot files, if the optional pygraphviz dependency is installed with:

$ pip install .[pygraphviz]

In order to be able to install pygraphviz, you will also need a C compiler and development libraries and headers of graphviz installed.

Running tests

To run tests, using tox is recommended:

$ tox

With tox, you can run single tests like so:

$ tox -- [-s] tests/test_te_manager.py::TestTEManager::test_generate_solver_input

The test that depend on pygraphviz are skipped by default. If you are able to install pygraphviz in your setup, you can run that test too with:

$ tox -e extras

Test data is stored in tests/data as JSON files.