Network Routing in Neo4j

People use Neo4j to manage enterprise architectures all the time. If you haven’t seen this presentation from Thomas Lawrence from Amadeus, then you owe it to yourself to watch it. But what about lower level networks? Can we use Neo4j to model routing in a physical network? Of course we can, and today I’ll show you how.

We will keep things simple and just have Routers, Switches, Interfaces and Servers. Routers will have “ROUTE_TO” relationships with each other. The relationship will contain the routing table as a String Array. For example: [“10.175.112.0/20”, “10.175.108.0/22”, “10.175.112.0/20”, “10.182.14.64/26″…]. Routers will also have “TRANSLATES_TO” relationships to Interfaces (for example a VLAN) with an ip and mac address properties. The Interfaces will have “CONNECTS_TO” relationships to Switches with a mac and port properties. Finally the Switches will also have “CONNECTS_TO” relationships to Servers with mac and port properties. The Servers like the Routers will have ip address properties. Maybe this picture will help make sense of this:

For this exercise, let’s start with a Router with an ip of “10.175.64.2” and see how we can get to a Server with an ip of “10.175.122.10”. Here is a picture of part of our network:

We will create a Stored Procedure that starts of by finding our router and server. Then we will create a TraversalDescription using the Traversal API that will explore the graph depth first, expanding using a NetworkExpander which we will talk about next, and evaluating the paths it traverses until it find the server node. Assuming we find some paths, we will return them as our result:

 
    @Procedure(name = "com.maxdemarzi.router", mode = Mode.READ)
    @Description("CALL com.maxdemarzi.router(from, to) - traverse paths")
    public Stream<PathResult> router(@Name("from") String from, @Name("to") String to) {
        Node router = db.findNode(Labels.Router, "ip", from);
        Node server = db.findNode(Labels.Server, "ip", to);
        if (router != null && server != null) {
            TraversalDescription td = db.traversalDescription()
                    .depthFirst()
                    .expand(new NetworkExpander(to))
                    .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_PRUNE,
                            Evaluation.EXCLUDE_AND_CONTINUE, server));

            return td.traverse(router).iterator().stream().map(PathResult::new);
        }
        return Stream.of(new PathResult(null));
    }

The tricky part is that NetworkExpander, so let’s take a look at it. Its constructor requires that we pass in the IP address we are trying to reach, and we will save it as a String and an IPAddress.

 
public class NetworkExpander implements PathExpander<String> {
    private String ip;
    private IPAddress ipAddress;

    public NetworkExpander(String ip) {
        this.ip = ip;
        this.ipAddress = new IPAddressString(ip).getAddress();
    }

In our expander we will first try the Layer 3 routes by looking at the ROUTES_TO relationships and seeing if any of the entries in the String Array routes property contains the ip address we are looking for and choose the one with the longer prefix. For example, if we encounter 3 ROUTES_TO relationships each having one routing table entry:

 
192.168.32.0/26 ROUTES_TO 10.1.1.1
192.168.32.0/24 ROUTES_TO 10.1.1.2
192.168.32.0/19 ROUTES_TO 10.1.1.3

…and we want to get to “192.168.32.1”, we would add all 3 relationships in to our unorderedRoutes, but upon ordering we would try the relationship going to “10.1.1.1” first because “192.168.32.1” is contained within the 192.168.32.0/26 network (192.168.32.0 to 192.168.32.63) and has the longer prefix (26).

If we wanted to get to “192.168.32.100” we would skip the first relationship “192.168.32.0/26” since x.100 isn’t included in its range of 0-63. The other two relationships would be valid since “192.168.32.0/24” includes 192.168.32.0 through 192.168.32.255 and “192.168.32.0/19” includes 192.168.32.1 through 192.168.63.254 but we would try “10.1.1.2” first since it has the longer prefix (24). Let me show you the code:

 
    @Override
    public Iterable<Relationship> expand(Path path, BranchState branchState) {
        Node last = path.endNode();

        ArrayList<Relationship> relationships = new ArrayList<>();
        ArrayList<Pair<Integer, Relationship>> unorderedRoutes = new ArrayList<>();

        // Layer 3 Longest prefix matching
        for(Relationship routes_to : last.getRelationships(RelationshipTypes.ROUTES_TO, Direction.OUTGOING)) {
            String[] routes = (String[])routes_to.getProperty("routes", new String[]{});
            for(String route : routes) {
                IPAddressString addrString = new IPAddressString(route);
                if(addrString.getAddress().contains(ipAddress)) {
                    unorderedRoutes.add(Pair.of(addrString.getNetworkPrefixLength(), routes_to));
                }
            }
        }
        unorderedRoutes.sort(Comparator.comparingInt(p -> - p.first()));
        unorderedRoutes.forEach( p -> relationships.add(p.other()));

Now you may be asking yourself, where did IPAddressString and IPAddress come from? They come from the IPAddress library from Sean C. Foley. If you wanted to roll your own, this StackOverflow post may be a good place to start.

Once we hopefully get to the Router that should lead us to our server, we go to Layer 2. Here we traverse the TRANSLATES_TO relationship leading to our ip address, translate to a mac address and continue our traversal. We follow the CONNECTS_TO relationships that have the same mac address until we reach our destination. Once again here is the code:

 
        // If there is no Layer 3 next hop, go to Layer 2
        if (relationships.isEmpty()) {
            // Layer 2
            for (Relationship translates_to : last.getRelationships(RelationshipTypes.TRANSLATES_TO, Direction.OUTGOING)) {
                String ip = (String) translates_to.getProperty("ip");
                if (ip.equals(this.ip)) {
                    relationships.add(translates_to);
                }
            }
            String mac = "";
            Relationship lastRel = path.lastRelationship();
            if (lastRel != null) {
                mac = (String) lastRel.getProperty("mac", "");
            }

            for (Relationship connects_to : last.getRelationships(RelationshipTypes.CONNECTS_TO, Direction.OUTGOING)) {
                String mac_too = (String) connects_to.getProperty("mac", "");
                if (mac.equals(mac_too)) {
                    relationships.add(connects_to);
                }
            }
        }
        return relationships;

The README file in the project repository contains a cypher script to build a small network. After we build our network we can try our stored procedure, for example:

 
CALL com.maxdemarzi.router('10.175.64.2', '10.175.122.10')

…and this would be our result.

If you are seeing more relationships than this, make sure you go to the Neo4j Browser “Settings” (click the gear on the side panel), scroll all the way down, unclick “Connect result nodes” and rerun the stored procedure.

As always the code is on github, so feel free to try it out. The routing table in this model is a simple list of strings, but in a more real world scenario each entry would probably be its own relationship between Routers with priorities, weights, and other meta properties that would affect the routing order but the concepts are the same.

Tagged , , , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: