Feature request: automatic creation of required LSPs based on provided traffic demands

[VictorTelcoBrain]

I have been exploring PyNTM lately and I love it, it provides great insights into network routing and on top of that it has helped me to improve my Python skills since I am a Java backend engineer by trade.
I see that autoconfiguration of the LSPs reserved bandwidth is supported (currently the LSP definitions need to be provided by the user), so I wonder if the automatic creation of LSPs based on traffic demands (and the network topology, of course, and maybe also some user-defined constraints) is in the PyNTM roadmap (sometimes this feature is called automesh).

As an example, a user would submit the following query to PyNTM:

• given a network topology and a set of demands, please calculate the required LSPs so that the standard deviation of the network link utilizations is as small as possible.

[tim-fiola]

Hi Victor. I'm glad it's providing value!

Generally RSVP auto-mesh could be supported, but I'm more interested in the example you give that involves standard deviation:

• What set of network links would be considered for utilization?
• As for standard deviation, pyNTM assumes many flows and perfect hashing, so that if a demand transits multiple paths, the demand will be spread equally between the paths. Given that, would standard deviation be relevant?

I apologize if I'm missing something obvious. Generally auto-mesh could be implemented. It's the qualification part that I am not sure about.

Thanks!
Tim

[VictorTelcoBrain]

Hi Tim,

sorry, I was not very clear before, let me try to explain what I mean with an example, let's say we have the following simple network topology:

As you can see in the diagram above, the network has 7 hosts and 7 links, all the links have cost = 1 and four links have capacity = 80 and the other three links have capacity = 60.
For the sake of simplicity, there is only one traffic demand with source_node = A and destination_node = G, its magnitude is 56 traffic units.
The task is to add/find/calulate the required LSPs so that the traffic is spread through the available paths (two paths in this case) in a way so that the link utilization values are as homogeneous as possible (that's what I meant when I mentioned the lowest standard deviation before).

The first attempt might be to create just one LSP with the same source and destination node as the demand, which will be routed through the cheapest/shortest path (cost = 3), this is it:

But this solution does not meet our requirements because three links have more than 90% utilization and the other four links are not utilized at all.

The second attempt might be to create two LSPs, as you said, pyNTM does not create LSPs (yet) but it is able to route them (i.e., to assign a path to an LSP if such a path exists) and the traffic will be split equally among the LSPs.
As seen in the diagram below, half of the traffic would flow through LSP_1 and the other half through LSP_2:

This second solution is better then the first one but it is not ideal as per our requirement, three links have utilization = 46.66% and the other four links have utilization = 35%.

The ideal solution (the third one) is depicted below:

In this solution, by unevenly splitting the traffic between the two LSPs, we managed to have the same utilization value (40%) for all of the links in the network.

So this is basically the feature that I am interested in: after providing the network topology and the traffic demands, ideally pyNTM will output the list of required LSPs with their related data (e.g., their paths, reserved bandwidths and expected traffic).
With that information, the network operator will still have to configure their network accordingly in the real world (probably by setting the LSP paths explicitly and also to achieve the desired uneven traffic load balancing between the parallel LSPs) but even if it is just for information purposes, I think it is worth it.

[tim-fiola]

Hi Victor. Thanks, I think I understand what you are looking for now, but I do have some follow up questions and points:

• in the context of RSVP, we can't put uneven traffic loads on otherwise parallel LSPs, meaning that if there are 2 LSPs, traffic will split 50/50, or 3 LSPs, traffic will split 33.3/33.3/33/3. It's possible to flood each physical path with different amounts of LSPs to get the amount of traffic we want on each interface in a topology like you describe above, but . . .
• this example above is for a simple network topology with a single traffic demand, 2 very simple physical paths, and every link is being utilized be the single demand. What about larger, more complex topologies with more demands?
• A more complex topology and more demands introduces a lot of questions:
  • Do you want even link utilization caused by each demand? Or even link utilization in general, regardless of which demand(s) may or my not transit a given interface
  • Ultimately, I am trying to understand what the algorithm would be to:
    1. recognize all *possible paths through the network (not just shortest paths) for each LSP ('all paths' gets very expensive computationally)
    2. decide/analyze which of the paths to utilize for a given demand, which may be affected by paths that other demands are taking and the utilization those demands create
    3. spawn the right amount of LSPs over the right paths to balance out the traffic for each demand
    4. do this for each demand in the model, trying to keep all interface utilizations somewhat even

All that becomes very non-trivial to understand and then code and would likely require a lot of compute resources for even moderately complex topologies with a medium amount of demands. Can you explain to me what is the real-world use case for this? That may help with my understanding.

Thanks!
Tim

[VictorTelcoBrain]

Hi Tim,

your follow-up questions are very relevant, let me try to answer them:

Do you want even link utilization caused by each demand? Or even link utilization in general, regardless of which demand(s) may or my not transit a given interface

I am referring to link utilization taking into account all the demands which are supposed to flow through each link.

The algorithm that you have described matches what I have in mind.
And I agree that it is non-trivial and it would require significant amount of computing resources.
On the other hand, existing software libraries may be used for the required computations, the same way that pyNTM uses networkx for graph analysis.
Regarding the amount of computing resources required, it could be reduced by leveraging parallel processing.

Regarding the real-world use case, I believe it could be useful in order to perform more advanced what-if analysis.
Currently, a user can perform what-if scenarios with pyNTM (e.g., what if this or that link/interface goes down?, what if I increase the current traffic demands by 10%?) and in response to that, pyNTM may re-route some existing LSPs.
But what I would like is pyNTM to tell the user something such as:

"if all the traffic demands increase by 10%, then for optimal performance (i.e., to meet a user-defined goal such as homogeneous link utilization), existing LSP_x should be removed and LSP_y and LSP_z should be created".

Looking further ahead, the next step could be to assign a different priority to each/some traffic demands so that pyNTM will create and assign shorter LSPs to the demands with higher priority (note that this is different from having different traffic Class of Services flowing within the same LSP).

And in the future, a user may also mark a traffic demand as "requires high availability" and in that case, two LSPs would be created for that demand by pyNTM, a main LSP and a backup LSP which would only become "active" when the main LSP goes down.

All of this is different from the regular automesh functionality which usually means to simply create one LSP for each pair of network nodes.

These new functionalities would help not only to analyze an existing network but also when designing and dimensioning a new network.
As you pointed out, the mathematical calculations required are not trivial, Integer Linear Programming needs to be applied but it is a well-known field and related mathematical software libraries exist.
This a slide from a presentation titled Dimensioning of IP Backbone. Planning of IP-based Networks (2007)

And also some proprietary (and quite expensive) network analysis/design software solutions which provide these capabilities have existed for long time, you may check Case Studies & Network Planning Tools presentation, also from 2007.

[tim-fiola]

Hi Victor. After looking into this a bit, it's outside of the scope of what I could do: the algorithm alone seems fairly complex, let alone optimal coding to ensure good performance. I'd be happy to review a pull request, however.

[VictorTelcoBrain]

Hi Tim, I understand, it is a big and complex change indeed.
I do not think I would be able to work on a PR for it since Python is not my main programming language, so feel free to close this issue.

On a different note, I have written a simple Python script in order to export the data calculated by pyNTM (e.g., interfaces traffic, LSP paths) into JSON format.
Not sure if you would find it useful, but if you are interested, I could polish them and create a PR for you to review it.

[tim-fiola]

Hi Victor. I'd be happy to take a look at something like that json formatting addition!