Below is the file 'tracepath.py' from this revision. You can also download the file.

#!/usr/bin/python

from pyPgSQL import libpq
import sys

def build_tuple_dictionary(res):
        rv = []
        for tuple_index in range(res.ntuples):
                rvn = {}
                for field_index in range(res.nfields):
                        rvn[res.fname(field_index)] = res.getvalue(tuple_index, field_index)
                rv.append(rvn)
        return rv

def get_l3path(from_ip, to_ip):
	def q(s):
		if s == None: return "NULL"
		else: return libpq.PgQuoteString(s)
	def hostname_from_ip(ip):
		res = cnx.query("SELECT hostname FROM adjacency WHERE ip_address=%s" % (q(ip)))
		res = build_tuple_dictionary(res)
		if len(res) == 0: return
		return res[0]['hostname']
	def get_best_route(hostname, ip_address):
		query = "SELECT * FROM routing WHERE hostname=%s AND network >> %s ORDER BY masklen(network) DESC LIMIT 1" % (q(hostname), q(ip_address))
		res = cnx.query(query)
		bestroute = build_tuple_dictionary(res)
		if len(bestroute) == 0: return None
		else: return bestroute[0]
	def get_router(ip_address):
		query = "SELECT hostname FROM addresses WHERE host(ip_address)=%s LIMIT 1" % (q(ip_address))
		res = cnx.query(query)
		routers = build_tuple_dictionary(res)
		if len(routers): return routers[0]['hostname']
		else: return None
	def get_path(from_hostname, to_ip):
		# returns a tuple
		# ([ .. list of network devices .. ], ip address via)
		# if the path actually terminates on one of our devices, the second entry in the tuple will be None
		path = [from_hostname]
		while True:
			current_router = path[-1]
			bestroute = get_best_route(current_router, to_ip)
			if not bestroute: return None, None # not in routing table, then it's unreachable. No path.
			# determine the best route available on our current_router
			if bestroute.has_key('via'):
				# ok, so do we know of anything with this IP address in our adjacency table?
				next_router = get_router(bestroute['via'])
				# check for failure to find it, or a loop
				if not next_router:
					# we don't know about this router, so we'll return that information
					return path, bestroute['via']
				if next_router == current_router: break
				# all good, go to this host
				path.append(next_router)
			else: break # no 'via', must be connected
		return path, None
	cnx = libpq.PQconnectdb("dbname=netinfo")
	####
	#
	# ALGORITHM:
	# choose a starting point
	# go to that starting point, and determine the best route to our destination
	#
	# if that route is connected (eg. local) then we are done. Otherwise, we should
	# check the adjacency table to find out if the next hop is one of the routers this
	# system knows about. If no match, then we stop - we have found the router closest
	# to this IP address (in terms of our network). If there is a match, go to that
	# router and repeat the above steps.
	#
	# Once we have determined the closest router to our destination address, we can
	# backtrack - determine which route that router would use to get to our from
	# address. Recurse using the algorithm above until we find the closest router to
	# our from address.
	#
	# This should give us the layer 3 path.
	#
	####
	starting_point = 'villa.net.uwa.edu.au'
	# firstly, figure out the path from our arbitrary starting point to 'to_ip'
	# this tells us the last router in our network that services 'to_ip'
	init_path, init_via = get_path(starting_point, to_ip)
	if not init_path: return None, None, None
	endpoint_router = init_path[-1]
	# then, take the path from that router to 'from_ip'
	l3path, final_via = get_path(endpoint_router, from_ip)
	if not l3path: return None, None, None
	l3path.reverse()
	# l3path is now a list, showing the hops taken to get from
	# from_ip to to_ip that were within our network
	if init_via: # the hop to get to to_ip
		l3path.append(init_via)
	if final_via: # the hop to get to from_ip
		l3path = [final_via] + l3path
	return final_via == None, l3path, init_via == None

if __name__ == '__main__':
	if len(sys.argv) <> 3:
		print "usage: tracepath <from_ip> <to_ip>"
	from_ip, to_ip = sys.argv[1:]
	from_connected, connected_path, to_connected = get_l3path(from_ip, to_ip)

	l3path = connected_path
	if not from_connected: l3path = [from_ip, "..."] + l3path
	else: l3path = [from_ip] + l3path
	if not to_connected: l3path += ["...", to_ip]
	else: l3path += [to_ip]
	print ' -> '.join(l3path)
	# determine the layer two path between the layer three hops
	for i in range(len(connected_path) - 1):
		print connected_path[i], connected_path[i+1]