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

Undesired links not working as expected #20

Closed italovalcy closed 1 year ago

italovalcy commented 2 years ago

The undesired_links should filter out undesired links in all paths found, however, it's current version is still returning paths containing links that should be excluded.

Steps to reproduce:

  1. Run Kytos latest version from Docker hub: docker run -d --name k2 --privileged amlight/kytos -E
  2. Create a topology with multiple connections at each node:
    
    # cat tests/helpers.py
    from mininet.topo import Topo
    class MultiConnectedTopo(Topo):
    """Multiply connected network topology six
    and one host connected to each switch """
    def build(self):
        # Create hosts
        h1 = self.addHost('h1', ip='0.0.0.0')
        h2 = self.addHost('h2', ip='0.0.0.0')
        h3 = self.addHost('h3', ip='0.0.0.0')
        h4 = self.addHost('h4', ip='0.0.0.0')
        h5 = self.addHost('h5', ip='0.0.0.0')
        h6 = self.addHost('h6', ip='0.0.0.0')
        # Create the switches
        s1 = self.addSwitch('s1')
        s2 = self.addSwitch('s2')
        s3 = self.addSwitch('s3')
        s4 = self.addSwitch('s4')
        s5 = self.addSwitch('s5')
        s6 = self.addSwitch('s6')
        # Add links between the switch and each host
        self.addLink(s1, h1)
        self.addLink(s2, h2)
        self.addLink(s3, h3)
        self.addLink(s4, h4)
        self.addLink(s5, h5)
        self.addLink(s6, h6)
        # Add links between the switches
        self.addLink(s1, s2)
        self.addLink(s2, s3)
        self.addLink(s3, s4)
        self.addLink(s4, s5)
        self.addLink(s5, s6)
        self.addLink(s1, s6)
        self.addLink(s2, s6)
        self.addLink(s3, s6)
        self.addLink(s4, s6)
    topos = {
    'multi': (lambda: MultiConnectedTopo()),
    }

tmux new-sess -d -s mn mn --custom tests/helpers.py --topo multi --controller=remote,ip=127.0.0.1

3. Request some paths from s1 to s5 and using the constrain undesired links = s1-s6 and s6-s5:

curl -s http://127.0.0.1:8181/api/kytos/topology/v3/links | jq -r '.links[] | .id + " " +(.endpoint_a.id|tostring) + " " + (.endpoint_b.id|tostring)' > /tmp/link-ids

s1_s6_id=$(grep :00:01: /tmp/link-ids | grep :00:06: | awk '{print $1}')

s6_s5_id=$(grep :00:06: /tmp/link-ids | grep :00:05: | awk '{print $1}')

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", "undesired_links": ["'$s1_s6_id'", "'$s6_s5_id'"], "spf_max_paths": 10}' | jq -r


4. Observe the result and check if s1-s6 or s6-s5 is present on any of the paths.

Expected result: you should see no path with s1-s6 or s6-s5

Actual result: the very first path (with cost = 14) is the path s1-s2,s2-s3,s3-s6,s6-s5

This is probably due to the fact that `_filter_paths` function is doing the [removal of list elements while iterating over the list](https://github.com/kytos-ng/pathfinder/blob/99cb431a76d9e0602f7ffb553cd57a91c11bb8e1/main.py#L74) (a known problem), specially because in this payload [the filtered_paths points to the original paths list, since no desired links were provided](https://github.com/kytos-ng/pathfinder/blob/99cb431a76d9e0602f7ffb553cd57a91c11bb8e1/main.py#L57). Another thing is: the unit test consider only a very [basic scenario](https://github.com/kytos-ng/pathfinder/blob/99cb431a76d9e0602f7ffb553cd57a91c11bb8e1/tests/unit/test_main.py#L204-L217), that was not able to capture this type of problem.
italovalcy commented 2 years ago

Attached is the topology used for this test.

Untitled Diagram drawio-2