Fast Name-based Packet Lookup Algorithm And Implementation On Multi-cores

With the further development of Internet, the increase of Internet page visiting and people’s needs have make the existing TCP/IP based protocol network reveal many problems and maladjustment. Currently, the problems exposed include: poor expanding, poor flexibility, insecurity and so on. There are two main solutions internationally: one idea is keeping IP in subject status, not changing the host-to-host communication, such as the expansion method of IPv6; the other idea is to change the IP network architecture, such as NDN(Named Date Network). This article focuses on NDN forwarding engine design and implementation issues, as follows:1. The structure design and implementation of forwarding engine: including the research for forwarding engine structure, and accordingly PatriciaTrie tree structure and describing the relevant principles of PatriciaTrie structure. And designing methods based on that. We proposed three models: divided by bytes, divided by bit and divided by component, respectively. In this article, we also elaborate the basic design and implementation of the first two models.2. The research of forwarding engine optimization technique: further analysis of the problems that will be faced in models divided by byte and models divided by bit optimization of the basic structures and algorithms. Study and elaborate the implementation of the multi-core parallel ways in forwarding engine.3. Forwarding engine experimental analysis: For the basic structure and optimized structure of forwarding engine mentioned in this article, we test in two aspects-function and performance. In the function tests, we focus on the correctness and completeness of the structural design, and we also test the correctness of the functions of inserting, searching, deleting and updating in each module. The test of performance are make in two aspects: one is the memory usage for the models designed in this article, large-scale set of tests have been done, from which we get the memory consumption results of different models, and we compare the characteristics among the various model methods. The other aspect is about efficiency. For the inserting and searching modules, testing their time efficiency. We analyse the efficiency of different modules and the characteristics among them. Through the comprehensive comparison in several aspects in different models we get the best design of forwarding engine. The chosen model will benefit the further research of high-speed named forwarding engine, thus promote the development of the entire NDN-the next generation network architecture project.