Точные границы эффективности алгоритмов распределения запросов между серверами

Abstract

Статья посвящена оценке эффективности алгоритмов диспетчеризации http-запросов между серверами. Для оценки эффективности предлагается найти ее теоретический максимум и минимум путем построения точной верхней и точной нижней границ эффективности алгоритмов распределения запросов между серверами. Главной проблемой является построение точной верхней границы. В целом вычисление границ можно свести к построению и анализу множества рациональных планов распределения между серверами поступающих от клиентов запросов, оценке эффективностей алгоритмов распределения запросов и последующему нахождению функций экстремума эффективности в каждый момент времени. Предложенный метод вычисления точных границ эффективности предполагает, что известны конфигурация программной системы, последовательность запросов во времени и их трудоемкость. Алгоритм, используемый методом для вычисления границ, имеет экспоненциальную сложность от времени и является трудноразрешимым для реальных конфигураций программных систем. Таким образом, этот метод для оценки эффективности алгоритмов диспетчеризации http-запросов является непригодным для применения в инженерных задачах.