=========================preview======================
(elec315)[2009](s)midterm~PPSpider^sol_10324.pdf
Back to ELEC315 Login to download
======================================================
(1) (4 pts) A CIDR lookup Table is given below.
IP address output port
144.45.24.12/22 port 1
144.45.14.10/23 port 2
144.45.28.0/23 port 3
144.45.12.0/24 port 2
0/0 port 1
An coming IP packet with the destination address:
144.45.31.22
What is the output port for this packet? Explain.
Reference Solution:
As it is CIDR lookup table, so the longest prefix matching is selected. 144.45.24.12/22 port1 10010000 00101101 00011000 00001100 11111111 11111111 11111100 00000000 144.45.14.10/23 port2 10010000 00101101 00001110 00001010 11111111 11111111 11111110 00000000 144.45.28.0/23 port3 10010000 00101101 00011100 00000000 11111111 11111111 11111110 00000000 144.45.12.0/24 port2 10010000 00101101 00001100 00000000 11111111 11111111 11111111 00000000 0/0 port 1
If the IP address is 144.45.31.22 => 10010000 00101101 00011111 00010110 If the IP address is 144.45.27.22 => 10010000 00101101 00011011 00010110 If the IP address is 144.45.15.22 => 10010000 00101101 00001111 00010110
so based on longest matching, we have
144.45.31.22 => no matching with the fist 4 IP addresses thus get to 0/0 (this match to all the IP addresses) => port 1
Note: pay attention to the mask when doing the prefix matching
144.45.27.22 => 144.45.24.12/22 => port 1
144.45.15.22 => 144.45.14.10/23 => port 2 Deduction rule: Answer is correct, get 2 points Correct explanation, get 2 points
Incomplete explanation, get 1 point
(2) (6 pts) TCAM is a common device that stores IP lookup tables. As discussed in class, this device allows a fast IP table lookup. Assume there are 40 entries in the TCAM and the length of 10 each for length 14, 16, 17, and 20. These entries are arranged in the following order:
Entries 0.\9 : length 14,
Entries 10\19: length 16
Entries 20\29: length 17
Entries 30\39: length 20
(a) Now suppose we like to add an entry with a prefix of length 17. What is the minimum number of entries that need to be rearranged? (b) Repeat (a) if the length of the new prefix to be added is 15.
Reference Solution
(a)
For an entry with the prefix of length 17, the minimum number of entries that need to be rearranged is one. Reason: As the entries are organized in ascending order of the prefix lengths, the entry with prefix of length 17 would be added below the entries 10\19 with prefix length 16 and above the entries 30\39 with length 20. For the TCAM, the sequence in each block is not important, so we only need to move entry 30 with prefix length 17 to the bottom, i.e. entry 40, and thus we get the gap to insert the entry with prefix length 17 into entry 30.
if length is 18 => one entry needed to be rearranged if length is 19 => one entry needed to be rearranged
(b)
if the new prefix to be added is 15, 3 entries that need to be rearranged Reason: As the entries are organized in ascending order of the prefix lengths, the entry with prefix of length 15 would be added below the entries 0\9 with prefix length 14 and above the en