A High Efficiency Routing Updating Algorithm Based On TCAM

TCAM(Ternary Content Addressable Memory) is a newly emerging hardware lookup technology. It can achieve high-speed routing lookup to meet the demand of the internet development. However, the high power consumption has been the restriction of the TCAM. Partitioned TCAMs and routing compression are two strategies to solve the high energy consumption of TCAM, but updating speed and updating energy of the two methods all need to be improved. Therefore, based on the rapid growth of the number of internet packets and the rapid expansion of the routing rules, this paper focus on the TCAM-based low-power routing update and routing lookup. The main work is as follows:(1)We put forward a overflow solution algorithm for the partitioned TCAMs. Partitioned TCAMs mean to divide the TCAM storage space into several sub-blocks, and each routing lookup only search one block of the sub-blocks to reduce the routing energy consumption. Due to the randomness and unexpected features of the update prefixes, update operation may concentrate in certain blocks and cause block overflow. Then forcing to the repartition of the routing table it would greatly reduce the routing speed. This paper through dynamically adjusting the TCAM storage space to avoid the sub-blocks to overflow during the update process.(2) Based on the prefixes are in descending order, we optimize the allocation of the free TCAM storage of each sub-block, which greatly improve the update speed. The prefixes stored in TCAM are in descending order according to the prefix length to meet the longest prefix matching. Therefore, the insertion and deletion operations of the routing update will cause a lot of prefix mobiles. For the partitioned TCAMs, each sub-block has a corresponding free storage space. Based on the descending order of the prefixes, we optimize the allocation of the free TCAM storage of each sub-block, which can reduce the movement of the irrelevant prefixes. Then it can improve the update speed and reduce the energy consumption.(3) Based on the large redundancy of the routing rules, this paper puts forward a routing table compaction algorithm. Generally, interfaces of the router are very less, but routing rules are tens of thousands. Therefore, the routing rules have a large compaction space. This paper deeply analyzes the redundancy form of the routing table, and puts forward a compaction algorithm which does not change the routing semantic. It can compress the routing table well, reduce the energy consumption, and can also improve the routing speed. Besides these, in order to meet the dynamical updating of the routing table, this paper proposes a updating algorithm for the compressed routing table from the prefixes insertion and deletion two aspacts.