Введение

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

Жадный маршрут

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

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

Жадный маршрутизатор не будет работать, если нет очевидной базовой информации. Это может произойти, например, в накладной сети, где информация о местоположении пункта назначения в базовой сети не доступна. Сети друзей-друзей являются примером этой проблемы. В таких сетях доверие обеспечивается тем, что вы знаете только основную информацию о узлах, с которыми вы уже соседи. Одно из решений в этом случае - навязать какой-то искусственный адрес на узлах таким образом, чтобы этот адрес мог эффективно использоваться методами жадного маршрутизации. В статье 2005 года разработчиком проекта Freenet обсуждается, как это может быть достигнуто в сетях "друг к другу". Учитывая предположение, что эти сети демонстрируют свойства малого мира, часто в результате реальных или знакомых отношений, должно быть возможно восстановить встроенный график малого мира Клейнберга. Это достигается путем выбора случайных пар узлов и потенциального их обмена на основе объективной функции, которая минимизирует произведение всех расстояний между любым данным узлом и его соседями. Важной проблемой, связанной с этим решением, является возможность местных минимумов. Это может произойти, если узлы находятся в оптимальной ситуации, учитывая только местный район, игнорируя возможность более высокой оптимальности, возникающей в результате обмена с удаленными узлами. В вышеуказанной статье авторы предложили симулированный метод отжига, при котором с небольшой вероятностью производились менее оптимальные свопы. Эта вероятность была пропорциональна стоимости совершения переключений. Другим возможным методом метаевристической оптимизации является табуированный поиск, который добавляет память к решению обмена. В своей наиболее упрощенной форме, ограниченная история прошлых свопов запоминается, так что они будут исключены из списка возможных узлов обмена. Этот метод построения справочной базы также может быть адаптирован к распределенным настройкам, где решения могут приниматься только на уровне отдельных узлов, которые не имеют знаний об общей сети. Оказывается, что единственная необходимая модификация - это метод выбора пар случайных узлов. В распределенной среде это делается путем периодического отправления каждым узлом случайного ходока, заканчивающегося на узле, который будет рассматриваться для обмена.

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

Модель сети Клейнберга эффективна в демонстрации эффективности алчного маршрутизации в малом мире. Модель использует сетку звеньев n x n для представления сети, где каждый узел соединен с ненаправленным краем со своими соседями. Чтобы создать эффект "маленького мира", в сеть добавляется ряд краев большого диапазона, которые, как правило, предпочитают узлы, расположенные ближе по расстоянию, а не дальше. При сложении краев вероятность соединения некоторой случайной вершины с другой случайной вершиной w пропорциональна , где экспонент кластеризации.

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

Легко увидеть, что жадный алгоритм, не используя краев длинного диапазона, может перемещаться со случайных вершин на сетке во времени. Следуя гарантированным соединениям с нашими соседями, мы можем двигаться по одной единице в направлении нашего назначения. Это также относится к случаям, когда кластерная составляющая большая, а края "длинного диапазона" в конечном итоге остаются очень близкими; мы просто не используем слабые связи в этой модели. Когда , края длинного диапазона однородно соединены случайным образом, что означает, что края длинного диапазона "слишком случайны", чтобы эффективно использоваться для децентрализованного поиска. Клейнберг показал, что оптимальным коэффициентом кластеризации для этой модели является , или обратное квадратное распределение. Чтобы понять, почему это так, если круг радиуса r будет нарисован вокруг начального узла, он будет иметь узловую плотность, где n - количество узлов в круговой области. По мере того, как этот круг расширяется дальше, число узлов в данной области увеличивается пропорционально тому, как вероятность наличия случайной связи с любым узлом остается пропорциональной, то есть вероятность того, что исходный узел имеет слабую связь с любым узлом на данном расстоянии, эффективно независима от расстояния. Поэтому можно сделать вывод, что с , края дальности равномерно распределены по всем расстояниям, что эффективно для того, чтобы позволить нам воронку к нашему конечному назначению. Некоторые структурированные системы Peer to peer, основанные на DHT, часто реализуют варианты топологии Kleinberg's Small World, чтобы обеспечить эффективную маршрутизацию в Peer to Peer сети с ограниченными степенями узлов.