Как един нов алгоритъм победи теорията, която управлява интернет през последните 60 години

Нов алгоритъм за намиране на най-кратките пътища в мрежи предизвика интерес в научната общност. В ново изследване се твърди, че този нов подход превъзхожда алгоритъма, разработен от легендарния учен Едсгер Дийкстра през далечната 1959 година и използван в повечето учебници по мрежови технологии.

Алгоритъмът на Дийкстра предхожда изобретяването на комутацията на пакети и е в основата на двата доминиращи протокола за маршрутизация – OSPF и IS-IS. Спецификацията на OSPF описва изпълнението толкова подробно, че всъщност задължава използването на алгоритъма на Дийкстра. Точно това е правено в продължение на десетилетия, като са правени само незначителни подобрения за ускоряване на работата.

Новият алгоритъм не е незначително подобрение, а коренно различен подход. Основното му постижение е преодоляването на така наречената „бариера на сортирането“. За разлика от алгоритъма на Дийкстра, който изисква операция за сортиране и е ограничен от производителността на най-добрите алгоритми за сортиране, новото решение се справя без нея и демонстрира по-добри теоретични резултати.

Работата е рецензирана на престижната конференция ACM Symposium on the Theory of Computing и теоретичната коректност на алгоритъма не буди съмнение. Въпросът е друг – доколко тя е важна на практика?

Времето за изпълнение на алгоритъма на Дийкстра е от порядъка на n log n + m за мрежа от n върха (маршрутизатори) и m ребра (комуникационни канали). Новият подход показва време от порядъка на m log2/3 n, което е очевидно по-малко, когато стойността на n е достатъчно голяма. Проблемът е, че за да оценим мащабируемостта, трябва да разберем колко голямa трябва да е стойността на n, за да стане разликата забележима. При малки стойности едно по-малко мащабируемо решение може да работи дори по-бързо поради разликите в постоянните коефициенти.

Историята показва, че понякога практически ползи се постигат дори без максимална мащабируемост. През деветдесетте години FORE Systems успешно продава 16-портови комутатори, докато изследователите от Bellcore изразходват време и средства за разработване на прототипи на 32-портови устройства с по-добра мащабируемост. Оказа се, че n=16 е напълно достатъчно за комутатори със 155-мегабитови връзки по онова време.

И така, коя стойност на n се счита за голяма стойност за изчисляване на най-краткия път? Според хора от бранша днес в най-големите мрежи на доставчиците на интернет услуги има няколко хиляди маршрутизатора. Това не е незначително, но е значително по-малко от броя на префиксите в BGP. И изглежда, че размерът на мрежите не е ограничен от производителността на изчислението на най-краткия път.

Важно – времето за изчисляване на SPF е само един от многото фактори, които влияят върху работата на протоколите за маршрутизация. При работата по технологията за бързо пренасочване на MPLS стана ясно, че най-важното за бързото възстановяване след повреда е скоростта на откриване на самата повреда. Ако трябва да изчакате десетки секунди за пропуснати OSPF Hello пакети, преди да обявите връзката за повредена, няма значение дали можете да изчислите най-краткия път за част от секундата. Ето защо е създаден BFD – бърз механизъм за откриване на повреди, независим от протокола за маршрутизация.

В допълнение към бързото откриване на повреди, времето за сходимост на маршрутизацията се влияе от времето на изпращане на пакета за състоянието на връзката, забавянето при разпространението му в мрежата, времето, необходимо на операционната система да получи и обработи пакета, да актуализира таблицата за маршрутизация, да изчисли промените в таблицата за препращане, да зареди актуализациите в линейните карти в големите маршрутизатори и да изпрати пакетите за състоянието на връзката до съседите. Всички тези стъпки са анализирани и оптимизирани през годините, така че конвергенцията на маршрутизацията за по-малко от секунда е станала нещо обичайно. До 2003 година подобренията във всички тези стъпки вече са постигнали сходимост под секунда. Да, не можехме да си позволим да прекараме 10 секунди в изчисляване на SPF, докато се стремяхме към бърза конвергенция, но този проблем вече беше решен. Оптимизирането на другите части се оказа също толкова важно, колкото и ускоряването на изчисляването на най-кратките пътища.

Има и друга причина, поради която алгоритъмът на Дийкстра остава предпочитан метод за изпълнение – той е разбираем за хората, които трябва да пишат код.

Самият Дийкстра го обяснява добре в интервю от 2001 година:

„Публикацията все още се чете, тя е наистина добра. Една от причините е, че аз проектирах алгоритъма без молив и хартия. По-късно осъзнах, че едно от предимствата на проектирането без молив и хартия е, че си почти принуден да избягваш цялата незадължителна сложност.“

С други думи, не усложнявайте нещата излишно. Много по-лесно е да насочите инженера към спецификацията на OSPF, отколкото да го изпратите да измисли хибриден подход на Белман-Форд и Дийкстра, който може да спести няколко милисекунди в некритична част от процеса на сходимост на маршрутизацията. Може би някой ден някой ще напише обяснение на новия алгоритъм SPF, което да е толкова ясно, колкото оригиналната работа на Дийкстра и спецификацията на OSPF, а хибридният алгоритъм може да работи добре за големи приложения за картографиране. Но замяна на алгоритъма на Дийкстра в индустриалните маршрутизатори не се очаква скоро.