A novel heuristic algorithm for highly utilizable shared protection in optical WDM mesh networks

Network survivability is one of the most pivotal issues in optical WDM networks. In particular, if a conduit is cut, approximately 16 terabits per millisecond can be lost in recent technology. A huge loss even by a single conduit failure fatally damages the performance and operation of the whole network. In this paper, we propose a new heuristic algorithm, called the Generalized Minimum-Cost (GMC) selection algorithm, to choose a pair of working and backup path which firstly minimizes total number of required wavelengths of working and backup path and secondly distributes lightpath request traffic into whole network links, if there are several pairs to require the same number of minimum wavelengths, in order to achieve load-balancing effect. GMC selection algorithm contains several formulas to get Working and Backup path Reservation Cost (WBRC) which can be obtained through heuristic GMC function. By using WBRC, our GMC selection algorithm achieves superior performance compared to the current Combined Min-Cost (CMC) selection algorithm and random selection algorithm in terms of the amount of wavelength consumption and blocked lightpath requests, especially on the relatively less-connected New Jersey LATA and 28-node US networks. Furthermore, we suggest a maximum number of non-blocked lightpath requests against single link failure in simulated networks for network operators to consider acceptable maximum traffic on their networks, so that they can provide 100% restoration capability in a single link failure without lightpath request blocking. We also analyze the complexity of the GMC selection algorithm and verify that the complexity of the GMC selection algorithm is lower than that of the CMC selection algorithm if the number of lightpath requests is sufficiently large.