Question

Problem 2 -  Consider a datagram network using 8-bit host addresses.Suppose a router uses longest prefix matching and has the following forwarding table:

Prefix Match    Interface

  1    1

10 2

111 3

100 4

010 5

otherwise 6

To which interface will datagrams having the following destination addresses be forwarded to?

11011011

10010001

11101011

10111110

01110110

Explain how you arrive at the answers.

Answer 1

Here, In the routing table every network address has the same subnet mask as the datagram network uses 8-bit addresses so we don't have to worry about ANDing and the prefixes are already given so we just have to compare the bits and see which are overlapping.

Longest prefix matching matches according to maximum number of bits exactly matched in the IP address and prefix in the routing table. So, we will match first 3 bits of IP address as our prefixes in the routing table contains a maximum of 3 bits: 111, 100, 010 if they are exactly matched, the packet will be forwarded to the respective port otherwise we will compare the first 2 bits of the IP address and prefix (10 at port 2), if they match exactly they will be forwarded to port number 2, if they do not we will compare the first bit of IP address to prefix 1 at port 1, if they match exactly they will be forwarded to port 1 other wise they will be forwarded to port 6.

a) 11011011 here the first 3 bits = 110 is not present in the routing table prefixes(only 3 bit prefixes are: 111, 100, 010) so now we go and compare its first 2 bits = 11 which is also not present in routing table prefixes (only 2 bit prefix is: 10) so now we compare the first bit = 1 which is present in the prefix table at port number 1. So, it will be forwarded to port 1.

b) 10010001, here the first 3 bits = 100 is also present in the prefixes table at port number 4. So, it will be forwarded to port 4.

c) 11101011, here the first 3 bits = 111 is also present in the prefixes table at port number 3. So, it will be forwarded to port 3.

d) 10111110, here the first 3 bits = 101 is not present in the routing table prefixes(only 3 bit prefixes are: 111, 100, 010) so now we go and compare its first 2 bits = 10 which is present at port number 2. So, it will be forwarded to port 2.

e) 01110110, here the first 3 bits = 011 is not present in the routing table prefixes(only 3 bit prefixes are: 111, 100, 010) so now we go and compare its first 2 bits = 01 which is also not present in routing table prefixes (only 2 bit prefix is: 10) so now we compare the first bit = 0 which is also not present in the prefix table so it will be forwarded to port number 6.

If you found this answer helpful, please give it a thumbs up! :)