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

Применение уравнения Колмогорова и перколяционных моделей для описания динамики обработки и передачи стохастических данных в сетях со случайной топологией

Жуков Д.О., Алешкин А.С.

ANNOTATION

In this article presented models of dynamics data transmission with the any law of distribution time between applications. The opportunity of application, for the description such processes of the equation of Kolmogorov. Besides in work considered questions of numerical modelling processes of data transmission in the networks having casual topology.

ВВЕДЕНИЕ

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

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

Вторым важным аспектом является то, что соединение узлов в реальной ИВС происходит случайным образом (сеть имеет случайную структуру) и это также необходимо учесть при моделировании работы ИВС.

В настоящее время при моделировании информационных вычислительных сетей (ИВС) большинство исследователей используют следующие основные подходы, которые достаточно полно описаны в обзоре [1]:

- Описание ИВС с помощью математического аппарата теории массового обслуживания.

- Использование для моделирования работы ИВС аппарата теории графов.

- Исследование работы ИВС с помощью аппарата теории нечетких множеств и нечеткой логики.

- Описание ИВС с использованием аппарата тензорного анализа.

- Использование для моделирования работы ИВС теории фракталов.

Все перечисленные направления исследований имеют как свои достоинства, так и недостатки, которые побуждают искать новые подходы моделирования работы ИВС.

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

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

Для построения динамической модели работы ИВС в представленной работе предлагается провести декомпозицию поставленной задачи и разделить её решение на два уровня:

- Уровень описания динамики обработки заявок на отдельном узле.

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

На первом уровне могут быть получены вероятностные характеристики работы отдельных узлов. А на втором уровне, используя полученные характеристики описания динамики обработки заявок на отдельном узле, построить общую модель работы ИВС.

МОДЕЛИРОВАНИЕ ВЕРОЯТНОСТИ ПЕРЕХОДА УЗЛА СЕТИ В ПЕРЕГРУЖЕННОЕ СОСТОЯНИЕ

Определение вероятности исключения узла (связи) из сети. Поскольку любая связь узла сети участвует как в получении заявок, так и в их передаче, то поток заявок µ_i, поступающих в узел на обработку, и поток заявок л_i, уходящих после обработки, не будут зависеть от числа связей.

В определенный момент времени число заявок, приходящих на i-узел, может превысить некоторый критический порог заявок L (который может быть обслужен или который задан, исходя из правил обеспечения надежной работы), и тогда можно считать, что узел перестает работать (исключается из сети). Будем считать, что узел находится в выключенном из сети (перегруженном) состоянии, если число заявок на нем равно некоторому пороговому значению L.

Для расчета характеристик процесса работы узла введем параметры входного потока, выходного потока и времени обслуживания:

ф₀ - среднее время обслуживания одной заявки

µ_i - среднее число заявок, поступающих на обслуживание в i-узел за единицу времени (входной поток)

л_i - среднее число заявок, покидающих i-узел за единицу времени (выходной поток).

Пусть за время ф₀ на узел приходит е заявок, а покидает одна заявка. Тогда:

.

Работа i-узла (связи) складывается из отдельных шагов h, имеющих среднюю продолжительность ф₀. После каждого шага система может переходить в одно из состояний, задаваемых числом заявок k, находящихся на узле.

Рисунок 1 Схема возможных переходов между состояниями i-узла на h+1 шаге

Пусть, после h шагов работы, P_x-е,h есть вероятность того, что на выбранном i-узле находится x-е заявок; P_x,h есть вероятность того, что на нем находится x заявок и P_x+1,h - находится (x+1) заявка. На одном шаге на узел может поступить некоторое количество заявок, тогда P_x,h+1 - вероятность того, что на h+1 шаге в i-узле будет находиться некоторое число заявок x (см. рисунок 1) будет равна:

P_x+1,h = P_x-е,h + P_x+1,h - P_x,h

введем t = h? ф₀, где t - время работы узла. Получаем:

P(x,t+ф₀) = P(x-е,t)+ P(x+ ф₀л,t) - P(x,t). (1)

Раскладывая уравнение (1) в ряд Тейлора и учитывая в левой части члены, содержащие не более чем первую производную по t, а в правой не более чем вторую производную по x, получим:

. (2)

Вторую производную по t можно исключить, поскольку по своему смыслу она описывает процесс, при котором сами заявки при обработке становятся источниками дополнительных заявок. Поскольку функция P(x,t) является непрерывной, перейдем от вероятности P(x,t) к плотности вероятности с(x,t), проведя операцию , что позволяет сформулировать следующую граничную задачу.

При числе заявок на узле x = L узел прекращает работу. Сама вероятность обнаружить такой узел будет отлична от 0. Однако плотность вероятности, определяющую поток заявок в состоянии x = L, необходимо положить равной 0 (мы стремимся избежать этого состояния), т.е.

. (a)

Второе граничное условие выберем, исходя из следующих соображений: состояние x = 0 определяет простой в работе узла вследствие того, что заявки по какой-либо причине на узел не приходят и не уходят с него, и данный узел также будет исключенным. Сама вероятность обнаружить такой узел будет отлична от 0, однако плотность вероятности, определяющую поток заявок в состоянии , необходимо положить равной 0 (так как мы стремимся избежать этого состояния), т.е.

. (b)

Cчитая, что µ и л от x не зависят и введя обозначение и , получим:

. (3)

Поскольку в момент времени t = 0 на любом i-узле уже может находиться x_i-заявок, то начальное условие зададим в виде:

,

что приводит к тому, что решение уравнения (2) и (3) оставаясь непрерывными в точке x = x₀, будет испытывать в ней разрыв производной.

Используя методы операционного исчисления для плотности вероятности с(x,t) исключения узла из сети, можно получить следующие решения:

при x > x_i

(4)

при x ? x_i

. (5)

Определение вероятности исключения узла (связи) из сети. Уравнения (4) и (5) описывают поведение плотности вероятности обнаружения состояния i-узла сети в одном из значений на отрезке от 0 до L. Отметим, что состояния узла могут принимать только целочисленные значения, однако (4) и (5) задают непрерывные распределения, что, тем не менее, не отвергает возможности их использования, поскольку эти уравнения могут быть дополнены условием, что значимыми являются только значения, полученные для целых величин x. Поэтому все результаты, представленные далее на рисунках кривыми моделирования, можно рассматривать, как заданные поточечно для целых значений х.

Если вычислить интеграл P(L,t):

, (6)

то функция P(L,t) будет задавать вероятность того, что состояние i-узла к моменту времени t будет находиться на отрезке от 0 до L, т.е. узел будет находиться в невыключенном состоянии.

Соответственно, вероятность Q_i(t) того, что узел окажется к моменту времени t выключенным, можно определить следующим образом:

. (7)

ОБРАЗОВАНИЕ ГРУП ПЕРЕГРУЖЕННЫХ УЗЛОВ В СЕТЯХ СО СЛУЧАЙНОЙ ТОПОЛОГИЕЙ

информационный вычислительный сеть моделирование

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

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

В определенном смысле ИВС можно рассматривать как некую структуру или среду, между узлами которой происходит протекание данных.

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

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

Случайная сеть Кейли. Исследования показали, что для доли узлов, входящих в кластеры малых размеров, наблюдается некоторое отличие для регулярной и случайной сетей Кэйли. Однако для среднего размера кластеров перегруженных узлов и зависимости количества областей неперегруженных узлов от вероятности Q_i наблюдается полное совпадение результатов для сети Кэйли, со случайным числом связей на узлах, с результатами для регулярной сети Кэйли с числом связей на одном узле Z = 3 (см. рис.3). Увеличение числа возможных связей для одного узла в сетях Кейли не изменяет их общего среднего значения, т.к. доля узлов, находящихся на границах сети и имеющих только по одной связи с соседями, увеличивается таким образом, что среднее значение числа связей всегда стремится к пределу, равному 2.

Рисунок 2 Зависимость среднего размера кластеров перегруженных узлов от вероятности Q_i для сетей с регулярной и случайной структурой при разных значениях среднего числа связей

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

В то же время число областей перегруженных узлов с ростом величины вероятности Q_i уменьшается при увеличении среднего числа связей (чем меньше связей, тем более вероятно разделение сети на несвязанные области).

Аналогом сети Кэйли со случайным числом связей на одном узле является регулярная сеть Кэйли. В связи с этим возникает вопрос, а к какому типу регулярных сетей можно отнести решетку, в которой каждый узел имеет множество случайных связей с другими узлами. При рассмотрении случайной сети со средним числом связей, лежащем в диапазоне от 3,80 до 7,27, можно обратиться к рис.2, на котором представлены зависимости среднего размера кластеров исключенных узлов от вероятности Q_i для различных сетей. Легко заметить, что произвольная сеть со средним числом связей 5,72 (кривая 3 на рис.2) близка к треугольной сети (среднее число связей 5,86, кривая 2 на рис.2), а произвольная сеть со средним числом связей 4,79 (кривая 4 на рис.2) близка к квадратной решетке (среднее число связей 3,93, кривая 5 на рис.2), произвольная сеть со средним числом связей 3,80 (кривая 6 на рис.2) к шестиугольной (среднее число связей 2,95, кривая 7 на рис.2).

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

ВЫВОДЫ

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

Таким образом, использование методов математического моделирования позволяет проанализировать динамику процессов стохастической обработки заявок на узлах ИВС и определить зависимость вероятности Q_i достижения на узле перегруженного состояния (критического порога L обрабатываемых заявок) от величины текущего значения входных и выходных потоков и времени процесса. Значения величин Q_i может быть использовано для описания передачи данных в ИВС на уровне, учитывающем топологию всей сети.

ЛИТЕРАТУРА

1. Макаренко, С.И. Анализ математического аппарата расчета качества обслуживания информационно-вычислительной сети на сетевом уровне эталонной модели взаимодействия открытых систем [Текст] / С.И. Макаренко // Сб. науч. тр. «VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям». Красноярск: ИВТ СО РАН, 2006. 102 с.

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