Knapsack based multicast traffic grooming for optical networks

- This works proposes a light-tree based heuristic algorithm, called 0/1 knapsack based multicast traffic grooming, in order to minimize the network cost by reducing the number of higher layer electronic and optical devices.
- The proposed algorithm constructs light-trees or sub light-trees, which satisfy sub bandwidth demands of all multicast requests.
- A light-tree based integer linear programming (ILP) formulation is presented to minimize the network cost.
- The performance of the proposed algorithm is comparable to the ILP in terms of cost.
- When the introduced ILP is not tractable for large network, the proposed algorithm still able to find the results.
- The proposed heuristic algorithm outperforms the conventional algorithms in terms of resource utilization, such as wavelengths, transceivers, splitters.
- The network cost using the proposed heuristic algorithm significantly decreases when the number of requests increases in the network.
- The network costs of each request using 0/1 KMTG are 24% and 31% lower compared to existing sub-light-tree saturated grooming (SLTSG) and logical-first sequential routing with multi-hop grooming (LFSEQMH), respectively.

This paper proposes a light-tree based heuristic algorithm, called 0/1 knapsack based multicast traffic grooming, in order to minimize the network cost by reducing the number of higher layer electronic and optical devices, such as transmitters, receivers, and splitters, and used wavelengths in the network. The proposed algorithm constructs light-trees or sub light-trees, which satisfy sub bandwidth demands of all multicast requests. We present a light-tree based integer linear programming (ILP) formulation to minimize the network cost. We solve the ILP problem for sample four-node and six-node networks and compare the ILP results with the proposed heuristic algorithm. We observe that the performance of the proposed algorithm is comparable to the ILP in terms of cost. When the introduced ILP is not tractable for large network, the proposed algorithm still able to find the results. Furthermore, we compare the proposed heuristic algorithm to existing heuristic algorithms for different backbone networks. Numerical results indicate that the proposed heuristic algorithm outperforms the conventional algorithms in terms of cost and resource utilization.