A kind data structure and arithmetic for subnetting

Written by www.softsession.com

This document describes a kind data structure and arithmetic for subnetting. With this arithmetic, the required subnet can be quickly located in a network with complicated hiberarchy.

Because network segment is identified by IP address and mask, such as 192.168.0.0/24. And IP address and mask is represented by 32 bits Binary. The binary tree can be used to describe the net structure and save IP address management information. 

Eg. A organization has the network segment 192.168.0.0/22, and there are two departments( Department A and Department B) under this organization. Department A was assigned subnet 192.168.0.0/25 and B was assigned subnet 192.168.1.0/25，the network structure chart is as following:

Below is the IP address management information structure chart represented by binary tree :

The data structure of each node is as below:
struct SNetdata
{
     string sIP;           //subnet ID, identified by IP address and mask, such as 192.168.0.0/24
     int iNodeType;
     string sLeftIP;     // left subtree node, left subtree subnet ID
     string sRightIP;   //right subtree node, right subtree subnet ID
     string sParentIP; //parent node, parent subnet ID
};

There are four types of node: used, unused, middle node, root node, as below:
enum NODE_TYPE
{
     USEDNODE=1,     //used node
     UNUSEDNODE=2, //unused node
     MIDDLENODE=3,  //middle node, which is generated during the course of subnetting
     ROOTNODE=4,     //root node
};

IP address management information is saved in these nodes. All these nodes can be linked by double linked list. Considering the subnet ID will be frequently used to perform searching in the IP address management dataset, thus the map of STL is used to save each node and subnet ID is used as index key in order to quicken the searching speed.
typedef map<string,SNetdata,less<string> > MAPNetData;
MAPNetData NetDatas;

Assumed that the organization is newly added Department C and Department D. C is needed to assign a 25-bits mask subnet and D is needed to assign a 24-bits mask subnet.
The ordinary IP address management software and subnet calculator can't solve this problem. With the binary tree data structure, the problem can be solved easily. For the first problem, to assign a 25-bits mask subnet for Department C, we preorder traversal the binary tree beginning from the root node 192.168.0.0/22, to find the leaf node of unused type and the mask less or equal 25. In this example, we can find 192.168.0.128/25, which is the subnet assigned for Department C.

Traversal arithmetic is as below:

int TraversalTree(string StartIP, int iTarMask, string& ResIP)
/*
StartIP: represents the subnet ID of the beginning node when preorder traversalling the binary tree. In this example it is root node192.168.0.0/22.
iTarMask: represents the mask of the target node we are searching for
ResIP: represents the subnet ID of the target node we have found
*/
{
     MAPNetData::iterator MyIterator;
     SNetdata NetData;
     int iSrcMask;     // represents the mask passing the node when traversal the tree
     int iRes,k;
     string tmpstr;

     MyIterator=NetDatas.find(StartIP);
     if(MyIterator==NetDatas.end())
          return -1;
     NetData=(*MyIterator).second;

     tmpstr=StartIP.substr(StartIP.find("/",0)+1,2);
     iSrcMask=atoi(tmpstr.c_str());

     if(iSrcMask>iTarMask)
          return 3;

     if(NetData.LeftIP==""&&NetData.RightIP=="")
     {
          if(NetData.iNodeType==UNUSEDNODE)
         {
               ResIP=NetData.IP;
               return 1;     // Have found it
         }
         else
              return 2;
     }

     iRes=TraversalTree(NetData.LeftIP,iTarMask,ResIP);
     if(iRes<0||iRes==1)
          return iRes;

     iRes=TraversalTree(NetData.RightIP,iTarMask,ResIP);
     if(iRes<0||iRes==1)
          return iRes;

     return 0;
}

Then for the second problem, to assign a 24-bits mask subnet for Department D. Following the above mentioned arithmetic to traversal the binary tree, we can find 192.168.2.0/23. Cause the assigned subnet is 24-bits mask, we need to perform subnetting under this node. Then we will get 192.168.2.0/24, which is the subnet we needed. After the assigning, the IP address management information structure chart represented by binary tree is as below:

Back