／var／logmarcus chiu

Capacity Assignment Problem

Created on

Capacity Assignment Problem determine the optimal capacities of each link, when given assigned flow value of each link and traffic demand between each pair of nodes

Problem

assuming that the following information is given as input:

  • network topology

  • traffic matrix R, where each entry Rpq is the traffic demand from node p to q

  • flow routing, in the form of a prescribed flow value fi on each link i. These values are collected in the flow vector f = (f1,f2, …, fl)

  • an upper limit Tmax on the network-wide mean delay

  • a cost function di(Ci) for each link. this means, if we allocate Ci capacity to link i, then its cost will be di(Ci). A special case when the problem is well solvable is the linear cost with fixed charge. In thus case the cost function is of the form: 

    where di and di0 are constants

    List indent undo

Objective

Find the link capacities C = (C1, C2, … , Cl), such that the total cost:

is minimized

Constraints

  • the flow cannot exceed the capacity on any link:
    fi ≤ Ci(∀i)
    in vector form:
    f ≤ C

  • the capacity is non-negative:
    Ci≥ 0 (∀i)
    in vector form:
    C ≥ 0

  • the network-wide mean delay cannot exceed Tmax:
    using the formula we derived for T (refer to: Network Wide Mean Delay) this can be expressed as

    List indent undo

    where γ is a constant that represents the total traffic rate within the network
    γ = Σp,q[Rpq]

LP Problem Formulation

LP Problem

  • objective function:
    minimize

    List indent undo

  • linear constraints:
    f ≤ C
    C ≥ 0

    List indent undo

Solution

if cost function di(Ci) is linear (i.e. di(Ci) = diCi + di0) there is an explicit formula for calculating the optimal capacity assignment:

once optimal capacity values are known, we substitute them into the cost function to obtain the optimal total cost

after substituting the expression of Ci,opt and rearranging we get