feature: Add last and loop for traces

[gretelliz]

Closes #37

Summary

This PR is for adding the loop and last types to traces. Currently, only 'starting' and 'trace' are supported.

Criteria in the proposed solution:

• loop: In each trace step it is analyzed if the following step leads to a loop. In such a case a last entry is added to the trace list with the type loop.

  Question: Is it desired that the last entry indicating the loop appear? In this ref, the list of traces is returned once a loop is detected, but the corresponding trace is not added.

• last: This type is assigned to traces that meet one of the following criteria: a) find_endpoint is None: This means that dpid is not in the result from trace_step b) switch is None

• incomplete: This type is temporal and is currently assigned in the case: a) trace_step returns None: This means that switch is not in stored_flows or there are not match_flows.

Local Tests

Topo: Linear(4)

Create a flow

curl -X POST -H 'Content-type: application/json' -d '{"flows": [{"priority": 10, "match": {"in_port": 1, "dl_vlan": 777}}]}' http://127.0.0.1:8181/api/kytos/flow_manager/v2/flows/00:00:00:00:00:00:00:01

Test 1:

curl -H 'Content-type: application/json' -X PUT http://127.0.0.1:8181/api/amlight/sdntrace_cp/trace -d '{"trace": {"switch": {"dpid": "00:00:00:00:00:00:00:01", "in_port": 1}, "eth": {"dl_type": 33024, "dl_vlan": 777}}}'

Response:

{"result":[{"dpid":"00:00:00:00:00:00:00:01","port":1,"time":"2023-02-17 10:00:26.629845","type":"starting","vlan":777},{"dpid":"00:00:00:00:00:00:00:02","port":2,"time":"2023-02-17 10:00:26.629922","type":"trace","vlan":3824},{"dpid":"00:00:00:00:00:00:00:03","port":2,"time":"2023-02-17 10:00:26.629956","type":"trace","vlan":4001},{"dpid":"00:00:00:00:00:00:00:02","out":null,"port":2,"time":"2023-02-17 10:00:26.629984","type":"loop","vlan":777}]}

Test 2:

curl -H 'Content-type: application/json' -X PUT http://127.0.0.1:8181/api/amlight/sdntrace_cp/trace -d '{"trace": {"switch": {"dpid": "00:00:00:00:00:00:00:02", "in_port": 1}, "eth": {"dl_type": 33024, "dl_vlan": 777}}}'

Response:

{"result":[{"dpid":"00:00:00:00:00:00:00:02","out":null,"port":1,"time":"2023-02-17 10:00:58.361897","type":"incomplete","vlan":777}]}

Test 3:

curl -H 'Content-type: application/json' -X PUT http://127.0.0.1:8181/api/amlight/sdntrace_cp/trace -d '{"trace": {"switch": {"dpid": "00:00:00:00:00:00:00:03", "in_port": 1}, "eth": {"dl_type": 33024, "dl_vlan": 777}}}'

Response:

{"result":[{"dpid":"00:00:00:00:00:00:00:03","port":1,"time":"2023-02-17 10:01:24.355650","type":"starting","vlan":777},{"dpid":"00:00:00:00:00:00:00:02","port":3,"time":"2023-02-17 10:01:24.355710","type":"trace","vlan":4001},{"dpid":"00:00:00:00:00:00:00:01","port":2,"time":"2023-02-17 10:01:24.355738","type":"trace","vlan":3824},{"dpid":"00:00:00:00:00:00:00:02","out":null,"port":1,"time":"2023-02-17 10:01:24.355762","type":"incomplete","vlan":777}]}

[gretelliz]

@viniarck, Possible scenarios in this update

• Empty list: bad request (temporal - waiting for a better validation)

• One item: -- incomplete: failed cases (no match - including when switch is not in stored_flows and no action in the flow) -- last: expected

• Several items: -- incomplete: failed cases -- last: expected -- loop: when a loop is found the type of the last item is set to loop. Then, the type of the last item into the path will not be trace anymore.

Note that an empty list is now not returned in failed cases, but the incomplete type in the last item of the path will be returned.

[gretelliz]

1 - I was also wondering if on mef_eline consistency check we'd need to adapt any of the checks there, but since it's completely relying on the "out" key value that will only be a dict when "type": "last" then it seems safe. Is that right?

That is, compare_uni_out_trace in mef_eline.utils returns False for the new type 'incomplete', since the field out of this trace is None.

Here an example:

[
   {
      'dpid': '00:00:00:00:00:00:00:01', 
      'out': None, 
      'port': 1, 
      'time': '2023-03-08 11:26:14.992519', 
      'type': 'incomplete', 
      'vlan': 100
  }
]

2 - Final question, since this is consolidating "type", can we have a more specific/descriptive name for "type": "trace"? From what I followed, "trace" now is only for intermediary steps, maybe we can it "transit" or "intermediary" something that facilitates understanding what it actually means?

Good point @viniarck, I think this update will make the response more intuitive.

• Change last to intermediary.
• Update main.py, openapi.yml CHANGELOG.rst and unit tests.
• Checked that unit tests pass

Let's keep on our radar to bump v1 in the API routes when validations are completed.

Fine.

[viniarck]

1 - I was also wondering if on mef_eline consistency check we'd need to adapt any of the checks there, but since it's completely relying on the "out" key value that will only be a dict when "type": "last" then it seems safe. Is that right?

That is, compare_uni_out_trace in mef_eline.utils returns False for the new type 'incomplete', since the field out of this trace is None.

Here an example:

[
   {
      'dpid': '00:00:00:00:00:00:00:01', 
      'out': None, 
      'port': 1, 
      'time': '2023-03-08 11:26:14.992519', 
      'type': 'incomplete', 
      'vlan': 100
  }
]

2 - Final question, since this is consolidating "type", can we have a more specific/descriptive name for "type": "trace"? From what I followed, "trace" now is only for intermediary steps, maybe we can it "transit" or "intermediary" something that facilitates understanding what it actually means?

Good point @viniarck, I think this update will make the response more intuitive.

• Change last to intermediary.
• Update main.py, openapi.yml CHANGELOG.rst and unit tests.
• Checked that unit tests pass

Let's keep on our radar to bump v1 in the API routes when validations are completed.

Fine.

Cool. Thanks for the info/confirmation. Using "intermediary" ended up great.

[gretelliz]

@viniarck, what concerns me now is the case loop. Note that out is a dictionary. What is the expected behavior in mef_eline in this case?

[[{'dpid': '00:00:00:00:00:00:00:01', 'port': 2, 'time': '2023-03-08 17:00:09.174384', 'type': 'starting', 'vlan': 100}, {'dpid': '00:00:00:00:00:00:00:02', 'out': {'port': 2, 'vlan': 100}, 'port': 2, 'time': '2023-03-08 17:00:09.174431', 'type': 'loop', 'vlan': 100}]]

[viniarck]

@viniarck, what concerns me now is the case loop. Note that out is a dictionary. What is the expected behavior in mef_eline in this case?

[[{'dpid': '00:00:00:00:00:00:00:01', 'port': 2, 'time': '2023-03-08 17:00:09.174384', 'type': 'starting', 'vlan': 100}, {'dpid': '00:00:00:00:00:00:00:02', 'out': {'port': 2, 'vlan': 100}, 'port': 2, 'time': '2023-03-08 17:00:09.174431', 'type': 'loop', 'vlan': 100}]]

Good point @gretelliz. The expected behavior is to return False for this type of trace. Looking into mef_eline, I'd expect it to either hit this conditional here https://github.com/kytos-ng/mef_eline/blob/master/models/evc.py#L1163 or this one https://github.com/kytos-ng/mef_eline/blob/master/models/evc.py#L1169 since it'll compare the uni vlan tag and the outgoing port.

This sounds like a good unit test to add to mef_eline if you could map it please with a low_priority tag. Also, on mef_eline check_trace since we have a stronger guarantee from sdntrace_cp now, we could even add a new early return there https://github.com/kytos-ng/mef_eline/blob/master/models/evc.py#L1159-L1160 checking if either trace_a or trace_z last step type != "last", if it is, then log as a warning (since that's really unexpected and maybe a network operator overwrote flows or something else expected is going on). What do you think?

[gretelliz]

@viniarck, very good, I agree with your suggestion, I think it will solve the problem and make the algorithm more robust against possible updates, for example, new types.