An algorithm of anycast routing with multi-QoS constraints based on PBIL
HU Chengjun · Journal of Liaoning Technical University · 2009
In order to achieve the goal of least-cost anycast routing with multiple Quality-of-Services (QoS) constraints, such as delay, delay-jitter, bandwidth and packet loss ratio, which is known as a NP-complete problem and can not be efficiently solved using traditional methods, a novel anycast routing algorithm based on Population-Based Incremental Learning (PBIL) is proposed in this paper. The PBIL combines the features of Genetic Algorithm (GA) and competitive learning in an efficient way. It is a tachytelic evolution method by updating a probability vector. In addition, a novel learning mechanism is developed to update the prototype vector. According to this new learning mechanism, two best individuals are used to update the prototype vector instead of only one best individual. It increases the chances of more individuals with better characteristics being selected and preserved for next generations. Finally, both the proposed algorithm and GA-based anycast routing algorithm are tested in randomly generated topologies for comparisons. Simulation results show that the proposed algorithm outperforms GA in terms of accuracy, routing success rate and execution speed.