vlan_range epic implementation

[Alopalao]

I have read the issue Blueprint (discuss on issue) mef_eline VLAN range EVPL, and partially implemented it. Creation, deletion, posting flows and tags allocation are working. I am missing things like error cases, consistency check and sdn_trace compatibility (I wonder if it will be a problem). So, I have some questions with some changes that I want to describe here:

1. Changes on mef_eline:

• Detecting a duplicated EVC with share_uni:
  Although I already asked about this in a meeting, I want to be more descriptive here and I also had another idea. With the addition of vlan_pool, UNI tag allocation is already implemented and ensures that two UNIs do not share the same TAG in the same Interface. _is_duplicated_evc left unique feature is the message that we have another UNI with the same TAG instead of showing the error that the TAG is already used. The cost of _is_duplicated_evc was negligible but now with the addition of vlan_range we have a list (specifically list[list[int]]) or more to check for each EVC addition which is already done by tag allocation.
  Proposed change:
  So far the only NApps that allocate a tag are mef_eline and of_lldp. Therefore, if for each EVC creation, we check against of_lldp tag, we can rule out whether it is used by another EVC or not when a tag is not available; instead of checking against every other EVC created (not archived).
  Needed:
  mef_eline will need to know of_lldp tag.

• Input for ranges:
  It was already decided to have a string representing the TAG values, comment. It is desired to avoid/detect human errors for example "100-105, 102-110". The input variable type should be changed in order to analyze errors. I think we should be asking for integers instead of strings.
  Proposed change:
  The input must be a list[list[int]] similar to what was implemented in vlan_pool. This includes _get_tag_ranges to ensure an input that works with vlan_pool.

2. Changes on kytos:

• Make a tag available, current code:
  available_vlan already works with ranges so the changes were not substantial when implementing vlan_ranges, working change. When trying to use tags, the algorithm can be briefly summarized as "take all tags or none" meaning that all the tags in a range should be present in available_tags otherwise none of them are going to be used.
  But when making a tag available "take all tags or none" does not apply correctly. make_tags_available is triggered when mef_eline deletes a circuit freeing a TAG or more. If a TAG was already available, a warning ("This TAG X was already available") was sent but the circuit deletion was not stopped. With the current implementation and vlan_range we cannot get away with lazy deletion.
  Do we want to apply "take all tags or none" to make_tags_available with vlan_ranges as well? To do so we should restrict the deletion of an EVC with an already available tag and I think this is not desirable.
  Proposed change:
  Change make_tags_available implementation to analyze only list[list[int]] adding everything even though it was available. The return values would be a list containing previously available values, using range_intersection.
  Needed:
  All tags received would need to be changed to list[list[int]].

• Used tags, current code:
  This is the new implementation of Interface.use_tags needs to ensure that each range in, for example, [[100, 200], [300, 400]] is available in the Interface. A deepcopy seems necessary in case an error is found because each analyzed range modifies available_vlan. This increases complexity and does not give any specific information on which tag was not available.
  Proposed change:
  Change the algorithm. First, see if any tag is not available (return any not available tag using range_intersection(desired_tags, available_tags)) . Second, use range_difference to get the new available_tags.
  Needed:
  All tags received would need to be changed to list[list[int]].

Final thoughts:

• We have "set" operations for lists of ranges in Interface. So far we have range_difference and range_intersection which could be used more if these changes are accepted. Also, we would be adding range_addition to lazily make a tag available. Are there any plans that involve ranges? Maybe these operations should be in kytos/helpers.py so these operations could be available to be used in other NApps.

cc'ing @italovalcy and @viniarck

[viniarck]

1. Changes on mef_eline:

Proposed change: So far the only NApps that allocate a tag are mef_eline and of_lldp. Therefore, if for each EVC creation, we check against of_lldp tag, we can rule out whether it is used by another EVC or not when a tag is not available; instead of checking against every other EVC created (not archived).

Yes. Let's remove shares_uni and refactor with existing methods that check if the new tags are available or not (there's also opportunity to go ahead and try to allocate/use directly and not just check first, which might simplify code since we know that the core will also validate, so please double check if we can go for it - and then revert the other UNI newly allocations if the other fail as you've done recently). I believe _is_duplicated_evc can also be replaced with _use_uni_tags. If mef_eline tries to use of_lldp's tag it won't be available since of_lldp is allocating the tag too as you've mentioned, and then don't allow the EVC to be created/updated and returning a HTTP 400|409.

The input must be a list[list[int]] similar to what was implemented in vlan_pool. This includes _get_tag_ranges to ensure an input that works with vlan_pool.

Yes. Let's use the current tag range anywhere where a range of tags is required, making also all of tag ranges inputs (and future ones) homogeneous. Its form that you specified is also relatively user high-level and friendly too since it ended up with [inclusive_a, inclusive_z] values, in addition to being well suited for the existing data lookups.

[Alopalao]

Yes _use_uni_tags already detects used tags. Removing shares_uni will not be a problem in functionality.

Also, I will implement [list[list[int]] from now on.

[viniarck]

Right.

[viniarck]

Do we want to apply "take all tags or none" to make_tags_available with vlan_ranges as well? To do so we should restrict the deletion of an EVC with an already available tag and I think this is not desirable.

On Kytos-ng core we do. But, let's break things down here. We can make make_tags_available idempotently if you think it makes it more ergonomic, I agree with you that if it's trying to make an available tag available again, it should be OK as long as it simplifies and we document it accordingly on docstrings. The only exceptional case should when it's trying to make a tag available outside of tag_ranges.

Now, regarding error handling and making sure it's clear what's the conflicting ranges, I think it'd be fantastic to have this too, and it's opportunity to also review and potentially change the returned bool values of make_tags_available and use_tags to return nothing if it succeeds and raise a custom exception if it can't make it available or can't use it (which is pretty much the pattern you've also used in some higher level functions on mef_eline, which is also aligned with certain "Pythonic" error patterns too). Historically, we used the boolean since for a single tag it was trivial to also know the conflict. Tuple results could also work, although, I believe the exception would make things clearer for this case. The custom exception should also have an attr with the conflicting result the difference that didn't succeed (whatever couldn't get used or whatever couldn't get made available) including the interface id just it can also get reused for the Link methods, also let's make the exception to implement __repr__ just so when reraising as HTTPException on endpoints it's easy to convert and set the detail. Wdyt?

You're right it shouldn't impact on mef_eline deletion, and it should proceed, but still it should be logged as an error if it tries to incorrectly make a tag available that's not on tag_ranges, it'd be a logic bug on mef_eline, let's say the range was passed incorrectly to a func or something else, (assuming we'll also make make_tags_available idempotent).

[Alopalao]

For a lazy addition, meaning [40, 65] + [[1, 41], [50, 60], [70, 100]] = [[1, 65], [70, 100]], the bisect returned index (0) it is a just a starting index. add_tags will contain a for loop to check how many ranges are covered in available_tags by the single soon to be added range of tags and return what was ignored ([[41,41],[50,60]]) so they are logged. With this added complexity, bisect does not look like the right method here. I will try to test both cases (with and without bisect) and post the results later.

The new exception is a good idea and it will be better to just return the conflicts.

[viniarck]

return what was ignored ([[41,41],[50,60]]) so they are logged.

add_tags returning list[list[int]] makes sense and can facilitate, but let's also keep in mind the current bool return value is also used to check whether or not to notify interface tags to update the DB collection. So, if it were to return what was ignored then we'd also need to compare if whatever is being added back if it's different that what was ignored (although comparing two lists in most cases would be a cheap operation) and then only notify if needed to avoid unnecessary DB writes too. With that said, maybe a flipped logic returning only what was actually made available, then if would be a matter of just checking if the list is non empty. Food for thought, let's see what facilitates more.

loop to check how many ranges are covered in available_tags by the single soon to be added range of tags and return what was ignored ([[41,41],[50,60]]) so they are logged. With this added complexity, bisect does not look like the right method here. I will try to test both cases (with and without bisect) and post the results later.

Yes, somewhere it'll need a loop. Either way the bisect is desirable there when dealing with a single range, right, let's measure and see what we can do best. Look forward to it. You can also consider a new method looping over the existing methods that only deal with a single tag or range.

The new exception is a good idea and it will be better to just return the conflicts.

Right. Let's go for it then.

[Alopalao]

I was not able to modify add_tags to be more lenient when adding so I went ahead and created range_addition.
Cases:

• Worst case
  Taking into account that the maximum number of values in list of ranges is 2047 (without unnecessary partition)
  available = [[n, n] for n in range(2, 4095, 4)]
  tags = [[n, n] for n in range(1, 4095, 2)]
  Time -> 0.008903264999389648 seconds

• Normal-ish worst case
  available = [[3, 10], [20, 50], [60, 70], [80, 90], [100, 110], [112, 120], [130, 140], [150, 160]]
  tags = [[1, 1], [3,3], [9, 22], [24, 55], [57, 62], [81, 101], [123, 128]]
  Time -> 8.726119995117188e-05 seconds

• Normal-ish best case
  available= [[3, 10], [20, 30], [40, 50]]
  tags = [[5, 18]]
  Time -> 1.6450881958007812e-05 seconds

These cases include the verification that tags is not inside tag_rangesby running for i in range_intersection(tags, available) inside the timing stamps.

I think I am gonna just add range_addition only when detecting list of list and leaving the old process for singular range.

[viniarck]

8.7 millisececonds on avg per interface in the worst case isn't that great, but the normal-ish best/worst with 87 microseconds and 16 microseconds are great. It's not a deal breaker though. Good thing that the vlan range more expensive-ish operations will only be for UNIs for the short/medium-term so it won't compound linearly per link per EVC, and for now also EVCs aren't being bulk created (but let's make sure that provisioning 100 ish or so EVCs concurrently with vlan range will still won't impact much on latency response times, please map a sub related task for this). Even for the worst case though, I think we don't even need to restrict it on higher level APIs such as mef_eline EVCs creation/updates. Let's keep this in mind though, and good to have the data points here for future discussions.

Did you only measure once or indeed was the avg? It'd be great to also have a median, max, min.

I think I am gonna just add range_addition only when detecting list of list and leaving the old process for singular range.

Sounds good.

[Alopalao]

These were average from 20 runs each, but haven't tested them with deletions made at the same time. Gonna try them later.

[viniarck]

This is the new implementation of Interface.use_tags needs to ensure that each range in, for example, [[100, 200], [300, 400]] is available in the Interface. A deepcopy seems necessary in case an error is found because each analyzed range modifies available_vlan Change the algorithm. First, see if any tag is not available (return any not available tag using range_intersection(desired_tags, available_tags)) . Second, use range_difference to get the new available_tags.

Yes, since interface.available_tags is being mutated, even with an exclusive lock you'll need deepcopy. Aldo, let's try to leverage this as a transaction, all or nothing, and as soon as you've hit the first conflict that's not available before raising a custom exception then you rollback to the copied available_tags ref. This is also assuming we'd go with a custom exception. I believe an all or nothing here would make things more predictable, easier to reason and maintain. Wdyt?

[Alopalao]

The addition of deepcopy is working well. When it comes to error logging, I gave more thought to the current method. I think it is possible to log the first encountered conflict. It should be enough information for the user to change an input.

[viniarck]

Not necessarily, if the conflict isn't bubbled up in a response (or/via exception) then in the UI users who don't have access to the console won't have enough information, for instance via mef_eline UI when trying to create a new EVC with a vlan range. A conflicting tag usage is equivalent to a validation error, validation error shouldn't not be on log.error. The logging ERROR level usage currently on core and NApps are indeed for actual application errors that it doesn't know how to subsequently handle it such as failed retries, failed loads, failing to deal with a data structure and so on. Whatever shows up on log.error requires special attention/analysis from network operators and they'll keep monitoring it, and depending on the error it might be an actual issue.

[viniarck]

Are there any plans that involve ranges? Maybe these operations should be in kytos/helpers.py so these operations could be available to be used in other NApps.

Good idea and observation. For sure, I'd recommend a new module though such as kytos/core/tag_ranges.py (or something similar). kytos/core/helpers.py could be used too, it's for general utilities, but tag ranges already have its own operations and well defined reponsibilities so it deserves its own module, wdyt? Also, feel free to move the other staticmethods tag ranges related from interface.py too such as find_index_add and find_index_remove, maybe we can keep them as free functions for now on this new module. It's OK to move them too since we're not breaking compatibility since your latest changes haven't been released yet.

[Alopalao]

A'right, going to move them.

[italovalcy]

@Alopalao regarding "Detecting a duplicated EVC with share_uni", I'm okay with leveraging the UNI tag allocation approach. My only concern here is for EPL (i.e., you dont have a TAG). Will that case also be covered?

Regarding "Input for ranges", can you please provide some examples of list[list[int]] ?

Regarding "Make a tag available", not sure if I understood, but what would be a case for deleting an EVC that frees more VLANs than it was allocated before? In that case, the database is inconsistent no? Please clarify the scenario here.

Other than that, I would refer to the issue discussion that replaced the Blueprint. Congratulations for the work here!

[Alopalao]

My only concern here is for EPL (i.e., you dont have a TAG). Will that case also be covered?

For EPLs, there is no tag duplication so there is not necessity to compare tags from those circuits.

can you please provide some examples of list[list[int]] ?

List of ranges, for example representing [{1,2,3,4}, {20}, {40, 41}] is the same as [[1,4], [20, 20], [40,41]]

Please clarify the scenario here.

For example, we have a UNI_A that allocated [[1, 4]] and there are [[3,3], [5,4095]] available tags in the moment of this UNI' circuit deletion.

Right now, the implementation only allows for entire ranges to be not available when deleting UNIs. Since 3 is already available, an error message will notify the user that [1,4] is available and that it needs to be "used" so UNI_A can be deleted. The user could use the tag manually through kytos console.
In this case, I think we should allow the deletion of UNI_A and add its range to available tags which would result in [[1,4095]]. Additionally to this, kytos should notify the user that 3 was already available. I am referring to this as a lazy addition of tags since it does not care if a tag is already available, it will still add the range to available tags.

It is a very unlikely bug. We do not expect it to happen and it has never happened to me yet but we have pipelined processes and things can go wrong with hardware.

[viniarck]

This issue discussion will be closed for major requirements. Nicely done, Aldo. Also, appreciated Italo's collaboration.

Anything else will be discussed in PRs since no major points are expected.