Multicast routing with quality of service and traffic engineering requirements in the Internet, based on genetic algorithm

摘要

The prevalent Internet service model is the best-effort, which does not permit users to obtain Quality of Service (QoS) because it does not have a differentiated treatment for data flows. The IETF (Internet Engineering Task Force) has proposed several solutions for QoS, among them, the Traffic Engineering (TE), which asks for Constraint-Based Routing. In the routing process, the combination of additive and/or multiplicative metrics is an NP-complete problem. Thus, the Constraint-Based Routing is viewed as an intractable implementation problem. In order to deal with the high computational power required by the QoS routing, the use of a Genetic Algorithm (GA) as a method to obtain the appropriate routes has been presented in various works [I, 2]. The GA discussed in this work was adapted from the model presented in [2] that uses bandwidth, delay and cost as metrics to evaluate the routes. Two innovations were incorporated in the GA in order to attend TE requirements: inclusion of the metric number of steps (or hops) in the route evaluation, and a mechanism to avoid the generation of repeated individuals producing several optimal and sub-optimal routes. These two modifications are important for TE because they enable fast re-routing, load balancing and an improvement in the general performance of the network, by reducing hops steps.