Packet classification using encoded addresses

• US 20070008962A1
• Filed: 06/30/2005
• Published: 01/11/2007
• Est. Priority Date: 06/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Naik, Uday, Barman, Utpal, Basu, Subhayu
• Granted Patent: US 7,596,141 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

Techniques that may be utilized in a multiprocessor computing system are described. In one embodiment, one or more addresses (such as source and/or destination addresses) of a received packet are encoded to reduce the size of the addresses and the encoded one or more addresses are utilized to classifying the received packet.

Claims

1. A method comprising:

parsing a received packet to obtain one or more 128-bit addresses of the received packet;

encoding the one or more addresses to reduce a size of the one or more addresses;

forming a key based on the one or more encoded addresses; and

classifying the received packet based on the key.

2. The method of claim 1, wherein classifying the received packet comprises looking up the key in a content addressable memory.

3. The method of claim 1, wherein encoding the one or more addresses comprises encoding a source address and a destination address of the received packet.

4. The method of claim 1, wherein forming the key comprises forming the key based on information from on one or more unencoded fields of the received packet.

5. The method of claim 1, further comprising determining whether the received packet has a unicast address format or a multicast address format.

6. The method of claim 5, wherein for the unicast address format, the method further comprises determining which one of a first encoding option, a second encoding option, or a third encoding option is utilized to encode the one or more addresses based on one or more classification rules.

7. The method of claim 6, wherein the first encoding option comprises:

providing a 16-bit first identifier for bits 0 through 47 of an address;

providing a 10-bit second identifier for bits 64 through 127 of the address; and

concatenating an encoding type code, 24 zeros, the first identifier, bits 48 through 63 of the address, and the second identifier to encode the address.

8. The method of claim 6, wherein the second encoding option comprises:

providing an 8-bit first identifier for bits 0 through 15 of an address;

providing a 10-bit second identifier for bits 64 through 127 of the address; and

concatenating an encoding type code, the first identifier, bits 16 through 63 of the address, and the second identifier to encode the address.

9. The method of claim 6, wherein the third encoding option comprises concatenating an encoding type code with bits 0 through 63 of an address.

10. The method of claim 5, wherein for the multicast address format, the method further comprises:

providing a 13-bit first identifier for bits 16 through 63 of an address;

providing a 13-bit second identifier for bits 64 through 95 of the address; and

concatenating an encoding type code, bits 7 through 15, the first identifier, the second identifier, and bits 96 through 127 of the address to encode the address.

11. An apparatus comprising:

a parser to parse a received packet to obtain one or more 128-bit addresses of the received packet;

an address compression block coupled to the parser to encode the one or more addresses to reduce a size of the one or more addresses;

a key formation block coupled to the address compression block to form a key based on the one or more encoded addresses; and

a packet classification block to classify the received packet based the key.

12. The apparatus of claim 11, further comprising an incoming port to receive the packet and an outgoing port to send the classified packet to a computer network.

13. The apparatus of claim 11, wherein the packet complies with Internet protocol version 6 (IPv6).

14. The apparatus of claim 11, wherein the one or more addresses are a source address of the received packet or a destination address of the received packet.

15. The apparatus of claim 11, wherein one or more of the parser, address compression block, key formation block, or packet classification block are implemented in a multiprocessor computing system.

16. The apparatus of claim 15, wherein the multiprocessor computing system comprises a symmetrical multiprocessor or an asymmetrical multiprocessor.

17. The apparatus of claim 15, wherein the multiprocessor computing system comprises one or more processor cores utilized to perform one or more operations of the parser, address compression block, key formation block, or packet classification block.

18. The apparatus of claim 15, further comprising one or more content addressable memory devices to store data for one or more of the address compression block or packet classification block.

19. The apparatus of claim 18, wherein the one or more content addressable memory devices comprise one or more ternary content addressable memory.

20. The apparatus of claim 11, wherein the packet is one of a unicast packet or a multicast packet.

21. A traffic management device comprising:

one or more memory devices to store information corresponding to a key; and

a multiprocessor computing system coupled to the one or more memory device to;

parse a received packet to obtain one or more 128-bit addresses of the received packet;

encode the one or more addresses to reduce a size of the one or more addresses;

form the key based on the one or more encoded addresses; and

classify the received packet based on the key.

22. The device of claim 21, further comprising a network interface to communicate the packet with a computer network in accordance with Internet protocol version 6 (IPv6).

23. The device of claim 21, wherein the one or more memory devices comprise a ternary content addressable memory (TCAM).

24. The device of claim 21, wherein the one or more memory devices are one or more of a hard drive, RAM, DRAM, SRAM, and SDRAM.

25. A computer-readable medium comprising:

stored instructions to parse a received packet to obtain one or more addresses of the received packet;

stored instructions to encode the one or more 128-bit addresses to reduce a size of the one or more addresses;

stored instructions to form a key based on the one or more encoded addresses; and

stored instructions to classify the received packet based on the key.

26. The computer-readable medium of claim 25, further comprising stored instructions to determine whether the received packet has a unicast address format or a multicast address format.

27. The computer-readable medium of claim 25, further comprising stored instructions to look up the key in a content addressable memory.