Анализ таблиц маршрутизации, или зачем ещё сетевому инженеру Python

в 17:26, , рубрики: Cisco, python, автоматизация, ненормальное программирование, сетевая автоматизация, Сетевые технологии, теги никто не читает

Hello Habr! Эта моя первая статья на Хабре, и родилась она из вопроса на одном из профессиональных форумов. Выглядел вопрос, несколько перефразируя, следующим образом:

  • Имеется набор текстовых файлов, содержащих вывод таблиц маршрутизации с различных сетевых устройств;
  • Каждый файл содержит информацию с одного устройства;
  • Устройства могут иметь различный формат вывода таблицы маршрутизации;
  • Необходимо на основании имеющихся данных по запросу выводить путь до произвольной подсети или IP-адреса с каждого из устройств;
  • Вывод должен включать на каждом участке пути информацию о записи из таблицы маршрутизации, по которой будет смаршрутизирован пакет.

Задача мне показалась мне интересной и перекликалась с одной из собственных сетевых утилит, планируемых в перспективе.Поэтому в свободный вечер, поразмыслив над ее решением, написал Proof-of-Concept реализацию на Python 2.7 под формат Cisco IOS, IOS-XE и ASA, отвечающую основным требованиям.

В статье попытаюсь воспроизвести ход мысли и прокомментировать основные моменты.
Материал рассчитан на людей, уже базово знакомых с основами сетей и Python.
Всем заинтересовавшимся добро пожаловать под кат!

Дисклеймер

Автор статьи, будучи сетевым инженером, не является профессиональным разработчиком и может пока не знать отличие интерфейса от абстрактного класса, но всегда открыт конструктивной критике и обратной связи. Замечания по коду, выбранным подходам и алгоритмам от более опытных коллег приветствуются.

Весь код в данной статье распространяется под лицензией MIT, в т.ч. приведён «как есть» и не дает гарантий никакого рода.

Уточнение условия и выбор алгоритма решения

С учетом вводной, задачу можно разделить на две основные части: парсинг исходных файлов с таблицами маршрутизации и непосредственный поиск пути по инициализированным данным.
Подобное разделение также позволит, при необходимости, делать импорт маршрутов с устройств для поиска пути произвольным образом (к примеру, по SNMP или REST API).

Для улучшения производительности инициализацию файлов имеет смысл делать однократно при запуске скрипта.
Парсер файлов должен распознавать формат таблиц маршрутизации из различных операционных систем. Далее будет рассмотрен вариант для Cisco IOS, IOS-XE и ASA для IPv4. Поддержка других форматов и IPv6 может быть добавлена позднее.

Как известно, выбор маршрута по таблице маршрутизации делается по принципу совпадения с префиксом наибольшей длины (longest prefix match).
В качестве одного из решений для быстрого поиска такого совпадения можно по исходным данным построить префиксное дерево. Так как ограничений по внешним зависимостям у нас нет, остановимся на готовом модуле SubnetTree.

На анализируемом участке сети потенциально могут быть петли маршрутизации, они должны детектироваться и не должны влиять на работу скрипта. Кроме того, на любом из узлов может не быть маршрута до искомой подсети. Это также следует учитывать.

При наличии VRF на устройстве таблицы маршрутизации из каждого инстанса должны быть сохранены в отдельных файлах, так как с точки зрения топологии они являются отдельными маршрутизаторами.

Ограничения по производительности железа для запуска скрипта, количеству и размеру анализируемых таблиц маршрутизации в условии не заявлены, но стоит иметь их в виду.
Специфика области применения подсказывает средний лимит в 1.000.000 записей в таблице маршрутизации на одно современное устройство. На роутере с BGP Full View по состоянию на июнь 2018 фактически может быть 724.000+ маршрутов.
По грубой оценке и результатам тестов на in-memory хранение и обработку каждого 1.000.000 префиксов потребуется около 500MB RAM. Таким образом средней производительности рабочая станция с 8GB RAM (2018 год все еще держим в уме) позволит проанализировать топологию с совокупной емкостью до 14-16.000.000 маршрутов. То есть сегмент из примерно 18-20 маршрутизаторов с full view на каждом.
Для большинства случаев этого вполне достаточно, а для больших (как ударение ни ставь) сетей нужно или разбивать анализ на сегменты, или переносить логику на out-of-memory базу данных.
640КБ хватит всем.Остановимся на in-memory варианте.

Парсинг исходных файлов и выбор структур данных

Файлы с таблицами маршрутизации вынесем в отдельную суб-директорию и сделаем ее переменной:

RT_DIRECTORY = "./routing_tables"

Для Cisco IOS и IOS-XE таблица маршрутизации может выглядеть примерно так:

show ip route

S* 0.0.0.0/0 [1/0] via 10.220.88.1
10.0.0.0/8 is variably subnetted, 2 subnets, 2 masks
C 10.220.88.0/24 is directly connected, FastEthernet4
L 10.220.88.20/32 is directly connected, FastEthernet4
     1.0.0.0/32 is subnetted, 1 subnets
S       1.1.1.1 [1/0] via 212.0.0.1
                [1/0] via 192.168.0.1
D EX     10.1.198.0/24 [170/1683712] via 172.16.209.47, 1w2d, Vlan910
                       [170/1683712] via 172.16.60.33, 1w2d, Vlan60
                       [170/1683712] via 10.25.20.132, 1w2d, Vlan220
                       [170/1683712] via 10.25.20.9, 1w2d, Vlan20
     4.0.0.0/16 is subnetted, 1 subnets
O E2    4.4.0.0 [110/20] via 194.0.0.2, 00:02:00, FastEthernet0/0
     5.0.0.0/24 is subnetted, 1 subnets
D EX    5.5.5.0 [170/2297856] via 10.0.1.2, 00:12:01, Serial0/0
     6.0.0.0/16 is subnetted, 1 subnets
B       6.6.0.0 [200/0] via 195.0.0.1, 00:00:04
     172.16.0.0/26 is subnetted, 1 subnets
i L2    172.16.1.0 [115/10] via 10.0.1.2, Serial0/0
     172.20.0.0/32 is subnetted, 3 subnets
O       172.20.1.1 [110/11] via 194.0.0.2, 00:05:45, FastEthernet0/0
O       172.20.3.1 [110/11] via 194.0.0.2, 00:05:45, FastEthernet0/0
O       172.20.2.1 [110/11] via 194.0.0.2, 00:05:45, FastEthernet0/0
     10.0.0.0/8 is variably subnetted, 5 subnets, 3 masks
C       10.0.1.0/24 is directly connected, Serial0/0
D       10.0.5.0/26 [90/2297856] via 10.0.1.2, 00:12:03, Serial0/0
D       10.0.5.64/26 [90/2297856] via 10.0.1.2, 00:12:03, Serial0/0
D       10.0.5.128/26 [90/2297856] via 10.0.1.2, 00:12:03, Serial0/0
D       10.0.5.192/27 [90/2297856] via 10.0.1.2, 00:12:03, Serial0/0
     192.168.0.0/32 is subnetted, 1 subnets
D       192.168.0.1 [90/2297856] via 10.0.1.2, 00:12:03, Serial0/0
O IA 195.0.0.0/24 [110/11] via 194.0.0.2, 00:05:45, FastEthernet0/0
O E2 212.0.0.0/8 [110/20] via 194.0.0.2, 00:05:35, FastEthernet0/0
C    194.0.0.0/16 is directly connected, FastEthernet0/0

В Cisco ASA формат схожий, но, вместо длин префиксов, отображается маска подсети в десятичном представлении:

show route

S    10.1.1.0 255.255.255.0 [3/0] via 10.86.194.1, outside
C    10.86.194.0 255.255.254.0 is directly connected, outside
S*   0.0.0.0 0.0.0.0 [1/0] via 10.86.194.1, outside

Как видно из примера, маршруты, несмотря на большое разнообразие, имеют одинаковую и предсказуемую структуру, а значит могут быть обработаны регулярными выражениями.
Выходит две глобальные группы: маршруты типов Local+Connected и все остальное.
Несколько усложняет дело возможность наличия многострочных маршрутов с переменным количеством next-hop’ов. Из-за этого же проблематично читать файл для обработки построчно. Один из выходов — обработка множества совпадений итератором регулярного выражения в загруженном целиком в текстовую переменную файле.

Напишем регулярные выражения с учетом перечисленных требований и ограничений:

# Local and Connected route strings matching.
REGEXP_ROUTE_LOCAL_CONNECTED = re.compile(
     '^(?P<routeType>[L|C])s+'
    + '((?P<ipaddress>dd?d?.dd?d?.dd?d?.dd?d?)'
    + 's?'
    + '(?P<maskOrPrefixLength>(/dd?)?'
    + '|(dd?d?.dd?d?.dd?d?.dd?d?)?))'
    + ' is directly connected, '
    + '(?P<interface>S+)',
    re.MULTILINE
)
# Static and dynamic route strings matching.
REGEXP_ROUTE = re.compile(
      '^(SS?*?s?S?S?)'
    + 's+'
    + '((?P<subnet>dd?d?.dd?d?.dd?d?.dd?d?)'
    + 's?'
    + '(?P<maskOrPrefixLength>(/dd?)?'
    +'|(dd?d?.dd?d?.dd?d?.dd?d?)?))'
    + 's*'
    + '(?P<viaPortion>(?:n?s+([dd?d?/d+])s+'
    + 'vias+(dd?d?.dd?d?.dd?d?.dd?d?)(.*)n?)+)',
    re.MULTILINE
)

Оба выражения содержат именованные группы (named groups) для удобства извлечения данных при поиске совпадений и поддержания кода.
В частности, из каждого маршрута нужно получить префикс (группы subnet/interface и maskOrPrefixLength) и информацию о том, куда он ведёт (группы viaPortion/interface).

Так как выражения учитывают несколько вариантов представления префикса, в группе maskOrPrefixLength может быть как маска подсети, так и длина префикса. Будем приводить это к единому формату при обработке, остановимся на длине префикса:

def convert_netmask_to_prefix_length(mask_or_pref):
    if not mask_or_pref:
        return ""
    if re.match("^/dd?$", mask_or_pref):
        return mask_or_pref
    if re.match("^dd?d?.dd?d?.dd?d?.dd?d?$",
                mask_or_pref):
        return (
            "/"
           + str(sum([bin(int(x)).count("1") for x in mask_or_pref.split(".")]))
        )
    return ""

Добавим также регулярные выражения для построчного разбора next-hop из группы viaPortion, проверки формата IPv4-адресов и пользовательского ввода:

# Route string VIA portion matching.
REGEXP_VIA_PORTION = re.compile(
    '.*vias+(dd?d?.dd?d?.dd?d?.dd?d?).*'
)
# RegEx template string for IPv4 address matching. 
REGEXP_IPv4_STR = (
      '((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?).'
    + '(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?).'
    + '(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?).'
    + '(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?))'
)
# IPv4 CIDR notation matching in user input.
REGEXP_INPUT_IPv4 = re.compile("^" + REGEXP_IPv4_STR + "(/dd?)?$")

Теперь перенесем представление нашей сети на структуры данных Python.
Полученные в результате парсинга таблиц маршрутизации префиксы будем использовать в качестве ключей в префиксном дереве. Объект префиксного дерева наследуем из модуля SubnetTree.
Результат поиска по префиксу в дереве будет возвращать список из списка next-hop’ов и полного текстового представления соответствующего маршрута из оригинального файла.
Дополнительно создадим лист локальных интерфейсов.
Каждый маршрутизатор представим словарем, в который поместим вышеперечисленные данные.

# Example data structures
route_tree = SubnetTree.SubnetTree()
route_tree[’subnet’] = ((next_hop_1, next_hop_n), raw_route_string)
interface_list = ((interface_1, ip_address_1), (interface_n, ip_address_n))
connected_networks = ((interface_1, subnet_1), (interface_n, subnet_n))
router = {
    ‘routing_table’: route_tree,
    ‘interface_list’: interface_list,
    ‘connected_networks’: connected_networks,
}

Запрос к таблице маршрутизации вынесем в отдельную функцию:

def route_lookup(destination, router):
    if destination in router['routing_table']:
        return router['routing_table'][destination]
    else:
        return (None, None)

Каждому маршрутизатору поставим в соответствие некоторый уникальный идентификатор. Назначать его можно множеством путей, в текущем примере будет допустимо и наглядно делать это на основе имени оригинального файла.
В результате будем добавлять получившиеся объекты маршрутизаторов в словарь с ключом в виде этого уникального идентификатора.

ROUTERS = {
    ‘router_id_1’: router_1,
    ‘router_id_n’: router_n,
}

Нам также необходим механизм для поиска следующего маршрутизатора по IP-адресу next-hop’а, полученного из таблицы маршрутизации во время поиска пути. Создадим для этого еще одно глобальное префиксное дерево с ключами в виде IP-адресов всех известных маршрутизаторов в топологии и возвращаемым по ним листам с идентификатором маршрутизатора и типом интерфейса.

# Example
GLOBAL_INTERFACE_TREE = SubnetTree.SubnetTree()
GLOBAL_INTERFACE_TREE[‘ip_address’] = (router_id, interface_type)

# Returns RouterID by Interface IP address which it belongs to.
def get_rid_by_interface_ip(interface_ip):
    if interface_ip in GLOBAL_INTERFACE_TREE:
        return GLOBAL_INTERFACE_TREE[interface_ip][0]

Соберём парсер для формата IOS/IOS-XE/ASA воедино. На входе передаем ему таблицу маршрутизации в текстовом виде, на выходе получаем словарь router в заданном выше формате. 

def parse_show_ip_route_ios_like(raw_routing_table):
    router = {}
    route_tree = SubnetTree.SubnetTree()
    interface_list = []
    # Parse Local and Connected route strings in text.
    for raw_route_string in REGEXP_ROUTE_LOCAL_CONNECTED.finditer(raw_routing_table):
        subnet = (
            raw_route_string.group('ipaddress') 
          + convert_netmask_to_prefix_length(
                raw_route_string.group('maskOrPrefixLength')
            )
        )
        interface = raw_route_string.group('interface')
        route_tree[subnet] = ((interface,), raw_route_string.group(0))
        if raw_route_string.group('routeType') == 'L':
            interface_list.append((interface, subnet,))
    if not interface_list:
        print('Failed to find routing table entries in given output')
        return None
    # parse static and dynamic route strings in text
    for raw_route_string in REGEXP_ROUTE.finditer(raw_routing_table):
        subnet = (
            raw_route_string.group('subnet') 
          + convert_netmask_to_prefix_length(
                raw_route_string.group('maskOrPrefixLength')
            )
        )
        via_portion =  raw_route_string.group('viaPortion')
        next_hops= []
        if via_portion.count('via') > 1:
            for line in via_portion.splitlines():
                if line:
                    next_hops.append(REGEXP_VIA_PORTION.match(line).group(1))
        else:
            next_hops.append(REGEXP_VIA_PORTION.match(via_portion).group(1))
        route_tree[subnet] = (next_hops, raw_route_string.group(0))
    router = {
        'routing_table': route_tree,
        'interface_list': interface_list,
    }
    return router

Обернём парсер в еще одну функцию для возможности последующего добавления парсеров других форматов (например, NX-OS):

def parse_text_routing_table(raw_routing_table):
    """
    Parser functions wrapper.
    Add additional parsers for alternative routing table syntaxes here.
    """
    router = parse_show_ip_route_ios_like(raw_routing_table)
    if router:
        return router

Итак, остаётся пройтись по текстовым файлам в директории:

def do_parse_directory(rt_directory):
    new_routers = {}
    if not os.path.isdir(rt_directory):
        print("{} directory does not exist.".format(rt_directory)
            + "Check rt_directory variable value."
        )
        return None
    start_time = time()
    print("Initializing files...")
    for FILENAME in os.listdir(rt_directory):
        if FILENAME.endswith('.txt'):
            file_init_start_time = time()
            with open(os.path.join(rt_directory, FILENAME), 'r') as f:
                print ('Opening {}'.format(FILENAME))
                raw_table = f.read()
                new_router = parse_text_routing_table(raw_table)
                router_id = FILENAME.replace('.txt', '')
                if new_router:
                    new_routers[router_id] = new_router
                    if new_router['interface_list']:
                        for iface, addr in new_router['interface_list']:
                            GLOBAL_INTERFACE_TREE[addr]= (router_id, iface,)
                else:
                    print ('Failed to parse ' + FILENAME)
            print (FILENAME + " parsing has been completed in %s sec".format(
                   "{:.3f}".format(time() - file_init_start_time))
            )
    else:
        if not new_routers:
            print ("Could not find any valid .txt files with routing tables"
                 + " in {} directory".format(rt_directory)
            )
        else:
            print ("nAll files have been initialized"
                 + " in {} sec".format("{:.3f}".format(time() - start_time))
            )
            return new_routers

И, разложив все файлы в упорядоченные структуры данных, можно приниматься за вторую часть задачи.

Поиск пути по обработанным таблицам маршрутизации

В целом на этом этапе задача сводится к анализу графа сети. Маршрутизаторы являются вершинами графа, L3-линки между ними — ребрами.
Словарь ROUTERS хранит в ключах идентификаторы маршрутизаторов, а в соответствующих им значениях — ссылки на IP-адреса next-hop'ов. То есть в совокупности с GLOBAL_INTERFACE_TREE, возвращающему по IP-адресу идентификаторы маршрутизаторов, для каждой искомой подсети он определяет таблицу смежности графа.

Если же провести параллели с реальными маршрутизаторами, для поиска пути нужно воспроизвести высокоуровневую логику их работы (абстрагируясь от RIB/FIB/ASIC и прочих оптимизаций) при обработке пакета от лукапа в таблицу маршрутизации до ARP-запроса (или router_id в нашем случае) и маршрутизации или дропа пакета, в зависимости от результата.

Реализуем рекурсивный поиск пути по маршрутизаторам. Каждый участок пути будет представлен листом из router_id и raw_route_string — исходной строки маршрута на нем. Текущий путь будем записывать в кортеж path. При достижении точки назначения, отсутствии маршрута в таблице маршрутизации или next-hop'а в изученной топологии текущий path будет добавляться в результирующий кортеж paths, который и возвратит функция. 

def trace_route(source_router_id, target_ip, path=[]):
    if not source_router_id:
        return [path + [(None, None)]]
    current_router = ROUTERS[source_router_id]
    next_hop, raw_route_string = route_lookup(target_ip, current_router)
    path = path + [(source_router_id, raw_route_string)]
    paths = []
    if next_hop:
        if nexthop_is_local(next_hop[0]):
            return [path]
        for nh in next_hop:
            next_hop_rid = get_rid_by_interface_ip(nh)
            if not next_hop_rid in [r[0] for r in path]:
                inner_path = trace_route(next_hop_rid, target_ip, path)
                for p in inner_path:
                    paths.append(p)
            else:
                path = path + [(next_hop_rid+"<<LOOP DETECTED", None)]
                return [path]
    else:
        return [path]
    return paths

def nexthop_is_local(next_hop):
    interface_types = ('Eth', 'Fast', 'Gig', 'Ten', 'Port',
                      'Serial', 'Vlan', 'Tunn', 'Loop', 'Null'
    )
    for type in interface_types:
        if next_hop.startswith(type):
            return True

Добавим функцию для запуска поиска в интерактивном режиме после инициализации текстовых файлов:

def do_user_interactive_search():
    while True:
        print ('n')
        target_subnet = raw_input('Enter Target Subnet or Host: ')
        if not target_subnet:
            continue
        if not REGEXP_INPUT_IPv4.match(target_subnet.replace(' ', '')):
            print ("incorrect input")
            continue
        lookup_start_time = time()
        for rtr in ROUTERS.keys():
            subsearch_start_time = time()
            result = trace_route(rtr, target_subnet)
            if result:
                print ("n")
                print ("PATHS TO {} FROM {}".format(target_subnet, rtr))
                n = 1
                print ('Detailed info:')
                for r in result:
                    print ("Path {}:".format(n))
                    print ([h[0] for h in r])
                    for hop in r:
                        print ("ROUTER: {}".format(hop[0]))
                        print ("Matched route string: n{}".format(hop[1]))
                    else:
                        print ('n')
                    n+=1
                else:
                    print ("Path search on {} has been completed in {} sec".format(
                           rtr, "{:.3f}".format(time() - subsearch_start_time))
                    )
        else:
            print ("nFull search has been completed in {} sec".format(
                   "{:.3f}".format(time() - lookup_start_time),)
            )

Финальный штрих для объединения двух частей:

def main():
    global ROUTERS
    ROUTERS = do_parse_directory(RT_DIRECTORY)
    if ROUTERS:
        do_user_interactive_search()

if __name__ == "__main__":
    main()

И имеем готовый к работе код.

Код


import os
import re
import SubnetTree
from time import time

# Path to directory with routing table files.
# Each routing table MUST be in separate .txt file.
RT_DIRECTORY = "./routing_tables"

# RegEx template string for IPv4 address matching. 
REGEXP_IPv4_STR = (
      '((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?).'
    + '(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?).'
    + '(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?).'
    + '(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?))'
)

# IPv4 CIDR notation matching in user input.
REGEXP_INPUT_IPv4 = re.compile("^" + REGEXP_IPv4_STR + "(/dd?)?$")

# Local and Connected route strings matching.
REGEXP_ROUTE_LOCAL_CONNECTED = re.compile(
     '^(?P<routeType>[L|C])s+'
    + '((?P<ipaddress>dd?d?.dd?d?.dd?d?.dd?d?)'
    + 's?'
    + '(?P<maskOrPrefixLength>(/dd?)?'
    + '|(dd?d?.dd?d?.dd?d?.dd?d?)?))'
    + ' is directly connected, '
    + '(?P<interface>S+)',
    re.MULTILINE
)

# Static and dynamic route strings matching.
REGEXP_ROUTE = re.compile(
      '^(SS?*?s?S?S?)'
    + 's+'
    + '((?P<subnet>dd?d?.dd?d?.dd?d?.dd?d?)'
    + 's?'
    + '(?P<maskOrPrefixLength>(/dd?)?'
    +'|(dd?d?.dd?d?.dd?d?.dd?d?)?))'
    + 's*'
    + '(?P<viaPortion>(?:n?s+([dd?d?/d+])s+'
    + 'vias+(dd?d?.dd?d?.dd?d?.dd?d?)(.*)n?)+)',
    re.MULTILINE
)

# Route string VIA portion matching.
REGEXP_VIA_PORTION = re.compile(
    '.*vias+(dd?d?.dd?d?.dd?d?.dd?d?).*'
)

# Store for 'router' objects generated from input routing table files. 
# Each file is represented by single 'router' object.
# Router is referenced by Router ID (RID).
# RID is filename by default.
# Format:
#
# ROUTERS = {
#     'RID1': {'routing_table': {}, 'interface_list': ()},
#     'RID_N': {'routing_table': {}, 'interface_list': ()},
# }
# 
ROUTERS = {}

# Global search tree for Interface IP address to Router ID (RID) resolving.
# Stores Interface IP addresses as keys.
# Returns (RID, interfaceID) list.
# Interface IP addresses SHOULD be globally unique across inspected topology.
GLOBAL_INTERFACE_TREE = SubnetTree.SubnetTree()

def parse_show_ip_route_ios_like(raw_routing_table):
    """
    Parser for routing table text output.
    Compatible with both Cisco IOS(IOS-XE) 'show ip route' 
    and Cisco ASA 'show route' output format.
    Processes input text file and writes into Python data structures.
    Builds internal SubnetTree search tree in 'route_tree'.
    Generates local interface list for router in 'interface_list'
    Returns 'router' dictionary object with parsed data.
    """
    router = {}
    route_tree = SubnetTree.SubnetTree()
    interface_list = []
    # Parse Local and Connected route strings in text.
    for raw_route_string in REGEXP_ROUTE_LOCAL_CONNECTED.finditer(raw_routing_table):
        subnet = (
            raw_route_string.group('ipaddress') 
          + convert_netmask_to_prefix_length(
                raw_route_string.group('maskOrPrefixLength')
            )
        )
        interface = raw_route_string.group('interface')
        route_tree[subnet] = ((interface,), raw_route_string.group(0))
        if raw_route_string.group('routeType') == 'L':
            interface_list.append((interface, subnet,))
    if not interface_list:
        print('Failed to find routing table entries in given output')
        return None
    # parse static and dynamic route strings in text
    for raw_route_string in REGEXP_ROUTE.finditer(raw_routing_table):
        subnet = (
            raw_route_string.group('subnet') 
          + convert_netmask_to_prefix_length(
                raw_route_string.group('maskOrPrefixLength')
            )
        )
        via_portion =  raw_route_string.group('viaPortion')
        next_hops= []
        if via_portion.count('via') > 1:
            for line in via_portion.splitlines():
                if line:
                    next_hops.append(REGEXP_VIA_PORTION.match(line).group(1))
        else:
            next_hops.append(REGEXP_VIA_PORTION.match(via_portion).group(1))
        route_tree[subnet] = (next_hops, raw_route_string.group(0))
    router = {
        'routing_table': route_tree,
        'interface_list': interface_list,
    }
    return router

def parse_text_routing_table(raw_routing_table):
    """
    Parser functions wrapper.
    Add additional parsers for alternative routing table syntaxes here.
    """
    router = parse_show_ip_route_ios_like(raw_routing_table)
    if router:
        return router

def convert_netmask_to_prefix_length(mask_or_pref):
    """
    Gets subnet_mask (XXX.XXX.XXX.XXX) of /prefix_length (/XX).
    For subnet_mask, converts it to /prefix_length and returns result.
    For /prefix_length, returns as is.
    For empty input, returns "" string.
    """
    if not mask_or_pref:
        return ""
    if re.match("^/dd?$", mask_or_pref):
        return mask_or_pref
    if re.match("^dd?d?.dd?d?.dd?d?.dd?d?$",
                mask_or_pref):
        return (
            "/"
           + str(sum([bin(int(x)).count("1") for x in mask_or_pref.split(".")]))
        )
    return ""

def route_lookup(destination, router):
    """
    Performs route_tree lookup in passed router object
    for passed destination subnet.
    Returns list of next_hops with original route strings or (None,None)
    depending on lookup result.
    """
    if destination in router['routing_table']:
        return router['routing_table'][destination]
    else:
        return (None, None)

def get_rid_by_interface_ip(interface_ip):
    """Returns RouterID by Interface IP address which it belongs to."""
    if interface_ip in GLOBAL_INTERFACE_TREE:
        return GLOBAL_INTERFACE_TREE[interface_ip][0]

def nexthop_is_local(next_hop):
    """
    Check if nexthop points to local interface.
    Will be True for Connected and Local route strings on Cisco devices.
    """
    interface_types = ('Eth', 'Fast', 'Gig', 'Ten', 'Port',
                      'Serial', 'Vlan', 'Tunn', 'Loop', 'Null'
    )
    for type in interface_types:
        if next_hop.startswith(type):
            return True

def trace_route(source_router_id, target_ip, path=[]):
    """
    Performs recursive path search from source Router ID (RID) to target subnet.
    Returns tuple of path tuples.
    Each path tuple contains a sequence of Router IDs with matched route strings.
    Multiple paths are supported.
    """
    if not source_router_id:
        return [path + [(None, None)]]
    current_router = ROUTERS[source_router_id]
    next_hop, raw_route_string = route_lookup(target_ip, current_router)
    path = path + [(source_router_id, raw_route_string)]
    paths = []
    if next_hop:
        if nexthop_is_local(next_hop[0]):
            return [path]
        for nh in next_hop:
            next_hop_rid = get_rid_by_interface_ip(nh)
            if not next_hop_rid in [r[0] for r in path]:
                inner_path = trace_route(next_hop_rid, target_ip, path)
                for p in inner_path:
                    paths.append(p)
            else:
                path = path + [(next_hop_rid+"<<LOOP DETECTED", None)]
                return [path]
    else:
        return [path]
    return paths

def do_parse_directory(rt_directory):
    """
    Go through specified directory and parse all .txt files.
    Generate router objects based on parse result if any.
    Populate new_routers with those router objects.
    Default key for each router object is FILENAME.
    Return new_routers.
    """
    new_routers = {}
    if not os.path.isdir(rt_directory):
        print("{} directory does not exist.".format(rt_directory)
            + "Check rt_directory variable value."
        )
        return None
    start_time = time()
    print("Initializing files...")
    for FILENAME in os.listdir(rt_directory):
        if FILENAME.endswith('.txt'):
            file_init_start_time = time()
            with open(os.path.join(rt_directory, FILENAME), 'r') as f:
                print ('Opening {}'.format(FILENAME))
                raw_table = f.read()
                new_router = parse_text_routing_table(raw_table)
                router_id = FILENAME.replace('.txt', '')
                if new_router:
                    new_routers[router_id] = new_router
                    if new_router['interface_list']:
                        for iface, addr in new_router['interface_list']:
                            GLOBAL_INTERFACE_TREE[addr]= (router_id, iface,)
                else:
                    print ('Failed to parse ' + FILENAME)
            print (FILENAME + " parsing has been completed in {} sec".format(
                   "{:.3f}".format(time() - file_init_start_time))
            )
    else:
        if not new_routers:
            print ("Could not find any valid .txt files with routing tables"
                 + " in {} directory".format(rt_directory)
            )
        else:
            print ("nAll files have been initialized"
                 + " in {} sec".format("{:.3f}".format(time() - start_time))
            )
            return new_routers

def do_user_interactive_search():
    """
    Provides interactive search dialog for user.
    Asks user for target subnet or host in CIDR notation.
    Validates input. Prints error and goes back to start for invalid input.
    Executes path search to given target from each router in global ROUTERS.
    Prints formatted path search result.
    Goes back to start.
    """
    while True:
        print ('n')
        target_subnet = raw_input('Enter Target Subnet or Host: ')
        if not target_subnet:
            continue
        if not REGEXP_INPUT_IPv4.match(target_subnet.replace(' ', '')):
            print ("incorrect input")
            continue
        lookup_start_time = time()
        for rtr in ROUTERS.keys():
            subsearch_start_time = time()
            result = trace_route(rtr, target_subnet)
            if result:
                print ("n")
                print ("PATHS TO {} FROM {}".format(target_subnet, rtr))
                n = 1
                print ('Detailed info:')
                for r in result:
                    print ("Path {}:".format(n))
                    print ([h[0] for h in r])
                    for hop in r:
                        print ("ROUTER: {}".format(hop[0]))
                        print ("Matched route string: n{}".format(hop[1]))
                    else:
                        print ('n')
                    n+=1
                else:
                    print ("Path search on {} has been completed in {} sec".format(
                           rtr, "{:.3f}".format(time() - subsearch_start_time))
                    )
        else:
            print ("nFull search has been completed in {} sec".format(
                   "{:.3f}".format(time() - lookup_start_time),)
            )

def main():
    global ROUTERS
    ROUTERS = do_parse_directory(RT_DIRECTORY)
    if ROUTERS:
        do_user_interactive_search()

if __name__ == "__main__":
    main()

Проверка работы скрипта

Вооружимся небольшой абстрактной топологией из четырех Cisco CSR-1000v:

Анализ таблиц маршрутизации, или зачем ещё сетевому инженеру Python - 1

Они соединены попарно через интерфейсы GigabitEthernet 2 и 3. Между ними установлено соседство по EIGRP, через который анонсируются все Connected сети, включая сети на Loopback интерфейсах за каждым маршрутизатором.
Между csr1000v-01 и csr1000v-04 дополнительно поднято два GRE-туннеля, через удаленные IP-адреса которых прописаны статические маршруты на сеть 10.0.0.0/8 для тестирования петли маршрутизации.

csr1000v-01#show ip route

Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area 
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route, H - NHRP, l - LISP
       a - application route
       + - replicated route, % - next hop override, p - overrides from PfR

Gateway of last resort is not set

S     10.0.0.0/8 [1/0] via 192.168.142.2
                 [1/0] via 192.168.141.2
      172.16.0.0/16 is variably subnetted, 2 subnets, 2 masks
C        172.16.114.0/24 is directly connected, GigabitEthernet2
L        172.16.114.5/32 is directly connected, GigabitEthernet2
      192.168.2.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.2.0/24 is directly connected, GigabitEthernet1
L        192.168.2.201/32 is directly connected, GigabitEthernet1
      192.168.12.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.12.0/24 is directly connected, GigabitEthernet2
L        192.168.12.201/32 is directly connected, GigabitEthernet2
      192.168.13.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.13.0/24 is directly connected, GigabitEthernet3
L        192.168.13.201/32 is directly connected, GigabitEthernet3
D     192.168.24.0/24 [90/3072] via 192.168.12.202, 00:06:56, GigabitEthernet2
D     192.168.34.0/24 [90/3072] via 192.168.13.203, 00:06:56, GigabitEthernet3
      192.168.141.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.141.0/30 is directly connected, Tunnel141
L        192.168.141.1/32 is directly connected, Tunnel141
      192.168.142.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.142.0/30 is directly connected, Tunnel142
L        192.168.142.1/32 is directly connected, Tunnel142
      192.168.201.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.201.0/24 is directly connected, Loopback201
L        192.168.201.201/32 is directly connected, Loopback201
D     192.168.202.0/24 
           [90/130816] via 192.168.12.202, 00:05:44, GigabitEthernet2
D     192.168.203.0/24 
           [90/130816] via 192.168.13.203, 00:06:22, GigabitEthernet3
D     192.168.204.0/24 
           [90/131072] via 192.168.13.203, 00:06:56, GigabitEthernet3
           [90/131072] via 192.168.12.202, 00:06:56, GigabitEthernet2

csr1000v-02#show ip route

Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area 
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route, H - NHRP, l - LISP
       a - application route
       + - replicated route, % - next hop override, p - overrides from PfR

Gateway of last resort is not set

      192.168.2.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.2.0/24 is directly connected, GigabitEthernet1
L        192.168.2.202/32 is directly connected, GigabitEthernet1
      192.168.12.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.12.0/24 is directly connected, GigabitEthernet2
L        192.168.12.202/32 is directly connected, GigabitEthernet2
D     192.168.13.0/24 [90/3072] via 192.168.12.201, 00:46:17, GigabitEthernet2
      192.168.24.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.24.0/24 is directly connected, GigabitEthernet3
L        192.168.24.202/32 is directly connected, GigabitEthernet3
D     192.168.34.0/24 [90/3072] via 192.168.24.204, 00:46:15, GigabitEthernet3
D     192.168.201.0/24 
           [90/130816] via 192.168.12.201, 00:36:59, GigabitEthernet2
      192.168.202.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.202.0/24 is directly connected, Loopback202
L        192.168.202.202/32 is directly connected, Loopback202
D     192.168.203.0/24 
           [90/131072] via 192.168.24.204, 00:06:31, GigabitEthernet3
           [90/131072] via 192.168.12.201, 00:06:31, GigabitEthernet2
D     192.168.204.0/24 
           [90/130816] via 192.168.24.204, 00:37:26, GigabitEthernet3

csr1000v-03#show ip route

Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area 
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route, H - NHRP, l - LISP
       a - application route
       + - replicated route, % - next hop override, p - overrides from PfR

Gateway of last resort is not set

      192.168.2.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.2.0/24 is directly connected, GigabitEthernet1
L        192.168.2.203/32 is directly connected, GigabitEthernet1
D     192.168.12.0/24 [90/3072] via 192.168.13.201, 00:46:12, GigabitEthernet3
      192.168.13.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.13.0/24 is directly connected, GigabitEthernet3
L        192.168.13.203/32 is directly connected, GigabitEthernet3
D     192.168.24.0/24 [90/3072] via 192.168.34.204, 00:46:12, GigabitEthernet2
      192.168.34.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.34.0/24 is directly connected, GigabitEthernet2
L        192.168.34.203/32 is directly connected, GigabitEthernet2
D     192.168.201.0/24 
           [90/130816] via 192.168.13.201, 00:36:56, GigabitEthernet3
D     192.168.202.0/24 
           [90/131072] via 192.168.34.204, 00:05:51, GigabitEthernet2
           [90/131072] via 192.168.13.201, 00:05:51, GigabitEthernet3
      192.168.203.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.203.0/24 is directly connected, Loopback203
L        192.168.203.203/32 is directly connected, Loopback203
D     192.168.204.0/24 
           [90/130816] via 192.168.34.204, 00:37:22, GigabitEthernet2

csr1000v-04#show ip route

Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area 
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route, H - NHRP, l - LISP
       a - application route
       + - replicated route, % - next hop override, p - overrides from PfR

Gateway of last resort is not set

S     10.0.0.0/8 [1/0] via 192.168.142.1
                 [1/0] via 192.168.141.1
      192.168.2.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.2.0/24 is directly connected, GigabitEthernet1
L        192.168.2.204/32 is directly connected, GigabitEthernet1
D     192.168.12.0/24 [90/3072] via 192.168.24.202, 00:46:17, GigabitEthernet3
D     192.168.13.0/24 [90/3072] via 192.168.34.203, 00:46:19, GigabitEthernet2
      192.168.24.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.24.0/24 is directly connected, GigabitEthernet3
L        192.168.24.204/32 is directly connected, GigabitEthernet3
      192.168.34.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.34.0/24 is directly connected, GigabitEthernet2
L        192.168.34.204/32 is directly connected, GigabitEthernet2
      192.168.141.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.141.0/30 is directly connected, Tunnel141
L        192.168.141.2/32 is directly connected, Tunnel141
      192.168.142.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.142.0/30 is directly connected, Tunnel142
L        192.168.142.2/32 is directly connected, Tunnel142
D     192.168.201.0/24 
           [90/131072] via 192.168.34.203, 00:37:02, GigabitEthernet2
           [90/131072] via 192.168.24.202, 00:37:02, GigabitEthernet3
D     192.168.202.0/24 
           [90/130816] via 192.168.24.202, 00:05:57, GigabitEthernet3
D     192.168.203.0/24 
           [90/130816] via 192.168.34.203, 00:06:34, GigabitEthernet2
      192.168.204.0/24 is variably subnetted, 2 subnets, 2 masks
C        192.168.204.0/24 is directly connected, Loopback204
L        192.168.204.204/32 is directly connected, Loopback204

Сохраним эти выводы show ip route в отдельные файлы в суб-директории ./routing_tables/ и запустим скрипт:

$ python2.7 traceRouteByShowIPRoute.py

$ python2.7 traceRouteByShowIPRoute.py
Initializing files...
Opening csr1000v-01.txt
csr1000v-01.txt parsing has been completed in 0.001 sec
Opening csr1000v-02.txt
csr1000v-02.txt parsing has been completed in 0.001 sec
Opening csr1000v-03.txt
csr1000v-03.txt parsing has been completed in 0.001 sec
Opening csr1000v-04.txt
csr1000v-04.txt parsing has been completed in 0.001 sec

All files have been initialized in 0.003 sec

Enter Target Subnet or Host:

Все файлы инициализированы, скрипт, как и ожидалось, запрашивает IP-адрес или подсеть для поиска пути до нее с каждого из маршрутизаторов.
Введем поочередно несколько вариантов и сверим полученный результат с информацией с самих маршрутизаторов.

Поиск пути до Loopback204 192.168.204.204 на csr1000v-04

Пути до этого IP-адреса должны быть со всех имеющихся маршрутизаторов.

Enter Target Subnet or Host: 192.168.204.204

Enter Target Subnet or Host: 192.168.204.204

PATHS TO 192.168.204.204 FROM csr1000v-04
Detailed info:
Path 1:
['csr1000v-04']
ROUTER: csr1000v-04
Matched route string: 
L        192.168.204.204/32 is directly connected, Loopback204

Path search on csr1000v-04 has been completed in 0.000 sec

PATHS TO 192.168.204.204 FROM csr1000v-03
Detailed info:
Path 1:
['csr1000v-03', 'csr1000v-04']
ROUTER: csr1000v-03
Matched route string: 
D     192.168.204.0/24 
           [90/130816] via 192.168.34.204, 00:37:22, GigabitEthernet2

ROUTER: csr1000v-04
Matched route string: 
L        192.168.204.204/32 is directly connected, Loopback204

Path search on csr1000v-03 has been completed in 0.000 sec

PATHS TO 192.168.204.204 FROM csr1000v-02
Detailed info:
Path 1:
['csr1000v-02', 'csr1000v-04']
ROUTER: csr1000v-02
Matched route string: 
D     192.168.204.0/24 
           [90/130816] via 192.168.24.204, 00:37:26, GigabitEthernet3
ROUTER: csr1000v-04
Matched route string: 
L        192.168.204.204/32 is directly connected, Loopback204

Path search on csr1000v-02 has been completed in 0.000 sec

PATHS TO 192.168.204.204 FROM csr1000v-01
Detailed info:
Path 1:
['csr1000v-01', 'csr1000v-03', 'csr1000v-04']
ROUTER: csr1000v-01
Matched route string: 
D     192.168.204.0/24 
           [90/131072] via 192.168.13.203, 00:06:56, GigabitEthernet3
           [90/131072] via 192.168.12.202, 00:06:56, GigabitEthernet2
ROUTER: csr1000v-03
Matched route string: 
D     192.168.204.0/24 
           [90/130816] via 192.168.34.204, 00:37:22, GigabitEthernet2

ROUTER: csr1000v-04
Matched route string: 
L        192.168.204.204/32 is directly connected, Loopback204

Path 2:
['csr1000v-01', 'csr1000v-02', 'csr1000v-04']
ROUTER: csr1000v-01
Matched route string: 
D     192.168.204.0/24 
           [90/131072] via 192.168.13.203, 00:06:56, GigabitEthernet3
           [90/131072] via 192.168.12.202, 00:06:56, GigabitEthernet2
ROUTER: csr1000v-02
Matched route string: 
D     192.168.204.0/24 
           [90/130816] via 192.168.24.204, 00:37:26, GigabitEthernet3
ROUTER: csr1000v-04
Matched route string: 
L        192.168.204.204/32 is directly connected, Loopback204

Path search on csr1000v-01 has been completed in 0.000 sec

Full search has been completed in 0.001 sec

Все пути найдены, маршруты выведены. Сверимся с маршрутизаторами:

csr1000v-01#show ip route 192.168.204.204

csr1000v-01#show ip route 192.168.204.204
Routing entry for 192.168.204.0/24
  Known via "eigrp 200", distance 90, metric 131072, type internal
  Redistributing via eigrp 200
  Last update from 192.168.13.203 on GigabitEthernet3, 00:02:15 ago
  Routing Descriptor Blocks:
    192.168.13.203, from 192.168.13.203, 00:02:15 ago, via GigabitEthernet3
      Route metric is 131072, traffic share count is 1
      Total delay is 5020 microseconds, minimum bandwidth is 1000000 Kbit
      Reliability 255/255, minimum MTU 1500 bytes
      Loading 1/255, Hops 2
  * 192.168.12.202, from 192.168.12.202, 00:02:15 ago, via GigabitEthernet2
      Route metric is 131072, traffic share count is 1
      Total delay is 5020 microseconds, minimum bandwidth is 1000000 Kbit
      Reliability 255/255, minimum MTU 1500 bytes
      Loading 1/255, Hops 2

На csr1000v-01 видны два equal-cost маршрута из EIGRP через csr1000v-02 и csr1000v-03.
Скрипт показал их, как и два пути: ['csr1000v-01', 'csr1000v-03', 'csr1000v-04'] и ['csr1000v-01', 'csr1000v-02', 'csr1000v-04'].

csr1000v-02#show ip route 192.168.204.204

csr1000v-02#show ip route 192.168.204.204
Routing entry for 192.168.204.0/24
  Known via "eigrp 200", distance 90, metric 130816, type internal
  Redistributing via eigrp 200
  Last update from 192.168.24.204 on GigabitEthernet3, 00:08:48 ago
  Routing Descriptor Blocks:
  * 192.168.24.204, from 192.168.24.204, 00:08:48 ago, via GigabitEthernet3
      Route metric is 130816, traffic share count is 1
      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit
      Reliability 255/255, minimum MTU 1500 bytes
      Loading 1/255, Hops 1

csr1000v-03#show ip route 192.168.204.204

csr1000v-3#show ip route 192.168.204.204
Routing entry for 192.168.204.0/24
  Known via "eigrp 200", distance 90, metric 130816, type internal
  Redistributing via eigrp 200
  Last update from 192.168.34.204 on GigabitEthernet2, 00:08:45 ago
  Routing Descriptor Blocks:
  * 192.168.34.204, from 192.168.34.204, 00:08:45 ago, via GigabitEthernet2
      Route metric is 130816, traffic share count is 1
      Total delay is 5010 microseconds, minimum bandwidth is 1000000 Kbit
      Reliability 255/255, minimum MTU 1500 bytes
      Loading 1/255, Hops 1

На csr1000v-2 и csr1000v-3 имеется по одному маршруту из EIGRP через csr1000v-4.
Вывод скрипта с этим согласуется, найдено по одному пути: ['csr1000v-02', 'csr1000v-04'] и ['csr1000v-03', 'csr1000v-04'] соответственно.

csr1000v-04#show ip route 192.168.204.204

csr1000v-04#show ip route 192.168.204.204
Routing entry for 192.168.204.204/32
  Known via "connected", distance 0, metric 0 (connected)
  Routing Descriptor Blocks:
  * directly connected, via Loopback204
      Route metric is 0, traffic share count is 1

На csr1000v-4 это Connnected сеть на интерфейсе Loopback204.
Скрипт показал Local маршрут и путь на самого себя: ['csr1000v-04'].

Поиск пути до подсети 10.10.10.0/24 (отсутствует в топологии)

Enter Target Subnet or Host: 10.10.10.0/24

Enter Target Subnet or Host: 10.10.10.0/24

PATHS TO 10.10.10.0/24 FROM csr1000v-04
Detailed info:
Path 1:
['csr1000v-04', 'csr1000v-01', 'csr1000v-04<<LOOP DETECTED']
ROUTER: csr1000v-04
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.1
                 [1/0] via 192.168.141.1

ROUTER: csr1000v-01
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.2
                 [1/0] via 192.168.141.2

ROUTER: csr1000v-04<<LOOP DETECTED
Matched route string: 
None

Path 2:
['csr1000v-04', 'csr1000v-01', 'csr1000v-04<<LOOP DETECTED']
ROUTER: csr1000v-04
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.1
                 [1/0] via 192.168.141.1

ROUTER: csr1000v-01
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.2
                 [1/0] via 192.168.141.2

ROUTER: csr1000v-04<<LOOP DETECTED
Matched route string: 
None

Path search on csr1000v-04 has been completed in 0.000 sec

PATHS TO 10.10.10.0/24 FROM csr1000v-03
Detailed info:
Path 1:
['csr1000v-03']
ROUTER: csr1000v-03
Matched route string: 
None

Path search on csr1000v-03 has been completed in 0.000 sec

PATHS TO 10.10.10.0/24 FROM csr1000v-02
Detailed info:
Path 1:
['csr1000v-02']
ROUTER: csr1000v-02
Matched route string: 
None

Path search on csr1000v-02 has been completed in 0.000 sec

PATHS TO 10.10.10.0/24 FROM csr1000v-01
Detailed info:
Path 1:
['csr1000v-01', 'csr1000v-04', 'csr1000v-01<<LOOP DETECTED']
ROUTER: csr1000v-01
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.2
                 [1/0] via 192.168.141.2

ROUTER: csr1000v-04
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.1
                 [1/0] via 192.168.141.1

ROUTER: csr1000v-01<<LOOP DETECTED
Matched route string: 
None

Path 2:
['csr1000v-01', 'csr1000v-04', 'csr1000v-01<<LOOP DETECTED']
ROUTER: csr1000v-01
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.2
                 [1/0] via 192.168.141.2

ROUTER: csr1000v-04
Matched route string: 
S     10.0.0.0/8 [1/0] via 192.168.142.1
                 [1/0] via 192.168.141.1

ROUTER: csr1000v-01<<LOOP DETECTED
Matched route string: 
None

Path search on csr1000v-01 has been completed in 0.003 sec

Full search has been completed in 0.004 sec

Результат получен.
Сверимся с маршрутизаторами:

csr1000v-01#show ip route 10.10.10.0 255.255.255.0

csr1000v-01#show ip route 10.10.10.0 255.255.255.0
Routing entry for 10.0.0.0/8
  Known via "static", distance 1, metric 0
  Routing Descriptor Blocks:
  * 192.168.142.2
      Route metric is 0, traffic share count is 1
    192.168.141.2
      Route metric is 0, traffic share count is 1

csr1000v-04#show ip route 10.10.10.0 255.255.255.0

csr1000v-04#show ip route 10.10.10.0 255.255.255.0
Routing entry for 10.0.0.0/8
  Known via "static", distance 1, metric 0
  Routing Descriptor Blocks:
    192.168.142.1
      Route metric is 0, traffic share count is 1
  * 192.168.141.1
      Route metric is 0, traffic share count is 1

На csr1000v-01 и csr1000v-04 имеются по два статических маршрута в GRE-туннели в направлении друг друга на широкую подсеть 10.0.0.0/8. То есть в сети есть петля маршрутизации.
Скрипт ее находит и прекращает поиск пути:

PATHS TO 10.10.10.0/24 FROM csr1000v-01
Path 1:
['csr1000v-01', 'csr1000v-04', 'csr1000v-01<<LOOP DETECTED']
Path 2:
['csr1000v-01', 'csr1000v-04', 'csr1000v-01<<LOOP DETECTED']

PATHS TO 10.10.10.0/24 FROM csr1000v-04
Path 1:
['csr1000v-04', 'csr1000v-01', 'csr1000v-04<<LOOP DETECTED']
Path 2:
['csr1000v-04', 'csr1000v-01', 'csr1000v-04<<LOOP DETECTED']

csr1000v-02#show ip route 10.10.10.0 255.255.255.0

csr1000v-02#show ip route 10.10.10.0 255.255.255.0
% Network not in table

csr1000v-3#show ip route 10.10.10.0 255.255.255.0

csr1000v-3#show ip route 10.10.10.0 255.255.255.0
% Network not in table

На csr1000v-02 и csr1000v-03 маршрутов до этой подсети нет. Аналогичный результат показывает и скрипт.

Основные варианты охвачены, скрипт выдает согласующийся с топологией и настройками маршрутизации на участке сети результат, что подтверждается информацией непосредственно с устройств, откуда загружены таблицы маршрутизации.

Заключение

Получившийся скрипт хоть и далек от идеала, но тем не менее успешно решает поставленную перед ним задачу с достаточной скоростью. На моем MacBook Pro с Intel Core i5 и 8GB RAM на борту инициализация одного файла с таблицей маршрутизации в 700.000+ строк занимает в среднем 6.85с (по результатам 100 запусков). В памяти он после этого занимает около 320-350МБ.
После инициализации файлов поиск любого пути занимает миллисекунды и имеет некоторое пространство для оптимизации (через многопоточную обработку или проверку уже найденных результатов).

Добавление дополнительных парсеров должно быть относительно прозрачно. IPv6 поддерживается модулем SubnetTree нативно.
Для миграции кода на Python3, навскидку, требуется поменять raw_input на input.

Помимо простого вывода путей и маршрутов, логику скрипта можно развить и доработать для произвольных проверок и действий над полученным результатом, в зависимости от потребностей в траблшутинге или анализе сети — от сверки того, "как должно быть" с тем, "как есть", до визуализации маршрутов и т.д.

Полезным дополнением также стал бы анализ Policy Based Routing (PBR) на устройствах в совокупности с таблицами маршрутизации. Впрочем, это уже совершенно другая история.

Надеюсь, кто-то найдет статью полезной для себя.
Спасибо всем, кто дочитал до конца.

Автор: Debug_all

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js