Aligned prefix caching based on singleton information

In recent years, the lookup speed of Content Address Memory (CAM), a hardware solution for IP caching, is greatly improved. CAM is a good candidate for lightweight routing-lookup modules on input line-cards in parallelism router architecture. In this paper, we propose aligned-ancestor poisoning (AAP) and aligned-prefix caching (APC) to enhance IP caching. In particular, AAP is a marking scheme for tree-based routing tables. Routing-lookup results thus carry additional singleton information, which indicates whether predefined aligned prefixes are cacheable or not. APC is a caching scheme to utilize such routing-lookup results. To properly configure AAP and APC, we further investigate the properties of referred singleton prefixes. Our trace-driven simulations show that the required cache size can be significantly reduced, compared with the conventional destination caching scheme.