The 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 optimized in terms of minimizing the mean delay.The input data for the task contains the following:• Network topology• Traffic matrix R. An entry Rpqthe matrix is the traffic demand fromnode p to q.• Link capacities C = (C1, C2, . . . , Cl).ObjectiveFind the flow assignment f = (f1, f2, . . . , fl), such that network-wide meandelay is minimized.1To make the delay formula more general, we can include the propagationdelay (Pi) and processing delay (Ki) on each link i. Since these delays areincurred for each packet, the additional term will be proportional to thearrival rate: λi(Pi+ Ki). Using that fi= λi/µi, the additional delay is equalto fiµ(Pi+ Ki). Thus, the more general mean delay formula isT =1γlXi=1ÃfiCi− fi+ fiµ(Pi+ Ki)!=1γlXi=1fiÃ1Ci− fi+ µ(Pi+ Ki)!Constraints• The flow cannot exceed the capacity on any link:f ≤ C• The flow is nonnegative:f ≥ 0• The flow should satisfy the demand. This is verbally expressed as“f is a multicommodity flow satisfying R.”What is a multicommodity flow? Recall the flow problems from theerlier notes. They can be generalized by allowing that more “com-modities” are flowing through the network. That is, there are moreflows, each with its own supply/demand and each demand has to besatisfied by its own flow, but the flows jointly have to obey the capac-ity constraints when summed up on each link. Just as for the singlecommodity flow, this can be formulated as a system of linear inequali-ties. Thus, the condition “f is a multicommodity flow satisfying R” is2expressible via a system of linear inequalities. Thus, there is a matrixA and a vector b, such that the condition is expressed asAf ≤ b.Since in the multicommodity flow formulation the flow cannot exceedthe capacity and cannot be negative, therefore, this includes the firsttwo constraints (f ≤ C and f ≥ 0), as well.Summarizing, the optimization task can be concisely formulated as follows:min T =1γlXi=1fiÃ1Ci− fi+ µ(Pi+ Ki)!Subject toAf ≤ bwhere the constraint formalizes the requirement that f is a nonnegative mul-ticommodity flow satisfying R, respecting the capacity constraints, as ex-plained in the previous page.How do we find out the entries of the A matrix and the b vector? It can beobtained by writing down the details of the flow model, similarly to what wedid in the lecture note “An Application to Network Design”.3SolutionA solution can be found by an algorithm called the Flow Deviation Algorithm.Let us review and explain this algorithm below.Notations:• Each link i is assigned a weight, computed aswi=∂T∂fiThis is the partial derivative of the objective function with respect tothe flow on link i, evaluated with the actual flow that we have in thecurrent iteration (as the iterative algorithm porceeds, the flow valueschange, so the weights will change, too).• Shortest path flow Φ. This is the flow assignment that is obtainedby routing all the flow between each source-destination pair along theminimum weight path, with respect to the current weights (=shortestpath).(Note: Routing everything along shortest paths may violate the ca-pacity constraints. If this happens, then we route as much as possiblealong shortest paths and route the rest along second shortest pathsetc.)Now the flow deviation algorithm can be described as follows.Step 0. Compute an initial feasible flow f(0).(Note that this may require solving a multicommodity flow problem.)Step 1. Compute the link weightswi=∂T∂fi4with the current flow. Using these weights compute the shortest pathflow (as explained above) for the current iteration j (initially the it-eration index is j = 0). Let us denote the resulting flow vector byΦ(j).Step 2. Update the flow vector f (i.e., compute the next iteration):f(j+1)= (1 − αj)Φ(j)+ αjf(j)where αjis a parameter with 0 ≤ αj≤ 1. The value of αjis chosenas follows. Compute the delay (the objective function) with the flowvector fα= (1 − α)Φ(j)+ αf(j):T (fα) = T ((1 − α)Φ(j)+ αf(j))Since Φ(j)and f(j)are already known vectors, therefore, the resultingdelay T depends only on the single variable α. Now choose α such thatthe delay is minimized, this will define αj:αj= arg min0≤α≤1T ((1 − α)Φ(j)+ αf(j))where arg min means the minimizing argument of the function.Step 3. If¯¯¯T (f(j+1)) − T (f(j))¯¯¯< ²for a given error bound ² > 0, then stop. Otherwise, set j := j + 1and repeat from Step 1.5Questions and answers about the flow deviation algorithm• Question: Is it true that in each iteration we obtain a feasible flow?Answer: Yes. At the beginning we start with a feasible flow and theshortest path flow is also feasible by definition. During the iterationfeasibility cannot be destroyed, since the domain of feasibility is a con-vex set (a polyhedron), being defined by a system of linear inequalitites,and the new flow is always computed as the convex conbination of twofeasible flows, so the new iteration stays within the convex polyhedron.• Question: Is it true thatT (f(j+1)) ≤ T (f(j))that is, the solution can only improve with more iterations?Answer: Yes. The value of αjis chosen as the value of α that minimizesthe expressionT ((1 − α)Φ(j)+ αf(j)).On the other hand, with α = 1 this expression gives T (f(j)), which is thedelay in the previous iteration. Since with the minimizing α the delaycannot be larger that for any particular α, therefore, T (f(j+1)) ≤ T (f(j))holds.• Question: Can we simply choose f(0)= 0 for the initial feasible flow?Answer: No. The zero flow f(0)= 0 would not be feasible, since it doesnot satisfy the traffic demand.• Question: Is it true that if we choose the
View Full Document
Unlocking...