Модель формирования динамической структуры для установления источника сообщений в памяти приемника

Цель исследования – повышение скорости процедур определения источника данных в режиме сцепления блоков за счет анализа динамической списочной структуры сообщений, формируемой в памяти приемника в результате промежуточных вычислений.

Методы. Модель формирования динамической списочной структуры строится на основе аппаратной реализации метода ограничения множества обрабатываемых приемником блоков данных. В состав сообщения входит специальное служебное слово, содержимое которого проверяется на предмет попадания в диапазон значений, формируемый приемником при поступлении каждого блока данных. Описанное ограничение позволяет снизить количество типовых операций сравнения служебных слов, выполняемых при определении источника сообщений, а также снижает вероятность возникновения ошибок определения источника данных.

Результаты. На основе модели формирования динамической древовидной списочной структуры получены распределения априорных вероятностей числа узлов определённого уровня в случае возникновения ошибок определения источника данных и без таковых. Это позволяет получить значащие апостериорные вероятности ошибки в зависимости от наблюдаемого числа узлов определённого уровня. Сформулированы критерии принятия решения об ошибке определения источника на основании подсчёта числа узлов до полного завершения формирования древовидной структуры и до этапа её анализа. Это позволяет уменьшить вычислительную сложность процедуры определения источника данных в режиме сцепления блоков и снизить затраты памяти на хранение промежуточных результатов.

Заключение. В ходе проведенного исследования было выявлено, что для последовательностей сообщений длиной более 20 обнаружение более чем 8 посторонних ветвей формируемой динамической списочной структуры позволяет с 90%-ной вероятностью утверждать, что процедура определения источника завершилась ошибкой. Отказ от передачи последующих сообщений последовательности и от выполнения операций обработки древовидной структуры позволяет повысить скорость проведения процедуры определения источника сообщений и снизать его вычислительную сложность.

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. P. 1–6. https://doi.org: 10.1109/SiPS55645.2022.9919209.

2. Пат. 2547628 Российская Федерация, H04L 9/32, H04L 12/801. Способ и устройство управления потоками данных распределенной информационной системы / Бухарин В. В., Дворядкин В. В., Пикалов Е. Д., Романюк О. В., Куленич А. И. Ступаков И. Г. Заявл. 05.08.13; опубл. 10.04.15.

3. Мыцко Е. А, Мальчуков А. Н., Иванов С. Д. Исследование алгоритмов вычисления контрольной суммы CRC8 в микропроцессорных системах при дефиците ресурсов // Приборы и системы. Управление, контроль, диагностика. 2018. № 6. С. 22–29.

4. Пат. 1140141 Российская Федерация, A1 SU G08C 19/28. Устройство для приема и обработки избыточной информации / Зубков Ю. П., Ключко В. И., Николаев Ю. И., Петухов В. Е. Устинов Г. Н. Заявл. 27.06.83; опубл. 15.02. 85.

5. Толоманенко Е. А. Дифференциальный анализ трех раундов шифра «Кузнечик» // Доклады Томского государственного университета систем управления и радиоэлектроники. 2018. Т. 21, № 2. С. 22–26. https://doi.org: 10.21293/1818-0442-2018-21-2-22-26.

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

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

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

9. Stallings W. NIST Block Cipher Modes of Operation for Authentication and Combined Confidentiality and Authentication // Cryptologia. 2010. N 34. P. 225–235.

10. Panos Papadimitratos, Zygmunt J. Haas Secure message transmission in mobile ad hoc networks // Ad Hoc Networks. 2003. N 1(1). P. 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, N 11. P. 3626–3644.

12. A real-time motion estimation FPGA architecture / K. Babionitakis, G. A. Doumenis, G. Georgakarakos [et al.] // J. Real-Time Image Proc. 2008. N 3. P. 3–20. https://doi.org/ 10.1007/s11554-007-0070-9.

13. Таныгин М. О., Чеснокова А. А., Ахмад А. А. А. Повышение скорости определения источника сообщений за счет ограничения множества обрабатываемых блоков данных // Труды МАИ. 2022. № 125. https://doi.org/10.34759/trd-2022-125-20.

14. Черемисинов Д. И., Черемисинова Л. Д. Задачи обработки больших графов (graph mining) // Big Data and Advanced Analytics. 2019. № 5. С. 328–333.

15. Колганов А. С. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2016. Т. 5, № 3. С. 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, 2015. P. 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, 2015. P. 1–15. https://doi.org/10.1145/2791347. 2791383.

18. Повышение скорости обнаружения ошибок при формировании цепочек блоков данных на основе анализа числа совпадений хешей / М. О. Таныгин, Е. А. Кулешова, А. В. Митрофанов, Е. Ю. Гладилина // Прикаспийский журнал: управление и высокие технологии. 2022. № 1(57). С. 85–93. https://doi.org/10.54398/2074-1707_2022_1_85.

19. Метод ограничения множества обрабатываемых приёмником блоков данных для повышения достоверности операций определения их источника / М. О. Таныгин, О. Г. Добросердов, А. О. Власова, А. А. Ахмад // Труды МАИ. 2021. Т. 118, № 3. С. 15. https://doi.org/10.34759/trd-2021-118-14.

20. Таныгин М. О., Чеснокова А., Ахмад А. А. А. Снижение ресурсных затрат на обработку кодов аутентификации сообщений за счет ограничения числа обрабатываемых сообщений // Прикаспийский журнал: управление и высокие технологии. 2022. № 4(60). С. 22–29.