Алгоритм маршрутизации MENTOR
 | Эта статья в значительной степени или полностью опирается на один источник . ( декабрь 2020 г. ) |
Алгоритм маршрутизации MENTOR представляет собой алгоритм , используемый при маршрутизации ячеистых сетей , в частности, в отношении их исходной топологии . Он был разработан в 1991 году Аароном Кершенбаумом, Парвизом Кермани и Джорджем А. Гроувом и опубликован IEEE.
Сложность
[ редактировать ]Эмпирические наблюдения показали, что класс сложности этого алгоритма равен O(N²) или квадратичный . Это представляет собой «значительное улучшение по сравнению с используемыми в настоящее время алгоритмами, [но при этом давая] решения, качество которых конкурирует с другими, гораздо более медленными процедурами».
Методология
[ редактировать ]Алгоритм предполагает, что три вещи способствуют низкозатратной (то есть минимальной по пройденному расстоянию и времени между пунктами назначения) топологии: пути будут иметь тенденцию быть прямыми, а не окольными; что каналы будут иметь «высокую загрузку» — то есть они будут использоваться почти на максимальной рабочей мощности; и что «по возможности [будут использоваться] длинные каналы с высокой пропускной способностью».
Общий план состоит в том, чтобы отправлять трафик по прямому маршруту между источником и пунктом назначения, когда величина требования достаточно велика, и отправлять его по пути внутри дерева во всех остальных случаях. В первом случае мы достигаем всех трех наших целей — мы используем прямой путь высокой загрузки и высокой мощности. В последнем случае мы удовлетворяем как минимум две последние цели, поскольку максимально агрегируем трафик.
Минимальное связующее дерево , по которому проходит трафик в последнем случае, эвристически определяется алгоритмом Дейкстры и алгоритмом Прима .
Ссылки
[ редактировать ]- Аарон Кершенбаум, Парвиз Кермани, Джордж А. Гровер. «МЕНТОР: Алгоритм топологической оптимизации и маршрутизации ячеистой сети» , IEEE Transactions on Communications , апрель 1991 г. По состоянию на 4 ноября 2007 г.