Trace route based on Cisco routing table text output

Question

I created a script for path search across network topology based on uploaded routing tables in text format. The final purpose is to be able to get all available paths to given subnet/host from each uploaded device with corresponding routing info.

Routing tables are stored in subdirectory (./routing_tables by default) in separate .txt files. Each file represents a single router/VRF.

Files are parsed and initialized into Python data structures before search. Subnet tree is built based on each routing table (using SubnetTree module) for quick longest prefix match lookups.

After text files initialization script asks for destination subnet/host to search network path to. I implemented recursive path search algorithm with dynamic nexthop lookup for that.

Output is a printed list of router IDs generated from file names from each uploaded topology member. It also includes raw route strings. I'm thinking of wrapping this into another function and returning result for possible further processing (e.g. visualizing) and/or script import/reuse.

The code is operable. Single 700k+ lines file (sample BGP full-view) initialization takes around 6.2-7.5sec on my mid-level MacBook Pro (i5/8GB RAM). After initialization, any path lookup takes just milliseconds.

What can be improved in terms of code performance, data handling, structure, style etc?

Being a network engineer, I'm still learning to code. I'm looking forward to receive some feedback from an experienced programmers. I'm willing to improve my code and my skills.

Code itself:

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 + "(\/\d\d?)?$")

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

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

# Route string VIA portion matching.
REGEXP_VIA_PORTION = re.compile('.*via\s+(\d\d?\d?\.\d\d?\d?\.\d\d?\d?\.\d\d?\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': {'routingTable': {}, 'interfaceList': ()},
#     'RID_N': {'routingTable': {}, 'interfaceList': ()},
# }
# 
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()


# Parser for routing table text output.
# Builds internal SubnetTree search tree in 'routeTree' object.
# routeTree key is Network Prefix, value is list of nexthops.
#
# Returns 'router' dictionary object.
# Format:
# 
# router = {
#   'routingTable': routeTree
# }
#
# Compatible with both Cisco IOS(IOS-XE) 'show ip route' and Cisco ASA 'show route' output format.
def parseShowIPRoute(showIPRouteOutput):

    router = {}
    routeTree = SubnetTree.SubnetTree()
    interfaceList = []

    # Parse Local and Connected route strings in text.
    connectedAndLocalRoutesFound = False
    for rawRouteString in REGEXP_ROUTE_LOCAL_CONNECTED.finditer(showIPRouteOutput):
        subnet = rawRouteString.group('ipaddress') + formatNetmaskToPrefixLength(rawRouteString.group('maskOrPrefixLength'))
        interface = rawRouteString.group('interface')
        routeTree[subnet] = ((interface,), rawRouteString.group(0))
        if rawRouteString.group('routeType') == 'L':
            interfaceList.append((interface, subnet,))
        connectedAndLocalRoutesFound = True

    if not connectedAndLocalRoutesFound:
        print('Failed to find routing table entries in given output')
        return None

    # parse static and dynamic route strings in text
    for rawRouteString in REGEXP_ROUTE.finditer(showIPRouteOutput):
        subnet = rawRouteString.group('subnet') + formatNetmaskToPrefixLength(rawRouteString.group('maskOrPrefixLength'))
        viaPortion =  rawRouteString.group('viaPortion')
        nextHops= []
        if viaPortion.count('via') > 1:
            for line in viaPortion.split('\n'):
                if line:
                    nextHops.append(REGEXP_VIA_PORTION.match(line).group(1))
        else:
            nextHops.append(REGEXP_VIA_PORTION.match(viaPortion).group(1))
        routeTree[subnet] = (nextHops, rawRouteString.group(0))

    router = {
        'routingTable': routeTree,
        'interfaceList': interfaceList,
    }

    return router

# Gets subnet mask or slashed prefix length
# Returns slashed prefix length format for subnet mask case.
# Returns slashed prefix length as is for slashed prefix length case.
# Returns "" for empty input.
def formatNetmaskToPrefixLength(rawMaskOrPrefixLength):
    if not rawMaskOrPrefixLength:
        return ""
    if re.match("^\/\d\d?$", rawMaskOrPrefixLength):
        return rawMaskOrPrefixLength
    if re.match("^\d\d?\d?\.\d\d?\d?\.\d\d?\d?\.\d\d?\d?$", rawMaskOrPrefixLength):
        return "/" + str(sum([bin(int(x)).count("1") for x in rawMaskOrPrefixLength.split(".")]))
    return ""

# Performs routeTree lookup in passed router object for passed destination subnet.
# Returns list of nexthops.
def routeLookup(destination, router):
    #print router
    if destination in router['routingTable']:
        nextHop = router['routingTable'][destination]
        return nextHop
    else:
        return (None, None)

# Returns RouterID by Interface IP address which it belongs to.
def getRIDByInterface(interface):
    if interface in GLOBAL_INTERFACE_TREE:
        rid = GLOBAL_INTERFACE_TREE[interface][0]
        return rid
    else:
        return None

# Check if nexthop points to local interface.
# Valid for Connected and Local route strings.
def nextHopIsLocal(nextHop):
    interfaceTypes = ['Eth', 'Fast', 'Gig', 'Ten', 'Port',
                      'Serial', 'Vlan', 'Tunn', 'Loop', 'Null'
    ]
    for type in interfaceTypes:
        if nextHop.startswith(type):
            return True
    return False


# Performs recursive path search from source Router ID (RID) to target subnet.
# Returns tupple of path tupples.
# Each path tupple contains a sequence of Router IDs.
# Multiple paths are supported.
def traceRoute(sourceRouterID, target, path=[]):
    if not sourceRouterID:
        return [path + [(None, None)]]
    currentRouter = ROUTERS[sourceRouterID]
    nextHop, rawRouteString = routeLookup(target, currentRouter)
    path = path + [(sourceRouterID, rawRouteString)]
    #print nextHop
    paths = []
    if nextHop:
        if nextHopIsLocal(nextHop[0]):
            return [path]

        for nh in nextHop:
            nextHopRID = getRIDByInterface(nh)
            if not nextHopRID in path:
                innerPath = traceRoute(nextHopRID, target, path)
                for p in innerPath:
                    paths.append(p)
    else:
        return [path]
    return paths


# Begin execution.

if not os.path.exists(RT_DIRECTORY):
    exit("%s directory does not exist. Check RT_DIRECTORY variable value." % RT_DIRECTORY)

print("Initializing files...")
starttime = time()

# Go through RT_DIRECTORY and parse all .txt files.
# Generate router objects based on parse result if any.
# Populate ROUTERS with those router objects.
# Default key for each router object is FILENAME.
#
for FILENAME in os.listdir(RT_DIRECTORY):
    if FILENAME.endswith('.txt'):
        fileinitstarttime = time()
        with open(os.path.join(RT_DIRECTORY, FILENAME), 'r') as f:
            print 'Opening ', FILENAME
            rawTable = f.read()
            newRouter = parseShowIPRoute(rawTable)
            routerID = FILENAME.replace('.txt', '')
            if newRouter:
                ROUTERS[routerID] = newRouter
                if newRouter['interfaceList']:
                    for iface, addr in newRouter['interfaceList']:
                        GLOBAL_INTERFACE_TREE[addr]= (routerID, iface,)
            else:
                print ('Failed to parse ' + FILENAME)
        print FILENAME + " parsing has been completed in %s sec" % ("{:.3f}".format(time() - fileinitstarttime),)
else:
    if not ROUTERS:
        exit ("Could not find any valid .txt files with routing tables in %s directory" % RT_DIRECTORY)
    print "\nAll files have been initialized in %s sec" % ("{:.3f}".format(time() - starttime),)


# Now ready to perform search based on initialized files.
# Ask for Target and perform path search from each router.
# Print all available paths.
#
while True:

    print '\n'
    targetSubnet = raw_input('Enter Target Subnet or Host: ')

    if not targetSubnet:
        continue
    if not REGEXP_INPUT_IPv4.match(targetSubnet.replace(' ', '')):
        print "incorrect input"
        continue

    lookupstarttime = time()
    for rtr in ROUTERS.keys():

        subsearchstarttime = time()
        result = traceRoute(rtr, targetSubnet)

        if result:
            print "\n"
            print "PATHS TO %s FROM %s" % (targetSubnet, rtr)
            n = 1
            print 'Detailed info:'
            for r in result:
                print "Path %s:" % n
                print [h[0] for h in r]
                for hop in r:
                    print "ROUTER:", hop[0]
                    print "Matched route string: \n", hop[1]
                else:
                    print '\n'
                n+=1
            else:
                print "Path search on %s has been completed in %s sec" % (rtr, "{:.3f}".format(time() - subsearchstarttime))
    else:
        print "\nFull search has been completed in %s sec" % ("{:.3f}".format(time() - lookupstarttime),)

Sample result for one of test routers:

Enter Target Subnet or Host: 10.5.5.5

    PATHS TO 10.5.5.5 FROM r2 
    Detailed info: 
    Path 1: 
    ['r2', 'r3', 'r5'] 
    ROUTER: r2 
    Matched route string: 
    S       10.5.5.5 [1/0] via 10.14.88.3 
                     [1/0] via 10.14.88.4 

    ROUTER: r3 
    Matched route string: 
    S       10.5.5.5 [1/0] via 10.35.35.2 
    ROUTER: r5 
    Matched route string: 
    C       10.5.5.5 is directly connected, Loopback1 


    Path 2: 
    ['r2', 'r4', 'r5'] 
    ROUTER: r2 
    Matched route string: 
    S       10.5.5.5 [1/0] via 10.14.88.3 
                     [1/0] via 10.14.88.4 

    ROUTER: r4 
    Matched route string: 
    S       10.5.5.5 [1/0] via 10.45.45.2 
    ROUTER: r5 
    Matched route string: 
    C       10.5.5.5 is directly connected, Loopback1 


    Path search on r2 has been completed in 0.000 sec

Below is a sample IOS routing table output with almost every possible route format. Script also supports Cisco ASA output format (the major difference is ASA uses subnet masks instead of prefix lengths (255.255.255.0 for /24 and so on)).

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

Answer 1

In addition to Coal_'s points, your entry point of the code should be a

if __name__ == "__main__":
    main()

with the code placed into a def main(): - the reason is you can avoid statements like:

if not os.path.exists(RT_DIRECTORY):
    exit("%s directory does not exist. Check RT_DIRECTORY variable value." % RT_DIRECTORY)

and turn those into return statements instead of exit statements (code untested):

def main():
    rt_directory = Path(__file__).parent / "routing_tables"
    if not rt_directory.exists():
        logging.warning("rt directory does not exist. Check RT_DIRECTORY variable value.")
        return

    logging.debug("Initializing files...")
    start_time = time()

    for filename in rt_directory.glob("*.txt"):
        file_init_start_time = time()
        logging.debug(f"Working with {filename}")
        raw_table = filename.read_text()
        new_router = parse_show_ip_route(raw_table)
        router_id = filename.stem 

and of course the code changes to use pathlib instead of using os for file and directory checks, and the logging functionality to handle displaying messages/logging to a file instead of using print.

Finally, you should also refactor out all the chunks of code under the for loops and if statements into separate functions. It will make your code easier to understand and you don't need all those comments, which will eventually begin to lie as your code is modified as time passes.

Hope this helps!

Answer 2

This isn't a comprehensive review, but just some thoughts.

• Try to adhere to the Python style guide (PEP-8):

  • Keep blank lines to a minimum. You can use blank lines to group logical sections together, but don't use them excessively. For example, you may want to get rid of the blank line at the top of parseShowIPRoute(), and the many blank lines at module level.

  • Pick a line length limit and stick to it. PEP-8 suggests 79 characters (and 73 for flowing text). Many developers (myself included) choose a soft limit of 79 or 80 and a hard limit of 100 characters.

  • Function and variable names should adhere to the snake_case naming convention. You already got the UPPERCASE_WITH_UNDERSCORES right for constants. :)

  • Don't use the naming conventions for constants for loop variables.

• In nextHopIsLocal(), shouldn't interfaceTypes be a constant?

• In a function, you can drop the else if the if-body returns. You could also drop the explicit return None altogether. In getRIDByInterface():

  if interface in GLOBAL_INTERFACE_TREE:
      rid = GLOBAL_INTERFACE_TREE[interface][0]
      return rid
  else:
      return None
  

  ... becomes:

  if interface in GLOBAL_INTERFACE_TREE:
      rid = GLOBAL_INTERFACE_TREE[interface][0]
      return rid
  

• Don't assign to a variable, only to return that variable unmodified on the next line. To take the previous example:

  rid = GLOBAL_INTERFACE_TREE[interface][0]
  return rid
  

  ... that's a wasteful instruction. Just return immediately:

  return GLOBAL_INTERFACE_TREE[interface][0]
  

• If you choose to report errors by using print(), make sure to pipe the error messages to stderr. The standard library provides sys.stderr:

  import sys
  print >>sys.stderr, "My error message"
  

• Why did you drop the parentheses around the print at the end? Either style is acceptable, but consistency is important.

• Consider using str.splitlines() instead of str.split(), to avoid an extra level of indentation.

• If you can, switch to Python 3. Support for Python 2 will soon drop. The most obvious changes are print being a function, and raw_input() having been renamed to input().

• The comments above the functions should be converted into docstrings. Docstrings are simply multiline string literals. They can be parsed, and are actually associated with an object, which allows for easier debugging. Here's an example of a docstring:

  def sub(a, b):
      """Return a - b. a and b must be numbers."""
      return a - b
  

• %-formatting is outdated and prone to breaking. Modern Python code should use str.format() or f-strings instead:

  print("Error message: %s" % err) # Bad
  print("Error message: {}".format(err)) # Good
  print(f"Error message: {err}") # Good, Python 3.6 and upwards
  

• os.path.exists() may not be specific enough. Wanna make sure the path points to a directory? Use os.path.isdir().