Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

TITech: Extended Multiroute Flow for Multilink Attack Networks

No description
by

Jean-Francois Baffier

on 5 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of TITech: Extended Multiroute Flow for Multilink Attack Networks

Extended Multiroute Flow for Multilink Attack Networks
(拡張マルチルートフローとマルチリンク攻撃問題への応用)
Jean-François Alexis Baffier
バフィエール ジャンフランソワ アレクシ
The University of Tokyo
Imai Laboratory/JFLI(CNRS)
Supervisor: Hiroshi Imai
Co-Supervisor: Abdel Lisser
Vorapong Suppakitpaisarn (NII - ERATO)
Hidefumi Hiraishi (Todai)
Wenkai Dai (Universitat des Saarlandes)

Network Flow
MLA Flows
MLA-Robust
MLA-Reliable
MLA-Decomposition
Complexity

History
Algorithms
Under Attacks

Multiroute Flow
History
Properties
Algorithms

Extended
Multiroute Flow

h is non-integer parameter
solves MLA-Robust Flow
capacity-differentiation

Experiments
Efficiency of EMRF
Gap between bounds
Integral mapping

Flow in Network
max-flow
History
Algorithms
Attacks
Network
Flow
Cut
Duality
Soviet railway network (Harris and Ross, 1955)
Ford-Fulkerson: general case, algorithm, max-flow/min-cut duality (1956)
Edmonds-Karp: polytime algorithm (1972)
Applications include:
Network management
Computer vision
Task scheduling
Multilink-Attack (MLA)
MLA-robust
MLA-reliable
MLA-effectiveness
Definition
Related
Properties
MLA-decomposition
MLA-attack (finding the best k attacks on a given flow) is NP-hard, by Wenkai Dai and Vorapong Suppakitpaisarn.
MLA-Reliable NP-hard for integral case (new result)
Special case of minimax problem by Lee, Misra, and Rubenstein that is solved heuristically.
Multiroute Flow
Definition
Variants
About
History
Applications
Algorithms
(k+1)-approximation
Inequalities
Implications
Bounds
Extended Multiroute Flow (EMRF)
Extensions
Capacity
differentiation
Solution to MLA-flows
Improvements
Tighter bounds
Average Speed
Completed Multiroute Flow
Bad Example
IMRF
Iterative Multiroute Flow
source s, sink t
edge-connectivity \lambda
Number of attacks k
Not a max-flow in the general case
No NP-hardness proved (*)

A solution to the max-(k+1)-route flow problem is also a (k+1)-approximation to the MLA-robust flow, the MLA-reliable flow , and the MLA-decomposition problems.

Theorem
Experiments
Bounds and IMRF
Efficiency of EMRF
Settings
Mapping & Integers
Contributions
Definition of MLA-robust flow, MLA-reliable flow, and other MLA problems
NP-hardness of MLA-robust flow
Analysis of Extended Multiroute Flow algorithms
Relations between Multiroute and MLA-robust flows:
A (k+1)-approximation algorithm
EMRF solves MLA-robust flow for a class of network
Results hold for MLA-reliable
Classification of instances (EMRF-solvable, Flying Cut)
Experiments (through our c++ library):
EMRF is efficient on many instances, but R-MAT
Approximation algorithm is under 80% gap on R-MAT
IMRF is fast and efficient in pratice
A feasible flow is a linear combination of elementary paths from s to t under the capacity constraint.
Its value is the sum of the linear coefficients.
A solution to the max-flow problem is a feasible flow with the maximum flow value.
A cut is a partition of the nodes in two subsets. Its capacity is the sum of the links from the source side to the sink side.
The value of a max-flow is equal to the value of a min-cut.
The first max-flow algorithm is based on an augmenting path approach. Edmonds&Karp improved it to a polytime version.
The push-relabel method is the fastest on the average on practical cases.
Here k=1
Two cases:
The attacker strike first (MLA-robust)
First comes the flow (MLA-reliable)
A solution to MLA-robust flow is a max-flow with the maximum value on the network after deleting any set of k links.
The attacker strikes first. Then a flow is routed from the source to the sink.
Given a flow F, its MLA-effectiveness is the minimum value left of F after any set of k attacks on the network.
This problem has a value in itself and is proved to be NP-hard by Wenkai Dai and Vorapong Suppakitpaisarn.
A solution to MLA-reliable flow is flow with a maximum MLA-effectiveness.
In this situation, the attacker knows the flow repartition on the link and strike after the construction of a flow.
(*) We proved the NP-hardness for integral flow case last week. Reduction from Hamiltonian Circuit.
A h-route flow (a multiroute flow of h routes) is a linear combination of h-links disjoint elementary paths from the source to the sink.
Its value is the sum of the linear coefficients.
max-2-route flow
Introduced by Kishimoto and Takeuchi in 1993 along with a polytime algorithm.
Aggarwal and Orlin (2002): improves complexity through the analyse of a restricted max-flow function.
Simpler duality proof by Bagchi et al. in 2004
Correctness and complexity proofs in 2006 by Du and Chandrasekaran.
Aggarwal and Orlin 2002:
Birkhoff's theorem can be generalized to matricees that are not doubly stochastic
Machine scheduling problem
Direct applications to robust flows
2-route flow guarantee the restoration of networks after one failure
In this work, it is apply to solve or approximate MLA-robust flow, MLA-reliable flow and MLA-decomposition.
All polytime algorithms use a parametric max-flow function.
This function is a restricted max-flow such that given a real value x, the capacity c on any link is equal to the minimum between c and x.
Kishimoto's algorithm
Binary search (integral capacities only)
Primal-dual algorithm
Kishimoto extended this notion to more general case with delta-relaible flow, and alikes.
A multi-commodity version is studied through linear programming.
NP-hardness of multi-commodity flow implies that the three polytime algorithm can not be used directly.
Any multiroute flow value is lower than the value of a MLA-reliable flow.
If a multiroute flow value is equal to the value of a MLA-robust flow, then MLA-reliable and MLA-robust flow values are equals.
The approximation ratio of the multoute flow can be really bad when k is huge.
There exist infinite graphs were the equality hold for each case.
The bound can be further improved when k is close to the connectivity lambda.
Two extensions from Aneja et al.:
The number of routes h can be non-integer (Aneja, Chandrasekaran, Kabadi, Nair, 2007)
h can be a parameter, O(n*T) algorithm (Aneja, Chandrasekaran, Nair, 2003)
Guaranted ratio of k+1 from multiroute flow
Lower determinisic bound to MLA-reliable flow from the pseudo-tangent projection
Upper heuristic bound to MLA-robust flow from the duality of MLA-robust flow and cut
Speed-up twice by skipping at most half of the breakpoints (if no switching cut)
Reduce heuristically the step to the minimal number of switching cut (but can fail)
Construct a reliable flow by iterating multiroute flow algorithms.
Start with a lambda-route flow.
Then compe a (lambda-1)-route flow on the residual network. And so on till h=1.
Finally, sum the multiroute flow.
Guarantee a high tolerance to any number of failures. Can be far from the optimal value.
Each setup contains 1000 networks, and each network lead to lambda instances.
Complete network: n in [4,256]
2D grid: n in [4,64] on each dimension
3D grid: n in [4,8] on each dimension
Random shape: n in [4,256], m in [n,2^n]
Link are generated randomly. Uniformly for grids and complete networks. Following 5 distributions for random-shape networks.
R-MAT
Publications
(Accepted)
Submissions
(acceptance should be known in January or February for LAGOS 2015 and Discrete Optimization)
Future Works
Class Diagram
About me
Introduction
Problem
Number of attacks k (here k=1)
Goldberg and Tarjan (2014)
Related Works
Max-flow
Soviet railway network (Harris and Ross, 1955)
Ford-Fulkerson: general case, algorithm, max-flow/min-cut duality (1956)
Edmonds-Karp: polytime algorithm (1972)
Applications include:
Network management
Computer vision
Task scheduling
Duality
The value of a max-flow is equal to the value of a min-cut.
Multiroute flow
Introduced by Kishimoto and Takeuchi (1993)
h-route flow : multiroute flow of h routes
Combinations of edge-disjoint paths with the same value
Extension of Duality to multiroute flow/cut
max-2-route flow
Algorithms
n nodes
m links
f max-flow value
U highest capacity
A max-h-route flow can be computed in h max-flow iterations
Kishimoto and Takeuchi (1993)
Aggarwal and Orlin (2002)
Improved to min[log(hU),h] max-flow iterations)
Overview
Network Flow
Multiroute Flow
Extended
Multiroute Flow
Grouped and analyzed
Average Speed-up
Multilink-Attack Network Flow
Definitions, analysis,
duality, complexity
Exact Algorithm
Class of instances
Capacity Differentiation
Approximation
k+1 approximation
Heuristic Upper Bound
Deterministic Lower Bound
Experiments
Network Synthesis
Maximum Flow (max-flow)
source
sink
Maximum Flow of value 6 from s to t
[· · · ], algorithm design techniques and data structures developed to compute maximum flows are useful for other problems as well. Although a special case of linear programming, the maximum flow problem is general enough so several important problems (such as the maximum bipartite matching problem) reduce to it.

Motivations
Network management
Tolerance to attacks or failures (recovery)
Resources consumption (energy, infrastructures)
MLA-robust flow shares max-flow properties
Computer Vision, Distribution Network
Stock Management, Task Scheduling
State-of-the-art (need of a trade-of)
Efficient algorithm on specific problems
Very broad problem often too complex or hard
Max-2-route flow
Multiroute Flow (max-h-route flow)
No attack
max-2-route flow = 10; max-flow = 10
One attack
max-2-route flow = 5; max-flow = 6
Contribution 1
MLA-robust flow
Number of attack k
Definition
MLA-robust duality
Definition (MLA-robust capacity)
Lemma 3.1
Definition (MLA-robust cut)
MLA-reliable flow
Definition (MLA-effectiveness)
Definition (MLA-reliable)
MLA-decomposition
Similar to MLA-reliable flow, but the attacker also know the routing information at the nodes.
Bad decomposition
Best Decomposition
(MLA-decomposition)
Exact Algorithm
Multiroute & MLA-robust cuts
Extended Multiroute Flow
s-t connectivity λ
restricted max-flow:
λ+1 parts (at most)
algorithm in O(λmn)
Extensions: (Aneja et al.)
non-integer
number of routes h (2007)
route-parametric
multiroute flow (2003)
Main Theorem (Corollary 3.9)
Informal:
Contribution 3
Flying Cut
EMRF does not detect the "Flying Cuts"
However, an approximation algorithm exists
The cut separating s and a
is the solution for 1 attack
The cut separating b and t
is the one detected by EMRF
k+1 approximation
Theorem 3.4
MLA-decomposition
MLA-reliable
MLA-robust
Guaranteed
max-(k+1)-route
Bounds
Heuristic upper bound (MLA-robust duality)
Deterministic lower bound of MLA-reliable (Extended Multiroute Flow)
Other results
Complexity: MLA-robust flow is NP-hard
Heuristic approximation algo: iterative multiroute flow
By W. Dai and V. Suppakitpaisarn:
MLA-attack of a decomposition is NP-hard
MLA-effectiveness of a flow is NP-hard
Compute a multiroute flow at each step
max-λ-route flow, then max-(λ-1)-route flow on residual network, and so on. Complexity: O(λ²mn)
Exact algorithm improvements (EMRF)
Speed average run-time: deterministic and heuristic
Capacity differentiation: enlarge class EMRF-solvable
Experiments
Classical flow versus completed multiroute flow
z
Success of exact algorithm (EMRF)
Approximation: gap bounds
COCOON 2015 (submit next month)
J.-F. Baffier, W. Dai, and V. Suppakitpaisarn
LAGOS 2015 (results February 3rd)
J.-F. Baffier, W. Dai, and V. Suppakitpaisarn
Discrete Optimization Special Issue (ISCO 2014)
J.-F. Baffier, V. Suppakitpaisarn, H. Hiraishi, H. Imai
WALCOM 2014
J.-F. Baffier and V. Suppakitpaisarn
ISCO 2014
J.-F. Baffier, V. Suppakitpaisarn, H. Hiraishi, H. Imai
TJIA 2014
V. Suppakitpaisarn and J.-F. Baffier
Broaden the scope of instances solved
Spectral Graph Theory
Wider field of problems
Variety of constraints
max-flow/min-cost
Real word flow constraints (CSP?)
Best MLA-flow
Candidate: Iterative Multiroute Flow
Resources optimization (at synthesis and use)
k=1 attack (red edge)
(Submitted)
HSPR 2015
Discrete Optimization (Special Issue ISCO 14)
MLA-robust
MLA-reliable
1. attacker strike
2. compute flow
1. compute flow
2. attacker strike
Contributions
Previous Works
Introduction and Analysis of Multilink-Attack (MLA) Network flows
MLA-robust flow
Duality of MLA-robust flow and cut
MLA-reliable flow
MLA-decomposition
Contribution 2
Analyze of Extended
Multiroute Flow (EMRF)
Relation between Multiroute cut and MLA-robust cut
Necessary condition for polytime algorithm
Flying cut (problematic case)
Approximation algorithm
max-(k+1)-route flow is a (k+1)-approximation algorithm to MLA-robust, MLA-reliable and MLA-decomposition
Upper Bound (duality of MLA-robust cut/flow)
Lower Bound (analysis of EMRF algorithm)
construct pairs of edge-disjoint paths with the same value (a pair of paths cannot share any common link)
Contributions
Max-h-route flow
(maximum multiroute flow of h routes)
max-2-route flow: guarantee a value of 5 after 1 attack
Definition:
A multiroute flow of h route is a combination of h edge-disjoint paths with the same value.
A max-h-route is multiroute flow of h routes with the maximum value.
min-h-route cut
MLA-robust cut
(k attacks)
By duality: relation between
multiroute flow and MLA-robust flow
Flow left = 2
Flow left = 3
(MLA-reliable flow)
Success rate of the EMRF algorithm on random shape networks
Success rate of EMRF algorithm on RMAT networks
Gap between the upper and lower bounds on random shape networks
Gap between upper and lower bounds on RMAT networks
Improvement of the multiroute flow over the classical max-flow
Bachelor/Master
at Paris-Sud
I was born in Paris (France)
Ph.D. at Todai
Post-Doc at ERATO Tohoku University
Network Flow (main topic)
Games
Game analysis (Skull&Roses board game)
Game AI (Starcraft, RTS games, Warhammer board game)
Alonso Gragera, Vorapong Suppakitpaisarn
Florian Richoux, Alberto Uriarte, Alonso Gragera
Search Algorithm (Local Search, Adaptive Search, CSP)
Application to both previous topics
Alex Fukunaga
Improvement of Search Methods
Salvador Abreu
Full transcript