An application of the genetic algorithm to virtual link management for reliable hierarchical link-state routing

This paper addresses the issue of augmenting backbone configuration, which arises from ISP's hierarchical Link-State(LS) routing operations. Focusing on Virtual Link(VL) configuration, proposed is an efficient augmentation scheme of increasing redundancy in the original backbone topology. A VL restores hidden information back to the backbone topological database, thereby enhancing redundancy in the backbone and preventing partition of the backbone when some links fail. With given potential VL locations and the original backbone topology, we propose a bi-objective optimal VL placement model together with a genetic algorithm. In particular, the model explicitly evaluates the benefit side as well as the cost side of VL configuration, and fully leverages the trade-off. To our knowledge, this is the first study to systematically attack the VL configuration problem in hierarchical LS routing. The proposed model and algorithm are expected to relieve network administrators from the burden of configuring VLs by making the routing domain more tolerable to backbone link failures.