| The proliferation of multimedia applications has led to the deployment of various telecommunication technologies (e.g. IP, wireless) in addition to the traditional PSTN circuit switched networks. Multimedia gateways perform call routing and scheduling, call signaling, and media format conversions among different networks. In addition to call delay, which is measured by delay cost, calls routed to different media incur varying media cost. Combined cost is delay cost plus media cost. The focus of this research is to investigate off-line and on-line call routing and scheduling algorithms to meet various optimization criteria associated with delay cost, media cost and combined cost on multimedia gateways.; The research for off-line problems involves both analysis of algorithm complexity and NP Completeness proofs, as well as simulation studies. We show that minimizations of delay cost, media cost and combined cost are all NP-Complete. Then, we prove that there is no good approximation algorithm to minimize media cost and, by extension, combined cost. Further, we develop several approximation algorithms to minimize delay cost, media cost and combined cost. Finally, we derive worst-case approximation ratios for these algorithms and compare their performance experimentally. In addition, we develop a network-flow based polynomial time algorithm to minimize media cost when there are only two media. Finally, we show that when each call has the same call length, a First Come First Served Greedy algorithm minimizes delay cost, media cost and combined cost.; The research for on-line problems involves algorithm design, queuing analysis and simulations. We introduce two queuing approaches: centralized queuing and distributed queuing. We develop algorithms to minimize the expected delay cost, expected media cost and expected combined cost for each of these two queuing approaches, derive performance measures of these costs, and compare the performance of these two queuing approaches analytically using the same set of system parameters. We establish the correctness of the analytical performance results by utilizing multivariable differential calculus, linear algebras and simulation results. |
