The traffic generated by multimedia applications has different requirements than those of traditional data traffic. New routing algorithms, capable of efficiently meeting these requirements, are needed. We show that the optimum multicast stream routing problem can be formulated as a linear integer programming problem, and propose an efficient solution technique for this problem. This solution technique is based on enhanced value-fixing rules to prune the search space for the integer solution, and a two-step decomposition, to speed-up the linear relaxation of the problem. We show that the proposed solution technique significantly decreases the time to compute the solution, when compared to traditional methods.
The optimum multicast stream routing problem is NP-complete; therefore, the optimum algorithm still has a worst-case exponential run time. Hence, its main use is as a benchmark for heuristic solutions. By using the optimum routing algorithm, we characterize the performance of the existing heuristic algorithms under realistic network and traffic scenarios. Based on these evaluation results, we derive guidelines for upgrading the network capacity.
Next, we consider the problem of routing unicast streams in a Wavelength-Division Multiplexing (WDM) network. The WDM network has an additional degree of freedom over traditional networks - its topology can be changed by the routing algorithm to create the routes as needed. We show that the optimum reconfiguration and routing problem can be formulated as a linear integer programming problem. Since this is a complex solution, we also propose an heuristic algorithm. The heuristic algorithm is based on an extension to Dijkstra's Shortest Path algorithm to reconfigurable networks, called the Shortest Path with Reconfiguration Algorithm. We show that the results from the heuristic are close to the optimum by means of an analytical upper bound.
We also propose and evaluate minimum-cost and minimum-delay algorithms for multicast routing in WDM networks, which can make use physical multicasting capability of the optical network.