A novel extension of Kruskal´s algorithm in multicast routing

Multimedia applications are expected to guarantee end-to-end quality of service (QoS) and are characterized by stringent constraints on delay, delay-jitter, bandwidth, cost, etc. In the litterature, we observe that Kruskal´s algorithm is limited to minimal (maximal) spanning unconstrained tree. In this paper, we extend Kruskal´s algorithm to incorporate the delay bound constraint. Consequently, we propose a novel algorithm, called EKRUS (Extended Kruskal), for constructing multicast trees. The EKRUS´ distinguishing features consists in a better management of Kruskal´s priority queues, and in the provision of edge priority aggregation. Preliminary results show that our proposed EKRUS algorithm performs as good as the best well-known algorithms (such as the DDMC, DMCTc algorithms) while exhibiting better complexity. Furthermore, we believe that EKRUS is well suited to actual implementation in networks requiring support for multicast communication.