Routing in sparse splitting optical networks with multicast traffic

In this paper, we investigate the problem of Multicast Routing in Sparse Splitting Networks (MR-SSN). Given a network topology with the multicast capable nodes distributed uniformly throughout the network, and a multicast session, the MR-SSN problem is to find a route from the source node of the multicast session to all destinations of the multicast session such that the total number of fibers used in establishing the session is minimized. In this paper, we develop a rerouting algorithm for a given Steiner tree, which makes it feasible to route a multicast session using a tree-based solution in sparse light splitting optical networks. In addition, we present a heuristic based on Tabu Search (TS) that requires only one transmitter for the source node and one wavelength for each multicast session. To evaluate the performance of heuristics, we formulate the MR-SSP problem as an integer linear program (ILP), and optimally solve small instances using the commercially available linear solver, CPLEX. We test our heuristic on a wide range of network topologies. Our experimental results show that: (1) The difference between our solution and ILP optimal solution, in terms of the number of fibers used for establishing a multicast session, is within 10% in almost all the instances and within 5% in about half of the instances. (2) The average delay, taken over all destination nodes, falls within three times the optimal value. (3) A sparse light splitting all-optical network with 30% of multicast capable cross-connects has an acceptable low cost and relatively good performance. (4) The improvement achieved by TS heuristic increases considerably when the session size is large, the number of Splitter-and-Delivery cross-connects is small, and the network connectivity is dense.