DevOps Within

Stories from a man against the machines.

Oh baby, it crawls!

Did you miss me? I have already used up my two weeks of break from the contest, so no more free time for me until June, I'm going to stay here 'till the end :). If you have already forgotten what this blog is about, you can always check here.

Use a library, they said...

Last time when I was writing about i-must-go, I have just managed to find neighbours of one single device on the network. Next step, obviously would be to follow through and find more nodes. And more. And them some more. Now, I might not be a CS graduate, but I know a graph when I see it!

Of course, graphs (and especially those easy ones, like the ones I'll be dealing with) are a well-documented topic and don't require that much of innovative thinking. So my obvious first step was to find a library, which would help me in dealing with graphs so that I don't have to implement everything myself.

It's easier said than done, though... will be fun, they said...

Code revision at the time of writing: 60a319a21.

DISCLAIMER: Following part is from my personal point of view of a golang beginner. Perhaps it all could have been done much easier :). If you're coming here in 2078, don't necessarily assume that I didn't change my mind.

I knew I needed some way of graph traversing and extending it on-the-fly. After some brief searching on the web, someone recommended using a DFS (Depth First Search) for network crawling. If it's on the Internet, it has to be right!

No, but seriously, after reading this SO answer I had no idea which algorithm to choose, and I picked the one with a cooler sounding name. 100% legit. So, off to implementation!

I have found two promising graph-oriented libraries for golang - gyuho/goraph and gonum/graph. First, I've started working with goraph.

It looked like a straightforward thing to use. There is already a graph structure implemented and ready to use, and different traversal options are available, such as DFS, recursive DFS implementation, BFS, topological sort... I wanted to use DFS provided by the library, so I have started implementing needed interfaces in my own structures and hit a wall at one point - I realised that the expected struct for the graph is quite restricting for me. It looks like this:

type graph struct {
    mu sync.RWMutex // guards the following

    // idToNodes stores all nodes.
    idToNodes map[ID]Node

    // nodeToSources maps a Node identifer to sources(parents) with edge weights.
    nodeToSources map[ID]map[ID]float64

    // nodeToTargets maps a Node identifer to targets(children) with edge weights.
    nodeToTargets map[ID]map[ID]float64

I didn't really like these maps of maps with weights, especially because I didn't need weights. I wanted a more 'traditional' approach to storing information about the graph: one data structure for nodes and the second structure for edges. It can't get easier than that so I thought that it might work for me.

After deciding that goraph is a no-go, I wanted to try using the second library, but I couldn't handle extending the available types with functions required for editing the graph during crawling. At that point, after wasting some more hours trying to make it all work, I gave up on this and decided to...

Be a man!

Feel free to take your time and listen to this great, motivational song, but then please come back and read on!

With all the force of a great typhoon, I settled on implementing a very simple version of the graph suited for me and my use case. Thus the arch mastery of code became like this:

type NetworkGraph struct {
    nodes map[IPAddr]NetworkDevice
    edges []Port

This impressive piece of code allowed me to create everything I needed for network crawling. Yay, I guess? Here come the complementary definitions of NetworkDevice and Port:

type IPAddr string

// type Port

type Port struct {
    RemoteAddress IPAddr
    RemotePort    int
    LocalAddress  IPAddr
    LocalPort     int

// interface NetworkDevice

type NetworkDevice interface {
    GetIP() IPAddr
    GetNeighbors() map[int]IPAddr

I have separated the methods used in graph logic and network logic. One can assume that any crawlable device should be able to find its neighbours, so this method is contained in the NetworkDevice interface and implementation using SNMP+LLDP is hidden from this view. Also, to simplify things, I have decided to not use pointers to switches in Port anymore and instead work on IPAddr, since I'm having everything mapped anyway. I still keep my Port structures, because they already contain some data which will be needed later (local port number, later to be monitored for throughput).

It's business time!

So, does it work? Yeah, it does! If I run it starting from one node on the network:

$ ./i-must-go | grep -v Trying
Found 56 nodes!
  [  ->  ->  -> -> -> -> ->

You can see that DFS algorithm is working - the crawler goes as deep as possible first, then checks for the neighbours. If I start from another node it looks similar:

$ ./i-must-go | grep -v Trying
Found 56 nodes!
  [  ->  ->  ->  ->  ->  ->  ->

(Note: I didn't care about proper CLI yet, had to recompile the code)

Funny thing is that I have accidentally found an error in the network configuration of the environment, which is now partially fixed, but the total number of devices should about two times bigger. At this moment two distribution switches cannot see each other both ways using LLDP. But 'tis but a scratch, nothing that a quick reboot of half a network can't fix. ;-)

Next stop: visualising the structure of a network!