A highly efficient path-restoration protocol for management of optical network transport integrity

Abstract—Distributed path restoration based on optical cross-connects can provide highly capacity-efficient real-time restoration for WDM-based optical networking. However, to obtain an assured restoration level with the theoretically very low amounts of spare capacity that path restoration allows, one must solve, or closely approximate a solution to, the integer multicommodity maximum flow (MCMF) problem. MCMF is, however, a hard combinatorial optimization problem due to what is called the “mutual capacity” aspects of the problem: which of many competing origin–destina-tion pairs should be allowed paths over the finite spares on each span? Integer MCMF is further complicated by the nonunimod-ular nature of the problem, i.e., fractional flows are forbidden but would arise if solved by Linear Programming. This paper presents a heuristic principle that tests well against Integer Programming solutions of MCMF routing. The heuristic is first characterized in a centralized program, then adapted for use in a distributed path restoration protocol. In all test cases, the protocol obtains over 97% of the paths found in an optimal MCMF solution in the same net-work. Via OPNET simulation it is also predicted that the protocol will run in well under 2 seconds which means it could be used di-rectly in real-time, or in distributed prefailure self-planning, for restoration. The significance is that network operators could ag-gressively optimize their spare capacity, toward theoretical mini-mums, while still assuring 100 % restorability. Index Terms—Dynamic provisioning, mesh restoration, network integrity, network management, optimization methods, survivable networks. I