Identifying QoS flows using indices
A multivariant, common basis classification method and apparatus for classifying protocol data units in a network switching device is disclosed. The method of classifying a protocol data unit (PDU) in the preferred embodiment includes the steps of generating a first string and a second string with which to characterize a PDU; mapping first and second strings into a first index and second index, respectively, where the first and second indices are selected from a plurality of indices; and selecting an instruction to apply to the PDU by matching the first and second indices. The plurality of strings are commonly generated from the source and destination address in the packet as well as other indicia with which to identify a traffic flow. The instructions specify how to classify, route, switch, or otherwise process the PDU.
1. A method of classifying a protocol data unit (PDU) comprising the steps of:
(a) generating with a string generator a first string and a second string with which to characterize the PDU;
(b) determining a first index associated with the first string and a second index associated with the second string, wherein the first index and second index are selected from a plurality of indices; and
(c) selecting an action from a plurality of actions based on the first index and the second index, each action being associated with two or more indices of the plurality of indices.
2. The method of claim 1 , wherein PDU has one or more fields and the first string and second string each comprise one or more bits derived from the one or more fields of the PDU.
3. The method of claim 2 , wherein the one or more fields are selected from a group consisting of: ingress switch slot number, egress switch slot number, ingress port number, egress port number, network layer protocol, and transport layer protocol.
4. The method of claim 2 , wherein the first string comprises one or more bits selected from a destination address field of the PDU.
5. The method of claim 4 , wherein the second string comprises one or more bits selected from a source address field of the PDU.
6. The method of claim 1 , wherein the method further includes the step of generating the plurality of actions from policies that characterize a plurality of traffic flows.
7. The method of claim 1 , wherein the selecting step further comprises the step of using the indices as keys into a memory device comprising the plurality of actions.
8. The method of claim 7 , wherein the actions further comprise instructions passing the PDU to a PDU destination address and instructions to filter the PDU.
9. The method of claim 7 , wherein the actions further comprise one or more pointers to one or more instructions defining the manner in which to process the PDU.
10. The method of claim 1 , wherein the PDU has one or more fields and the step of determining a first index and the second index further comprises the step of searching a tree, wherein one or more fields of the PDU are compared against the nodes of the tree.
11. The method of claim 10 , wherein the tree is a Patricia trie.
12. An apparatus for classifying a protocol data unit (PDU), the apparatus comprising:
(a) a string generator for generating a first string and a second string with which to characterize the PDU;
(b) an index allocator for retrieving a first index associated with the first string and a second index associated with the second string, wherein the first index and second index are selected from a plurality of indices; and
(c) a memory device, operatively coupled to the index allocator, comprising a plurality of actions, each being selected based on two or more indices from the plurality of indices.
13. The apparatus of claim 12 , wherein the first string and second string each comprise one or more bits derived from one or more fields of the PDU.
14. The apparatus of claim 13 , wherein the one or more fields are selected from the group consisting of: a source address, an ingress and an egress switch slot numbers, an ingress and an egress port numbers, an IP protocol, and a transport layer protocols including transmission control protocol (TCP) and user datagram protocol (UDP).
15. The apparatus of claim 14 , wherein the first string comprises one or more bits selected from a destination address field of the PDU.
16. The apparatus of claim 15 , wherein the second string comprises one or more bits selected from a source address field of the PDU.
17. The apparatus of claim 12 , wherein the plurality of actions are derived from policies that characterize a plurality of traffic flows.
18. The apparatus of claim 12 , wherein the plurality of indices are keys into the memory device.
19. The apparatus of claim 18 , wherein the actions further comprise instructions for passing the PDU to a PDU destination address and instructions to filter the PDU.
20. The apparatus of claim 18 , wherein the actions further comprise one or more pointers to one or more instructions defining the manner in which to process the PDU.
21. The apparatus of claim 12 , wherein the index allocator comprises a trie, the trie comprising nodes against which one or more fields of the PDU are compared.
22. A method of classifying a protocol data unit (PDU) comprising the steps of:
(a) generating with a string generator a first string from source information associated with the PDU;
(b) generating with the string generator a second string from destination information associated with the PDU;
(c) identifying a first QoS action from a plurality of QoS actions based on the first string;
(d) identifying a second QoS action from a plurality of QoS actions based the second string; and
(e) determining a final QoS action from at least one of the first and second QoS actions.
23. The method of claim 22 , wherein the step of determining a final QoS action comprises applying a hierarchical rule indicating which one of the first and second QoS actions has precedence.
24. The method of claim 22 , wherein one of the first and second QoS actions is a PDU pass action recommending that the PDU be forwarded, and one of the QoS actions is a PDU drop action recommending that the PDU be filtered.
25. The method of claim 22 , wherein the hierarchical rule indicates that the PDU drop action has precedence over the PDU pass action.