обработка данных в распределенных системах

УДК: 62-83:007.52

ВОПРОСЫ ОБРАБОТКИ ДАННЫХ В РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ СИСТЕМАХ

Васильев А.М.

Московский государственный университет приборостроения и информатики

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

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

Ключевые слова: Распределенная информационно-измерительная система; теория массового обслуживания; информационный поток коммутация блоков данных; пропускная способность канала.

Для изучения процессов происходящих в распределенных информа- ционно-измерительных системах (РИИС) с большим количеством пользователей наиболее широко применяемой методологией является теория массового обслуживания [1, 5].

Применение теории массового обслуживания к исследованию процессов, происходящих в РИИС при передаче данных, основывается на предположении о том, что моменты поступления требований в систему (моменты прихода пакетов в маршрутизатор) образуют пуассоновский поток с интенсивностью λ. Если распределение длительностей времени обслуживания также является пуассоновским, то применение методологии системы массового обслуживания М/М/1 позволяет определить среднее число требований в системе и с помощью теоремы Литтла [4] связать это число со средней задержкой в системе в равновесном состоянии. Анализ систем массового обслуживания предполагает, что процесс, считающий число требований находящихся в системе является марковским процессом с непрерывным или дискретным временем, исследование которого и дает среднее число требований в системе в стационарном режиме. Таким образом, получают формулы для среднего числа требований (1) и среднего времени пребывания требований (2) в системе

N = λ / μ − λ	(1)
где μ - скорость обслуживающего прибора
T = 1/ μ − λ	(2)

Если же предполагается произвольное распределение длительностей обслуживания требований, то такая система массового обслуживания обозначается M / G /1 , и среднее время пребывания требования в обслуживающем приборе выражается формулой Поллачека-Хинчина [4]:

	W = λ X 2 / 2(1− ρ ),	(3)
где W - математическое ожидание времени пребывания требования в оче-
реди, ρ =	λ X 2 / μ = μ X 2 , если X i - длительность обслуживания i-ro требо-
вания, а	X 2 = E( X ) момент второго порядка распределения длительно-
стей обслуживания.
	T = X + λ X 2 / 2(1− ρ )	(4)

Для РИИС с коммутацией блоков данных применялись методы, основывающиеся на предположении о том, моменты прибытия блоков или инициализации соединений имеют ограниченную дисперсию, поскольку аналитическая модель для таких систем хорошо известна [5]. На основании этой модели рассчитывались основные характеристики РИИС, и производилось планирование ее ресурсов, в частности, объема буферного пространства.

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

Итак, традиционный подход к моделированию информационного потока РИИС с коммутацией блоков данных базируется полностью на предположении о неограниченности дисперсии процесса поступления блоков данных, что позволяет применять теоретический аппарат марковских цепей для анализа таких систем. Однако развитие современных скоростных РИИС передачи данных информационных потоков с выраженной гетерогенной физической и логической инфраструктурой и большим набором разнообразных функций, приводит к появлению существенно более сложных характеристик потоков. Информационный поток в таких РИИС имеет явно выраженный всплесковый характер, не сглаживаемый усреднением по длительным временным промежуткам и большому числу потоков [4].

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

Формализуем модель изучаемой РИИС. Представим РИИС, в схему, которой входят несколько узлов, два коммутатора (маршрутизатора) и набор каналов соединяющих узлы. Стрелками указано направление передачи данных (рис.1).

Рис.1. Упрощенная функциональная схема РИИС с коммутацией блоков данных.

Наиболее важными характеристиками при анализе являются [5]:

–пропускная способность канала, определяющая скорость поступления битов в канал;

–задержка передачи, характеризующая длительность интервала между поступлением определенного бита в канал и появлением его из канала;

–пропускная способность канала задержка передачи;

–вероятность битовой ошибки, определяющая вероятность потери сегмента в зависимости от вероятности ошибки при передаче;

–относительное число потерь сегментов (отношение числа потерянных к общему числу отправленных сегментов);

–коэффициент использования пропускной способности каналов;

–коэффициент равноправия разделения ресурсов

где bi - есть доля пропускной способности, занятая i-м соединением, сред-

няя длина очереди Q в маршрутизаторе R1.

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

Построение математической модели передачи данных проведем исходя из следующих упрощающих предположений:

–передача данных производится в одном потоке;

–блок данных включает К порций данных;

–канал передачи абсолютно надежен, т.е. отсутствует повторная

передача блоков данных.

Заметим, что из первого предположения следует, что временем обработки порций данных на фазе выбора направления передачи можно пренебречь. Предположим также, что поток данных является пуассоновским с параметром N, а время передачи блока данных в потоке распределено по экспоненциальному закону с параметром 1/х. Тогда в качестве упрощенной математической модели функционирования передачи данных может быть рассмотрена система массового обслуживания (СМО) типа М|М|1 (рис. 2) с групповым обслуживанием заявок, в которой заявки соответствуют порциям данных, а размер группы заявок — числу порций, передаваемых в одном блоке данных.

Рис.2. Математическая модель в виде СМО с групповым обслуживанием заявок.

Таким образом, в построенной модели поступление группы заявок на обслуживающий прибор производится только в том случае, когда в очереди имеется по крайней мере К заявок. В этом заключается принципиальное отличие данной модели от СМО, исследованной в [13], где размер группы ограничен сверху и не фиксирован.

На рис. 3 показана диаграмма интенсивностей переходов марковского процесса, описывающего функционирование рассматриваемой СМО, где под состоянием понимается общее число заявок в системе.

Рис.3.

Пусть pi вероятность того, что в некоторый момент времени система

находится в состоянии i. Тогда соответствующая система уравнений равновесия имеет вид

(5) Для решения (5) введем производящую функцию

нетрудно видеть, что она имеет вид

(6)

где p = λ / μ .

Из условия нормировки, т.е. P (z) → 1, при z → 1 получаем уравнение

(7)

которое вместе с К — 1 уравнениями, полученными при подстановке в числитель (7) соответствующих нулей знаменателя, образует невырожденную систему уравнений

(8)

Из (8) получаем искомую производящую функцию в виде

(9)

Основные вероятностно-временные характеристики рассматриваемой системы массового обслуживания можно вычислить по формулам

(10)

(11)

где N — среднее число заявок в системе и P0 — вероятность простоя при-

бора. Для вычисления среднего времени пребывания заявок в системе можно воспользоваться формулой Литтла [4].

Заметим, что условие эргодичности очереди имеет вид р < К, а для вычисления (10 ,11) необходимо найти значение величины ZK , что можно сделать, решив, например, методом деления отрезка пополам уравнение

учитывая, что

Очевидно, что современный аппарат теории массового обслуживания позволяет провести анализ модели функционирования передачи данных без столь упрощающих предположений об обслуживаемой нагрузке, как в случае СМО типа М|М|1.

Результаты численного анализа задержек передачи данных для случая детерминированного времени обслуживания представлены на рис. 4. Это графики зависимости среднего значения задержки данных от интенсивности входящего потока для случаев, когда время передачи блока данных распределено по экспоненциальному и детерминированному законам с одинаковым средним значением. Размер группы заявок был принят равным 4, поскольку при максимальной длине данных 279 байт и длине заголовка блока данных, равного 32 байтам. Среднее время обслуживания было выбрано равным 1 мс по результатам измерений на ЭПК.

Поведение графиков на рис. 4 объясняется тем, что при сравнительно небольшой нагрузке общая задержка передачи в значительной мере зависит от времени формирования группы заявок. Действительно, чем меньше нагрузка, тем реже поступают заявки, и тем больше требуется времени для формирования группы, и, следовательно, тем больше значение времени

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

Рис.4. Графики задержек передачи данных.

Класс, моделирующий канал, получает значения пропускной способности и задержки передачи при инициализации. Структура данных класса реализуется односвязной динамической очередью, в которую помещаются сегменты, принятые на обслуживание. После начала обслуживания сегмента канал блокирует последующие запросы в течение времени t=S/R, где S - размер сегмента, a R - скорость канала, т.е. времени приема сегмента размера S в канал. В очереди канала сегмент задерживается в течение установленного времени задержки передачи. По истечении этого времени, объект канала вызывает метку следующего объекта в структуре РИИС. Если следующий объект отказывает в обслуживании сегмента, то этот сегмент отбрасывается.

Обработка прерывания переводит внутренний счетчик времени и вызывает передачу готового сегмента из канала следующему объекту структуры.

Для моделирования ошибок среды передачи блок данных может быть инициализирован перегружаемым инициализатором, который помимо параметров скорости и задержки канала получает также параметр, соответствующий значению ошибки передачи σ. С вероятностью 1 - (1 - σ) сегмент отбрасывается вместо передачи следующему элементу структуры.

При приеме сегмента интерфейс незамедлительно передает его объекту маршрутизатора. Блокировки при этом произойти не может, т.е. моделируется не резидентной вероятностью ошибки, называется ее вероятность после применения алгоритмов коррекции ошибок.

Объект маршрутизатора вносит запись, состоящую из двух полей (номер интерфейса, адрес отправителя) в таблицу маршрутизации. После этого сопоставление адреса назначения сегмента со вторым полем таблицы маршрутизации дает номер выходного интерфейса для данного сегмента.

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

пространство в ней Qmax − Q > S , в противном случае сегмент отбрасыва-

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

Метод обработки прерывания каждого из интерфейсов вызывается методом обработки прерывания объекта маршрутизатора. Также объекты маршрутизатора и интерфейса снабжены методами для выдачи отчета по текущим параметрам трафика: средняя скорость, счетчики пропущенных/отброшенных сегментов, таблица маршрутизации, средняя длина очереди.

Таким образом, объект маршрутизатора моделирует современное межсетевое устройство с не блокирующей коммутационной матрицей и буферизацией на выходе.

Модель алгоритма реализует управление скоростью отправки сегментов посредством механизма скользящего окна и собственно самого алгоритма, коррекцию ошибок передачи не связанную с управлением передачи и быструю ретрансляцию сегментов.

Данный класс алгоритма реализует схему стандартного управления потоком по методу скользящего окна. Класс содержит динамический список двойной связности, в который записываются указатели на сегменты, поставленные в очередь. Методы алгоритмов такого класса позволяют осуществлять вставку сегмента с сортировкой, сканирование списка, нахождение очередного сегмента готового к передаче. Ретрансляция реализована посредством изменения очередности готовых к отправке сегментов. Взаимодействие очередей с объектом протокола и схема обработки сегментов приведены на рис. 5. Прямые линии указывают направление потоков данных, кривые - управляющей информации.

Рис.5. Схема взаимодействия очередей приема и передачи с алгоритмом управления потоком РИИС ГАП.

При обработке приема сегмент, принятый узлом, передается в работу алгоритма, который принимает сегмент и обрабатывает его как подтверждение, если сегмент содержит поле подтверждения. Параметры алгоритма вычисляются, если установлено поле "TI" сегмента.

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

Например, сегменты в очереди передачи: {к, к+1, к+2, к+3, к+4, ...} и узел получает подтверждение {к+3}, из очереди удаляются сегменты к, к+1, к+2.

Если сегмент содержит данные, то он помещается в приемную очередь, после чего приемная очередь сканируется, из нее убираются (передаются пользователю) сегменты, полученные в непрерывной последовательности порядковых номеров. Затем генерируется подтверждение следующего ожидаемого получателем сегмента, в поля которого заносятся следующие значения:

–кумулятивное подтверждение,

–номер последнего полученного сегмента,

–свободное пространство в очереди приема.

Например, в очереди приема находятся сегменты {i+1, i+2, i+3}, после получения i-ro сегмента и его записи в очередь, из нее удаляются сегменты i, i+1, i+2, i+З и значение кумулятивного подтверждения становится равным i+4. Прототип контрольного сегмента с подтверждением ста-

вится на очередь к передаче. При обработке прерывания обновляется значение внутреннего счетчика времени экземпляра объекта протокола, вычисляется текущая скорость передачи потока.

Вычислив значение межсегментного интервала, алгоритм определяет, прошло ли это время с момента отправки предыдущего сегмента. Если да, то запрашивается экземпляр очереди передачи на предмет наличия в ней готового к отправке сегмента. Сегмент для отправки берется из очереди или создается новый (в случае отсутствия готового сегмента в очереди), после чего в соответствующие поля заносятся значения из прототипа контрольного сегмента и сегмент передается объекту узла для передачи. Если передача успешна, то узел, уведомляет об этом объект протокола, который отмечает соответствующий сегмент как отправленный. На рис. 6 представлен график зависимости скорости отправки потока от времени. Sending rate -устанавливаемая скорость отправки, measured received rate - измеряемая скорость приема потока.

Рис.6. График зависимости скорости отправки потока от времени.

В некоторых работах приводятся более сложные системы визуализации, например в [2, 3, 5]. В настоящей работе на рис. 6, 7, 8 результаты моделирования наиболее наглядно представляются следующими способами: зависимость скорости потока, порядкового номера передаваемого сегмента, времени RTT, средней длины очереди от времени.