CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 4: Exact Match Lookups 1CS 636 Internetworking Spring 2009  Definition: given a key, retrieve state associated with it (lookup) under tight timing constraint (insertion might take longer)  Typical solutions: search trees, hash tables  Major use: per port tables of MAC addresses in Ethernet bridges  Chapter structured around 3 challenges that lead to bridges 2 Three main challenges ◦ Limited bandwidth—as n grows, bw 0 ◦ Distance ( < 1.5 Km)  Obvious question: ◦ Can we extend ethernet to arbitrarily size ?  Possible solutions: ◦ Physical layer repeaters not enough ◦ Routers were too slow at that time ◦ Too many protocols (IBM SNA, Xerox SNS) CS 636 Internetworking Spring 2009 3CS 636 Internetworking Spring 2009  Mark Kempf  3 (logical) steps ◦ Packet repeater  just repeat physical bits ◦ Filtering repeater  Table indicating positions ◦ Learning bridge  Learn the positions passively 4 BRIDGE C B A A CCS 636 Internetworking Spring 2009  Scenario ◦ Let AB 1000 pkts  These packets are buffered in the bridge to be examined ◦ Let AC 500 pkts  Will be dropped if buffer size is only 500 pkts ◦ Unless AB burst can be handled in the time they arrive 5 BRIDGE C B A A CCS 636 Internetworking Spring 2009  Without wire speed forwarding can lose packets if local traffic on one Ethernet is high  Budget 51.2 μs per frame (2 ports  25.6"μs)  Impossible! Many thought !"6 Ethernet chip Packet memory + lookup memory Ethernet chip Lookup engine Processor (68000) Ethernet 1 Ethernet 2CS 636 Internetworking Spring 2009  Architecture: 4-port cheap DRAM with cycle time of 100 ns. Bus parallelism, memory bandwidth, page mode  Data copying: Ethernet chips used DMA, packets copied from one port to the other by flipping pointers  Control overhead: Interrupt overhead minimized by processor polling  Lookups: Went through cautionary questions 7CS 636 Internetworking Spring 2009  Q1 Worth improving performance? Yes  Q2 Really a bottleneck? Software too slow  Q3 Impact on system? Allows wire speed  Q4 Initial analysis shows benefits? Logic in hardware, log2 8000 DRAM reads = 1.3 μs  Q5 Worth adding hardware? Cheap  Q7 Do prototypes confirm promise? Yes  Q8 Sensitive to environment changes? No"8 Binary search does not scale to FDDI speeds (100 Mbps) ◦ 64K database requires 16 accesses ◦ With 100ns DRAM access  3.2us  FDDI min packet size ~ 40bytes requires 3.2us  What about SRAM ? ◦ Too expensive ◦ Does not easily scale to 1Gbps.  What we need is reduce # of lookups. CS 636 Internetworking Spring 2009 9CS 636 Internetworking Spring 2009  Gigaswitch 32 x 100Mbps FDDI ports  Use hashing instead of search tree ◦ Avoid worst case by using perfect hashing to avoid too many collisions – A(x)*M(x) mod G(x) where G(x) = X48+X36+X25+X10+1, and A(x) is address, M(x) is a non-zero multiplier  Bottom 16 bits index into 64K hash table ◦ Remainint 32bits used to disambiguate entries 10 Non-deterministic ◦ Do not provide worst case guarantees ◦ Can restrict to 3-4 memory accesses, but update complexity even worse  Alternate approach ◦ Hardware pipelining of a binary search tree CS 636 Internetworking Spring 2009 11CS 636 Internetworking Spring 2009  Pipelined lookup in binary search trees 12CS 636 Internetworking IP prefix lookups 13 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 14CS 636 Internetworking  The entry with the longest (most specific) IP prefix matching the destination address decides which interface to send packet to 15CS 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 16CS 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 17CS 636 Internetworking  Similar to ATM link local VCIs, but one index per destination (not per connection) 18CS 636 Internetworking  Distance vector routing proto. passes indices  No circuit setup overhead 19CS 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