| The forwarding process key technologies, IP routing lookup and flow forwarding/switching, which are used in NGI (Next Generation Internet) high-performance routers are studied in this paper. There are two conclusions extracted from the relative previous routing lookup algorithms by analyzing their performance. The first one is that no existent algorithms suit NGI high-performance routers to forward IPv6 packets at wire speed. The second one is that the NGI high-performance routers' routing lookups should be multipartite and TCAM-based. The two conclusions are the basic principles of the main reseach work in this paper.Algorithm based on binary-search on Trie (BSTrie) integrating the advantages of the algorithms based on prefix-length binary-search and that based on Trie is researched. Different from the bit-by-bit matching algorithms basd on Radix Trie, or the algorithms based on prefix-length binary-search, it makes the IP destination address match the Trie using binary-search method. And it uses parts of the destination IP address as index to avoid Hash functions. Its implementation scheme for IPv4 and for IPv6 is discussed. Its routing lookup speed and the entry update speed of forwarding tables are suitable for OC-48 (2.5Gbps) ports.Algorithm based on prefix-range binary-search (BSPR) and its two groups of implementation schemes are given. The first group consists of BSPR-based TCAM IPv4 routing lookup pipeline, BSPR-based TCAM IPv6 routing lookup pipeline, and BSPR-based TCAM IPv4/IPv6 dual-stack routing lookup pipeline. They use comparators and store hole forwarding table in each step of TCAM. By storing half of the forwarding table, comparators are avoided and TCAM cost is reduced. HS-BSPR-based TCAM IPv4 routing lookup pipeline, HS-BSPR-based TCAM IPv6 routing lookup pipeline, and HS-BSPR-based TCAM IPv4/IPv6 dual-stack routing lookup pipeline are proposed to compose the second group.Algorithm based on prefix-range quaternary-search is provided. Via prefix-expansion, QSPE-based TCAM IPv4 routing lookup pipeline, QSPE-based TCAM IPv6 routing lookup pipeline, and QSPE-based TCAM IPv4/IPv6 dual-stack routing lookup pipeline are created. With BSPR following QSPR, QBSPR-based TCAM IPv4 routing lookup pipeline, QBSPR-based TCAM IPv6 routing lookup pipeline, and QBSPR-based TCAM IPv4/IPv6dual-stack routing lookup pipeline are constructed.Different from those algorithms based on prefix-length or single stage TCAM, the two routing lookup algorithms, BSPR and QSPR are based on prefix-range and implemented by multi-step TCAM pipelining. Entry sorting is not needed any more in spite of TCAMs using. One IPv6 lookup or one IPv6 forwading table entry updating can be completed within one 2-clock-cycle. The lookup pipelining is interrupted only once per entry updating. They achieve OC-768 (40Gbps) interfaces' wire-speed forwarding and satisfy IPv4 core routers, IPv6 core routers and IPv4/IPv6 dual-stack core routers.Virtual-packet concept and Virtual-packet switching (VPS) mechanism are proposed. By adding adjacent indicators to the tranditional IP packet, VPS supports not only the sporadic packets forwarding but also high-speed switching of UDP or TCP packets flows, such as the transmission of real-time audio and video.
|
PDF Full Text Request