With the recent developments in transmission and computing technologies, distributed multimedia applications, such a video conferencing and video on demand have now become possible and will be widely used in near future. Such applications transmit information which usually have different traffic characteristics and various QoS performance requirement, similar to real-time communication. If the QoS constraints are not satisfied, the received data is meaningless. But satisfying multiple QoS is a well known NP-complete problem even for unicast. To find an optimal solution for that in dynamic multicast situation would be impractical. So we proposed a heuristic solution based on Bellman-Ford shortest path algorithm.

2.研究概要

　Routing algorithms which are used currently employed in networks are either Dijkstra or Bellman-Ford algorithms. Though both are optimal and run in polynomial time, they could not find the routes that satisfy multiple QoS constraints such as bandwidth, delay, delay jitter and loss probability, which are required for multimedia applications. To avoid the NP-completeness related problem, we first reduced the complexity of the problem by using QoS bound expression for a WFQ service discipline. 　There are two main adjectives of the proposed algorithm: (1) how to use part of the existing multicast (MC) tree while connecting a new participant, so that the traffic over the network is minimized over the whole session period; (2) how to connect a new node to the source so that QoS requirements are met? The basic algorithm is similar to that of the Bellman-Ford (BF) shortest path algorithm.

 

3.システム構成

　We have a specific source node and the existing MC tree. The cost of the links which constitute the MC tree are lower compared to the yet unused links. Among those already in the MC tree, the cost of the links which have a longer life-time is less than those with a shorter life-time. With every link we associate a pair [w, tag], where w is the link-cost and tag is the time stamp. The effective cost (c) of a link is derived from w and the duration of time the link remains in the multicast tree. The tag represents the time the link will have to be connected to the multicast tree. 図1 shows how the link-cost has modified according to new-node’s staying duration.

▲図1　(a) Link-cost before re-calculation.
(b) Link-cost after re-calculation with respect to new node’s staying time.

 

4.これまでの成果

　Random networks of 100 nodes are generated by modifying popularly used Waxman’s proposed algorithm. The nodes of these networks are so connected that degree of each node is at least 2, and average node degree is 4, which is close to the average node degree of current network. For unconstrained routing algorithm we have compared our algorithm Distributed Modified Greedy (DMG) with Greedy and Naive algorithm.

　　
▲図2　Average Maximum and average Minimum tree cost comparison (unconstrained DMG algorithm)

　In 図2. we have shown the Maximum average and Mean average tree cost for different set of multicast nodes and 図3 shows cumulative cost of our proposed multiple QoS satisfying multicast routing (MQ-DMR) and other dynamic routing algorithms.

　The above table is a comparison table showing different algorithms and their corresponding hop-count and average tree-cost. We have also compared the number of failures with other routing algorithm along with our proposed DMG and multiple QoS satisfying MQ-DMR algorithm.

▲図3　Average cumulative tree cost of different

5.社会的効果

　The advancement in optical fiber and switching technologies have resulted in a new generation high-speed networks that can achieve speeds of up to a few gigabits per second. Also the progress in audio, video and data storage technologies has given rise to new distributed real-time applications. These applications may involve multimedia, which require low end-to-end delay. The applications’ requirements, such as the end-to-end delay, delay jitter, and loss rate, are expressed as QoS parameters which must be guaranteed. In addition, many of these new applications may involve multiple users, and hence the importance of multicast communication.

6.まとめ（総括）

　Dynamic multicast routing satisfying more than one QoS constraints required for multimedia transmission is an important problem. While finding such routes from source to destination is important, it is also important to see that use of network resources is optimized. We achieve this dual goal through our MQ-DMR algorithm. MQ-DMR used a unique way of cost calculation for the links constituting the existing multicast (MC) tree. The links which will remain connected to the MC tree for longer periods will have less cost. Therefore they will be used more to connect newer destination.