name: Теоретический и эмпирический анализ фундаментальных проблем организации компьютерных сетей и распределенных вычислений
keyword_list: АГРЕГАЦИЯ ДАННЫХ, БЕССЕРВЕРНЫЕ ВЫЧИСЛЕНИЯ, КЛАССИФИКАЦИЯ СЕТЕВЫХ ПАКЕТОВ, КОНКУРЕНТНЫЙ АНАЛИЗ, МОДЕЛЬ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ, ОНЛАЙН-АЛГОРИТМЫ
abstract: Объект исследования: алгоритмические аспекты функционирования компьютерных сетей, вычислительных систем и их взаимодействия. Цель: существенно расширить вычислительные  возможности существующих распределенных систем без дорогостоящего обновления  инфраструктуры, устранив лишь их некоторые фундаментальные ограничения. Для задачи управления очередью с двумя характеристиками пакетов доказаны общие и частные нижние оценки для алгоритмов, основанных на приоритетных очередях. Доказана константная конкурентность алгоритма, предпочитающего более ценные пакеты, для случая двух возможных ценностей. Предложены оптимальные полиномиальные алгоритмы преобразования обобщенных тернарных классификаторов пакетов в эквивалентную группу LPM классификаторов. Ключевой идеей является новая взаимосвязь между теорией порядка и способностью сетевых устройств конструировать сложные ключи для запросов. Разработана простая и эффективная схема распределения правил классификации вдоль пути потока данных. Данная система, используя один бит метаданных, позволяет избежать чрезмерных требований к вычислительным ресурсам и памяти устройств. Сформулирована теоретическая модель для бессерверных вычислений. В рамках данной модели были проанализированы с позиции конкурентного анализа жадный алгоритм и алгоритм, использующий амортизацию.  Исследована взаимосвязь между эффективностью алгоритмов и вводимой ими задержкой.Разработан двухэтапный подход для выполнения задач вычисления - агрегирования, учитывающий как особенности компьютерной сети, так и свойства приложений. Найдена взаимосвязь между задачами построения оптимального плана агрегирования и минимального дерева Штейнера. Предложены новые алгоритмы оптимизации классификаторов сетевых пакетов. Также доказаны ранее неизвестные теоретические оценки на онлайн-алгоритмы для задач управления буфером и выделения ресурсов. Рассмотрен новый двухэтапный подход для задач вычисления - агрегирования, выделяющий этап планирования. Предложенные методы были реализованы и протестированы в искусственной симуляционной среде. Все рассмотренные алгоритмы строят либо оптимальные, либо приближенные решения соответствующих оптимизационных задач за полиномиальное время. Точность приближения имеет строгие теоретические границы. Область применения: проектирование компьютерных сетей и распределенных вычислительных систем.
chairman_dissertation_council.surname: Верещагин Н. К.
chairman_dissertation_council.position: профессор
chairman_dissertation_council.degree: Доктор физико-математических наук
organization_supervisor.surname: Радаев В.В.
organization_supervisor.position: первый проректор
organization_supervisor.degree: Доктор экономических наук
rubrics.code: 27.45.17
rubrics.name: Теория графов
rubrics.code: 27.41.41
rubrics.name: Алгоритмы решения задач вычислительной и дискретной математики
oecds.code: 01.02.EX
oecds.name: COMPUTER SCIENCE, THEORY & METHODS
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Николенко С.И.
supervisors.scientific_degree: Кандидат физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: нет
opponents.responsible_type: Оппонент
opponents.fio: нет
opponents.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: 1037843013174
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения