Cost-effective heuristics for planning GMPLS transport networks

With the explosive traffic growth of WDM-based transport networks, the development of GMPLS (or multi-granularity)-based transport networks becomes essential to cope with the network scalability problems. Much work has been devoted to the development of Multi-Granular Crossconnect (MG-XC) architectures and planning (or dimensioning) methods. Extending these efforts here, we are defining a novel problem of planning GMPLS-based transport networks by (1) considering the whole traffic hierarchy defined in GMPLS; (2) allowing bifurcation of multi-granularity traffic demands among different physical routes. We will call such a problem the Routing and Multi-Granular Paths Assignment (RMGPA). The objective of the problem is to minimize the total weighted node port count. Due to the computational complexity of the problem, only very-small-sized problems can be solved exactly through Mixed Integer Linear Programming (MILP) optimization. In this paper, we propose novel heuristics that are capable of solving large-sized problems in a reasonable amount of time.