Маршрутизация малого мира - Small-world routing

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

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

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

Создание справочной базы

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

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

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

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

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

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

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

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

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

Некоторые структурированные одноранговые системы, основанные на DHT, часто реализуют варианты топологии Kleinberg Small-World для обеспечения эффективной маршрутизации в одноранговой сети с ограниченными степенями узлов.^[3]

Смотрите также

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

Рекомендации

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