Fast Enumeration of Regional Link Failures Caused by Disasters With Limited Size

Fast Enumeration of Regional Link Failures Caused by Disasters With Limited Size

연구 분야: Infrastructure

학회: IEEE/ACM Transactions on Networking, Volume 28, Issue 6

At backbone network planning, an important task is to identify the failures to get prepared for. Technically, a list of link sets, called Shared Risk Link Groups (SRLG), is defined. The observed reliability of network services strongly depends on how carefully this list was selected and whether it contains every high-risk failure event. Regional failures often cause the breakdown of multiple elements of the network, which are physically close to each other. In this article, we show that operators should prepare a network for only a small number of possible regional failure events. In particular, we give an approach to generate the list of SRLGs that hit every possible circular disk shaped disaster of a given radius <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>. We show that this list has <inline-formula> <tex-math notation="LaTeX">$O((n+x)\rho _{r})$ </tex-math></inline-formula> SRLGs, where <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the number of nodes in the network and <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> is the number of link crossings, and <inline-formula> <tex-math notation="LaTeX">$\rho _{r}$ </tex-math></inline-formula> is the maximal number of links that could be hit by a circular disaster of radius <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>. We give a fast polynomial algorithm to enumerate the list of SRLGs and show that its worst-case time complexity is asymptotically optimal under some practical restrictions. Finally, through extensive simulations, we show that this list in practice has a size of <inline-formula> <tex-math notation="LaTeX">$\approx 1.2 n$ </tex-math></inline-formula>.