D2V-VNS-RPS: Delay and Delay Variation Constrained Algorithm based on Variable Neighborhood Search Algorithm for RP Selection Problem in PIM-SM Protocol

Due to the progress of network multimedia technology, a majority of real-time multimedia applications need multicast communication to transmit information. These applications require a multicast routing protocol in which packets arrive to multicast receptors within a specified QOS guaranteed. D2V-RPS's problem (delay and delay variation RP Selection) consists in choosing an optimal multicast router in the network as the root of the Shared multicast Tree (ST) within a specified delay and delay variation associated. The choice of this specific router, called RP in PIM-SM protocol, is the main problem concerning the construction of multicast tree; this choice affects the structure of multicast routing tree, and therefore influences performances of both multicast session and routing scheme. The determination of a best position of the RP within a specified delay and delay variation associated is an NP complete problem: it needs to be solved through a heuristic algorithm. In this paper, we propose a new RP Selection algorithm based on Variable Neighborhood Search algorithm, which based on a systematic neighborhood changing. D2V-VNS-RPS algorithm selects the RP router by considering tree cost, delay and delay variation. Simulation results show that good performance is achieved.