Geum.ru

А. В. Савостьянова московский государственный университет приборостроения и информатики анализ влияния топологии регулярных информационно-вычислительных сетей на надежность их работы с использованием теории перколяции вдоклад

Вид материалаДоклад
Подобный материал:

Д.О. ЖУКОВ, А.С. АЛЕШКИН, А.В. САВОСТЬЯНОВА

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


АНАЛИЗ ВЛИЯНИЯ ТОПОЛОГИИ РЕГУЛЯРНЫХ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
НА НАДЕЖНОСТЬ ИХ РАБОТЫ С ИСПОЛЬЗОВАНИЕМ ТЕОРИИ ПЕРКОЛЯЦИИ


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


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

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

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

Если задана вероятность Qi – того, что число заявок на данном узле ИВС достигает критическое значение L, то можно ввести плотность вероятности ns(Qi) того, что произвольно выбранный узел принадлежит кластеру узлов размера S, достигших критического значения числа заявок L. В общем случае функция  задается следующим выражением:



где S – размер кластера (число входящих в него узлов), t – периметр кластера (число неперегруженных узлов, полностью окружающих кластер),  – число возможных конфигураций кластеров имеющих по S узлов с периметром t. Функция , задающая распределения кластеров по размерам позволяет вычислить ряд важных характеристик, например: долю узлов в сети узлов, входящих в кластер размера S, долю исключенных из сети узлов, на которых число заявок достигает критическое значение, средний размер кластера исключенных узлов.

Геометрический анализ ряда регулярных структур, таких, как сеть Кейли, квадратная, треугольная, шестиугольная решетки и решетка типа3,122 позволяет получить при небольших размерах кластеров аналитические выражения для функции .

Анализ полученных функций  показывает:
  1. При описании ИВС имеющей регулярную структуру можно использовать подходы и методы принятые в теории перколяции.
  2. При некоторых значениях Qi, меньших, чем величина порога перколяции, плотность вероятности образования кластеров узлов (на которых число заявок достигает критический порог L), достигает максимума, и это необходимо учитывать при описании работы ИВС. Сравнение результаты расчетов доли узлов, входящих в кластер размера 2, для квадратной решетки, треугольной решетки, шестиугольной решетки и дерева Кейли показало, что наибольшее значение для доли исключенных узлов наблюдается для сети Кэйли, затем идет шестиугольная решетка, а наименьшее значение имеет треугольная и квадратная решетки. Таким образом, наибольшее образование кластеров, состоящих из 2-х узлов, при увеличении Qi будет наблюдаться в сети Кэйли и шестиугольной решетке, а наименьшее – в квадратной и треугольной структурах.
  3. При малых значениях вероятности Qi (0,01 ÷ 0,05) – достижения критического порога числа заявок на отдельном узле происходит образование кластеров малых размеров, и этот процесс практически не зависит от топологии рассматриваемых структур.