So guys, before we started discussion of our algorithm for implementing IP before routing table, we
need to get ourselves familiar with certain representations that we were going to follow.
So as I said, we were going to use triad data structure in order to implement routing table.
And Amtrak is a tree like data structure.
So obviously am tribal going to have nodes.
We will call those nodes as AM try node.
All right.
So this is a diagram which shows a typical I'm trying node which will be used to store groups.
So each node of an AM try it will going to the store route.
So let us discuss with the help of an example that how each node in an empty drive will going to store
information.
So let us suppose that we have around 1.2.2.4 slash 24.
So we will going to express this route in terms of prefix and wildcard.
And obviously for IPV four out, the prefix LAN is 32.
So following is the effective prefix that we were going to derive from the prefix and wildcard combination.
All right.
So as I said, it's not will going to store the information regarding out each node.
We're going to store the effective prefix, the prefix lamb and certain pointers which point to its
child nodes.
The child nodes we're going to discuss later when we will actually discuss the algorithm.
So the I'm trying node, which will be used to store this particular out, would look something like
this.
This is the effective prefix.
This is the perfect lan.
All right.
Similarly, if I have a 16 bit prefix and a 16 bit wild card, then the effective prefix would be this
one.
And the tri node that we were going to store this information would have 16 bit effective prefix.
And this is the perfect slam.
All right.
Now note that each amp try node may store a part of their out or the entire out altogether.
There is no restriction.
So now if I were to ask you that, can you write a data structure definition which represents an MRI
not optimized for storing doubts?
So you would say that this is such a data structure, as I said, that each MTI node would going to
store effective prefix and effective prefixes are stored as a combination of prefix and wildcard.
Therefore, you would need to bitmaps in order to store prefix and wildcard separately, but together
they represent an effective prefix.
All right, bitmap is nothing, but you can visualize bitmap as an array of bits and nothing else.
All right.
Prefix them.
We already know in this case the prefix land is 32.
In this case, the prefix lan is 16.
So number of beds in the prefix and total number of beds.
And the wildcard is the prefix land and.
Prefix, length of the prefix and wildcard is always going to be same no matter what.
All right.
Then each note contains a pointer to the parent and each note contains the pointer to its children.
This we will going to discuss when we will be actually discussing the algorithm.
Each note also contains some data which we will going to discuss when we will be discussing the algorithm.
All right.
So the point here is that that you should need.
You should understand the MTI no data structure and how we will going to store the effective prefix
in this data structure as well as the prefix lam.
And finally, we need to discuss how to represent the root of the EmDrive.
So as I said, Amara is a tree and every tree has a root.
In our case, Autumn tried it.
A structure has a root, which is actually a space, a node in them.
Try and defers from rest of the nordson the Amtrak.
So rude of the Amtrak was going to be a special note and we need to disclose that.
So this represents the route of the Amtrak.
And the special thing about route is that that do not have any effective prefix and its prefix lana
zero.
So it means that this particular bitmap will contain all zeros and the wild card also contains all zeros.
The prefix line will be zero.
The pointer to the parent will be null and to initialize red in the beginning, when the tree is entirely
empty, all the child nodes would point to null.
All right.
And the data part is also no.
So this is what Route Nord is and this is what am trying to structure would look like when the AMP tried
to restructure is just initialized a freshly initialized and created a structure with just contain a
root node with everything initialized to null or zero.
All right.
Now, coming to this enumeration, as I said, that each I'm trying, Lord, we're going to have three
children.
These children are indexed in the MTI node as zero one and don't care children.
All right.
We will going to discuss in detail when we will going to discuss the algorithm that what does it mean
by saying that this particular children is a zero to children, a zero to child on this particular children
is the one that the child.
And this particular children is a don't care child.
So each node in the Amtrak can have maximum of three children and we indexed these children as zero
one or don't care.
And as I said, you need to visualize bitmap as an array of bits and nothing else.
And on this day you can perform operations like you would have performed on normal areas.
For example, we can implement the function bitmap set at bars, the pointer to the bitmap and pass
the index.
So for example, if you pass the index number as 18, then this particular function must set the budget
at index dipping to one.
All right.
So, guys, with this, we have finished with all the prerequisite details that we need to know before
we start our discussion on implementation of APB for a routing table.
First, we will only going to focus on the algorithmic part.
That is how we will going to insert rounds in this AMP trial.
How we will going to delete the rules from this and try.
How we will going to search for Arabs and the Samurai and how we will going to implement longest prefix
match based search and this and try to do the structure.
Remember this and try to a structure would be nothing, but it is your IPV four routing table in the
end.
So I hope you understood this structure.
This is structure is very much important in order to understand the algorithm.
Once again, every note of the amp travel going to stored defective prefix, which is a combination
of the prefix and wildcard of course the prefix land, the pointer to the parent and the pointer to
its children and the additional application, the specific data.
So now in the next lecture video, we will going to start our discussion with how we will going to insert
routs one by one into and try to add a structure.