CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 5: IP prefix lookups 1 Major tasks ◦ IP lookup & classification ◦ Switching ◦ Queuing  Parameters of problem ◦ 8 ns / packet at OC-768 ◦ 320ns / packet at 1 Gbps ◦ Up to 1,000,000 prefixes ◦ Updates every 10 ms ◦ Caching not enough CS 636 Internetworking 2CS 636 Internetworking  The entry with the longest (most specific) IP prefix matching the destination address decides which interface to send packet to 3CS 636 Internetworking  Avoiding lookup (tag switching)  Hardware solution  Algorithmic solutions ◦ Unibit tries ◦ Multibit tries ◦ Level-compressed tries ◦ Lulea compressed tries ◦ -- Next lecture -- ◦ Tree bitmap ◦ Binary search on prefix lengths ◦ Binary search on ranges (for solving range matching) ◦ Specialized memory allocation solution 4CS 636 Internetworking  ATM: forward based on virtual circuit index initialized at connection setup time – problems: extra roundtrip, drastic changes  Tag switching: add to each packet index of matching entry in next hop’s forwarding table – problems: hierarchy boundaries, changes  IP switching: lazily setup virtual circuits for large flows and pass VCI to previous hop – problems: as in tag switching + short flows 5CS 636 Internetworking  Similar to ATM link local VCIs, but one index per destination (not per connection) 6CS 636 Internetworking  Distance vector routing proto. passes indices  No circuit setup overhead 7CS 636 Internetworking  MPLS ◦ Extends tag switching by allowing a stack of tags ◦ Implemented by ~ every router today  IP switching ◦ Slow path does normal forwarding ◦ When processor decides it is worth switching it sets up an ATM VCI and passes to previous hop ◦ The idea is dead 8CS 636 Internetworking  Avoiding lookup (tag switching)  Hardware solution – use TCAMs  Algorithmic solutions ◦ Unibit tries ◦ Multibit tries ◦ Level-compressed tries ◦ Lulea compressed tries ◦ -- Next lecture -- ◦ Tree bitmap ◦ Binary search on prefix lengths ◦ Binary search on ranges (for solving range matching) ◦ Specialized memory allocation solution 9CS 636 Internetworking 10 P1 0* P2 1* P3 100* P4 1000* P5 100000* P6 101* P7 110* P8 11001* P9 111* Uni-bit trie 0 P1 1 P2 0 1 0 P7 1 P9 0 P3 1 P6 0 P4 1 0 1 0 P5 1 0 1 0 1 P8 Input 11000010 Longest matching prefix P2 P7 Consider multiple bits at a time  Faster lookup  Problem: ◦ Prefixes are not aligned with stride boundary  Solution: ◦ Controlled prefix expansion CS 636 Internetworking 11CS 636 Internetworking 12 P1 0* P2 1* P3 100* P4 1000* P5 100000* P6 101* P7 110* P8 11001* P9 111* Old routing table P1 000* P1 001* P1 010* P1 011* P2 100* P2 101* P2 110* P2 111* P3 100* P4 100000* P4 100001* P4 100010* P4 100011* P5 100000* P6 101* P7 110* P8 110010* P8 110011* P9 111* Controlled prefix expansion with stride 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* New routing tableCS 636 Internetworking 13 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 14 Leaf pushing reduces memory usage but increases update time 000 P1 001 P1 010 P1 011 P1 100 P3 3 101 P5 110 P7 2 111 P9 000 P5 001 P4 010 P4 011 P4 100 101 110 111 00 01 P8 10 11 Multi-bit trie with variable stride Given a maximum trie height h and a routing table of size n dynamic programming algorithm computes optimal variable stride trie in O(nw2h) • Reduces storage significantly (from about 2MBytes to 423KBytes for MAE East database) • Gupta McKeown a special case of variable strides.CS 636 Internetworking 15 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* 000 P1 001 P1 010 P1 011 P1 100 101 P5 110 111 P9 P1 P5 P9 000 1 001 0 010 0 011 0 100 1 101 1 110 1 111 1 Lulea bitmap compression Repeating entries are stored only once in the compressed array. An auxiliary bitmap is needed to find the right entry in the compressed node. It stores a 0 for positions that do not differ from the previous one. Reduces storage to about 160KBytes for MAE East Compressed nodeCS 636 Internetworking 16 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 P7CS 636 Internetworking  Tree bitmap  Binary search on prefix lengths  Binary search on ranges (for solving range matching)  Specialized memory allocation solution 17CS 636 Internetworking 18 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