Study On Packet Forwarding Engine For High Speed Router

With the development of optical communication, the transport speed of links is increased rapidly, but the capacity of router legs behind it, the main cause is the difficulty of route lookup. Route lookup is to find the next hop for pakects based on routing table. With the rapid grouth of Internet, the routing table blows up, and decreases the route lookup speed and demand more router memory space. On the other hand, because of the complex structure of routing table, it is necessary to use the longest-prefix match algorithm. But determining the longest matching prefix involves not only comparing the bit pattern itself, but also finding the appropriate length, called searching in two dimensions. Therefore, the study of route lookup is very important, but difficult. Many software and hardware solutions to the route lookup problem have been published recently. However, there still exist a lot of unsolved problems. A few examples are listed as follows: (1) how to propose the more efficient algorithm with fast updates? (2) Some hardware algorithms are fast, cost-effective and simple to manage. However, there are drawbacks, such as high power consumption and slow route update. (3) With the deployment of IPv6, the route lookup algorithm should be suited for it, etc. In order to solve some problems above, the research project "Study on Packet Forwarding Engine for High Speed Router" is proposed. Several IP-address lookup algorithms are presented and deeply studied in this dissertation. On the base of the inclusion relation between prefixes in routing tables, the prefixes are categorized as: Standalone prefixes, Root prefixes, Sub-prefixes. The prefixes in routing tables can be represented as a data structure--Trie, every prefix has the corresponding node in the Trie. There is the only one path from root to each node (prefix). Then the Level of prefixes is defined, and the structure of routing tables is proposed. The routing tables form backbone routers are analyzed, it is found that there is the fixed ratio of the prefixes between Levels, the maximum of the Level is far less than the theoretic value, and there are less prefixes that match with an IP address. On study of the impaction of the IP-address distribution on the growth and structure of the routing tables, it is found that the policies of IP-address distribution have the impaction on Standalone and Root prefixes, no on Sub-specific prefixes, one of the cause of the growth of routing table is due to the behavior that the users distribute the fragmented prefixes, and the difficulty of route lookup is due to the Sub-prefixes. Based on the Level of prefixes in routing table, a new route-lookup algorithm is proposed. The routing table is partitioned into some part tables by the Level of prefixes. There is no intersection between the part tables, and there is no more than one prefix in each part table that matches with an IP address. The exact match algorithm can be used in each part table for route lookup, then the longest-match prefixes is seclected. A new parallel algorithm is proposed based on the partitioning technology. The search complexity is O(1), the route update is more efficient than the existing algorithms. Based on the characteristic of the TCAM-based forwarding engine, a new scheme of route update is proposed. TCAM have been emerging as a promising device in building a high-speed forwarding engine, but it is necessary to move the prefixes for inserting a new prefix, because all prefixes are sorted in TCAM. The prefixes in routing table are partitioned by the Level of prefixes, and stored in TCAM with free space between Levels. The number of memory movement per update depends on the sequence of the new-inserted prefixes, instead of the initial prefixes in routing table. In worst case, the inserting complexity is O(W), W is the number of parent prefixes. For the real route update traces, the average number of movements is less than 0.01. Further, when compared with the existing algorithm, in the average case, our algorithm shows a 90% reduction in movement overheads. A new architecture is proposed to reduce the power consumption of TCAM based on the bursty access patterns. A TCAM searches a destination IP-address against all prefixes in the routing table in parallel. It is fast, cost-effective and simple to manage. However, a major drawback of TCAM is its high power consumption. The high power consumption increases power supply and cooling cost, also limits the router design to fewer ports. Based on the classification of prefixes in routing table, a new algorithm is proposed to reduce the power consumption for the independently skewed access patterns and the bursty access pattern. The prefixes can be moved between layers based on the access frequency. For the real packet traces and routing tables, the average power consumption can be reduced by factors of 10. When compared with the existing, our algorithm not only reduces power comsumption, but also makes route lookup faster.