Resrarch On Routing Lookup Algorithm For Named Data Network

As the core of the Internet structure design, IP packet switching has been popular for decades. The initial goal of network interconnection is to realize the sharing of hardware resources. However, with the rapid development of technology and the explosive increase of information, information sharing has become the main goal, and the hardware is becoming less important. Named data network as a new network model, the purpose is to meet the needs of the user's fast and convenient access to Internet content.Named data network realize the route search and forwarding through the contents of the name. Compared with the IP network routing method, the name lookup has some different characteristics. Such as the name structure with variable length and hierarchical structure, and 2~3 orders of magnitude difference in routing table size, and the routing update which is caused by the frequent release and delete operation. These characteristics make fast name routing lookup algorithm become an important and difficult task. In order to solve this problem, this paper improves the structure and algorithm of the name lookup by combining with the characteristics of named data network.Firstly, this paper studied the three commonly used structures like search tree, hash table and bloom filter in name routing lookup algorithm. Combined with the characteristics of the name hierarchy, this paper designs a routing algorithm based on hash search tree, which in view of the problem that the search tree storage cost is too large, and the hash table is collision and does not meet the longest prefix matching. This method calculates hash value from word components rather than the entire name by the hash function, which is suitable for the longest prefix match. At the same time, each layer of word components design hash function alone can guarantee control the hash collision in a low range. Then the state transfer of the tree is determined not passed through the word element but by the hash value, so that the search efficiency is improved. In addition, the hash value will occupy less storage space compared with name element, thereby reducing the structure of space overhead. What's more, the hash computation can be advance processed, and the name lookup is a parallel structure. Experimental results show that the structure can effectively improve the space efficiency compare with search tree and improve the search efficiency.In order to solve the problems of the deep level of the search tree structure and the low search efficiency which are caused by the variable length of the name. This paper designs a mixed data structure combined with search tree and bloom filter. Taking into account the named data network name hierarchy and variable-length structure in the algorithm, a complete name is divided into two parts of treatment: the front part is fixed length search tree segment, and the rear part is the bloom filter segment with variable length. Then we discussed the different hierarchical effects on the efficiency of the algorithm, and an optimal hierarchical partition is obtained. Experimental results show that the structure has a good performance in terms of storage cost and search speed.