Flow Assignment Problem or Flow Routing Problem is the reversed situation of the Capacity Assignment Problem

determine the optimal assignment of flow on each link, when given capacities of each link and the traffic demand between each pair of nodes

assign flows in such a way that the network performance is optimized in terms of minimizing the network wide mean delay

Problem

input data:

• network topology
• traffic matrix R, where each entry R_pq is the traffic demand from node p to q
• link capacities C = (C₁, C₂, …, C_l)

Objective

find the flow assignment f = (f₁, f₂, …, f_l), such that the network wide mean delay is minimized

to make the delay formula more general, we can include the propagation delay (Pi) and processing delay (Ki) on each link i. Since these delays are incurred for each packet, the additional term will be proportional to the arrival rate: λi(Pi + Ki). Using that fi = λi/μi, the additional delay is equal to fiu(Pi + Ki). Thus, the more general mean delay formula is:

Constraints

• the flow cannot exceed the capacity on any link:
  f ≤ C

• the flow is non-negative:
  f ≥ 0

• the flow should satisfy the demand:
  “f is a multi-commodity flow satisfy R” is expressible via a system of linear inequalities. Thus, there is a matrix A and a vector b, such that the condition is expressed as

  Af ≤ b

  since in the multi-commodity flow formulation the flow cannot exceed the capacity and cannot be negative

  therefore, this includes the first 2 constraints (f ≤ C and f ≥ 0) as well

LP Problem Formulation

How do we find out the entries of the A matrix and the b vector? similar to LP - Multi-Commodity Flow Problem - 1

Solution

• Flow Deviation Algorithm