Flow Deviation Algorithm

Flow Deviation Algorithm is used to solve the Routing Problem

Notations

• each link i is assigned a weight, computed as

  w_i= ∂T/∂f_i

  this is the partial derivative of the objective function with respect to the flow on link i, evaluated with the actual flow that we have in the current iteration (as the iteration algorithm proceeds, the flow values change, so the weights will change, too)

• shortest path flow Φ

  this is the flow assignment that is obtained by routing all the flow between each source-destination pair along the minimum weight path, with respect to the current weights (=shortest path)

  (note: routing everything along the shortest paths may violate the capacity constraints. if this happens, then we route as much as possible along shortest paths and route the rest along the second shortest paths, etc)

Flow Deviation Algorithm

1. compute an initial feasible flow f⁽⁰⁾(note: this may require solving a multi-commodity flow problem)
2. compute the link weights: w_i= ∂T/∂f_iwith the current flow
3. using these weights compute the shortest path flow for current iteration j
4. let us denote the resulting flow vector by Φ^(j)
5. update the flow vector f (i.e. compute the next iteration):
   f^(j+1) = (1 - α_j)Φ^(j)+ α_jf^(j)
6. where α_j is a parameter with 0 ≤ α_j≤ 1. the value of α_j is chosen as follows. compute the delay (objective function) with the flow vector f_α = (1 - α)Φ^(j)+ αf^(j):
   T(f_α) = T [(1 - α)Φ^(j)+ αf^(j)]
7. since Φ^(j)and f^(j)are already known vectors, therefore, the resulting delay T depends only on the single variable α. Now choose α such that the delay is minimized, this will define α_j
   α_j= arg min_0≤α≤1T [(1 - α)Φ^(j)+ αf^(j)]
   where arg min means the minimizing argument of the function
8. if |T(f^(j+1)) − T(f^(j))| < ε for a given error bound ε > 0, then STOP. Otherwise, set j := j + 1 and repeat from step 1