A heuristic for widest edge-disjoint path pair lexicographic optimization

Abstract

Telecommunication services are pervasive in today’s human activity and are required to offer reliable and quality-of- service(QoS)-aware guaranteed services. In global path protection, the working path between a source and a destination can be protected by a backup path, which ensures data transfer in the event of a failure that makes the working path to be unavailable. Multipath and disjoint routing may require the calculation of disjoint paths maximizing the total bandwidth of the path pair (or set of paths) or the calculation of maximum-bandwidth disjoint paths. In this paper, a lexicographic optimization problem for obtaining maximum-bandwidth disjoint paths, and then maximizing the bandwidth of the widest path in the pair, is formalized. An effective heuristic for addressing this problem is presented.