В теории сетей , маршрутизация в маленьком мире относится к методам маршрутизации для сетей в маленьком мире . Сети этого типа отличаются тем, что между любыми двумя узлами существуют относительно короткие пути. Однако определение этих путей может быть сложной проблемой с точки зрения отдельного узла маршрутизации в сети, если о сети в целом не известно никакой дополнительной информации.
Жадная маршрутизация
Почти каждое решение проблемы маршрутизации в маленьком мире включает применение жадной маршрутизации. Такой вид маршрутизации зависит от относительной контрольной точки, с помощью которой любой узел на пути может выбрать следующий узел, который, по его мнению, наиболее близок к месту назначения. То есть должно быть чего жадничать. Например, это может быть географическое положение, IP-адрес и т. Д. В случае первоначального эксперимента Милграма с маленьким миром участники знали местоположение и род занятий конечного получателя и, следовательно, могли пересылать сообщения на основе этих параметров. [ необходима цитата ]
Создание справочной базы
Жадная маршрутизация не сработает, если нет очевидной справочной базы. Это может происходить, например, в оверлейных сетях, где информация о местоположении пункта назначения в базовой сети недоступна. Сети типа " друг другу" - частный пример этой проблемы. В таких сетях доверие обеспечивается тем фактом, что вам известна только основная информация об узлах, с которыми вы уже являетесь соседом. [ необходима цитата ]
Одно из решений в этом случае - наложить на узлы некую искусственную адресацию таким образом, чтобы эта адресация могла эффективно использоваться жадными методами маршрутизации. В статье 2005 года разработчика проекта Freenet обсуждается, как этого можно достичь в сетях « друг другу» . Учитывая предположение, что эти сети демонстрируют свойства небольшого мира, часто в результате реальных или знакомых отношений, должно быть возможно восстановить встроенный граф малого мира Клейнберга . Это достигается путем выбора случайных пар узлов и их возможной замены местами на основе целевой функции, которая минимизирует произведение всех расстояний между любым заданным узлом и его соседями. [ необходима цитата ]
Важной проблемой, связанной с этим решением, является возможность локальных минимумов . Это может произойти, если узлы находятся в ситуации, которая оптимальна только с учетом локального окружения, игнорируя при этом возможность более высокой оптимальности в результате обмена с удаленными узлами. В вышеупомянутой статье авторы предложили метод моделирования отжига, при котором неоптимальные замены выполнялись с небольшой вероятностью. Эта вероятность была пропорциональна стоимости переключения. Другой возможный метод метаэвристической оптимизации - это запретный поиск , который добавляет память к решению о замене . В самой упрощенной форме запоминается ограниченная история прошлых свопов, так что они будут исключены из списка возможных узлов подкачки. [ необходима цитата ]
Этот метод построения справочной базы также может быть адаптирован к распределенным настройкам, где решения могут приниматься только на уровне отдельных узлов, которые не знают обо всей сети. Оказывается, единственная необходимая модификация - это метод выбора пар случайных узлов. В распределенной настройке это достигается за счет того, что каждый узел периодически отправляет случайного блуждающего устройства, заканчивающегося на узле, который будет рассматриваться для замены. [ необходима цитата ]
Модель Клейнберга
Модель сети Клейнберга эффективна для демонстрации эффективности жадной маршрутизации в маленьком мире. Модель использует сетку узлов nxn для представления сети, где каждый узел связан ненаправленным ребром со своими соседями. Чтобы придать ей эффект «маленького мира», к сети добавляется ряд дальних ребер, которые, как правило, предпочитают узлы ближе друг к другу, а не дальше. При добавлении ребер вероятность соединения некоторой случайной вершины другой случайной вершине w пропорционально , где - показатель кластеризации. [1]
Жадная маршрутизация в модели Клейнберга
Легко видеть, что жадный алгоритм без использования дальних ребер может переходить от случайных вершин. на сетке в время. Следуя гарантированным связям с нашими соседями, мы можем перемещать по одному юниту за раз в направлении нашего пункта назначения. Это также относится к случаю, когда компонент кластеризациибольшой, и края «дальнего действия» в конечном итоге остаются очень близко; мы просто не пользуемся более слабыми связями в этой модели. Когда, края дальнего действия равномерно соединены случайным образом, что означает, что края дальнего действия «слишком случайны», чтобы их можно было эффективно использовать для децентрализованного поиска. Клейнберг показал, что оптимальный коэффициент кластеризации для этой модели равен, или обратное квадратное распределение. [2]
Чтобы объяснить, почему это так, если вокруг начального узла провести круг радиуса r, он будет иметь узловую плотность где n - количество узлов в круговой области. По мере того, как этот круг расширяется дальше, количество узлов в данной области увеличивается пропорционально поскольку вероятность наличия случайной связи с любым узлом остается пропорциональной , что означает, что вероятность того, что исходный узел имеет слабую связь с любым узлом на заданном расстоянии, фактически не зависит от расстояния. Таким образом, можно сделать вывод, что при, дальние края равномерно распределяются по всем расстояниям, что позволяет нам эффективно двигаться к нашему конечному пункту назначения. [ необходима цитата ]
Некоторые структурированные одноранговые системы, основанные на DHT, часто реализуют варианты топологии Кляйнберга Small-World, чтобы обеспечить эффективную маршрутизацию в одноранговой сети с ограниченными степенями узлов. [3]
Смотрите также
- Социальная сеть - Социальная структура, состоящая из множества социальных субъектов.
- Сеть малого мира - математический граф, в котором до большинства узлов можно добраться за небольшое количество шагов.
- Модель Ваттс-Строгаца
Рекомендации
- ^ Клейнберг, Джон. «Сети, толпы и рынки: рассуждения о высокосвязном мире» (PDF) . Проверено 10 мая 2011 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Клейнберг, Джон М. (август 2000 г.). «Навигация в маленьком мире» . Природа . 406 (6798): 845. DOI : 10.1038 / 35022643 . ISSN 1476-4687 . PMID 10972276 .
- ^ Манку, Гурмит Сингх Манку. «Симфония: распределенное хеширование в маленьком мире» (PDF) . www.usenix.org .