Research Of High Performance Routing Lookup Toward The Future Internet

Born in the 1960s,the Interent has far exceeded its expectations.In today's Interent that takes TCP/IP as the core,more and more issues have been exposed in supporting ever-complicating applications and growing demands.To fundamentally address these issues,new Interent architectures come to the fore.But,no matter how the Internet reforms,its essential aim of enabling information exchange will never change,to which packet forwarding is the key component,where routing lookup plays a very important role.Routing lookup can be defined as the process of looking up the input packet toward pre-defined rules to find out the most matched rule,according to which the packet will be forwarded.Lookup acceleration,memory compres-sion,and scalability optimization have been hot topics in this area.Thus,this thesis,based on the present but looking into the future,is aimed at improving the comprehensive performance of the routing lookup engine,for TCP/IP and three representative new scenarios or architectures,namely network function virtualization(NFV),software defined networking(SDN)and named data networking(NDN).SEVEN works have been carried out.First of all,this thesis focuses on the routing lookup in TCP/IP,namely the IP address lookup(IP lookup in short).In view of the lackness of existing solutions in guaranteeing the performance of lookup and update while aiming at memory compression,this thesis goes deep into the problem and presents a parallel lookup model on basis of prefix splitting.By utilising the partial similarity among prefixes,it can compress the on-chip memory sharply,producing a reduction of up-to 90%.Besides,owing to such "splitting" not only route updates are diverged to be more targeted,but also the lookup is decomposed to support parallel processing.As a result,update performance as well as lookup speed is enhanced significantly.As for the hardware implementation of IP lookup engine,the lookup pipeline based on field-programmable gate array(FPGA)is becoming the first choice.However,balancing the memory cost among stages and the load among sub-pipelines is challenging.Existing solutions have to pay a high price to achieve an ideal balance,which limites their applications in IPv6 or large-scale routing tables.As such,this thesis proposes a memory-efficient and balanced bidirectional pipeline architecture,on basis of a series of balance optimisations.While achiev-ing the same degree of balance as exiting solutions,the proposed architecture consumes much less stages,gaining a reduction ranging from 75%to 85.7%.Besides,its significant superi-orities in comprehensive performance,in terms of pipeline latency,average memory accesses per lookup,on-chip memory efficiency,update overhead and the degree of load balance in the multi-pipeline implementation,are all clearly demonstrated in experimental evaluation.While,on the other hand,the graphics processing unit(GPU)has been shown of value in supporting high performance software lookup engines.Existing solutions have already pro-posed a fast lookup algorithm with a temporal complexity of O(1)(one memory access per lookup).However,it supports IPv4 only,and not all updates in a batch can be processed in parallel,which limits the update performance and leads to unstable lookup throughputs as well.In response,this thesis proposes a novel structure called Threaded SEgment Tree along with an efficient update mechanism,which enables completely parallel updates with redundant memory accesses eliminated.As a result,the update performance has been improved by a factor of 9.Most importantly,the proposed scheme can keep the system throughput stable(decreases by less than 4%)while that of existing solutions have declined more than a half as the update fre-quency increases.Then,this thesis seeks for further optimisations on lookup acceleration and the support to IPv6.A GPU-Accelerated Multi-bit Trie is proposed.It is cored with the multi-bit trie that enables fast IPv6 address lookup naturally,and works with an efficient cooperative update mechanism to cope with highly frequent updates.By encoding trie nodes and trimming the trie shape according to GPU's characteristics,and improving the performance via the multi-stream pipeline,the proposed scheme achieves high throughputs of 1000 Million Lookups Per Second(MLPS)and 650 MLPS on IPv4/IPv6 address lookup respectively,and can keep those throughputs even under highly frequent updates.The virtual router platform is the core infrastructure of enabling NFV,where the key chal-lenges of routing lookup are the maintenance of and the lookup on forwarding information bases(FIBs)of different logic routers.Each router instance is associated with an unique virtual ID(VID)used to identify the target FIB during lookup.Existing solutions reserve spaces for-VIDs of potential instances,which leads to low scalability and raises the bar of dynamic instance in-sertion.Besides,there is no previous work focusing on GPU-accelerated virtual routers.There-fore,this thesis designs a new structure called TailTirie for-multi-FIB lookup toward the scenario of GPU acceleration.It utilizes the finite state automata to manage VIDs,and then employs the double-array trie for memory compression.The increasing trend of memory cost is thus reduced from linear to sub-linear,and dynamic instance insertion is fully supported.What's more,it,ac-celerated by GPU,can perform IPv4/IPv6 address lookup at a rate of multi-hundreds of MLPS.while keeping the lookup latency below 100 ?s.As the core infrastructure of SDN,the OpenFlow switch manages packet rules in flow tables.Routing lookup(namely flow table lookup)here requires to resolve the problem of mul-tidimensional rule matching.Existing solutions are difficult to keep both high matching speed and high memory efficiency when the number of rules or the number of fileds increase.In view of this,this thesis firstly establishes the theory of iteratively dimension-reducing based on rule projecting,and then presnets a novel Iterative Hash Table that achieves a temporal complex-ity of O(d)(where d denotes the number of fileds)and a spatial complexity of O(n)(where n denotes the number of rules),when performing multidimensional rule matching.According to the evaluation results,the proposed scheme gains a compression up-to 80%on memory foot-print compared with existing hierarchical-trie based solutions.Meanwhile,the matching speed is enhanced by at least 5 times.In NDN's forwarding process,though three name tables along with two kinds of packets are involved,the fundamental problem is name lookup.Existing solutions utilize GPU to sat-isfy the requirement of line-speed name lookup,but the latency resulted by data transfer and batch processing is unignorable.By contrast,this thesis switches the focus to FPGA and makes the.first-attempt to accelerate NDN name lookup via the FPGA-based pipeline.A novel ar-chitecture called Hierarchical Aligned Transition Arrays(HATA)is proposed.It take the name trie as the core,which is transformed into a series of state transitions to improve the memory efficiency.Then,a multi-candidates-and-parallel-validating mechanism is designed to com-press the memory footprint further.At last,the name trie,with the height bounded based on the statistic on name lengths,produces a linear pipeline through a level-by-level mapping.As clearly demonstrated in evaluation results,HATA reduces the memory footprint by more than 90%,compared with the referred GPU solution.Most importantly,the lookup latency is almost 3 orders of magnitude lower,while keeping the lookup throughput at the same level(a little bit higher in fact).In a word,this thesis firstly carried out a series of researches on IP lookup,ranging from model optimization,balanced pipeline architecture construction toward FPGA platform,to com-pact structure and efficient mechanism design for GPU acceleration.Meanwhile,key chal-lenges of routing lookup in three emerging scenarios are studied in detail and addressed with novel schemes.Apart from improvements on lookup engines' comprehensive performance in all referred scenarios,some initial yet effective attempts has made legible achievements,and highlighted several directions for future research as well.