Packet flow with multiples bridges & Routers

We have seen the packet flow when there are multiple bridges,  Now let us expand it bit more by adding one or more routers in between bridges and analyse the packet flow.

I have taken a basic example of two bridges and a router topology for connecting two nodes .

As we can see from above diagram Node1 is connected to Node2 via switch1-Router1-Switch2 . Both the nodes are in different network and hence we need a router to route packets .

To start with we assume Node1 & Node2 are just powered on and they do not have any information about connecting devices ( arp table is empty ).   Now a ICMP packet is being sent from node1 to node2 ( pinging 20.20.20.30 from node1 ) , let us analyse what happens while packet is being sent and received.

1. When an icmp packet gets trigger from Node1 , it checks the arp table entry for reaching the Node2. As it does not contain any arp entry for node2 it sends an arp request for finding the layer2 information of Node2 . In our case Node1 and Node 2 are not in the same network (which would be a basic L2 forwarding) and hence the arp packet would be sent on default gateway . ( if default gateway is not configured then Node1 cannot know where it has to send arp packet out).
2. Switch 1 will receive the arp request packet from Node1 . Now  Switch 1 will learn the mac entry corresponding to Node1 ,and creates /updates a mac entry corresponding to Node1.
3. Now switch 1 will forward the packet on to all of its interfaces except from which it has received the packet .In our case only one interface which is connected to router 1 .
4. When Router 1 receives the arp request , it checks in its route table if the destination ip address is part of its route table ( Either statically configured route entry or a dynamically learnt route) .
•  If Router1 finds the route entry corresponding to Node2 it gives reply to arp packet by providing its own mac address for reaching Node2.
•  If there is not route entry for Node 2 , the packet would be dropped and arp reply will not be sent .
5. The Arp reply sent by router 1 will be sent back to switch 1 , which intern will send it back to Node1 as it has learned the Node1 mac address during the arp request phase.
6. While sending the arp reply , Switch 1 will learn the mac address corresponding to Route 1 and creates/updates its mac address table.
7. Now since Node 1 has got the destination mac address to reach the Node2 ( strictly speaking it is the Router 1 mac address , how ever it is Router 1's job to take it further other side), it sends a ICMP request packet to Node2.
8. Since bridge1 has learned mac address of Router 1, it forwards the ICMP packet to the interface associated with Router 1.
9. When an ICMP packet is received at Router 1 , it checks if the destination ip address is its own ip address . If it is its own ip address it would send back the reply for ICMP packet.  In our case it is Node 2 ip address , it would keep ICMP packet aside and send an arp request for finding the layer2 mac address associated with Node2 ( Since it has got Route entry corresponding to Node2 ip address , it would know to which interface it should send the arp request).
10. Bridge 2 will learn the mac address of Router 1 and forwards the arp request on all of its interfaces except on the received interface (Similar to step 2 &3 ).
11. Node 2 would respond for the arp request , by providing its layer 2 information (mac address) to reach .
12. Bridge 2 would learn and update the arp entry for Node2 .
13. Now Router 1 will send the arp request which it kept aside by changing the destination mac address to the one it has learnt in step 11 and changing source mac address to Router 1's mac address.
14. Node 2 will respond to icmp request ( bridge 2 would have learnt the mac addresses of node 2 and router 1 by now as similar to step 2&3).
15. Once Router 1 gets reply for ICMP packet , it will alter the destination mac address to Node1's mac address ( ICMP echo Reply contains the mac address of Router1 from Node2) and source address as router1's mac address.
16. Bridge 1 will forward icmp reply to Node1 as it has updated its forwarding table while sending the icmp echo request .
17. Finally at Node1 , we will be having a reply for the ping request we have sent .

If we have multiple routers instead of Router 1 alone , at each router stage source and destination mac addresses would be changed similar to step 9 and 13 . And each router would send arp request for finding the next hop mac address at every stage and keeps it in its forwarding table.

Let us look into some other topic soon !

Source routing .

Usually routing is performed at the routing device ( network routing ) , to send the packet to a destination based on various routing decisions & routing protocols .

Where as in Source routing the sender would mention the route the packet must take to reach the destination . The router present in the network path, will simply forward the packet based on the routing path mentioned. 

We have two types of source routing techniques .

• Strict source routing 
• Loose source record route (LSRR)

In strict source routing , the sender determines the exact route the packet must follow to reach the destination . This type of source routing is generally not employed .

In LSSR  , the sender would mention one or more hops the packet must go through to reach the destination .

The main usages of source routing techniques are for 

• performance improvement 
• trouble shooting.

Understanding spanning tree !

Let us look into all important protocol of Layer 2 , which is spanning tree protocol . As we have seen in bridging loops article , it is understood that redundant topology and bridging loops coexist together unless we have some mechanism to avoid loops .

The mechanism is nothing but running a spanning tree protocol which will make sure to avoid loops and switches to redundant path during a failure.

Let us dive into the protocol and analyse how it exactly does this job for us .  I have created a following topology for understanding the protocol .

As we can see from the diagram, i have created a topology which has got multiple paths to reach a particular node . 

For example to for bridge 1 to reach bridge 4  , it can reach via bridge 1-bridge 3 -bridge 4   (or) bridge 1-bridge 4 (or) bridge 1 -bridge 2- bridge 4

Same is the case with other bridges . So in these type of topologies we must disable/shut down the ports which might causes loops.  Thankfully we have spanning tree protocol which takes cares of all such issues for us otherwise life would have been hell for network administrators !

If you observe in the picture, i have mentioned the mac address and priority of each of the bridges which are one of the key factors in spanning tree . 

The key steps in spanning tree protocol are .

• Find out the root bridge,
• Find the root ports 
• Find the designated ports 

To start with , All the nodes think they are the root bridges . Hence all the bridges participating in spanning tree will send STP (bridge protocol Data units) BPDUs out towards connected bridges.  

The BPDU format is as below

Protocol Identifier	2 (bytes)
Version	1
Message Type	1
Flags	1
Root ID	8
Path Cost	4
Bridge ID	8
Port ID	2
Message Age	2
Maximum Time	2
Hello Time	2
Forward delay	2

Considering the complexity of all the parameters , We will limit ourselves to Parameters which are relevant during convergence of a STP . I will present the complete BPDU details in a separate article.

Now coming back to election of root bridge ,  Since all the bridges are sending BPDUs each of the bridge ports will also receive BPDU from its adjacent bridge ports . The bridge will keep a "best" BPDU and discard the rest of the BPDU  , the  "best" BPDU is decided on the following criteria .

• Lowest root bridge ID ( bridge priority + MAC address )
• If Root IDs are equal , it will start checking for Lowest path cost  ( Cumulative cost of links between switch and root bridge)
• If the Path costs are equal ,Lowest sender bridge ID 
• If the Sender bridge IDs are also equal ,  Lowest sender port ID  (Port priority + port number)

Once the root bridge is decided based on the above election criteria , Now its turn for deciding the port roles .

• Root port - Every non root bridge must select the root port , the port which is closest root port (based on path cost )
• Designated port -  Ports providing the least path cost from the segment to root bridge , have to be decided . The bridge containing designated ports for a given segment is called designated bridge .
• Ports which are neither root port nor designated ports are put into blocking state ( Non designated ports).

If a bridge receives a better configuration that it would transmit , it would stop sending the configuration messages . Hence once the algorithm stabilizes only one bridge per LAN i.e. designated bridge for that LAN will send configuration messages. 

When a failure happens in any of the ports i.e designated bridge stops sending BPDUs for a period about max age time , Non designated bridge will turn the blocking port to forwarding state enabling packet transmission via that port .

After converging , the entire topology might look like below . It is not the only way it could converge , but depends on the selection criteria logic it could change accordingly .

Now we know the STP selection criteria , we will try to come up with state diagram of the STP by considering various stages during election process .

• Blocking  - The switch will go into blocking state when it receives a better path to root bridge Or a port is not a root port or designated port . During this state switch will not forward packets and discards frames it receives on its ports  . This time is normally 20 seconds.
• Listening  - After blocking state the root port or designated port will move into listening state. In this states , switch will not forward packets and discards the frames received from another segment for forwarding .It will accept BPDUs and gives it to switch module for processing. This time period is normally 15 seconds.     
• Learning  -  In this state switch starts learning the mac address from the received frames , but it will not forward frames in this state .  This time period is normally 15 seconds.
• Forwarding  - In this state, switch will start forwarding frames learns mac addresses of the received frames .
• Disabled  - The ports which are not participating in STP will be put into this state.

As we have seen how the topology got converged and states present in the STP , we should by know understood the time it takes for moving from one state to another is huge. So based on this time it will try to converge when there is a failure.  

There are some changes done in the STP to fasten the process and not loose the advantage of STP . We shall look into such things in the next article .

Finding maximum sub array in a given array

Hello everybody ,

I have got this question from some website and felt i should put it in my blog under a new label "interview section " 

As the question speaks out , we need to find out the maximum number of a sub array in a given array  ( this sub array was containing positive and negative integers so the question makes sense).

to make it more clear , assume we have an array 

example 1 :

 {3,4,-1,0,8,3,4,10,32,-30,5}        in this array the maximum sub array would be "57"

example 2 :

{3,4,-1,0,8,3,4,-20,32,-30,5};    in this array the maximum sub array would be "32" .

So we will try to write the program in a simplest form and with less complexity !

void main()
{
  int i = 0;
  int prev_max  = 0;
  int new_max  = 0;
  for (i = 0 ;i < 30; i ++)
   {
     new_max  += array[i];
      if(new_max < 0 )
          new_max = 0;
      else
        {
          if(prev_max < new_max)
          prev_max = new_max;
        }
   }

printf("Max of a sub array is %d \n", prev_max);


}

Above logic would find out the maximum of a sub array with o(n) complexity . 

I shall come up with such simple yet interesting questions on a regular basis. 

Bridging loops ..

As we have learned from the basic concept of bridges, what is a transparent bridge . From this understanding we will go one step ahead and find out what are bridging loops.

In any topology we would love to have redundant paths to reach  any destination so that during failure of one path , it seamlessly switches its direction and  chooses another path . 

In a bridged LAN environment, where we have multiple paths bridging loops will exists and drain the network bandwidth by continuously looping the packet around . Let us first see how it actually happens.

  

In the above picture, we see there are two bridges placed for connecting station 1 from network segment 1 to station 2 in network segment 2 . 

Let us imagine both the bridges forwarding table entry is empty and we get a packet from station 1 destined towards station 2.

•            Since both the bridges are in promiscuous mode , both will receive packet in segment 1 , destined to Station 2 .  Now since they are transparent bridges , they will learn that station 1 can be reached  via port connected to segment 1 .         
•             Both the bridges will now plan to send the packet out on all other interfaces except on the received port, as they do not have any entry for reaching station 2 .
•             Since only one bridge can transmit packet out any point of time ( because of CSMA/CD or any other layer 1 protocol), assuming bridge 1 will get time slice for sending packet . This packet will be received by station 2 as well as bridge 2. 
• Now bridge 2 thinks that station 1 has moved its position from segment 1 to segment 2 , it will alter its forwarding table accordingly .
• When bridge 2 sends packet out once its get time slice , Along with  station 2 , bridge 1  will also receive the packet. Now imagine station 2 behavior , it has received same packet twice from two different points - whose behavior is unpredictable here !!
•  Since bridge 1 also received the packet  from bridge 2 , it alters its own forwarding table thinking that station 1 has moved it position from segment 1 to segment 2 .
• Every time a packet is generated , it loops around the paths continuously and bridge forwarding entries will flap every time . Imagine a case when you send a broadcast packet from station 1 / station 2 . 
• This is mere example of what could happen if we have multiple paths , in real life scenario situation is much worse , each of stations will have multiple paths in various segments . 

To avoid loops , we need to run a protocol on the bridges which can determine a possible loop and shuts down one of the ports of the bridges ( logically !! )

Lets look in to such protocol in the next article , which is "spanning tree protocol "

How to check if a tree is a BST

Hello Folks,  In my previous post i have mentioned the ways to create , delete and display a binary search tree . Now let us create logic for finding out if the binary tree is a binary search tree or not !

In a binary search tree each  node and its child nodes must follow these rules.

•  Parent node must be greater than left child node.
•  Right child node must be greater than the parent node.

So we shall try to check if the tree satisfies above two rules by recursively traversing down the tree in both the directions  ( left branch & Right branch).

int

check_if_bst_or_not(struct binary_tree *temp)

{

  if(temp != NULL)

  {

    if(temp->pleft &&  temp->pleft->data > temp->data)

     return -1 ;

    if(temp->pright &&  temp->pright->data < temp->data)

     return -1 ;

    check_if_bst_or_not(temp->pleft);

    check_if_bst_or_not(temp->pright);

  }

 return 0;

}

In first if condition , i have tried to check if a left node exists and if it greater than the parent node , as per Rule 1 it should not be true.

In second if condition , i have tried to check if a right node exists and it is  less than the parent node , Which is as per Rule 2 should not be true.

This way , recursively traversing down the tree and checking for all the nodes .  If all the nodes satisfy the condition it means our binary tree is a Binary search tree !!

You can try this program , along with the creation of binary search tree for checking the result !!

Building a binary tree !!

In this article i would like to present the binary tree basics and how to implement it using C program .

Binary tree is a data structure , in which each of its node will have at most two children which we refer them as left child and right child.

As we can see from above picture , parent node has got two child nodes( Node2,Node3). Node2 has got again two child nodes (left child and right child) . Node 3 has got only child to its right side (Right child) . 

We can organize this tree in two ways .

• Binary tree 
• Binary search tree

A Binary tree can have up to two leaf nodes and there is no rule in filling / building the tree . Where as in a binary search tree

• Parent node data should be greater than all of its leaf nodes data.
• Right node data should be greater than its left siblings data

First we will see how we can construct a binary search tree (addition/deletion/display) in all the possible ways (pre-order ,in-order & post-order)

Before proceeding , we need to look into the heart of a tree i.e node data structure which is capable of storing its own data as well as having references to its children !

struct binary_tree{

  int data;

  struct binary_tree *pleft;

  struct binary_tree *pright;

};

As we can see it contains node element or data of the node and self referenced left and right nodes .

Now , to add a node to the tree we need to look at the root node i.e. the top node of the binary tree  (like a great grand father  !! )  if it exists need to add the node to its proper position .  Proper position here i mean is if the data is lesser than its parent node data , it should go to left branch of the tree , and  if it is more than its parent data it should got to right node .

Now this will be called as a " binary search tree "

void add_node(int data, struct binary_tree *tree)

{

  struct binary_tree *temp = NULL;

  if(root == NULL)

   {

     temp = malloc(sizeof(struct binary_tree));

     temp->data = data;

     temp->pleft = NULL;

     temp->pright = NULL;  

     root = temp;

     return ;

   }

  temp = tree ;

  if(data < temp->data)

   add_left_node(data,temp);

  else if(data > temp->data)

   add_right_node(data,temp);

  else

    printf("Duplicate entry , not adding \n");

 return ;

}

/*Adding a Right node*/

void add_right_node( int data, struct binary_tree *tree)

{

  struct binary_tree *temp = NULL;

  if(tree->pright == NULL)

  {

    printf("Adding to the Right node \n");

    temp = malloc(sizeof(struct binary_tree));

    temp->data = data;

    tree->pright = temp;

    temp->pleft = NULL;

    return ;

  }

  temp = tree->pright;

  if(data < temp->data)

   add_left_node(data,temp);

  else

   add_right_node(data,temp);

}

/*Adding a left node*/

void add_left_node( int data, struct binary_tree *tree)

{

  struct binary_tree *temp = NULL;

  if(tree->pleft == NULL)

  {

    temp = malloc(sizeof(struct binary_tree));

    temp->data = data;

    tree->pleft = temp;

    temp->pright = NULL;

    return ;

  }

  temp = tree->pleft;

  if(data < temp->data)

   add_left_node(data,temp);   

  else if(data > temp->data)

   add_right_node(data,temp);   

  else

    printf("Duplicate entry , not adding \n");

   

}

We have three traversal techniques

• Pre order 
• In order
• Post order

We shall see all the three traversal methods

/*In order display*/

/*Display left node , Root node , Right node */

void display_tree_inorder(struct binary_tree *temp)

{

  if(temp != NULL)

  {

    display_tree_inorder(temp->pleft);

    printf("node = %d \n",temp->data);

    display_tree_inorder(temp->pright);

  }

}

/*Pre order display*/

/*Display Root node , left node ,Right node */

void display_tree_preorder(struct binary_tree *temp)

{

  if(temp != NULL)

  {

    printf("node = %d \n",temp->data);

    display_tree_preorder(temp->pleft);

    display_tree_preorder(temp->pright);

  }

}

/*Postorder display*/

/*Display Root node ,left node , Right node */

void display_tree_postorder(struct binary_tree *temp)

{

  if(temp != NULL)

  {

    display_tree_postorder(temp->pleft);

    display_tree_postorder(temp->pright);

    printf("node = %d \n",temp->data);

  }

}

Deleting a node is a tricky part in entire binary tree  , i must tell you

• Case 1 : Both left child and right child are NULL
• Case 2 : Right child exists and Left child is NULL
• Casee 3 : Left child exists and Right child is NULL
• Case 4 : Right child & Left Child exists !!
• Case 4 .b  - Only one right child and from then no left child

These are the combinations one needs to consider before deleting a node from a binary search tree , to make sure it builds up properly after you delete any node !!

/*Deleting a node*/

void delete_node(int data, struct binary_tree *temp)

{

  struct binary_tree *current_node = NULL;

  struct binary_tree *prev_node = NULL;

  struct binary_tree *tmp_node = NULL;

  prev_node = current_node =temp;

  while(current_node)

  {

    if(current_node->data == data) /*It is the node to be deleted*/

    {

        /* Case 1 : Both left child and right child are NULL*/

        if(current_node->pright == NULL  && current_node->pleft == NULL)

         {

           if(current_node->data < prev_node->data)

             prev_node->pleft = NULL;

           else

             prev_node->pright = NULL;

           free(current_node);

           return;

         }

        /* Case 2 : Right child exists and Left child is NULL*/

        if(current_node->pright != NULL  && current_node->pleft == NULL)

         {

           prev_node->pright = current_node->pright;

           free(current_node);

           return;

         }

        /*Casee 3 : Left child exists and Right child is NULL*/

        else if (current_node->pleft != NULL && current_node->pright == NULL )

         {

           prev_node->pleft = current_node->pleft;

           free(current_node);

           return ;

         }

       else /*Case - 4*/

        /*Right child & Left Child exists !!*/

        {

           prev_node = current_node;

           tmp_node = current_node->pright;

           if(tmp_node && tmp_node->pleft != NULL)

           {

            while(tmp_node->pleft != NULL)

             {

               current_node = tmp_node;

               tmp_node = tmp_node->pleft;

            }

            prev_node->data = tmp_node->data;

            current_node->pleft = tmp_node->pleft;

            free(tmp_node);

            return;

           }

           else /*Case 4 .b  - Only one right child and from then no left child */

           {

             current_node->data = tmp_node->data;

             current_node->pright = NULL;

             free(tmp_node);

             return;

           }

       }

    }

    else

    {

      prev_node = current_node ;

      if(data <  current_node->data)

       current_node = current_node->pleft;

      else 

         if(data >  current_node->data)

          current_node = current_node->pright;

    } 

  }

}

void delete_data()

{

 int data ;

 printf("Enter the node data to be deleted \n");

 scanf("%d",&data);

 delete_node(data,root);

}

void main()

{

  int i ; 

  int number ;

  //char test[20]={20,19,18,16,15,14,17,21,22,23,24,25};

  //char test[20]={8,10,14,13,3,6,1,4,7};

  unsigned char test[20]={90,150,95,175,92,111,166,200,20,75,5,25,66,80};

  for ( i =0 ; i<14 div="" i="">

  {

    number = rand() % 30 ;

    //printf("adding number %d \n", number);

    printf("adding number %d \n", test[i]);

    //add_node(number ,root);

    add_node(test[i] ,root);

  }

  display_tree_inorder(root);

}

Hope I have covered binary search tree in the most simple way to learn !  My next topic would be  " how to find out if a binary tree is a binary search tree or not "  . Till then bye :-)