Network protection with multiple availability guarantees

This paper develops a novel network protection scheme that provides guarantees on both the fraction of time a flow has full connectivity, as well as a quantifiable minimum grade of service during downtimes. In particular, a flow can be below the full demand for at most a maximum fraction of time; if after a network failure the flow is below its full demand, it must still support at least a fraction q of that demand. This is in contrast to current protection schemes that offer either availability-guarantees with no bandwidth guarantees during the downtime, or full protection schemes that offer 100% availability after a single link failure.We show that the multiple availability guaranteed problem is NP-Hard, and develop an optimal solution in the form of an MILP. If a connection is allowed to drop to 50% of its bandwidth for just 1 out of every 20 failures, then a 24% reduction in spare capacity can be achieved over traditional full protection schemes. Allowing for more frequent drops to partial flow, additional savings can be achieved. Algorithms are developed to provision resources for connections that provide multiple availability guarantees for both the sharing and non-sharing case. For the case of q=0q=0, corresponding to the standard availability constraint, an optimal pseudo-polynomial time algorithm is presented.