Expediating IP Lookups with Reduced Power via TBM and SST Supernode Caching Export

@article{citeulike:6049228, abstract = {In this paper, we propose a novel supernode caching scheme to reduce IP lookup latencies and energy consumption in network processors. In stead of using an expensive TCAM based scheme, we implement a set associative SRAM based cache. We use two different algorithms, tree bitmap (TBM) and shape shifting trie (SST), to organize an IP routing table as a supernode tree composed of a group of supernodes. We add a small supernode cache in-between the processor and the low level memory containing the IP routing table in a tree structure. The supernode cache stores recently visited supernodes of the longest matched prefixes in the IP routing tree. A supernode hitting in the cache reduces the number of accesses to the low level memory, leading to a fast IP lookup. According to our simulations, up to 72\% memory accesses can be avoided by a 128KB TBM supernode cache for the selected three trace files, and up to 78\% memory accesses can be reduced while using a same size of SST supernode cache. Average TBM and SST supernode cache miss ratios are as low as 4\% and 7\% respectively. Compared to a TCAM with the same size, the TBM and SST supernode caches can both reduce 77\% of energy consumption.}, author = {Zhang, Ying and Peng, Lu and Lu, Wencheng and Duan, Lide and Rai, Suresh}, citeulike-article-id = {6049228}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.comcom.2009.10.006}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0140366409002643}, day = {27}, doi = {10.1016/j.comcom.2009.10.006}, issn = {01403664}, journal = {Computer Communications}, month = {October}, posted-at = {2009-10-31 17:10:06}, title = {Expediating IP Lookups with Reduced Power via TBM and SST Supernode Caching}, url = {http://dx.doi.org/10.1016/j.comcom.2009.10.006}, year = {2009} }

TY - JOUR ID - citeulike:6049228 L3 - citeulike-article-id:6049228 N2 - In this paper, we propose a novel supernode caching scheme to reduce IP lookup latencies and energy consumption in network processors. In stead of using an expensive TCAM based scheme, we implement a set associative SRAM based cache. We use two different algorithms, tree bitmap (TBM) and shape shifting trie (SST), to organize an IP routing table as a supernode tree composed of a group of supernodes. We add a small supernode cache in-between the processor and the low level memory containing the IP routing table in a tree structure. The supernode cache stores recently visited supernodes of the longest matched prefixes in the IP routing tree. A supernode hitting in the cache reduces the number of accesses to the low level memory, leading to a fast IP lookup. According to our simulations, up to 72% memory accesses can be avoided by a 128KB TBM supernode cache for the selected three trace files, and up to 78% memory accesses can be reduced while using a same size of SST supernode cache. Average TBM and SST supernode cache miss ratios are as low as 4% and 7% respectively. Compared to a TCAM with the same size, the TBM and SST supernode caches can both reduce 77% of energy consumption. JF - Computer Communications SN - 01403664 TI - Expediating IP Lookups with Reduced Power via TBM and SST Supernode Caching AU - Zhang, Ying AU - Peng, Lu AU - Lu, Wencheng AU - Duan, Lide AU - Rai, Suresh PY - 2009/10/27/ UR - http://dx.doi.org/10.1016/j.comcom.2009.10.006 ER -