Введение
Протокол обнаружения и маршрутизации mesh-сети
Протокол маршрутизации OrderOne MANET – это алгоритм, позволяющий компьютерам, взаимодействующим по цифровому радио в mesh-сети, находить друг друга и обмениваться сообщениями по относительно эффективному маршруту. Он был разработан и позиционировался как предназначенный для работы с беспроводными mesh-сетями. Разработчики OON утверждают, что он способен обрабатывать тысячи узлов, в то время как большинство других протоколов поддерживают менее ста. OON использует иерархические алгоритмы для минимизации общего объема передач, необходимых для маршрутизации. Накладные расходы на маршрутизацию ограничены 1–5% пропускной способности между узлами в любой сети и не увеличиваются с ростом размера сети. Основная идея заключается в том, что сеть самоорганизуется в виде дерева. Узлы сходятся к корню дерева для установления первоначального маршрута. Затем маршрут отклоняется от корня, «отсекая углы», подобно муравьиным тропам. Когда больше не остается углов для отсечения, формируется почти оптимальный маршрут. Этот маршрут постоянно поддерживается. Каждый процесс может быть выполнен с использованием локализованной минимальной коммуникации и очень небольших таблиц маршрутизации. OORP требует около 200 КБ памяти. В смоделированной сети из 500 узлов, передающих данные со скоростью 200 байт в секунду, самоорганизация заняла около 20 секунд. По состоянию на 2004 год OORP был запатентован или имел другие существенные ограничения в отношении интеллектуальной собственности. См. ссылку ниже.
Предположения
Каждый компьютер, или "узел" сети, имеет уникальное имя, как минимум одно сетевое соединение и возможность хранить список соседей.
Организация дерева
Сетевые узлы формируют иерархию, выбирая каждый узел своего родителя. Родитель – это соседний узел, являющийся наиболее оптимальным следующим шагом для большинства других узлов. Этот метод создает иерархию вокруг узлов, которые с большей вероятностью будут доступны, обладают большей пропускной способностью и находятся ближе к топологическому центру сети. Ограниченные ресурсы памяти небольшого узла отражаются в его небольшой таблице маршрутизации, что автоматически исключает возможность его выбора в качестве предпочтительного центрального узла. В верхней части иерархии один или два узла не могут найти узлы с лучшей связностью, чем у них самих, и поэтому становятся родителями для всей сети. Алгоритм формирования иерархии не требует сложного протокола маршрутизации или больших объемов обмена данными.
Маршрутизация
Все узлы прокладывают маршрут от себя к корню дерева. Узел, желающий установить соединение, может отправить запрос к корню дерева и всегда найти маршрут. Коммерческий протокол использует алгоритм Дейкстры для непрерывной оптимизации и поддержания маршрута. По мере перемещения и изменения сети, маршрут постоянно корректируется.
Преимущества
Предполагая, что некоторые узлы в сети обладают достаточной памятью для знания обо всех узлах сети, практических ограничений на размер сети нет. Поскольку пропускная способность управления определена как менее 5% вне зависимости от размера сети, объем необходимой пропускной способности управления не должен увеличиваться с ростом размера сети. Система может использовать узлы с небольшим объемом памяти. Сеть располагает надежным и эффективным способом определения отсутствия узла в сети. Это ценное и сложнодостижимое свойство в самоорганизующихся mesh-сетях. Большинство протоколов маршрутизации масштабируются либо за счет уменьшения объема проактивной информации о состоянии каналов связи, либо за счет реактивного управления маршрутизацией по запросам на соединение. OORP сочетает в себе проактивные и реактивные подходы. Правильно настроенная сеть OORP может масштабироваться до сотен тысяч узлов и часто демонстрирует приемлемую производительность, даже при ограничении пропускной способности маршрутизации до 5%.
Критика
Центральные узлы испытывают дополнительную нагрузку, поскольку им требуется достаточно памяти для хранения информации обо всех узлах сети. Следовательно, при определенном количестве узлов сеть перестанет масштабироваться. Если все узлы в сети обладают низкой пропускной способностью, сеть может быть перегружена изменениями. Это может ограничить максимальный масштаб. Однако, в подавляющем большинстве реальных сетей, по мере удаления от периферийных узлов пропускная способность увеличивается. Эти замечания могут оказаться непрактичными. Например, рассмотрим радиоканал с низкой пропускной способностью 9,6 Кбит/с. Если протокол настроен на отправку одного пакета размером 180 байт каждые 5 секунд, он будет потреблять 3% от общей пропускной способности сети. Общедоступные предложения по OON не предусматривают механизмы безопасности или аутентификации. Обеспечение безопасности и аутентификации может быть предоставлено интегратором протокола. Типичные меры безопасности включают шифрование или подпись протокольных пакетов и использование счетчиков для предотвращения атак повторного воспроизведения.