Find Best Path Using Constraints

[MarvinTorres]

IMPORTANT: See this post before merging!

This updates Pathfinder to support searching for constrained shortest flexible paths via REST API calls to the main module.

Note that the changes are so extensive that tests created for the old graph module might fail.

Overview

Note: Tests that invoked KytosGraph's _set_default_metadata() will fail, because it was removed as part of our changes.

KytosGraph has been extended to support searches for constrained flexible paths using graphs with edge attribute metadata.

Edges can now contain the following attributes:

• Priority
• Utilization
• Reliability
• Ownership
• Delay
• Bandwidth

It also uses six Filters (one for each attribute) that produce subgraphs, which have edges that meet user-specified attribute requirements, such as "Bandwidth must be 20 or more."

In addition, users can specify flexible ("would like to have") requirements on top of the base ("must have") requirements.

Implementation

REST API Documentation

Method Signature: constrained_flexible_paths(source, destination, depth=None, **metrics)

Filters

Six filters from a new Filter class are now used by KytosGraph. Each attribute maps to one Filter. Each Filter contains a required type for the value and one of three filtering functions.

When KytosGraph creates a subgraph, it picks a user-specified attribute name ("bandwidth", "delay", etc.) from the user-specified requirement list, finds the attribute's associated Filter (one of three, explained below). Then it calls that Filter's run method, which accepts a graph and user-specified attribute value and returns a subgraph. If it has more attributes to process, then it repeats everything but with new attribute names and values.

Filtering Functions

FilterLEQ Lower is better. Edges must be at most a user-specified value.

• Utilization
• Delay

FilterGEQ Higher is better. Edges must be at least a user-specified value.

• Bandwidth
• Priority
• Reliability

FilterEEQ Must match exactly. Edges must match a user-specified value.

• Ownership

Usage Examples:

1. constrained_flexible_paths("S1", "S1")
2. constrained_flexible_paths("S1", "S3", base={"bandwidth": 50})
3. constrained_flexible_paths("S1", "S2", 4, base={"ownership": "B"}, flexible={"delay": 50, "bandwidth": 100, "reliability": 3})

1 returns source, since source and destination are the same. 2 returns the shortest path from S1 to S3 with edges that have at least 50 bandwidth. 3 returns the shortest path from S1 to S2 with edges that are owned by B, with the possibility of those edges having at most 50 delay, at least 100 bandwidth, or at least 3 reliability.

Base and flexible metrics are represented as two dictionaries. To pass those dictionaries to the constrained shortest path function, use the keyword arguments base for the base requirements dictionary and flexible for the flexible requirements dictionary.

Main has been updated to reflect these changes.

Three test suites have been provided.

constrained_flexible_paths(...) returns a list of dictionaries:

[{"paths" : <set of edges from shortest path>, "metrics" : <set of fulfilled requirements> }, ...]

Each dictionary represents a shortest path, and the user-specified attributes used to find it. The base requirements are guaranteed to be fulfilled, while the flexible requirements may or may not be fulfilled.

Algorithm for constrained_flexible paths

1. If source is in the graph and source == destination, return source
2. Create subgraph A using the edges in the graph that fulfill the _base_ requirements.
3. Create "power set" P of combinations of _flexible_ requirements. Note that it's not a true power set since it excludes the empty set.
4. For each combination p(i) in P, where 1 < i < |P|
5.    Create subgraph A* using the edges from A that fulfill p(i).
6.    Find the shortest path from source to destination in A*.
7.    If at least one shortest path found, break from the for loop and return results.

• This assumes full depth (6). Depth affects the size of P - If it is less than 6 (the current max of the attribute count) then P will have fewer combinations.
• In addition, this algorithm's complexity grows exponentially based on the number of attributes, since the size of P doubles for every added attribute.

Class Diagram for Main, KytosGraph, and Filter

Sequence Diagram for constrained_flexible paths

[MarvinTorres]

Okay, I think I have everything. Let me know if I am missing anything crucial.

[MarvinTorres]

@hdiogenes @ajoaoff I have updated the original post with a link to the REST API Documentation.

[MarvinTorres]

Hi everyone, I streamlined the history of our changes to prepare for the eventual squash. Make sure that your local repository has the latest version of my logicchanges branch.

EDIT: I'm not sure why but updating my remote branch to reflect the streamline broke this PR. Will see if I can fix.

EDIT: Fixed. Turns out that I can not recreate (delete then push) this remote branch without closing this PR. I fixed it by moving logicchanges back to the last commit in the original timeline and running:

git push origin <SHA1 of last commit>:logicchanges --force

and reopening this PR.

[MarvinTorres]

@hdiogenes I updated the REST API link to show the result of rendering #62

[MarvinTorres]

@hdiogenes @gleybersonandrade @ajoaoff I have created an alternate branch logicchanges_squashed which contains an identical (changes-wise), linear, and easy-to-squash version of this timeline. Check it out here: https://github.com/MarvinTorres/pathfinder/tree/logicchanges_squashed

EDIT: A separate branch, which serves as the squashed timeline, can be found here.

[MarvinTorres]

@beraldoleal Understood. I will create several more PRs that feature bug fixes from our senior project changes.

I have also squashed the 100 changes in a separate branch. Link

[beraldoleal]

No problem @MarvinTorres.

Just make sure that each commit has a mean full description and the changes make sense for the commit itself. A big squash into a single commit is also not desirable, we need the right balance.

As a suggestion I would recommend applying on PR at the time, to avoid logical dependency and frustration. Sending a PR that depending on another PR could lead to rework and it is not desired.

Also, I haven't looked closely here, but based on your descriptions and diagrams this seems to me that is not a small change/fix. I'm assuming that you have discussed this openly in a blueprint or issue about this before sending such a big change. I will wait for the smaller PR to comment properly on that.

https://docs.kytos.io/developer/how_to_contribute/#submitting-a-pull-request

[hdiogenes]

Superseded by #68