COMP9334: Capacity Planning of Computer Systems and Networks
Optimisation (3): Network flow
The story so far
Linear programming (LP)
Real values for decision variables, linear in objective function, linear in constraints
Large LP problems can be solved routinely
Integer programming (IP)
Some decision variables can only take integer values
Some decision variables can only take binary values, e.g. for making yes-or-no decisions
IP problems can be solved using branch and bound in principle Computation complexity is generally exponential except for unimodular problems
Page 1
Week 9B
Applications of integer programming for network flow problems
Traffic Engineering Dimensioning problem Topology design
Page 2
Traffic Engineering Example (1)
An ISP owns the following network which connects 5 cities A, B, C, D and E.
Capacity of each link is 1000 Mbps
A
B
The traffic demands between cities are: A to B: 600 Mbps
A to E: 400 Mbps
A to C: 500 Mbps
Question: How should we route the traffic so that the links are at most 80% utilised and we use the minimum amount of resources?
EC D
Page 3
Traffic Engineering Example (2)
Capacity of each link is 1000 Mbps
500 Mbps
600 Mbps
A
The traffic demands between cities are: A to B: 600 Mbps
A to E: 400 Mbps
A to C: 500 Mbps
B Let us assume that the traffic demand
will take the shortest path between its end points
But 1100 Mbps in link A-B! The link is over-utilised!
400 Mbps
EC
D
How should you route the traffic?
Page 4
Traffic Engineering Example (3)
Capacity of each link is 1000 Mbps
100 Mbps
600 Mbps
• The traffic demands between cities are:
A to B: 600 Mbps
A to E: 400 Mbps
A to C: 500 Mbps
• Traffic in links
A-B = 700 Mbps } B-C = 100 Mbps A-E = 800 Mbps E-D = 400 Mbps D-C = 400 Mbps
• Link A-E is 80% utilised. Others are less utilised.
A
400 Mbps
B
+
EC 400 Mbps D
Resources used = 2400Mbps
Page 5
Traffic Engineering Example (4)
Capacity of each link is 1000 Mbps
200 Mbps
600 Mbps
• The traffic demands between cities are:
A to B: 600 Mbps
A to E: 400 Mbps
A to C: 500 Mbps
• Traffic in links
A-B = 800 Mbps } B-C = 200 Mbps A-E = 700 Mbps E-D = 300 Mbps D-C = 300 Mbps
• Link A-B is 80% utilised. Others are less utilised.
A
400 Mbps
B
+
EC 300 Mbps D
Resources used = 2300Mbps
Page 6
Traffic Engineering
General traffic engineering problem:
Given:
A network (i.e. nodes, links and their capacites) The traffic demand between each pair of nodes.
Find: how to route the traffic to best utilise the resource
The traffic engineering example earlier was simple, but for a commercial carrier (Next slide shows the network map of a commercial carrier.), it’s no longer so.
Traffic engineering problems can be solved systematically using integer programming
These problems are generally known as network flow problems. Note: flow is synonymous with traffic demand between a pair of nodes.
We will start with the simplest network flow problem, finding the shortest path for one flow.
Page 7
Page 8
Network flow problems
Network flow problems are important applications of integer programming
Move some entity from one point to another in the network Given alternative ways, find the most efficient one, e.g. minimum cost, maximum profit, etc.
Network is represented as a directed graph G = (N, E) N = the set of nodes, e.g. N = {1,2,3,4,5,6}
E = the set of directed edges, e.g. E = {⟨1,2⟩,⟨1,3⟩,⟨2,1⟩,…}
Page 9
Finding the shortest path
Aim: Find the shortest path from the source node to the destination node of a flow
Cost is generally assumed to be additive, i.e. cost of a path = sum of the cost of using each edge in the path
E.g. cost of using edges ⟨1, 2⟩, ⟨2, 4⟩ and ⟨4, 6⟩
= cost of edge ⟨1,2⟩ + cost of edge ⟨2,4⟩ + cost of edge ⟨4,6⟩
Page 10
Shortest path problem (SPP)
Given
A directed graph G = (N, E)
A flow of size 1 enters at node s (source) and leaves at node d (destination)
It costs ci,j for using directed edge ⟨i, j⟩
Find which directed edges the flow should use in order that
The total cost is minimized
The entire flow must use only one path
Logical decision: Should I use a directed edge or not?
Page 11
Formulating SPP
Decision variables
1 if directed edge ⟨i, j⟩ in E is used 0 otherwise
xi,j =
We assume 1 unit of flow from the source to the destination
An important part of the formulation is to make sure the directed edges selected actually form a connected path from the source to the destination
This is by adding the conservation of flow constraints
Page 12
Conservation of flow: Source node
What goes in = What goes out
Flow going into node 1 from external = 1
Flow going into node 1 from neighboring nodes = x2,1
Second index is “1”
Flow going from node 1 to neighboring nodes = x1,2 + x1,3
First index is “1” Therefore, we have
1+x2,1 =x1,2 +x1,3
Page 13
Conservation of flow: Destination node
What goes in = What goes out
Flow going into node 6 from neighboring nodes = x4,6 + x5,6 Second index is “6”
Flow going from node 6 to neighboring nodes = x6,5 First index is “6”
Flow going from node 6 to external = 1 Therefore, we have
x4,6 +x5,6 =x6,5 +1
Page 14
Conservation of flow: Other nodes
E.g. flow conservation at node 2: What goes in = What goes out
Flow going into node 2 from neighboring nodes = x1,2 + x4,2 Second index is “2”
Flow going from node 2 to neighboring nodes = x2,1 + x2,4 + x2,5 First index is “2”
Therefore, we have
x1,2 + x4,2 = x2,1 + x2,4 + x2,5
Page 15
Conservation of flow constraints
In our example network, the source is node 1, so the constraint is
1+x2,1 =x1,2 +x1,3 This can be rewritten as
x1,j− xj,1=1 j :⟨1,j ⟩∈E j :⟨j,1⟩∈E
The destination is node 6, so the constraint is
x4,6 +x5,6 =x6,5 +1 This can be rewritten as
x6,j − xj,6 =−1 j :⟨6,j ⟩∈E j :⟨j,6⟩∈E
Page 16
Conservation of flow constraints (cont.)
For all other nodes (neither a source or a destination), e.g. node 2, the constraint is
x1,2 + x4,2 = x2,1 + x2,4 + x2,5 This can be rewritten as
x2,j− xj,2=0 j :⟨2,j ⟩∈E j :⟨j,2⟩∈E
The flow conservation constraints can be written in a compact form
xi,j− xj,i=0, i∈N−{s,d} j :⟨i,j ⟩∈E j :⟨j,i⟩∈E
Page 17
IP formulation for SPP
SPP can be formulated as
subject to
xi,j− xj,i = j :⟨i,j ⟩∈E j :⟨j,i⟩∈E
xi,j ∈
1
min ci,j xi,j ⟨i,j ⟩∈E
if i = s
0 ifi∈N−{s,d}
−1 ifi=d
{0,1} for all ⟨i,j⟩ ∈ E
Page 18
SPP example
We will use AMPL/CPLEX for solving SPP in this example network
Note:
It is far more efficient to use Dijkstra’s algorithm for solving SPP The reason of using integer programming here is for illustration only
The files are shortest.dat, shortest.mod and shortest_batch Page 19
Flow conservation constraints
The flow conservation constraints ensure that there is only one path from the source node s to destination node d
xi,j− xj,i = j :⟨i,j ⟩∈E j :⟨j,i⟩∈E
xi,j ∈
1 if i = s
0 ifi∈N−{s,d}
−1 ifi=d
{0,1} for all ⟨i,j⟩ ∈ E
Page 20
Introducing non-unit flow and link capacity (1)
(Note: A dot point preceded by ⋆ indicates that it is different from the setting of the shortest path problem.)
Given
A directed graph (N, E)
⋆ A flow of size f with source node s and destination node d
It costs cij (per unit flow) for the flow to use directed edge (i, j) ⋆ The capacity of the directed edge (i, j) is bij
Find which directed edges the flow should use in order that
The total cost is minimised
The entire flow must use only one path
⋆ The flow on any directed edge does not exceed its capacity
Page 21
Introducing non-unit flow and link capacity (2)
Decision variables are the same as before
1 if directed edge (i, j) is used 0 otherwise
xij =
The amount of flow on directed edge (i,j) will be fxij
Page 22
Introducing non-unit flow and link capacity (3)
The problem formulation is
subject to
xij− xji = j :(i,j )∈E j :(j,i)∈E
1 if i = s
0 ifi∈N−{s,d}
min cij xij (i,j )∈E
−1 ifi=d
fxij ≤ bij forall(i,j)∈E (∗∗∗)
xij ∈ {0,1} for all (i,j) ∈ E
Note: (∗ ∗ ∗) — this constraint ensures that only links with sufficient capacity may be chosen to carry the flow.
Solution: Eliminate edges with insufficient capacity, then Dijkstra.
Page 23
Multiple flows (1)
Given: Each link has capacity of 10 Mbps
Flow 1: 8 Mbps
2 1
4
3
5
Flow 2: 8 Mbps
Assuming cost for each link is 1.
What if both flows use the shortest path?
Page 24
Multiple flows (2)
Given: Each link has capacity of 10 Mbps
Flow 1: 8 Mbps
2 1
4
3
5
Flow 2: 8 Mbps
16 Mbps of flows on 10Mbps
⇒ Utilisation > 1, High packet delay and loss
Page 25
Traffic engineering problem
Given
A directed graph (N, E)
⋆ m flows (indexed by k = 1, 2, …m)
⋆ Flow k has size fk, source node sk, destination dk
⋆ It costs cij for a unit of flow to use directed edge (i, j)
The capacity of directed edge is bij
Find the directed edges that each flow should use in order that
The total cost is minimised
The entire flow must use only one path
⋆ The total flow on a directed edge does not exceed its capacity
Page 26
Digression: Integral versus continuous traffic engineering
There are two versions of traffic engineering problem
The integral version where each flow must use only one path, i.e. all packets in a flow must use the same path
In order to ensure that the packets use a certain path, you can use source routing (available in IP version 6) or MPLS (multi- protocol label switching – covered in COMP9332)
The continuous version where each flow may use multiple paths, e.g. the one described on pages 5 – 6 of this lecture.
In order to split the flow, a classifier will be required at the router to send packets on different paths
We will see how we can formulate the integral traffic engineering problem
Page 27
Traffic engineering IP formulation (1)
Decision variables: m sets of decision variables, one for each flow
1 if flow k uses directed edge (i, j) 0 otherwise
xijk =
The flow on directed edge (i, j) will be
m fkxijk
k=1
Ex: m = 3. Flows 1 and 3 use edge (1,2) but flow 2 doesn’t.
Total flow in edge (1,2) = f1 + f3
mk=1fkx12k =f1 ×x121+f2 ×x122+f3 ×x123 =f1 +f3
=1 =0 =1
Page 28
Traffic engineering IP formulation (2)
The problem formulation is
subject to
1 ifi=s k
0 ifi∈N−{sk,dk} k=1,…,m(∗) −1 ifi=dk
bij for all (i,j) ∈ E (∗∗)
{0,1} for all (i,j) ∈ E, k = 1,…,m
j :(i,j )∈E
j :(j,i)∈E m
xijk−
xjik = fkxijk ≤
k=1
min
m
cijfkxijk
(i,j)∈E k=1
xijk ∈
(∗) – One set of flow balance constraint per flow. Enforces flow k is from sk to dk
(∗∗) – Total flow on a link does not exceed its capacity.
Page 29
AMPL Example
Given: Each link has capacity of 10 Mbps
Flow 1: 8 Mbps
2 1
4
3
5
Flow 2: 8 Mbps
Assuming cost for each link is 1.
What if both flows use the shortest path?
Files are mcf1.dat, mcf1.mod and mcf1_batch,
Page 30
Traffic engineering problem
Also known as
The multi-commodity flow problem in operations research Flow assignment problem
Essence: assign a flow to a path so that performance is met i.e. routing problem
Many variations possible
Constraint on the path delay / number of hops Constraint on packet loss rate
Page 31
Network design problem(1)
In flow assignment, we assume the network topology and link capacities are given.
Flow 2: 8 Mbps
Flow 1: 8 Mbps
2 1
4
3
5
Why should we choose capacity 10Mbps? Why not 100Mbps? Why should we choose to have a link between (2,3) but not (2,5)?
Page 32
Network design problem(2)
Given
A set of nodes N
m flows of size fk, source sk, destination dk Minimum network building cost
Design options in network design problems
Topology: Which directed links to include Capacity of the link
How the flows are routed?
There are a few different network design problems
Page 33
Different network design problems
Flow Assignment Problem
Given: flows, topology, capacity Find: paths for the flows
Capacity and Flow Assignment Problem
Given: flows, topology, network cost Find: paths for the flows, capacity
Topology, Capacity and Flow Assignment Problem
Given: flows, network cost
Find: paths for the flows, capacity, topology
Page 34
Summary
Network flow problem
How to route traffic from a source node to destination node? Many variations
Flow conservation constraint to enforce a path from a source node to a destination node
Page 35
References
Advanced formulation of integer programming problems Winston, “Operations Research”, Section 9.2
Network flow problems
Ahuja et al, “Network Flows”, Sections 1.2
Page 36