Quality of Service Based Initial Route Setup Algorithms for Multimedia Communication
Xing Wang · Chinese Journal of Computers · 2001
QoS(Quality of Service) based network routing mechanisms are fundamental means to support QoS guarantees required by distributed multimedia applications. The QoS based routing algorithms are key components in QoS routing mechanisms. In this paper, two routing algorithms are presented, which are suitable to QoS based initial route setup for multimedia communication. The first algorithm supports the QoS based initial route setup between two participants. It can not only act as the QoS based routing (or the QoS based initial route setup algorithm if on line rerouting permitted) for point to point multimedia communication, but also act as the QoS based initial route setup algorithm for multimedia dynamic group communication in which the number of initial group members is two. It is based on Dijkstra's algorithm and belongs to hop by hop routing algorithm. It finds the minimum usage cost path from source node to destination one with certain constrains satisfied, at the same time, leads to the optimal resource (such as CPU, buffer, bandwidth) utility and guaranteeing end to end delay and end to end error rate requirements to maximum degree. The second proposed algorithm supports the QoS based initial route setup between multiple participants. It can not only act as the QoS based routing (or the QoS based initial route setup algorithm if on line rerouting permitted) for multimedia static group communication, but also act as the QoS based initial route setup algorithm for multimedia dynamic group communication in which the number of initial group members is greater than two. What to be solved is a kind of constrained Steiner tree problem, which is NP complete. By introducing a kind of heuristic cost, it is transformed into a kind of Steiner tree problem. Due to the NP completeness, GA(Genetic Algorithm) is applied to find the minimum heuristic cost Steiner tree. In addition, in order to speedup the convergence to the optimal solution, the domain knowledge based active mutation concept is presented and introduced into the second proposed algorithm. The defined heuristic cost is proportional to the available CPU capability and buffer capacity of the nodes and the available bandwidth of the edges along the route inversely, thus, the second proposed algorithm tends to setup route along the light loaded nodes and edges, helping application QoS requirements satisfied and network load balanced.The correctness of the proposed algorithms is also discussed. Simulation results show that they are effective and efficient.