Mesh Restoration Planning with St*Mesh

Mesh restoration is a technique for restoring failed services by using shared spare resources in a system-wide efficient manner.  In circuit assignment for optical networks, for example, recovery from failures is one of the requirements in finding the best circuit path for each demand while sharing the resources required for recovery.  Smart solutions usually cost much less than simple ones.  St*Mesh is a constraint-programming optimization tool that solves a general class of restoration planning problems.

A case study is shown here to compare the bandwidth requirements for a number of currently-deployed mesh restoration techniques with the ones generated by St*Mesh.  Unless the mesh network is designed with the right algorithms and capacity checks, network restoration can fail when there isn't enough bandwidth on the selected backup path.  

The amount of spare bandwidth required for backup can vary significantly.  For example, for an all-to-all uniform traffic distribution in a 13 node, 23 link network, the ratio of spare (restoration) bandwidth to the (shortest path) working bandwidth is given for various restoration types in the following chart.

For this (Net 3) sample network, there are three different types of path restoration:  Optimal Path (backup paths are chosen to minimize total spare capacity), MPLS Path (shortest backup path disjoint from working path), and Ded Path (no sharing of bandwidth on backup paths).   In these three cases, the new path is chosen at the endpoints of the demand (or LSP in MPLS networks) and is completely disjoint from the working path.   There are also three types of link restoration (Optimal Link, MPLS FRR, and Ded Link) that are defined similarly, except that the endpoints of the failed link are used as switching points.

The algorithm in St*Mesh is designed for the more general case where the logical topology of links between switches is different than the underlying physical topology.  See the discussion section below for more information on the general case.  

The chart below shows that St*Mesh produces very efficient mesh restoration designs even when the logical and physical topologies are the same.  Using the same network as shown above, here's a comparison of St*Mesh with a simulated annealing (SA) and a fast heuristic algorithm (SSR), compared to the Optimal Path method shown above:

In this one example, the St*Mesh algorithm performs quite well.   Actually, all of them are much better than the MPLS design shown above.  St*Mesh also supports capacity modularities (links with capacity larger than individual demand bandwidth) and express links (which connect two non-adjacent nodes along an existing physical path).   Designs with modular capacity tend to achieve efficiency between the (non-modular) St*Mesh and (non-modular) SSR.

Indeed, it was the vital role of express links in reducing the cost of networks that motivated the design of St*Mesh.   In many restoration algorithms, demands are assigned restoration paths sequentially, but the order of assignment is not given a priori.  For each demand, when it is time to assign its restoration path, the least cost feasible path is chosen.  This choice may take into account previously-assigned spare capacity.  If it is a greedy algorithm, which are the simplest to implement, capacity deployed to support previous assignments is considered free for the current demand, and no consideration of future demand assignments is made.  

Some assignment orders may lead to efficient designs, whereas other orders may not.  I call this the demand-order bias.  A common technique is to try many different orders and pick the best design.   But if you think about the number of ways of ordering demands, any arbitrary ordering is likely to be sub-optimal.  

Express links make it even harder for greedy algorithms to perform well.  Since an express link covered the same path as a sequence of conventional links, it is usually cheaper than the sequence of links in traversing the path.  Greedy algorithms will gravitate to these express links.  But the efficiency of any mesh restoration algorithm depends on the sharing of spare capacity across independent failures, and greedy algorithms do not take bandwidth sharing into account.  St*Mesh does.

What's particularly exciting about St*Mesh is that its constraint-based decision methodology can be applied to more general systems, particularly when an existing system of services and resources needs to be transitioned to a more efficient design.