Quality of Service Optimization in Delay-Tolerant Networks through Cross-Layer Organization of Delivery Routes Mykola Vinogradov 1 [0000-0001-9997-4865], Viktoriia Lukashenko 1 [0000-0001-9997-4865], Marek Aleksander 2 [0000-0003-2619-1063], Dmytro Shevchuk 1 [0000-0001-9911-7214], Yevhen Vasiliu 3 [0000-0002-8582-285X] and Andriy Fesenko 4 [0000-0001-5154-5324] 1 National Aviation University, Kyiv, Ukraine 2 State Higher Vocational School in Nowy Sącz, Nowy Sącz, Poland 3 O.S.Popov Odessa National Academy of Telecommunication, Odessa, Ukraine 4 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine vl43radar@yahoo.co.uk, v.v.lukashenko@gmail.com, aleksandermarek4@gmail.com Abstract. Protocols of data delivery in delay-tolerant networks with a low sensibility to the delays of signal and control data and to the intermittent connection (Delay/Disruption-Tolerant Networks – DTN) are considered in work. DTN (both for real-time and for non-real-time applications) have high requirements and strict constraints on delay, packet loss, and energy consumptions. The comparative analysis of parameters of different protocols of delivery of information in DTN is conducted. A mathematical model for quality of service (QoS) route determination is proposed. We suppose that any DTN sensor is enable to determine the optimal bundle of paths for minimising resource use while satisfying the required QoS constraints. The proposed mathematical model is grounded on the Lagrangian relaxation procedure introduced for approximately solving a large linear programming problem with NP-complexity. A lower bound on the value of the objective function on some set to define critical parameters and appropriate objective functions for controlling the adaptive QoS of constrained route discovery process is received. Performance trade-offs between QoS requirements and energy efficiency were simulated using Saaty Analytic Hierarchy Process. The proposed approach improves the network energy saving due to reducing energy consumption and decreasing average end-to-end delays within the DTN via optimised resource sharing in terminal and intermediate nodes compared with existing routing algorithms. Keywords: delay-tolerant network, network protocol, optimization, functional of quality, multi-criteria optimization nonlinear convolution of criteria, additive convolution of criteria. 1. Introduction As shown in [1], there are fundamental differences in the approaches to data transmission, storage, packet lifetime in information networks with low sensitivity to signal and control information delays and to unexpected connection delays (DTT). Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) CMiGIN-2019: International Workshop on Conflict Management in Global Information Networks. (Time-to-Live – TTL) and delivery guarantees. For example, if in normal networks the TTL parameter can be tens, a maximum of hundreds of milliseconds [2], then in specialized networks such as the interplanetary Internet, the data delivery time is from seconds (from Earth to the Moon) to units of minutes (from Earth to Mars). The problem is aggravated by an increase in the ratio of the number of distorted bits to the total number of transmitted bits (BER) due to the deterioration of the Signal-to- Noise Ratio (SNR) caused by external factors, in particular, the effect of solar radiation, magnetic storms, etc. Based on these considerations, it is necessary to carefully calculate the technical characteristics of specialized DTN-networks and correctly organize data transmission. 2. Related works in delay-tolerant networks As the results of analysis showed the number of reliable transport solutions for DTN have been designed in the framework of deep-space communications. Most of these solutions aim at extending the TCP mode of operation so as to handle very long delays and possible route disconnection: SCPS-TP (Space Communication Protocol Standards-Transport Protocol) [3], DS-TP (Deep-Space Transport Protocol) [4] and TP-Planet (Transport Protocol for Inter-Planetary Internet) [5] are some examples. Other solutions (e.g., Saratoga [6] or LTP-T [7]) are based on the Bundle Protocol (BP) [8] proposed by the DTN-RG [9], and are able to deliver only a hop-by-hop reliability (wit 2 therefore a per-hop retransmission method). Specifically, LTP-T handles errors and Automatic Repeat reQuest (ARQ) on a hop-by-hop basis. Nevertheless, all these solutions assume data delivery with probability one as soon as they know a route from the source to the destination. However, in this paper, we are interested in sparse DTN with random mobility, where assumption can be made neither about the existence of a contemporaneous path to the destination nor about knowledge of the destination location, beforehand. 3. Characteristics of the main protocols Routing is a non-standard task of organizing data delivery in DTN-networks. Traditional routing protocols are generally not suitable because of the high speed requirements and memory requirements of the data delivery management system to ensure guaranteed data storage for an indefinite time and complete information about the state of the communication system. Existing network protocols of DTN-networks can be divided into three large categories [2]: one copy (or directional transmission), multiple copies (or broadcast), and hybrid (multicast). Protocols of the first type transmit only one copy of the message along the selected route to the destination. Broadcast transmissions transmit multiple copies of the message to sensory nodes within the network, waiting for at least one copy to reach the destination. Broadcast protocols, for example, protocols based on epidemic theory or even a pandemic [10], can improve delivery guarantees. However, obviously, with loss of network connectivity and/or occasional connections/disconnections, the requirements for buffer memory volumes increase rapidly with increasing network size. The choice of unicast or broadcast dispatch is conditioned due to the following considerations:  broadcasting protocols can work with minimal information about parameters and network status, while using forwarded protocols, you need to have comprehensive information about the network in order to calculate the best route;  multicast protocols result in redundancy, but the cost of re-sending due to packet loss can be quite high. Network protocols can be passively adaptive or actively adaptive, depending on when the route is calculated. In active-adaptive network protocols, all routes are predicted and calculated before they are in demand. Passive-adaptive network protocols calculate routes only when the need arises. If the information about the connectivity of the network is regularly updated in the sensor nodes, the optimal routes in systems with actively adaptive protocols are calculated quite simply. But these network protocols require more network resources to compute and update routing tables, especially when the network topology changes frequently. On the other hand, in passive-adaptive protocols, routing tables are smaller, so their calculation and updating is easier. However, because of the need to calculate the route, an additional delay is introduced before the message is sent. Hybrid network protocols combine both approaches. Let's consider the main characteristics of the network protocols of DTN-networks. The protocol stacks for OSI, TCP/IP and DTN reference models are shown on Fig. 1. OSI TCP/IP DTN Application Application Application Presentation Absent Bundle Session Transport Transport Transport Network Internet Network Data Link Data Link Host-to-Network Physical Physical Fig. 1. Reference models Bundle Protocol [11-12] is an additional level protocol for the reference model of open systems interconnection (OSI), which is introduced between the transport layer and the application layer and serves to guarantee the delivery of data. It works on top of the so-called LTP protocol - the Licklider transmission protocol (sometimes called the longhaul transmission protocol), a point-to-point protocol designed for backbone communications in deep space [14-17]. 3. Multi-criteria protocols optimization In DTN-networks, there are situations when the entire route from the source to the destination does not exist. As a result, network protocols, in which it is assumed that the general route from source to destination, may not work reliably. Due to energy and storage time limitations in network nodes, protocols that are not energy efficient and do not provide storage guarantees are less preferable for DTN networks [18]. To reduce the load on the network without loss in the speed of delivery and the relative number of delivered packages, consider the delivery algorithm with diffusion of the Markov process through M c  1 hops. To achieve the equilibrium point the restriction of multiplication of the number of copies of the packet in the network - select the corresponding transition threshold. If the number of copies of the package is small, the number of nodes involved grows rapidly, on the other hand, as the number of copies of the packet increases; the number of nodes participating in the package distribution process should decrease. After the number of duplicate copies of the packet reaches the equilibrium point, Mc  1 hops enter a second state in which the nodes that receive the copy of the packet do not advance it to other nodes except the destination node. Thus, we are striving to provide a simple but effective solution to address the routing problem in DTN networks of variable structure when the network topology forecast is impossible. This minimizes the number of messages transmitted and ensures the delivery of urgent messages with the minimum possible delay. We will consider the delivery delay d as the main metric of the route. In this case, messages will be redirected from nodes with large d to nodes with smaller ones. Then the delay in delivery to the node d k is the minimum amount dl and kl among its neighbours [19-21]: dk  min  dl  kl  (1) d l D where dk is delivery delay to neighbour node dl , kl is contact interval between d k and dl , D is the set of neighbour nodes with d k . The proposed algorithm implies the presence of a priori data about the resources and volumes of the buffer memory. In addition to information about the delivery delay, it is necessary to calculate and enter in the routing table the data on the level of the energy resource, the amount of free buffer memory and other parameters arbitrarily combined in the quality function (Fig. 2) [22]. Fig. 2. Functions of the quality of service management during data transmission In order to save energy and exclude the possibility of looping the route, the messages are routed to nodes with minimal delivery delays and better parameters of the routing table than those that are recorded in the transmitted message [23]. In the transmission of high priority messages, the delivery delay is the only metric used to calculate the optimal route in order to minimize waiting time. An efficient delivery algorithm based on multiplication of data and an actively adaptive delivery algorithm with low sensitivity to data errors ensure the delivery of data in DTN with variable structure due to accidental disconnections or withdrawal of carriers from the reception area. At the same time, it is necessary to ensure both guaranteed storage and transmission of data, as well as mechanisms for managing the buffer memory of nodes. Fig. 3 presents domains of the quality of service system architecture. Fig. 3. Quality of service system architecture The data transfer algorithm is based on estimating the probability that a node can deliver a message to the receiving point. Let it k  t  denotes the probability of the message being delivered by the k th node within a time t, and   0  0 . Each node has a timer  to calculate its probability. If the k th node does not transmit any data to the other node during the time , k  t  decreases. The law of decrease depends on the statistics of network traffic. For the specialized networks considered in this paper, the distribution of the traffic intensity can be subject to different laws depending on the specifics of the network. For example, in the autonomous terrestrial network of radio sensors (sensor network) or in the network of open space, the law of rare events of the Poisson or exponential family can take place. In a sensor network with long- term storage and controlled data transmission, on the contrary, it is logical to expect self-similar traffic with Hurst coefficients close to unity. In any case, before the choice of a priori probability distributions it is necessary to conduct additional analytical or, if possible, experimental studies [24-25]. If k th the node transmits the message to the other node m, respectively, is updated to the value  m . Messages are placed in the queue with the FIFO service discipline in each node. When a k th node has a message to send and advance through a sequence of nodes, the required probability of delivery and free buffer memory of each node are provided through simple messages of Hello type. Next, the k th node transmits a message to the neighbouring node m with a free buffer space, the probability of delivery from the entire set of neighbouring nodes being the highest, which is also higher than the probability of delivery actually through the k th node, m  k . To determine the randomised functional of the efficiency of the delivery protocol, we introduce a function-a standardized quantification of the stability to errors (distortions) of a message transmitted to a neighbouring node. At the time of message generation, the value g  k,l   0 , and at the time of delivery dv  k,l   1 . After the k th node transmits messages to Mc neighbouring nodes, M c  1 copies appear in the network. Then, applying the multiplication theorem for event probabilities, it is possible to calculate the probabilistic error-resistance estimate of the transmitted message to the mth neighbouring node by the following formula: K   k, l   1  1    k, m   1  l   1  lm  . (2) m 1 mk Accordingly, the estimation of the error tolerance of the transmitted message at the kth node is recalculated according to the formula 3: K   k, k   1  1    k, m    1  lm  . (3) m 1 Thus, in each node a list of messages for transmission, a list of deleted messages and a list of priorities for sending messages are stored. The list for transmission is combined into a tuple with a list of message priorities. When the contact becomes available, the messages are delivered in accordance with the queue in the gear list and priorities. When two nodes discover each other, they exchange the mentioned message lists. If the nodes have messages in their buffers that are simultaneously in both lists, the exchange of which occurred, the messages are excluded. If the node has some messages destined for another node, it transmits mentioned messages. For network protocols, it is also important to evaluate energy efficiency, buffer space control efficiency, and computational complexity. These quantitative and qualitative parameters must be taken into account in the resulting functional of quality. Therefore, the resulting functional must include partial (auxiliary) functionals associated with different parameters. This, firstly, the time delivery parameters:  time of delivery delay d ;  total time dk of contact between nodes d and k;  time  rt of building routing table;  time  pp of packet processing (or the set of packets processing – bundle processing). Secondly, there are the functionals 1  k, m  and  2   k  t   , related to delivery errors and message delivery probabilities, respectively. In view of the above considerations, we will write down the final expression for the resulting quality functional of protocols for DTN-networks:       d , dk , rt , pp  , 1  k, m  ,  2 k  t   max , V ,  (4) where   d , dk , rt , pp  is temporal functional of messages delivery quality; 1  k, m  is functional of delivery errors;  2   k  t   is functional of delivery probabilities; V  ,   is the vector of routing protocol parameters. 4. Experimental study and discussion Theoretically, the resulting functional (4) is a non-linear convolution of partial functionals associated with temporal and probabilistic characteristics of message delivery. The search for the best value of such a functional is not only very difficult, but also a low-productivity task. The point is that the solution obtained as a result of optimization of the functional (4) is very sensitive to errors in setting the initial data. Since the specificity of the DTN-networks under consideration lies precisely in the absence of reliable a priori information about the current parameters and network state-topology, network scale, number of network and terminal nodes, etc. - the stability of the optimal solution is not guaranteed. In essence, this problem should be attributed to the class of ill-posed problems of mathematical physics. In our opinion, the most realistic approach to solving this problem is to obtain some asymptotic solutions of minimax type, which can be treated as the best estimates for the worst case. In other words, it is expedient to look for certain estimates of maximum likelihood. Such estimates can be sought by replacing the non-linear convolution of the criteria by linear additive convolution with pre-selected weight coefficients of the terms. Consequently, to design future major components of DTN devices (nodes) that consume extremely low energy, have low production cost, and operate in high density, it is important to study how to involve integer optimization for an industrial implementation of these severe constraints in terms of operating the sensor nodes for a long time over months or even years. The general problem formulation can be represented as min f  x, y, z  , x, y, z  gi  x, y, z   0, i  1, m;  h j  x, y, z   0, j  1, l ;   x  , y  0, 1 , z  , where f is the objective function; a set of explicit linear constraints defined as g i make up the inequality constraints function; h j is the equality constraint function; x belong to the set of natural numbers, while y are binary digits. Thus, if z  0 , the problem is referred to as almost integer-programming, whereas if y  0 , the problem is referred to as pure integer programming. The problem is otherwise considered to be a mixed integer-programming problem. Lagrangian relaxation (LR) considers only some solution methods in an optimization that cuts across the domains of integer, combinational, and non-linear programming 5. In other words, LR is defined as a procedure that uses the idea of relaxing the explicit linear constraints by bringing them into the objective function with the associated Lagrange multipliers  i [13]. Proceeding from these considerations, we replace this non-linear functional by a linear parametric functional of the form      d , dk , rt , pp  , 1  k, m  ,  2  k  t     a1  d   a 2   dk   a 3  rt   a 4   pp   a 5 1  k, m   a 6  2  k  t   max, (5) V  ,   where a i , i  1,6 are the weights of the importance of particular quality indicators. The initial values of the weights are chosen subjectively, experimentally and specified in the current operation of the network. In addition, some quality indicators (for example, energy resources, buffer memory volumes) can be considered as constraints and solve the problem of conditional optimization. If none of the network protocols meet all the requirements for network performance, reliability of message delivery, it is obviously necessary to use a unique protocol stack and change a protocol taking into account the specifics of the task being solved at the moment. 5. Conclusion In this paper, a comparative analysis of the effectiveness of network protocols for use in specialized information and computer networks that have low sensitivity to data delivery delays was performed. A mathematical model for QoS route determination is proposed and it is grounded on the Lagrangian relaxation procedure introduced for approximately solving a large linear programming problem with NP-complexity. In the future research study, it is planned to consider real-time buffer memory control tasks and to evaluate the computational complexity of algorithms for optimizing network protocols. References 1. Lukashenko, V.V. Characteristics of the corporate network management system in the presence of random delays in the delivery of control and signal information, Scientific Notes of Ukrainian Scientific and Research Institute, №19, 2011, pp. 62-68 (in Russian) 2. Tanenbaum, A.S. Computer Networks, 5th Ed. / Andrew S. Tanenbaum, David J. Wetherall, Prentice Hall, Cloth, 2011, 960 p. 3. Consultative Committee for Space Data Systems, “Space Communications Protocol Standards, Transport Protocol (SCPS-TP),”CCSDS 714.0-B-2, Blue Book, Oct. 2006. 4. I. Psaras, G. Papastergiou, V. Tsaoussidis, and N. Peccia, “DS-TP: Deep-Space Transport Protocol,” in IEEE Aerospace Conf., 2008, pp. 1–13. 5. O. B. Akan, J. Fang, and I. F. Akyildiz, “TP-Planet: A Reliable Transport Protocol for InterPlanetary Internet,” IEEE Journal on Selected Areas in Comm. (JSAC), vol. 22, no. 2, pp. 348-361, 2004. 6. L. Wood, J. McKim, W. Eddy, W. Ivancic, and C. Jackson, “Saratoga: A Scalable File Transfer Protocol,” in IETF draft draft-woodtsvwg-saratoga-03, Oct. 2007. 7. S. Farrell and V. Cahill, “LTP-T: a Generic Delay Tolerant Transport Protocol,” in Technical report , 2005. [Online]. Available: http://www.scss.tcd.ie/publications/tech- reports/reports.05/TCD-CS-2005-69.pdf 8. Al-Azzeh J.S., Al Hadidi M., Odarchenko R., Gnatyuk S., Shevchuk Z., Hu Z. Analysis of self-similar traffic models in computer networks, International Review on Modelling and Simulations, № 10(5), pp. 328-336, 2017. 9. Internet Research Task Force, “Delay-Tolerant Networking Research Group,” 2013. [Online]. Available: http://www.dtnrg.org 10. Mundur P., Seligman M. Delay Tolerant Network Routing: Beyond Epidemic Routing, Proceedings of third international symposium on Wireless Pervasive Computing, 2008, ISWPC 2008, 7-9 May 2008, Santorini, pp. 550-553. 11. Cerf V., Burleigh S., Hooke A., Torgerson L., Durst R., Scott K., Fall K., Weiss H. Delay-Tolerant Networking Architecture // Request for Comments: 4838, April 2007, 35 р. http://tools.ietf.org/pdf/rfc4838.pdf 12. Fisher M.L. The Lagrangian relaxation method for solving integer programming problems.Management Science, vol. 27, 1981, pp 1-18. 13. Shapiro J.F. A survey of Lagrangian techniques for discrete optimization. Ann. Discrete Math. vol. 5, 1979, pp 113-138. 14. Mazin Al Hadidi, Jamil S. Al-Azzeh, R. Odarchenko, S. Gnatyuk, A. Abakumova, Adaptive Regulation of Radiated Power Radio Transmitting Devices in Modern Cellular Network Depending on Climatic Conditions, Contemporary Engineering Sciences, Vol. 9, № 10, рр. 473-485, 2016. 15. A. Tikhomirov, N. Kinash, S. Gnatyuk, A. Trufanov, O. Berestneva et al, Network Society: Aggregate Topological Models, Communications in Computer and Information Science. Verlag: Springer Intern. Publ, Vol. 487, рр. 415-421, 2014. 16. Mazin Al Hadidi, J. Samih Al-Azzeh, O. Tkalich, R. Odarchenko, S. Gnatyuk, Yu. Khokhlachova. ZigBee, Bluetooth and Wi-Fi Complex Wireless Networks Performance Increasing, International Journal on Communications Antenna and Propagation, Vol. 7, № 1, рр. 48-56, 2017. 17. Richa Thakur, K.L. Bansal, Delay Tolerant Networks: An Analysis of Routing Protocols with ONE Simulator, International Journal of Computer Network and Information Security (IJCNIS), vol.8, No.12, pp.51-58, 2016. 18. S. Gnatyuk, V. Kinzeryavyy, M. Iavich, D. Prysiazhnyi, Kh. Yubuzova, High- Performance Reliable Block Encryption Algorithms Secured against Linear and Differential Cryptanalytic Attacks, CEUR Workshop Proceedings, Vol. 2104, pp. 657-668, 2018. 19. Kalimoldayev M., Tynymbayev S., Gnatyuk S., Khokhlov S., Magzom M., Kozhagulov Y. Matrix multiplier of polynomials modulo analysis starting with the lower order digits of the multiplier, News of the National Academy of Sciences of the Republic of Kazakhstan, Series of Geology and Technical Sciences, №4 (436), pp. 181-187, 2019. 20. Iavich M., Gagnidze A., Iashvili G., Gnatyuk S., Vialkova V. Lattice based Merkle, CEUR Workshop Proceedings, Vol. 2470, pp. 13-16, 2019. 21. M. Iavich, S. Gnatyuk, E. Jintcharadze, Y. Polishchuk, A. Fesenko and A. Abisheva, Comparison and Hybrid Implementation of Blowfish, Twofish and RSA Cryptosystems, Proceedings of 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON), Lviv, Ukraine, 2019, pp. 970-974. 22. Tynymbayev S., Gnatyuk S.A., Aitkhozhayeva Y.Z., Berdibayev R.S., Namazbayev T.A. Modular reduction based on the divider by blocking negative remainders, News of the National Academy of Sciences of the Republic of Kazakhstan, Series of Geology and Technical Sciences, №2 (434), pp. 238-248, 2019. 23. Kalimoldayev M., Tynymbayev S., Gnatyuk S., Ibraimov M., Magzom M. The device for multiplying polynomials modulo an irreducible polynomial, News of the National Academy of Sciences of the Republic of Kazakhstan, Series of Geology and Technical Sciences, №2 (434), pp. 199-205, 2019. 24. M. Iavich, S. Gnatyuk, E. Jintcharadze, Yu. Polishchuk, R. Odarchenko, Hybrid Encryption Model of AES and ElGamal Cryptosystems for Flight Control Systems, Proceedings of the 2018 IEEE 5th International Conference on Methods and Systems of Navigation and Motion Control, October 16-18, 2018, Kyiv, Ukraine, pp. 229-233. 25. Savita, D. K. Lobiyal, Multicopy Energy Aware Distance and Inter-Contact Delay Routing (EDICDR) Approach for Delay Tolerant Networks, International Journal of Computer Network and Information Security (IJCNIS), vol.11, No.5, pp.36-42, 2019.