College of Computer and Information Engineering Inner Mongolia Agricultural University, Hohhot, Inner Mongolia, 010018, P.R. China

---

Abstract—The design of survivable WDM mesh networks based on p-cycles has been extensively studied. However, most of studies only deal with a single link failure rather than node failure. In this paper, we develop a new scalable and efficient design method for computing node-protecting p-cycles in order to ensure network survivability. The performance of our new proposed design method makes an obvious improvement 20% in capacity redundancy over that of the previous one. The conventional design methods formulate the problem of p-cycle design as an Integer Linear Program (ILP). To solve the ILP, the prerequisite is to a priori enumerated all possible p-cycle candidates. For a large network, the resulting ILP may be intractable as the huge number of cycles may exist. We propose a new design and solution method based on large scale optimization tools, namely Column Generation (CG), where p-cycle candidates are generated on-line when needed. The main advantage of our CG-based method is that no p-cycles are a-priori off-line enumerated; the generation of the promising set of p-cycles is embedded in the optimization process. Extensive experiments have been conducted for comparison. Experimental results show that our new proposed method outperforms the previous method in terms of capacity efficiency.

Index Terms—p-cycles, node protection, column generation

[PDF]

Cite: Hong Hui Li, Xue Liang Fu, "A Novel Efficient Design of Survivable WDM Mesh Networks," Journal of Computers vol. 9, no. 7, pp. 1684-1689, 2014.