Проблема распределения нагрузки в информационно-телекоммуникационной сети

Современные информационные технологии/1. Компьютерная инженерия

Жуаспаев Т.А., старший преподаватель

Костанайский государственный университет имени А.Байтурсынова, Республика Казахстан

Проблема распределения нагрузки в информационно-телекоммуникационной сети

Основной задачей создания первых территориально распределенных сетей ЭВМ было предоставление удаленного доступа к вычислительным ресурсам. При создании и эксплуатации сети вычислительных машин имеет место проблема распределения нагрузки по вычислительным серверам. Эта проблема описана в ряде работ [1, 2, 3].

Но принятые методы, в частности [3], ориентируются на принцип распределения задач наиболее близким (с географической точки зрения) вычислительным узлам. В случае использования неоднородной сети на основе протоколов TCP/IP должны применяться иные подходы.

Пусть сеть базовых вычислительных серверов (в дальнейшем – серверов) имеет множество компьютеров А и множество задач X, которые предполагается выполнить в сети, и пусть А состоит из n серверов, а Х – из m независимых друг от друга задач.

Для каждого сервера a_iÎ А задана доступная мощность, измеряемая в вычислительных операциях в сутки. В соответствии с множеством А имеется вектор p=(p₁,...p_n) доступных вычислительных ресурсов всей сети. Известно, что стоимость единицы ресурса одинакова по всем серверам множества А (всем серверам сети) и что каждые два сервера a_i и a_j могут обмениваться между собой по одному кратчайшему маршруту длиной r_ij. В качестве меры длины маршрута будет определяться не физическое расстояние по каналам связи, а среднее время передачи пакета данных между узлами i и j. Два удаленных на тысячи километров узла могут быть связаны оптоволоконной линией, а связь с соседним сервером может проходить через телефонный канал с высокой степенью загрузки.

Время передачи r_ij берется в секундах. В соответствии с множеством А существует квадратная матрица R=||r_ij|| ранга времен передачи пакетов между узлами. Каждая задача х_iÎ Х характеризуется требуемым ресурсом z_i для ее выполнения в течение суток. По всем задачам множества Х существует вектор Z = (z₁,...,z_m) требуемых ресурсов.

По каждой задаче х_iÎ Х дан вектор v_i= (v_i₁,..., v_in), определяющий интенсивность обмена (байт/сут) задачи x_i с каждым сервером множества А. По всей совокупности задач имеем прямоугольную матрицу V размера m x n, составленную из векторов v_i, 1£ i£ m. Каждую задачу множества Х можно выполнять на любом одном сервере множества, т. е. распараллеливание задач недопустимо.

Проблема состоит в распределении задач Х по серверам множества в соответствии с заданным функционалом и ограничениями на допустимые ресурсы сервера. Ниже приводится постановка данной задачи с учетом специфики сетей TCP/IP.

Пусть в сети передачи данных между серверами нет каких-либо ограничений на пропускную способность каналов связи и процессов передачи данных. Логично считать, что при заданных параметрах качество проектируемой сети будет зависеть от среднего времени реакции системы на запросы к задачам, от стоимости арендуемых каналов связи и стоимости оборудования процессоров передачи данных.

Принимаем, что с точки зрения времени выполнения задачи все серверы множества А имеют одинаковые характеристики.

Задача распределения заявок по серверам сети может быть поставлена следующим образом. Необходимо сформировать такое распределение b, для которого время передачи данных абонентами и задачами будет минимальным.

Очевидно, что сеть ЭВМ, для которой время передачи данных минимально, требует при заданном р минимальной суммарной пропускной способности всех трактов (каналов связи) сети передачи данных.

При изложенных допущениях задача распределения математически формулируется следующим образом.

Даны множества А и X, представленные соответственно кортежами:

<А, р, R> и <Х, Z, V>,

где: р –вектор доступных вычислительных ресурсов,

R –матрица времен передачи данных между серверами;

Z – вектор требуемых ресурсов задач;

V – матрица интенсивности обмена задач с серверами.

Требуется найти такое отображение b:Х ® А, чтобы средневзвешенное время передачи данных L(b) между задачами и абонентами принимало минимальное значение, т.е.: , где: ,

определяет, закреплена ли задача х_k за сервером а_i,

, при условии для всех aÎ A.

Очевидно, что такая постановка также позволяет минимизировать средневзвешенное время передачи пакета данных между серверами.

Приведем одну из возможных числовых интерпретаций такой постановки.

Представим вектор Z в виде m-мерного вектор-столбца:

, где z_i - объем вычислений для задачи х_i. Тогда функцию b можно представить характеристической функцией (характеристической матрицей) Н ее трафика, т. е. Н = ||h_ij||, i=1,...,m; j=1 ,..., n.

Пусть a_j - номер некоторого сервера. Двоичный m-мерный вектор-столбец Н_j, содержащий единицу в местах с номерами составляющих его задач, назовем характеристическим столбцом а_j-го сервера. Скалярное произведение векторов равно используемому объему ресурса сервера а_j, а произведение H_jZ (матричное) представляет собой вектор s_j = (s_j₁,...,s_jn), i-й компонент которого равен интенсивности обмена между серверами а_i и а_j. Определим в векторе s_js_ij=0 при i = j. Квадратную матрицу ранга n значений s_ij обозначим S.

Суммарный поток между серверами есть функция распределения b, определяемая выражением: , где v_j – вектор-столбец матрицы V, а суммарный поток между задачами и абонентами не зависит от распределения b: . Тогда функционал

или

Основой определения h(b) служит штраф c_ij, за назначение задачи x_i на сервер a_jÎ A. Если по ряду причин недопустимо назначение задачи х_i на сервер а_j, в частности z_i> p_j, то величина c_ij принимается равной заданной большой величине m. Совокупность значений c_ij составляет прямоугольную матрицу С штрафов за назначение задач Х на серверы А.

Таким образом, задача сведена к минимизации линейного функционала. При выбранном критерии задача распределения нагрузки по серверам сводится к разбиению множества Х на подмножества и назначению их серверам множества А. Она соответствует классической транспортной задаче, в которой удовлетворение потребителя в ресурсе допускается только из одного источника множества А.

Литература:

1. Лозовский В. С. Семантические сети. – М.: ВИНИТИ, 1986.

2. Митин А. И., Пасхин Е. Н. Программно-методическое обеспечение подготовки учебного материала для АОС. – М.: Высшая школа, 1988.

3. Наумов Б. Н. Системы и средства информатики. – М.: Наука, 1989.