Optimizing Multipath Routing for Congestion Minimization
Explore the concept of multipath routing to minimize congestion in network flows, focusing on multiroute scenarios. Learn about flow decomposition, s-t flows in directed graphs, and the utilization of multiroute flows to enhance network efficiency. Discover how congestion minimization plays a crucial role in path selection, utilizing acyclic edge flows and edge-disjoint paths. The discussion delves into various strategies for congestion minimization, including special cases like edge-disjoint paths and solving flow relaxation problems. Examining congestion minimization from different perspectives sheds light on improving network performance in challenging scenarios.
Uploaded on | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Multipath Routing for Congestion Minimization & Multiroute Flows Chandra Chekuri Univ of Illinois, Urbana-Champaign Joint work with Mark Idleman
s-t flows in directed graphs G=(V,E) directed graph with edge capacities c(e), e in E Edge based definition of flow f(e) flow on edge e flow conserved at internal nodes V \ {s,t} f(e) c(e) for all e Path based definition of flow f(p) flow on path p ?(st) ? ?? ? ? ? for all e
Flow Decomposition Edge flow f of value v can be decomposed into a path flow in O(nm) time A path flow of value v induces an edge flow of same value
Multi-route flows ?(st) = { p | p is a st path } ?(st, h) = {p = (p1,p2,...,ph) | each pj ?(st) and the paths are edge-disjoint } h-route s-t flow f : ?(st, h) R+ f(p) flow on path-tuple p
s p q t
Multiroute flows: basic theorem [Kishimoto,Aggarwal-Orlin] Theorem: An acyclic edge s-t flow x : E R+ with value v can be decomposed into a h-route flow iff x(e) v/h for all edges e 3 2 1 1 s s t t 1 1
Congestion Minimization t3 s2 Choose a path for each pair t1 Minimize max number of paths using any edge (congestion) G s1 t2 s3
Congestion Minimization t3 0.7 s2 Choose a path for each pair 0.5 0.25 t1 0.3 Minimize max number of paths using any edge (congestion) G 0.1 0.15 Special case: Edge-Disjoint Paths s1 [Raghavan-Thompson 87] Solve mc-flow relaxation (LP) Randomly pick a path according to fractional solution Chernoff bounds to show approx ratio of O(log n/log log n) 0.2 0.15 t2 s3 0.65
Multipath Routing h2 = 1 t3 s2 Choose hi paths for pair (si, ti) (assume paths for pair disjoint) t1 G Minimize max number of paths using any edge (congestion) h1 = 2 s1 t2 s3 h3 = 2
Multipath Routing t3 0.7 s2 Choose hi paths for pair (si, ti) (assume paths for pair disjoint) 0.5 0.3 t1 0.3 G 0.25 Minimize max number of paths using any edge (congestion) 0.95 s1 [Srinivasan 99] Solve relaxation (LP) Dependent rounding O(log n/log log n) approx via negative correlation 0.7 0.5 t2 s3 0.8
Can use multiroute flow decomposition Decompose for each pair flow into hi-route flow of value 1 Do independent rounding ala Raghavan-Thompson 0.5 0.3 s1 t1 0.25 0.95 0.05 0.2 0.25 0.5
Advantages Rounding and analysis exactly the same as it is for standard congestion minimization. No need for technicalities of dependent rounding. If paths are short can use Lovasz-Local-Lemma to reduce congestion to O(log d/log log d) where d is max # of edges in any path collection of decomposition (via existing results of [Srinivasan, Moser-Tardos, Haeupler-Saha-Srinivasan])
Choosing Paths G=(V,E) , (s1,t1), , (sk,tk) and need hi edge-disjoint paths per pair Minimize congestion
Multi-route flow LP Min C p P(siti, h) f(p) 1 for all (si, ti) p P(siti, h) :e p f(p) C for all e, i f(p) 0 for all p
Multi-route flow LP Min C p P(siti, hi) f(p) 1 for all (si, ti) p P(siti, hi) :e p f(p) C for all e, i f(p) 0 for all p How do we solve LP? 1. Ellipsoid for dual: separation oracle is min-cost flow 2. Compact LP followed by multi-route flow decomposition
Compact LP Min C for each i flow of value hi from si to ti f(e,i) 1 for all e, i i f(e,i) C for all e f(e,i) 0 for all e, i Can decompose f(e,i) into multi-route hi-route-flow and choose one path collection for each (si,ti) independently
Compact LP Min C for each i flow of value hi from si to ti f(e,i) 1 for all e, i i f(e,i) C for all e f(e,i) 0 for all e, i [Doerr-Kunnemann-Wahlstrom 10] solve same LP but do standard flow decomposition which does not guarantee disjoint paths. They employ dependent rounding after standard flow decomposition.
Choosing Short Paths G=(V,E) , (s1,t1), , (sk,tk) and need hi edge-disjoint paths per pair Want paths for each pair to be short : no more than d edges in total Minimize congestion
Min C for each i flow of value hi from si to ti f(e,i) 1 for all e, i i f(e,i) C for all e f(e,i) 0 for all e, I e f(e,i) d for all i Decompose f(e,i) into multi-route hi-route-flow. Apply filtering to find flow of value at least on paths which use at most 2d edges Choose one path collection for each (si,ti) independently from short path collections Congestion of O(log d/log log d) via LLL
Concluding Remarks Multiroute flows are useful to know Several explicit and implicit applications in routing and network design see refs in paper
