Research On Compression, Lookup And Incremental Update Techniques Of Backbone Routing Tables

With the fast development of Internet, the size of backbone routing table maintainsa rapid growth, which puts great pressure on routing table storage, and one effectivesolution is routing table compression. Meanwhile, the link rate of backbone network hasbeen constantly growing, which makes routing lookup a challenging problem. Inaddition, the update messages become more frequent and bursty due to theever-increasing dynamic changes on network topologies and new emergingfunctionalities of the Internet. Consequently, a system which performs routing tablecompression or fast routing lookup must be able to operate fast incremental update.Routing compression, lookup and incremental update is profoundly studied in this paper,and our main contributions lie in the following four aspects:(1) With regard to the routing table storage problem, we propose two sub-optimalalgorithms based on EAR: EAR-fast and EAR-slow, which preserve the structureinformation attached in a single compressed tree to reduce the need for secondarystorage, achieving long recompression interval while approaching the optimalcompression ratio. With regard to the prefixes overlap problem, we propose ONRTCalgorithm to compute an equivalent routing table with a minimal number of prefixesunder the constraint that all the prefixes are not overlapped. With regard to themathematical analyses, we propose a universal mathematical method based on theGroup theory which can be used to prove the correctness of all the routing compressionand lookup algorithms.Existing algorithms often sacrifice the performance of fast incremental updatewhen pursuing high table compression ratio or fast routing lookup, one solution whichcan gracefully handle the three problems simultaneously has not been proposed. Giventhe routers in different ranks have the different performance requirements, threesolutions are proposed to be adopted in three typical scenes:(2) Scenes I: for the core routers which require ultra-fast lookup speed, and canaccommodate expensive hardware cost and power consumption, we propose a completeset of solutions—CLUE, by improving previous works and adding a novel incrementalupdate mechanism to achieve ultra-fast lookup. (3) Scenes II: for the backbone routers which require fast lookup speed, and canaccommodate relatively expensive hardware cost and power consumption, we proposeTDDBF algorithm to achieve one on-chip memory access per routing lookup withoutoff-chip lookup operations by dividing the routing table according to next hop andprefix length.(4) Scenes III: Some routers require relatively fast lookup speed, but cannotaccommodate expensive hardware cost and power consumption, and thus want to adoptsophisticated software algorithm which unfortunately cannot operate fast update. Wepropose an ultra-fast universal incremental update algorithm by picking out thoseupdating nodes which would have produced domino effect.These three critical techniques of routers are of great importance to the design ofhigh performance routers and the future Internet.