IP Lookup Some subtle concurrency issues Arvind Computer Science Artificial Intelligence Lab Massachusetts Institute of Technology February 22 2011 http csg csail mit edu 6 375 L06 1 IP Lookup block in a router LC Line Card LC Packet Processor SRAM lookup table IP Lookup Arbitration Control Processor Switch Queue Manager Exit functions A packet is routed based on the Longest Prefix Match LPM of it s IP address with entries in a routing table Line rate and the order of arrival must be maintained February 22 2011 LC LC line rate 15Mpps for 10GE http csg csail mit edu 6 375 L06 2 1 F F A F B F A A F 10 18 200 C 3 E A 7 5 F 14 C 7 5 E F IP address Result F 10 255 F M Ref 7 13 7 3 F 2 10 18 201 5 F 3 5 13 7 2 E 10 18 200 7 C 1 4 18 200 5 F D 10 18 200 5 D B F 7 14 7 3 0 A 7 14 Sparse tree representation C 7 14 7 2 February 22 2011 L06 3 http csg csail mit edu 6 375 0 28 1 0 0 28 1 1 int lpm IPA ipa 3 memory lookups int p Level 1 16 bits p RAM ipa 31 16 if isLeaf p return value p Level 2 8 bits p RAM ptr p ipa 15 8 if isLeaf p return value p Level 3 8 bits p RAM ptr p ipa 7 0 return value p must be a leaf C version of LPM 216 1 Memory latency 30ns to 40ns Must process a packet every 1 15 s or 67 ns Must sustain 3 memory dependent lookups in 67 ns February 22 2011 http csg csail mit edu 6 375 L06 4 2 Longest Prefix Match for IP lookup 3 possible implementation architectures Rigid pipeline Linear pipeline Inefficient memory usage but simple design Efficient memory usage through memory port replicator Designer s Ranking Circular pipeline Efficient memory with most complex control Which is best http csg csail mit edu 6 375 Arvind Nikhil Rosenband Dave ICCAD 2004 February 22 2011 L06 5 Circular pipeline inQ enter RAM d done outQ yes y no fifo The fifo holds the request while the memory access is in p progress g The architecture has been simplified for the sake of the lecture Otherwise a completion buffer has to be added at the exit to make sure that packets leave in order February 22 2011 http csg csail mit edu 6 375 L06 6 3 FIFO interface FIFO type t method Action enq t x enqueue an item method Action deq remove oldest entry method t first inspect oldest item endinterface n of bits needed to represent a value of type t FIFO O module n first deq q not empty rdy enq n enab rdy not full enab rdy not empty L06 7 http csg csail mit edu 6 375 February 22 2011 Ready ctr 0 ctr ctr enq deq Data Ready ctr peek req Enable Ack de eq Request Response Interface for Synchronous Memory Synch Mem Latency N Data Addr interface Mem type addrT type dataT method Action req addrT x method Action deq Making a synchronous method dataT peek component latencyinsensitive endinterface February 22 2011 http csg csail mit edu 6 375 L06 8 4 Circular Pipeline Code inQ enter RAM done rule enter True IP ip inQ first fifo ram req ip 31 16 fifo enq ip 15 0 done Is the same as isLeaf inQ deq rule recirculate True endrule TableEntry p ram peek ram deq When can enter fire IP rip fifo first if isLeaf p p outQ enq p Q q p else begin fifo enq rip 8 ram req p rip 15 8 end fifo deq endrule February 22 2011 L06 9 http csg csail mit edu 6 375 Circular Pipeline Code discussion inQ enter RAM done rule enter True IP ip inQ first fifo ram req ip 31 16 fifo enq ip 15 0 inQ deq rule recirculate True endrule TableEntry p ram peek ram deq When can recirculate IP rip fifo first fire if isLeaf p outQ enq p else begin fifo enq rip 8 ram req p rip 15 8 end fifo deq endrule February 22 2011 http csg csail mit edu 6 375 L06 10 5 Ordinary FIFO won t work but a pipeline FIFO would February 22 2011 http csg csail mit edu 6 375 L06 11 Problem solved PipelineFIFO fifo mkPipelineFIFO use a Pipeline fifo rule recirculate True TableEntry p ram peek ram deq IP rip fifo first if isLeaf p outQ enq p else begin fifo enq rip 8 ram req p rip 15 8 end fifo deq endrule February 22 2011 http csg csail mit edu 6 375 RWire has been safely encapsulated inside the Pipeline FIFO users of the fifo need not be aware of RWires L06 12 6 Dead cycles inQ enter RAM done rule enter True IP ip inQ first fifo ram req ip 31 16 assume simultaneous fifo enq ip 15 0 inQ deq enq deq is allowed endrule rule recirculate True TableEntry p ram peek ram deq Can a new IP rip fifo first request enter if isLeaf p outQ enq p the system when h an old ld one else begin is leaving fifo enq rip 8 ram req p rip 15 8 end fifo deq endrule L06 13 http csg csail mit edu 6 375 February 22 2011 The Effect of Dead Cycles yes in enter RAM done no fifo Circular Pipeline RAM takes several cycles to respond to a request Each IP request generates 1 3 RAM requests FIFO entries hold base pointer for next lookup and unprocessed part of the IP address What is the performance loss if exit and enter don t ever happen in the same cycle February 22 2011 http csg csail mit edu 6 375 L06 14 7 Scheduling conflicting rules When two rules conflict on a shared th th execute t in i resource they cannott b both the same clock The compiler produces logic that ensures that when both rules are applicable only one will fire February 22 2011 Which one source annotations L06 15 http csg csail mit edu 6 375 So is there a dead cycle inQ enter RAM done rule enter True IP ip inQ first fifo ram req ip 31 16 fifo enq ip 15 0 inQ deq endrule rule recirculate True TableEntry p ram peek ram deq IP rip fifo first In general these if isLeaf p outQ enq p two rules conflict but else l b begin i when isLeaf p fifo enq rip 8 is true there is ram req p rip 15 8 no apparent end conflict fifo deq endrule February 22 2011 http csg csail mit edu 6 375 L06 16 8 Rule Spliting rule foo True p r1 5 if p else r2 7 endrule rule fooT p r1 5 endrule rule fooF p r2 7 endrule rule fooT and fooF can …
View Full Document
Unlocking...