Patent ID: 8775727

Claim:
A method of processing lookup requests by a system comprising a lookup engine coupled to a lookup table having a plurality of entries, the method comprising: receiving, by the lookup engine, a plurality of lookup requests, each lookup request comprising (i) a requested key and (ii) a speculative add requestor; iteratively, for each one of the plurality of lookup requests: searching, by the lookup engine, each of the plurality of entries of the lookup table for an entry having a key matching the requested key of the lookup request; if the lookup table includes an entry having a key matching the requested key: sending, by the lookup engine to a corresponding control processor, a hit indication corresponding to the lookup request; if the lookup table does not include an entry having a key matching the requested key: sending, by the lookup engine to a corresponding control processor, a miss indication corresponding to the lookup request; if the speculative add requestor is set, speculatively adding, by the lookup engine, the requested key to a free entry in the lookup table; wherein speculatively added keys are searchable in the lookup table for subsequent ones of the plurality of lookup requests, thereby maintaining data coherency of the lookup table without (i) creating duplicate key entries, (ii) comparing missed keys with each other, and (iii) stalling the lookup engine to insert missed keys.