Таблица за маршрутизиране на Quagga
По естеството на работата си се занимавам с мрежово проектиране и конфигуриране на мрежово оборудване. По някое време исках да разбера как са подредени мрежовите устройства, които винаги са представлявали за мен черни кутии, които магически реализират мрежови протоколи. Тъй като устройства от доставчици като Cisco или Juniper са затворени и не са достъпни за проучване, изборът ми падна върху програмата Quagga - рутер с отворен код, който се използва широко в реалния живот и доста успешно се справя с протоколите OSPF и BGP. Въоръжен с източниците на Quagga, започнах да изследвам. В тази статия искам да ви кажа как е подредена таблицата за маршрутизиране в Quagga, какви структури и алгоритми се използват за нейното внедряване.
Quagga архитектура
Първо, няколко думи за общата архитектура на Quagga. Quagga се състои от няколко отделни програми или демони, всяка от които изпълнява определена функция. Например, ospfd изпълнява OSPF, докато bgpd прилага BGP. Демонът на зебра играе централна роля в Quagga. Една от основните му роли е да получава информация за маршрутизиране от демони, които изпълняват специфични протоколи и да избира най-добрите маршрути от различни източници. След това най-добрите маршрути се предават на ядрото на Linux, което всъщност прехвърля потребителски трафик (предполагаме, че Quagga е инсталиран на Linux). По този начин се осъществява класическото разделяне на „интелигентността“ на рутера (Control Plane) и предаването на потребителски трафик (Data Plane). В нашия случай Quagga е контролната равнина, а ядрото на Linux е контролната равнина. Таблицата за маршрутизиране на Quagga е вътре в демона на зебра.
Съхраняване на информация за маршрута
Когато изтриете маршрут, този маршрут се премахва от списъка с маршрути за този префикс и процедурата за избор на най-добрия маршрут също се стартира. Например, след изтриване на статичен маршрут, картината ще изглежда така:
След като изберете най-добрия маршрут, информацията за него се прехвърля в ядрото на Linux.
Съхранение на префикси
В бъдеще ще бъде по-удобно да се представят префиксите в двоична форма, като се посочват само първите битове, в количество, равно на дължината на префикса. Останалите битове на префикса са 0 и не са важни за търсенето. Например, префикс 10.0.0.0/8 в двоичен файл ще изглежда като 00001010, префикс 128.0.0.0/1 ще изглежда като 1, 128.0.0.0/2 като 10 и т.н.
Какво е трие или дърво на префикс и как работи, може да се прочете например тук. За нашите цели най-лесният начин да го разберем е с пример. Например имаме префикси 1, 111, 010, 0110000. Тези префикси ще бъдат организирани в следното дърво на префиксите:
Белите възли съответстват на интересуващите префикси. Жълтите възли са междинни и служат за правилно организиране на дървесната структура. Най-горният възел е коренът на дървото и съответства на префикса 0.0.0.0/0. Търсенето на желания префикс се извършва, както следва. Търсенето започва от корена на дървото. След това се проверява първият бит от желания префикс. Ако първият бит е 0, тогава слизаме до левия дъщерен елемент. Ако първият бит е 1, тогава на правилното дете. След това повтаряме тази процедура за втория бит от желания префикс, след това за третия и т.н. докато достигнем желания префикс или се уверим, че го няма. Ако необходимият префикс липсва, той се добавя към дървото на подходящото място. Вижда се, че броят на достъпите на дърво е равен на дължината на желания префикс и за най-дългия префикс IPv4 е 32. Строго погледнато, не е необходимо самият префикс да се съхранява във всеки възел на дървото, тъй като той се определя уникално от местоположението на възела, но аз го посочих за по-голяма яснота. Също така, в реалната структура на Quagga, префиксът всъщност се съхранява във всеки възел на дървото.