Abstract :
Many real-time applications, such as video conferencing, require the transmission of flows from a sender to multiple receivers subject to Quality of Service (QoS) delivery constraints (e.g. bounded delay). This paper addresses the problem of effective multicast tree construction for interactive audiovisual communication. QoS metrics (bandwidth, delay, etc.) on links of some networks are not symmetric as in wireless ad hoc networks. So, the network is modelled as a directed graph. We associate an arc cost, an arc bandwidth, an arc delay, etc., with each arc in the network. The problem is to construct a tree spanning the destination nodes, such that it has the least cost, and so the QoS metrics on the path from source to each destination are bounded. Since the problem of computing the optimal constrained multicast tree is NP-complete, we present a quasipolynomial-time and deterministic approximation algorithm. Experimental results through simulations show that the performance of the heuristic is near optimal.
Keywords :
computational complexity; directed graphs; multicast communication; multimedia communication; quality of service; telecommunication network routing; telecommunication network topology; trees (mathematics); NP-complete problem; QoS metrics; arc bandwidth; arc cost; arc delay; deterministic approximation algorithm; deterministic source-based heuristic; directed graph; interactive audiovisual communication; multimedia information multicasting; optimal constrained multicast tree; quality-of-service; quasipolynomial-time heuristic; routing algorithms; spanning tree construction; Approximation algorithms; Bandwidth; Computational modeling; Costs; Delay; Mobile ad hoc networks; Multicast algorithms; Quality of service; Tree graphs; Videoconference;
