ISSN 0735-2727, Radioelectronics and Communications Systems, 2008, Vol. 51, No. 5, pp. 239–246. © Allerton Press, Inc., 2008. Original Russian Text © V.I. Parfenov, S.V. Zolotarev, 2008, published in Izv. Vyssh. Uchebn. Zaved., Radioelektron., 2008, Vol. 51, No. 5, pp. 12–22.
Algorithm of Conditional Minimization of the Goal Function for Optimal Routing in Information Networks V. I. Parfenov and S. V. Zolotarev Voronezh University, Voronezh, Russia Received in final form August 9, 2007
Abstract—A new algorithm has been proposed for solving the optimal routing problem. This algorithm is based on applying the Kirchhoff laws to information networks and does not require the mandatory use of derivatives of the goal function making it quite convenient for distributed realizations. The algorithm convergence is substantiated by drawing an analogy between information and electric networks. On the basis of a case study of the network it was shown that its speed is tens of times as high as that of the flow deviation algorithm. It was shown that theoretical labor intensity of implementing this method is substantially less than that of the algorithms based on finding the shortest routes, since the cyclic part of this algorithm does not contain laborious logical operations. DOI: 10.3103/S0735272708050026
The routing problems exist in all kinds of networks: packet and message switching networks and digital circuit switching networks. Actual realization of the routing algorithm tangibly depends on special features of the network, but generally, a fairly similar mathematical apparatus is applied for different networks. This apparatus consists of the shortest route algorithms and the flow algorithms applied to flow models of networks based on intensities of the traffic entering communication lines. In flow models a tacit assumption is made to the effect that traffic statistics varies with time very slowly. Such assumption is valid when the specified statistics varies very slowly as compared with the average time required for reducing queues in the network and when flows in the lines are measured by temporal averaging. Under routing algorithm we understand the rule which determines the choice of communication line for transmitting a data block (message or packet) in each node of the data network. Under fixed (unramified) routing we shall understand such routing procedure, where a single route is used to transmit data from the source node to the destination node (sender-receiver pair, SR-pair). If the routing procedure allows more than one route to be used, it is called alternative ramified or multipath. It is obvious that generally the alternative routing is preferable as compared with the fixed one, because it ensures a better use of network resources. Let us consider the following flow model of information network (IN) with alternative routing of messages. IN consists of N switching nodes and M communication lines. The traffic entering the network consists of messages having the equal priority; it generates a stochastic flow with average value gp [messages/sec] for messages following path p. Let us designate the total external traffic by the formula g=
å å g p,
wÎW pÎPw
where Pw is the set of oriented paths for SR-pair w = (i, j), where node i is sender, while node j is receiver of messages and W is the number of SR-pairs in the network. Each communications circuit consists of a single unidirectional communications channel with capacity dkl [byte/sec], where (k, l) is communication line between nodes k and l. The average length of message [bytes] is equal to 1/m. The total flow passing through the line (i, j) [messages/sec] will be equal to f ij =
å
îver all paths p, ñîntaining (i , j ) 239
g p.
240
PARFENOV, ZOLOTAREV
If the set of flows in communication lines is designated as f ={ f ij }; i, j =1,2,..., N ; then the expression having the form D( f ) =
å D ij ( f ij ),
(i , j )
where each function D ij ( f ij ) is monotonically increasing, is often selected as a goal function used during optimization. Let us define optimal routing problem as follows: To minimize function D ( f ) under the following constraints 0 £ f ij < md ij ; g=
i, j =1,2,..., N ,
(1)
å å g p , g p ³ 0; p Î Pw , w ÎW .
wÎW pÎPw
In the case of alternative routing this problem is referred to the class of multiproduct problems with convex goal function and a convex set of constraints. Hence, this problem features the existence of a single local minimum, which is global one. Many computation methods were developed [1, 2] that are suitable for finding this minimum. The most common method for solving this problem is the flow deviation method proposed in paper [1]. This algorithm is a particular case of the so-called Frank–Wolfe method [3] designed for solving more general problems of nonlinear programming. The flow deviation algorithm is based on the following two properties of optimal solution of the problem. PROPERTY 1 The set of multiproduct flows in communication lines f is a convex polyhedron, the end points of which are so-called “extreme flows” that are determined in accordance with the principle of the shortest paths. For each SR-pair the shortest routes calculated under conditions of the arbitrary assignment of “weights” of communication lines are considered as optimal routes. Each such assignment corresponds to an extreme flow and vice versa. In paper [1] it was shown that any multiproduct flow in communication lines f can be presented as a convex combination of “extreme” flows. PROPERTY 2 For the specified set of multiproduct flows in communication lines f we shall determine the “weight” of communication line (k, l) as a partial derivative of the goal function in terms of variable fkl, i.e., ¶D / ¶f kl . Let j be a flow along the shortest routes determined in accordance with “weights” ¶D / ¶f kl . Next, let f ¢ = f + a (j - f ) be a convex combination of j and f that minimizes function D(a ). If D ( f ¢ ) = D ( f ), then f is optimal flow. Let us prove the validity of choice of “weights” ¶D / ¶f kl and the algorithm convergence. Let f be an optimal solution. This means that any deviation from f leads to higher values of the goal function, i.e., for any such deviation of f ¢ with respect to f, where f ¢ is admissible multiproduct flow, the following inequality will be valid: D( f ¢) ³ D( f ) .
(2)
Let us consider the difference: D ( f ¢ ) - D ( f ) = dD. For a << 1: N N
D ( f ¢ ) - D ( f ) » å å ( f kl¢ - f kl ) k =1 l =1
N N ¶D ¶D . = a å å (j kl - f kl ) ¶f kl ¶ f kl k =1 l =1
Then from inequality (2) it follows that RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
Vol. 51
No. 5
2008
ALGORITHM OF CONDITIONAL MINIMIZATION OF THE GOAL FUNCTION
¶D
N N
å å (j kl - f kl ) ¶f
k =1 l =1
241
³ 0.
kl
Besides, in the optimum point this inequality turns into equality. Thus, for ensuring that f ¢ approaches ¶D N N the optimal solution as a result of iterations, it is necessary to minimize the value åk =1 ål =1j kl ³ 0, ¶f kl where j is the flow along the shortest routes determined in accordance with “weights” wkl = ¶ / ¶f kl . Theoretical labor intensity of the flow deviation algorithm is determined by stages where the search for the shortest routes is conducted among all the pairs of nodes. For example, if the Floyd algorithm is used, the labor intensity amounts to O ( N 3 ). In the limit the flow deviation algorithm reduces the value of the goal function to minimum, however in the course of approaching this optimum the convergence rate becomes very small. Let us consider another method of finding a solution of optimal routing problem. In order to substantiate (at the qualitative level) its convergence, it is expedient to use the concept of network cybernetic power [4] N N
P = å å l ij Tij , 2
(3)
i =1 j =1
where Tij represents the time delay of packets present in the (i, j) communication line, while lij is the value of flow passing through this line. Let us present the goal function D ( f ) in the form N N
D ( f ) = å å f ij i =1 j =1
2
D ij ( f ij ) 2 f ij
N N
= å å f ij z ij ( f ij ). 2
(4)
i =1 j =1
From expressions (3) and (4) it can be seen that any convex goal function having the form N N D ( f ) = åi =1 å j =1 D ij ( f ij ) can be always presented in the form of cybernetic power of the network consisting of communication lines, where time delays of the “weight” of packets are determined by the formula z ij ( f ij ) = D ij ( f ij ) / f ij2 . In this case f ij represents the value of total flow passing through line (i, j). Let us introduce an auxiliary function of one variable g ( x | a ), where a is parameter: N N
2 g ( f ¢| f ) = å å ( f ij¢ ) z ij ( f ij ),
(5)
i =1 j =1
where f ¢ = f + a (j - f ) is convex combination of admissible flows j and f. The flow shall be called admissible, if it satisfies constraints (1). The set of admissible flows passing through communication lines will be designated as F. Then, if f is admissible flow, f Î F. Under relationship (5) we can understand the conditional power of the network, where the flow distribution is specified by vector f, when “weights” of communication lines z (f) are assumed constant (independent of flow f ¢ passing through them), i.e., flows f play the part of parameters. Let f * be the vector of optimal flows. Then, for any admissible flow f ¢ the following inequality will be satisfied * D ( f ¢ ) ³ D ( f ).
(6)
From (5) it follows that for any admissible flow x Î F the equality D(x) = g(x|x) is satisfied that allows us to rewrite expression (6) in the form g ( f ¢| f ¢ ) ³ g ( f * | f * ). The last inequality is a particular case of more general principle: for two arbitrary flows f ¢, f Î F the following expression is valid: RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
Vol. 51
No. 5
2008
242
PARFENOV, ZOLOTAREV
g ( f ¢| f ) ³ g ( f * | f * ), besides, equality in this case occurs when f ¢ = f = f * . This principle can be easily explained by the fact that minimum of the conditional power is achieved then and only then, when the network flows are optimally distributed. Any deviation from the optimal distribution brings about an increase of the conditional network power. Hence, the problem of finding optimal solution is reduced to finding the minimum of conditional power (5). This problem is referred to the class of iterative algorithms for solving the problem of optimal routing. The main iteration of this algorithm can be presented by the following relationship: * f : = f + a (j - f ),
where a * is such size of step that minimizes function D [ f + a (j - f )] for all values a Î [0, 1]. For the optimal size of step a * we shall use the method proposed in paper [5] that yields the following relationship ì dD ij ( f ij ) ü ï ï j ( f ) å ij ij df ïï ï ij i, j ï . a * = min {D [ f + a (j - f )]} = min í1, ý 2 a Î[ 0,1] d D f ( ) ï ij ij ï å (j ij - f ij ) 2 ï ï 2 df ij i, j ïþ ïî
(7)
Given the use of a flow model of the network we shall draw an analogy (well justified) between the information network and electric network that has the same structure (topology). Currents in electric networks are always distributed in such way that the total power released in network elements would be minimal. Then, we can speak that the conditional power of network g (j | f ) that is an analogue of the electric power will have its minimum value when vector j satisfies the Kirchhoff laws, i.e. when the information flows are distributed in such way as electric currents. For information network the first Kirchhoff laws can be defined as follows: algebraic sum of flows coming into an arbitrary node of the network and flowing out of it is equal to zero:
å å j ij = 0. i
(8)
j
The first Kirchhoff law ensures the condition of flow conservation in the network. The second Kirchhoff law for IN can be defined as follows: algebraic sum of the number of packets along any closed loop of the information network is equal to zero, i.e.
å å j ij z ij ( f ij ) = 0, i
(9)
j
where values z ij ( f ij ) = D ij ( f ij ) / f ij2 can be interpreted as cybernetic resistances (in terms of time) of communication lines (analogues of electric resistances). Flows j found in accordance with relationships (8) and (9) as well as power g (j | f ) will be called conditionally optimal (for the given f ). Let us rewrite the expression for conditional power (5) in the form: N N
g (a | f ) = å å [ f ij + a (j ij - f ij )]2 z ij ( f ij ); a Î [0,1]. i =1 j =1
RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
Vol. 51
No. 5
2008
ALGORITHM OF CONDITIONAL MINIMIZATION OF THE GOAL FUNCTION
243
It can be shown that if j is conditionally optimal flow, then g (a | f ) is a monotonically decreasing quadratic function a Î [0, 1], i.e., value g (0 | f ) = D ( f ) is its maximum, while g (1| f ) = g (j | f ) is its minimum. That is why direction D = j - f is the direction of descent for function g (a | f ); this means that for any a Î [0, 1] the following inequality is satisfied: ¶g (a | f ) £ 0. ¶a The fact that on the basis of laws (7) and (8) we can always find conditionally optimal flows j specifying the direction of descent for conditional power g ( f + a (j - f )| f ), indicates the potential possibility of finding the minimum of conditional power that, in its turn, proves the convergence of the proposed optimization method since the minimum of conditional power coincides with the optimal value of goal function D ( f * ). Thus, the procedure for finding the flow vector f : = f + a * (j - f ) at each iteration consists of two stages. At the first stage we determine the direction of descent D = j - f of conditional power of the network g ( f + a (j - f )| f ). Hence, we need to determine the conditionally optimal vector of flows j satisfying relationships (8) and (9). At the second stage we determine optimal step a * by using relationship (7). A model of the algorithm implementing the proposed method of network optimization is presented below. (Hereinafter it will be called “conditional minimization algorithm”). Step 1. To carry out the analysis of IN on the basis of laws (8), (9) and derive the analytic expression for finding conditionally optimal vector of flows j = j [ z ( f )] under an assumption that the network topology is time invariable. Step 2. To initialize “weights” of communication lines z ij : z ij =1 / (md ij );
i, j =1,2,.., N .
If any data about capacities of the communication lines dij is not available in the problem specification, the “weights” of communication lines are initialized by the formula: 0 0 2 z ij = D ij ( f ij ) / ( f ij ) ; i, j =1,2,.., N ,
where f 0 is an arbitrary admissible flow. Step 3. Using “weights” of communication lines zij, it is necessary to determine the conditionally optimal flows jij; i, j = 1, 2, …, N by using relationship j = j [ z ( f )] obtained at the first step of the algorithm. Step 4. To distribute flows in accordance with the conditionally optimal flows determined: f ij = j ij ; i, j =1,2,.., N . Step 5. To calculate the value of the goal function: D g1( f ) = D ( f ). Step 6. To determine the weight of communication line z ij ( f ij ) = D ij ( f ij ) / f ij2 ; i, j =1,2,.., N . Step 7. Using the known relationship j = j [ z ( f )], it is necessary to determine the conditionally optimal flows jij; i, j = 1, 2, …, N. Step 8. To determine such step size a * that satisfies the relationship: a * = min D [ f + a (j - f )] . a Î[ 0,1]
Step 9. To distribute the flows in accordance with the following formula:
RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
Vol. 51
No. 5
2008
244
PARFENOV, ZOLOTAREV
Fig. 1.
Table 1 Iteration (number) k
0
10
20
30
40
50
60
f1
0.4
0.4593
0.4702
0.4795
0.4866
0.4917
0.4950
f2
0.3
0.4345
0.4562
0.4717
0.4823
0.4893
0.4938
f3
0.3
0.1061
0.0735
0.0490
0.0310
0.0189
0.0110
0.2945
0.2588
0.2553
0.2532
0.2518
0.2510
0.2506
Goal function D ( f )
* f : = f + a (j - f ).
Step 10. To compute a new value of the goal function: D g2 : = D ( f ). Step 11. If | D g2 - D g1| £ e, then STOP (terminate the operation of the algorithm), else assign D g1:= D g2 and jump to step 6. It should be noted that this algorithm implies admissibility of external flows entering the network; this means a priori that the specified flows should not cause overloading of the network. If this condition is satisfied, the algorithm makes it possible to obtain asymptotically exact solution of the problem of optimal alternative routing. We shall consider now a specific example of the algorithm operation. Given is the network (Fig. 1) consisting of two nodes connected with one another by three communication lines with the corresponding flows f1, f2 and f3 that satisfy the constraints: f = f 1 + f 2 + f 3 = 1;
f 1 , f 2 , f 3 ³ 0.
The network goal function is presented by the following expression: D ( f ) = 0 .5( f 12 + f 22 + 0 .1 f 32 ) + 0 .55 f 3 . The solution of this problem by the flow deviation method was considered in paper [5], where also were presented the results of analysis shown in Table 1. The optimal solution of the problem is vector f * = (1 / 2,1 / 2,0). In this case, the optimal value of the goal function is equal to D ( f * ) = 0.25. From the table it can be seen that as we approach optimal solution, the flow deviation method slows down. Let us solve the specified problem by using the conditional minimization algorithm. First, we must specify threshold e. Let e = 0.2506 – 0.25 = 0.0006. This threshold corresponds to 320 iterations of the flow deviation algorithm. In accordance with the first step of the algorithm we shall find the relationship of conditionally optimal flows ji in communication lines as a function of “weights” z i = z i ( f i ) of communication lines. Let us write down the first Kirchhoff law for the node-sender: RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
Vol. 51
No. 5
2008
ALGORITHM OF CONDITIONAL MINIMIZATION OF THE GOAL FUNCTION
245
Table 2 Iteration (number) k
0
1
2
3
4
f1
0.4
0.44141
0.47497
0.48892
0.49503
f2
0.3
0.44141
0.47497
0.48892
0.49503
f3
0.3
0.11719
0.05007
0.02215
0.00993
Goal function D ( f )
0.29450
0.25998
0.25326
0.25125
0.25053
Accuracy e = D ( f ) - D ( f * )
0.04450
0.00998
0.00326
0.00125
0.00053
j 1 + j 2 + j 3 = 1.
(10)
The application of the second Kirchhoff law to this network enables us to obtain two more equations: j 1 z 1 - j 2 z 2 = 0; j 1 z 1 - j 3 z 3 = 0.
(11)
Solving the system of equations (10) and (11) we obtain the desired relationships: j1 =
1 1 + z1 / z 2 + z1 / z 3
; j2 =
1 1 + z 2 / z1 + z 2 / z 3
;
j3 =
1 1 + z 3 / z1 + z 3 / z 2
.
(12)
Now, let us determine the analytical expression for “weights” z i = z i ( f i ) required for the execution of the second and sixth steps of the algorithm. To this end, let us present the goal function in the form: 2
2
2
D ( f ) = 0 .5 f 1 + 0 .5 f 2 + (0 .05 f 3 + 0 .55 f 3 ) = D1( f 1 ) + D 2 ( f 2 ) + D 3 ( f 3 ), where D1( f 1 ) = 0 .5 f 12 , D 2 ( f 2 ) = 0 .5 f 22 , and D 3 ( f 3 ) = 0 .05 f 32 + 0 .55 f 3 . Thus, we obtain analytical expressions for “weights” of the communication lines: 2
z 1( f 1 ) = D1( f 1 ) / f 1 = 0 .5,
2
z 2 ( f 2 ) = D 2 ( f 2 ) / f 2 = 0 .5,
z 3 ( f 3 ) = D 3 ( f 3 ) / f 32 = 0 .05 + 0 .55 / f 3 .
(13)
Next, we shall determine the order of finding the optimal step of iteration a * that is implemented at the eighth step of the algorithm. It can be shown that in our case the step size a, which allows us to achieve the minimum of the goal function, is computed by the formula: f (j - f 1 ) + f 2 (j 2 - f 2 ) + (0 .1 f 3 + 0 .55)(j 3 - f 3 ) . a =- 1 1 2 2 2 (j 1 - f 1 ) + (j 2 - f 2 ) + 0 .1(j 3 - f 3 ) Then the optimal step size in accordance with relationship (7) will be *
a = min{1, a } .
RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
(14)
Vol. 51
No. 5
2008
246
PARFENOV, ZOLOTAREV
Using relationships (12)–(14) the conditional minimization algorithm was realized to the specified accuracy of e = 0.0006 in the environment of Matchcad 2001 Professional; the results obtained are presented in Table 2. From the comparison of Table 1 and Table 2 it can be seen that for the specified accuracy (sufficiently high) the conditional minimization algorithm uses much smaller number of iterations (about 100 times less) than the flow deviation algorithm. Under theoretical labour intensity of the algorithm we shall understand the approximate number of logical operations needed for its realization. Under total labour intensity of the algorithm realization we shall understand the sum of theoretical labour intensity and the computational efforts required for executing arithmetic instructions. The cyclic part of the conditional minimization algorithm is formed by steps 6–11. The total labour intensity of implementing this part is determined by computational efforts of executing arithmetic instructions during calculation of values j, z ( f ), a * and the elementary operation of finding the minimum of two numbers at step 8, i.e., there are nowhere in evidence any other logical operations such as those found in the flow deviation algorithm at the stage of determining the shortest paths. This is an advantage of this method. The main part of the theoretical labour intensity of the conditional minimization algorithm represents the network analysis conducted at the first step. The first step of the algorithm can be executed by using the tensor analysis, the application of which may be highly effective for networks with strong connectivity of switching nodes. The tensor method of network analysis, first proposed in paper [6] for analysis and synthesis of electric networks, and later extended to information networks [4], is the most general technique suitable for implementing the procedure of finding conditionally optimal flows. It can be shown that in this case the theoretical labour intensity of executing the first step involves generation of the transformation matrices and amounts to O [ M ´ ( M - n )], where n is the number of linearly independent loops in the network, M is the number of communication lines. This study did not include the comparison of the proposed algorithm with gradient algorithms [2] of solving the problems of optimal routing that are faster than the flow deviation algorithm. It is obvious, however, that the conditional minimization algorithm is simpler and more suitable for distributed realizations, because it does not require using derivatives of the goal function. This can be extremely convenient for practical applications of the algorithm. However, in this case we must use another technique of choosing the step of iterations a * instead of formula (7), since it contains the first and second derivatives of the goal function. REFERENCES 1. L. Fratta, M. Gerla, and L. Kleinrock, “The Flow Deviation Method: An Approach to Store and Forward Communication Network Design,” Networks 3, No. 2, 97 (1973). 2. M. Schwartz and C. K. Cheung, “The Gradient Projection Algorithm for Multiple Routing in Message–Switched Networks,” IEEE Trans. Commun. 25, 100 (1976). 3. M. Frank and P. Wolfe, “An Algorithm for Quadratic Programming,” Naval Research Logistic Quarterly, No. 3, 95 (1956). 4. I. I. Pasechnikov, Methodology of Analysis and Synthesis of Information Networks with Maximum Load (Mashinostroenie-1, Moscow, 2004) [in Russian]. 5. D. Bertsekas and R. Gallager, Data Networks (Mir, Moscow, 1989) [Russian translation]. 6. G. Kron, Tensor Analysis of Networks (Sov. Radio, Moscow, 1978) [Russian translation, ed. by L. T. Kuzina and P. G. Kuznetsova].
RADIOELECTRONICS
AND
COMMUNICATIONS
SYSTEMS
Vol. 51
No. 5
2008
