Selective routing of data flows using a TCAM
First Claim
1. A method for classifying a plurality of data flows in a router comprising the steps of:
- partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition;
said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index;
loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order;
loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order;
setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; and
comparing a prefix comprising predetermined packet header information of an incoming packet to said loaded one or more first TCAM entries and one or more second TCAM entries such that a matching said one or more first TCAM entries subsumes any matching said one or more second TCAM entries.
5 Assignments
0 Petitions
Accused Products
Abstract
The present invention relates to a method and system for supporting in a router a plurality of data flows using a ternary content addressable memory (TCAM) in which the number of accesses to write to the TCAM is optimized to improve efficiency of updating and subsequent look up. To accommodate the plurality of data flows, the TCAM is partitioned into at least two partitions in which a first portion includes indices having a higher priority and a second portion includes indices having a lower priority. For example, multiple protocol label switching (MPLS) flows and IP-Virtual Private Network (VPN) can be added to the first partition and policy based routing flows can be added to the second partition. During subsequent TCAM look-up of a prefix of an incoming packet the MPLS or IP-VPN flow will subsume any matching policy based routing flow, such as flows classified by an access control list or traffic manager flows.
-
Citations
67 Claims
-
1. A method for classifying a plurality of data flows in a router comprising the steps of:
-
partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition;
said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index;loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order; loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order; setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; and comparing a prefix comprising predetermined packet header information of an incoming packet to said loaded one or more first TCAM entries and one or more second TCAM entries such that a matching said one or more first TCAM entries subsumes any matching said one or more second TCAM entries. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A method for classifying a plurality of data flows in a router comprising the steps of:
-
partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition, said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index; loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order; loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order; setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; and comparing a prefix comprising predetermined packet header information of an incoming packet to said loaded one or more first TCAM entries and one or more second TCAM entries such that a matching said one or more first TCAM entries subsumes any matching said one or more second TCAM entries, wherein said first plurality of data flows are MPLS or IP-VPN flows and said second plurality of data flows are policy based routing flows.
-
-
25. A method for classifying a plurality of data flows in a router comprising the steps of:
-
partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition, said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index; loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order; loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order; setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; comparing a prefix comprising predetermined packet header information of an incoming packet to said loaded one or more first TCAM entries and one or more second TCAM entries such that a matching said one or more first TCAM entries subsumes any matching said one or more second TCAM entries; maintaining a flow index space having entries corresponding to said TCAM; and determining said predetermined order of said first TCAM entries and said predetermined order of said second TCAM entries in said flow index space before said steps of loading said one or more first TCAM entries.
-
-
26. A system for classifying a plurality of data flows in a router comprising:
-
means for partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition, said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index; means for loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order; means for loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order; means for setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; and means for comparing a prefix comprising packet header information of in incoming packet to predetermined said loaded one or more first TCAM entries and one or more second TCAM entries, wherein a matching said one or more first TCAM entries subsumes an matching said one or more second TCAM entries. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
-
-
49. A system for classifying a plurality of data flows in a router comprising:
-
means for partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition, said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index; means for loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order; means for loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order; means for setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; and means for comparing a prefix comprising predetermined packet header information of an incoming packet to said loaded one or more first TCAM entries and one or more second TCAM entries such that a matching said one or more first TCAM entries subsumes any matching said one or more second TCAM entries, wherein said first plurality of data flows are MPLS or IP-VPN flows and said second plurality of data flows are policy based routing flows.
-
-
50. A system for classifying a plurality of data flows in a router comprising:
-
means for partitioning a ternary content addressable memory (TCAM) into at least a first partition and a second partition, said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index; means for loading one or more first flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order; means for loading one or more second flow TCAM entries of a second of said plurality of data flows into said second partition in a predetermined order; means for setting bit values of a corresponding mask for each of said first TCAM entries and said second TCAM entries such that bits of said respective first TCAM entries and said second TCAM entries are individually masked by said masks; means for comparing a prefix comprising predetermined packet header information of in incoming packet to said loaded one or more first TCAM entries and one or more second TCAM entries such that a matching said one or more first TCAM entries subsumes an matching said one or more second TCAM entries; means for maintaining a flow index space having entries corresponding to said TCAM; and means for determining said predetermined order of said first TCAM entries and said predetermined order of said second TCAM entries in said flow index space before said steps of loading said one or more first TCAM entries.
-
-
51. An apparatus for classifying a plurality of data flows in a routing system comprising:
-
a ternary content addressable memory (TCAM); a partitioning algorithm for partitioning said TCAM into at least a first partition and a second partition, said first partition includes indices having highest priority ranging from a lowest index to a partition index and said second partition includes indices having lowest priority ranging from a highest index to said partition index; a loading algorithm for selecting a respective mask value to structure one or more first flow TCAM entries of a first of said data flows and one or more second flow TCAM entries and said respective mask values into said second partition; and a search algorithm for performing an associative comparison of a prefix comprising predetermined packet header information of an incoming packet to said loaded one or more first flow TCAM entries and one or more second flow TCAM entries of a first of said plurality of data flows into said first partition in a predetermined order such that a matching said one or more first TCAM entries subsumes an matching said one or more second TCAM entries. - View Dependent Claims (52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67)
-
Specification