METHOD AND APPARATUS FOR FORWARDING PACKETS

• US 20110292943A1
• Filed: 05/18/2011
• Published: 12/01/2011
• 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, YI, Yi, HONG, Rongfeng
• Granted Patent: US 8,879,555 B2
• Time in Patent Office: Days
• 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 address of a received packet;

searching for a Ternary Content Addressable Memory (TCAM) entry according to the first group of bits, and obtaining an index value from the TCAM entry; and

searching for a preset Forwarding Information Base (FIB) entry according to the index value and a second group of bits in the destination address of the received packet, and obtaining a forwarding address of the packet.

2. The method for forwarding packets according to claim 1, wherein:

the second group of bits is composed of the rest bits except for the first group of bits in the destination address of the packet.

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

if no TCAM entry is hit, searching for the forwarding address of the packet by using complete field of the destination address.

4. The method for forwarding packets according to claim 1, wherein the searching for the preset Forwarding Information Base (FIB) entry according to the index value and the second group of bits in the destination address of the received packet, and obtaining the forwarding address of the packet comprises:

obtaining a second key value according to the index value and the second group of bits in the destination address of the packet;

searching for the FIB entry according to the second key value; and

obtaining the forwarding address of the packet from the FIB entry.

5. The method for forwarding packets according to claim 4, wherein the obtaining the second key value according to the index value and the second group of bits in the destination address of the packet comprises:

combining the index value and the second group of bits in the destination address of the packet to form the second key value.

6. The method for forwarding packets according to claim 1, wherein the searching for the preset Forwarding Information Base (FIB) entry according to the index value and the second group of bits in the destination address of the received packet, and obtaining the forwarding address of the packet comprises:

obtaining, according to the index value, a scope for searching for the FIB entry;

taking the second group of bits in the destination address of the packet as a third key value, and searching, for the FIB entry in the scope; and

obtaining the forwarding address of the packet from the FIB entry.

7. The method for forwarding packets according to claim 1, wherein the destination address of the packet comprises a destination Internet Protocol (IP) address.

8. The method for forwarding packets according to claim 1, wherein the destination address of the packet comprises a combination of the destination IP address and a predetermined network identifier.

9. The method for forwarding packets according to claim 1, wherein:

the first group of bits extracted from the destination address is composed of a predetermined number of forepart bits of the destination address.

10. The method for forwarding packets according to claim 1, wherein the searching for the Ternary Content Addressable Memory (TCAM) entry according to the first group of bits comprises:

obtaining a key value from the first group of bits; and

searching for the TCAM entry according to the key value.

11. The method for forwarding packets according to claim 10, wherein the obtaining the key value from the first group of bits comprises taking the first group of bits as the key value.

12. An apparatus for forwarding packets, comprising:

an extracting unit, configured to extract a first bit sequence from a destination address of a received packet;

a first search unit, configured to search for a Ternary Content Addressable Memory (TCAM) entry according to the first bit sequence extracted by the extracting unit, and obtain an index value from the TCAM entry; and

a second search unit, configured to search for a preset Forwarding Information Base (FIB) entry according to the index value and a second group of bits in the destination address of the received packet, and obtain a forwarding address of the received packet from the FIB entry.

13. The apparatus for forwarding packets according to claim 12, further comprising:

a third search unit, configured to;

when no TCAM entry is hit, search for the forwarding address of the packet by using a complete field of the destination address.

14. The apparatus for forwarding packets according to claim 12, wherein the second search unit comprises:

a generating subunit, configured to combine the index value obtained by the first search unit and the second group of bits in the destination address of the packet to form a second key value; and

a first search subunit, configured to search for the FIB entry according to the second key value, and obtain the forwarding address of the received packet from the FIB entry.

15. The apparatus for forwarding packets according to claim 12, wherein the second search unit comprises:

an obtaining subunit, configured to obtain a scope for searching for the FIB entry according to the index value obtained by the first search unit; and

a second search subunit, configured to search for a FIB entry in the scope for searching for a FIB entry according to the second group of bits, and obtain the forwarding address of the received packet from the FIB entry.