Limited-time offer! Save up to 50% Off | Solutions starting at \$6 each

# Advanced Topics in IP networks PDF

Added on - 22 Nov 2021

• 5

Pages

• 1231

Words

• 25

Views

• 0

• Save

Share

Showing pages 1 to 2 of 5 pages
Advanced Topics in IP networks: Exercise 1
Submission date: 15.11.2018
1.Consider the case of IP-lookup with Binary Search on Prefix
Lengths. M. Waldvogel, G. Varghese, J. Turner, and B. Plattner.
Scalable High Speed IP Routing Lookups.Proceedingsof ACM Sigcomm, 1997
(a)Give a worst case example for a lookup with markers butwithout pre-computations of the
bmpand calculate its complexity (assume the packet in your example is not the first
forwarded to its destination)
The objective lies in determining entire prefixes of specific lengths denoted as L. through
the use of hashes in finding the perfect corresponding prefix.
(b)Show an example where the worst complexity of lookup in the final algorithmwith
markersand bmpis logW+1.
(c)Consider that the prefixes in your database are only of lengths: /31 /22 /18 /15 /14 /8 . Design
an algorithm that is optimized to this type of database. What is the complexity of your
suggested algorithm?
Given Forward table .2
128.17\16
128.179\9
128.15.19\23
160.3\16
160.128\9
The procedure is carried out in backward retrogressive by dividing length posed on
databases in accordance to prefix lengths.
First, the use of markers in directing binary searches while bidding for greater corresponding
prefixes is a prerequisite for this example.
Linear Searching Hash Tables
Organizing a tables prefix length in the following elementary scheme searches hash tables in
a linear fashion.
LENGTH (L)HASHHASH TABLES
9o01010
16o01010 | 0110110
23o011011010101
The above case scenario depicts a small routing table containing four prefixes where (L) is
9,9,16,16 and 23. Since the prefixes are arrayed to only 3 submissions.
Therefore, searching for an address denoted as (D) begins with the most farsighted length
(L)of 23, extracting beginning length (L) bits of the address (D) followed by conducting
a search for all length unveilings in the hash table.
Since there is no use of a BMP, the first least length (l)is sought from the array (L). The latter
is actuated by classifying a single position lower than actual position of (l)as the searching
proceeds.