Задача . BGP (2024-2025, 9-10)

Интернет состоит из отдельных крупных сетей, управляемых отдельными организациями. Между такими сетями распределяется пространство IP-адресов и устанавливается техническое и организационное взаимодействие. Несколько упрощая, можно сказать, что такие крупные сети называются автономными системами (AS). За каждой AS закрепляется IP-подсеть. Для обмена маршрутной информацией между маршрутизаторами AS используется внешний протокол динамической маршрутизации BGP (Border Gateway Protocol). BGP выбирает наилучший маршрут для передачи пакетов на основе ряда атрибутов и метрик.

BGP-роутер при маршрутизации пакета выбирает IP-адрес следующего по маршруту маршрутизатора, который в BGP называется «соседом» (neighbor), по набору атрибутов маршрутов. В задаче для упрощения будем считать, что реализуется следующий алгоритм.

1. по адресу назначения в IP-пакете выбираются подходящие маршруты из таблицы маршрутизации по полю «сеть назначения».
2. потом из них выбирается лучший, для чего последовательно проверяются атрибуты маршрутов. То есть сначала проверяется первый атрибут всех подходящих маршрутов, и если у возможных маршрутов он имеет равное значение, проверяется второй атрибут и т.д.

В задаче используются следующие атрибуты в указанном порядке:

1. Локальное предпочтение (Local Preference)
Local Preference — это атрибут, который используется для выбора исходящего трафика из автономной системы. Маршрут с наибольшим значением Local Preference считается предпочтительным.

2. Наименьший Путь AS (AS Path)
BGP предпочитает маршруты с наименьшим количеством автономных систем в пути (AS Path). Чем короче путь, тем лучше.

3. Наименьший IGP Metric до Next Hop
Если есть несколько маршрутов с одинаковыми атрибутами, BGP выбирает маршрут с наименьшим значением метрики IGP до Next Hop (следующего прыжка).

4. Старейший маршрут (Oldest Route)
Если все предыдущие атрибуты равны, BGP предпочитает старейший маршрут, так как он считается более стабильным.

5. Наименьший IP-адрес соседа
В крайнем случае, если все предыдущие атрибуты равны, BGP выбирает маршрут, полученный от соседа с наименьшим IP-адресом (сравнение производится как сравнение 32-битных значений адресов).

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

 

AS1:

AS2:

AS3:

AS4:

AS5:

AS6:

AS7:

AS8:

Определите сначала маршрут прохождения пакета из AS8 в AS6, а потом маршрут прохождения пакета в случае, если из-за аварии будет отключены связи между AS8 и AS3, а также между AS1 и AS6, а записи, соответствующие этим связям, будут исключены из таблиц.

В ответ запишите номера автономных систем через запятую, начиная с 8 и заканчивая 6, сначала для первого случая, а потом, через тире, для второго. Если маршрут построить нельзя (например, его нет или образуется цикл), вместо перечисления номеров автономных систем укажите NULL.

Пример ввода ответа: 8,10,12,6-8,10,1,2,6.