1.Introduction
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.Overview of our research activity
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.Detail of the system
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. Figure 1 shows how the linkcost has modified according
to newnode’s staying duration.
[Figure 1. (a) Linkcost before recalculation.
(b) Linkcost after recalculation with respect to new node’s staying
time]
4.Results of our research
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 Naïve algorithm.
[Figure 2. Average Maximum and average Minimum tree cost comparison
(unconstrained DMG algorithm)]
In Figure 2. we have shown the Maximum average and Mean average tree cost
for different set of multicast nodes and Figure 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.
[Figure 3. Average cumulative tree cost of different ]
5.Impacts of our research activity
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.Summary
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.
