Алгоритм Дейкстры не будет заменен в серийных маршрутизаторах • –

1770703443
2026-02-10 05:47:00

базовое исследование претендует на улучшение классического подхода, впервые предложенного Дейкстра этому учат в большинстве учебников по сетевым технологиям (в том числе наш). Поначалу я был настроен немного скептически, как и если бы прочитал, что Гипотеза Римана было доказано.

Дейкстра — легенда компьютерных наук, и его алгоритм, который он опубликовал в 1959 году, появился на несколько лет раньше коммутации пакетов. спецификация для OSPF (Сначала откройте кратчайший путь (OSPF), один из двух доминирующих протоколов маршрутизации по состоянию канала (вторым является промежуточная система-промежуточная система, также известная как IS-IS).

Руководство для разработчиков OSPF необычайно подробно и в основном предписывает им использовать алгоритм Дейкстры. И это то, что большинство реализаций делали на протяжении десятилетий, с несколькими незначительными улучшениями на протяжении многих лет, чтобы ускорить внедрение, но без каких-либо реальных изменений в основах.

Новый алгоритм не является незначительной поправкой к алгоритму Дейкстры, а существенно отличается от подхода. Его заголовок гласит, что, хотя Дейкстре требуется операция сортировки и, следовательно, он может работать не хуже лучшего алгоритма сортировки, этот новый подход «ломает барьер сортировки». То есть он позволяет избежать необходимости сортировки и способен обеспечить более высокие оценки производительности, чем Дейкстра.

Хотя я не считаю себя квалифицированным для оценки статьи, описывающей новый алгоритм, она прошла рецензирование на конференции высшего уровня (Симпозиум ACM по теории вычислений) и получил достаточно внимания, так что я не сомневаюсь, что теория работает. Вопрос, который я хочу обсудить здесь: имеет ли это значение?

Когда я попытался оценить последствия теоретического улучшения производительности алгоритмов, мне сразу пришли в голову две основные проблемы. Во-первых, каковы фактические ограничения масштабирования, которые нам необходимо учитывать в реальной системе маршрутизации. Например, время работы алгоритма Дейкстры порядка (п журнал п + м) для сети н вершины (маршрутизаторы) и м ребра (звенья). Новый подход требует порядка (м журнал2/3 п) что явно будет меньше для достаточно большого н. (Мне пришлось пройти курс повышения квалификации по лог-нотации, прежде чем я смог хотя бы написать это предложение с какой-либо уверенностью.) Проблема с оценкой свойств масштабирования чего-либо в том, что вам нужно задаться вопросом, насколько велики н должен получить, прежде чем это изменит ситуацию. Существуют постоянные факторы, которые могут различаться между двумя подходами; в маленьком н, «менее масштабируемый» подход может фактически обеспечить более высокую производительность.

Какой предел масштабирования?

Одной из моих первых работ было участие в создании команды масштабируемый коммутатор пакетов на основе массивов малых переключающих элементов. (Здесь мне пришлось построить случайный SmartNIC). У нас были документы, доказывающие, что мы можем создавать коммутаторы с тысячами портов со скоростью 155 Мбит/с в эпоху, когда общий Ethernet работал со скоростью 10 Мбит/с и еще не был вытеснен коммутируемым Ethernet.

Пока мы в Bellcore тратили много времени и денег на создание набора прототипов 32-портовых коммутаторов, ФОРЭ-системы поставила коммерчески успешные 16-портовые коммутаторы. Почти наверняка они не были такими масштабируемыми, как наш дизайн, но оказалось, что н=16 была весьма полезной емкостью для коммутаторов со скоростью 155 Мбит/с в 1990-х годах. Нам было очень грустно, что наши исследования, похоже, были вытеснены коммерческими продуктами. Мой вывод заключался в том, что к масштабируемости стоит стремиться, но иногда можно добиться хорошего результата с помощью менее масштабируемого решения. Один из моих любимых учебников, «Принципы проектирования компьютерных систем», использует пример остановки супер танки чтобы продемонстрировать пределы масштабирования системы. Тот факт, что супертанкеры имеют предел масштабирования, не мешает им быть основой нефтеперевозок. Вам просто нужно не делать их слишком большими.

Что такое большое значение для н в расчетах SPF? Я связался с парой коллег, чтобы обновить свои воспоминания о том, сколько маршрутизаторов можно найти в большой магистральной сети OSPF или IS-IS. На моей памяти их были сотни; сегодня в крупнейших сетях поставщиков услуг их количество исчисляется небольшими тысячами. Так что это не мелочь, а небольшая по сравнению, скажем, с количеством префиксов, передаваемых в BGP.

И, похоже, это не ограничивается производительностью расчета SPF, как я объясню ниже.

Многогранность производительности

Еще одно воспоминание, оставшееся у меня со времени работы в Big Router, — это анализ всех факторов, влияющих на производительность протоколов маршрутизации. Я работал над MPLS на заре его существования, и нас очень воодушевила технология под названием «быстрая перемаршрутизация» (FRR), которая использует MPLS для перенаправления пакетов по отказавшему каналу, не дожидаясь сходимости маршрутизации после сбоя. Но в то же время люди, ответственные за разработку протокола маршрутизации, усердно работали над улучшением времени сходимости маршрутизации. Оказывается, одной из самых важных вещей как для MPLS, так и для стандартной маршрутизации было просто быстрее обнаружить неисправность. Например, если вам приходится ждать десятки секунд отсутствия пакетов приветствия OSPF, прежде чем объявить канал отключенным, на самом деле не имеет значения, сможете ли вы вычислить кратчайший путь за долю секунды. Это послужило причиной создания BFD (обнаружение двунаправленной пересылки): быстрый механизм, независимый от маршрутизации, с помощью которого можно обнаружить сбои канала для любого типа канала.

Помимо быстрого обнаружения сбоев, на конвергенцию маршрутизации влияют и другие факторы: время отправки нового пакета состояния канала по каналу и задержка распространения по сети; время на получение такого пакета и отправку его нужному процессу в операционной системе; время SPF; время обновления базы маршрутной информации; время расчета воздействия на таблицу пересылки; время отправить любые обновления таблицы пересылки на линейные карты (на больших маршрутизаторах, которые имеют такие вещи); пришло время рассылать пакет о состоянии канала соседям. Все эти шаги анализировались и оптимизировались на протяжении многих лет до такой степени, что конвергенция маршрутизации за доли секунды теперь стала рутиной. Еще в 2003 году усовершенствования всех вышеописанных шагов позволили добиться сходимости за доли секунды, поскольку эта презентация НАНОГ шоу. Да, вы не могли позволить себе потратить 10 секунд на расчет SPF, если хотели быстрой сходимости, но к тому времени эта проблема уже была решена. Оптимизация всех остальных частей была не менее важна, чем сокращение времени расчета SPF.

Наконец, я поговорил на эту тему с другим коллегой, и он напомнил мне причину, по которой алгоритм Дейкстры остается предпочтительным методом реализации: его могут понять люди, которым приходится писать код. Сам Дейкстра хорошо выразил это в интервью 2001 года:

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

Другими словами, Будь проще, глупый. Я бы, конечно, предпочел указать инженеру на Спецификация OSPF чем отправить их, чтобы понять гибрид Беллмана-Форда/Дийкстры подход, который может сэкономить несколько миллисекунд на той части конвергенции маршрутизации, которая не является узким местом. Возможно, однажды кто-нибудь напишет объяснение нового подхода SPF, которое будет таким же ясным, как статья Дейкстры и спецификация OSPF. Гибридный алгоритм может оказаться отличным решением для крупных картографических приложений. Но я не думаю, что алгоритм Дейкстры будет заменен в серийных маршрутизаторах в ближайшее время. ®

#Алгоритм #Дейкстры #не #будет #заменен #серийных #маршрутизаторах #Register