ОЦЕНКА ВЛИЯНИЯ ПАРАМЕТРОВ УЗЛА СЕТИ НА ВРЕМЯ ОБРАБОТКИ ЗАПРОСА

 

Данилин Г.Г., Корнышев В.В.

(Москва, Московский Энергетический Институт (Технический университет), Россия)

 

 

 

 

Вычислительные сети на сегодняшний день являются одним из наиболее динамически развивающихся сектором информационных технологий. Одним из его подразделов является разработка систем, ориентированных на одновременную работу большого количества пользователей. Характерным примером таких систем могут служить интернет-магазины и игровые порталы. Размещение таких систем в публичных сетях приводит к тому, что число зарегистрированных, и как следствие, число одновременно подключенных к системе пользователей стремительно растет. Это приводит к тому, что производительность аппаратного обеспечения оказывается недостаточной для корректной работы такой системы. Возникает вопрос об увеличении этой производительности. Лежащее на поверхности решение – поставить более мощное оборудование – далеко не всегда оказывается приемлемым, поскольку его стоимость растет быстрее, нежели его производительность. Наиболее часто используемое решение – кластеризация системы, когда нагрузка распределяется между несколькими однотипными узлами. Масштабирование такой системы не представляет особых трудностей и достигается за счет добавления дополнительных узлов и переконфигурации системы. Однако, несмотря на широкую распространенность такого  рода решений (именно так, например, организована поисковая система “Яндекс”[1]), работы, позволяющие определить количественные характеристики системы (такие, как, например, количество узлов), отсутствуют. Данная работа является попыткой восполнить этот пробел.

 

Характерной особенностью рассматриваемых систем является жесткое ограничение на среднее время отклика системы: среднее время отклика системы T_ср. не должно превышать некоторого значения T_max при числе n одновременно работающих пользователей, не превышающего определенного значения N:

T_ср. £ T_max, n £ N (1)

Значения T_max и N оговариваются, как правило, в техническом задании.

Пусть рассматриваемая система представляет собой кластер из k узлов, каждый из которых содержит пул из m потоков, способных одновременно обрабатывать запросы пользователей. Пусть с системой одновременно работают N пользователей, каждый из которых генерирует поток запросов к системе с интенсивностью l₀ (следует отметить, что, хотя в общем случае поток клиентских запросов имеет явно выраженный нестационарный характер – его интенсивность зависит от времени суток – можно выделить отдельные интервалы времени, в течении которых его характеристики близки к стационарному). Также известно среднее время обработки одиночного клиентского запроса t₀. Требуется определить количество узлов k в системе и количество потоков m в узле при условии, что время отклика системы не должно превышать T_max.

Рассматриваемую систему можно представить как систему массового обслуживания (СМО), содержащую k узлов, способных одновременно обрабатывать m запросов. Общий поток клиентских запросов, интенсивность которого равна

l = N * l₀  (2)

равномерно распределяется между узлами, таким образом, на каждый узел поступает поток запросов с интенсивностью

  (3)

Отдельный узел можно представить как m-канальную СМО с неограниченной очередью. Однако, в отличие от классических СМО, рассматриваемых в [2], каналы влияют друг на друга – при одновременной обработка m запросов время обработки отдельного запроса увеличивается в m раз (рассматривается наиболее простой, но в то же время наиболее распространенный случай – узел на основе обычного ПК). Таким образом, формулы, описывающие поведение классической m-канальной СМО, в данном случае неприменимы. Рассмотрим стационарный режим работы узла – в этом режиме его поведение описывается системой алгебраических уравнений

  -l_k*P₀ + m₀*P₁ = 0,

l_k*P_n-1 – (l_k + m₀)*P_n + m₀*P_n+1 = 0, n ³ 1,  (4)

      ,

где , P_n – вероятность того, что в узле обрабатывается n запросов. Введем для удобства параметр r:

  (5)

Тогда при условии, что r < 1, решение системы уравнений (4) имеет вид

P₀ = 1 - r,

P_n = rⁿ * P₀  (6)

Среднее время обслуживания запроса в узле можно определить как

  (7)

Произведя нужные математические преобразования, получим

  (8)

Среднее число клиентов в очереди на одном узле можно определить как

  (9)

Произведя нужные математические преобразования, получим

  (10)

Тогда среднее время обработки запроса в узле (или же, среднее время отклика системы) будет равно

T_ср = (L_ср + 1)*t_ср  (11)

 

Результатом данной работы стало построение на основе теории массового обслуживания математической модели распределенной многопользовательской системы, ориентированной на работу в публичных информационных сетях. Как и ожидалось, характеристики такой системы оказались отличными от классических СМО с неограниченной очередью. Выражение (11) вместе с условием (1) дают возможность при известных значениях t₀, l₀, N рассчитать параметры системы – количество узлов k и количество потоков в узле m. К сожалению, сложность выведенных уравнений не позволяет получить решение аналитически, поэтому при реальных расчетах следует использовать численные методы.

 

ЛИТЕРАТУРА

1.     Сегалович И., “Как работает поисковая система”, http://www.computerra.ru/offline/2002/467/21440/

2.     Гнеденко Б.В., Коваленко И.Н., “Введение в теорию массового обслуживания”, М., 1987