Beyond Djikstra: Routing Algorithms in the Real World

Posted on: 10th February 2020

Quickly calculating the shortest path between A and B is well covered by many Djikstra, Bellman-Ford or A* implementations. However, for telecom operators, in areas such as capacity planning, network optimisation or complex service design, these routing algorithms only address part of the real-world requirement. The drive for greater automation means OSS solution developers need access to smarter, more sophisticated routing technology.

Solving the business problem of finding the optimum route through a network almost always involves additional factors, policies and preferences. Not just hop count or utilisation.

For example:

  • Finding a route that is disjoint or diverse from one (or more) other given paths
  • Routing using the most reliable underlying links or equipment
  • Routing avoiding a particular vendor’s kit (e.g. one targeted for swapout)

These additional factors are most often applied as a manual override after a conventional routing algorithm has done its work. So as operators drive for greater network automation, so their OSS requires routing that cover more than just the basics.

For OSS solution developers, the key is a routing engine component that can take account of those additional real-world requirements. Functions to route shortest path using IGP or TE metrics are table stakes. Add the ability to find the shortest path according to any other custom metrics or parameters of a link, and you’ve made it much easier for OSS developers to build a much more valuable application.

So far so good, but we’re still a step away from the real-world way that enterprise customers define their needs: not in terms of configurations but in terms of objectives and constraints. For example:

Objective: “I want the minimum latency route I can get.” (e.g. for datacentre-to-datacentre backup service)

Constraint: “I must have latency not more than 200ms” (e.g. to support an online gaming service provider customer)

A Djikstra, Bellman-Ford or A* algorithm can only go so far in addressing these sorts of requirements. Which means more software to be developed, more expertise needed, and more time before a customer gets a usable application.

But by treating objectives and constraints as integral concepts to the job of a routing engine, we can radically accelerate solution development:

low_latency_demand.route(1).set_limit({“latency”: {“max“: 200})

This code sets a constraint on the latency of a low-latency demand route. The optimal path must have latency of not more than 200ms.

Although a maximum latency of 200ms is acceptable, perhaps we’d actually like the value to be as low as possible.

low_latency_demand.route(1).set_objective({“latency”: “minimise“})

The returned path would have as low a latency as possible.

As mentioned at the outset, in practice service routes are determined by a wide range of factors – hops, utilisation, MTBF, vendor preference, and so on. So, developing a modern-day fulfilment solution would be radically simplified by calling a routing engine that can generate optimal paths based on multiple objectives and constraints.

That’s a task that’s so complex that only AI can answer it.

Fortunately for OSS solution developers, that’s the smarts that we’ve built into the latest release of our SDK. Which means that it’s now quicker and easier to build sophisticated applications for network simulation, capacity planning, fulfilment, service impact analysis, what-if scenario modelling.

Using this approach, wider network and service properties such as OPEX costs, disjoint requirements, path reliability, equipment vendors or geographic restrictions can all be incorporated into optimal route design.

Aria’s SDK already provides constraint-based and objective-based optimal routing against latency, packet loss, costs, hops and distance – or any combination of the five – for user demands across a network layer.

By re-framing the challenge of “optimal routing” in the everyday language used by enterprise customers, we uncover a powerful application for AI techniques. More importantly we enable OSS solution developers to accelerate development cycles for new high-value applications.

Dr Archie Wade, CTO, Aria Networks