Динамическое управление информационными процессами в распределенных управляющих системах

Размещено на http: //www. allbest. ru/

Аппарат полномочного представителя в Уральском федеральном округе Россия, г. Екатеринбург, тел.8-343 -247-75-92

Динамическое управление информационными процессами в распределенных управляющих системах

Еременко А.В., Чистяков М.В.

Annotatіon

Problems of dynamic optimization for information processes are intended for the decision of questions about management by distribution of streams information messages (packages) and volume of these streams in dynamics of functioning of the allocated managing systems. In this article some of the common approaches to the decision of problems with the such sort are considered. Thus questions of management by distribution of streams (a problem of routing) and volume of these streams (a problem of management of a stream) are separately discussed.

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

Считается, что в канал поступает поток заявок (пакетов) интенсивностью лi, пропускная способность канала постоянна и равна Ci, а последующие заявки имеют в среднем длину 1/м. Предполагается также, что при коммутации пакетов имеются неограниченные возможности для их буферирования (длина очереди на канал не ограничена).

В этом случае преобразование Лапласа - Стилтьеса функции распределения времени задержки (пребывания) пакетов на канале запишется так:

(1)

а среднее значение этой величины

(2 )

3десь pi - загрузка канала

Предположение о независимости, приемлемость которого для инженерных расчетов характеристик обслуживания заявок в РУС была доказана на обширном фактическом материале [5], позволяет оценивать сквозные задержки для пары абонентов отправитель - получатель. Допустим, что РУС удовлетворяет условию отсутствия опережения, т. е. для произвольной пары каналов i, j пакеты, поступающие по некоторому маршруту L в канал i после выделенного пакета, никогда не опережают этого пакета в канале j. В этом случае преобразование Лапласа - Стилтьеса функции распределения времени задержки пакетов для пары абонентов при фиксированных маршрутах пакетов выразится следующим образом [3]:

(3)

Соответственно среднее значение и дисперсия задержки вычисляются, как

(4)

Описанный подход позволяет учитывать многие реально существующие в РУС ограничения и свойства [3]. Так, предполагая экспоненциальный характер распределения “ценности” заявки во времени, получаем на основании общих свойств преобразования Лапласа - Стилтьеса, что вероятность своевременной доставки пакета

(5)

где - интенсивность обесценивания пакета.

В предположении экспоненциального распределения времени коммутации с параметром г вероятность своевременной доставки пакета

(6)

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

Пусть хjk1 - средняя задержка для однопакетного ИС, представляющего ИП с начальным состоянием (этапом) в узле j и конечным в узле k (путь Ljk) На основании изложенного выше для случая фиксированных маршрутов можно записать

(7)

где фi1 определяется в соответствии, например, с (2).

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

(8)

где N - число узлов сети.

Поскольку величина лjk/л определяет долю от общего числа поступающих в сеть пакетов, имеющих среднюю задержку v}k\, то задержка, усредненная по всем возможным ИП, выразится как

(9)

Учитывая (7), а также тот факт, что средняя интенсивность потока пакетов, проходящих через i-й канал, определяется суммой средних интенсивностей потоков пакетов для всех ИП, использующих этот канал, т. е.

где L i- множество ИП, использующих канал i, получаем

Подставляя выражение для фi1, например, из (2), имеем

(10)

Соотношение (10) используется при решении многих задач оптимизации ИП на уровне сети.

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

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

Коммуникационные системы (КС) в узлах РУС являются реальными устройствами и имеют ограниченные возможности по обработке сообщений (пакетов). Если число сообщений в сети чрезмерно велико, то возникает перегрузка. В результате наблюдается значительное ухудшение временных характеристик обслуживания абонентов и даже может сложиться ситуация, когда передача сообщений в РУС становится невозможной из-за различного рода блокировок. В самом деле, сообщение в узле назначения не может быть обработано до тех пор, пока не поступят все пакеты, составляющие данное сообщение. При больших потоках сообщений память КС в некотором узле может оказаться переполненной пакетами разных сообщений, ожидающими “сшивки”. Это, в свою очередь, вызовет переполнение памяти КС в узлах, предшествующих данному, так как пакеты из этих узлов :не могут быть выданы в данный узел и т. д. Таким образом, передача сообщений в РУС блокируется. Существуют ,и другие виды блокировок [4].

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

В первом случае процессы управления реализуются на канальном уровне семиуровневой архитектуры, во втором и третьем - на сетевом Для каждого из указанных вариантов организации управления потоком разработаны достаточно эффективные методы реализации [1,5]

Наиболее просто задачи управления потоком решаются путем ограничения доступа к РУС (глобальное управление) для режима коммутации пакетов виртуального режима Здесь объем поступающих в РУС потоков ограничивается числом виртуальных маршрутов. В случае же дейтаграммного режима при глобальном управлении вводят ограничение на общее число пакетов, которые могут находиться в РУС.

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

В одном случае при достижении узла назначения пакетом разрешение “освобождается” и отдается другому пакету, ожидающему передачи. Если же в узле нет таких пакетов, разрешение циркулирует по РУС случайным образом и отдается при встрече пакету, ожидающему передачи. В другом случае, в каждом узле существует некоторое множество разрешений, которые и используются для передачи пакетов, возникающих в данном узле

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

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

математический экспоненциальный сеть динамический

Литература

1. Шварц М. Сети связи: протоколы, моделирование и анализ. Часть 1. Пер. с англ. - М.: Наука. Гл. ред. физ.-мат. лит., 1992. - 272 с.

2. Клейнброк Л. вычислительные системы с очередями. - М.: Мир, 1979. 600 с.

3. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи. - М.: Радио и связь, 1983. -216 с.

4. Мельников Д. А. Информационные процессы в компьютерных сетях. Протоколы, стандарты, интерфейсы, модели. - М.: КУДИЦ-ОБРАЗ, 1999. - 256 с.

5. Колганов С.К., Корников В.В., Попов П.Г., Хованов Н.В. Построение в условиях дефицита информации сводных оценок сложных систем. - М.: Радио и связь, 1994. - 79 с.

Размещено на Allbest.ru