Research Of Lookup Algorithm And Packet Process Platform Toward High-efficiency NDN Forwarding

NDN(Named Data Networking)is a novel network architecture designed for future internet,which is aimed at replacing the traditional network based on TCP/IP.Unlike TCP/IP network that bases on IP address,NDN bases on named data,which makes NDN have better mobility,scalability and security than TCP/IP network.On the data plane of NDN,name lookup is the key factor that affects the performance of packet forwarding.However,name has complex architecture,indefinite length and no theoretical limit of length,therefore it is important to reduce the memory cost and time overhead of name lookup.At present,most existing name lookup algorithms base on single data structure,including trie tree,hash table and bloom filter.For example,LNPM(Longest Name Prefix Match)algorithm bases on hash table,uses binary search to reduce the time complexity of lookup,but has huge memory cost.However,BBS(Bloom-filter assistant Binary Search)algorithm bases on LNPM algorithm,adopts a mixed data structure combining with bloom filter and hash table,greatly reduces the cost of memory,but meanwhile increases time overhead.Therefore,based on multi-core CPU,this paper proposes a novel name lookup algorithm whose name is MBBS(Multi-core BBS),in which parallel calculation is introduced to decrease the time overhead of lookup based on BBS.Test shows that memory cost of MBBS is almost same as BBS,while the throughput of MBBS is improved by at most 100% compared to BBS.In order to evaluate the performance of algorithm more comprehensively,this paper also test the performance of MBBS and BBS when CPU is in heavy load.Test shows that MBBS can be up to 2.5 times the throughput of BBS in such an extreme case,which shows that MBBS has better stability.Furthermore,because NDN lacks support from the underlying network devices,current researches of NDN packet forwarding is mainly based on simulation.Considering this problem,this paper also implements a user-mode packet process platform.This platform is aimed at implementing system level deployment of NDN,have the ability to make packet forwarding application bypass the kernel to interact with NIC directly,and support GPU acceleration.In order to evaluate the performance of GPU acceleration in this platform,this paper deploys a packet forwarding experiment with BBS algorithm.The experimental result shows that when the threshold of batch process is 1024,the lookup time on GPU decreases about by 50% compared to CPU,while the throughput increases by at most 16%.