Алгоритм маршрутизации MENTOR - MENTOR routing algorithm

В Алгоритм маршрутизации MENTOR является алгоритм для использования в маршрутизация из ячеистые сети, особенно в отношении их начального топология. Он был разработан в 1991 году Аароном Кершенбаумом, Парвизом Кермани и Джорджем А. Гроувом и опубликован IEEE.

Сложность

Эмпирическое наблюдение показало, что класс сложности этого алгоритма составляет O (N²), или квадратичный. Это представляет собой «значительное улучшение по сравнению с используемыми в настоящее время алгоритмами, [при этом все еще предлагая] решения, качество которых не уступает другим, гораздо более медленным процедурам».

Методология

Алгоритм предполагает, что три вещи способствуют низкой «стоимости» (то есть минимальное пройденное расстояние и время между пунктами назначения): что пути будут иметь тенденцию быть прямыми, а не окольными; что ссылки будут иметь «высокую загрузку», то есть они будут использоваться почти на полную мощность; и что «по возможности [будут использоваться] длинные каналы с высокой пропускной способностью».

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

В минимальное остовное дерево на какие потоки трафика в последнем случае эвристически определяется Алгоритм Дейкстры и Алгоритм Прима.

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