Shared risk resource group (commonly referred to as shared risk group or SRG) is a concept in optical mesh network routing that different networks may suffer from a common failure if they share a common risk or a common SRG. SRG is not limited to optical mesh networks: SRGs are also used in MPLS, IP networks, and synchronous optical networks. An SRG failure makes multiple circuits go down because of the failure of a common resource those networks share. There are three main shared risk groups:
Shared risk link group (SRLG) Shared risk node group (SRNG) Shared risk equipment group (SREG). Failure recovery is a crucial in all types of networks. The MPLS as well as the IP network uses the high speed capabilities of modern optical networks. SRLGs typically deal with links between fiber optic nodes, but that is not always the case. SRLG can also be modeled if the links contain transmission lines instead of fiber optic cable. SRG modeling is also used when a provider generates a service-level agreement with a client with various protection schemes.
Types of SRRGs
SRLG
Fiber spans are fiber optic cables that connect two nodes. In practice, these cables are bundled on one concrete conduit or power/telephone pole (aerial), which creates a shared risk link group. For example, if there is a cut on a fiber span, it takes down all circuits (upper layer logical links) that use that particular SRLG. The term SRLG may have first appeared in 2000. Early work (from 1990s) that considered SRLG (before the term was coined) in understanding implications due to SRLG, and designing for survivability and restoration by considering SRLG can be found in
.
SRNG
In optical mesh networks, nodes are junctions of fiber spans. Some nodes might contain highly sophisticated routing equipment— while others may be just a patch panel. Whatever the case, a node is a shared risk node group—because if the node fails, the failure affects all signals through that particular node.
SREG Shared risk group also extends within a node itself—in particular nodes that contain multi-port network cards. Dense wavelength division multiplexing equipment are also considered SREG because failure of a DWDM multiplexer affects all of the channels through that DWDM. The same is true for multi-port network cards. When routing over SNRG is not possible, circuit-pack diversity with-in the same node can lessen the risk of failure.
Diverse Routing in SRG failure Failure recovery is an essential part of any optical based network. When provisioning a circuit, engineers typically use a shortest path algorithm, such as Dijkstra. Calculations for a protection path must take into account that the protection path must provide 100% SRG protection. In other words, the protection path cannot go through the same SRLG or SRNG. If SRG diversity is not achieved then the failure of that SRG fails both primary path and back-up paths simultaneously. Therefore, the two calculated paths must be SRG diverse. There has been recent studies that have proved that the SRG diverse routing is in fact NP-complete. There is currently no known discrete method to solve this real world problem for large-scale network. People have been able to solve this problem by finding a heuristic solution.
NP Completeness
The SRG diverse routing problem has proven to be NP-complete. To prove something is NP-complete, it is sufficient to prove that the problem closely resembles another well-known NP-complete problem. To prove the case, engineers introduce a graph, as shown in the picture. The graph depicts that, between two nodes, there exist multiple paths, which may include other nodes. The parallel paths in sub-graphs (circled in blue) belong to the same SRLG. Finding an SRG diverse path is the same as finding two disjoint subsets, such that each subset contains at least one common element. This is equivalent to the set-splitting problem, which has been proven NP-complete. Therefore, the SRG diverse routing problem is also NP-complete. (SRLG is solvable using Suurballe's algorithm)
Graph Transformation Approach
There has been many attempts to overcome the fact that there is no solution for the SRG diverse routing problem. One of these attempts is by means of a graph transformation approach. This method takes the original network graph and applies some transformations to the graph to obtain a transformed graph that overcomes the SRG diverse problem to some degree. However, this method has its own shortcomings. After obtaining the transformed graph one would simply compute the primary path using a known shortest path algorithm such as Dijkstra's. On computing the primary path, and removing all nodes and links in that path, run the algorithm again on the remaining network. There may be instances when, due to topological restrictions, unavoidable traps could be introduced that prevent the algorithm from finding a solution. There are also avoidable traps, which come from parameter restrictions such as cost. These can be overcome by reconsidering the parameter values or altering the algorithm to make it more robust. This method is limited, the following conditions must be met to calculate two SRG diverse paths:
The number of links to an SRLG must be lower than the degree of the node the SRLG is incident on An SRLG cannot be a subset of another SRLG An edge (two nodes connected by a link) can share two SRLGs at most This approach works only in very narrow circumstances. When looking at actual large scale implemented networks this approach is useless because the links in the network greatly exceed these restrictions. A typical link can contain as many as 50,000 SRLG. One of the reasons this approach falls short is in the case of two independent edges where links fall in the same SRLG, even though the algorithm might find a path that would be incorrect because there would be no physical route.
… excerpt ends here. Continue reading the full article.
