Research On Table Lookup In Content Centric Networking

CCN(Content-centric Networking) is proposed recently as a clean-slate network architecture for future Internet, which no longer concentrates on “where” the information is located, but “what” the information is needed. Data itself becomes the key element of the internet structure in CCN. CCN fundamentally resolves the traditional issues like running out of IP address, security and mobility. Research on its system structure and related technology has received great attention.Table lookup is one of the main topics in CCN. In CCN, the delivery of information or data is based on data’s name instead of IP. CCN’s table has about 810 items and is two orders more than that of IP route table, which makes it impossible for traditional methods like TC AM or distributed memory unit to meet the requirement of CCN. Currently, CCN lookup technology is still in its infancy with few solutions and specific algorithms, so researches about theoretical model, algorithms and engineering realization are in urgent need. The paper focus on two different tables lookup in CCN, i.e., FIB(forwarding information table) and PIT(pending interest table), and the main work can be summarized as follows:1、Binary tree used for IP prefix set is not suitable for FIB prefix set, accordingly, a new reasonable model is required. Rooted tree is introduced based on the CCN prefix set’s basic hierarchical naming property, and a rooted tree based FIB name prefix tree model is proposed. Furthermore, the model’s statistical property is pointed out with analysis of actual domain name’s characteristics.2、Existed algorithm with high memory utilization rate, like Bloom filter, has to be realized on distributed memory with limited capacity in exchange for large memory access bandwidth, which cannot meet the scale requirement of FIB. Considering the FIB property, a load balancing fast searching algorithm named EMA-NPMA is proposed, where large amount of the longest match of FIB can be accomplished through only one access to the mass storage unit. Its adjusting success rate theorem and arbitrary space proportion theoretical equation are given, then estimation of false positive rate and throughput are given. Theoretical analysis and simulations show that the algorithm perfectly meets the both requirements in space and time at the cost of certain false positive rate. O nly about ten bits are needed for each item and most prefix searching can be accomplished by accessing the storage only once. Take RLDRAM with 1.25 G memory for example, the algorithm can accomplish 100 M items longest match at matching rate of about 60 M times per second with less than 5% false positive rate.3、Perfect hash based on d- left has a good storage utilization rate, however, it needs d searching times for each item, which leads to a low throughput rate. A n indexed hash bucket is proposed based on minimum perfect hash function(MPHF). Analysis shows that d-left can be modeled as a hash bucket which can accommodate more conflict items. Accordingly, a design method of virtual hash bucket is given. Via the proposed index mechanism, an query can be determined the sub-table number of d, then only one access to this sub-table is needed. Analysis and simulations show that the algorithm has to access to the storage only once at the cost of about 10 bits for each item. O ff-chip mass storage unit can be exploited for super large scale hash table like CCN prefix set.4、MPHF is suitable for static item set application scenario, while its updating issue for dynamic data set cannot be neglected. Therefore, MPHF’s updating efficiency is mathematical modeled and theoretical analyzed, the theorem of average moving time when adding an item is proposed. Considering the theorem, the address mapping table is proposed to realize no-moving updating.5、PIT is an important characteristic of CCN. PIT’s selecting timeout aging and one-by-one updating mechanism greatly increases the difficulty of table searching. Different processing requirements of different PIT traffic are summarized, and an operational model for PIT searching engine is proposed to quantitatively describe the throughput requirement of searching engine under different PIT traffic distribution.6、Scheduled scanning aging method has a high requirement on storage bandwidth, while software maintenance aging method has poor real time performance. Bloom filter is suitable for PIT searching considering its large table scale and variable length searching keys. Improved algorithm named A2-PIT is proposed based on Bloom filter double cache aging mechanism. At a little precision cost, it can realize high efficient selective timeout aging without extra scanning bandwidth and communication cost.7、The worst case of PIT searching happens when all the packets in the link are new interest packets, which are all no-matching items of Bloom filter. A searching accelerating control method for Bloom filter is proposed based on the research of characteristics of Bloom filter with no- matching item. It can greatly increase the throughput at the worst case with a little cost of main processing unit’s logical resource, and the packet forwarding rate is about 1.5 times of the original one.