Коммуникационные и компьютерные сети. Анализ архитектуры и режимов функционирования

Распределенные системы, в том числе компьютерные сети, WWW, сотовые и ad-hoc-системы связи и т. п., обычно обладают сложной топологией. Недавние исследования показали, что они представляют собой результат действия самоорганизующихся процессов, управляемых общими, довольно простыми законами. Их свойства резко отличаются от свойств случайных сетей.

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

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

Для изучения подобных явлений в сложных сетях необходим адекватный теоретический аппарат. Работы по его созданию и применению интенсивно ведутся. Недавно в журнале «Physica A» для координации исследований в этой области открыт специальный раздел «Сложные системы и сети».

Одним из интересных подходов к анализу таких объектов являются модели малого мира (small world models), смысл которых можно объяснить на следующем примере. Население земного шара 12 декабря 1999 года достигло 6 миллиардов человек. Тем не менее, несмотря на огромное число людей на планете, структура социальных сетей такова, что все мы очень тесно связаны друг с другом [2-4]. Оказывается, два случайно выбранных человека, как правило, связаны весьма короткой цепочкой промежуточных знакомств. Типичная длина такой цепочки около шести звеньев. На жаргоне это явление называется эффектом малого мира.

Первой попыткой объяснения эффекта малого мира было использование модели случайного графа. Предположим, что имеется сообщество, состоящее из N членов. В среднем каждый из них имеет z знакомств (рис. 1а). Это означает, что во всем сообществе имеется Nz / 2 контактов между людьми. Модель предполагает, что эти связи устанавливаются между случайно выбранными парами. Оказалось, что такая модель действительно демонстрирует эффект малого мира. Средняя длина D цепочки, соединяющей двух случайных людей, согласно этой модели равна D = lg N / lg z. Поскольку lg N медленно увеличивается с ростом N, D также мало даже для очень больших систем.

В качестве примера изучались свойства сети гиперссылок между документами в WWW. К моменту проведения исследований в Сети имелось N ~ 8•10⁸ документов. Средняя же длина цепочки («расстояние» между документами) составляла около 19.

Однако модель случайных графов не определяет всех свойств реальных сетей. В частности, она не предсказывает кластеризацию в сети. В случайном графе вероятность того, что две персоны будут знакомы между собой, не зависит от того, какие персоны выбраны. С другой стороны, кластеры (группы связанных между собой элементов) существуют во многих реальных сетях. Можно ввести коэффициент кластеризации C, представляющий собой среднюю долю таких пар в общем числе пар соседей узла, которые также являются соседями друг друга. В полностью связанной сети, в которой каждый знает каждого, C = 1. В случайном графе C ~ 1 / N, что является очень малой величиной при очень большом размере сети. Было выяснено, что в реальных сетях значение C хотя и много меньше единицы, однако существенно превосходит 1 / N.

Противоположностью случайным графам в некотором смысле являются решетки с полностью упорядоченными связями каждого элемента с некоторым числом соседей (рис. 1б). Легко видеть, что часть непосредственных соседей каждого элемента всегда связана друг с другом, благодаря чему обеспечиваются кластерные свойства сети. Однако такая сеть не обладает эффектом малого мира - из-за отсутствия «дальних» связей.

Оказывается, модель, узлы которой имеют одновременно некоторое количество локальных и случайных «дальних» связей (рис. 1в), демонстрирует и эффект малого мира, и кластеризацию.

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

О применении моделей этого типа для анализа структуры и функционирования сетей связи и компьютерных сетей см. [5-7].

Дата добавления: 2014-01-11