An Application of Multi-Objective Genetic Algorithm to Virtual Link Configuration in a Link-State Backbone Area

摘要

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 in the topological database of each backbone router, thereby increasing 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, which explicitly evaluates the benefit side as well as the cost side of VL configuration, and fully leverages the trade-off between both sides. To our knowledge, this is the first try to attack systematically 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, support making the backbone more tolerable to backbone link failures, and finally, provide a practical vehicle for reliable LS hierarchical routing indispensable to overall service quality.