Method and apparatus for forwarding packets by obtaining addresses of the packets using a preset forwarding information base entry

• US 8,879,555 B2
• Filed: 05/18/2011
• Issued: 11/04/2014
• Est. Priority Date: 05/26/2010
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Du, Wenhua, Hong, Rongfeng, Yi, Yi
• Primary Examiner(s): Sam, Phirin
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US13/110,694
• Publication Number:
  US 20110292943A1
• Time in Patent Office: 1,266 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

The present invention relates to the field of communication technologies, and discloses a method and an apparatus for forwarding packets to solve the problems in the prior art, namely, if a long Internet Protocol (IP) address needs to be searched for at the time of forwarding a packet, the number of Ternary Content Addressable Memories (TCAMs) need to be increased, or an external Random Access Memory (RAM) needs to be accessed for more times, which leads to a high cost and low performance. The method includes: extracting a first bit sequence from a destination address of a received packet, and using the first bit sequence as a key value; searching for a preset TCAM entry by using the key value, and obtaining an index value returned by the TCAM entry; and using the index value and a second group of bits in the destination address of the packet as conditions for searching, according to a predetermined algorithm, for a preset Forwarding Information Base (FIB) entry, and obtaining a forwarding address of the packet. The technical solution under the present invention is applicable to searching a table for an Internet Protocol version 6 (IPv6) address in a router.

Claims

1. A method for forwarding packets, comprising:

extracting a first group of bits from a destination Internet Protocol (IP) address of a received packet, wherein the first group of bits comprises a predetermined number of bits from the destination IP address;

searching a Ternary Content Addressable Memory (TCAM) for a TCAM entry that matches the predetermined number of bits from the destination IP address;

returning an index value from the TCAM entry when the TCAM entry is found that matches the predetermined number of bits;

combining the index value with a second group of bits from the destination IP address of the received packet to form a key value, wherein the second group of bits includes all bits from the destination IP address that are not included in the first group of bits; and

searching a random-access memory (RAM) for a preset Forwarding Information Base (FIB) entry according to the key value to obtain a forwarding IP address of the received packet.

2. The method for forwarding packets according to claim 1, wherein the destination IP address comprises a 128-bit IP version 6 (IPv6) address and a 16-bit Virtual Private Network (VPN) identifier.

3. The method for forwarding packets according to claim 1, further comprising:

forming a second key value that comprises all bits from the destination IP address; and

searching the RAM for the preset FIB entry according to the second key value when the TCAM entry is not found that matches the predetermined number of bits.

4. The method for forwarding packets according to claim 1, wherein searching the RAM for the preset FIB entry according to the key value comprises searching for the preset FIB entry according to the key value and a Trie algorithm.

5. The method for forwarding packets according to claim 1, wherein searching the RAM for the preset FIB entry according to the key value comprises searching for the preset FIB entry according to the key value and a B-Tree algorithm.

6. The method for forwarding packets according to claim 1, wherein the destination IP address of the received packet comprises a 128-bit IP version 6 (IPv6) address.

7. The method for forwarding packets according to claim 1, wherein the destination IP address of the received packet comprises a predetermined network identifier, and wherein the predetermined network identifier comprises a Virtual Private Network (VPN) identifier.

8. The method for forwarding packets according to claim 7, wherein the destination IP address comprises 128 bits, wherein the predetermined network identifier comprises 16 bits, and wherein a combination of the destination IP address and the predetermined network identifier comprises 144 bits.

9. The method for forwarding packets according to claim 1, wherein the destination IP address comprises a 128-bit IP version 6 (IPv6) address, wherein the predetermined number of bits comprises 64 bits or less, and wherein the index value comprises 16 bits.

10. The method for forwarding packets according to claim 9, wherein the destination IP address further comprises a 16-bit Virtual Private Network (VPN) identifier, and wherein a total number of bits in the destination IP address comprises 144 bits.

11. The method for forwarding packets according to claim 9, further comprising searching for a next-hop IP address of the destination IP address using the 128-bit IPv6 address when the TCAM entry is not found that matches the predetermined number of bits.

12. The method for forwarding data packets according to claim 1, wherein the destination IP address comprises a 128-bit IP version (IPv6) address, wherein the first group of bits comprises a first 64 bits of the 128-bit IPv6 address, wherein the second group of bits comprises a last 64 bits of the 128-bit IPv6 address, and wherein the index value comprises 16 bits.

13. A non-transitory computer readable storage medium comprising instructions, which when executed by a processor, perform steps of:

extracting a first group of bits from a destination Internet Protocol (IP) address of a received packet, wherein the first group of bits comprises a predetermined number of bits from the destination IP address;

searching a Ternary Content Addressable Memory (TCAM) for a TCAM entry that matches the predetermined number of bits from the destination IP address and receive an index value from the TCAM entry when the TCAM entry is found that matches the predetermined number of bits;

combining the index value with a second group of bits from the destination IP address of the received packet to form a key value, wherein the second group of bits includes all bits from the destination IP address that are not included in the first group of bits; and

searching a random-access memory (RAM) for a preset Forwarding Information Base (FIB) entry according to the key value to obtain a forwarding IP address of the received packet from the preset FIB entry.

14. The non-transitory computer readable storage medium according to claim 13, wherein the instructions further cause the processor to perform a step of searching for the forwarding IP address of the received packet using all bits from the destination IP address when the first search unit does not find the TCAM entry that matches the predetermined number of bits, and wherein the predetermined number of bits comprises half or less than half of the bits from the destination IP address.

15. The apparatus for forwarding data packets according to claim 13, wherein the destination IP address comprises a 128-bit IP version (IPv6) address, wherein the first group of bits comprises a first 64 bits of the 128-bit IPv6 address, wherein the second group of bits comprises a last 64 bits of the 128-bit IPv6 address, and wherein the index value comprises 16 bits.

16. A method for forwarding packets, comprising:

extracting a first group of bits from a destination Internet Protocol (IP) address of a received packet, wherein the first group of bits comprises a predetermined number of bits that is less than a total number of bits in the destination address of the received packet;

searching a Ternary Content Addressable Memory (TCAM) for a TCAM entry that matches the predetermined number of bits from the destination IP address;

returning an index value from the TCAM entry when the TCAM entry is found that matches the predetermined number of bits;

forming a key value by combining the index value from the TCAM entry with a second group of bits from the destination IP address of the received packet, wherein the second group of bits comprises all bits from the destination IP address that are not included in the first group of bits; and

searching a random-access memory (RAM) for a preset Forwarding Information Base (FIB) entry using the key value to obtain a forwarding IP address of the received packet.

17. The method for forwarding packets according to claim 16, further comprising searching for the forwarding IP address of the received packet using all the bits from the destination IP address when the TCAM entry is not found that matches the predetermined number of bits.

18. The method for forwarding packets according to claim 16, wherein the destination IP address of the received packet comprises a 128-bit IP version 6 (IPv6) address, and wherein the first group of bits comprises 16 bits, 32 bits, or 64 bits.

19. The method for forwarding data packets according to claim 16, wherein the destination IP address comprises a 128-bit IP version (IPv6) address, wherein the first group of bits comprises a first 64 bits of the 128-bit IPv6 address, wherein the second group of bits comprises a last 64 bits of the 128-bit IPv6 address, and wherein the index value comprises 16 bits.