Please use this identifier to cite or link to this item:
Title: An effective algorithm for obtaining the set of all minimal cost pairs of disjoint paths with dual arc costs
Authors: Gomes, Teresa
Craveirinha, José
Jorge, Luísa
Keywords: Telecommunication networks
Paths with minimal cost sum
Dual arc costs
Issue Date: 2008
Publisher: Bo Chen
Citation: Gomes, Teresa; Craveirinha, José; Jorge, Luísa (2008) - An effective algorithm for obtaining the set of all minimal cost pairs of disjoint paths with dual arc costs. In 6th International Symposium on Combinatorial Optimization. University of Warwick
Abstract: In today’s telecommunications networks it is necessary, for reliability reasons, to use protection schemes involving the calculation of two (or more) disjoint paths for each node-to-node connection, especially when large amounts of traffic have to be routed in the network. This concern is particularly relevant in optical networks, namely WDM (Wavelength Division Multiplexing) networks due to the very high rates supported by lightpaths, and in the Internet using MPLS (Multiprotocol Label Switching). In this context the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability while minimising bandwidth consumption, is extremely important. The problem of finding k disjoint paths from s to t (two distinct nodes), in a network with k different costs on every arc such that the total cost of the paths is minimised is NP-complete even for k = 2, when the relationship between the k arc costs (in the same arc) is arbitrary. When k = 2 these networks are usually designated as dual arc cost networks. In this paper we propose an exact algorithm for finding the whole set of arc-disjoint path pairs, with minimal cost in a network with dual arc costs. The addressed problem can be formalised as follows. Let G = (V,E) be a directed network with node set V = {v1, v2, . . . , vn} and and arc set E = {e1, e2, . . . , em} (were n and m designate the number of nodes and arcs in G, respectively), where two different non-negative cost functions (or metrics) in the arcs, are defined: η(j) : E → IN0 (j = 1, 2) (1) η(j)((va, vb)) = c(j) vavb (va, vb) ∈ E (2) The cost C(j) of a (loopless) path p in G with respect to metric η(j), is: C(j)(p) = X (va,vb)∈p c(j) vavb (j = 1, 2) (3) Let path p, p = hv1, e1, v2, . . . , vi−1, ei−1, vii, be given as an alternate sequence of nodes and arcs from G, such that the tail of ek is vk and the head of ek is vk+1, for k = 1, 2, . . . , i − 1 (all the vi in p are different). Let the set of nodes in p be V ∗(p) and the set of arcs in p be E∗(p). Two paths p = hv1, e1, v2, . . . , vi−1, ei−1, vii and q are arc-disjoint if E∗(p) ∩ E∗(q) = ∅. Two paths p and q are disjoint if V ∗(p) ∩ V ∗(q) = ∅, and are internally disjoint if {v2, . . . , vi−1} ∩ V ∗(q) = ∅. We will say that two paths are node disjoint if they are internally disjoint. The addressed problem is to find the whole set of pairs (p, q) of arc disjoint paths which minimise the total cost of the pair, defined by: C[(p, q)] = C(1)(p) + C(2)(q) (4) where p and q have the same source and sink node. An exact algorithm for solving this NP-complete problem will be proposed, based on a condition which guarantees that the optimal path pair cost has been obtained. This optimality condition is based on the calculation of increasingly tightened upper and lower bounds on the optimal cost. A formal proof of the correctness of the algorithm is described. Extensive experimentation is presented to show the effectiveness of the algorithm. It will also be explained how the proposed approach can also be used for obtaining the minimal cost disjoint path pair with constraints on the maximum number of arcs allowed per path, a problem of interest in various applications, namely in telecommunication networks.
Appears in Collections:IC - Resumos em Proceedings Não Indexados ao ISI/Scopus

Files in This Item:
File Description SizeFormat 
co2008_abstractbook.pdf913,76 kBAdobe PDFView/Open

FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.