Analysis and Algorithms for Partial Protection in Mesh Networks

作者：Kuperman Greg^*; Modiano Eytan; Narula Tam Aradhana

来源：Journal of Optical Communications and Networking, 2014, 6(8): 730-742.

DOI：10.1364/JOCN.6.000730

• Multipath routing
• Networks
• Network survivability
• Network protection and restoration

This paper develops a novel mesh network protection scheme that guarantees a quantifiable minimum grade of service upon a failure within the network using multipath routing. Typically, networks fully guarantee service after a single-link failure, which is often an over-provisioning of resources to maintain essential traffic for the infrequent event of a failure. Our scheme guarantees that a fraction q of each demand remains after any single-link failure, at a fraction of the price of full protection. A linear program is developed to find the minimum-cost capacity allocation to meet both demand and protection requirements. For q <= 1/2, an exact algorithmic solution for the minimum-cost routing and capacity allocation is developed using multiple shortest paths. For q > 1/2, an algorithm is developed based on disjoint path routing that performs, on average, within 1.4% of optimal, and runs four orders of magnitude faster than the minimum-cost solution achieved via the linear program. Moreover, the partial protection strategies developed achieve reductions of up to 83% over traditional full protection schemes.

• 出版日期2014-8-1
• 单位MIT