The Study Of Routing Lookup Algorithms For Prototype System Of Network Processor

This thesis studies Routing lookup algorithms,one of the key technologies of the network processor. The study is one part of the 863 projects "The design and prototype of a network processor chip".With the development of optical fiber communications, One of the main obstacles restricting the performance of network processors is that the growth rate of speed of accessing memories could not keep pace with that of link speed according Moore's Law.Routing lookup and packet classification functions of network processors need accessing memory. Their performances are subject to restrictions of memories'access time. Therefore, the study of routing lookup algorithm to improve speed of routing lookup is the key to further enhance performance of network processorsThe thesis presents a detailed analysis of the existing high-speed routing algorithms and points out the advantages and disadvantages of these algorithms and discusses the hardwre implementation of these algorithms.Traditional routing lookup algorithms generally finds the longest matching prefix in two step: At first it identifies all prefixs that matching the IP address and then selects the longest length in these prefixs.Therefore it needs to access memory to get prefix value for matching the IP address.This thesis adopts a different thinking from the traditional route lookup algorithm.Among in all prefixs matched, only the longest prefix matching is necessary.Therefore, we only needs to determine the length of longest matching prefix.According to the thought, this thesis proposes a routing lookup algorithm of bit map trie on length flag(BMTLF).The BMTLF routing lookup algorithm bulids an length Flag that recording the length of the longest matching prefix length in node for avoiding prefix value matching in internal node. The BMTLF routing lookup algorithm uses some simple flag bits which means a prefix matching in a corresponding length and check these bits to determine the longest matching prefix only in routing search terminating nodes.This thesis simulates BMTLF routing algorithm in software and the performance of the BMTLF routing algorithm is evaluated.As for results , BMTLF routing lookup algorithm has obvious advantages in the memory utilization and increases speed of routing lookup to a certain extent.Comparing to multi-bit Trie, the BMTLF route lookup algorithm to decreases the complexity of storage, access time from O (2 kNM / k )to O ( NW / k ). Although the BMTLF route lookup algorithm uses the routing table compression methods, but it has no increasing in the complexity of routing update operation..At the same time, it avoids the proliferation of prefixes update.This thesis also implementes the BMTLF routing lookup algorithm in the prototype network processor.As for the problems of rearranging during routing table updating and high power consuming when using TCAMs, this thesis presents an implementation scheme of ordering-free and low-power TCAM. A new memory management algorithm which is very simple to operate by using programmable pointer is put forward., The algorithm can can effectively reduce the storage debris.