kytos-ng / pathfinder

Kytos main path finder Network Application (NApp)
https://kytos-ng.github.io/api/pathfinder.html
MIT License
0 stars 7 forks source link

`desired_links` filter can include duplicated paths #27

Closed viniarck closed 1 year ago

viniarck commented 1 year ago

I found this issue when analyzing #20 that @italovalcy has reported for undesired_links (I was assessing holistically the integration and all parameters that mef_eline could use), I realized that desired_links filter implementation is iterating over every path for each desired link (included link), so it can include multiple times if multiple links are given, instead of iterating over all paths only once (like le_cost filter does) and only including each path if any of the links are included, looks like the original implementation was meant to perform a logical or if any of the desired_links is an edge of a path then include the path. The existing unit test is only covering a case with a single link, so this case hasn't been covered properly.

You can reproduce this problem using the topology that Itatlo has provided and send this request:

curl -H 'Content-type: application/json' -X POST http://127.0.0.1:8181/api/kytos/pathfinder/v2 -d '{"source": "00:00:00:00:00:00:00:01:1", "destination": "00:00:00:00:00:00:00:05:1", " desired_links": ["'$s1_s6_id'", "'$s6_s5_id'"], "spf_max_paths": 10}' | jq -r

Here's a truncated response showing two duplicated paths that got included:

{
  "paths": [
    {
      "cost": 8,
      "hops": [
        "00:00:00:00:00:00:00:01:1",
        "00:00:00:00:00:00:00:01",
        "00:00:00:00:00:00:00:01:3",
        "00:00:00:00:00:00:00:06:3",
        "00:00:00:00:00:00:00:06",
        "00:00:00:00:00:00:00:06:2",
        "00:00:00:00:00:00:00:05:3",
        "00:00:00:00:00:00:00:05",
        "00:00:00:00:00:00:00:05:1"
      ]
    },
   ...
    {
      "cost": 8,
      "hops": [
        "00:00:00:00:00:00:00:01:1",
        "00:00:00:00:00:00:00:01",
        "00:00:00:00:00:00:00:01:3",
        "00:00:00:00:00:00:00:06:3",
        "00:00:00:00:00:00:00:06",
        "00:00:00:00:00:00:00:06:2",
        "00:00:00:00:00:00:00:05:3",
        "00:00:00:00:00:00:00:05",
        "00:00:00:00:00:00:00:05:1"
      ]
    },
  ]
}

This could've been a logical to ony include a path if a path has all edges given on desired_links but the original implementation didn't go for this, in the future, I guess we can evolve and provide another attr to specify if desired_links and undesired_links should work as a logical OR or AND when computing the filter experession, by default and historically it's been a logical OR.

viniarck commented 1 year ago

Landed on https://github.com/kytos-ng/pathfinder/pull/30