On Finding Disjoint Paths in Single and Dual Link Cost NetworksOutlineFinding Disjoint Path PairsComputational ComplexitiesSolving The Min-Min ProblemInefficiency of KSPProposed ApproachConflicting Link SetDivide and ConquerThe Proposed Conflicting Link Exclusion (COLE) HeuristicSolving the Sub-problemFinding Conflicting Link SetFinding Conflicting Link Set (II)Reason for Not Using an Ordinary Min-CutShared Path ProtectionPerformance EvaluationNumber of Dijkstra Invocations (Min-Min)Performance in Shared Path ProtectionSummary~1~Infocom’04Mar. 10th. 2004On Finding Disjoint Pathsin Single and Dual Link Cost NetworksChunming Qiao*Chunming Qiao*LANDER, CSE DepartmentLANDER, CSE DepartmentSUNY at BuffaloSUNY at Buffalo*Collaborators: Dahai Xu, Yang Chen, Yizhi Xiong and Xin He*Collaborators: Dahai Xu, Yang Chen, Yizhi Xiong and Xin He~2~Infocom’04Mar. 10th. 2004OutlineThe Min-Min ProblemMotivation and DefinitionExisting and Proposed HeuristicsApplication and Performance EvaluationSummary~3~Infocom’04Mar. 10th. 2004Finding Disjoint Path PairsBasic and important problem in survivable routingThe Min-Min ProblemDefinition: Finding a link (node) disjoint path pair such that the length of the shorter path is minimized.ApplicationsEncrypted data on the shorter path, and decryption key on the longer pathShared Path Protection (use the shorter path as AP)Counterpart problemsMin-MaxMin-Sum~4~Infocom’04Mar. 10th. 2004Computational ComplexitiesMin-Sum (P) [Suurballe-74]Min-Max (NP Complete) [Li-90]Min-Min (P or NP Hard?)NP Complete! proved by Xu et. al. in INFOCOM’04]Reduction from a well-known NPC problem 3SATWe also proved that it is NP-hard to obtain a k-approximation to the optimal solution for any k > 1~5~Infocom’04Mar. 10th. 2004Solving The Min-Min ProblemActive Path First (APF) HeuristicFinds a shortest path for use as AP, followed by searching a disjoint BP.It may fail to find such a BP even though a disjoint path pair does exist.K Shortest Path (KSP) HeuristicFirst K shortest paths are found and tested in the increasing order of their costs (path lengths) to see if a disjoint BP exists.Could be time-consuming~6~Infocom’04Mar. 10th. 2004Inefficiency of KSP Any path from s to d consists of two sub-paths in domain E1 and E2 respectively.Links in E1 is much shorter than those in E2.The number of all possible sub-paths in E1 is very large1st2nd~7~Infocom’04Mar. 10th. 2004Proposed ApproachFind a shortest AP first (as in APF)If the AP doesn’t have a disjoint BP, determine the “conflicting link set” that are causing the problemTry another AP without using these problematic links~8~Infocom’04Mar. 10th. 2004Conflicting Link SetDefinitionA minimal subset of the links on AP such that no path using ALL these “problematic” links can find a disjoint counterpart, e.g., e1 and e2 in the following example. The Min-Min problem can be solved much faster by avoiding using at least one link in the conflicting link set for the next shortest AP.~9~Infocom’04Mar. 10th. 2004Divide and ConquerLet P(I, O) be the problem of finding a disjoint path pair where AP must use the links in set I (Inclusion) but not the links in O (the Exclusion set).Denote the original Min-Min problem by P(, )Find a shortest AP; If no disjoint BP, find the Conflicting Link SetDivide P(, ) into sub-problems based on the conflicting link set, e.g., P(, {e1}) and P({e1}, ) in the previous example. The same procedure may be applied recursively on these sub-problems, e.g., P({e1}, ) can be further divided into P({e1},{e2}) and P({e1,e2}, ).The definition of conflicting link set means that we do not need to try to solve P({e1,e2}, ).~10~Infocom’04Mar. 10th. 2004The Proposed Conflicting Link Exclusion (COLE) HeuristicAn algorithm to find the conflicting link set (to be discussed) Usually has fewer links than the half of the links on APFewer sub-problems than KSP“Divide and Conquer” based on the conflicting link set (rather than all the links on AP as in KSP)Then pick a best solution (with a shorter AP) among those for the sub-problems.Find a optimal or near-optimal result for each sub-problemEach sub-problem may be solved recursively using Divide-and-Conquer~11~Infocom’04Mar. 10th. 2004Solving the Sub-problemFinding a shortest path consisting of certain links (e.g. set I) is itself NP-HardApproximation method to speed up the computation. [Xu et al. OFC’04]~12~Infocom’04Mar. 10th. 2004Finding Conflicting Link SetFinding a link-disjoint path pair between nodes s and d in graph G=(V, E) = Finding two unit-flows in a flow network where each link's capacity is set to 1 unitAssume that the network is symmetricalFor the chosen AP, construct a new graph G0G0 uses the same V and E of GThe capacity of the links in AP is set to 1The capacity of the reverse links in AP is set to 0.The capacity of all other links with non-zero capacity in G (except those in AP) is set to |AP|+1 (or a larger value).~13~Infocom’04Mar. 10th. 2004Finding Conflicting Link Set (II)Let Φ0=(S, D) be a min-cut of G0, S={s, 3, 7} D={1, 2, 4, 5, 6, d} The set of negative links (from D to S) on AP of Φ0 is a Conflicting Link Set {e1, e2}~14~Infocom’04Mar. 10th. 2004Reason for Not Using an Ordinary Min-CutDivide and conquer based on Ordinary Min-Cut might not help reducing the computational complexity.AP0 is the shortest path (and no link-disjoint BP exists)APopt is the shortest path with a link-disjoint BPThe min-cut: The partition S = {s}, positive links are a and bDivide the original Min-Min problem into P(, {a}) and P({a}, {b})(no solution in P({a, b}, ) )Solving P(, {a}) leads to a non-optimal solution, and trying to solve P({a}, {b}) will again yield AP0~15~Infocom’04Mar. 10th. 2004Shared Path ProtectionTwo BPs can share backup bandwidth on a common link as long as their APs are disjoint (with a single failure)~16~Infocom’04Mar. 10th. 2004Performance EvaluationSolution to Min-Min problem (Single Link Cost Networks)COLE will stop iteration after finding optimal result.KSP can find the optimal result with a large enough K but has a longer running time than COLEIn both algorithms, the time for each invocation of the Dijkstra Algorithm to find the (next) shortest path