So guys, now let us start with understanding of the algorithm to construct IPV four routing table.
So to start with, we have a route node of the entry and the route node initially is empty.
It do not have any effective prefix.
The prefix lan is zero and all the pointers offered children are now here.
One represents the node ID, so I have taken a node idea only for the sake of making our discussion
a little bit easier so that I can talk about that this node and that node with the help of node I.D..
Otherwise, node I.D. has nothing to do with the algorithm.
It is only for the sake to identify that which node I'm talking about.
So to start with, let us say that we need to insert around 1.2.2.4 slash 32.
All right.
So the very first thing that we need to do is to convert this out into its effective prefix form.
So this is the effective prefix for this route.
All right.
And when we say it out, it also means that you are also saying that when this route is used for forwarding
the traffic.
Then which is the next hope to be used.
So next hope is some data structure which is in mammary somewhere else.
All right.
And we call the date of this drought as that next talk.
That is the atlas of that next hope.
So every out is associated with the next tool and the data part is nothing, but it is the next hope
object which is associated with that drought.
All right.
So the next thing that we need to do is to insert this drought into our I'm trying it out structure.
So insertion of drought always begins from the root.
Now, in order to insert a drought, we will going to examine the very first bit of the effective prefix
bit of a drought.
In our case, the very first bit is zero.
All right.
So it means that we need to insert this drought as a zero to child of the root naught.
And it's over.
All right.
So the new node that is just inserted is has been given a node it said to.
And because the effective prefix of this drought started with but zero.
So we will going to insert this particular around as a zeroth child of the root not.
So far, the nod to this is the effective prefix.
This is the perfect slam and this is the data part.
And obviously all the children of the Node two will point to none.
And now the zero child of the root node points to the Node two.
All right.
So with this, the insertion of this route is successful.
Similarly, if you want to insert the rout, one to wait two, three, four, quickly convert this round
into its effective prefix form.
So this is the representation of this rout.
And examine the first bit of this round, which is one.
So again, the insertion of the root begins with the root node.
So we will going to create a new node with Node ITC three, and we will make this new node as the one
that child of the root knot.
And the node number three will going to contain that effective prefix as the following.
And this is the perfect slam.
And this is the data part.
All right.
So we have successfully insert the root number two in the same tried it out structure.
So things are pretty much easy and simple.
We just scan the first bit of the effective prefix of the new root.
And based on that, we insert a new child node as a child of the root note.
Similarly, suppose you want to insert the root number three, which is of default root 0.0.0.00.
So the effective prefix representation of this now does nothing but all don't curse.
All right.
So the first bit of this effect, the prefix is don't care.
So it simply means that you need to insert a new child node as a don't care child of the root not.
All right.
So for that node number four, the effective prefix is the following.
And the prefix lan would be time to to.
Of course, I missed it.
And the data part will point to the next top up to sprout.
So so far, the things are pretty much easy and simple.
Now let us talk about insertion of the route.
128.2.0.0 Slide 16.
All right.
So now things becomes a little bit non-trivial.
So let us convert the routing number four into its effective prefix form.
So you can see this is the route number four, which is converted into effective prefix form.
Now let us start traversing the tree.
The starting from the root node.
So the first bit of this new route is one.
So we will traverse the child number one of the parent mode.
So we reach the number three and once we descend down the tree we do the prefix matching.
So viable going to match the effective prefix of the node three with the effective prefix of the new
route.
And we find that the first 16 bits of the node, three matches exactly with the first 16 bits of this
new route of the effective prefix of course.
So it means that the bit which is highlighted in pink colour is the bit at which the mismatch happens.
So whenever in that routine session a mismatch happens like this case, the not present in the am try
at which the mismatch happens will undergo node split.
So it means that norm node number three will undergo node split procedure.
Now what is not a separate procedure?
Let's discuss that.
So guys, now let us discuss how node spec procedure is executed.
The Nord number three will undergo not split because while traversing down the AM try from the root
node at node number three, there occurs a mismatch in the effective prefix of the node three and the
effective prefix of the new root.
The bit at which the mismatch happens is shown in the pink column.
All right.
So this is the point at which a node number three will undergo in order to split.
So as a part of node split procedure, the very first thing that we do is that we will going to create
two new nodes, the node number five and the node number six.
The node number five is called a data node, whereas node number six is called and is not now, nor
number five is called a daughter node.
Because as a daughter of its parent, the data node will bottle the positions of its parent note.
Now what are those positions?
First of all, the data node will bottle the bits from the effective prefix of experience node from
the point where the mismatch has happened up to the last.
All the bits from the effective prefix of the parent node is copied as it is as the data node effect
the prefix.
So actually it is not a copy, but it is a transfer.
So as we are transferring here, 16 bits from the parents node effective prefix to the daughter node
effective prefix.
Therefore parent note effective prefix would be shrink by 16 bits.
So the new prefix length of the parent node would become 16 because the latter part of the 16 bits has
been transferred to the parent node.
All right.
So the parent node prefix lan would become 16.
This is the first thing.
Now why we have made the date honored as the zeroth child of the parent, not because the rate at which
that split happens is the zeroth bed.
All right.
So it means that the Dayton Road will become the 0 to 0 of the parent, not then.
Dayton would also borrows the data of the parent mode.
So whatever with the data pointer of the parent from what was the Dayton will borrow all that data.
All right.
So that data point or the parent board would become null.
And the third thing that the data node borrows from the parent mode is the children of the parent node.
So in this case, we did not have any children of the nor number three before that, nor number three
undergo a split.
But if it had any children, all those children will be transferred to the daughter.
So we will see this procedure when we will go to split the node which already had children in our subsequent
example.
So this was the story of the daughter, not the daughter not borrows three things from the parent mode.
The first is the bits from the effective graphics of the parent mode.
The second is the state of the parent mode.
And the third is the children on the parent mode.
All right.
And obviously, the perfect slant on the parent note would get reduced after a split, depending on
how many birds have been transferred to the total node.
Then the second node is the nese node, which is very simple case.
The Nese Nord will borrow, it's the Nese Nord will borrow its effective prefix bits from the effective
prefix because of the new role of the new route.
Right.
So from the point where the mismatch has happened, we will going to copy the prefix bits of the new
round as the prefix bits of the nice snort.
And here since we are copying the 16 bits.
Therefore the prefix length of the nice node is 16 and obviously the data part of the new route will
be copied as it is as the data part of this and nought.
And obviously, since that nice node is a new node, all of its children points to known and why this
news node is made as a don't care children of its parent because the first bit of this nice node is
a don't care.
So this is the procedure of splitting an order.
You can rewind this video and go through the explanation again to understand it better.
However, we will going to insert few more roots in this tree, and we will going to discuss nodes split
algorithm a few more times again.
So the following points needs to be highlighted.
Data of the parent node is transferred to the data node transfer of the effective prefix bits of the
parent node to the total node, and transfer all the children of the parent floor to the daughter.
Not right.
So you can see that the daughter node is notorious in the sense that it takes away all the positions
offered spin and node which is undergoing a split.
Remember that?
So the next slide shows that how does the and try it structured looks after the insertion of the root
128200.
Slide 16.
This is the pictorial representation of the and try to add a structure before the insertion of the out
and this is the pictorial representation of the and try to add a structure after the insertion of their
out.
And you can see all the changes has happened in the node three and downwards.
The Node two and four of the same try to add a structure is untouched.
You can see the data part of the tree is now the prefix length of the tree has been reduced from 32
to 16.
The bits from the effective prefix of the note three has been transferred to its daughter node.
And the news notes bottles its effective prefix birds from the birds of the out which is just inserted.
So now can you write the steps regarding how the no disparate algorithm can be written in simple, plain
English words?
Can you do that?
Let us do that in the next lecture video.