The OpenLANscape Project
The LANout Algorithm
Author: Maciek Kolbusz
License: GPL
Copyright: Maciek Kolbusz (c) 2007-2008
Overview
LANout is the algorithm which creates a 3-dimentional network topology layout. The name comes from the combination of LAN and layout.
It's designed for SNMP enabled LANs, as MIBs are good sources of informations needed to recreate physical topology of LAN.
The matter of network discovery and scanning won't be covered by this article. There's another project called
WiR3D which uses this algorithm together with PING/SNMP scanner to provide a complete toolkit for LAN topology mapping.
The snippets of code to picture the idea are written in C++ using STL objects (maps and lists). Input data are pulled
from SQLite3 database file which is accessed via libsqlitewrapped API. Drawing is made with OpenGL by FreeGLUT.
Input Objects
Subnet - a logical subnet identified by integer ID.
Node - a device with one or more NIC accessible for PING; identified by ID and type - both integers.
Interface - NIC; identified by ID, has two owners: a parent node and a parent subnet.
FDB - Forwarding Database; a table of switch ports and MAC addresses of devices connected to them.
Output Objects
Wirea - wired/wireless network area; a set of subnets with belonging nodes and relations between them.
Nodes - an indexed list of all nodes in the wirea;
Subnets - an indexed list of subnets with belonging nodes.
Stacks - an indexed list of switches and hubs per subnet.
Bridges - a list of hubs and switches indexed by switch/hub ID with ID of a parent stack.
Neighbours - a list of routers with pointers to neighbouring nodes.
class WiREA
{
public:
WiREA();
~WiREA();
void openDB( char* );
void draw();
private:
int Root; // root node id
std::map< int, int > Nodes; // id, type
std::map< int, std::list > Subnets; // subnet id, node list
std::map< int, std::list > Neighbours; // router/root id, neighbours list
std::map< int, std::list > FDBs; // switch id, node list
std::map< int, std::list > Stacks; // stack id, list of switches/hubs
std::map< int, int > Bridges; // switch/hub id, stack id
std::map< int, int > Drawn; // node id, 0/1 (not drawn/drawn)
void drawNode( int );
void drawNeighbours( int );
};
The process
Add all nodes to Nodes, so each node is represented by a pair of intergers (id, type).
void WiREA::openDB( char *name )
{
Database db( name );
if ( db.Connected() ) {
Query q( db );
q.get_result( "SELECT idNode, nodeType FROM Nodes" );
while ( q.fetch_row() ) {
int id = q.getval();
int type = q.getval();
Nodes[ id ] = type;
if ( type == 0 ) Root = id;
}
q.free_result();
Add all subnets to Subnets. Each element of Subnets is a pair of subnet ID and a list of child nodes. Note that every node with more than one network interface is considered as a router and is present in as many subnets as many interfaces it has.
q.get_result( "SELECT idSubnet FROM Subnets" );
while( q.fetch_row() ) {
int netID = q.getval();
std::list< int > temp;
std::stringstream stmt;
stmt << "SELECT idNode FROM Nodes " <<
"JOIN Interfaces ON Nodes.idNode = Interfaces.belongsToNode " <<
"WHERE Interfaces.belongsToSubnet = " << netID;
Query q2( db );
q2.get_result( stmt.str() );
while( q2.fetch_row() ) {
temp.push_back( q2.getval() );
}
q2.free_result();
Subnets[ netID ] = temp;
}
q.free_result();
Add all FDB entries to FDBs. Each element of FDBs is a pair of switch ID and a list of connected nodes. Node IDs are found by MAC addresses of their interfaces. Node is directly connected to a switch, if the assigned port number appears in FDB only once, so after FDB is purged from entries with non-unique port numbers directly connected nodes (or more precisely: MAC addresses of their interfaces) are left.
for ( std::map< int, int >::iterator i = Nodes.begin();
i != Nodes.end();
i++ )
{
if( i->second == 1 ) { // node is a switch
std::multimap< int, int > port_map;
std::multimap< int, int >::iterator j = port_map.begin();
std::stringstream stmt;
stmt << "SELECT Nodes.idNode, FDBs.portNum FROM FDBs " <<
"JOIN Interfaces ON FDBs.MACaddress = Interfaces.MACaddress " <<
"JOIN Nodes ON Interfaces.belongsToNode = Nodes.idNode " <<
"WHERE FDBs.belongsTo = " << i->first <<
" ORDER BY FDBs.portNum";
q.get_result( stmt.str() );
while( q.fetch_row() ) {
port_map.insert(
port_map.end(),
std::pair< int, int >(q.getval(), q.getval())
);
}
j = port_map.begin();
while( j != port_map.end() ) {
if( port_map.count(j->first) > 1 ) port_map.erase(j->first);
else j++;
}
// save the results
std::list< int > node_list;
for( j = port_map.begin(); j != port_map.end(); j++ ) {
node_list.push_back( j->second );
}
FDBs[ i->first ] = node_list;
q.free_result();
port_map.clear();
node_list.clear();
}
}
Create virtual hubs if:
1. There are more than 2 nodes in a subnet, but no switch is found. In such case one virtual hub is created for the subnet and all subnet's nodes are added to its FDBs.
2. There are switches in a subnet, but some nodes are not assigned to FDBs. After all switches together with their FDBs member nodes are removed from a subnet and there are still some nodes left, the left-overs are added to the FDBs of newly created virtual hub.
int hc = 0; // hub counter for ( std::map< int, std::list>::iterator i = Subnets.begin(); i != Subnets.end(); // i iterates Subnets i++ ) { if ( Subnets[ i->first ].size() > 2 ) { std::list< int > hub_children; // temp hub hub_children = Subnets[ i->first ]; for ( std::list< int >::iterator j = i->second.begin(); // j iterates node list j != i->second.end(); j++ ) { if ( Nodes[ *j ] == 1 ) { // a switch found // remove the switch from hub_children hub_children.remove( *j ); // process FDB of the switch and remove its children from hub_children for ( std::list< int >::iterator k = FDBs[ *j ].begin(); k != FDBs[ *j ].end(); k++ ) { hub_children.remove( *k ); } } } // if there are nodes left on hub_children, add the hub to the subnet: if ( !hub_children.empty() ) { hc++; Nodes[ -1 * hc ] = 4; Subnets[ i->first ].insert( Subnets[ i->first ].end(), -1 * hc ); FDBs[ -1 * hc ] = hub_children; } } }
Assign neighbours to routers:
1. If there's just one node in a subnet, there's no neighbours.
2. If there are two nodes in a subnet, assign one to the neighbours list of another and vice versa (if the one to assign to is a router).
3. If there are more than two nodes in a subnet, look up routers in FDBs of switches and hubs from the subnet and assing the proper switch/hub to router's neighbours.
for ( std::map< int, std::list>::iterator i = Subnets.begin(); i != Subnets.end(); i++ ) { switch( i->second.size() ) { case 1: { break; } case 2: { std::list< int >::iterator j = i->second.begin(); std::list< int >::iterator k = i->second.end(); if ( Nodes[ *j ] == 2 ) Neighbours[ *j ].push_back( *k ); if ( Nodes[ *k ] == 2 ) Neighbours[ *k ].push_back( *j ); break; } default: { // find switches and hubs in the subnet, then search FDBs for routers and // assign parent switches/hubs to routers' neighbour lists // finally add switch/hub to the stack for ( std::list< int >::iterator j = i->second.begin(); j != i->second.end(); j++ ) { if ( Nodes[ *j ] == 1 or Nodes[ *j ] == 4 ) { for ( std::list< int >::iterator k = FDBs[ *j ].begin(); k != FDBs[ *j ].end(); k++ ) { if ( Nodes[ *k ] == 2 or Nodes[ *k ] == 0 ) Neighbours[ *k ].push_back( *j ); } Stacks[ i->first ].push_back( *j ); Bridges[ *j ] = i->first; } } break; } } } } else { std::cout << " Database not connected. " << std::endl; exit(-1); }
Having all of the above ready, the layout can be drawn:
1. Draw the root node.
2. Draw its neighbours recursively. Stacked switches and hubs are drawn above each other. For each switch and hub its FDBs and parent Stacks has to be processed and drawn.
void WiREA::draw()
{
// Create Drawn map
for ( std::map< int, int >::iterator i = Nodes.begin();
i != Nodes.end();
i++ )
{
Drawn[ i->first ] = 0;
}
drawNode( 0 );
drawNeighbours( Root );
}
void WiREA::drawNeighbours( int node )
{
Drawn[ node ] = 1;
if ( Nodes[ node ] == 0 or Nodes[ node ] == 2 ) {
int j = 0;
for ( std::list< int >::iterator i = Neighbours[ node ].begin();
i != Neighbours[ node ].end();
i++ )
{
if ( Drawn[ *i ] == 0 ) {
glPushMatrix();
glRotatef( j * 20.0, 0.0, 1.0, 0.0 );
glColor3f( 0.0, 1.0, 0.0 );
glBegin( GL_LINES );
glVertex3f ( 0.0, 0.0, 0.0 );
glVertex3f ( 2.0, 0.0, 0.0 );
glEnd();
glTranslatef( 2.0, 0.0, 0.0 );
drawNode( Nodes[ *i ] );
drawNeighbours( *i );
glPopMatrix();
j++;
}
}
}
else
if ( Nodes[ node ] == 1 or Nodes[ node ] == 4 ) {
int j = 0;
for ( std::list< int >::iterator i = FDBs[ node ].begin();
i != FDBs[ node ].end();
i++ )
{
if ( Drawn[ *i ] == 0 ) {
glPushMatrix();
glRotatef( j * 20.0, 0.0, 1.0, 0.0 );
glColor3f( 0.0, 1.0, 0.0 );
glBegin( GL_LINES );
glVertex3f ( 0.0, 0.0, 0.0 );
glVertex3f ( 2.0, 1.0 * ( j / 18 ), 0.0 );
glEnd();
glTranslatef( 2.0, 1.0 * ( j / 18 ), 0.0 );
drawNode( Nodes[ *i ] );
drawNeighbours( *i );
glPopMatrix();
j++;
}
}
j = 1;
for ( std::list< int >::iterator i = Stacks[ Bridges[node] ].begin();
i != Stacks[ Bridges[node] ].end();
i++ )
{
if ( Drawn[ *i ] == 0 ) {
glPushMatrix();
glColor3f( 0.0, 1.0, 0.0 );
glBegin( GL_LINES );
glVertex3f ( 0.0, 0.0, 0.0 );
glVertex3f ( 0.0, j / 18 + 2.0, 0.0 );
glEnd();
glTranslatef( 0.0, j / 18 + 2.0, 0.0 );
drawNode( Nodes[ *i ] );
drawNeighbours( *i );
glPopMatrix();
j++;
}
}
}
}