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