;A;-Penalty: a novel approach to find ;A;-Disjoint paths with differentiated path costs

摘要

In this paper we investigate the issue of preplanned end-to-end protection against multiple failures. In recent communications networks, such protection is provided by finding a set of k-disjoint paths for each demand. In particular, we analyze here the problem of calculating the set of k-disjoint paths of a demand in multi-cost networks, where each network arc an may be assigned k different costs ¿h (1), ¿h (2), ...., ¿h (k). A novel algorithm, called k-Penalty, is next introduced, in which the relation between values ¿h (i) for each arc ¿h may be arbitrary.