We are all well aware about the problem space of finding the Shortest Path and use of Dijsktra algorithm. In this blog, we will take a peek at the problem space for Disjoint Path routing, see how it can be reduced to the optimization problem and a few algorithms in that space.
So first, let’s take a brief look at what is Linear Programming (LP) and an example of LP formulation for the Shortest path first problem. A basic background in Algebra would be helpful. Also, I am going to take some luxuries while explaining to keep things simple, so it’s possible that some statements may not be mathematically accurate.
What is an Optimization Problem? An optimization problem is a problem that aims to find the best solution from all feasible solutions. The best solution can be the minimum or maximum solution. An example of minimum solution can be finding a route from point A to point B that takes the shortest time. An example of maximum solution can be how a production factory can maximize its profit using limited materials. Both problems are example of optimization problems.
What is Linear Programming? The technique to solve optimization problems by expressing and solving problems as mathematical models is called Linear Programming (or Linear Optimization). Every optimization problem consists of three elements:
- Decision variables: describe our choices that are under our control;
- Objective function: describes a criterion that we wish to minimize (e.g., cost) or maximize (e.g., profit);
- Constraints: describe the limitations that restrict our choices for the decision variables.
In order to formulate an LP problem
- Define the Decision Variables
- Choose an Objective function
- Identify the constraints
Let’s look at a simple transportation example to grasp few concepts and then we will try to formulate an LP problem for the shortest path. Imagine that below figure represents a one-way road from Node 1 to Node 4. Traffic Enters at Node 1 (Source Node) and exits at Node 4 (Sink Node). The cost of using each road (represented by edges) is shown in the diagram as well.
So just with this information, we can make a few observations which should be intuitive:
With this understanding, let’s try to formulate the shortest path problem as an LP problem for the same graph which we saw earlier. In the example we will assume that the amount of traffic volume is 1 (which was the number of vehicles entering at the source) entering at the source Node 1.
And constraints mentioned below in eq.1, 2 and 3 is something we have already seen when we looked at the Transportation problem with one minor change that for the eq.1 it had the value 3 and now it’s 1 as the traffic volume entering at the source node is 1.
We could have added the below eq. 4 as a constraint as well, but we did not, as this can be derived from the above equation eq. 1, 2 and 3 (by adding eq.2 and 3 and doing substitution from eq.1) which means the below equation does not bring anything new to the table.
There you go, we have just formulated our first LP problem. Now if you wish, you wish to to solve it via linear programming kit like GLPK or Pyomo. We will be using GLPK.
As you can see the answer is 11 which is the minimum cost from Source to Destination. You can derive the shortest path based on the variables whose value is set to 1 which gives us 1→2→3→4 as the shortest path. If we want, we can further generalize the problem equations
So hopefully you got some idea about Linear programming. Now let’s take a look at some disjoint path problems, there LP formulations and some algorithms.
The basic problem of finding disjoint paths in a graph boils down to finding a set of disjoint routes whose total cost is minimized. This is also known as MIN-Sum problem.
But first, let’s take a step back and ask why do we care about Disjoint path routing. Typically, when we design our networks, many times our logical paths are shared by same physical paths. For instance, in the below graph, assume that the fiber for both paths 1→3 and 2→3 is sharing the same paths. Now if we want to find two best shortest from Node 1 to Node 3 as an Active and Backup path, we will have path’s 1→3 and 1→2→3 but off-course that is not ideal as in the event of a fiber cut we will lose both paths.
Hence finding disjoint paths help in increasing the survivability of the network.
A set of disjoint routes can be categorized into Node Disjoint paths and Edge Disjoint paths. Edge Disjoint paths are sub – sets of Node Disjoint paths. Let’s look at a simple way of finding a Disjoint path first on the below graph which is also known as the Trap topology (you will see why).
Assume that we want to find K = 2 disjoint shortest paths from Node 1 to Node 6 in this graph. We first run our simple SPF algorithm and found Shortest path to be 1→2→3→6. Then we prune the shortest path edges from the graph to find the next shortest path on the remaining graph. But as you can see below, pruning leaves no path from Node 1 to Node 6.
If we would have not chosen the first path as the shortest path, we could have got, 1→4→3→6 and 1→2→5→6 as our two disjoint paths.
Now let’s formulate the LP problem for finding K shortest paths
Now you can model this problem in LP solver if you wish and see what answer you get for our graph topology above. You should get 1→4→3→6 and 1→2→5→6 as the two disjoint paths.
Disjoint Shortest Pair Algorithm
We could also use Disjoint shortest pair algorithms to solve the disjointness. Below are the high level steps for the algorithm:
1: Find the first shortest path in a given network.
2: Reverse the directions of links on the first shortest path and make those link costs negative.
3: Find the second shortest path in the modified network.
4: A duplicated link that is used in both first and second shortest paths with different directions is deleted.
5: The remaining links on the first and second shortest paths form two disjoint paths.
One problem with this algorithm is that if you notice, the edges have negative costs, which means Dijkstra can’t be used and instead Bellman ford’s algorithm is used which has higher computational complexity.
Suurballe’s algorithm can also solve MIN-SUM problem to find two disjoint paths without including any negative link cost which means Dijkstra’s algorithm can be used for shortest path computation.
Disjoint paths with shared risk link group
SRLG is defined as a group of links that are affected simultaneously when a network failure occurs. In the network in below figure, S(i, j, g) indicates the SRLG information and for SRLG number g = 1, if S(i, j, 1) = 1 then it means that link (i, j) belong to SRLG group g=1. For instance, in the figure, SRLG (5,7,1) and SRLG (3,7,1) means that edges (5,7) and (3,7) belong to a same SRLG group =1
A potential reason for both links (5,7) and (3,7) part of same SRLG is because the optical fiber may be sharing the same path. If a fiber is cut happens, both links (3,7) and (5,7) will be disconnected.
A link can be part of multiple SRLG groups and an SRLG can have multiple links.
If we just try to find two MIN-SUM paths in the topology, we will get 1→2→3→7 and 1→4→5→7 but as you know they share the same SRLG and we can do better than this.
If you model this ILP and solve it, you will see that we will find two disjoint paths of 1 → 2 → 6 → 7 and 1 → 4 → 5 → 7, as shown in the below figure. The MIN-SUM in this case will be the total cost of both paths which is 9.
As the size of the network becomes large, it becomes harder to solve and do the ILP computation for the MIN-SUM problem. That’s where heuristic based algorithm comes into play to find disjoint paths with SRLG constraints. One example of such an algorithm is weighted-SRLG algorithm (WSRLG). I am going to skip the details and interested readers can find more details at the below link
So we started with Basics of Linear Programming, looked at the LP formulation of SPF problem, then we looked at the LP formulation of Disjoint routing and a few algorithms like Disjoint Shortest Pair and Suurballe’s Algorithm. Then we ended by looking at the LP formulation of Disjoint Routing with SRLG. I hope this was somewhat informative to you.