Minimum-Multiplicity Routing Problems of Multimedia Communications

In this work, we investigate the routing problems of minimizing the number of distinct transmission mediums or carrier domains for multimedia communications. We consider the problems of two-party connection as well as three-or-more-party connections. By minimizing the number of distinct transmission mediums or carrier domains on the connections, rather than minimizing bandwidth, length or hop counts, the network carriers may achieve higher cost savings on connection provisioning and management. These problems are proven to be NP-hard. Heuristic algorithms are proposed for larger instances of the problems and evaluated through simulations.