The Capacity Assignment ProblemIn this task we aim at dimensioning link capacities, assuming that the fol-lowing information is given as input:• Network topology• Traffic matrix R. An entry Rpqthe matrix is the traffic demand fromnode p to q.• Flow routing, in the form of a prescribed flow value fion each link i.These values are collected in the flow vector f = (f1, f2, . . . , fl).• An upper limit Tmaxon the network-wide mean delay.• A cost function di(Ci) for each link. This means, if we allocate Cicapacity to link i, then its cost will be di(Ci). A special case when theproblem is well solvable is the linear cost with fixed charge. In this casethe cost function is of the formdi(Ci) = diCi+ di0where di, di0are given constants.1ObjectiveFind the link capacities C = (C1, C2, . . . , Cl), such that the total costD =lXi=1di(Ci)is minimized.Constraints• The flow cannot exceed the capacity on any link:fi≤ Ci(∀i)In vector form:f ≤ C• The capacity is nonnegative:C ≥ 0• The network-wide mean delay cannot exceed Tmax. Using the formulawe derived for T (see the lecture note “Queueing Delay as a Penalty),this can be expressed as1γlXi=1fiCi− fi≤ Tmaxwhere γ =Pp,qRpqand this quantity can be directly computed fromthe input (via summing up the entries of the traffic matrix).2Thus, the optimization task is formulated as follows:max D =lXi=1di(Ci)Subject tof ≤ CC ≥ 01γlXi=1fiCi− fi≤ TmaxSolutionAn interesting thing is that for the case of linear cost with fixed charge (whenthe cost fuction is expressed as di(Ci) = diCi+ di0) there is an expliciteformula for the optimal capacities. This can be obtained via the method ofLagrange multipliers. The optimal capacity assignment isCi,opt= fi+Plj=1qdjfjγTmaxsfidi.Note that it is a rare, nice event that we can express the optimum via aclosed formula, in most mathematical programming models this cannot beexpected.Once the optimal capacity values are known, we can substitute them intothe cost function to obtain the optimal total cost:Dopt=lXi=1(diCi,opt+ di0)After substituting the expression of Ci,optand rearranging we get3Dopt=lXi=1(difi+ di0)
View Full Document
Unlocking...