A Problem of Managing the Reserve of Capacity for the Arcs of a Communication Network Olexander Trofymchuk[0000-0003-3358-6274] , Volodymyr Vasyanin[0000-0003-4046-5243], Liudmyla Ushakova[0000-0002-9020-1329] Institute of Telecommunications and Global Information Space of NAS of Ukraine, 13 Chokolovsky Boulevard, Kyiv, 03186, Ukraine itelua@kv.ukrtel.net, archukr@meta.ua,archukr@i.ua Abstract. The article considers the problem of managing the reserve of capaci- ty of arcs, which is relevant for the distribution of flows and designing reliable communication networks with discrete parameters and a constraint on flows de- lay time or average load factor of the network arcs. An algorithm for the ap- proximate 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 contain- ing 1000 nodes and 4000 arcs are presented. The results of the experiment showed the sufficient accuracy and speed of the proposed algorithm, which al- lows us to assert of its practical applicability for engineering calculations on the large-dimensional networks. Keywords: flows in networks, the reserve of capacity of arcs, time of delay flows, problems of combinatorial optimization 1 Introduction The article is an addition to the work [1], in which the Problem of Choosing the Ca- pacity of Arcs (PCCA) for communication network from a given set of discrete inte- ger values with constraint on flows delay time was considered. Delays of flows t kl on arcs are defined as tkl = f kl / ( wkl − f kl ) , kl  E , and the constraint on the delay time of flows t av in a network has the following form tav = 1/ U   f kl / ( wkl − f kl )  Tmax . klE Here f kl  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 — total flow in network, uij  Z + — value of the flow ijS from a node i to a node j , S — 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 through- put capacities of arcs from a given set of integers so that the constraint on the delay Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). ICST-2020 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 paramet- rically 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 increas- ing flows and a threat of emergence overloads in the network. An increase in the pa- rameter 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 nn . 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; d kl  R + , kl  E — arcs lengths; Ckl ( wkl , d kl )  R + , kl  E — discrete values cost of arcs, such that Ckl ( wi , d kl )  Ckl ( wi +1 , d kl ) , i = 1,  − 1 ; f kl =  uijkl , kl  E — fixed total flows in ijS transport blocks, a flowing along the arcs of the network, where uijkl — 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 , d kl ) , wkl  {w1 , w2 , ..., w } (1) wkl klE s.t. 1 f  kl  Tmax , wkl  f kl , kl  E U  klE wkl − f kl (2) for the parameter of selected values Tmax , that vary within the following limits 1 f kl 1 f kl  U  klE w − f kl  Tmax   U  klE wkl ,min − f kl , (3) where wkl ,min = min wi  f kl , i = 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 1 f kl ALF =  . (4) e klE wkl (Tmax ) Note that problem (1), (2) can be represented as a knapsack problem with Boolean variables and multi-choice (0-1 Multiple-choice Knapsack Problem, 0-1 MCKP), which, as you know, belongs to the class of NP-hard problems [7]. Let cij  R + — discrete values cost of arcs i with capacity wij  {w1 , w2 , ..., w }  Z + and length d i , j = 1,  , i = 1, e ; tij = f i / ( wij − f i ) , wij  f i , j = 1,  , i = 1, e —delays of flows on arcs; f i — flow on the arc i , i = 1, e . Suppose that xij = 1 , if for the arc i the ca- pacity wij is selected, j = 1,  , i = 1, e , and xij = 0 otherwise. We require to find e  min   cij xij (5) i =1 j =1 s.t. 1 e   tij xij  Tmax , U  i =1 j =1 (6)   x = 1 , i = 1, e , j =1 ij (7) xij  {0,1} . (8) * Here, the required throughputs wij correspond to the optimal solution x to the ij problem (5) - (8). It is easy to see that any individual problem formulated in the form of (1), (2) can be transformed in time O (e ) into the corresponding instance of problem (5) - (8). To do this, it is necessary to construct two matrices of size e  , whose rows corre- spond to arcs, the columns — to a set of discrete capacities, and the cost of arcs cij and delays on arcs tij are taken as matrix elements. The converse is also true. For the knapsack problem with multi-choice (5) - (8), there are exact pseudo- polynomial algorithms and Fully Polynomial Time Approximation Scheme (FPTAS) [8, 9]. This means that for them there are algorithms that, polynomial time of the size for the input of the problem and 1 /  make it possible to obtain a (1 +  ) - guaranteed approximate solution, where  is an arbitrarily small positive number. Therefore, to obtain an accurate or guaranteed  -approximate solution to problem (5) - (8), it is possible to use the algorithms described in [8-13]. These algorithms can also be used to solve the problem in statement (1) - (2). 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 clas- sical 0-1 MCKP problem is O (e 2  /  ) [9].Therefore, in [1], for solving NP-hard problems (1), (2) and (5) - (8), two approximate algorithms were proposed on the basis of the approximation of discrete cost functions by linear ones, and on the meth- od of sequential analysis of options, which was first proposed and investigated in the works [14-17]. The first algorithm uses the Lagrange multiplier method, which allows one to ana- lytically 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 prob- lem, and to the statement in the form (5) - (8). We consider problem (1), (2) when it is known, that a given discrete values cost of the arcs Ckl ( wkl , d kl ) can be approximated with a sufficient degree of adequacy by continuous linear functions Ckl ( wkl , d kl ) = ckl0 + c1kl  wkl , kl  E (9) where ckl0 , c1kl — we found approximation coefficients. For linear cost functions, the analytical solution wkl* , Cmin * , which is obtained by the method of Lagrange multipli- ers is known as [2, 3]. We write the Lagrange function  f kl L =  ckl ( wkl , d kl ) + klE U  w kl − f kl where  — is the Lagrange multiplier. Equating the partial derivatives of this func- L  f kl tion to zero, we obtain = c1kl − =0 where from wkl U  ( wkl − f kl ) 2  f kl wkl = f kl + . Substituting the values wkl in the original equality constraint, we U  c1kl c1kl f kl c1kl f kl obtain Tmax = 1/ U   f kl / ( wkl − f kl ) =  and  = 1/ Tmax  . klE klE U klE U Substituting the value of the multiplier in the expression for wkl , we finally obtain the values wkl* for the optimal capacity of communication lines 1 f kl c1rs f rs wkl* = f kl + Tmax  U  c1kl rsE U , or after obvious transformations f kl rs c1rs f rs E w = f kl + * kl . (10) U  Tmax c1 f kl kl The optimal network cost is defined as 1 * Cmin =  c1kl f kl + (  c1kl f kl )2 . (11) klE U  Tmax klE 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 f kl = max{ f kl , f lk } . The approximation algorithm allows one to quickly get into the neighborhood of continuous points optimum of wkl* and find an approximate discrete solution wkl . The idea of the algorithm is as follows. Suppose that for all arcs kl  E the coefficients ckl0 , c1kl of the linear dependence (9) are known. Such coefficients can be obtained for each arc kl of length d kl by linear approximation (for example, by the least squares method) of discrete values cost of the arcs for a number of standard discrete capacity wkl  {w1 , w2 , ..., w } , the same for all arcs. Knowing the coefficients c1kl = tg (Fig. 1) and the values of f kl , through formula (10) you can find the throughput wkl* . Next in the neighborhood of continuous opti- mums wkl* according to a certain procedure, we select the suitable carrying capacity values from a discrete range. We present a general scheme of the “greedy” algorithm for the parametric solution of problem (1), (2) for linear cost functions. 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 , d kl ) with linear functions. We determine the coefficients ckl0 , c1kl in (9). 2. Through the formula (3), we determine the boundaries of the interval of varia- tion of the parameter Tmax . It is arbitrarily to choose the first parameter value Tmax from the interval, for example, starting from its left or right border. 3. We calculate wkl* , Cmin * according to (10) and (11). 4. From wkl  {w1 , w2 , ..., w } for each arc kl  E we select the closest to wkl* the permissible values wklj , j = 1,  , such as f kl  wklj  wkl* . If wklj  f kl , then as wklj , we choose the nearest larger value of wklj  f kl (it may be, that wklj  wkl* ). If f kl = 0 , then it is accepted that arc kl does not exist. 5. In the neighborhood of the point wkl* for each arc, we find the values ckl* = ckl / tkl , where ckl = ckl ( wklj +1 ) − ckl ( wklj ) , tkl = f kl / ( wklj − f kl ) − f kl / ( wklj +1 − f kl ) , j  {1, ...,  − 1} . 6. We arrange all the arcs kl  E in ascending order of values ckl* 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 ( wklj )  ckl ( wklj +1 ) , and tkl ( wklj ) = f kl / ( wklj − f kl )  tkl ( wklj +1 ) = f kl / ( wklj +1 − f kl ) . 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. 8. We increase throughput w(jk ,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  wkl*  w(jk ,l )i , j  {1, ...,  − 1} . We recalculate the value t av 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 satis- fied in the cycle for i due to the fact that for all arcs may turn out to be w(jk+,1l )i  wkl* . 9. The found values w(jk ,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 (4), we calculate the average load factor of the network arcs ALF and the cost of the network AS =  klE Ckl ( wkl , d kl ) . 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 mag- nitude and go to step 3. The time complexity of the AP algorithm is O(e 2 + e + Me log e + K1 e) 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, K 1 — is some constant. ckl ( wkl )  ckl ( wkl ) ckl ( wklj +1 ) ckl ( wklj ) ckl ( w1kl ) w1kl … wklj wkl* wklj +1 … wkl wkl Fig. 1. The cost function of arcs 3 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 d kl , kl  E ranged from 20 to 50 km, and values of flows u ij , i, j = 1, n from 1 to 2 transport blocks. The f kl , 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 , d kl ) = k0j + k1j d kl , 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 , k 0j , k1j was determined depend- ing on the maximum flow along the arc max f kl , 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  wkl* , the set {w1 , w2 , ..., w } can be automatically ex- 5 panded to the value w =  wkl*  , where  — is the rounding sign to a larger inte- 5 ger multiple of 5. The table 1 shows the results of solving the problem when chang- ing 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. Table 1. Results for an experimental study of the dependence for the network cost and the average load factor of arcs on the value Tmax for the AP algorithm № Tmax Continuous Approximate Average Load Deviation from Con- Optimal Solution Factor tinuous Solution of the Arc Optimal Solution, % 1 0,002 702606912 702629696 0,38942969 0,0032 2 0,003 594371712 594391104 0,48080164 0,0033 3 0,004 540254080 540272512 0,54661781 0,0034 4 0,005 507783520 507800512 0,59667718 0,0033 5 0,006 486136480 486152288 0,63623863 0,0033 6 0,007 470674304 470691072 0,66836989 0,0036 7 0,008 459077664 459092352 0,69505483 0,0032 8 0,009 450058080 450074496 0,71761900 0,0036 9 0,01 442842368 442856736 0,73692870 0,0032 10 0,02 410371808 410387264 0,84252059 0,0038 11 0,03 399548288 399564960 0,88708848 0,0042 12 0,04 394136544 394153120 0,91188490 0,0042 13 0,05 390889472 390907136 0,92762768 0,0045 14 0,06 388724768 388742280 0,93870205 0,0045 15 0,07 387178560 387197728 0,94657397 0,0050 16 0,08 386018880 386038144 0,95283246 0,0050 17 0,09 385116928 385137024 0,95748824 0,0052 18 0,1 384395360 384416224 0,96161634 0,0054 19 0,2 381148320 381177888 0,9798876 0,0078 20 0,3 380065952 380102912 0,98587686 0,0097 21 0,4 379524768 379568832 0,98896205 0,0116 22 0,5 379200064 379250464 0,99074137 0,0133 23 0,6 378983616 379040928 0,99179864 0,0151 24 0,7 378828992 378893472 0,99245179 0,0170 25 0,8 378713024 378784000 0,99292845 0,0187 26 0,9 378622816 378700672 0,99332023 0,0206 27 1,0 378550656 378635168 0,99358821 0,0223 28 2,0 378225952 378363360 0,99453980 0,0363 29 3,0 378117728 378303680 0,99463964 0,0492 30 4,0 378063616 378296352 0,99464238 0,0616 31 5,0 378031136 378295712 0,99464256 0,0700 32 6,0 378009472 378295264 0,99464262 0,0756 33 7,0 377994016 378295008 0,99464267 0,0796 34 8,0 377982432 378295008 0,99464267 0,0827 35 9,0 377973408 378295008 0,99464267 0,0851 36 10,0 377966176 378295008 0,99464267 0,0870 As it is visible in table 1, continuous optimal and discrete approximate solutions are differing slightly with a value from 0.0032% to 0.0796%. In a variant of solution 33 at Tmax = 7.0, the lower boundary of the network cost 378295008 is reached, 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 or- ders 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 algo- rithm 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 calcu- lations 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 de- signing 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]. Fig. 2. Change in network cost and load factor of the arcs from Tmax. The values in the AS line is multiplied by 109 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 soft- ware environment Microsoft Developer Visual Studio. 4 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 experi- mental 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. References 1. Trofymchuk, O.M., Vasyanin, V.A.: Choosing the Capacity of Arcs with Constraint on Flow Delay Time. Cybernetics and Systems Analysis. 55(4), 561-569 (2019). doi 10.1007/s10559-019-00165-0 2. Kleinrock, L.: Queueuing Systems. Volume II: Computer Applications. John Wiley & Sons, (1976) 3. Bertsekas, D., Gallager, R.: Data Networks (2nd Edition). Prentice-Hall, Inc., (1992) 4. Zaichenko, Yu.P.: The task of designing the structure of distributed computing networks. Automation. No. 4, 35-44 (1981). (In Russian) 5. Zaichenko, E.YU.: A set of models and algorithms for optimizing the characteristics of networks with MPLS technology. System research and information technology. No. 4, 58- 71 (2007). (In Russian) 6. Vasyanin, V.A.: Problem of Distribution and Routing of Transport Blocks with Mixed At- tachments and Its Decomposition. Journal of Automation and Information Sciences. 47(2), 56-69 (2015). doi 10.1615/JAutomatInfScien.v47.i2.60 7. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman & Co. New York, NY, USA, (1979) 8. Martelo, S., Toth, P.: Knapsack problems: algorithms and computer implementa- tions. Great Britain: Wiley, (1990) 9. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer-Verlag Berlin Hei- delberg, (2004). doi 10.1007/978-3-540-24777-7 10. Bansal, M.S., Venkaiah, V.Ch.: Improved Fully Polynomial time Approximation Scheme for the 0-1 Multiple-choice Knapsack Problem. Technical Report Number: IIIT- H/TR/2004/003, IIIT, Hyderabad, India, (2004) 11. Suri, B., Bordoloi, U.D., Eles, P.: A Scalable GPU-based Approach to Accelerate the Mul- tiple-Choice Knapsack Problem. Design, Automation & Test in Europe Conference & Ex- hibition (DATE), (2012). http://ieeexplore.ieee.org/document/6176665/ 12. Rhee, D.: Faster fully polynomial approximation schemes for Knapsack problems. Massa- chusetts Institute of Technology. Operations Research Center, (2015). http://hdl.handle.net/1721.1/98564 13. Bednarczuk, E.M., Miroforidis, J., Pyzel, P.: A multi-criteria approach to approximate so- lution of multiple-choice knapsack problem, (2017).https: //arxiv.org/abs/1712.06723 14. Mikhalevich, V.S., Shor, N.Z .: Numerical solutions of multivariate problems by the meth- od of sequential analysis of options. In the book: Scientific and methodological materials of the economic-mathematical seminar, Moscow, Issue 1, 15-42 (1962). (Rotprint / USSR Academy of Sciences, LEMI). (In Russian) 15. Mikhalevich, V.S.: Sequential optimization algorithms and their application. I. Cybernet- ics. No. 1, 45-55 (1965). (In Russian) 16. Mikhalevich, V.S.: Sequential optimization algorithms and their application. II. Cybernet- ics. 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(5), 759-767 (2014). doi 10.1007/s10559-014-9666-9 19. Trofymchuk, O.M., Vasyanin, V.A.: Simulation of Packing, Distribution and Routing of Small-Size Discrete Flows in a Multicommodity Network. Journal of Automation and In- formation Sciences. 47(7), 15-30 (2015). doi 10.1615/JAutomatInfScien.v47.i7.30 20. Trofymchuk, O.M., Vasyanin, V.A., Kuzmenko, V.N.: Optimization Algorithms for Pack- ing of Small-Lot Correspondence in Communication Networks. Cybernetics and Systems Analysis. 52(2), 258-268 (2016). doi 10.1007/s10559-016-9822-5