VLAN pool reintegration conclusion

[Alopalao]

Here are the summary of the conclusion of the previous discussion of VLAN pool: (UPDATED Aug 17, 2023)

1. Move kytos/mef_eline.link_available_tags to kytos/core to be an addition of Interface class, issue.
2. Issue #408, Change TAGs collections from list[int] to list[list[int]] to represent a list of ranges [[100,201], [600, 801]]. To make maintainability consistent and easier, these list of ranges should followed some rules:
   2.1. Not unnecessary partitions. [[10, 101], [101, 201]] will not be allowed and should be avoided, instead [[10, 201]] is the correct form.
   2.2. It should be ordered
   2.3. Ranges will follow [inclusive, inclusive] format.
   2.4. Singular integers should be converted to range format for comparabilities. [[200, 300], 405] should be changed to [[200, 300], [405, 405]]. User input with singular integers are accepted but not stored.
3. Add tag_ranges replacing vlan_pool which is going to be the range of restricted VLANs. One value to restrict both NNI and UNI. tag_ranges is going to be an attribute of Interface class
4. Adapt interface.available_tags to dict[str, list[list[int]]]. This adds compatibility to future applications of multiple VLAN types even though for now we only support type 1. Example {'1': [[10, 20], [40, 40]], '2': [[1, 4097]], '3': [[1, 4097]]}
5. A script is needed to update interface_details documents from list[int] to list[list[int]].
6. UNIs should start allocating TAGs, an issue for mef_eline was already created. An issue for of_lldp is needed as well.
7. Add API requests to modify tag_ranges, issue. POST for additions/replacements, DELETE for deletions and GET to get existent tag_ranges. Body example: {"tag_range": [[100, 201], [400, 2001]]}, "tag_type": 1}. For tag_type we are only accepting 1 and it is not required.
8. Add e2e tests to cover cases related to TAGs, issue

ccing @italovalcy @jab1982

[viniarck]

@Alopalao thanks for consolidating this feature discussion. Overall, +1 from me. New minor details that I just realized though:

1 - Regarding the new API endpoints:

1. Can you rename the endpoint prefix as reserved_tags as tag_ranges? I believe it'd reflect more closely what it actually is.
2. Also when configuring a tag_ranges, notice that the TAG object does have a tag_type, currently, in the core, we're always using TAGType.VLAN without exposing, and we do want to maintain the same behavior. Let's also include a tag_type to accepted in the body, but only accept the literal "VLAN", which should also be the default value. It's also an opportunity to refactor the TAGType. Side note: of_core ActionPushVlan is already differentiating between a service or client tag accordngly, so in the core, it's just a tag, the core doesn't care what's on top of the allocated tag, which is why I also think that only keeping the "VLAN" tag type for now is fine, and then if MPLS is ever used (highly unlikely) then we allow it to be set too. OK?
3. Having the POST and DELETE makes sense, but for certain configurations it'll require more requests, for instance, when an operator is trying to reduce but also adding a new range, how common that case will be? I don't know, but, maybe we can include a PATCH where it would try to set a new entire range, see what I mean?
4. Also, how are you going to list tag_ranges (reserved_tags)? There's no GET endpoint currently, and augmenting the existing as_dict interface could get too cluttered (especially when there are multiple non contiguous ranges), so let's include a new GET for this resource. Maybe GET v4/interfaces/tag_ranges/ for all interfaces and GET v4/interfaces/{interface_id}/tag_ranges for a single interface, what do you think? Let's not forget to bump v4 too since it's a major feature in the API being added.

2 - Also, let's include and plan to cover the feature with a few e2e test cases, OK?

[Alopalao]

maybe we can include a PATCH where it would try to set a new entire range

POST replaces the entire range for set/non-set tag_ranges. Since it is going to verify if the range is applicable, I think it should be fine. I thought about exclusives endpoint for reducing and increasing range but I deemed them currently unnecessary.

Updated the first comment with all the other points:

• Changed reserved_tags to tag_ranges
• Added tag_type to the body of the new POST request
• Added new GET request
• Added issue for e2e tests planning

[viniarck]

Got it. Excellent.

[Alopalao]

About of_lldp sending kytos/core.link_available_tags through the interface. This issue could be related but it looks too broad.
To achieve the notification of a used TAG by of_lldp, we would need to discover the NNIs in the switches. But the flows are being created before the NNIs are discovered. Could change the event triggering the creation of the flows? and is it related to the mentioned issue?

[viniarck]

Great observation, Aldo. This issue is partly related, although we haven't prioritized its epic yet, so in the meantime we'll still have this generalized one flow per switch. In the meantime, a good compromise would be to always try to allocate/use (interface.use_tag(settings.FLOW_VLAN_VID)) on all interfaces, right before a switch flow is pushed, but without carrying about whether or not this tag is still available. Similarly, right before a switch flow is removed to deallocate it. In the future, when we refactor of_lldp to have per interface flows, then we can check whether or not the flows exist before trying to allocate the tag, in that case if the tag isn't available then it shouldn't even push the flows.

Does that make sense to you? It still wouldn't be completely ideal, but at least settings.FLOW_VLAN_VID will still be allocated and released accordingly. Since other NApps always try to check if the VLAN is still available then I think it wouldn't lead to any issues for of_lldp completely assume in the meantime it owns it, as a result other NApps wouldn't be able to use it.

[viniarck]

Also to recap for other future readers of this thread, with #405, NApps wouldn't need to send kytos/core.link_available_tags, and as they call use_tag(tag) and make_tag_available(tag) the core will be responsible for sending the KytosEvent.

[Alopalao]

Got it.

[italovalcy]

Hi Aldo and Vinicius! Excellent to see this summary of the discussion around vlan pool feature. I will take a broad look later, but I just want to comment on something:

2.3. Ranges will follow range() format from Python. In short, [inclusive, non-inclusive)

This point here I would like to request further discussion. Having the list of vlans in the same way we have for python range can lead to for confusion for network operators.. for developers, it is easy and you can just pass through the value to python range function. For network operators, I'm sure it will be a point of doubts. What would be the impact of having this ranges as [inclusive, inclusive] ?

[Alopalao]

For now [inclusive, non-inclusive) operations are O(n) except for next_tag() which is O(1). Only thinking about it, it sounds possible to adapt these operations (except is_available_log) to be [inclusive, inclusive] with some modifications but I am not sure (let me back to you on this).

Another possibility is to only have the format [inclusive, inclusive] format to the front end on the UI and API requests so [inclusive, non-inclusive) will be only for the back end. This will result in O(n) time complexity for the format transformation.

[Alopalao]

After trying with [inclusive, non-inclusive), I think it is possible but because of the nature of having two forms of values (either [40] or [[40]] for singular integers), the methods will be a listing of if statements with all the possible comparisons that we would have. Possible "ranges" for example:

available_tag	desired_tag	result
[20, 40]	23	[20, 22], [24, 40]
[20, 40]	20	[21, 40]
[20, 40]	40	[20, 39]
[20, 40]	[20,25]	[26, 40]
[20, 40]	[25,40]	[20, 24]
[20, 40]	[25, 38]	[20, 24], [39, 40]
[20, 40]	[21, 40]	20
[20, 40]	[21, 39]	20, 40
[20, 40]	[20, 40]	None
[20, 21]	21	20
20	20	None

They can be reduced to 2/3.

[viniarck]

For sure, we can reach out to conversions (back and forth, API -> DB -> API), but ideally, if we can keep the same format, and find a format that's both suitable to both data model and API that's even better, including to potentially debug issues. Although, in practice, even if convertions are needed (in API boundaries) it wouldn't be a major issue, a 4K list element will perform well even in linear time complexity, and we know that VLAN type will still be the default one and be around for a long time.

What if for [inclusive1, inclusive2] for a single value we always required it to be a multiple value [40, 40] for instance meaning 40? and in the validations, we always ensure that inclusive1 <= inclusive2. That would allow us to minimize ifs when merging and bisecting the ranges. If you could assess this one here too, Aldo, that'd be great, I mean, if Italo also agrees that [40, 40] for a single value wouldn't be too confusing too.

[Alopalao]

Having a guarantee of two values in a range helps it a lot and the changes are very few. Yes, that format is great.

[viniarck]

Right. If we stick with this one, let's make sure that for VLAN range we use a same pattern to be consistent everywhere, back then, in the initial proposal, it was a string, if we were to accept a list[list[int]] there, then we can also minimize conversions when displaying the values and reusing it with the other related operations, assuming that before the value is set, it'll be validated upfront.

[Alopalao]

On another note, I was expecting desired_tags to be one range (list[int]) but I see that for vlan_range epic we would be expecting a list of ranges (list[list[int]]). Bisecting for when the desired_tags is one range is totally possible and recommended since we can achieve an O(log m). But for a list of ranges going over the whole list is necessary, this results in O(n (log m)). In this case, simulating a sliding window is way better at O(n + m). We can have both methods and decide which one to use based on the type of desired_tags. Since the number of methods increases, is it a good idea to have available_tags as an object of a class that can manage these range operations?

*m is the length of available_tags
*n is the length of desired_tags

[viniarck]

But for a list of ranges going over the whole list is necessary, this results in O(n (log m)). In this case, simulating a sliding window is way better at O(n + m)

I'd expect O(n (log m)) to be good enough, considering that both lengths are expected to be < 4096, and typically it'll be way less than that considering that usually most ranges won't be too fragmented, let's keep it as minimal as we can, and maintain less code as possible. With linear time complexity that we currently have for single value it only takes a dozens of microseconds, this likely will never be a bottle neck. Once the implementation with O (n (log m)) is getting stable, it's a good idea to run benchmark at least once to confirm the expected results.

[viniarck]

is it a good idea to have available_tags as an object of a class that can manage these range operations?

I'll recommend that you try to consider refactoring the existing related methods (is_tag_available(tag), use_tag(tag), make_tag_available(tag)), both at the interface and link level, and then also introduce is_tag_ranges_available(tag_ranges), use_tag_ranges(tag_ranges), make_tag_ranges_available(tag_ranges), whenever a client is working with ranges.

We'll also need to make a decision regarding TAG abstraction, currently, in the runtime available_tags is a list[TAG], and all tag related methods is dealing with it. If we could get rid of the TAG abstraction, and then whenever a tag operation is needed, then callers pass its tag_type: str and with either a tag: int or tag_ranges: list[list[int]] when working with a range (for example, is_tag_available(tag_type: str, tag: int)). That way, in the runtime interface.available_tags could be dict[str, list[list[int]]], where the key of the dict would be the type of the tag, currently we'll only support "vlan" as we've been doing.

The main benefit of this would be that the shape of the data would be in the format that you're expecting when making a range operation. Consequently, when writing to MongoDB we can just pass the list[list[int]] without any issues or unnecessary extra conversions (facilitating to debug in the future too), and we could reuse all of the list[list[int]] operations everywhere that you're already implementing for the collection. Historically, TAG abstraction and the contents of available_tags weren't designed for efficient lookups, and using a TAG object becoming apparent that it'll get in the way, so it didn't seem that it was the right abstraction to have.

Also, UNI would need to get refactored accordingly when passing a user_tag (split into a tag: int, and tag_type: str). In the future, when vlan range is implemented then UNIRange can get introduced, passing tag_ranges: list[list[int]] and tag_type: str. This would also imply a refactoring on mef_eline shares_uni too.

New requirement to analyze and consider, @Alopalao, it's not a minor one, but certainly one that can impact and is crucial to get it right. If you could assess it too and think thoroughly about it.

[Alopalao]

using a TAG object becoming apparent that it'll get in the way

Yep, I assumed we would ditch the TAG abstraction. Rather, after choosing the tag value an object is created by each with the tag type argument. Otherwise, a conversion would be necessary before each method with ranges. Changing interface.available_tags to dict[str, list[list[int]]] sounds good to me, it does not require any major change and looks compatible with future changes.
*Changing the first comment about interface.available_tags

UNI would need to get refactored accordingly when passing a user_tag (split into a tag: int, and tag_type: str)

Thought about this too. I added some validations to check availability for UNI tag at the initialization of the UNI class. When doing this availability check the integer is passed as [int, int] so it complies with the range operations. Although shares_uni looks like it can work unchanged still, I agree that it needs to be refactored for vlan_ranges.

[viniarck]

I'll go ahead and close this discussion, the implementation is in progress. Excelent proposal, Aldo. Congrats.