РАЗРЕШЕНИЕ КОНФЛИКТОВ ИДЕНТИФИКАТОРОВ СОСТОЯНИЯ ЛИНИИ СВЯЗИ
LINK STATE IDENTIFIER CONFLICT RESOLUTION

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ
Варианты осуществления изобретения относятся к области протоколов маршрутизации на основе состояния линии связи, в частности к разрешению конфликтов идентификаторов состояния линии связи при назначении состояния линии связи.
УРОВЕНЬ ТЕХНИКИ
Протоколы маршрутизации на основе состояния линии связи, например первоочередного открытия кратчайшего пути (Open Shortest Path First) (OSPF) (например, заданный в RFC 2328, апрель 1998 г.), используют идентификаторы состояния линии связи (LSID) в качестве ключей при идентификации извещений о состоянии линии связи (LSA). LSA для разных маршрутов, которые совместно используют один и тот же LSID, могут приводить к различным проблемам, включая неверный топологический вид, проблемы с отображением данных, множественные маршруты, указывающие на одно и тоже LSA, и т.д.
Для большинства маршрутов LSA, связанным с каждым маршрутом, назначается LSID, эквивалентный сетевому адресу этого маршрута. Сетевой адрес для маршрута вычисляется путем осуществления побитовой операции и над префиксом маршрута и маской маршрута. Например, поскольку сетевой адрес для маршрута [10.0.0.0, 255.255.0.0] равен 10.0.0.0, LSA для этого маршрута обычно назначается значение LSID, равное 10.0.0.0.
Хотя считается, что маршруты с одним и тем же префиксом различны, если их маски отличаются, сетевой адрес этих маршрутов может быть одинаковым. Например, маршруты [10.0.0.0, 255.255.0.0] и [10.0.0.0, 255.255.255.0] различны, несмотря на то, что совместно используют один и тот же сетевой адрес 10.0.0.0. Таким образом, LSID для LSA, связанных с этими маршрутами, будут конфликтовать. В таком случае, RFC 2328 описывает алгоритм, который пытается назначить разные LSID для LSA для этих маршрутов (алгоритм задан в Приложении E RFC 2328). Алгоритм разрешения конфликтов LSID, заданный в RFC 2328 выбирает маршрут с более длинной маской и осуществляет побитовую операцию НЕ над этой маской, осуществляет побитовую операцию ИЛИ над этим результатом с префиксом маршрута и назначает результат в качестве LSID. Например, с использованием двух вышеуказанных маршрутов, выбирается маршрут [10.0.0.0, 255.255.255.0] результат побитовой операции НЕ над маской 255.255.255.0, который равен 0.0.0.255, подвергается побитовой операции ИЛИ с префиксом маршрута 10.0.0.0, в результате чего получается значение 10.0.0.255, которое затем назначается в качестве LSID для LSA этого маршрута. Маршруту, который не выбран, назначается LSID, эквивалентный сетевому адресу.
Алгоритм разрешения конфликтов LSID, описанный в RFC 2328, не разрешает конфликты LSID верно, когда один из конфликтующих маршрутов является маршрутом к хосту. Маршрут к хосту - это маршрут с хост-маской (например, 255.255.255.255). Рассмотрим, например, маршруты [10.0.0.0, 255.255.255.0] и [10.0.0.0, 255.255.255.255], которые имеют один и тот же сетевой адрес (10.0.0.0). Согласно алгоритму разрешения конфликтов LSID, заданному в RFC 2328, выбирается маршрут [10.0.0.0, 255.255.255.255] (который является маршрутом к хосту), результат побитовой операции НЕ над маской 255.255.255.255, который равен 0.0.0.0, подвергается побитовой операции ИЛИ с префиксом маршрута 10.0.0.0, в результате чего получается значение 10.0.0.0, которое затем назначается в качестве LSID для LSA этого маршрута. Таким образом, при использовании алгоритма разрешения конфликтов LSID, заданного в RFC 2328, разные маршруты [10.0.0.0, 255.255.255.0] и [10.0.0.0, 255.255.255.255] будут иметь LSA, которые совместно используют один и тот же LSID 10.0.0.0. Таким образом, алгоритм разрешения конфликтов LSID, описанный в RFC 2328, в случае применения к маршрутам к хосту, дает LSA разных маршрутов, совместно использующие один и тот же LSID, что может приводить к вышеописанным проблемам.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
Описаны способы и устройство для разрешения конфликтов LSID для элемента сети во избежание совместного использования одного и того же LSID разными LSA, связанными с разными маршрутами. Согласно одному варианту осуществления изобретения, элемент сети генерирует предварительный LSID для первого маршрута в процессе назначения LSID. Элемент сети определяет, что значение предварительного LSID уже назначено второму маршруту, и что либо первый маршрут, либо второй маршрут является маршрутом к хосту, причем маршрут к хосту имеет маску маршрута к хосту, и первый и второй маршруты различны. В случае определения, что первый маршрут является маршрутом к хосту, первый маршрут подавляется во избежание конфликта LSID между первым и вторым маршрутами, включая запрет отправки LSA для первого маршрута. В случае определения, что второй маршрут является маршрутом к хосту, второй маршрут подавляется во избежание конфликта LSID между первым и вторым маршрутами, включая очистку LSA второго маршрута, и LSA для первого маршрута отправляется с LSID, который был назначен второму маршруту. Хотя маршрут к хосту подавлен, досягаемость сети в диапазоне, категоризующем маршрут к хосту, обеспечивается через маршрут, который не является маршрутом к хосту. Если маршрут, который мог бы иметь конфликт LSID с маршрутом к хосту, удален до маршрута к хосту, подавление маршрута к хосту отменяется, и LSA автоматически отправляется для маршрута к хосту с LSID, который был ранее назначен LSA другого маршрута.
Согласно другому варианту осуществления изобретения, элемент краевой сети потребителя распределяет маршруты OSPF к первому элементу краевой сети провайдера согласно протоколу OSPF, причем, по меньшей мере, некоторые из маршрутов OSPF являются маршрутами к хосту, причем маршрут к хосту - это маршрут, который имеет маску маршрута к хосту. Первый элемент краевой сети провайдера распределяет маршруты OSPF ко второму элементу краевой сети провайдера согласно пограничному межсетевому протоколу (BGP). Первый элемент краевой сети провайдера включает в себя модуль OSPF, который реализует протокол OSPF и генерирует LSA и назначает LSID LSA. При назначении LSID модуль OSPF подавляет те из маршрутов OSPF, которые являются маршрутами к хосту, которые, в противном случае, имели бы соответствующие LSA с LSID, конфликтующими с другими LSA. Подавление маршрутов OSPF включает в себя удаление LSA, связанных с подавленными маршрутами к хосту, и запрет отправки LSA для подавленных маршрутов к хосту. Хотя LSA не отправляются для этих подавленных маршрутов к хосту, досягаемость сети обеспечивается для каждого подавленного маршрута к хосту через маршрут, связанный с LSA, которое имело LSID, конфликтующий с этим маршрутом к хосту. Подавление каждого подавленного маршрута к хосту отменяется при удалении маршрута, связанного с LSA, имеющим тот же LSID, что и маршрут к хосту, до этого подавленного маршрута к хосту, и LSA автоматически отправляется для этого маршрута к хосту со снятым подавлением с LSID, который был ранее назначен LSA другого маршрута.
Согласно другому варианту осуществления изобретения, элемент сети для разрешения конфликтов LSID включает в себя модуль OSPF для сохранения базы данных состояний линии связи (LSDB) и генерации LSA, которые включают в себя LSID. При назначении LSID для LSA модуль OSPF назначает LSID LSA для маршрутов на основании префиксов сети и масок маршрута этих маршрутов, подавляет те из маршрутов, которые являются маршрутами к хосту, которые, в противном случае, имели бы соответствующее LSA с LSID, который конфликтует с LSID другого LSA, связанного с другим маршрутом. Подавление этих маршрутов включает в себя удаление LSA, связанных с подавленными маршрутами к хосту, и запрет отправки LSA для подавленных маршрутов к хосту. Хотя LSA не отправляются для этих подавленных маршрутов к хосту, досягаемость сети обеспечивается для каждого подавленного маршрута к хосту через маршрут, связанный с LSA, которое имело LSID, конфликтующий с этим маршрутом к хосту. Подавление каждого подавленного маршрута к хосту отменяется при удалении маршрута, связанного с LSA, имеющим тот же LSID, что и маршрут к хосту, до этого подавленного маршрута к хосту, и LSA автоматически отправляется для этого маршрута к хосту со снятым подавлением с LSID, который был ранее назначен LSA другого маршрута.
Таким образом, предотвращается отправка LSA, которые совместно используют один и тот же LSID, для разных маршрутов, включая маршруты к хосту, и, в то же время, обеспечивается досягаемость каждого из маршрутов даже при наличии подавленных маршрутов к хосту. Когда маршрут, связанный с LSA, который имеет LSID, который конфликтовал бы с LSA для подавленного маршрута к хосту, удален до этого подавленного маршрута к хосту, подавление этого подавленного маршрута к хосту отменяется, и LSA отправляется для этого маршрута к хосту с LSID, который был назначен LSA другого маршрута.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Изобретение можно лучше всего понять, обратившись к нижеследующему описанию и прилагаемым чертежам, которые используются для иллюстрации вариантов осуществления изобретения, при этом на чертежах:
Фиг. 1 - блок-схема, демонстрирующая иллюстративную сеть согласно одному варианту осуществления изобретения;
Фиг. 2 - блок-схема, демонстрирующая иллюстративную сеть согласно одному варианту осуществления изобретения;
Фиг. 3 - блок-схема, демонстрирующая иллюстративный элемент сети для разрешения конфликтов LSID согласно одному варианту осуществления изобретения;
Фиг. 4 - схема обработки данных, демонстрирующая иллюстративный процесс добавления маршрута, который назначает LSID для маршрутов, включающий в себя разрешение конфликтов LSID согласно одному варианту осуществления изобретения;
Фиг. 5 - схема обработки данных, демонстрирующая иллюстративный процесс удаления маршрута, включающий в себя отмену подавления маршрутов согласно одному варианту осуществления изобретения;
Фиг. 6 - логическая блок-схема, демонстрирующая иллюстративные операции, осуществляемые в процессе добавления маршрута, включающие в себя разрешение конфликтов LSID согласно одному варианту осуществления изобретения;
Фиг. 7 - логическая блок-схема, демонстрирующая иллюстративные операции, осуществляемые в процессе удаления маршрута согласно одному варианту осуществления изобретения;
Фиг. 8 - блок-схема, демонстрирующая назначения LSID для набора маршрутов, которые приходят по порядку согласно одному варианту осуществления изобретения; и
Фиг. 9 - блок-схема, демонстрирующая назначения LSID для набора маршрутов, которые приходят в другом порядке, чем показано на Фиг. 8, согласно одному варианту осуществления изобретения.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
В нижеследующем описании изложены многочисленные конкретные детали. Однако очевидно, что варианты осуществления изобретения можно осуществлять на практике без этих конкретных деталей. В других случаях, общеизвестные схемы, структуры и методы не описаны подробно, чтобы не затемнять это описание ненужными подробностями. Специалисты в данной области техники на основании данного описания смогут реализовать соответствующие функции без ненужного экспериментирования.
Выражения, употребляемые в этом описании изобретения, как то: “один вариант осуществления”, “вариант осуществления”, “иллюстративный вариант осуществления” и т.д., - указывают, что описанный вариант осуществления может включать в себя конкретный признак, структуру или характеристику, но каждый вариант осуществления не обязан включать в себя конкретный признак, структуру или характеристику. Кроме того, такие выражения не обязательно относятся к одному и тому же варианту осуществления. Дополнительно при описании конкретного признака структуры или характеристики в связи с вариантом осуществления предполагается, что специалисты в данной области техники способны реализовать такой признак, структуру или характеристику в связи с другими вариантами осуществления, описанными или неописанными в явном виде.
В нижеследующем описании и в формуле изобретения могут использоваться термины “соединенный” и “связанный”, а также их производные. Следует понимать, что эти термины не являются синонимами. Термин “соединенный” используется для указания, что два или более элемента, которые могут находиться или не находиться в прямом физическом или электрическом контакте друг с другом, кооперируются или взаимодействуют друг с другом. Термин “связанный” используется для указания установления связи между двумя или более элементами, которые связаны друг с другом.
Методы, показанные на фигурах, можно реализовать с использованием кода и данных, хранящихся и выполняющихся на одном или нескольких электронных устройствах (например, оконечной станции, элементе сети и т.д.). Такие электронные устройства сохраняют и передают (внутренне и/или посредством других электронных устройств по сети) код и данные с использованием машинно-считываемых сред, например, машинно-считываемых носителей (например, магнитных дисков; оптических дисков; оперативной памяти; постоянной памяти; устройств флэш-памяти; памяти на основе фазовых переходов) и машинно-считываемых сред связи (например, электрических, оптических, акустических или других распространяющихся сигналов, например, несущих волн, инфракрасных сигналов, цифровых сигналов и т.д.). Кроме того, такие электронные устройства обычно включают в себя набор из одного или нескольких процессоров, связанных с одним или несколькими другими компонентами, например, одним или несколькими запоминающими устройствами, устройствами пользовательского ввода/вывода (например, клавиатурой, сенсорным экраном и/или дисплеем), и сетевыми соединениями. Набор процессоров и других компонентов обычно соединяется через один или несколько шин или мостов (также именуемых контроллерами шины). Запоминающее устройство и сигналы, несущие сетевой трафик, соответственно, представляют один или несколько машиночитаемых носителей и машиночитаемых сред связи. Таким образом, в запоминающем устройстве данного электронного устройства обычно хранится код и/или данные для выполнения на наборе из одного или нескольких процессоров этого электронного устройства. Конечно, одну или несколько частей варианта осуществления изобретения можно реализовать с использованием различных комбинаций программного обеспечения, программно-аппаратного обеспечения и/или оборудования.
Используемое здесь понятие «элемент сети» (например, маршрутизатор, коммутатор, мост и т.д.) означает элемент сетевого оборудования, включающий в себя аппаратное и программное обеспечение, который обеспечивает возможностью связи другое оборудование в сети (например, другие элементы сети, оконечные станции и т.д.). Некоторые элементы сети являются “многосервисными элементами сети”, которые обеспечивают поддержку множественных сетевых функций (например, маршрутизации, организации мостового соединения, коммутации, агрегации 2 уровня, сеансового пограничного контроля и/или управления абонентами), и/или обеспечивают поддержку множественных прикладных сервисов (например, передачу данных, речи и видеосигнала). Абонентские оконечные станции (например, серверы, рабочие станции, портативные компьютеры, планшетные компьютеры, мобильные телефоны, смартфоны, мультимедийные телефоны, телефоны, поддерживающие протокол Voice Over Internet (VOIP), портативные медиаплееры, устройства GPS, игровые системы, телевизионные приставки и т.д.) осуществляют доступ к контенту/услугам, обеспеченным в интернете и/или контенту/услугам, обеспеченным в виртуальных частных сетях (VPN), подключенных к интернету. Контент и/или услуги обычно обеспечиваются одной или несколькими оконечными станциями (например, серверными оконечными станциями), принадлежащими провайдеру услуг или контента, или оконечными станциями, участвующими в службе, организованной между равноправными устройствами, и могут включать в себя публичные веб-страницы (бесплатный контент, виртуальные магазины, поисковые службы и т.д.), частные веб-страницы (например, веб-страницы, требующие ввода имени пользователя и пароля, обеспечивающие услуги электронной почты и т.д.), корпоративные сети над VPN и т.д. Обычно абонентские оконечные станции связаны (например, через домашнее оборудование потребителя, связанное с сетью доступа (проводным или беспроводным образом)) с элементами краевой сети, которые связаны (например, через один или несколько элементов базовой сети) с другими элементами краевой сети, которые связаны с другими оконечными станциями (например, серверными оконечными станциями).
Обычно элемент сети включает в себя набор из одной или нескольких линейных карт, набор из одного или нескольких карт управления, и, в необязательном порядке, набор из одной или нескольких сервисных карт (иногда именуемых ресурсными картами). Эти карты связаны друг с другом посредством одного или нескольких механизмов (например, первой полносвязной топологии, связывающей линейные карты, и второй полносвязной топологии, связывающей все карты). Набор линейных карт образует плоскость данных, а набор карт управления образует плоскость управления и обмена пакетами с элементом внешней сети через линейные карты. Набор сервисных карт может обеспечивать специализированную обработку (например, услуги уровней с 4 по 7 (например, брандмауэр, IPsec, IDS, P2P), сеансовый пограничный контроллер VoIP, мобильные беспроводные шлюзы (GGSN, шлюз Evolved Packet System (EPS)) и т.д.). В порядке примера, сервисную карту можно использовать для завершения туннелей IPsec и выполнения алгоритмов аутентификации и шифрования служителя.
Описан способ и устройство для разрешения конфликтов LSID. В одном варианте осуществления изобретения, маршруты к хосту, LSA которых имели бы конфликт LSID с другими маршрутами, подавляются, благодаря чему, LSA для этих маршрутов к хосту не отправляются и/или вычищаются из базы данных состояний линии связи (LSDB). Подавление этих маршрутов к хосту не позволяет множественным разным маршрутам иметь LSA, которые совместно используют один и тот же LSID. Это позволяет предотвращать проблемы, которые могут возникать в связи с отправкой LSA с одним и тем же LSID для разных маршрутов (например, неверная топология, вопросы целостности данных, выбраковка трафика, отказы программного обеспечения и т.д.).
В одном варианте осуществления, каждый подавленный маршрут к хосту связан с маршрутом, LSA которого имеет LSID, который будут конфликтовать с LSID, который был бы назначен LSA подавленного маршрута к хосту. В случае удаления другого маршрута до подавленного маршрута к хосту, подавление маршрута к хосту отменяется и LSA отправляется с LSID, который был назначен LSA этого другого маршрута.
На Фиг. 1 показана блок-схема, демонстрирующая иллюстративную сеть 100 согласно одному варианту осуществления изобретения. Согласно Фиг. 1, сеть 100 включает в себя абонентские оконечные станции 110A-110N, связанные с элементом 120 сети (прямо или косвенно). Элемент 120 сети действует как автономный граничный маршрутизатор системы (ASBR) в сети 100. Элемент 120 сети может изучать маршруты к хосту от абонентских оконечных станций 110A-110N путем перераспределения маршрутов на OSPF на элементе 120 сети, и/или маршруты к хосту могут статически конфигурироваться на элементе 120 сети (которые также обычно предоставляются OSPF путем перераспределения маршрутов). Хотя это не показано, элемент 120 сети также изучает маршруты помимо маршрутов к хосту, назначенных абонентским оконечным станциям 110A-110N.
Элемент 120 сети объявляет изученные маршруты, включая маршруты к хосту, в домен OSPF (например, элементу 130 сети, который действует как граничный маршрутизатор области (ABR) в сети 100). Например, элемент 120 сети может объявлять маршруты к хосту, назначенные абонентским оконечным станциям 110A-110N, и маршрут, который соответствует пулу, из которого выделяются маршруты к хосту. В одном варианте осуществления, элемент 120 сети объявляет маршруты, включая маршруты к хосту, элементу 130 сети с использованием LSA 5 типа OSPF (внешних LSA).
На Фиг. 2 показана блок-схема, демонстрирующая иллюстративную сеть 200 согласно одному варианту осуществления изобретения. Согласно Фиг. 2, сеть 200 является VPN (например VPN 3 уровня). Элемент 215 краевой сети потребителя (CE) осуществляет связь с элементом 220 краевой сети провайдера (PE) по линии 280 связи CE-PE, которая является линией связи OSPF. Аналогично, элемент 230 сети CE осуществляет связь с элементом 225 сети PE по линии 282 связи CE-PE, которая является линией связи OSPF. Элементы 220 и 225 сети PE осуществляют связь по линии 284 связи PE-PE, которая является линией связи BGP.
Элемент 215 сети CE объявляет маршруты, включая маршруты к хосту, от сайта 210 элементу 220 сети PE по линии 280 связи CE-PE. Элемент 230 сети CE объявляет маршруты, включая маршруты к хосту, от сайта 240 элементу 225 сети PE по линии 282 связи CE-PE. Каждый из сайтов 210 и 240 может включать в себя множественные абонентские оконечные станции. Элементы 220 и 225 сети PE экспортируют маршруты, включая маршруты к хосту, изученные из элементов 215 и 230 сети CE, соответственно, друг другу. Как будет описано более подробно ниже, маршруты, экспортируемые через BGP, можно перераспределять в OSPF.
Следует понимать, что сети, показанные на Фиг. 1 и 2, являются иллюстративными, и варианты осуществления изобретения применимы к другим типам сетей, где маршруты к хосту объявляются согласно протоколу состояния линии связи.
На Фиг. 3 показана блок-схема, демонстрирующая иллюстративный элемент сети для разрешения конфликтов LSID согласно одному варианту осуществления изобретения. Хотя на Фиг. 3 показан элемент 220 сети, следует понимать, что элемент 120 сети, показанный на Фиг. 1, и элемент сети 225 включают в себя аналогичные функции в некоторых вариантах осуществления изобретения.
Элемент 220 сети включает в себя модуль 320 OSPF, который реализует вариант протокола OSPF, связанный с модулем 360 информационной базы маршрутизации (RIB), который связан с модулем 340 BGP, который реализует вариант модуля 340 BGP. Модуль 320 OSPF и модуль 340 BGP загружают записи маршрута в главную RIB 365 на основании определенных метрик маршрута (метрики могут различаться для модуля 320 OSPF и модуля 340 BGP). Модуль 360 RIB управляет главной RIB 365 (например, обрабатывает обновления маршрутов, удаления маршрутов и т.д.) и также может обеспечивать перераспределение маршрутов между протоколами маршрутизации. Например, модуль 360 RIB может обеспечивать перераспределение маршрутов, изученных модулем 340 BGP (которые могут включать в себя маршруты к хосту, экспортированные элементом 225 сети PE) на модуль 320 OSPF. В порядке еще одного примера, модуль 360 RIB может обеспечивать перераспределение маршрутов, изученных модулем 320 OSPF (которые могут включать в себя маршруты к хосту, изученные из элемента 215 сети CE) на модуль 340 BGP для экспорта на элемент 225 сети PE.
Хотя варианты осуществления описывают, что функция перераспределения обеспечивается модулем 360 RIB, который управляет главной RIB 365, следует понимать, что перераспределение маршрутов между протоколами может осуществляться по-разному (например, модуль 320 OSPF и модуль 340 BGP могут напрямую обмениваться маршрутами, перераспределение может осуществлять модуль перераспределения, предусмотренный отдельно от главной RIB 365, и т.д.). Согласно одному варианту осуществления, оператор системы конфигурирует элемент 200 сети для перераспределения маршрутов OSPF в модуль 340 BGP и для перераспределения маршрутов BGP в модуль 320 OSPF.
Модуль 320 OSPF может изучать маршруты от других элементов сети, которые реализуют OSPF (например, от элемента 215 сети CE) в форме LSA (модуль 320 OSPF также отправляет LSA). Модуль 320 OSPF также может изучать маршруты, перераспределяемые из других протоколов (например, маршруты, перераспределяемые из модуля 340 BGP) и/или статически изученные (например, сконфигурированные операторами элемента 220 сети через интерфейс 330 командной линии). В случае изучения нового маршрута, модуль 320 OSPF начинает процесс добавления маршрута, который осуществляется модулем 350 добавления маршрута. Иллюстративный процесс добавления маршрута будет описан более подробно со ссылкой на Фиг. 4 и 6. Модуль 320 OSPF также включает в себя модуль 355 удаления маршрута для осуществления процесса удаления маршрута, который будет описан более подробно со ссылкой на Фиг. 5 и 7.
Элемент 220 сети также включает в себя следующие структуры данных: базу 324 данных состояний линии связи (LSDB), локальную RIB 326 OSPF, локальную RIB 328 BGB и главную RIB 365. Однако следует понимать, что в описанных здесь вариантах осуществления изобретения можно использовать другое количество структур данных (например, структуру данных, объединяющую в себе две или более вышеупомянутых структур данных и т.д.).
В LSDB 324, которая связана с модулем 320 OSPF, хранятся LSA, связанные с маршрутами в сети. В некоторых реализациях предусмотрена отдельная LSDB для каждой области, которой принадлежит элемент 220 сети, и в некоторых реализациях существуют разные LSDB для разных LSA типов. Как будет описано более подробно ниже, модуль 320 OSPF добавляет LSA в LSDB 324 и удаляют LSA из LSDB 324.
В локальной RIB 326 OSPF, которая связана с модулем 320 OSPF, хранятся записи маршрута OSPF, включая те, которые не загружены в главную RIB 365, и те, для которых LSA не отправляется. Например, в локальной RIB 326 OSPF могут храниться подавленные маршруты, которые являются маршрутами, для которых не будет отправлено LSA (что будет описано более подробно ниже). Согласно одному варианту осуществления, локальная RIB 326 OSPF поддерживает связь между каждым подавленным маршрутом к хосту и маршрутом, который, в противном случае, имел бы LSA с LSID, который будут конфликтовать с LSA для этого подавленного маршрута к хосту.
В главной RIB 365 хранятся маршруты, выбранные модулем 320 OSPF и модулем 340 BGP. Хотя это не показано, чтобы не затемнять суть изобретения, подмножество маршрутов в главной RIB 365 (иногда именуемых активными записями маршрута) загружается в линейные карты элемента 220 сети для использования при ретрансляции трафика. В локальной RIB 328 BGP, которая связана с модулем 340 BGP, хранятся записи маршрута BGP, включая те, которые не загружены в главную RIB 365.
На Фиг. 4 показана схема обработки данных, демонстрирующая иллюстративный процесс добавления маршрута, который назначает LSID для маршрутов, включающий в себя разрешение конфликтов LSID согласно одному варианту осуществления изобретения.
Согласно Фиг. 4, модуль 350 добавления маршрута включает в себя генератор предварительных LSID для генерации предварительных LSID и модуль 420 разрешения конфликтов LSID для разрешения конфликтов LSID. Модуль 320 OSPF вызывает модуль 350 добавления маршрута для маршрутов, которые он изучил. Маршруты могут изучаться из других равноправных устройств OSPF, перераспределяться другим протоколом или статически конфигурироваться.
Генератор 415 предварительных LSID генерирует предварительный LSID в операции 455 для маршрута, который добавляется. Первоначально, предварительный LSID является сетевым адресом маршрута, который вычисляется путем осуществления побитовой операции И над префиксом маршрута и маской маршрута. Предварительный LSID передается модулю 420 разрешения конфликтов LSID.
Модуль 420 разрешения конфликтов LSID определяет, конфликтует ли предварительный LSID с LSID, назначенным существующему LSA другого маршрута. Например, модуль 420 разрешения конфликтов LSID осуществляет операцию 460 проверки конфликта LSID для доступа LSDB 324, чтобы определить, назначен ли какому-либо из LSA в LSDB LSID, эквивалентный предварительному LSID. В отсутствие конфликта предварительный LSID будет назначен, и процесс назначения LSID завершается. Затем модуль 320 OSPF может вызвать модуль 435 отправки LSA для отправки LSA для этого маршрута с назначенным LSID. Однако при наличии конфликта LSID, и если добавленный маршрут или существующий маршрут (маршрут, который связан с LSA, LSID которого равен предварительному LSID) является маршрутом к хосту, вызывается процесс 425 разрешения конфликтов маршрута к хосту.
Процесс 425 разрешения конфликтов маршрута к хосту подавляет маршрут, который является маршрутом к хосту, осуществляя операцию 465 подавления маршрута к хосту. Если добавленный маршрут является маршрутом к хосту, то операция 465 подавления маршрута к хосту включает в себя запрет отправки LSA для этого маршрута к хосту и, таким образом, запрет включения LSA для этого маршрута в LSDB 324. LSID для LSA для существующего маршрута (маршрута, который, в противном случае имел бы конфликт LSID с добавленным маршрутом) остается неизменным. В одном варианте осуществления операция 465 подавления маршрута к хосту также включает в себя модификацию записи маршрута для маршрута к хосту в локальной RIB 326 OSPF для указания, что маршрут к хосту подавлен (например, флаг, указывающий, что маршрут к хосту подавлен, и LSA для маршрута не следует отправлять). Согласно одному варианту осуществления, модуль 435 отправки LSA пропускает тем маршруты, в записи маршрута которых установлен флаг подавления.
Если существующий маршрут является маршрутом к хосту, то операция 465 подавления маршрута к хосту включает в себя осуществление операции 480 очистки LSA для очистки LSA, связанного с этим маршрутом к хосту, из LSDB 324 (например, процесс 425 разрешения конфликтов маршрута к хосту обращается к LSDB 324 и удаляет LSA для подавленного маршрута к хосту). В одном варианте осуществления операция 465 подавления маршрута к хосту также включает в себя модификацию записи маршрута для маршрута к хосту в локальной RIB 326 OSPF для указания подавления маршрута к хосту. Таким образом, независимо от того, является ли маршрут к хосту добавляемым маршрутом или существующим маршрутом, в некоторых вариантах осуществления операция 465 подавления маршрута к хосту включает в себя модификацию записи маршрута для маршрута к хосту в локальной RIB 326 OSPF для указания подавления маршрута к хосту. Затем LSA для добавляемого маршрута перенимает LSID, который был ранее назначен LSA, связанному с маршрутом к хосту. Затем модуль 435 отправки LSA может осуществлять операцию 475 отправки LSA для отправки LSA с этим LSID для маршрута (который затем сохраняется в LSDB 324). В целях объяснения, маршрут к хосту, который подавляется, иногда именуется “подавляемым” маршрутом, и маршрут, который связан с подавляемым маршрутом, который, в противном случае, имел бы конфликт LSID с подавляемым маршрутом, иногда именуется “маршрутом-подавителем”.
Следует понимать, что маршрут, который, в противном случае, имел бы конфликт LSID с подавленным маршрутом к хосту, обеспечивает IP-досягаемость для диапазона, категоризующего маску маршрута к хосту. Так, например, перераспределяемые маршруты досягаемы в автономной системе даже при наличии подавленных IP-маршрутов к хосту.
Модуль 320 OSPF связывает подавляемый маршрут и маршрут-подавитель, благодаря чему, при удалении маршрута-подавителя, подавляемый маршрут автоматически добавляется, и для этого маршрута отправляется LSA с LSID, который был назначен маршруту-подавителю. Например, процесс 425 разрешения конфликтов маршрута к хосту связывает подавляемый маршрут с маршрутом-подавителем. В одном варианте осуществления изобретения связь имеет место в локальной RIB 326 OSPF. Например, в одном варианте осуществления, записи маршрута в локальной RIB 326 OSPF указывают, подавляется ли маршрут другим маршрутом, и идентификацию этого маршрута, и подавляет ли маршрут другой маршрут, и идентификацию этого маршрута.
При наличии конфликта LSID, и если ни маршрут, который добавляется, ни существующий маршрут не является маршрутом к хосту, вызывается процесс 430 разрешения конфликтов маршрута не к хосту. Согласно одному варианту осуществления, процесс 430 разрешения конфликтов маршрута не к хосту является модифицированной версией алгоритма разрешения конфликтов LSID, описанного в RFC 2328. Процесс 430 разрешения конфликтов маршрута не к хосту выбирает маршрут с самой длинной маской и определяет, связан ли этот маршрут с подавленным маршрутом (т.е. является ли выбранный маршрут маршрутом-подавителем подавляемого маршрута к хосту). Следует понимать, что маршрутами-подавителями могут быть только те выбранные маршруты LSA которых в данный момент существуют в LSDB (таким образом, добавляемый маршрут не может быть маршрутом-подавителем).
Если выбранный маршрут является маршрутом-подавителем, то процесс 430 разрешения конфликтов маршрута не к хосту осуществляет операцию 470 переноса маршрута-подавителя для переноса связи с выбранного маршрута (маршрута с более длинной маской маршрута) на маршрут с более короткой маской маршрута (например, путем модификации записей маршрута в локальной RIB 326 OSPF). Перенос связи происходит потому, что выбранному маршруту будет назначен другой LSID, и маршрут, который не выбран (маршрут с более короткой маской маршрута) получит LSID, который был назначен выбранному маршруту. LSID, который использовался бы подавленным маршрутом к хосту, не изменяется.
Для выбранного маршрута генерируется новый предварительный LSID (например, генератор 415 предварительных LSID осуществляет побитовую операцию НЕ над маской выбранного маршрута и осуществляет побитовую операцию ИЛИ над этим результатом с префиксом выбранного маршрута (по аналогии с тем, что определено в RFC 2328). После генерации нового предварительного LSID для выбранного маршрута снова осуществляется операция 460 проверки конфликта LSID, поскольку возможно, что этот новый предварительный LSID уже назначен LSA для другого маршрута (который может быть или не быть маршрутом к хосту). В отсутствие конфликта, LSA для этого маршрута может отправляться с предварительным LSID. Маршрут, который не выбран, берет на себя использование LSID, который был ранее назначен LSA выбранного маршрута.
Если выбранный маршрут не является маршрутом-подавителем, то процесс 430 разрешения конфликтов маршрута не к хосту генерирует новый предварительный LSID для выбранного маршрута по аналогии с тем, что определено в RFC 2328. Снова осуществляется операция 460 проверки конфликта LSID для определения, назначен ли уже новый предварительный LSID LSA для другого маршрута. Маршрут, который не выбран, берет на себя использование LSID, который был ранее назначен LSA выбранного маршрута.
На Фиг. 5 показана схема обработки данных, демонстрирующая иллюстративный процесс удаления маршрута, включающий в себя отмену подавления маршрутов, согласно одному варианту осуществления изобретения. На Фиг. 5 показаны взаимодействия между модулем 355 удаления маршрута и модулем 350 добавления маршрута, локальной RIB 326 OSPF и LSDB 324.
В соответствии с принятой инструкцией удалить маршрут, модуль 355 удаления маршрута вызывает модуль 525 отмены подавления. Модуль 525 отмены подавления осуществляет операцию 560 проверки маршрута-подавителя для определения, связан ли в данный момент маршрут, подлежащий удалению, с подавленным маршрутом (т.е. является ли маршрут маршрутом-подавителем). В одном варианте осуществления операция 560 проверки маршрута-подавителя включает в себя обращение к записи маршрута для маршрута, подлежащего удалению, в локальной RIB 326 OSPF (например, для определения установлен ли флаг подавителя для маршрута, подлежащего удалению). Если флаг подавителя установлен, модуль 525 отмены подавления осуществляет поиск маршрута в локальной RIB 326 OSPF с ключами (LSID, IP хост-маской), где значением LSID является LSID, которое использовалось маршрутом-подавителем. Если поиск оканчивается неудачей (например, возвращает значение NULL), значит подавляемый маршрут уже удален. Однако, если поиск возвращает маршрут, то модуль 525 отмены подавления отменяет подавление этого маршрута (например, отправляет LSA с LSID, которое использовалось маршрутом-подавителем). В другом варианте осуществления запись маршрута для маршрута-подавителя в локальной RIB 326 OSPF также указывает идентификацию подавляемого маршрута. В одном варианте осуществления модуль 525 отмены подавления также, в необязательном порядке, определяет, подавлен ли в данный момент удаляемый маршрут (т.е., является ли маршрут подавляемым маршрутом).
Если удаляемый маршрут является маршрутом-подавителем, то модуль 525 отмены подавления осуществляет операцию 570 отмены подавления подавляемого маршрута для отмены подавления подавляемого маршрута. Согласно одному варианту осуществления, операция 570 отмены подавления подавляемого маршрута включает в себя осуществление доступа к и модификацию записи маршрута для подавляемого маршрута в локальной RIB 326 OSPF для удаления всякого указания, что маршрут к хосту подавлен (например, очистки флага, указывающего, что маршрут к хосту является подавляемым маршрутом). Затем модуль 355 удаления маршрута вызывает модуль 350 добавления маршрута для добавления маршрута к хосту со снятым подавлением. Согласно одному варианту осуществления, модуль 350 добавления маршрута будет осуществлять операцию 575 добавления маршрута со снятым подавлением, которая назначает LSID для LSA, связанного с маршрутом к хосту со снятым подавлением, который был ранее назначен маршруту-подавителю (т.е. маршрут к хосту со снятым подавлением перенимает LSID, который был ранее назначен маршруту-подавителю).
Следует понимать, что поскольку маршрут-подавитель категоризует подавляемый им маршрут, подавляемый маршрут становится недосягаемым при удалении маршрута-подавителя до этого подавляемого маршрута. Благодаря отмене подавления этого маршрута и объявления LSA для этого маршрута по сети, маршрут к хосту со снятым подавлением вновь становится досягаемым.
Модуль 355 удаления маршрута также осуществляет операцию 580 очистки LSA для удаления LSA, связанного с удаляемым маршрутом (например, модуль 525 отмены подавления обращается к LSDB 324 и удаляет LSA, связанное с удаляемым маршрутом). В одном варианте осуществления модуль 355 удаления маршрута также удаляют запись маршрута для удаляемого маршрута из локальной RIB 326 OSPF.
На Фиг. 6 показана логическая блок-схема, демонстрирующая иллюстративные операции, осуществляемые в процессе добавления маршрута, включая разрешение конфликтов LSID, согласно одному варианту осуществления изобретения. Фиг. 6 будет описана со ссылкой на иллюстративные назначения LSID, показанные на Фиг. 8 и 9, однако следует понимать, что операции, показанные на Фиг. 6, могут осуществляться со ссылкой на другие назначения LSID. Кроме того, операции, показанные на Фиг. 6, будут описаны со ссылкой на иллюстративный вариант осуществления, показанный на Фиг. 4. Однако следует понимать, что операции, показанные на Фиг. 6, могут осуществляться согласно вариантам осуществления изобретения, отличным от рассмотренных со ссылкой на Фиг. 4, и варианты осуществления, рассмотренные со ссылкой на Фиг. 4, могут осуществлять операции, отличные от рассмотренных со ссылкой на Фиг. 6.
В блоке 610 модуль 320 OSPF начинает процесс добавления маршрута для маршрута 1 [10.0.0.0, 255.255.0.0], показанный на Фиг. 8. Маршрут может быть изучен из других маршрутов OSPF, перераспределен другим протоколом или статически сконфигурирован. В целях объяснения, на Фиг. 8 представлено назначение LSID для LSA, связанных с маршрутами, которые изучены в элементе 220 сети в разные моменты времени. Первоначально (до добавления маршрута 1), в LSDB не существует LSA, и поэтому LSID не назначены.
Процедура переходит от блока 610 к блоку 615, где начинается процесс назначения LSID. Согласно Фиг. 4, модуль 410 назначения LSID начинает назначение LSID для маршрута 1. Затем процедура переходит к блоку 620, где генератор 415 предварительных LSID генерирует предварительный LSID для маршрута 1. В одном варианте осуществления предварительный LSID генерируется согласно RFC 2328. Например, предварительный LSID для маршрута 1 является сетевым адресом маршрута (10.0.0.0).
1
Процедура переходит от блока 620 к блоку 625, где модуль 420 разрешения конфликтов LSID определяет, конфликтует ли предварительный LSID для маршрута 1 с LSID существующего маршрута. Поскольку в данный момент не назначено ни одного LSID, конфликт LSID отсутствует. Соответственно, процедура переходит к блоку 630, где обработка выполняется стандартно (например, LSA отправляется для маршрута 1 и ему назначается LSID 10.0.0.0). Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 связан со значением LSID 10.0.0.0.
Маршрут 2 [10.0.0.0, 255.255.255.0], показанный на Фиг. 8, является следующим маршрутом, подлежащим добавлению. Предварительный LSID для маршрута 2 является сетевым адресом маршрута (10.0.0.0). Поскольку маршрут 1 связан с LSID 10.0.0.0, существует конфликт LSID. Соответственно, процедура переходит от блока 625 к блоку 635.
В блоке 635 производится определение, является ли маршрут 1 или маршрут 2 маршрутом к хосту. Поскольку ни один из этих маршрутов не является маршрутом к хосту (ни один из них не имеет хост-маски), процедура переходит к блоку 640. Согласно одному варианту осуществления, операции, описанные со ссылкой на блоки 640-660, осуществляются процессом 430 разрешения конфликтов маршрута не к хосту. В блоке 640 выбирается маршрут 2, поскольку он имеет более длинную маску маршрута, чем маршрут 1. Процедура переходит от блока 640 к блоку 645.
В блоке 645 процесс 430 разрешения конфликтов маршрута не к хосту определяет, связан ли маршрут 2 с подавленным маршрутом. Например, процесс 430 разрешения конфликтов маршрута не к хосту обращается к записи для маршрута 2 в локальной RIB 326 OSPF (например, для определения установлен ли флаг подавляемого). Поскольку маршрут 2 в данный момент не связан с подавленным маршрутом, процедура переходит к блоку 655. В блоке 655 над маской маршрута 2 (255.255.255.0) осуществляется побитовая операция НЕ, в результате чего получается значение 0.0.0.255. Процедура переходит от блока 655 к блоку 660, где новый предварительный LSID для маршрута 2 является результатом побитовой операции ИЛИ результата побитовой операции НЕ с предварительным LSID. Таким образом, новый предварительный LSID для маршрута 2 является значением 0.0.0.255 | 10.0.0.0, которое равно 10.0.0.255.
2
Процедура переходит от блока 660 обратно к блоку 625, где модуль 420 разрешения конфликтов LSID определяет, конфликтует ли предварительный LSID 10.0.0.255 с LSID, связанным с существующим маршрутом. Согласно Фиг. 8, LSID 10.0.0.255 в данный момент не назначен LSA для другого маршрута. Таким образом, процедура переходит к блоку 630, где обработка выполняется стандартно, и LSA отправляется для маршрута 2, и ему назначается LSID 10.0.0.255. Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 связан со значением LSID 10.0.0.0, и маршрут 2 связан со значением LSID 10.0.0.255.
Маршрут 3 [10.0.0.0, 255.255.255.255], показанный на Фиг. 8, является следующим маршрутом, подлежащим добавлению. Предварительный LSID для маршрута 3 является сетевым адресом маршрута (10.0.0.0) (например, в результате осуществления блока 620). Поскольку маршрут 1 связан с LSID 10.0.0.0, существует конфликт LSID. Соответственно, процедура переходит от блока 625 к блоку 635.
В блоке 635 модуль 420 разрешения конфликтов LSID определяет, является ли маршрут 1 или маршрут 3 маршрутом к хосту. Поскольку маршрут 3 является маршрутом к хосту (он имеет хост-маску), процедура переходит к блоку 665. Согласно одному варианту осуществления, операции, описанные со ссылкой на блоки 665 и 670, осуществляются процессом 425 разрешения конфликтов маршрута к хосту.
В блоке 665 процесс 425 разрешения конфликтов маршрута к хосту подавляет маршрут 3, поскольку он является маршрутом к хосту. Поскольку маршрут 3 находится в процессе добавления (и, таким образом, в данный момент не существует LSA для маршрута 3), подавление маршрута 3 включает в себя предотвращение отправки LSA для маршрута 3. В одном варианте осуществления подавление маршрута к хосту также включает в себя модификацию записи маршрута для маршрута 3 в локальной RIB 326 OSPF для указания, что маршрут 3 подавляется (например, устанавливается флаг подавляемого для маршрута 3 в локальной RIB 326 OSPF). Следует понимать, что, хотя маршрут 3 подавляется, маршрут 1 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 3.
Процедура переходит от блока 665 к блоку 670, где процесс 425 разрешения конфликтов маршрута к хосту связывает маршрут 3 с маршрутом 1 (например, связывает подавляемый маршрут с маршрутом-подавителем). Как будет описано более подробно ниже, маршрут 3 и маршрут 1 связаны так, что если маршрут 1 удаляется до маршрута 3, LSA для маршрута 3 может отправляться с LSID, назначенным маршруту 1. Связь между маршрутом 3 и маршрутом 1 может осуществляться по-разному в разных вариантах осуществления. Например, запись маршрута для маршрута 1 в локальной RIB 326 OSPF может модифицироваться для указания, что он является маршрутом-подавителем (например, устанавливается флаг подавителя) и, в необязательном порядке, что он подавляет маршрут 3. Запись маршрута для маршрута 3 в локальной RIB 326 OSPF также может модифицироваться для указания, что он является подавляемым маршрутом (например, устанавливается флаг подавляемого) и, в необязательном порядке, что он является подавляемый маршрутом 1. В порядке еще одного примера, для связывания маршрута 3 с маршрутом 1 можно использовать структуру данных, отличную от локальной RIB 326 OSPF.
3
Процедура переходит от блока 670 к блоку 675, где обработка OSPF продолжается. Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 связан со значением LSID 10.0.0.0 и является подавителем маршрута 3, маршрут 2 связан со значением LSID 10.0.0.255, и маршрут 3 является подавляемым маршрутом (подавляемый маршрутом 1).
Маршрут 4 [10.0.0.255, 255.255.255.255], показанный на Фиг. 8, является следующим маршрутом, подлежащим добавлению. Предварительный LSID для маршрута 4 является сетевым адресом маршрута (10.0.0.255) (например, в результате осуществления блока 620). Модуль 420 разрешения конфликтов LSID определяет, что конфликт LSID существует, поскольку значение 10.0.0.255 в данный момент связано с маршрутом 2. Соответственно, процедура переходит от блока 625 к блоку 635.
В блоке 635 модуль 420 разрешения конфликтов LSID определяет, является ли маршрут 2 или маршрут 4 маршрутом к хосту. Поскольку маршрут 4 является маршрутом к хосту (он имеет хост-маску), процедура переходит к блоку 665. В блоке 665 процесс 425 разрешения конфликтов маршрута к хосту подавляет маршрут 4, поскольку он является маршрутом к хосту. Поскольку маршрут 4 находится в процессе добавления (и, таким образом, в данный момент не существует LSA для маршрута 4), подавление маршрута 4 включает в себя предотвращение отправки LSA для маршрута 4. В одном варианте осуществления, подавление маршрута к хосту также включает в себя модификацию записи маршрута для маршрута 4 в локальной RIB 326 OSPF для указания, что маршрут 4 подавляется. Следует понимать, что, хотя маршрут 4 подавляется, маршрут 2 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 4.
4
Процедура переходит от блока 665 к блоку 670, где процесс 425 разрешения конфликтов маршрута к хосту связывает маршрут 4 с маршрутом 2 (подавляемый маршрут с маршрутом-подавителем) так, что если маршрут 2 удаляется до маршрута 4, LSA для маршрута 4 может отправляться с LSID, назначенным маршруту 2. Связь может осуществляться по аналогии с описанным выше применительно к маршрутам 1 и 3. Процедура переходит от блока 670 к блоку 675, где обработка OSPF продолжается. Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 связан со значением LSID 10.0.0.0 и является подавителем маршрута 3, маршрут 2 связан со значением LSID 10.0.0.255 и является подавителем маршрута 4, маршрут 3 является подавляемым маршрутом (подавляется маршрутом 1), и маршрут 4 является подавляемым маршрутом (подавляется маршрутом 2).
4
Таким образом, после момента T, показанного на Фиг. 8, LSDB 324 включает в себя LSA, которому назначен LSID 10.0.0.0 (связанный с маршрутом 1), и LSA, которому назначен LSID 10.0.0.255 (связанный с маршрутом 2). Кроме того, маршрут 1 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 3 (который подавлен), и маршрут 2 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 4 (который подавлен).
На Фиг. 7 показана логическая блок-схема, демонстрирующая иллюстративные операции, осуществляемые в процессе удаления маршрута согласно одному варианту осуществления изобретения. Фиг. 7 будет описана со ссылкой на иллюстративные назначения LSID, показанные на Фиг. 8 и 9, однако следует понимать, что операции, показанные на Фиг. 7, могут осуществляться со ссылкой на другие назначения LSID. Кроме того, операции, показанные на Фиг. 7, будут описаны со ссылкой на иллюстративный вариант осуществления, показанный на Фиг. 5. Однако следует понимать, что операции, показанные на Фиг. 7, могут осуществляться согласно вариантам осуществления изобретения, отличным от рассмотренных со ссылкой на Фиг. 5, и варианты осуществления, рассмотренные со ссылкой на Фиг. 5 могут осуществлять операции, отличные от рассмотренных со ссылкой на Фиг. 7.
В блоке 710 модуль 320 OSPF начинает процесс удаления маршрута для маршрута 1 [10.0.0.0, 255.255.0.0], показанного на Фиг. 8. Следует понимать, что маршрут может быть удален по многим причинам (например, принадлежность абонента маршрута, который завершил свой сеанс, и т.д.). Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 1 с подавленным маршрутом. В одном варианте осуществления модуль 355 удаления маршрута обращается к записи маршрута для маршрута 1 в локальной RIB 326 OSPF для определения, установлен ли флаг подавителя. Поскольку маршрут 1 является маршрутом-подавителем маршрута 3, процедура переходит к блоку 725.
В блоке 725 модуль 525 отмены подавления отменяет подавление подавленного маршрута (маршрута 3). Модуль 525 отмены подавления определяет идентификацию подавленного маршрута через связь между маршрутом-подавителем (маршрутом 1) и подавленным маршрутом (маршрутом 3). Например, в некоторых вариантах осуществления, запись маршрута для маршрута 1 в локальной RIB 326 OSPF указывает, что маршрут 1 является маршрутом-подавителем, но не указывает идентификацию подавленного маршрута. В таких вариантах осуществления поиск маршрута осуществляется в локальной RIB 326 OSPF с ключами (LSID, IP хост-маской), где значением LSID является LSID, который был назначен LSA для маршрута 1. Такой поиск маршрута возвращает идентификацию маршрута 3. В других вариантах осуществления запись маршрута для маршрута 1 в локальной RIB 326 OSPF указывает, что он является маршрутом-подавителем, и также указывает идентификацию подавляемого маршрута (маршрут 3). Отмена подавления маршрута 3 также включает в себя модификацию записи в локальной RIB 326 OSPF для маршрута 3, производимую модулем 525 отмены подавления для удаления указания, что маршрут 3 является подавленным маршрутом (например, путем очистки флага подавляемого).
5
Процедура переходит от блока 725 к блоку 730, где LSA, связанное с маршрутом 1, очищается из LSDB 324 и удаляется из локальной RIB 326 OSPF. Процедура переходит от блока 730 к блоку 735, где начинается процесс добавления маршрута 3 (например, процедура переходит к блоку 610, показанному на Фиг. 6). В процессе добавления маршрута для маршрута 3, LSA с LSID, который был назначен маршруту 1 (10.0.0.0), отправляется для маршрута 3. Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 удален, маршрут 2 связан со значением LSID 10.0.0.255 и является подавителем маршрута 4, маршрут 3 теперь освобожден от подавления и связан со значением LSID 10.0.0.0, и маршрут 4 является подавляемым маршрутом (подавляется маршрутом 2).
Следует понимать, что в некоторых вариантах осуществления изобретения этап очистки существующего LSA (LSA для маршрута, который удаляется) и этап отправки нового LSA (LSA с тем же LSID, что и удаленный LSA, который отправляется в данный момент (например, LSA для маршрута к хосту)) осуществляются одновременно, просто путем замены существующего LSA новым LSA.
Маршрут 2 [10.0.0.0, 255.255.255.0], показанный на Фиг. 8, является следующим маршрутом, подлежащим удалению. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 2 с подавленным маршрутом. Поскольку маршрут 2 является маршрутом-подавителем маршрута 4, процедура переходит к блоку 725. В блоке 725 модуль 525 отмены подавления отменяет подавление маршрута 4, в том числе, модифицирует запись в локальной RIB 326 OSPF для маршрута 4 для удаления указания, что маршрут 4 является подавленным маршрутом (например, путем очистки флага подавляемого).
6
Процедура переходит от блока 725 к блоку 730, где LSA, связанное с маршрутом 2, очищается из LSDB 324 и удаляется из локальной RIB 326 OSPF. Процедура переходит от блока 730 к блоку 735, где начинается процесс добавления маршрута 4 (например, процедура переходит к блоку 610, показанному на Фиг. 6), в процессе добавления маршрута для маршрута 4, LSA с LSID, который был назначен маршруту 1 (10.0.0.255), отправляется для маршрута 4. Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 удален, маршрут 2 удален, маршрут 3 связан со значением LSID 10.0.0.0, и маршрут 4 теперь освобожден от подавления и связан со значением LSID 10.0.0.255.
7
Маршрут 3 [10.0.0.0, 255.255.255.255], показанный на Фиг. 8, является следующим маршрутом, подлежащим удалению. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 3 с подавленным маршрутом. Поскольку маршрут 3 не связан с подавленным маршрутом, процедура переходит к блоку 720, где выполняется альтернативное действие (например, процесс удаления осуществляется нормально, и LSA, связанное с маршрутом 3, очищается из LSDB 324). Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 удален, маршрут 2 удален, маршрут 3 удален и маршрут 4 теперь освобожден от подавления и связан со значением LSID 10.0.0.255.
8
Маршрут 4 [10.0.0.255, 255.255.255.255], показанный на Фиг. 8, является следующим маршрутом, подлежащим удалению. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 4 с подавленным маршрутом. Поскольку маршрут 4 не связан с подавленным маршрутом, процедура переходит к блоку 720, где выполняется альтернативное действие (например, процесс удаления осуществляется нормально, и LSA, связанное с маршрутом 4, очищается из LSDB 324). Таким образом, согласно Фиг. 8, в момент времени T, маршрут 1 удален, маршрут 2 удален, маршрут 3 удален и маршрут 4 удален.
На Фиг. 9 показана блок-схема, демонстрирующая назначения LSID для набора маршрутов, которые приходят в другом порядке, чем показано на Фиг. 8, согласно одному варианту осуществления изобретения. Согласно Фиг. 9, добавляются те же маршруты, что и на Фиг. 8 (например, маршрут 1 [10.0.0.0, 255.255.0.0], маршрут 2 [10.0.0.0, 255.255.255.0], маршрут 3 [10.0.0.0, 255.255.255.255] и маршрут 4 [10.0.0.255, 255.255.255.255]); однако они добавляются в другом порядке, чем на Фиг. 8.
Маршрут 2 [10.0.0.0, 255.255.255.0], показанный на Фиг. 9, является первым маршрутом, подлежащим добавлению. В блоке 610 модуль 320 OSPF начинает процесс добавления маршрута для маршрута 2, показанного на Фиг. 9. Аналогично описанному со ссылкой на Фиг. 8, первоначально (до добавления маршрута 2), в LSDB нет LSA, и поэтому ни один LSID не назначен. Процедура переходит от блока 610 к блоку 615, где начинается процесс назначения LSID. Со ссылкой на Фиг. 4, модуль 410 назначения LSID начинает назначение LSID для маршрута 2. Затем процедура переходит к блоку 620, где генератор 415 предварительных LSID генерирует предварительный LSID для маршрута 2. В одном варианте осуществления предварительный LSID генерируется согласно RFC 2328. Например, предварительный LSID для маршрута 2 является сетевым адресом маршрута (10.0.0.0).
1
Процедура переходит от блока 620 к блоку 625, где модуль 420 разрешения конфликтов LSID определяет, конфликтует ли предварительный LSID для маршрута 2 с LSID, связанным с существующим маршрутом. Поскольку в данный момент не назначено ни одного LSID, конфликт отсутствует. Соответственно, процедура переходит к блоку 630, где обработка выполняется стандартно (например, LSA, связанное с маршрутом 2, отправляется, и ему назначается значение LSID 10.0.0.0). Таким образом, согласно Фиг. 9, в момент времени T маршрут 2 связан со значением LSID 10.0.0.0.
Маршрут 3 [10.0.0.0, 255.255.255.255] является следующим маршрутом, подлежащим добавлению. Предварительный LSID для маршрута 3 является сетевым адресом маршрута (10.0.0.0). Поскольку маршрут 2 связан с LSID 10.0.0.0, существует конфликт LSID. Соответственно, процедура переходит от блока 625 к блоку 635.
В блоке 635 производится определение, является ли маршрут 2 или маршрут 3 маршрутом к хосту. Поскольку маршрут 3 является маршрутом к хосту (он имеет хост-маску), процедура переходит к блоку 665. В блоке 665 процесс 425 разрешения конфликтов маршрута к хосту подавляет маршрут 3, поскольку он является маршрутом к хосту. Поскольку маршрут 3 находится в процессе добавления (и, таким образом, в данный момент не существует LSA для маршрута 3), подавление маршрута 3 включает в себя предотвращение отправки LSA для маршрута 3. В одном варианте осуществления, подавление маршрута к хосту также включает в себя модификацию записи маршрута для маршрута 3 в локальной RIB OSPF 326 для указания, что маршрут 3 подавляется (например, путем установки флага подавляемого). Следует понимать, что, хотя маршрут 3 подавляется, маршрут 2 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 3.
Процедура переходит от блока 665 к блоку 670, где процесс 425 разрешения конфликтов маршрута к хосту связывает маршрут 3 с маршрутом 2 (например, связывает подавляемый маршрут с маршрутом-подавителем). Как будет описано более подробно ниже, маршрут 3 и маршрут 2 связаны так, что если маршрут 2 удаляется до маршрута 3, LSA для маршрута 3 может отправляться с LSID, назначенным маршруту 2. Маршруты могут быть связаны аналогично описанному здесь ранее (например, процесс разрешения конфликтов маршрута к хосту предписывает модификацию записи для маршрута 2 для указания, что он является маршрутом-подавителем и, в необязательном порядке, что он подавляет маршрут 3).
2
Процедура переходит от блока 670 к блоку 675, где обработка OSPF продолжается. Таким образом, согласно Фиг. 9, в момент времени T, маршрут 2 связан со значением LSID 10.0.0.0 и является подавителем маршрута 3, и маршрут 3 является подавляемым маршрутом (подавляется маршрутом 2).
3
Маршрут 4 [10.0.0.255, 255.255.255.255], показанный на Фиг. 9, является следующим маршрутом, подлежащим добавлению. Предварительный LSID для маршрута 4 является сетевым адресом маршрута (10.0.0.255) (например, предварительный LSID генерируется в результате осуществления блока 620). Модуль 420 разрешения конфликтов LSID определяет в блоке 625, что конфликт LSID отсутствует, поскольку значение 10.0.0.255 в данный момент не связано с другим маршрутом. Соответственно, процедура переходит от блока 625 к блоку 630, где обработка выполняется стандартно (например, LSA, связанное с маршрутом 4, отправляется, и ему назначается значение LSID 10.0.0.255). Таким образом, согласно Фиг. 9, в момент времени T, маршрут 2 связан со значением LSID 10.0.0.0 и является подавителем маршрута 3, маршрут 3 является подавляемым маршрутом (подавляется маршрутом 2) и маршрут 4 связан со значением LSID 10.0.0.255.
Маршрут 1 [10.0.0.0, 255.255.0.0], показанный на Фиг. 9, является следующим маршрутом, подлежащим добавлению. Предварительный LSID для маршрута 1 является сетевым адресом маршрута (10.0.0.0) (например, предварительный LSID генерируется в результате осуществления блока 620). Модуль 420 разрешения конфликтов LSID определяет в блоке 625, что существует конфликт LSID, поскольку значение 10.0.0.0 связано с маршрутом 2. Соответственно, процедура переходит от блока 625 к блоку 635.
В блоке 635 модуль 420 разрешения конфликтов LSID определяет, является ли маршрут 1 или маршрут 2 маршрутом к хосту. Поскольку ни один из этих маршрутов не является маршрутом к хосту (ни один из них не имеет хост-маски), процедура переходит к блоку 640. В блоке 640 выбирается маршрут 2, поскольку он имеет более длинную маску маршрута, чем маршрут 1. Процедура переходит от блока 640 к блоку 645.
В блоке 645 процесс 430 разрешения конфликтов маршрута не к хосту определяет, связан ли маршрут 2 с подавленным маршрутом. Например, процесс 430 разрешения конфликтов маршрута не к хосту обращается к записи для маршрута 2 в локальной RIB 326 OSPF для определения, связан ли маршрут 2 с подавленным маршрутом (например, установлен ли флаг подавителя для маршрута 2). Поскольку маршрут 2 является маршрутом-подавителем, который подавляет маршрут 3, процедура переходит к блоку 650.
В блоке 650 процесс 430 разрешения конфликтов маршрута не к хосту переносит связь с маршрутом 3 с маршрута 2 на маршрут 1. Другими словами, поскольку маршрут 1 перенимает у маршрута 2 роль маршрута-подавителя маршрута 3, маршрут 1 теперь связан с маршрутом 3. В некоторых вариантах осуществления запись маршрута для маршрута 2 в локальной RIB 326 OSPF модифицируется для удаления указания, что он является маршрутом-подавителем (например, путем очистки флага подавителя), и запись маршрута для маршрута 1 модифицируется для включения указания, что он является маршрутом-подавителем (например, путем установки флага подавителя для этой записи). В некоторых вариантах осуществления запись для маршрута 1 также модифицируется для идентификации подавляемого маршрута (например, маршрута 3). В некоторых вариантах осуществления запись маршрута для маршрута 3 в локальной RIB 326 OSPF модифицируется для указания, что маршрут 1 теперь является маршрутом, который подавляет маршрут 3.
Маршрут 1 перенимает у маршрута 2 роль маршрута-подавителя, поскольку маршруту 2 будут назначаться разные LSID согласно RFC 2328 (он имеет более длинную маску маршрута, чем маршрут 1). Статус маршрута 3 «подавленный» не изменяется во избежание конфликта LSID с маршрутом 1, и поскольку он является маршрутом к хосту. Таким образом, маршрут 1 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 3.
Процедура переходит от блока 650 к блоку 655, где над маской маршрута 2 осуществляется побитовая операция НЕ (255.255.255.0), в результате чего получается значение 0.0.0.255. Процедура переходит от блока 655 к блоку 660, где новый предварительный LSID для маршрута 2 является результатом побитовой операции ИЛИ на результатом побитовой операции НЕ с предварительным LSID. Таким образом, новый предварительный LSID для маршрута 2 является значением 0.0.0.255|10.0.0.0, которое равно 10.0.0.255.
Процедура переходит от блока 660 обратно к блоку 625, где модуль 420 разрешения конфликтов LSID определяет, конфликтует ли предварительный LSID 10.0.0.255 с LSID, связанным с существующим маршрутом. Согласно Фиг. 9, LSID 10.0.0.255 в данный момент назначен LSA для маршрута 4. Соответственно, процедура переходит к блоку 635, где модуль 420 разрешения конфликтов LSID определяет, является ли один из маршрутов 2 и 4 маршрутом к хосту. Поскольку маршрут 4 является маршрутом к хосту, процедура переходит к блоку 665.
В блоке 665 процесс 425 разрешения конфликтов маршрута к хосту подавляет маршрут 4, поскольку он является маршрутом к хосту. Поскольку маршрут 4 уже связан с одним или несколькими LSA, подавление маршрута 4 включает в себя очистку LSA для маршрута 4 из LSDB 324 и модификацию записи маршрута для маршрута 4 в локальной RIB 326 OSPF для указания, что маршрут 4 является подавляемым маршрутом (например, путем установки флага подавляемого) и, в необязательном порядке, что он подавляется маршрутом 2. Следует понимать, что маршрут 2 обеспечивает IP-досягаемость для диапазона, категоризующего маршрут 4.
Процедура переходит от блока 665 к блоку 670, где процесс 425 разрешения конфликтов маршрута к хосту связывает маршрут 4 с маршрутом 2 так, что если маршрут 2 удаляется до маршрута 4, LSA для маршрута 4 может отправляться с LSID, связанным с маршрутом 2. Связь между маршрутом 4 и маршрутом 2 может осуществляться по аналогии с описанным выше.
4
Процедура переходит от блока 670 к блоку 675, где обработка OSPF продолжается нормальным образом. Таким образом, согласно Фиг. 9, в момент времени T, маршрут 1 связан со значением LSID 10.0.0.0 и теперь является маршрутом-подавителем маршрута 3 (перенесенного с маршрута 2), маршрут 2 больше не является маршрутом-подавителем маршрута 3 и связан со значением LSID 10.0.0.255 и теперь является маршрутом-подавителем маршрута 4, маршрут 3 является подавляемым маршрутом, который подавляется маршрутом 1, и маршрут 4 является подавляемым маршрутом, который подавляется маршрутом 2.
Со ссылкой на Фиг. 7, в блоке 710 модуль OSPF начинает процесс удаления маршрута для маршрута 1 [10.0.0.0, 255.255.0.0], показанного на Фиг. 9. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 1 с подавленным маршрутом (например, путем обращения к записи маршрута для маршрута 1 в локальной RIB 326 OSPF для определения, является ли маршрут 1 маршрутом-подавителем). Поскольку маршрут 1 является маршрутом-подавителем маршрута 3, процедура переходит к блоку 725. В блоке 725 модуль 525 отмены подавления отменяет подавление маршрута 3. Например, модуль 525 отмены подавления модифицирует запись в локальной RIB 326 OSPF для маршрута 3 для удаления указания, что маршрут 3 является подавленным маршрутом.
5
Процедура переходит от блока 725 к блоку 730, где LSA, связанное с маршрутом 1, очищается из LSDB 324. В некоторых вариантах осуществления запись маршрута для маршрута 1 также удаляется из локальной RIB 326 OSPF. Процедура переходит от блока 730 к блоку 735, где начинается процесс добавления маршрута 3 (например, процедура переходит к блоку 610, показанному на Фиг. 6). В процессе добавления маршрута для маршрута 3, LSA с LSID, который был назначен маршруту 1 (10.0.0.0), отправляется для маршрута 3. Таким образом, согласно Фиг. 9, в момент времени T маршрут 1 удален, маршрут 2 связан со значением LSID 10.0.0.255 и является подавителем маршрута 4, маршрут 3 теперь освобожден от подавления и связан со значением LSID 10.0.0.0, и маршрут 4 является подавляемым маршрутом (подавляется маршрутом 2).
6
Маршрут 4 [10.0.0.255, 255.255.255.255], показанный на Фиг. 9, является следующим маршрутом, подлежащим удалению. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 4 с подавленным маршрутом. Поскольку маршрут 4 сам является подавленным маршрутом, он не связан с подавленным маршрутом (т.е. в данный момент он не действует как маршрут-подавитель другого маршрута). Таким образом, процедура переходит к блоку 720, где выполняется альтернативное действие (например, LSA, связанное с маршрутом 4, очищается из LSDB 324, указание, что маршрут 2 является маршрутом-подавителем, который подавляет маршрут 4, удаляется, и т.д.). Таким образом, согласно Фиг. 9, в момент времени T маршрут 1 удален, маршрут 2 связан со значением LSID 10.0.0.255, но больше не является подавителем маршрута 4, маршрут 3 связан со значением LSID 10.0.00 и маршрут 4 теперь удален.
7
Маршрут 3 [10.0.0.0, 255.255.255.255], показанный на Фиг. 9, является следующим маршрутом, подлежащим удалению. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 3 с подавленным маршрутом. Согласно Фиг. 9, маршрут 3 не связан с подавленным маршрутом. Соответственно, процедура переходит к блоку 720, где выполняется альтернативное действие (например, LSA, связанное с маршрутом 3, очищается из LSDB 324). Таким образом, согласно Фиг. 9, в момент времени T маршрут 1 удален, маршрут 2 связан со значением LSID 10.0.0.255, маршрут 3 теперь удален и маршрут 4 удален.
8
Маршрут 2 [10.0.0.0, 255.255.255.0], показанный на Фиг. 9, является последним маршрутом, подлежащим удалению. Процедура переходит от блока 710 к блоку 715, где модуль 355 удаления маршрута определяет, связан ли маршрут 2 с подавленным маршрутом. Согласно Фиг. 9, маршрут 2 не связан с подавленным маршрутом. Соответственно, процедура переходит к блоку 720, где выполняется альтернативное действие (например, LSA, связанное с маршрутом 2, очищается из LSDB 324). Таким образом, согласно Фиг. 9, в момент времени T, маршрут 1 удален, маршрут 2 теперь удален, маршрут 3 удален, и маршрут 4 удален.
Следует понимать, что подавление отправки LSA для маршрутов к хосту, которые, в противном случае, имели бы конфликт LSID с существующими маршрутами, препятствует совместному использованию одного и того же LSID множественными разными маршрутами. Таким образом, можно избегать проблем, которые могут возникать вследствие того, что разные маршруты совместно используют один и тот же LSID (например, неверная топология, вопросы целостности данных, выбраковка трафика, отказы программного обеспечения и т.д.). Кроме того, маршруты-подавители обеспечивают IP-досягаемость для диапазона, категоризующего маршруты к хосту.
Описанные здесь варианты осуществления изобретения можно использовать для множественных типов LSA, включая LSA OSPF 3 типа (Summary LSA), LSA OSPF 5 типа (внешние LSA), и OSPF 7 типа (Not-So-Stubby Area External LSA). Однако следует понимать, что в описанных здесь вариантах осуществления изобретения можно использовать и другие типы LSA.
Хотя логически блок-схемы на фигурах демонстрируют конкретный порядок операций, осуществляемых определенными вариантами осуществления изобретения, следует понимать, что такой порядок является иллюстративным (например, альтернативные варианты осуществления могут осуществлять операции в другом порядке, комбинировать некоторые операции, частично совмещать некоторые операции и т.д.).
Хотя изобретение было описано применительно к нескольким вариантам осуществления, специалистам в данной области техники должно быть очевидным, что изобретение не ограничивается описанными вариантами осуществления и в практическом осуществлении допускает модификации и альтернативы, не выходящие за рамки сущности и объема, заданных формулой изобретения. Таким образом, описание следует рассматривать в порядке иллюстрации, но не ограничения.