|[Theme]Dynamic Multicast Routing: with multiple QoS Constraints|
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.Overview of our research activity
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.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 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. Figure 1 shows how the link-cost has modified according to new-node’s staying duration.
4.Results of our research
5.Impacts of our research activity
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.
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.
|The inquiry about this webpage.||Copyright (C) 2004 TAO All Rights Reserved.|