Selective routing of data flows using a TCAM

• US 7,028,098 B2
• Filed: 07/20/2001
• Issued: 04/11/2006
• Est. Priority Date: 07/20/2001
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Mahamuni, Atul, Mate, Ashutosh, Chander, Vijay
• Primary Examiner(s): Lim, Krisna
• Assistant Examiner(s): NASH, LASHANYA RENEE
• Application Number:
  US09/909,739
• Publication Number:
  US 20030056001A1
• Time in Patent Office: 1,726 Days
• Field of Search: 709/238, 709239-244, 711/108, 711/212, 711/151, 711/158
• US Class Current: 709/238
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• 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/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/627 policing
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9036 Common buffer combined with individual queues
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet

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.

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.

2. The method of claim 1 where said first plurality of data flows are MPLS or IPVPN flows.

3. The method of claim 1 wherein said second plurality of data flows are policy based routing flows.

4. The method of claim 3 wherein said policy based routing flows are access control list (ACL) flows.

5. The method of claim 3 wherein said policy based routing flows are traffic manager flows.

6. The method of claim 1 further comprising the steps of:

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 and loading said one or more second TCAM entries.

7. The method of claim 2 wherein said MPLS or IP-VPN flows are classified by connection index (CIX) and destination address (DA), CIX only or DA only.

8. The method of claim 7 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index and said flows classified by CLX and DA and CIX only are assigned to said first portion and said flows classified by DA only are assigned to said second portion.

9. The method of claim 8 wherein said flows classified by CIX and DA and said flows classified by CIX only are loaded into said first portion starting at said gMaxCixDaFix index and said flows classified by said DA only are loaded in said second portion starting at said gMinDaOnlyFix index.

10. The method of claim 9 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index, said gMaxCixDaFix index being adjacent to said gMinDaOnlyFix index and a free entry being positioned below said gMinDaOnlyFix index in said second portion and further comprising the steps of:

(a) moving a flow classified by DA only at said gMinDaOnlyFix index to said free entry;

(b) assigning a flow classified by CIX and DA or CIX only to said gMinDaOnlyFix index after step (a);

(c) setting the gMaxCixDaFix index at the index assigned to said flow classified by CIX and DA or CIX only in step (b); and

(d) setting the gMinDaOnlyFix index immediately after the index assigned to said 10 flow classified by CIX and DA or CIX only in step (b).

11. The method of claim 10 further comprising the steps of:

ordering said loaded one or more flows classified by CIX and DA or CIX only which are between said lowest index and said gMaxCixDaOnlyFix index for subsuming ordering; and

ordering said loaded one or more flows classified by DA only which are between said gMinDaOnlyFix index and said partition index for subsuming ordering.

12. The method of claim 9 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index, said gMaxCixDaFix index being adjacent to said gMinDaOnlyFix index and a free entry being positioned above said gMinDaOnlyFix index in said second portion and further comprising the steps of:

(a) moving a flow classified by CIX and DA or CIX only at said gMaxCixDaFix to said free entry;

(b) assigning a flow classified by DA only to said gMaxCixDaFix index after step (a);

(c) setting the gMinDaOnlyFix index at the index assigned to said flow classified by DA only in step (b); and

(d) setting the gMaxCixDaFix entry immediately before the index assigned to said flow classified by DA only in step (b).

13. The method of claim 12 further comprising the steps of:

ordering said loaded one or more flows classified by DA only which are between said partition index and said gMinDaOnlyFix index for subsuming ordering; and

ordering said loaded one or more flows classified by CLX and DA or CLX only between said gMaxCixDaFix index and said lowest index for subsuming ordering.

14. The method of claim 7 further comprising the steps of:

maintaining a flow index space having entries corresponding to said TCAM; and

assigning said flows classified by CIX and DA and CIX only to a CIX prefix tree.

15. The method of claim 7 further comprising the steps of:

maintaining a flow index space having entries corresponding to said TCAM; and

assigning said flows classified by DA only to a DA prefix tree.

16. The method of claim 7 further comprising the step of:

removing a flow in said TCAM by freeing up a corresponding said entry in said 20 flow index space and invalidating a corresponding said TCAM entry.

17. The method of claim 1 wherein said predetermined order of said first partition has one of said TCAM entries with a longest prefix located at an index having highest priority followed by decreasing prefix values with a shortest prefix at an index having lowest priority.

18. The method of claim 3 wherein said second partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from a lowest index in said second partition to a GACL-partition index and said second portion includes indices having lowest priority ranging from said GACL-partition index to said highest index, said ACL flows ar global access list flows are assigned to said second portion.

19. The method of claim 18 wherein said ACL flow specifies a range of source or destination ports, and further comprising the step of:

mapping said ACL flow to multiple flows in said TCAM wherein said mask for each of said multiple flows covers a portion of said range of source or destination ports for optimally determining a number of flows to cover said portion of said range.

20. The method of claim 18 further comprising the step of:

maintaining a flow index space having entries corresponding to said TCAM.

21. The method of claim 20 further comprising the steps of:

removing a flow in said TCAM by freeing up a corresponding said entry in said 15 flow index space and invalidating a corresponding said TCAM entry; and

compacting said flows in said TCAM by moving each remaining said TCAM entry up by one index.

22. The method of claim 19 further comprising the steps of:

maintaining a flow index space having entries corresponding to said TCAM.

23. The method of claim 22 further comprising the step of:

removing said multiple flows in said TCAM by freeing up corresponding said entries in said flow index space and invalidating said corresponding entries in said TCAM entry; and

compacting said flows in said TCAM by moving each remaining said TCAM entry up by one or more indices.

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.

27. The system of claim 26 where said first plurality of data flows are MPLS or LP-VPN flows.

28. The system of claim 26 wherein said second plurality of data flows are policy based routing flows.

29. The system of claim 28 wherein said policy based routing flows are access control list (ACL) flows.

30. The system of claim 28 wherein said policy based routing flows are traffic manager flows.

31. The system of claim 26 further comprising:

means for maintaining a flow index space having entries corresponding to said 15 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.

32. The system of claim 27 wherein said MPLS or IP-VPN flows are classified by connection index (CLX) and destination address (DA), CIX only or DA only.

33. The system of claim 32 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index and said flows classified by CLX and DA and CLX only are assigned to said first portion and said flows classified by DA only are assigned to said second portion.

34. The system of claim 33 wherein said flows classified by CIX and DA and said flows classified by CIX only are loaded into said first portion starting at said gMaxCixDaFix index and said flows classified by said DA only are loaded in said second portion starting at said gMinDaOnlyFix index.

35. The system of claim 32 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM; and

assigning said flows classified by CIX and CLX only to a CIX prefix tree.

36. The system of claim 32 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index, said gMaxCixDaFix index being adjacent to said gMinDaOnlyFix index and a free entry being positioned below said gMinDaOnlyFix index in said second portion and further comprising:

means for moving a flow classified by DA only at said gMinDaOnlyFix index to said free entry;

means for assigning a flow classified by CLX and DA or CLX only to said gMinDaOnlyFix index;

means for setting the gMaxCixDaFix index at the index assigned to said flow 20 classified by CIX and DA or CIX only; and

means for setting the gMinDaOnlyFix index immediately after the index assigned to said flow classified by CIX and DA or CIX only.

37. The system of claim 36 further comprising:

means for ordering said loaded one or more flows classified by CIX and DA or CIX only which are between said lowest index to said gMaxCixDaOnlyFix index for subsuming ordering; and

means for ordering said loaded one or more flows classified by DA only which are between said gMinDaOnlyFix index and said partition index for subsuming ordering.

38. The system of claim 32 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index, said gMaxCixDaFix index being adjacent to said gMinDaOnlyFix index and a free entry being positioned above said gMinDaOnlyFix index in said second portion and further comprising:

means for moving a flow classified by CIX and DA or CIX only at said gMaxCixDaFix to said free entry;

means for assigning a flow classified by DA only to said gMaxCixDaFix index;

means for setting the gMinDaOnlyFix index at the index assigned to said flow classified by DA only; and

means for setting the gMaxCixDaFix entry immediately before the index assigned to said flow classified by DA only.

39. The system of claim 36 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index, said gMaxCixDaFix index being adjacent to said gMinDaOnlyFix index and a free entry being positioned above said gMinDaOnlyFix index in said second portion and further comprising:

means for moving a flow classified by CIX and DA or CIX only at said gMaxCixDaFix to said free entry;

means for assigning a flow classified by DA only to said gMaxCixDaFix index;

means for setting the gMinDaOnlyFix index at the index assigned to said flow classified by DA only; and

means for setting the gMaxCixDaFix entry immediately before the index assigned to said flow classified by DA only.

40. The system of claim 32 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM; and

means for assigning said flows classified by DA only to a DA prefix tree.

41. The system of claim 40 further comprising:

means for removing a flow in said TCAM by freeing up a corresponding said entry in said flow index space and invalidating a corresponding said TCAM entry.

42. The system of claim 26 wherein said predetermined order of said first partition has one of said TCAM entries with a longest prefix located at an index having highest priority followed by decreasing prefix values with a shortest prefix at an index having lowest priority.

43. The system of claim 28 wherein said second partition is divided into a first is portion and a second portion, said first portion includes indices having highest priority ranging from a lowest index in said second portion to a GACL-partition index and said second portion includes indices having lowest priority ranging from said GACL-partition index to said highest index, said ACL flows are assigned to said first portion and global access list flows are assigned to said second portion.

44. The system of claim 43 wherein said ACL flow specifies a range of source or destination ports, and further comprising:

means for mapping said ACL flow to multiple flows in said TCAM wherein said mask for each of said multiple flows covers a portion of said range of source or destination ports.

45. The system of claim 43 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM.

46. The system of claim 45 further comprising:

means for removing a flow in said ICAM by freeing up a corresponding said entry in said flow index space and invalidating a corresponding said TCAM entry; and

means for compacting said flows in said TCAM by moving each remaining said TCAM entry up by one or more indices.

47. The system of claim 44 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM.

48. The system of claim 47 further comprising:

means for removing said multiple flows in said TCAM by freeing up corresponding said entries in said flow index space and invalidating said corresponding entries in said TCAM entry; and

means for compacting said flows in said TCAM by moving each remaining said 15 TCAM entry up by one or more indices.

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.

52. The apparatus of claim 51 wherein said first plurality of data flows are MPLS or IP-VPN flows.

53. The apparatus of claim 51 wherein said second plurality of data flows are policy based routing flows.

54. The apparatus of claim 51 wherein said partitioning algorithm and said loading algorithm are implemented in flow index space having entries corresponding to said TCAM and said predetermined order of said first TCAM entries and said predetermined order of said second TCAM entries is represented in said flow index space.

55. The apparatus of claim 52 wherein said MPLS or IP-VPN flows are classified by connection index (CIX) and destination address (DA), CIX only or DA only.

56. The apparatus of claim 55 wherein said first partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from said lowest index to a gMaxCixDaFix index and said second portion includes indices having lowest priority ranging from a gMinDaOnlyFix index to said partition index and said flows classified by CIX and DA and CIX only are assigned to said first portion and said flows classified by DA only are assigned to said second portion.

57. The apparatus of claim 56 wherein said flows classified by CIX and DA and flows classified by CIX only are loaded into said first portion starting at a beginning of said TCAM and ending at said gMaxCixDaFix index and said flows classified by said DA only are loaded in said second portion starting at said gMinDaOnlyFix index.

58. The apparatus of claim 52 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM; and

means for assigning said flows classified by CIX to a CIX prefix tree.

59. The apparatus of claim 52 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM; and

means for assigning said flows classified by DA only to a DA prefix tree.

60. The apparatus of claim 59 further comprising:

means for removing a flow in said TCAM by freeing up a corresponding said entry in said flow index space and invalidating a corresponding said TCAM entry.

61. The apparatus of claim 52 wherein said predetermined order of said first partition has one of said TCAM entries with a longest prefix located at an index having highest priority followed by decreasing prefix values with a shortest prefix at an index having lowest priority.

62. The apparatus of claim 53 wherein said second partition is divided into a first portion and a second portion, said first portion includes indices having highest priority ranging from a lowest index in said second partition to a GACL-partition index and said second portion includes indices having lowest priority ranging from said GACL-partition index to said highest index in said second partition, said ACL flows are assigned to said first portion and global access list flows are assigned to said second portion.

63. The apparatus of claim 62 wherein said ACL flow specifies a range of source or destination ports, and further comprising:

means for mapping said ACL flow to multiple flows in said TCAM wherein said mask for each of said multiple flows covers a portion of said range of source or destination ports.

64. The apparatus of claim 62 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM.

65. The apparatus of claim 64 further comprising:

means for removing a flow in said TCAM by freeing up a corresponding said 20 entry in said flow index space and invalidating a corresponding said TCAM entry; and

means for compacting said flows in said TCAM by moving each remaining said TCAM entry up by one index.

66. The apparatus of claim 62 further comprising:

means for maintaining a flow index space having entries corresponding to said TCAM.

67. The apparatus of claim 62 further comprising:

means for removing said multiple flows in said TCAM by freeing up 30 corresponding said entries in said flow index space and invalidating said corresponding entries in said TCAM entry; and

means for compacting said flows in said TCAM by moving each remaining said TCAM entry up by one or more indices.