The article considers the problem of managing the reserve of capacity of arcs, which is relevant for the distribution of flows and designing reliable communication networks with discrete parameters and a constraint on flows delay time or average load factor of the network arcs. An algorithm for the approximate solution of the problem for the case of linear functions for the cost of arcs is proposed and the results of its experimental study on a network containing 1000 nodes and 4000 arcs are presented. The results of the experiment showed the sufficient accuracy and speed of the proposed algorithm, which allows us to assert of its practical applicability for engineering calculations on the large-dimensional networks.
The article is an addition to the work [1], in which the Problem of Choosing the Capacity of Arcs (PCCA) for communication network from a given set of discrete integer values with constraint on flows delay time was considered. Delays of flows tkl on arcs are defined as tkl = fkl / (wkl − fkl ) , kl E , and the constraint on the delay time Here fkl Z + — fixed arc flow value for kl E , E — set of arcs of network, wkl Z + — bandwidth capacity of arc kl E , Tmax — the maximum of flows delay time in network, U = uij
ijS from a node i to a node j , S — total flow in network, uij Z + — value of the flow
— set of pairs of indexes corresponding nodes in the network. When approaching the magnitude of the flow on the arcs to their carrying capacity, the delay increases and, therefore, network congestion can occur.
The essence of the problem is for fixed flows it is necessary to choose the throughput capacities of arcs from a given set of integers so that the constraint on the delay time of flows is fulfilled and the minimum of some objective function is achieved. For the design of data transmission networks, PCCA was studied in detail in [2-5]. This problem also arises in transport networks when distributing flows according to the criterion of the minimum cost of the network and a given restriction on the delay time of flows [6].
A Problem of Managing the Reserve of Capacity of Arcs (PMRCA) is to parametrically solve a PCCA problem, in which as a variable parameter are selected values Tmax with the given sampling step. By controlling the parameter Tmax for maximum delay, the data network administrator or the transport network manager can provide the required reserve for the bandwidth capacity of the communication channels or the carrying capacity of vehicles at predicted fluctuations of values of flows on a given time of intervals. A decrease in the parameter Tmax (increase in the reserve) leads to a rise in the cost of the network, but reduces the probability of redistribution of flows and technical re-equipment of communication channels or fleet of vehicles at increasing flows and a threat of emergence overloads in the network. An increase in the parameter Tmax makes it possible to reduce the capacity of communication channels or the carrying capacity of vehicles and the cost of the network, but increases the risk of redistributing flows and upgrading the network. As a quantitative measure of reserve capacity can be taken as the average load factor of the network arcs.
Topical issues are the affiliation of PCCA and PMRCA to the class of NP-hard problems, and the development of approximate time-polynomial algorithms. The article provides an example of a parametric PCCA solution on a network containing 1000 nodes and 4000 arcs, which clearly demonstrates the methodological approach to solve PMRCA and to the practical choice of required reserve capacity of arcs for the communication network. 2
The formulation and algorithm of solving the problem We consider a direct connected network G(N , E) with a set of nodes N , n = N and a set of arcs E , e = E . In network for each direct arc kl , ( k l ) exist back arc lk , ( l k ). An arc represents a switched communication line in a data network or a vehicle route, the final nodes of which coincide with the initial and final node of the arc. The network may contain loops and parallel arcs, since cyclic and repeating communication lines and communication lines with the same final nodes are allowed. An integer flow matrix is given on the network U = uij nn . Let wkl , kl E — sought-for a bandwidth capacity of arcs of the network in transport blocks, wkl {w1 , w2 , ..., w } , wi , i = 1, — ascending positive integers; dkl R+ , kl E — arcs lengths; Ckl (wkl , dkl ) R+ , kl E — discrete values cost of arcs, such that Ckl (wi , dkl ) Ckl (wi+1 , dkl ) , i = 1, −1 ; fkl = uikjl , kl E — fixed total flows in ijS transport blocks, a flowing along the arcs of the network, where uikjl — is the flow of transport blocks from i to j , which passes along arc kl .
It is required to find the minimum value of the network cost function min Ckl (wkl , dkl ) , wkl {w1 , w2 , ..., w } wkl klE s.t.
1
fkl Tmax , wkl fkl , kl E
U klE wkl − fkl for the parameter of selected values Tmax , that vary within the following limits 1 fkl Tmax 1 fkl ,
U klE w − fkl U klE wkl,min − fkl
where wkl,min = min wi fkl , i = 1, .
(
e min cij xij
i=1 j=1 1 e U i=1 j=1 tij xij Tmax , xij = 1 , i = 1, e , j=1 xij {0,1} .
To estimate the bandwidth reserve for each solution wkl (Tmax ) {w1 , w2 , ..., w } , kl E , we will calculate the average load factor of arcs for the network ALF = 1 fkl .
(
Note that problem (
Here, the required throughputs wij correspond to the optimal solution xi*j to the
problem (
It is easy to see that any individual problem formulated in the form of (
For the knapsack problem with multi-choice (
Despite the existence of exact pseudo-polynomial algorithms, their application for the parametric solution of the PCCA problem is not justified due to the great time complexity of the algorithms.
So, for example, the time complexity of the FPTAS algorithm for solving the
classical 0-1 MCKP problem is O(e2 / ) [9].Therefore, in [1], for solving NP-hard
problems (
The first algorithm uses the Lagrange multiplier method, which allows one to
analytically solve a relaxed problem and obtain an exact continuous solution. The second
algorithm enumerates the solutions, narrowing the range of feasible solutions at each
iteration, and can be used for any monotonically non-decreasing cost of arcs with an
increase in their throughput. It can be applied both to the initial statement of the
problem, and to the statement in the form (
We consider problem (
Ckl (wkl , dkl ) = ck0l + c1kl wkl , kl E
(
L = ckl (wkl , dkl ) + fkl
klE U wkl − fkl where — is the Lagrange multiplier. Equating the partial derivatives of this function to zero, we obtain L wkl = c1kl −
fkl U (wkl − fkl )2 = 0 where from wkl = fkl + fk1l . Substituting the values wkl in the original equality constraint, we U c
kl obtain Tmax = 1 / U klE fkl / (wkl − fkl ) = klE c1klUfkl and = 1 / Tmax klE cU1kl fkl . Substituting the value of the multiplier in the expression for wkl , we finally obtain the values wk*l for the optimal capacity of communication lines or after obvious transformations wk*l = fkl +
1 Tmax
Ufkcl 1 kl rsE c1rs frs ,
U wk*l = fkl +
fkl UTmax rsE
c1rs frs c1kl fkl .
(
klE UTmax klE Note that in practice for data transmission networks and transport networks, capacity, as a rule, should be the same for the forward kl and reverse lk directions. Therefore, at practical solution to the problem, two oriented communication lines kl and lk are replaced with one non-oriented communication line kl, (k l) and selected fkl = max{ fkl , flk } .
The approximation algorithm allows one to quickly get into the neighborhood of continuous points optimum of wk*l and find an approximate discrete solution wkl . The idea of the algorithm is as follows.
Suppose that for all arcs kl E the coefficients ck0l , c1kl of the linear dependence
(
Knowing the coefficients c1kl = tg (Fig. 1) and the values of fkl , through formula
(
We present a general scheme of the “greedy” algorithm for the parametric solution
of problem (
AP Algorithm
1. For each arc kl E and a given range of throughputs wkl {w1 , w2 , ..., w } ,
through the least-squares method, it is needed to approximate a discrete cost
Ckl (wkl , dkl ) with linear functions. We determine the coefficients ck0l , c1kl in (
2. Through the formula (
3. We calculate wk*l , Cmin according to (
* 4. From wkl {w1 , w2 , ..., w } for each arc kl E we select the closest to wk*l the permissible values wkjl , j = 1, , such as fkl wkjl wk*l . If wkjl fkl , then as wkjl , we choose the nearest larger value of wkjl fkl (it may be, that wkjl wk*l ). If fkl = 0 , then it is accepted that arc kl does not exist.
5. In the neighborhood of the point wk*l for each arc, we find the values ck*l = ckl / tkl , where ckl = ckl (wkjl+1 ) − ckl (wkjl ) , tkl = fkl / (wkjl − fkl ) − fkl / (wkjl+1 − fkl ) , j {1, ..., −1} .
6. We arrange all the arcs kl E in ascending order of values ck*l and get a set E* = {(k, l)1 , (k, l)2 , ..., (k, l)e } . The reason for such an ordering is for all arcs ckl (wkjl ) ckl (wkjl+1 ) , and tkl (wkjl ) = fkl / (wkjl − fkl ) tkl (wkjl+1 ) = fkl / (wkjl+1 − fkl ) . We set the initial value of the arcs counter i = 0 .
7. Let i i +1. We select an arc (k, l)i from the set E * and go to step 8.
j 8. We increase throughput w(k,l)i for the arc (k, l)i to the nearest larger value from the discrete row {w1 , w2 , ..., w } , i.e. choose such w(jk+,1l)i , that w(jk+,1l)i wk*l w(k,l)i , j j {1, ..., −1} . We recalculate the value tav taking into account an increase in throughput of the arc (k, l)i . If tav Tmax , then go to step 9. Otherwise, go to step 7 to increase the counter of arcs. The value of the counter of arcs i cannot exceed the value number of arcs e , since the condition tav Tmax will be guaranteed to be satisfied in the cycle for i due to the fact that for all arcs may turn out to be w(jk+,1l)i wk*l . 9.
The found values
j
w(k,l)i ,
j {1, ..., } ,
i {1, ..., e}
or
wkl (Tmax ) {w1 , w2 , ..., w } , kl E , are an approximate solution to the problem for
the current parameter value Tmax . Through the formula (
10. If the choice of the current parameter value Tmax is completed, there is the end of the algorithm. Otherwise, we change the parameter value Tmax to the selected magnitude and go to step 3.
The time complexity of the AP algorithm is O(e 2 + e + Me log e + K1e) and is mainly determined by the time complexity of the algorithm for approximating the cost of arcs with linear functions and of the sorting algorithm, where M — is the number of values Tmax with a given sampling step, K1 — is some constant.
ckl (wkl ) ckl (wkl ) ckl (wkjl+1 ) ckl (wkjl ) ckl (w1kl ) w1kl … wkjl wk*l w j+1 kl wkl
Results of the experimental solution of the problem The problem was solved by using an example of a network with n = 1000 nodes and e = 4000 arcs, generated by a pseudo random number sensor. The lengths of arcs dkl , kl E ranged from 20 to 50 km, and values of flows uij , i, j = 1, n from 1 to 2 transport blocks. The fkl , kl E values were obtained by distributing all flows along the shortest paths using the two-criteria lexicographic algorithm [18]. The throughput of arcs was selected from the set {5, 10, 15, 20, ...} with a sampling step of 5 units. The cost of arcs for a given set of throughputs of arcs was calculated by the formula Ckl (wkl , dkl ) = k0j + k1j dkl , j = 1, 2, ... , kl E . For linear functions, the coefficients k01 k02 ... and k11 k12 ... were chosen from the sets {0, 0, 0, 0, 0, ...} and {5, 10, 15, 20, ...}. The number of values in the sets for wkl , k0j , k1j was determined depending on the maximum flow along the arc max fkl , kl E , the sampling step of the throughput capacities of the arcs, and the initial value Tmax . If for the current value of Tmax , it turned out to be w wk*l , the set {w1 , w2 , ..., w } can be automatically expanded to the value w = wk*l 5 , where 5 — is the rounding sign to a larger integer multiple of 5. The table 1 shows the results of solving the problem when changing constraint at the delay time from Tmax = 0.002 to Tmax = 10.0. For all values of the parameter Tmax , the following are given: Continuous Optimal Solutions, rounded to integers and Approximate Discrete Solutions (AS) in nominal units of cost value; values of the average load factor of arcs for network (ALF); deviations in percent of approximate solution from the continuous optimal solution. which cannot be improved at the further increasing the value of Tmax . It follows that the deviations of discrete optimal and approximate solutions will be even smaller.
The most interesting variants for analyzing and deciding the choice of reserve for the capacity of arcs, are the solutions with numbers 1-12, for which the network cost is significantly reduced (by 308476576 units) and load factor of arcs is increased from 0.39 to 0.91. These variants solutions are clearly shown in Fig. 2.
The same results as in table 1 were obtained, when solving the problem with an approximate algorithm on the basis of the method of sequential analysis for variants, which is given in [1]. However, the time complexity of this algorithm is several orders of magnitude greater, and to calculate each solution for the given values Tmax , it took from 5 to 12 seconds on a PC with a clock frequency of 2.66 GHz. The AP algorithm coped with such tasks in a split second.
The conducted experimental studies showed the sufficient accuracy and speed of the AP algorithm, which in the most cases allows it to be used for engineering calculations on networks containing more than 1000 nodes and 4000 arcs. The PMRCA solution can be useful in solving the practical problems of flow distribution and designing reliable communication networks with discrete parameters and a constraint on the time delay of flows or on the average load factor of arcs of network [19, 20].
The experimental results were obtained on a dual-core PC with a clock frequency of 2.66 GHz and 2 GB RAM under Windows XP. All programs are written in software environment Microsoft Developer Visual Studio.
Conclusion The article formulates the problem of managing the reserve of capacity arcs in a communication network with discrete parameters when changing the constrain on the delay time of flows. An approximate polynomial algorithm for solving the problem for the case of linear of arcs cost’s functions is proposed and the results of its experimental study are presented. The experimental results allow us to state the practical applicability of the algorithm for solving the problem on large-dimensional networks containing more than 1000 nodes and 4000 arcs. 15. Mikhalevich, V.S.: Sequential optimization algorithms and their application. I. Cybernetics. No. 1, 45-55 (1965). (In Russian) 16. Mikhalevich, V.S.: Sequential optimization algorithms and their application. II. Cybernetics. No. 2, 85-89 (1965). (In Russian) 17. Mikhalevich, V.S., Volkovich, V.L., Voloshin, A.F., Pozdnyakov, Yu.M.: Algorithms for sequential analysis and screening of options in discrete optimization problems.
Cybernetics. No. 3, 76-85 (1980). (In Russian)
18. Vasyanin, V.A.: A Two-Criterion Lexicographic Algorithm for Finding All Shortest Paths
in Networks. Cybernetics and Systems Analysis. 50(