Purdue CS 63600 - IP prefix look ups

Unformatted text preview:

CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 6: IP prefix lookups 1CS 636 Internetworking 2 000 P1 001 P1 010 P1 011 P1 100 P3 101 P5 110 P7 111 P9 000 P5 001 P4 010 P4 011 P4 100 101 110 111 000 001 010 P8 011 P8 100 101 110 111 Input 000 P1 001 P1 010 P1 011 P1 100 101 P5 110 111 P9 000 P5 001 P4 010 P4 011 P4 100 P3 101 P3 110 P3 111 P3 000 P7 001 P7 010 P8 011 P8 100 P7 101 P7 110 P7 111 P7 Leaf pushing Multi-bit trie with fixed stride Multi-bit trie with variable stride 11000010 Longest matching prefix P7 Leaf pushing reduces memory usage but increases update timeCS 636 Internetworking 3 P1 000* P1 001* P1 010* P1 011* P3 100* P4 100001* P4 100010* P4 100011* P5 100000* P6 101* P7 110* P8 110010* P8 110011* P9 111* 00000 1 00001 0 00010 0 00011 0 00100 1 00101 1 00110 1 00111 0 01000 1 01001 0 01010 1 01011 0 01100 1 01101 0 01110 0 01111 1 10000 1 10001 0 10010 1 10011 0 10100 1 10101 1 10110 1 10111 0 11000 0 11001 0 11010 0 11011 0 11100 1 11101 1 11110 1 11111 0 00 0 01 4 10 8 11 13 When the compression bitmaps are large it is expensive to count bits during lookup. The bitmap is divided into chunks and a pre-computed auxiliary array stores the number of bits set before each chunk. The lookup algorithm needs to count only bits set within one chunk. Bitmap supporting fast counting 13+0=13 11001010 Longest matching prefix P7 P7 One main problem with Lulea compressed ◦ Inserts are not fast ◦ So, it requires two copies – waste in storage ◦ Can actually half the number of prefixes  Ideas ◦ Leaf pushing – main culprit ◦ How to rectify this problem ? ◦ Use two bit maps – one for internal prefixes and other for pointers CS 636 Internetworking 4CS 636 Internetworking 5 11001010 P1 0* P2 1* P3 100* P4 1000* P5 100000* P6 101* P7 110* P8 11001* P9 111* Longest matching prefix P7 000 0 001 0 010 0 011 0 100 1 101 0 110 1 111 0 0* 1 1* 1 00* 0 01* 0 10* 0 11* 0 000* 0 001* 0 010* 0 011* 0 100* 1 101* 1 110* 1 111* 1 P1 P2 P3 P6 P7 P9 Pointers to children and prefixes are stored in separate structures. Prefixes of all lengths are stored, thus leaf pushing is not needed and update is fast. Bitmaps have 1s corresponding to entries that are not empty. Representing node as tree bitmap P2 What about next hop pointers ? ◦ Can have a different indexing array ◦ Two accesses for every node, but can be reduced only to one extra access at the end of the search  Search algorithm requires iterations ◦ 101* can match 1* or 10* or 101* -- 3 iterations. ◦ Hardware much simpler – using combinatorial logic CS 636 Internetworking 6 Generalizing exact matches to prefix lookups ◦ Adaptation of binary search ◦ Adaptation of hashing CS 636 Internetworking 7 Each prefix is a range ◦ N prefixes partition space into 2N+1 disjoint intervals  Use binary search to find interval where a destination lies  Precompute mappings for all ranges  Complexity – O(log 2N) memory accesses ◦ Use higher radix for lower number of accesses (e.g., B-Tree)  Not better than multi-bit tries with compression, but it is not covered by patents CS 636 Internetworking 8 Naïve search of all possible prefix lengths (W exact matches, W possible lengths) ◦ Can do binary search (log W)  Different from binary search on prefix ranges that would take log N accesses  Need to add markers to guide binary search and precompute best matching prefixes CS 636 Internetworking 9CS 636 Internetworking 10CS 636 Internetworking 11 Markers announce: “Possibly better info on right, no guarantees” Can lead to wild goose chase ! Compute best matching prefix of each marker as Marker.bmp  When we get a match with a marker, we do a search to the right, but we remember the bmp of the latest marker encountered. CS 636 Internetworking 12CS 636 Internetworking 13X 1 1 1 1 1 m-bit Array H1 H2 H3 H4 Hk Bloom FilterY 1 1 1 1 1 m-bit Array 1 1 1 H1 H2 H3 H4 HkX 1 1 1 1 1 m-bit Array 1 1 1 match H1 H2 H3 H4 HkW 1 1 1 1 1 m-bit Array 1 1 1 Match (false positive) H1 H2 H3 H4 Hk n : number of messages to be stored  k : number of hash functions  m : the size of the bit-array (memory)  The false positive probability f = (½)k" The optimal value of hash functions, k, is k = ln2 × m/n = 0.693 × m/n" Key Point is that false positive probability decreases exponentially with linear increase in number of hash functions Y 1 1 1 1 1 m-bit Array 1 1 1 H1 H2 H3 H4 Hk10101110110110110110100010110111 Destination IP address 1 2 3 4 21 24 20 25 32 0* 3 1* 4 01* 6 10* 13 11* 22 010* 7 011* 12 101* 56 0010* 4 1001* 5 1010* 13 1011011010100101001111111111111* 7 10110110101010111101001111111111 5 11011110111101010111111111111111 13 prefix Next hop10101110110110110110100010110111 Destination IP address 0* 3 101* 56 0010* 4 10110110101010111101001111111111 5 11011110111101010111111111111111 13 01* 6 1010* 13 011* 12 010* 7 1011011010100101001111111111111* 7 1001* 5 11* 22 10* 13 1* 4 Prefix Next hop Hash Table 21 24 20 25 32 1 2 3 410101110110110110110100010110111 Destination IP address 0* 3 101* 56 0010* 4 10110110101010111101001111111111 5 11011110111101010111111111111111 13 01* 6 1010* 13 011* 12 010* 7 1011011010100101001111111111111* 7 1001* 5 11* 22 10* 13 1* 4 Prefix Next hop Hash Table10101110110110110110100010110111 Destination IP address 0* 3 101* 56 0010* 4 10110110101010111101001111111111 5 11011110111101010111111111111111 13 01* 6 1010* 13 011* 12 010* 7 1011011010100101001111111111111* 7 1001* 5 11* 22 10* 13 1* 4 Prefix Next hop Hash Table Hash FunctionHash Table Interface Bloom filters Destination IP address Next Hop Priority Encoder Prefix Next Hop Hash Table On an average, one Bloom filter makes f false hash probes per lookup  B Bloom filters make Bf false hash probes  One additional true hash probe required for route lookup  Expected hash probes per lookup Eexp ≤ Bf + 1  Worst case hash probes per lookup Eworst = B + 1! Uniform false positive probability for all the Bloom filters required  Same number of hash functions in all Bloom filters  Hence,  Thus, Prefix


View Full Document

Purdue CS 63600 - IP prefix look ups

Download IP prefix look ups
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view IP prefix look ups and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view IP prefix look ups 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?