Research And Design Of SDN Query Structure Based On Bloom Filter And Refined Trie Algorithms

With the rapid development of network technology,the Internet has become one of indispensable parts of people's life.With the development of optical communication technology,the link transmission rate is no longer the performance bottleneck of network technology.Network lookup and forwarding performance has become the main constraint of the development of the Internet.The next generation Software Defined Networking,whose main feature is separating the structure to control plane and data plane,is more convenient to manage and control the network.The ability of software defined network makes the detection and process of packets in a finer granularity,which enhances the flexibility of network device so as to deal with packets and promote the virtualization of network.In the core protocol OpenFlow of SDN,the search process is based on the flow table,and based on the multi protocols and multi fields table entries.Contents of the paper covers:first of all,the research and analysis of the existing high speed search algorithm is carried out.Combining the forms and requirements of Trie method and flow table of OpenFlow based on the longest prefix matching,we proposed an exact search method based on Bloom filter and refined Trie algorithms.The general OpenFlow switch uses the TCAM to achieve the lookup,but TCAM brings such drawbacks like power and cost to system design.Bloom filter is a kind of saving resource and simple and efficient search structure,its rich derivative structure can be applied to many kinds of scenes to complete different functions.The method proposed in this paper consists of two parts:the on-chip Bloom filter structure and the routing table saved on off-chip Trie.Bloom filter is designed to reduce the number of off-chip accesses a successful search required.By reasonable design,the Bloom filter can overcome the false probability and reduce the number of off-chip accesses up to one.The combination of counting Bloom filter and Trie algorithm can not only improve the search efficiency,but can also realize the function of dynamic update.And the combination of parallel Bloom filter and Trie algorithm can complete the multi field searching tasks.According to the form of OpenFlow flow table and the characteristics of SRAM,this paper designs a multi field look-up table structure which is suitable for the flow table lookup,and completes the design and verification of SRAM control and read/write module.In this paper,the structure and main function modules of SDN switch system based on FPGA Xilinx chip is designed,and the detailed analysis and verification are carried out,which can provide reference for the implementation of the study of SDN in the future.