Маршрутизация маленького мира

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

Жадная маршрутизация

Почти каждое решение проблемы маршрутизации в маленьком мире предполагает применение жадной маршрутизации. Этот вид маршрутизации зависит от относительной контрольной точки, с помощью которой любой узел на пути может выбрать следующий узел, который, по его мнению, находится ближе всего к месту назначения. То есть должно быть чему жадничать. Например, это может быть географическое положение, IP-адрес и т. д. В случае оригинального эксперимента Милгрэма с маленьким миром участники знали местоположение и род занятий конечного получателя и, следовательно, могли пересылать сообщения на основе этих параметров. ^{[ нужна ссылка ]}

Построение справочной базы

Жадная маршрутизация не будет работать, если нет очевидной ссылочной базы. Это может произойти, например, в наложенных сетях , где информация о местоположении пункта назначения в базовой сети недоступна. Сети «друг-друг» являются частным примером этой проблемы. В таких сетях доверие обеспечивается тем фактом, что вы знаете только основную информацию об узлах, с которыми вы уже являетесь соседом. ^{[ нужна ссылка ]}

Одним из решений в этом случае является введение какой-то искусственной адресации узлам таким образом, чтобы эта адресация могла эффективно использоваться методами жадной маршрутизации. В статье 2005 года, написанной разработчиком проекта Freenet, обсуждается, как этого можно добиться в сетях «друг другу» . Учитывая предположение, что эти сети обладают свойствами маленького мира, часто в результате отношений реального мира или знакомств, должно быть возможно восстановить встроенный Кляйнберга граф маленького мира . Это достигается путем выбора случайных пар узлов и потенциальной замены их местами на основе целевой функции , которая минимизирует произведение всех расстояний между любым данным узлом и его соседями. ^{[ нужна ссылка ]}

Важной проблемой, связанной с этим решением, является возможность существования локальных минимумов . Это может произойти, если узлы находятся в ситуации, оптимальной только с учетом локальной окрестности, игнорируя при этом возможность более высокой оптимальности в результате обмена с удаленными узлами. В приведенной выше статье авторы предложили метод моделирования отжига , при котором с небольшой вероятностью производились неоптимальные замены. Эта вероятность была пропорциональна ценности переключения. Другой возможный метаэвристической метод оптимизации — это поиск с табу , который добавляет память к решению об обмене. В наиболее упрощенной форме запоминается ограниченная история прошлых обменов, поэтому они исключаются из списка возможных узлов обмена. ^{[ нужна ссылка ]}

Этот метод построения эталонной базы также можно адаптировать к распределенным условиям, где решения могут приниматься только на уровне отдельных узлов, не имеющих знаний об общей сети. Оказывается, единственная необходимая модификация — это метод выбора пар случайных узлов. В распределенной среде это достигается за счет того, что каждый узел периодически отправляет случайный блуждающий объект, заканчивающийся на узле, который рассматривается для замены. ^{[ нужна ссылка ]}

Модель Кляйнберга

Модель сети Кляйнберга эффективна для демонстрации эффективности жадной маршрутизации маленького мира. Модель использует сетку узлов nxn для представления сети, где каждый узел соединен ненаправленным ребром со своими соседями. Чтобы придать ей эффект «тесного мира», в сеть добавляется ряд ребер дальнего действия, которые имеют тенденцию отдавать предпочтение узлам, расположенным ближе по расстоянию, а не дальше. При добавлении ребер вероятность соединения некоторой случайной вершины $v$ другой случайной вершине w пропорциональна $1/d(v,w)^{q}$ , где $q$ – показатель кластеризации. ^[1]

Жадная маршрутизация в модели Кляйнберга

Легко увидеть, что жадный алгоритм , не используя ребра большого радиуса действия, может перемещаться из случайных вершин. $v\rightarrow w$ на сетке в $O(n)$ время. Следуя гарантированным связям с нашими соседями, мы можем перемещать по одному объекту за раз в направлении пункта назначения. Это также имеет место, когда компонент кластеризации $q$ большой, и края «дальнего радиуса действия» в конечном итоге остаются очень близкими; мы просто не пользуемся более слабыми связями в этой модели. Когда $q=0$ , дальние края соединены равномерно случайным образом, что означает, что дальние края «слишком случайны», чтобы их можно было эффективно использовать для децентрализованного поиска. Клейнберг показал, что оптимальный коэффициент кластеризации для этой модели равен $q=2$ или обратное квадратичное распределение. ^[2]

Чтобы объяснить, почему это так, если вокруг начального узла нарисовать круг радиуса r, он будет иметь плотность узлов. $n/(\pi r^{2})$ где n — количество узлов в круговой области. По мере дальнейшего расширения этого круга количество узлов в данной области увеличивается пропорционально $r^{2}$ поскольку вероятность наличия случайной связи с любым узлом остается пропорциональной $1/r^{2}$ , что означает, что вероятность того, что исходный узел имеет слабую связь с любым узлом на заданном расстоянии, фактически не зависит от расстояния. Таким образом, делается вывод, что с $q=2$ дальние края равномерно распределены по всем расстояниям, что эффективно позволяет нам направиться к конечному пункту назначения. ^{[ нужна ссылка ]}

Некоторые структурированные одноранговые системы, основанные на DHT, часто реализуют варианты топологии «Маленький мир» Кляйнберга, чтобы обеспечить эффективную маршрутизацию в одноранговой сети с ограниченными степенями узлов. ^[3]

См. также

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

Ссылки

^ Кляйнберг, Джон. «Сети, толпы и рынки: размышления о мире с высокой степенью взаимосвязанности» (PDF) . Проверено 10 мая 2011 г.
^ Кляйнберг, Джон М. (август 2000 г.). «Навигация в маленьком мире» . Природа . 406 (6798): 845. Бибкод : 2000Natur.406..845K . дои : 10.1038/35022643 . ISSN 1476-4687 . ПМИД 10972276 .
^ Манку, Гурмит Сингх Манку. «Симфония: распределенное хеширование в маленьком мире» (PDF) . usenix.org .

[1] Кляйнберг, Джон. «Сети, толпы и рынки: размышления о мире с высокой степенью взаимосвязанности» (PDF) . Проверено 10 мая 2011 г.

[2] Кляйнберг, Джон М. (август 2000 г.). «Навигация в маленьком мире» . Природа . 406 (6798): 845. Бибкод : 2000Natur.406..845K . дои : 10.1038/35022643 . ISSN 1476-4687 . ПМИД 10972276 .

[3] Манку, Гурмит Сингх Манку. «Симфония: распределенное хеширование в маленьком мире» (PDF) . usenix.org .

[1]

[2]

[3]