=Paper=
{{Paper
|id=Vol-2588/paper14
|storemode=property
|title=Quality of Service Optimization in Delay-Tolerant Networks through Cross-Layer Organization of Delivery Routes
|pdfUrl=https://ceur-ws.org/Vol-2588/paper14.pdf
|volume=Vol-2588
|authors=Mykola Vinogradov,Viktoriia Lukashenko,Marek Aleksander,Dmytro Shevchuk,Yevhen Vasiliu,Andriy Fesenko
|dblpUrl=https://dblp.org/rec/conf/cmigin/VinogradovLASVF19
}}
==Quality of Service Optimization in Delay-Tolerant Networks through Cross-Layer Organization of Delivery Routes==
https://ceur-ws.org/Vol-2588/paper14.pdf
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
mk
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.