M-trie based packet processing

• US 7,149,216 B1
• Filed: 09/05/2000
• Issued: 12/12/2006
• Est. Priority Date: 09/05/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R.
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/655,295
• Time in Patent Office: 2,289 Days
• Field of Search: 370/351, 370/389, 370/390, 370/392, 370/238, 370/393, 370401-405, 370/408, 703/20, 703/27, 703/238
• US Class Current: 370/392
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

In an embodiment, different aspects of a packet header and data included in the packet are singled out for attention, rather that just the four byte IP destination address. Different information is included in nodes of the trie that enables matching and branching on different header fields. In an embodiment, the ACL of a configuration file in a router or switch is compiled into a trie data structure located in the memory of the router or switch. In an embodiment, a trie data structure is used to map a multicast packet header by a sequence of nodes that match on destination address or source address.

Claims

1. A method for routing or switching data packets, comprising the computer-implemented steps of:

receiving a data packet at an input interface on a router or switch;

looking up information in the header of said data packet in an expanded M-trie data structure, wherein said expanded M-trie data structure is organized as a multi-level tree including a root node, inferior nodes, and terminal nodes, wherein each node stores values for an address and an opcode, wherein said opcode specifies;

a particular field of a plurality of fields in the header of said data packet;

an operation that is to be performed on the data stored in said particular field,

wherein said operation is one of a plurality of operations that said opcode can specify; and

terminating said step of looking up information; and

routing said data packet at one or more output interfaces on said router or switch bases on the looked up information.

2. A method as in claim 1, wherein said address includes the address of a node in said expanded M-trie data structure that is to be traversed.

3. A method as in claim 1, wherein said expanded M-trie data structure includes a set of access control parameters.

4. A method as in claim 1, wherein said expanded M-trie data structure includes a set of Quality of Service (QoS) parameters.

5. A method as in claim 1, wherein said expanded M-trie data structure includes a set of Class of Service (CoS) parameters.

6. A method as in claim 1, wherein said nodes include opcodes for demultiplexing, opcodes for matching, and opcodes for hashing.

7. A method as in claim 6, wherein said opcodes for demultiplexing include instructions to demultiplex into branches of said expanded M-trie data structure based on contents of a byte of said packet header that is being read.

8. A method as in claim 6, wherein said opcodes for matching include instructions to compare the contents of a given byte of the flow label to given node data.

9. A method as in claim 6, wherein said opcodes for hashing include instructions to hash into different M-trie plus branches based on the contents of a given byte in said packet header.

10. A method as recited in claim 1, further comprising routing said data packet at one or more output interfaces on said router or said switch.

11. A method as recited in claim 1, further comprising determining, based on one or more Access Control List (ACL) criteria stored in said expanded M-trie data structure, whether to drop or forward said data packet.

12. A method as recited in claim 11, wherein determining whether to drop or forward said data packet comprises matching said information in the header of said data packet to the one or more ACL criteria stored in said expanded M-trie data structure.

13. A method as recited in claim 11, wherein said one or more ACL criteria include at least one of a source address, destination address, and upper-layer protocol information.

14. A method as recited in claim 11, wherein said one or more ACL criteria are stored in a sub-tree of said expanded M-trie data structure.

15. An apparatus for routing or switching data packets, comprising:

means for storing in memory an M-trie data structure, said data structure organized as a multi-level tree having a set of nodes, including a root node, inferior nodes and terminal nodes, wherein each node stores values for an address and an opcode, wherein said opcode specifies;

a particular field of a plurality of fields of data packet headers; and

an operation that is to be performed on the data stored in said particular field,

wherein said operation is one of a plurality of operations that said opcode can specify;

means for receiving a data packet at an input interface on a router or switch, wherein the data packet includes information in at least a header with at least a field that is used by said M-trie data structure to indicate an action for said device to perform in order to select a leaf associated with said M-trie data structure;

means for looking up the information, wherein the looking up includes performing the action; and

means for routing said data packet at one or more output interfaces on said router or said switch based on the looked up information.

16. A method for routing or switching data packets, comprising the computer-implemented steps of:

storing in memory an M-trie data structure, said data structure organized as a multi-level tree having a set of nodes, including a root node, inferior nodes and terminal nodes, wherein each node stores values for an address and an opcode, wherein said opcode specifies;

a particular field of a plurality of fields of data packet headers; and

an operation that is to be performed on the data stored in said particular field,

wherein said operation is one of a plurality of operations that said opcode can specify;

receiving a data packet at an input interface on a router or switch, wherein the data packet includes information in at least a header with at least a field that is used by said M-trie data structure to indicate an action; and

routing said data packet at one or more output interfaces on said router or switch based on the looked up information for a router to perform in order to select a leaf associated with said M-trie data structure;

looking up the information, wherein the looking up includes performing the action; and

routing said data packet at one or more output interfaces on said router or switch based on the looked up information.

17. A method as recited in claim 16, further comprising routing said data packet at one or more output interfaces on said router or said switch.

18. A method as recited in claim 16, further comprising determining, based on one or more Access Control List (ACL) criteria stored in said M-trie data structure, whether to drop or forward said data packet.

19. A method as recited in claim 18, wherein determining whether to drop or forward said data packet comprises matching said information to the one or more ACL criteria stored in said M-trie data structure.

20. A method as recited in claim 18, wherein said one or more ACL criteria include at least one of a source address, a destination address, and upper-layer protocol information.

21. A method as recited in claim 18, wherein said one or more ACL criteria are stored in a sub-tree of said M-trie data structure.

22. A computer readable memory storing a program for performing a method for routing or switching data packets, comprising:

storing in memory an M-trie data structure, said data structure organized as a multi-level tree having a set of nodes, including a root node, inferior nodes and terminal nodes, wherein each node stores values for an address and an opcode, wherein said opcode specifies;

a particular field of a plurality of fields of data packet headers; and

an operation that is to be performed on the data stored in said particular field,

wherein said operation is one of a plurality of operations that said opcode can specify;

receiving a data packet at an input interface on a router or switch, wherein the data packet includes information in at least a header with at least a field that is used by said M-trie data structure to indicate an action for a router to perform in order to select a leaf associated with said M-trie data structure;

looking up the information, wherein the looking up includes performing the action; and

routing said data packet at one or more output interfaces on said router or said switch based on the looked up information.

23. A memory as in claim 22, wherein said address includes an address of a node in said M-trie data structure that is to be traversed.

24. A memory as in claim 22, wherein said M-trie data structure includes a set of access control parameters.

25. A memory as in claim 22, wherein said M-trie data structure includes a set of Quality of Service (QoS) parameters.

26. A memory as in claim 22, wherein said expanded M-trie data structure includes a set of Class of Service (CoS) parameters.

27. A memory as in claim 22 wherein at least one of the root node, inferior nodes, or the terminal node includes an opcode for demultiplexing, an opcode for matching, and an opcode for hashing.

28. A memory as in claim 27 wherein said opcode for demultiplexing includes instructions to demultiplex into branches of the M-trie data structure based on contents of a byte of said packet header.

29. A memory as in claim 27, wherein said opcode for matching includes instructions to compare the contents of a given byte of a flow label to given node data.

30. A memory as in claim 27, wherein said opcode for hashing includes instructions to hash into different branches the M-trie data structure based on the contents of a given set of bytes in said packet header.