Network Design with Capacity and FlowAssignmentNow we are considering network design problems in which the link capacitiesare also to be dimensioned and the flows of traffic are to be routed. In otherwords, we want more than just designing the network topology. Before goinginto details, let us overview the issues that will be discussed:• How to take network performance into account, so that the model do esnot become hopelessly complicated.• Capacity assignment problem: flow routing and traffic demand is given,dimension the link capacities.• Flow assignment problem: link capacities are given, route the trafficflows.• Combined capacity and flow assignment: find both the capacities andthe flow routing.• Other heuristic solutions for capacity and flow assignment, combinedwith network topology design:– Branch Exchange Algorithm– Cut Saturation AlgorithmQueueing Delay as a PenaltyA reasonable way of coupling capacity assignment with network performancein a packet switched network is to consider the delay incurred by waiting inqueues (buffers), due to the capacity (rate) limit of the outgoing link.The simplest queueing model is the so called M/M/1 queue with infinitebuffer. For this model the following simple relationship can be derived.Notations:• τ: average queueing delay (average time a packet spends by waiting inthe queue)• λ: arrival rate (average number of packets arriving at the queue in unittime)• µ: service rate. The most practical interpretation of this is in terms ofpacket length: 1/µ is the average packet length.• C: channel (link) capacity (the rate in bit/sec at which data can leavethe queue)Then the following holds:τ =1µC − λNote that µC also has a practical meaning: it is the average number ofpackets that leave the queue in unit time. Why? Because C bit/sec is theoutgoing speed and an average packet is 1/µ bits long, soC1/µpackets canleave in unit time, on the average, which is equal to µC.The above formula also shows a natural condition for stability: in order toavoid infinitely growing delays, it is necessary that µC > λ, that is, thearrival rate should be smaller than the rate at which packets can leave.Let us denote the τ, C, λ values for link i by τi, Ci, λi. Then we haveτi=1µCi− λiNow let γj,kbe the average traffic rate between source node j and destinationk. Then the traffic in the whole network can be characterized by the sumγ =Xj,kγj,k.The network wide mean delay can be defined by summing up the link delaysfor all the l links, but weighting them with the arrival rate of the link, relativeto the network wide traffic:T =lXi=1λiγτi.This expresses the natural weighting that the delay on links that carry alarger part of the overall traffic is more critical.Using the formula for τiwe obtainT =1γlXi=1λiµCi− λi=1γlXi=1λi/µCi− λi/µNow observe that λi/µ has a practical meaning: if, on the average, λ packetsper second arrive at link i and a packet is 1/µ bits long, then λi·1µ= λi/µis the number of bits per second that flow trough the link, on the average.Thus,fi=λiµis the flow on link i. Substituting this into the mean delay formula we obtain akey relationship that connect the network wide mean delay, the link capacitiesand the link flow values:T =1γlXi=1fiCi− fiWe will use this formula in several network design models.(Note: Generalizations to more sophisticated queueing models are also pos-sible, such as for the M/G/1 queue, but here we restrict ourselves to the basecase only.)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) +³Plj=1qdjfj´2γTmax4The Flow Assignment ProblemCompared to the Capacity Assignment Problem, here the situation is re-versed: now the link capacities are given and we would like to find how muchtraffic should flow on each link.Note: The same problem is also called flow routing problem, since it essen-tially means planning the routes of the traffic flows through the network.We prefer the name flow assignment because the term routing is more oftenused for the task of finding a route for a given call or a packet, rather thanreferring to a network design task.New objectiveNow, as the link capacities are given, the objective cannot be cost optimiza-tion, since the cost has been already spent for buying and implementingcapacities. A reasonable objective now is to assign the flows such that thenetwork performance is
View Full Document
Unlocking...