A Model of Forming a Dynamic Structure for Establishing the Source of Messages in the Receiver's Memory

The purpose of research is increasing the speed of procedures for determining the data source in the block coupling mode, due to the analysis of the dynamic list structure of messages formed in the receiver's memory as a result of intermediate calculations.

Methods. The model of forming a dynamic list structure is based on the hardware implementation of the method of limiting the set of data blocks processed by the receiver. The data package includes a special service word, the contents of which are checked for falling into the range of values formed by the receiver when each data block is received. The described restriction reduces the number of typical comparison operations of service words performed when determining the source of messages, and also reduces the likelihood of errors in determining the data source.

Results. Based on the model of the formation of a dynamic tree-like list structure, distributions of a priori probabilities of the number of nodes of a certain level are obtained in case of errors in determining the data source and without them. This allows us to obtain significant a posteriori error probabilities depending on the observed number of nodes of a certain level. The criteria for making a decision on the error of determining the source based on the calculation of the number of nodes before the complete completion of the formation of the tree structure and before the stage of its analysis are formulated. This reduces the computational complexity of the procedure for determining the data source in the block coupling mode and reduces the memory costs for storing intermediate results.

Conclusion. In the course of the study, it was revealed that for sequences of messages with a length of more than 20, the detection of more than 8 extraneous branches of the dynamic list structure being formed allows us to state with a 90% probability that the procedure for determining the source ended in an error. The refusal to transmit subsequent sequence messages and to perform processing operations of the tree structure allows to increase the speed of the procedure for determining the source of messages and reduce its computational complexity.

1. Hashemipour-Nazari M., Goossens K., Balatsoukas-Stimming A. Multi-Factor Pruning for Recursive Projection-Aggregation Decoding of RM Codes. 2022 IEEE Workshop on Signal Processing Systems (SiPS). Rennes, France, 2022, pp. 1–6. https://doi.org/ 10.1109/SiPS55645.2022.9919209

2. Bukharin V. V., e. a. Sposob i ustrojstvo upravleniya potokami dannyh raspredelennoj informacionnoj sistemy [Method and device for controlling data flows of a distributed information system]. Patent RF, no. 2547628, 2015.

3. Mytsko E. A., Malchukov A. N., Ivanov S. D. Issledovanie algoritmov vychisleniya kontrol'noj summy CRC8 v mikroprocessornyh sistemah pri deficite resursov [Investigation of algorithms for calculating the CRC8 checksum in microprocessor systems with a shortage of resources]. Pribory i sistemy. Upravlenie, kontrol', diagnostika = Devices and Systems. Management, Control, Diagnostics, 2018, no. 6, pp. 22–29.

4. Zubkov Yu. P., e. a. Ustrojstvo dlya priema i obrabotki izbytochnoj informacii [Device for receiving and processing redundant information]. Patent RF, no. 1140141, 2015.

5. Tolomanenko E. A. Differencial'nyj analiz trekh raundov shifra "Kuznechik" [Differential analysis of three rounds of the cipher "Grasshopper"]. Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki = Reports of Tomsk State University of Control Systems and Radioelectronics, 2018, vol. 21, no. 2, pp. 22–26. https://doi.org/ 10.21293/1818-0442-2018-21-2-22-26

6. Aghdam S. M., Khansari M., Rabiee H., Salehi M. WCCP: A congestion control protocol for wireless multimedia communication in sensor networks. Ad Hoc Networks, 2014, vol. 13, pp. 516–534.

7. Bellare M., Kilian J., Rogaway P. The security of the cipher block chaining message authentication code. JCSS, 1994, vol. 3, no. 3, pp. 341–358.

8. Black J., Rogaway P. CBC MACs for arbitrary-length messages: The three-key constructions. J. Cryptol, 2005, vol. 18, no. 2, pp. 111–131.

9. Stallings W. NIST Block Cipher Modes of Operation for Authentication and Combined Confidentiality and Authentication. Cryptologia, 2010, no. 34, pp. 225–235.

10. Panos Papadimitratos, Zygmunt J. Haas Secure message transmission in mobile ad hoc networks. Ad Hoc Networks, 2003, no. 1, pp. 193–209.

11. Premkumar P., Shanthi D. Block Level Data Integrity Assurance Using Matrix Dialing Method towards High Performance Data Security on Cloud Storage. Scientific Research Publishing, 2016, vol. 7(11), pp. 3626–3644.

12. Babionitakis K., Doumenis G. A., Georgakarakos, G. eds. A real-time motion estimation FPGA architecture. J. Real-Time Image Proc., 2008, no. 3, pp. 3–20. https://doi.org/ 10.1007/s11554-007-0070-9

13. Tanygin M. O., Chesnokova A. A., Ahmad A. A. A. Povyshenie skorosti opredeleniya istochnika soobshchenij za schet ogranicheniya mnozhestva obrabatyvaemyh blokov dannyh [Increasing the speed of determining the source of messages by limiting the set of processed data blocks]. Trudy MAI = Proceedings of MAI, 2022, no. 125. https://doi.org/10.34759/trd2022-125-20

14. Cheremisinov D. I., Cheremisinova L. D. Zadachi obrabotki bol'shih grafov (graph mining) [Tasks of processing large graphs (graph mining)]. Big Data and Advanced Analytics, 2019, no. 5, pp. 328-333.

15. Kolganov A. S. Parallel'naya realizaciya algoritma poiska minimal'nyh ostovnyh derev'ev s ispol'zovaniem central'nogo i graficheskogo processorov [Parallel implementation of the algorithm for finding minimum threshold values using centralized and graphical processes]. Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya: Vychislitel'naya matematika i informatika = Bulletin of the South Ural University. Series: Computational Mathematics and Computer Science, 2016, vol. 5, no. 3, pp. 5–19. https://doi.org/10.14529/ cmse160301

16. Tasci S., Demirbas M. Employing in-memory data grids for distributed graph processing // IEEE 2015 IEEE International Conference on Big Data (Big Data). Santa Clara, CA, USA, IEEE Publ., 2015, pp. 1856–1864. https://doi.org/10.1109/bigdata.2015.7363959

17. Paradies M., Lehner W., Bornhövd C. GRAPHITE: an extensible graph traversal framework for relational database management systems. Proceedings of the 27th International Conference on Scientific and Statistical Database Management. New York, United States, Association for Computing Machinery Publ., 2015, pp. 1–15. https://doi.org/10.1145/2791347. 2791383

18. Tanygin M. O., Kuleshova E. A., Mitrofanov A. V., Gladilina E. Y. Povyshenie skorosti obnaruzheniya oshibok pri formirovanii cepochek blokov dannyh na osnove analiza chisla sovpadenij heshej [Increasing the speed of error detection in the formation of data block chains based on the analysis of the number of hash matches]. Prikaspijskij zhurnal: upravlenie i vysokie tekhnologii = Caspian Journal: Management and High Technologies, 2022, no. 1(57), pp. 85–93. https://doi.org/10.54398/2074-1707_2022_1_85

19. Tanygin M. O., Dobroserdov O. G., Vlasova A. O., Ahmad A. A. Metod ogranicheniya mnozhestva obrabatyvaemyh priyomnikom blokov dannyh dlya povysheniya dostovernosti operacij opredeleniya ih istochnika [Method of limiting the set of data blocks processed by the receiver to increase the reliability of operations for determining their source]. Trudy MAI = Proceedings of MAI, 2021, vol. 118, no. 3, p. 15. https://doi.org/10.34759/trd2021-118-14

20. Tanygin M. O., Chesnokova A. A., Akhmad A. A. A. Snizhenie resursnyh zatrat na obrabotku kodov autentifikacii soobshchenij za schet ogranicheniya chisla obrabatyvaemyh soobshchenij [Reduction of resource costs for processing message authentication codes by limiting the number of processed messages]. Prikaspijskij zhurnal: upravlenie i vysokie tekhnologii = Caspian Journal: Management and High Technologies, 2022, no. 4(60), pp. 22–29.