Reintegration: Vlan_config

[Alopalao]

Vlan_pool settings

Currently the option from kytos.conf, vlan_pool causes some bugs if it is used. Having this option being used initializes an interface even though connection is None. This causes:

• A warning, for example, Couldn't get port 1 speed, sw 00:...:01, feats None.
• An error with pydantic validation because mac and speed are None, document.

Additionally, the event "kytos/mef_eline.link_available_tags" is not used thus vlan_pool configuration is not saved in the database collection interface_details. This collection is used when loading an existent topology.

Alternatives to have vlan_pool option functional:
1. Fixed old approach:
Move the settings of interfaces tags to initialization of an interface, code. We can get the configuration of vlan_pool from controller.options.vlan_pool. I have not noticed that using the collection interface_details would be beneficial to this case since it would be loaded at every start of Kytos. But it is a way to unify where the information for available VLANs is if we add vlan_pool settings to the database.

2. Add an API request: (Decision)
   We could have a request to set/add a configuration to vlan_pool while Kytos is running. With this approach, we would need to utilize the database collection interface_details. We could minimize queries in the database by keeping track of which interface IDs have a field in the database with a variable in the Controller or, also, creating a list of iterables.

NNI and UNI VLAN differentiation (EDITED 7-31-2023)

There is another problem when using NNIs as UNIs and this is because the vlan_pool for both are treated as the same. Both values should have different restriction of availability and should not overlap between them. Example, if NNI has a range tag of [100 - 199]. A UNI should be able to take tag 2 and 110. Then, the range for NNI changes to [100 - 109] U [111 - 199].

A solution for this could be having two lists of available tags for each interface available_tags_nni and available_tags_uni (Probably changed to used_tags).

• available_tags_nni should be used by path from mef_eline.
• available_tags_uni should be use to validate the creation of a EVC. Also, we will need to delete the used tag from the list.

Database

Two collections similar to interface_details are needed. These will be read when loading a switch. This means that interface_details will be deprecated in favor of having interface_nni_vlans and interface_uni_vlans.

ccing @viniarck, @italovalcy, @jab1982

[italovalcy]

Hi all,

Excellent to see this discussion here! Originally, the vlan pool was first mentioned on Blueprint 12, when people started designing MEF E-Line and VLAN services on Kytos. To quote that PR very quickly:

Interface tags pool mechanism

For each Interface object:
Each Interface object will have its own VLAN pool with pop() and push()
methods. This pool will be used for EPLs. Administrator might predefine via
configuration the VLAN pool to be used (for instance, VLAN 100 to 200).

For each Link object:
Each Link object will have its own VLAN pool to be used by two
directly-connected NNIs. pop() and push() methods should be available.
Administrator might predefine via configuration the VLAN pool to be used
(for instance, VLAN 100 to 200).

and also:

Provisioning Requirements

In this section we describe the target behaviour. All code here is in
pseudo-code.

1. User submits an EVC request via E-Line NApp's REST

#. For EVPL: E-Line NApp verifies if UNI_A's requested C-VID and UNI_Z's requested C-VID are
available from the interfaces' pools.

#. E-Line NApp requests a primary and a backup path to the Pathfinder NApp
using the attributes primary_links and backup_links submitted via REST

#. For each link composing paths in #3:

#. E-Line NApp requests a S-VID available from the link VLAN pool.
#. Using the S-VID obtained, generate abstract flow entries to be sent to
FlowManager

#. Push abstract flow entries to FlowManager and FlowManager pushes OpenFlow
entries to datapaths

#. E-Line NApp generates an event to notify all Kytos NApps of a new EVC
creation

#. Notify user of the status of its request

So, having available_tags_nni and avaliable_tags_uni sounds good and aligns with the above concept. However, thinking on this for the long term, why not move the available_tags_nni to b ea Link attribute (e.g., Link.available_tags) and leave the interface available tags in the same way it currently is (Interface.available_tags). That way would simplify a lot the process of getting the next available VLAN, because instead of running a loop to find a VLAN ID that matches both sides, we could just get the next available tag.

Additionally, I would like to discuss with you the possibility of NOT having available_tags but instead having used_tags and then having another parameter to configure what is the allowed range (allowed_tags). With this change, we could improve a few things on Kytos:

• It would be easy to see what is the configured range on a link/interface. We could have API endpoints for changing that parameter. Changes on that parameter can be allowed only if certain requirements are met (ex: reprovision EVCs that are using VLANs outside of the range or refuse to change a range if there is any service using that range)
• Performance increases by just storing what we are using. This will help us in an incremental increase of used VLANs. Currently, by default, we have to store a list with 4095 items, while we are using just a few of them. If we store only the used VLANs, that list will begin small and grow together with Kytos usage.

Another requirement to keep in mind is: Link tags and Interface tags should not overlap. Even though they can be used in different contexts, at the end of the day, they are all VLAN tags, and we should not conflict.

OF-LLDP also utilizes a VLAN-tagged package to do its job, and we are not taking that into consideration when setting UP MEF-Eline EVCs. Since we are touching this subject here, I would like to suggest we also take actions to avoid conflict on the used tags for an interface or link and the tag being used by of_lldp (the action to be done here could be just making of_lldp compliance with the process of checking the available tag, or even remove the of_lldp special VLAN ID from the list available tags).

[Alopalao]

Is restricting NNI TAGs going to affect of_lldp current set value (3799)? I see two possibilities here:

• of_lldp have a set value but is configurable so this value should be sent in an event notifying of its usage.
• If we restrict an NNI for example with [10, 100]. Then of_lldp should have a value within that range.

With the latter, if we implement an API request then of_lldp should be changing TAGs. If we keep kytos.conf, then of_lldp should take an available value from what was set and we should remove FLOW_VLAN_VID from settings.
In short, is of_lldp going to modify the restriction or be modified by it?

EDIT: After another reply, I think is safe to assume that we want a modifiable range through an API request. Also, this new range should allow used TAGs. So after of_lldp tag is set, it should be allowed in all ranges.

[viniarck]

Regarding kytos.conf, all of those configurations are just for the runtime, anything that changes overtime due to runtime usage isn't a good parameter to keep it there. Agreed with delegating topology to manage the persistency as it's been doing with interface_details and then you specify and propose an API for it, keep updating/writing it to the DB as we've been doing when "kytos/mef_eline.link_available_tags" is received is fine, this can result in hundreds of writes per second, but it won't be that frequent. In the worst case, it tends to be spiky when provisioning multiple services at once which in fact has been working reliably with the current load we have.

There is another problem when using NNIs as UNIs and this is because the vlan_pool for both are treated as the same

I don't think it's an issue, it's behaving as intended, VLAN 1 in this case shouldn't be available again, I don't think UNIs should have a different pool than NNIs, a pool is for the entire interface. Something that we still need to likely cover in the future is to start using available_tags from a UNI when supporting vlan range too, since both are related I'll recommend that you also review what we've discussed regarding vlan range (although its priority is lower, but it's on our radar).

we could just get the next available tag.

I second Italo's suggestion to also try to simplify and move available_tags to links to not rely on the underlying UNIs but on the link itself, in practice, as far as I know, it's never desirable to have mismatched VLANs in the same link for both practical and maintainability reasons. I also agree that to configure a range we probably should follow a similar format that we've discussed on vlan range issue, maybe something like {"allowed_tags": {"range": "1-100,200-300,400", "type": 1}, and then only Interface(s) who have uni=True and Link(s) should keep track of the configuration value, and the available_tags or the current used range (if we were to go down this path).

Now, regarding flipping the logic of available_tags to only track what's being used, used_tags, it can also be beneficial for when trying to compute intersections (which we need when checking for overlaps on UNIs when creating a new circuit), we could also refactor the list a SortedSet. But, still, it wouldn't be trivial to get the next available tag since to check if it's being used you'd need to parse or derive the configured range again and iterate on it or keep it sorted in memory (so still going back to have a list of the rest of the values, or having to keep track of last and max values, but then also tags can get released again). I'll keep thinking about it, but I'm still not convinced to move away from available_tags (only using it on UNIs and Link already can reduce most of the pain points), let me know if you're seeing other benefits.

The problem we're dealing here is two-fold a) just the configuration of the explicit range and b) keeping track of usage/available values, the second part b), I think it's not problematic currently, also the price to refactor isn't too small (and considering DB scripts too). Also, when changing the configuration of the range, for sure it should only be allowed to reduce the range if the entire new range is available.

I would like to suggest we also take actions to avoid conflict on the used tags for an interface or link and the tag being used by of_lldp

Indeed, of_lldp should be allocating this tag too, we need an issue/enhancement for this

[Alopalao]

Now, let's simulate reducing the reserved_tags to [1, 10] from [1, 21], it would be a matter of bisecting if the difference between the current reserved_tags with the potential new one

If we are using separate restrictions there is this corner case:

If we want to apply the restriction to [2000, 3050], we only have used = available - restriction which results in [3001, 4001]. [2000, 3050] will not be accepted since it is lower in range than [3001, 4001] when it is possible to be applied.

How would you get the next available tag?

At the moment I am thinking we substract restriction - used to obtain availability range.

would it always be [inclusive, non_inclusive) like a Python range

Yes, if we are going with ranges, we would need to represent a number as range to make operations with them and simplify maintenance.

[viniarck]

At the moment I am thinking we substract restriction - used to obtain availability range.

It doesn't seem ideal. I'm not seeing much benefits to refactor available_tags as used_tags.

However, this last comment just made me realize that actually it's probably not a good idea to lift the current available_tags at the Link level, and still to only rely on the Interface level. At the link level it would require a loop on both ends of the interface, but then since mef_eline currently supports creating an EVC on NNIs (as UNIs), the vlan pools of a link and interface needs indeed to be as they currently are, otherwise it could have a mismatch if a link weren't to be aware of NNIs (interface) pool. So, we probably shouldn't support link pool configuration, but only at the interface level, and still, a pool should only exist at an interface level regardless if it's an UNI or not.

Great discussion going on here, can you try to provide this feature only with reserved_tags, and available_tags, but with range optimizations, and assess if it covers for what we need? These two also can address points that Italo raised. What I mean by reserved_tags would be indeed the initial range would be [1, 4096] for compatibility reason, but then reserved_tags would be the actual configuration for a new range in the runtime. Let me know if you encounter a major blocker, or anything else that might require used_tags instead.

Also, for the user exposed configuration, we still need to decide if range will be given as a string like it was discussed on vlan range: {"range": "1-100,200-300,400", "type": 1}, or if we can simplify here the API and go ahead and ask users to configure based on a range that we're trying to officialize, the range list optimization it's not that obvious for folks who aren't developer - since it looks like a standard list of integers, at first sight, folks can get confused, (unless we were to keep list of lists, which is the current pattern that initially exposed on kytos.conf although it's not functional)

[Alopalao]

What if we leave available_tags as it is (or as ranges) and used_tags and reserved_tags are added as ranges? The only difference would be what we have in memory and database:

• available_tags only in memory
• used_tags on DB and memory
• reserved_tags on DB and memory

Although taking one element from available_tags would mean resizing used_tags as well (O(log n)).

About VLAN range for users, the API is going to accept list[list] or list[tuple]. For the front-end, we would need to compute the whole range of reserved_tags from list[int] to list[list].

[viniarck]

What if we leave available_tags as it is (or as ranges) and used_tags and reserved_tags are added as ranges?

@Alopalao, first, just a comment regarding available_tags, I've used sys.getsizeof to measure how many bytes available_tags is using:

kytos $> getsizeof(controller.switches['00:00:00:00:00:00:00:01'].interfaces[1].available_tags)                                                                                          
    ...:                                                                                                                                                                                 
Out[2]: 33048

So currently, it's using 33 kbytes on average. In prod, a switch will typically have 32 interfaces, so, that results in roughtly 1 MB per switch just for available_tags. At AmLight in prod, currently there's less than 10 switches, so even though 10 MB is wasteful it's not a major problem. But certainly, in a topology with 300+ switches this start to look not great, although still it wouldn't be that catastrophic considering a modern server and the size of a typical production network that rarely will have 100+ OpenFlow switches. Also, mongodb is typically consuming 130 MB for all collections using a 3 node ring topology. Also, in prod at AmLight currently, mongo master instance is using on average 200 MB, although kytosd container is consuming roughtly 800 MB which is more than we expect, this part needs further analysis, but I wouldn't expect that available_tags would be the only offensor, since it'd be contributing to less than 10 MB based in total on the calculations since AmLight currently has less than 10 switches.

[viniarck]

Second, to reduce the amount of memory we'd have to: a) Allocate less and / or b) Use ranges representation (which in turn also allocate less). With that said, I'd recommend that we extend this feature to support configuration and solve problem incrementally while minimizing risks:

1 - Still keep available_tags without ranges since we're already paying the price and it hasn't resulted in major problems based on the expected production scalability.
2 - Provide a sort of a reserved_tags (or range_tags or whatever equivalent better name) string configuration that wouldn't require to constantly keep the entire in range in memory for its lifetime, but only trying to reconfigure it, just so we don't keep wasting more memory with tags. Probably a similar pattern that was discussed on vlan range.
3 - When trying to reduce the configured range it will always compare with available_tags if all vlans are still available.
4 - Let's enhance available_tags: list[int] to still be a list[int] but keep it sorted, just so at least search for a tag or range improves a bit, but still, let's keep writing the entire available_tags in the DB for now since it's not a major problem.
5 - All Interfaces and Link methods should also provide thread safety when trying to allocate or remove multiple tags.
6 - There's also opportunity to move kytos/.*.link_available_tags event to core, instead of having each client having to publish this event (which of_lldp would also have to), whenever an interface successfully allocate or remove one or multiple tags.

Let me know if you can come up with a solution with these constraints and officialize a proposal. I liked the ideas, and I do appreciate all of the efforts to try to also enhance or even replace available_tags, but let's go incrementally, until we actually have to solve this difficult problem, let's stick with the safest route that will also keep this easy to be maintained in prod. Also, as you know, currently mef_eline is already dealing with a potential race condition with tags, and currently to debug a potential leak isn't that hard since we're exactly storing the entire available_tags, but now imagine debugging this on top of ensuring that all resizing and ranges were to be correct too and ensuring no potential leaks (just to save a few mega bytes of memory, it doesn't sound like a good trade-off at this time, all things considered). Let's keep it safe and keep evolving it incrementally when we have to.

[Alopalao]

Seems that we going with API request because we would need a modifiable vlan_pool. Currently, I know what would be the restriction for the content of this new request:

• It should be ordered.
• Not unnecessary partitions. For example for a range [[10, 100], [100, 200]] it is unnecessarily divided when it could easily be [[10, 200]]. Although we can accept it and fix it in the code (so far undivided ranges make their comparisons easier).
• Singular integer values (eg. [[1,10], 20]) are accepted. But they are going to be changed in the back end ([1,10],[20,21]) for comparison purposes.

I am still thinking about what would be better to have either available_tags or used_tags. (Probably used_tags)

[Alopalao]

DEPRECATED
Whether we go with available_tags or used_tags (comment), we can minimize the lists of lists ([[10, 30],[50, 100]]) to just a list of integers ([10, 30, 50, 100]). As @viniarck mentioned, the entire list of integers could be reduced to a list of ranges with the following operations using library bisect:

used_tags = [1, 20]
def add_range(range: tuple):
    """Add range to used_tags"""
    start = bisect.bisect_left(used_tags, range[0])
    end = bisect.bisect_right(used_tags, range[1])
    print(start, " ", end)

    "If index is outside of a range, it is added to range"
    left = [range[0]] * (start % 2 == 0)
    right = [range[1]] * (end % 2 == 0)
		
    used_tags[start:end] = left + right

def remove_range(range: tuple):
    """Remove range to used_tags"""
    start = bisect.bisect_left(used_tags, range[0])
    end = bisect.bisect_right(used_tags, range[1])
    print(start, " ", end)
    
    "If index is inside of a range, it is added to range"
    left = [range[0]] * (start % 2 == 1)
    right = [range[1]] * (end % 2 == 1)
		
    used_tags[start:end] = left + right

def check_restriction(restriction: list[tuple]):
    """Check if restriction does not interfere with any used tags
    Returns True when restriction is aplicable, False otherwise"""

    n = len(used_tags)//2 # Number of ranges
    bool_list = [False] * n

    for range in restriction:
        start = bisect.bisect_left(used_tags, range[0])
        end = bisect.bisect_right(used_tags, range[1])
        if start % 2 == 0 and end % 2 == 0:
            bool_list[start//2:end//2] = [True] * ((end - start)//2)
        
    return all(bool_list)

# Testing
print(used_tags)
add_range((9, 40))
print(used_tags)
remove_range((21, 23))
print(used_tags)
used_tags = [1,4,8,11]
restriction = [(1,5), (7, 16)]
print(check_restriction(restriction))

These operation have the characteristic of only accept ranges but a number (2) can be represented as a range ([2,3]). Time complexities:

• add_range(range) and remove_range(range) is log n. N is the length of used_tags.
• check_restriction(restriction) is n/2 + m(log n). M is the length of restriction: list[tuple].

Note: These operations are suited for list[int] variables which are deprecated.

[Alopalao]

More decisions made:

• Change available_tags to list[int] list[list], the continuous pair of ranges are going to be representing ranges. It is going to be always sorted.
  • Both UNI and NNI available_tags values will be at the interface level because both should not overlap.
  • A value taken to be used by UNI should also be taken from available_tags from NNI.
  • On memory and DB for each NNI/UNI.
    - Range operations
• Add reserved_tags replacing vlan_pool which represents an additional range restriction smaller than [1, 4096].
  • This value is going to be modified by an API request from Topology: GET (get current restriction), POST (modify restriction).
  • Move set_switch_options() in the controller to the topology. It used to set vlan_pool values to each interface.
  • On DB and each interface will know its reserved_tags (memory)
  • API request rules, comment
    - Drawback when setting reserved_tags, current TAG usage would be calculated from the operation reserved_tags - available_tags. It can be inaccurate sometimes but it will never leave behind a used TAG. Explained.
• Ranges are going to be in the format [inclusive, non_inclusive), like in Python. It is possible to represent a single interger 100 with a range [100, 101]
• Move kytos/mef_eline.link_available_tags to core and call such events from there.

[viniarck]

@Alopalao, thanks for summarizing here and all of the suggestions and improvements:

• Reducing memory usage with range is great, it's a major refactor, after more thought, I suggested that you go about it in a next opportunity, BUT, if you're sure you can deliver, maintain, cover the new ranges completely with tests, including the DB scripts to update the existing available_tags into ranges, I'd be OK with it, and I'd appreciate that since you're also improving other things.

• Notice that Range Operations, if you were to initially have used_tags = [10, 20, 21, 21, 23, 23, 30, 35], a fragmented range, and were to call add_range((9, 40)), it would result in [9, 40], so it included many unexpected vlans like 22, 24-29. The list[int] optimization and slices insertion seem interesting, but again, this is certainly not trivial to debug and maintain. If you really want to improve the range parts, I'd recommend that you then try to consider to use a 2d array, it's easier to reason about, and then we'd have to deal with resizing and merging when needed. Let me know if you could reassess this part again and if you wish to start maintaining ranges, I'll count on you on that.

Drawback when setting reserved_tags, current TAG usage would be calculated from the operation reserved_tags - available_tags. It can be inaccurate sometimes but it will never leave behind a used TAG. #401 (reply in thread).

It sounds like we're not in the same page regarding this point, if we go with available_tags with ranges (your proposal), or as it is (without ranges), reserved_tags when it needs to change again (be reconfigured), let's say going from [[1, 4096]] to [[1, 1000]], it's a matter of validating if it's being reduced by comparing with the existing reserved_tags, and if it is, then bisect if all intervals, from [[1000, 4096]] are in available_tags if they aren't, they are being used, so it couldn't get changed. I still don't get the inaccuracy that you're mentioning. Let me know if this paragraph makes sense or if we're discussing about different things, or if I misunderstood what you meant.

[Alopalao]

if you were to initially have used_tags = [10, 20, 21, 21, 23, 23, 30, 35], a fragmented range, and were to call add_range((9, 40)), it would result in [9, 40]

The add_range() was meant to be for bulk adittions after checking availability. In this case, if we want to use [9, 40] before we need to check if the indexes from bisecting are in from only one range start - end == 1. This is because of second rule. This case [9, 40] fits inside indexes 0 and 8 meaning there is more than one range and there are gaps with missing numbers. Thus there should be a error message there.

[viniarck]

Got it, Aldo. Thanks for clarifying, indeed add_range and remove_range would work well with used_tags. Also, my cocern with used_tags is iteration of the next available tag as mentioned before. Let me raise this final question, great discussion but lots of back and forth, but with good reason, after all, this is a decision that is core to the platform and has a horizontal impact.

Can you come up with range solution but only using available_tags and reserved_tags, and using a 2D list, that has reasonable performance, and then also include a way to verify if the range is available? If the solution works well we can consider taking the opportunity to also introduce it too.

Note: the 1D list you have demonstrated that for used_tags the add_range and remove_range works well, and I appreciated your effort, but it's not that easy to reason with the indexes and potential off by ones on top of an existing optimized list, so long term, speaking for myself as a current core team member, I'd rather not have to maintain it.

[Alopalao]

More points:

• VLAN pools available_tags and reserved_tags are going to be created by interface and not by NNI/UNI. used_tags will no longer be used, updated some comments regarding this decision.
• Changed ranges from list[int] to list[list] because it turned out complicated for mantainers.
• Interfaces will carry the VLAN ranges and not Links as initially thought.

Update: Create script for saved available_tags on DB

[Alopalao]

Summarized this discussion thoughts into another discussion

[viniarck]

Closing this discussion