| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 83.47 KB | Adobe PDF |
Advisor(s)
Abstract(s)
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.
Description
Keywords
Telecommunication networks Paths with minimal cost sum Dual arc costs
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