Новый алгоритм поиска кратчайших путей в сетях вызвал интерес в научном сообществе, но вряд ли заменит классический метод Дейкстры в реальных маршрутизаторах. Исследование утверждает, что превосходит подход, разработанный легендарным ученым Эдсгером Дейкстрой еще в 1959 году и используемый в большинстве учебников по сетевым технологиям.
Алгоритм Дейкстры появился еще до изобретения коммутации пакетов и лег в основу двух доминирующих протоколов маршрутизации — OSPF и IS-IS. Спецификация OSPF настолько детально описывает реализацию, что фактически предписывает использовать именно метод Дейкстры. Именно так делали десятилетиями, внося лишь незначительные улучшения для ускорения работы.
Новый алгоритм представляет собой не мелкую доработку, а принципиально иной подход. Его главное достижение — преодоление так называемого «барьера сортировки». В отличие от метода Дейкстры, который требует операции сортировки и ограничен производительностью лучших алгоритмов сортировки, новое решение обходится без нее и демонстрирует лучшие теоретические показатели.
Работа прошла рецензирование на престижной конференции ACM Symposium on the Theory of Computing, и теоретическая корректность алгоритма не вызывает сомнений. Вопрос в другом — насколько это важно на практике?
Время работы алгоритма Дейкстры составляет порядка n log n + m для сети из n вершин (маршрутизаторов) и m ребер (каналов связи). Новый подход демонстрирует порядок m log2/3 n, что явно меньше при достаточно больших n. Проблема в том, что для оценки масштабируемости нужно понимать, насколько большим должно быть n, чтобы разница стала заметной. При небольших значениях менее масштабируемое решение может работать даже быстрее из-за различий в константных факторах.
История показывает, что иногда практическая польза достигается и без максимальной масштабируемости. В девяностые годы компания FORE Systems успешно продавала 16-портовые коммутаторы, в то время как исследователи из Bellcore тратили время и деньги на разработку прототипов 32-портовых устройств с лучшей масштабируемостью. Оказалось, что n=16 вполне достаточно для коммутаторов со 155-мегабитными каналами того времени.
Какое же значение n считается большим для расчетов кратчайших путей? По данным коллег из индустрии, в крупнейших сетях провайдеров сегодня работает несколько тысяч маршрутизаторов. Это немало, но значительно меньше, чем количество префиксов в BGP. И похоже, что размер сетей ограничен не производительностью расчета кратчайших путей.
Важный момент — время расчета SPF это лишь один из многих факторов, влияющих на производительность протоколов маршрутизации. При работе над технологией быстрого перенаправления MPLS выяснилось, что самое важное для быстрого восстановления после сбоя — это скорость обнаружения самого сбоя. Если приходится ждать десятки секунд пропущенных Hello-пакетов OSPF, прежде чем объявить канал неработающим, не имеет значения, можете ли вы рассчитать кратчайший путь за доли секунды. Именно поэтому был создан BFD — быстрый механизм обнаружения отказов, независимый от протокола маршрутизации.
Кроме быстрого обнаружения отказов, на время сходимости маршрутизации влияют время отправки пакета состояния канала, задержка распространения по сети, время получения и обработки пакета операционной системой, обновление таблицы маршрутизации, расчет изменений в таблице пересылки, загрузка обновлений на линейные карты в больших маршрутизаторах, рассылка пакетов состояния соседям. Все эти этапы анализировались и оптимизировались годами, так что сходимость маршрутизации менее чем за секунду стала обычным делом. Уже к 2003 году улучшения всех перечисленных шагов обеспечили субсекундную сходимость. Да, нельзя было позволить себе тратить десять секунд на расчет SPF при стремлении к быстрой сходимости, но эта проблема уже была решена. Оптимизация остальных частей оказалась не менее важной, чем ускорение расчета кратчайших путей.
Есть и еще одна причина, по которой алгоритм Дейкстры остается методом выбора при реализации — его могут понять люди, которым предстоит писать код. Сам Дейкстра в интервью 2001 года хорошо это объяснил: «Публикация до сих пор читабельна, она действительно хороша. Одна из причин в том, что я спроектировал алгоритм без карандаша и бумаги. Позже я понял, что одно из преимуществ проектирования без карандаша и бумаги заключается в том, что вы почти вынуждены избегать всех необязательных сложностей».
Другими словами — не усложняй без необходимости. Гораздо проще направить инженера к спецификации OSPF, чем отправить его разбираться в гибридном подходе Беллмана-Форда и Дейкстры, который может сэкономить несколько миллисекунд на некритичной части процесса сходимости маршрутизации. Возможно, когда-нибудь кто-то напишет объяснение нового алгоритма SPF столь же понятное, как оригинальная работа Дейкстры и спецификация OSPF. И гибридный алгоритм может отлично подойти для крупных картографических приложений. Но замену алгоритму Дейкстры в промышленных маршрутизаторах в ближайшее время ожидать не стоит.