So guys, now let us take an example.
Let the router fetches an IP address from the IP header of the incoming packet and let the IP address.
120 8.2.3.5.
And our objective is to look up into the central data structure in order to find the route as per the
longest prefix match principle.
So the very first thing that we need to do is to convert the given IP address into its equivalent binary
form.
So this is the binary form of this IP address, which is a 32 bit address.
Now we will pass this 32 bit IP address into this and tried it out structure starting from the root.
Now note that route lookup algorithm uses an intermediate data structure called Stack.
We start our search in the central data structure from the route as usual.
All right.
Since we are starting our search from the route.
In that stack.
We always push the don't care child of the current mode at this point of time.
The current mode is the route where we are starting our from and the don't care child of the root node
is the node number four.
So in the stack we push the node number four and we also push the second thing in the stack.
And that second thing is the number of bits of the input string which has been parsed so far.
While we are traversing this, I'm trying to restructure from top to bottom at this point of time.
We are at the root node.
Therefore, the number of.
Bits of the input string that we have parsed so far is zero.
All right.
That is we are on the first bit.
So these are the two things which we need to push as a single entity in the stack, the don't care child
and the number of bits of the input string which we have passed so far.
While we are traversing this, I'm trying to add a structure from top to down.
So now let us begin our search in the same tried in add structure.
The first node of the input string is one.
So we will take the part along the one of the child of the root node and we land and the node number
three, the perfect slant of the node number three is eight.
So we will going to match.
First a bit of an input, a string with the first eight bits of the node three.
All right.
And they exactly matches.
Now, as the second step, we also need to push the don't care child of the note three.
But in this case the don't care child of the note three do not exist.
It is null.
So no need to push anything into the stack.
All right.
And we will continue our search down the tree.
So the next bit of the end for the string is zero.
So we will take the part along the zero child of the note three and we will land at number seven.
The prefix length of the number seven is eight.
So we're going to match the next eight bits of the input, the string with the eight bits of the north
seven and the exactly matches because they are exactly matches.
Therefore we will going to push the don't care child of the note seven into the stack so don't get out
of the note seven is six that the sixth note and.
By the time we reach the number seven, the total number of births that we have passed on this import
string is eight plus eight, which is 16.
So 16 bits of the input.
The string has been successfully parsed so far.
And after making an entry into the stock, we will continue our search.
Now the next bit of the string is zero.
So we will take the path along the zero child of the North seven and we land and the number five, the
perfect length of the number five is 16.
So we will going to match the 16 bits of the input string with the 16 bits of the effective prefix of
the naught five.
And they do not matches unfortunately.
So the moment there is a mismatch using this stack, we will going to backtrack.
So we will backtrack and we will shift our sides from the Nord five to the Nord six.
But how we will going to pop the element from the top of the stack.
So finally, Bob, the element from the top of the stack, it essentially says that we need to begin
our search from the Node six.
That is this mode and we have successfully passed 16 bits of our input string.
So it's essentially say is that we need to shift our search to the node number six and 16 bits of then
put the string has successfully passed.
So we need to begin matching the bits of the input, the string from this particular bit because previous
16 bits have already been passed and I, I'm trying to know structure.
All right.
So what we will going to do, we will going to shift our size to the node number six because we have
popped out this entry from the stack.
The entry of the stack essentially tells us that where we are, we have to shift our surge in the same
try to add a structure.
So here, after shifting to the node number six, the prefix length of the node number six is 16.
So we have to match the 16 bits of the string with the 16 bits of the node six and the matches.
All right.
So here the entire input, a string of the input is exhausted.
So this is the node where our search ends.
So the node six corresponds to the route 120 8.2.0.0 slash.
16.
So this is the round which matches with our IP address as per the longest prefix match principle and
the next hope of this round.
And the next hope of this drought that is the data part of the drought will be used for forwarding the
traffic and not that when your outlook algorithm and it is not necessary that your stack should be empty.
All right.
You ought to stack may have some elements by the time you have found the out of your interest.
So you have to discard or destroy the stack, which may contain some elements in it.
The moment you found they're out of your interest.
All right.
So in that stack, we always push the node, which is a don't care child offered spirit whenever there
is a no match.
Backtrack using stack pop operation.
Destroy the stack after the search is complete.
All right, so we will destroy the stack because we have already found the root of our interest.
Let us discuss the Outlook algorithm with one more example in the next lecture video.