Method and apparatus for classifying a network protocol and aligning a network protocol header relative to cache line boundary

• US 20060104268A1
• Filed: 11/15/2004
• Published: 05/18/2006
• Est. Priority Date: 11/15/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Recordation Form Cover Sheet Credit Card Payment Form For The Amount of $179600
• Inventors: Hughes, Martin, Haridas, Sriram, Chowdhury, Joydeep, Wright, Michael, Lee, William
• Granted Patent: US 7,848,332 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/60 Router architectures
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

Techniques for routing a payload of a first network protocol, which includes header information for a second network protocol, include communicating a packet. In a circuit block, a first type for the first network protocol and a second type for the second network protocol are determined. The circuit block stores a classification that indicates a unique combination of the first type and the second type. A general purpose processor routes the packet based on the classification. Processor clock cycles are saved that would be consumed in determining the types. Furthermore, based on the classification, the processor can store an offset value for aligning the header relative to a cache line. The circuit block can store the packet shifted by the offset value. The processor can then retrieve from memory a single cache line to receive the header, thereby saving excess loading and ejecting of cache.

Claims

1. An apparatus for routing information in a payload of a first network protocol, which payload includes header information for a second network protocol, comprising:

a network interface that is coupled to a network for communicating therewith a packet;

a memory for storing information;

a circuit block configured to perform the steps of;

determining a first type for the first network protocol and a second type for the second network protocol based on information in the packet; and

storing into the memory classification data that indicates a unique combination of the first type and the second type;

one or more processors; and

one or more sequences of instructions in a computer-readable medium, which, when executed by the one or more processors, causes the one or more processors to carry out the step of routing the packet based at least in part on the second network protocol without performing the step of determining the first type and the second type based on information in the packet, thereby omitting processor clock cycles that would otherwise be consumed in determining the first type and the second type.

2. The apparatus as recited in claim 1, the sequence of instructions, when executed, further causing the one or more processors to carry out the step of storing into memory, in association with the classification data, an offset value indicating a number of bits for aligning the header for the second network protocol relative to a boundary of a cache line for moving data between the memory and the one or more processors.

3. The apparatus as recited in claim 1, wherein:

the circuit block is further configured to perform the steps of

receiving, based on the classification data, an offset value indicating a number of bits for aligning the header for the second network protocol relative to a boundary of a cache line for moving data between the memory and the one or more processors, and

storing the packet into memory shifted by the number of bits indicated by the offset value; and

the sequence of instructions, when executed, further causes the one or more processors to perform the step of retrieving from the memory no more than one cache line to receive the header for the second networking protocol.

4. The apparatus as recited in claim 2, said step of storing the packet into memory shifted by the number of bits indicated by the offset value further comprising padding a start of the packet with an arbitrary value until the packet is shifted by the number of bits indicated by the offset value.

5. The apparatus as recited in claim 2, said step of storing into memory the offset value further comprising determining the offset value for aligning a beginning of the header for the second network protocol on the boundary of the cache line.

6. The apparatus as recited in claim 2, said step of storing into memory the offset value further comprising determining the offset value based on a programmable mapping between a plurality of values for the classification data and a corresponding plurality of offset values.

7. The apparatus as recited in claim 2, said step of storing into memory the offset value further comprising storing into memory an integer value indicating an integral number of bytes.

8. The apparatus as recited in claim 1, said step of storing, into the memory, classification data further comprising storing the classification data in a descriptor record that points to a packet data buffer where the packet is stored in the memory.

9. The apparatus as recited in claim 1, said step of determining the first type and the second type further comprising comparing a value in a type field in the packet to a special value in a programmable register, thereby allowing the circuit block to identify a protocol type not known when the circuit block was designed.

10. The apparatus as recited in claim 1, said step of determining the first type and the second type further comprising determining the second type that indicates a protocol that corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

11. The apparatus as recited in claim 10, said step of determining the first type and the second type further comprising determining the second type that indicates one of:

an Internet Protocol (IP);

a Multi-protocol Layer Switch (MPLS); and

a protocol developed after design of the circuit block, which corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

12. The apparatus as recited in claim 1, said step of determining the first type and the second type further comprising determining the first type that indicates a protocol that corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

13. The apparatus as recited in claim 12, said step of determining the first type and the second type further comprising determining the first type that indicates one of:

a plain International Electrical and Electronics Engineers (IEEE) 802.3 protocol;

a Sub-network Access Protocol (SNAP) within IEEE 802.3;

a virtual local area network (VLAN) using IEEE 802.3 protocol;

a VLAN using SNAP within IEEE 802.3 protocol;

a nested VLAN (QINQ) using IEEE 802.3 protocol;

a QINQ using SNAP within IEEE 802.3 protocol; and

a protocol other than listed protocols, which corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

14. The apparatus as recited in claim 1, said one or more sequences of instructions further causing the one or more processors to carry out the step of forming a plurality of descriptor rings corresponding to a plurality of values for the classification data, wherein a descriptor ring stores a plurality of descriptor records that each point to a packet data buffer where the packet is stored in the memory.

15. The apparatus as recited in claim 14, said one or more sequences of instructions further causing the one or more processors to use a limited instruction set for processing only a particular combination of protocols when processing a packet pointed to by descriptor records in a particular descriptor ring corresponding to the particular combination of protocols, thereby reducing at least one of a number of instructions transferred from memory to an instruction cache in a processor and a number of parameters stored in a descriptor record.

16. The apparatus as recited in claim 14, said one or more sequences of instructions further causing a particular processor to process data pointed to by descriptor records in a particular descriptor ring corresponding to a particular combination of protocols, thereby reducing a number of times instructions are transferred from memory to an instruction cache in the processor.

17. An apparatus for routing information in a payload of a first network protocol, which payload includes header information for a second network protocol, comprising:

a network interface that is coupled to a network for communicating therewith a packet;

a memory for storing information;

a circuit block configured to perform the steps of;

determining a first type for the first network protocol and a second type for the second network protocol based on information in the packet, including comparing a value in a type field in the packet to a special value in a programmable register, thereby allowing the circuit block to identify a protocol type not known when the circuit block was designed;

storing classification data that indicates a unique combination of the first type and the second type in the memory in a descriptor record that points to a packet data buffer where the packet is stored in the memory; and

storing the packet into memory shifted by a number of bits indicated by an offset value retrieved for memory by padding a start of the packet with an arbitrary value until the packet is shifted by the number of bits indicated by the offset value;

one or more processors; and

one or more sequences of instructions in a computer-readable medium which, when executed by the one or more processors, causes the one or more processors to carry out the steps of;

storing into memory, based on the classification data, the offset value indicating the number of bits for aligning a beginning of the header for the second network protocol on a boundary of a cache line for moving data between the memory and the one or more processors as an integer value indicating an integral number of bytes, including determining the offset value based on a programmable mapping between a plurality of values for the classification data and a corresponding plurality of offset values;

retrieving from the memory no more than one cache line to receive the header for the second networking protocol, which cache is aligned with the beginning of the header for the second network protocol, thereby omitting at least one of a cache line load and a cache line ejection that would otherwise be executed for finding a cache line that includes the header for the second networking protocol; and

routing the packet based at least in part on the header for the second network protocol without performing the step of determining the first type and the second type based on information in the packet, thereby omitting processor clock cycles that would otherwise be consumed in determining the first type and the second type.

18. An apparatus for routing information in a payload of a first network protocol, which payload includes header information for a second network protocol, comprising:

a means for communicating a packet;

a means for determining a first type for the first network protocol and a second type for the second network protocol based on information in the packet without using a general purpose processor, thereby omitting processor clock cycles that would otherwise be consumed in determining the first type and the second type;

a means for storing classification data that indicates a unique combination of the first type and the second type without using a general purpose processor; and

a means for routing the packet based at least in part on the classification data.

19. A method for a network device, which includes a general purpose processor configured to execute a router operating system, for processing information in a payload of a first network protocol which payload includes header information for a second network protocol, the method comprising the steps of:

receiving a packet at a network device;

determining a first type for the first network protocol and a second type for the second network protocol based on information in the packet without using a general purpose processor in the network device;

storing into memory without using the general purpose processor, classification data that indicates a unique combination of the first type and the second type; and

routing the packet based at least in part on the classification data.

20. The method as recited in claim 19, further comprising the steps of:

receiving an offset value indicating a number of bits for aligning the header for the second network protocol relative to a boundary of a cache line for moving data between the memory and the general purpose processor; and

storing the packet into memory shifted by the number of bits indicated by the offset value without using the general purpose processor.

21. The method as recited in claim 20, said step of storing the packet into memory shifted by the number of bits indicated by the offset value further comprising padding a start of the packet with an arbitrary value until the packet is shifted by the number of bits indicated by the offset value.

22. The method as recited in claim 20, said step of receiving the offset value further comprising receiving the offset value for aligning a beginning of the header for the second network protocol on the boundary of the cache line.

23. The method as recited in claim 20, said step of receiving the offset value further comprising receiving an integer value indicating an integral number of bytes.

24. The method as recited in claim 19, said step of storing, into the memory, classification data further comprising storing the classification data in a descriptor record that points to a packet data buffer where the packet is stored in the memory.

25. The method as recited in claim 19, said step of determining the first type and the second type further comprising comparing a value in a type field in the packet to a special value in a programmable register of a circuit block, thereby allowing classification of a protocol type not known when the circuit block was designed.

26. The method as recited in claim 19, said step of determining the first type and the second type further comprising determining the second type that indicates a protocol that corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

27. The method as recited in claim 26, said step of determining the first type and the second type further comprising determining the second type that indicates one of:

an Internet Protocol (IP);

a Multi-protocol Layer Switch (MPLS); and

a protocol developed after design of the circuit block, which corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

28. The method as recited in claim 19, said step of determining the first type and the second type further comprising determining the first type that indicates a protocol that corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

29. The method as recited in claim 28, said step of determining the first type and the second type further comprising determining the first type that indicates one of:

a plain International Electrical and Electronics Engineers (IEEE) 802.3 protocol;

a Sub-network Access Protocol (SNAP) within IEEE 802.3;

a virtual local area network (VLAN) using IEEE 802.3 protocol;

a VLAN using SNAP within IEEE 802.3 protocol;

a nested VLAN (QINQ) using IEEE 802.3 protocol;

a QINQ using SNAP within IEEE 802.3 protocol; and

a protocol other than listed protocols, which corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

30. A method for a network device, which includes a general purpose processor configured to execute a router operating system, for processing information in a payload of a first network protocol which payload includes header information for a second network protocol, the method comprising the steps of:

receiving classification data that indicates a unique combination of a first type for the first network protocol and a second type for the second network protocol based on information in a packet received at the network device without performing the step of determining the first type and the second type based on information in the packet, thereby omitting processor clock cycles that would otherwise be consumed in determining the first type and the second type; and

routing the packet based at least in part on the classification data.

31. The method as recited in claim 30, further comprising the step of storing into memory, based on the classification data, an offset value indicating a number of bits for aligning the header for the second network protocol relative to a boundary of a cache line for moving data between memory and the general purpose processor without performing the step of shifting the packet in memory by the number of bits indicated by the offset value thereby omitting processor cycles that would otherwise be consumed in shifting.

32. The method as recited in claim 31, further comprising the step of retrieving from memory no more than one cache line to receive the header for the second networking protocol which is aligned with a cache line boundary, thereby omitting at least one of a cache line load and a cache line ejection that would otherwise be executed for finding a cache line that includes the header for the second networking protocol.

33. The method as recited in claim 31, said step of storing into memory the offset value further comprising determining the offset value for aligning a beginning of the header for the second network protocol on the boundary of the cache line.

34. The method as recited in claim 31, said step of storing into memory the offset value further comprising determining the offset value based on a programmable mapping between a plurality of values for the classification data and a corresponding plurality of offset values.

35. The method as recited in claim 31, said step of storing into memory the offset value further comprising storing into memory an integer value indicating an integral number of bytes.

36. The method as recited in claim 30, said step of receiving classification data further comprising retrieving the classification data from a descriptor record that points to a packet data buffer where the packet is stored in memory.

37. The method as recited in claim 30, further comprising programming a special type value into a programmable register in a circuit block configured to determine the first type and the second type, thereby allowing the circuit block to identify a protocol type not known when the circuit block was designed.

38. The method as recited in claim 30, said step of receiving classification data further comprising receiving classification data that indicates the second type indicates a protocol that corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

39. The method as recited in claim 38, said step of receiving classification data further comprising receiving classification data that indicates the second type indicates one of:

an Internet Protocol (IP);

a Multi-protocol Layer Switch (MPLS); and

a protocol developed after design of the circuit block, which corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

40. The method as recited in claim 30, said step of receiving classification data further comprising receiving classification data that indicates the first type indicates a protocol that corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

41. The method as recited in claim 40, said step of receiving classification data further comprising receiving classification data that indicates the first type indicates one of:

a plain International Electrical and Electronics Engineers (IEEE) 802.3 protocol;

a Sub-network Access Protocol (SNAP) within IEEE 802.3;

a virtual local area network (VLAN) using IEEE 802.3 protocol;

a VLAN using SNAP within IEEE 802.3 protocol;

a nested VLAN (QINQ) using IEEE 802.3 protocol;

a QINQ using SNAP within IEEE 802.3 protocol; and

a protocol other than listed protocols, which corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

42. The method as recited in claim 30, further comprising the step of forming a plurality of descriptor rings corresponding to a plurality of values for the classification data, wherein a descriptor ring stores a plurality of descriptor records that each point to a packet data buffer where a packet is stored in the memory.

43. The method as recited in claim 42, said step of routing the packet further comprising using a limited instruction set for processing only a particular combination of protocols when processing a packet pointed to by descriptor records in a particular descriptor ring corresponding to the particular combination of protocols, thereby reducing at least one of a number of instructions and a number of variables associated with processing the packet.

44. The method as recited in claim 42, said step of routing the packet further comprising using a particular processor to process data pointed to by descriptor records in a particular descriptor ring corresponding to a particular combination of protocols, thereby reducing a number of times instructions are transferred from memory to an instruction cache in the processor.

45. A computer-readable medium carrying one or more sequences of instructions for processing information in a payload of a first network protocol which payload includes header information for a second network protocol, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving classification data that indicates a unique combination of a first type for the first network protocol and a second type for the second network protocol based on information in a packet received at a network device without performing the step of determining the first type and the second type based on information in the packet, thereby omitting processor clock cycles that would otherwise be consumed in determining the first type and the second type; and

routing the packet based at least in part on the classification data.

46. The computer-readable medium as recited in claim 45, wherein execution of the one or more sequences of instructions further causes the one or more processors to perform the step of storing into memory, based on the classification data, an offset value indicating a number of bits for aligning the header for the second network protocol relative to a boundary of a cache line for moving data between memory and the one or more processors without performing the step of shifting the packet in memory by the number of bits indicated by the offset value, thereby omitting processor cycles that would otherwise be consumed in shifting.

47. The computer-readable medium as recited in claim 46, wherein execution of the one or more sequences of instructions further causes the one or more processors to perform the step of retrieving from memory no more than one cache line to receive the header for the second networking protocol which is aligned with a cache line boundary, thereby omitting at least one of a cache line load and a cache line ejection that would otherwise be executed for finding a cache line that includes the header for the second networking protocol.

48. The computer-readable medium as recited in claim 46, said step of storing into memory the offset value further comprising determining the offset value for aligning a beginning of the header for the second network protocol on the boundary of the cache line.

49. The computer-readable medium as recited in claim 46, said step of storing into memory the offset value further comprising determining the offset value based on a programmable mapping between a plurality of values for the classification data and a corresponding plurality of offset values.

50. The computer-readable medium as recited in claim 46, said step of storing into memory the offset value further comprising storing into memory an integer value indicating an integral number of bytes.

51. The computer-readable medium as recited in claim 45, said step of receiving classification data further comprising retrieving the classification data from a descriptor record that points to a packet data buffer where the packet is stored in memory.

52. The computer-readable medium as recited in claim 45, further comprising programming a special type value into a programmable register in a circuit block configured to determine the first type and the second type, thereby allowing the circuit block to identify a protocol type not known when the circuit block was designed.

53. The computer-readable medium as recited in claim 45, said step of receiving classification data further comprising receiving classification data that indicates the second type indicates a protocol that corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

54. The computer-readable medium as recited in claim 53, said step of receiving classification data further comprising receiving classification data that indicates the second type indicates one of:

an Internet Protocol (IP);

a Multi-protocol Layer Switch (MPLS); and

a protocol developed after design of the circuit block, which corresponds to an Open Systems Interconnection (OSI) Reference Model layer above a data link layer.

55. The computer-readable medium as recited in claim 45, said step of receiving classification data further comprising receiving classification data that indicates the first type indicates a protocol that corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

56. The computer-readable medium as recited in claim 55, said step of receiving classification data further comprising receiving classification data that indicates the first type indicates one of:

a plain International Electrical and Electronics Engineers (IEEE) 802.3 protocol;

a Sub-network Access Protocol (SNAP) within IEEE 802.3;

a virtual local area network (VLAN) using IEEE 802.3 protocol;

a VLAN using SNAP within IEEE 802.3 protocol;

a nested VLAN (QINQ) using IEEE 802.3 protocol;

a QINQ using SNAP within IEEE 802.3 protocol; and

a protocol other than listed protocols, which corresponds to Open Systems Interconnection (OSI) Reference Model data link layer.

57. The computer-readable medium as recited in claim 45, said one or more sequences of instructions further causing the one or more processors to carry out the step of forming a plurality of descriptor rings corresponding to a plurality of values for the classification data, wherein a descriptor ring stores a plurality of descriptor records that each point to a packet data buffer where the packet is stored in the memory.

58. The computer-readable medium as recited in claim 57, said one or more sequences of instructions further causing the one or more processors to use a limited instruction set for processing only a particular combination of protocols when processing a packet pointed to by descriptor records in a particular descriptor ring corresponding to the particular combination of protocols, thereby reducing at least one of a number of instructions transferred from memory to an instruction cache in a processor and a number of parameters stored in a descriptor record.

59. The computer-readable medium as recited in claim 57, said one or more sequences of instructions further causing a particular processor to process data pointed to by descriptor records in a particular descriptor ring corresponding to a particular combination of protocols, thereby reducing a number of times instructions are transferred from memory to an instruction cache in the particular processor.