Single- and multi-path logical topology design and traffic grooming algorithm in IP over WDM networks

In this paper we investigate single- and multi-path logical topology design and traffic grooming algorithms. Since the problem of the optimal logical topology design for all traffic demands is NP-complete, we design a logical topology by sequentially constructing the shortest path for one source-destination pair at a time. In the single path case, the demand for each source-destination pair must be routed on a single path. In the multi-path case, if it is not feasible to route a demand on a single path, the traffic demand is divided into multiple subdemands and a path is provided for each subdemand. Each path is a locally optimized path in the sense that there are no other paths with less hop count that may be constructed from existing links and newly created links. We propose heuristic algorithms for logical topology design and traffic grooming in both the single path and multi-path cases. The performance of these algorithms in terms of weighted hop count and throughput is evaluated using the GLASS/SSF simulator. The results indicate that a proposed single path algorithm outperforms other known algorithms in terms of weighted hop count and throughput. Also, we observed that multi-path algorithms improve network throughput and a multi-path algorithm with widest-shortest paths reduces the weighted hop count compared to single path algorithms.