name: Новые методы, алгоритмы и теоретические оценки работы алгоритмов в дизайне сетевых элементов
keyword_list: программно-­определяемые сети дизайн сетевых элементов алгоритмы
abstract: Объект исследования: Представления программ обработки пакетов и пакетных классификаторов в сетевых элементах.
  Цель работы: Разработать эффективные представления пакетных классификаторов; уменьшить объем памяти, используемой программами обработки пакетов в каждом сетевом элементе.
  Методы исследования, кроме используемых приборов и аппаратуры: Комбинаторный, сложностной, и аппроксимацонный анализ алгоритмов; алгоритмические методы теории графов; минимизация булевых формул.
  Достигнутые результаты:
  1. Предложены эффективные тернарные представления интервальных классификаторов, сохраняющие непересекаемость правил на уровне бит. Введено понятие подинтервала, доказано что подинтервал состоит либо из одного интервала либо из  двух «граничных» интервалов, разработаны эффективные методы кодировки подинтервалов в тернарные строки. Разработаны методы построения представлений классификаторов, содержащие подинтервалы вместо интервалов. 
  2. Разработаны методы построения комбинированных представлений нескольких пакетных классификаторов, заданных с помощью абстракции «класс». Предложено достаточное условие существования комбинированных представлений, содержащих ровно один экземпляр каждого класса, и алгоритм построения таких представлений. Для общего случая разработано два алгоритма построения комбинированных политик с минимальном число фильтров в дублированных экземплярах классов.  Доказаны верхние и нижние оценки аппроксимационных факторов для предложенных алгоритмов.
  3. Введено понятие приближенного классификатора с контролируемой ошибкой, позволяющее уменьшить количество классификационных правил даже в несжимаемом точном классификаторе. Обобщены булевы операторы, минимизирующие количество классификационных правил в точном классификаторе, на случай приближенных классификаторов. Предложены эффективные эвристики минимизации приближенных классификаторов, использующие обобщённые операторы.
  4. Предложены распределенные счетчики пакетов, фрагменты которых хранятся в сетевых элементами на пути потока. Для поддержки фрагментов счетчика в консистентном состоянии предложено два алгоритма. Устойчивость этих алгоритмов к сетевому шуму доказана аналитически. 
  Новизна: В работе предлагаются новые методы построения эффективных тернарных представлений интервальных пакетных классификаторов, вводятся эффективные комбинированные представления нескольких пакетных классификаторов, определяются приближенные классификаторы позволяющие еще больше уменьшить количество правил классификации. Также разработаны распределённые счетчики, позволяющие увеличить масштабируемость задачи мониторинга сетевых потоков.
  Внедрение: Предложенные методы  протестированы на синтетических данных.
  Эффективность: Для разработанных алгоритмов построения эффективных представлений классификаторов доказаны различные аналитические свойства результатов решения соответствующих комбинаторных задач. Толерантность распределенных счетчиков к сильному сетевому шуму доказана аналитически. Симуляции показали высокую эффективность предложенных методов и представлений на практике.
  Область применения: Дизайн компьютерных сетей и отдельных сетевых коммутаторов.
chairman_dissertation_council.name: Николай
chairman_dissertation_council.surname: Верещагин
chairman_dissertation_council.patronymic: Константинович
chairman_dissertation_council.position: профессор
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: L-9806-2016
chairman_dissertation_council.scopus_author_id: 7005187259
chairman_dissertation_council.rinc_id: 54
chairman_dissertation_council.orcid: 0000-0002-7386-979X
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Вадим
organization_supervisor.surname: Радаев
organization_supervisor.patronymic: Валерьевич
organization_supervisor.position: Первый проректор
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.47.17
rubrics.name: Математическая теория информации
oecds.code: 01.02.ER
oecds.name: COMPUTER SCIENCE, CYBERNETICS
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Николенко С.И.
supervisors.scientific_degree: Кандидат физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
supervisors.fio: Коган К.
supervisors.scientific_degree: Кандидат физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
protection_organization.short_name: Национальный исследовательский университет "Высшая школа экономики"; Национальный исследовательский университет ВШЭ; Высшая школа экономики; НИУ ВШЭ; ВШЭ
protection_organization.name: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики"
protection_organization.ogrn: 1027739630401
protection_organization.organization_type: Организация
protection_organization.okogu: Правительство Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: МИАН
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ МАТЕМАТИЧЕСКИЙ ИНСТИТУТ ИМ. В.А. СТЕКЛОВА РОССИЙСКОЙ АКАДЕМИИ НАУК
author_organization.ogrn: 1027739665436
author_organization.supervisor_name: ДМИТРИЙ
author_organization.supervisor_surname: ТРЕЩЕВ
author_organization.supervisor_patronymic: ВАЛЕРЬЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения