1.まえがき
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 realtime communication. If the QoS constraints are not satisfied,
the received data is meaningless. But satisfying multiple QoS is a well
known NPcomplete 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 BellmanFord shortest path algorithm.
2.研究概要
Routing algorithms which are used currently employed in networks
are either Dijkstra or BellmanFord 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 NPcompleteness 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 BellmanFord (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 lifetime is less than those with a shorter
lifetime. With every link we associate a pair [w, tag], where w is the
linkcost 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 linkcost has modified according
to newnode’s staying duration.
▲図1 (a) Linkcost before recalculation.
(b) Linkcost after recalculation 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 (MQDMR)
and other dynamic routing algorithms.
The above table is a comparison table showing different
algorithms and their corresponding hopcount and average treecost.
We have also compared the number of failures with other routing algorithm
along with our proposed DMG and multiple QoS satisfying MQDMR algorithm.
▲図3 Average cumulative tree cost of different
5.社会的効果
The advancement in optical fiber and switching technologies
have resulted in a new generation highspeed 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
realtime applications. These applications may involve multimedia, which
require low endtoend delay. The applications’ requirements, such as
the endtoend 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 MQDMR algorithm. MQDMR 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.
