Системный подход В прошлом году мне переслали одну и ту же статью о новом методе поиска кратчайших путей в сетях.
Лежащее в основе исследование утверждает, что оно превосходит классический подход, разработанный Эдсгером Дейкстрой и преподаваемый в большинстве учебников по сетям (включая наш). Поначалу я отнесся к этому скептически, как и к сообщению о доказательстве гипотезы Римана.
Дейкстра — легенда в области информатики, а его алгоритм, опубликованный в 1959 году, появился за несколько лет до пакетной коммутации. Спецификация OSPF (Open Shortest Path First, один из двух доминирующих протоколов маршрутизации по состоянию канала, второй — IS-IS, Intermediate System-to-Intermediate System) предписывает использовать именно его.
Рекомендации для разработчиков OSPF необычайно подробны и, по сути, говорят им использовать алгоритм Дейкстры. Большинство реализаций следуют этому десятилетиями, с некоторыми незначительными улучшениями для ускорения, но без фундаментальных изменений.
Новый алгоритм — это не мелкая доработка алгоритма Дейкстры, а принципиально иной подход. Его главное заявленное преимущество в том, что, в то время как алгоритм Дейкстры требует операции сортировки и, следовательно, его производительность ограничена лучшими алгоритмами сортировки, новый подход «преодолевает барьер сортировки». То есть он избавляется от необходимости сортировки и способен обеспечить лучшие пределы производительности, чем алгоритм Дейкстры.
Хотя я не считаю себя достаточно квалифицированным для оценки статьи, описывающей новый алгоритм, она прошла рецензирование на конференции высшего уровня (ACM Symposium on the Theory of Computing) и получила достаточно внимания, чтобы я не сомневался в теоретической состоятельности. Вопрос, который я хочу обсудить здесь: имеет ли это значение?
При оценке последствий теоретического улучшения производительности алгоритма мне сразу пришли на ум два основных момента. Во-первых, каковы реальные пределы масштабирования, с которыми нам приходится сталкиваться в реальных системах маршрутизации? Например, время работы алгоритма Дейкстры для сети с *n* вершинами (маршрутизаторами) и *m* ребрами (каналами) составляет порядка O(n log n + m). Новый подход претендует на O(m log2/3 n), что, очевидно, будет меньше при достаточно большом *n*. (Мне пришлось освежить знания логарифмической нотации, прежде чем я смог с уверенностью написать это предложение.) Проблема оценки свойств масштабируемости чего-либо заключается в том, что нужно понять, насколько большим должен быть *n*, чтобы это имело значение. Существуют константные множители, которые могут различаться между двумя подходами; при малых *n* «менее масштабируемый» подход может фактически демонстрировать лучшую производительность.
Какой предел масштабирования?
Одной из моих первых работ было участие в команде, создававшей масштабируемый коммутатор пакетов на основе массивов небольших коммутирующих элементов. (Именно тогда мне удалось создать случайный SmartNIC.) У нас были статьи, демонстрирующие, что мы можем создавать коммутаторы с тысячами портов на скорости 155 Мбит/с в эпоху, когда общий Ethernet работал на скорости 10 Мбит/с и еще не был вытеснен коммутируемым Ethernet.
Пока мы в Bellcore вкладывали много времени и денег в сборку комплекта из 32-портовых прототипов коммутаторов, FORE Systems выпустила коммерчески успешные 16-портовые коммутаторы. Скорее всего, они не были столь же масштабируемы, как наша разработка, но оказалось, что *n*=16 было вполне достаточной емкостью для коммутаторов с каналами 155 Мбит/с в 1990-х годах. Мы были очень опечалены тем, что наши исследования, казалось, были обойдены коммерческими продуктами. Мой вывод заключался в том, что масштабируемость — это хорошо, к чему стоит стремиться, но иногда можно добиться хорошего результата с менее масштабируемым решением. В одном из моих любимых учебников, «Principles of Computer Systems Design», используется пример остановки супертанкера для демонстрации пределов масштабирования системы. Тот факт, что у супертанкеров есть предел масштабирования, не мешает им быть основой транспортировки нефти. Просто нужно избегать их чрезмерного увеличения.
Какое большое значение *n* имеет для расчетов SPF? Я связался с парой коллег, чтобы обновить свои воспоминания о том, сколько маршрутизаторов можно найти в крупной магистральной сети OSPF или IS-IS. По моим воспоминаниям, их было несколько сотен; в крупнейших сетях поставщиков услуг сегодня их число исчисляется немногими тысячами. Так что это не так уж мало, но все же мало по сравнению, скажем, с количеством префиксов, передаваемых в BGP.
И, похоже, это не ограничивается производительностью расчета SPF, как я объясню ниже.
Многогранная производительность
Еще одно воспоминание из моего времени работы в Big Router — анализ всех факторов, влияющих на производительность протоколов маршрутизации. Я работал над MPLS на ранних этапах, и мы были в восторге от технологии под названием «быстрая перемаршрутизация» (FRR), которая использует MPLS для перенаправления пакетов в обход отказавшего канала без ожидания сходимости маршрутизации после сбоя. Но в то же время люди, ответственные за разработку протоколов маршрутизации, усердно работали над сокращением времени сходимости маршрутизации. Одной из самых важных вещей, как оказалось, как для MPLS, так и для стандартной маршрутизации, было просто более быстрое обнаружение сбоев. Например, если вам приходится ждать десятки секунд отсутствия пакетов OSPF Hello, прежде чем объявить канал нерабочим, не так уж важно, можете ли вы рассчитать кратчайший путь за доли секунды. Именно этим соображением была вызвана разработка BFD (Bidirectional Forwarding Detection): быстрого механизма, независимого от маршрутизации, с помощью которого можно было обнаруживать сбои каналов любого типа.
Помимо быстрого обнаружения сбоев, к другим факторам, влияющим на сходимость маршрутизации, относятся: время отправки нового пакета состояния канала по каналу и задержка распространения по сети; время получения такого пакета и его передачи соответствующему процессу в операционной системе; время SPF; время обновления базы данных маршрутной информации; время расчета влияния на таблицу пересылки; время отправки обновлений таблицы пересылки на линейные карты (в больших маршрутизаторах, где они есть); время рассылки пакета состояния канала соседям. Все эти шаги были проанализированы и оптимизированы за годы, до такой степени, что сходимость маршрутизации менее чем за секунду стала обычным делом. Уже в 2003 году улучшения всех вышеперечисленных шагов позволили добиться сходимости менее чем за секунду, как показано на этой презентации NANOG. Да, вы не могли позволить себе потратить 10 секунд на расчет SPF, если хотели быстрой сходимости, но к тому времени эта проблема уже была решена. Оптимизация всех остальных частей была не менее важна, чем улучшение времени расчета SPF.
Наконец, я пообщался с еще одним коллегой на эту тему, и он напомнил мне причину, по которой алгоритм Дейкстры остается предпочтительным методом реализации: его могут понять люди, которые должны писать код. Сам Дейкстра хорошо выразил это в интервью 2001 года:
Публикация до сих пор читаема, она, по сути, довольно хороша. Одна из причин, почему она так хороша, заключается в том, что я разработал ее без карандаша и бумаги. Позже я понял, что одно из преимуществ проектирования без карандаша и бумаги заключается в том, что вы почти вынуждены избегать всякой излишней сложности.
Другими словами, Keep It Simple, Stupid (Делай проще, глупый). Я бы определенно предпочел направить инженера на спецификацию OSPF, чем отправлять его разбираться в гибридном подходе Беллмана-Форда/Дейкстры, который может сэкономить несколько миллисекунд на некритичной части сходимости маршрутизации. Возможно, однажды кто-нибудь напишет объяснение нового подхода к SPF, столь же ясное, как статья Дейкстры и спецификация OSPF. И гибридный алгоритм может быть отлично применим для больших картографических приложений. Но я не думаю, что алгоритм Дейкстры будет заменен в производственных маршрутизаторах в ближайшее время. ®
Ларри Петерсон и Брюс Дэви — авторы книги Computer Networks: A Systems Approach и связанной серии книг Systems Approach. Весь их контент является открытым исходным кодом и доступен бесплатно на GitHub. Вы можете найти их в Mastodon, их информационный бюллетень здесь, а прошлые колонки The Register — здесь.
Всегда имейте в виду, что редакции могут придерживаться предвзятых взглядов в освещении новостей.
Автор – Bruce Davie
