Method and apparatus for building and using multi-dimensional index trees for multi-dimensional data objects

• US 6,859,455 B1
• Filed: 11/10/2000
• Issued: 02/22/2005
• Est. Priority Date: 12/29/1999
• Status: Expired due to Fees

• Current Assignee: Nasser Yazdani, Paul Seungkyu Min
• Original Assignee: Nasser Yazdani, Paul Seungkyu Min
• Inventors: Min, Paul Seungkyu, Yazdani, Nasser
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): George, Keith M.
• Application Number:
  US09/710,193
• Time in Patent Office: 1,565 Days
• Field of Search: 370/389, 370/401, 370/392, 370/402, 707/6, 707/7, 707/103.R, 707/103.Y, 707/103.Z
• US Class Current: 370/392
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• 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/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A method and apparatus are provided for building a searchable multi-dimensional index tree that indexes a plurality of data objects. In one aspect of the invention, the index tree divides dataspace into three subspaces and indexes the data objects using a single dimension. If too many data objects map to the same point in that dimension, the dimension is switched to a new dimension of the data object and the data object is indexed using the new dimension. A split node having a split value is used to keep track of the indexing. In another aspect of the invention, the index tree divides dataspace into two subspaces, and equal bits are used in the split nodes to track the content of the data objects in the subspaces. If too many data objects sharing the same key within the same dimension map to a single point, then the dimension is switched to a new dimension and the data objects are indexed using the new dimension. Also disclosed is the multi-dimensional index tree itself as well as a router that uses the multi-dimensional index tree of the present invention to provide packet classification functions.

Claims

1. A method of building a multi-dimensional index tree for use in searching for data objects;

said method comprising;

a) placing a data object into an appropriate leaf node, said leaf node having a predetermined capacity for data objects, each of said data objects having a plurality of keys, each of said keys being associated with a split dimension;

b) dividing said leaf node into N subtrees when said leaf node is filled with a number of data objects exceeding said capacity, each of said subtrees having a predetermined capacity for data objects, wherein N is at least two;

c) indexing said data objects in said excessively-filled leaf node into an appropriate subtree on the basis of a first split dimension if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said first split dimension or on the basis of a different split dimension if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of said first split dimension; and

d) repeating steps a) through c) until all data objects presented for placement have been indexed, wherein each of said subtrees is treated as a leaf node on each successive pass.

2. The method of claim 1 wherein step c) further comprises:

i) if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said keys in said data objects associated with a first split dimension, then;

A) splitting said data objects in said excessively-filled leaf node on the basis of a key within each of said data objects associated with said first split dimension;

B) if said split of data objects is an initial split, then creating a split node associated with said first split dimension pointing to each of said subtrees;

C) if said split of data objects is not an initial split, then supplementing said split node created upon said initial split with pointers pointing to each of said subtrees; and

D) placing each of said data objects in said excessively-filled leaf node into an appropriate subtree;

ii) if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of a first split dimension, then;

A) changing said first split dimension to a new split dimension under which said data objects in said excessively-filled leaf node can be identifiably separated;

B) splitting said data objects in said excessively-filled leaf node on the basis of a key within each of said data objects associated with said new split dimension;

C) creating a split node associated with said new split dimension pointing to each of said subtrees; and

D) placing each of said data objects in said excessively-filled leaf node into an appropriate subtree; and

wherein on each successive pass, if a split node is pointing to a subtree, said first split dimension for said subtree is said split dimension associated with said split node pointing to said subtree.

3. The method of claim 2 wherein N is three, said three subtrees being a first subtree, a second subtree, and a third subtree.

4. The method of claim 3 wherein steps c)i)B) and c)ii)C) further comprise determining a split value for said split node, said split node having a space occupied by a pointer pointing to said first subtree, a space occupied by said split value, a space occupied by a pointer pointing to said second subtree, and a space occupied by a pointer pointing to said third subtree.

5. The method of claim 4 wherein step c)i)C) further comprises determining a supplemental split value for said split node, said split node further having a space occupied by a pointer pointing to said first subtree, a space occupied by said supplemental split value, a space occupied by a pointer pointing to said second subtree, and a space occupied by a pointer pointing to said third subtree.

6. The method of claim 5 wherein steps c)i)D) and c)ii)D) further comprise placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split less than said split value into said first subtree, placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split equal to said split value into said second subtree, and placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split greater than said split value into said third subtree.

7. The method of claim 6 further comprising determining a match type by checking a split table, said match type determination depending upon said split dimension under which said data objects were split, and wherein said split value determinations depend upon said determined match type.

8. The method of claim 7 wherein said determined match type is selected from one of a group consisting of exact matching, range matching, and prefix matching.

9. The method of claim 2 further comprising choosing a first split dimension for an initial split of data objects on the basis of discrimination ratios assigned to each split dimension associated with said plurality of keys in said data objects, wherein said first split dimension is that split dimension with the largest discrimination ratio.

10. The method of claim 9 further comprising choosing said new split dimension on the basis of said discrimination ratios, wherein said new split dimension is that split dimension with the next-largest discrimination ratio under which said data objects needing to be split can be identifiably separated.

11. The method of claim 2 wherein N is two, said two subtrees being a first subtree and a second subtree.

12. The method of claim 11 wherein steps c)i)B) and c)ii)C) further comprise determining a split value for said split node, said split node having a space occupied by a first equal bit, a space occupied by a pointer pointing to said first subtree, a space occupied by said split value, a space occupied by a second equal bit, and a space occupied by a pointer pointing to said third subtree.

13. The method of claim 12 wherein step c)i)C) further comprises determining a supplemental split value for said split node, said split node further having a space occupied by a first equal bit, a space occupied by a pointer pointing to said first subtree, a space occupied by said supplemental split value, a space occupied by a second supplemental equal bit, and a space occupied by a pointer pointing to said second subtree.

14. The method of claim 13 further comprising determining a match type by checking a split table, said match type determination depending upon said split dimension under which said data objects were split, and wherein said split value determination depends upon said determined match type.

15. The method of claim 13 wherein steps c)i)D) and c)ii)D) further comprise placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split less than or equal to said split value into said first subtree, and placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split greater than said split value into said second subtree.

16. The method of claim 15 wherein if data objects within an excessively-filled first subtree are split under step c)ii), said method further comprising the step of setting said first equal bit associated with said excessively-filled first subtree in said split node pointing to said excessively-filled first subtree.

17. The method of claim 15 wherein if data objects within an excessively-filled second subtree are split under step c)ii), said method further comprising the step of setting said second equal bit associated with said excessively-filled second subtree in said split node pointing to said excessively-filled second subtree.

18. The method of claim 15 wherein if a rightmost subtree problem exists, then performing a rightmost subtree node reconfiguration.

19. The method of claim 15 wherein if an enclosure overflow problem exists, then performing a previous split value adjustment.

20. The method of claim 15 wherein if an equal bit subtree problem exists, then performing an equal subtree insertion procedure.

21. The method of claim 1 wherein said predetermined capacity for data objects is ten data objects.

22. The method of claim 1 wherein said predetermined capacity for data objects is sixteen data objects.

23. The method of claim 1 further comprising the step of searching said index tree for a data object matching a query object.

24. The method of claim 23 wherein said searching step includes searching said index tree for a data object that is an exact match of said query object.

25. The method of claim 23 wherein said searching step includes searching said index tree for all data objects that are a range match of said query object.

26. The method of claim 23 wherein said searching step includes searching said index tree for all data objects that are a prefix match of said query object.

27. The method of claim 1 wherein said data objects are IP packet classification rules.

28. The method of claim 27 wherein said IP packet classification rules have keys associated with a plurality of split dimensions, said split dimensions comprising a destination address, a source address, a destination port, a source port, and a protocol.

29. A computer configured to build a multi-dimensional index tree for use in searching data objects;

said computer comprising;

a) dataspace comprising a plurality of leaf nodes, said leaf nodes capable of being recursively divided into a plurality of subtrees;

b) means for placing a data object into an appropriate leaf node, said leaf node having a predetermined capacity for data objects, each of said data objects having a plurality of keys, each of said keys being associated with a split dimension;

c) means for dividing said leaf node into N subtrees when said leaf node is filled with a number of data objects exceeding said capacity, each of said subtrees having a predetermined capacity for data objects, wherein N is at least two;

d) means for indexing said data objects in said excessively-filled leaf node into an appropriate subtree on the basis of a first split dimension if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said first split dimension or on the basis of a different split dimension if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of said first split dimension; and

e) means for repeating said functions of means b), c), and d) until all data objects presented for indexing have been placed, wherein each of said subtrees is treated as a leaf node on each successive pass.

30. The computer of claim 29 wherein said means d) further comprises:

i) means for splitting said data objects in said excessively-filled leaf node on the basis of a key within each of said data objects associated with said first split dimension if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said keys in said data objects associated with a first split dimension;

ii) means for creating a split node associated with said first split dimension pointing to each of said subtrees if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said keys in said data objects associated with a first split dimension and said split of data objects is an initial split;

iii) means for supplementing said split node pointing created upon said initial split with pointers pointing to each of said subtrees if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said keys in said data objects associated with a first split dimension and if said split of data objects is not an initial split;

iv) means for changing said first split dimension to a new split dimension under which said data objects in said excessively-filled leaf node can be identifiably separated if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of a first split dimension;

v) means for creating a split node associated with said new split dimension pointing to each of said subtrees, if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of a first split dimension;

vi) means for splitting said data objects in said excessively-filled leaf node on the basis of a key within each of said data objects associated with said new split dimension, if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of a first split dimension;

vii) means for placing each of said data objects in said excessively-filled leaf node into an appropriate subtree; and

wherein on each successive pass, if a split node is pointing to a subtree, said first split dimension for said subtree is said split dimension associated with said split node pointing to said subtree.

31. The computer of claim 30 wherein N is three, said three subtrees being a first subtree, a second subtree, and a third subtree.

32. The computer of claim 31 wherein means d)ii) and d)v) further comprise means for determining a split value for said split node, said split node having a space occupied by a pointer pointing to said first subtree, a space occupied by said split value, a space occupied by a pointer pointing to said second subtree, and a space occupied by a pointer pointing to said third subtree.

33. The computer of claim 32 wherein means d)iii) further comprises means for determining a supplemental split value for said split node, said split node further having a space occupied by a pointer pointing to said first subtree, a space occupied by said supplemental split value, a space occupied by a pointer pointing to said second subtree, and a space occupied by a pointer pointing to said third subtree.

34. The computer of claim 33 wherein means d)vii) further comprises means for placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split less than said split value into said first subtree, means for placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split equal to said split value into said second subtree, and means for placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split greater than said split value into said third subtree.

35. The computer of claim 33 further comprising a split table and wherein means d)ii), d)iii), and d)v) further comprise means for determining a match type by checking said split table, said match type determination depending upon said split dimension under which said data objects were split, and wherein said split value determination depends upon said determined match type.

36. The computer of claim 35 wherein said determined match type is selected from on of a group consisting of exact matching, range matching, and prefix matching.

37. The computer of claim 30 further comprising means for choosing a first split dimension for an initial split of data objects on the basis of a discrimination ratio assigned to each split dimension associated with said plurality of keys in said data objects, wherein said first split dimension is that split dimension with the largest discrimination ratio.

38. The computer of claim 37 further comprising means for choosing said new split dimension on the basis of said discrimination ratios, wherein said new split dimension is that split dimension with the next-largest discrimination ratio under which said data objects needing to be split can be identifiably separated.

39. The computer of claim 30 wherein N is two, said two subtrees being a first subtree and a second subtree.

40. The computer of claim 39 wherein means d)i) and d)iv) further comprise means for determining a split value for said split node, said split node having a space occupied by a first equal bit, a space occupied by a pointer pointing to said first subtree, a space occupied by said split value, a space occupied by a second equal bit, and a space occupied by a pointer pointing to said third subtree.

41. The computer of claim 40 wherein means d)iii) further comprises means for determining a supplemental split value for said split node, said split node further having a space occupied by a supplemental first equal bit, a space occupied by a pointer pointing to said first subtree, a space occupied by said supplemental split value, a space occupied by a supplemental second equal but, and a space occupied by a pointer pointing to said second subtree.

42. The computer of claim 41 further comprising a split table and wherein said means d)i, d)iii), and d)v) further comprise means determining a match type by checking said split table, said match type determination depending upon said split dimension under which said data objects were split, and wherein said split value determination depends upon said determined match type.

43. The computer of claim 41 wherein means d)vii) further comprises means for placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split less than or equal to said split value into said first subtree, and means for placing each data object in said excessively-filled leaf node having a key associated with said split dimension under which said data objects were split greater than said split value into said second subtree.

44. The computer of claim 43 wherein if data objects within an excessively-filled first subtree are split by means d)vi), said computer further comprising means for setting said first equal bit associated with said excessively-filled first subtree in said split node pointing to said excessively-filled first subtree.

45. The computer of claim 43 wherein if data objects within an excessively-filled second subtree are split by means d)vi), said computer further comprising means for setting said second equal bit associated with said excessively-filled second subtree in said split node pointing to said excessively-filled second subtree.

46. The computer of claim 43 wherein means d) further comprises means for performing a rightmost subtree node reconfiguration, said reconfiguration occurring if a rightmost subtree problem exist.

47. The computer of claim 43 wherein means d) further comprises means for performing a previous split value adjustment, said adjustment occurring if an enclosure overflow problem exists.

48. The computer of claim 43 wherein means d) further comprises means for performing an equal subtree insertion procedure, said procedure occurring if an equal bit subtree problem exists.

49. The computer of claim 29 wherein said predetermined capacity for data objects is ten data objects.

50. The computer of claim 29 wherein said predetermined capacity for data objects is sixteen data objects.

51. The computer of claim 29 further comprising means for searching said index tree for a data object matching a query object.

52. The computer of claim 51 wherein said searching means includes means for searching said index tree for a data object that is an exact match of said query object.

53. The computer of claim 51 wherein said searching means includes means for searching said index tree for all data objects that are a range match of said query object.

54. The computer of claim 51 wherein said searching means includes means for searching said index tree for all data objects that are a prefix match of said query object.

55. The method of claim 29 wherein said data objects are IP packet classification rules.

56. The method of claim 55 wherein said IP packet classification rules have keys associated with a plurality of split dimensions, said split dimensions comprising a destination address, a source address, a destination port, a source port, and a protocol.

57. A database indexing a plurality of multi-dimensional data objects on a plurality of a dimensions, said database comprising:

a) a upper level comprising;

i) an upper level split node having at least one split value, said upper level split node having pointers pointing to each upper level subtree, and said upper level split node having at least one pointer pointing to a split node in a lower level;

ii) at least N upper level subtrees, each of said upper level subtrees being associated with an upper level split value;

iii) a plurality of indexed upper level data objects, each of said upper level data objects having a plurality of keys, each of said keys being associated with a different split dimension; and

wherein each of said upper level data objects are indexed into said upper level subtrees on the basis of a key within said upper level data objects, said key being associated with a split dimension for said upper level; and

b) a lower level comprising;

i) at least one lower level split node having at least one split value, said lower level split node having pointers pointing to each lower level subtree;

ii) at least M lower level subtrees, each of said lower level subtrees being associated with a lower level split dimension;

iii) a plurality of indexed lower level data objects, each of said lower level data objects having a plurality of keys, each of said keys being associated with a different split dimension; and

wherein each of said lower level data objects are indexed into said lower level subtrees on the basis of a key within said lower level data objects, said key being associated with a split dimension for said lower level, said lower level split dimension being different than said upper level split dimension.

58. The database of claim 57 wherein N is two.

59. The database of claim 58 wherein upper level data objects having a key associated with said upper level split dimension less than a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys less than said upper level split value.

60. The database of claim 58 wherein upper level data objects having a key associated with said upper level split dimension greater than a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys greater than said upper level split value.

61. The database of claim 58 wherein upper level data objects having a key associated with said upper level split dimension equal to a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys equal to said upper level split value.

62. The database of claim 57 wherein M is three.

63. The database of claim 62 wherein lower level data objects having a key associated with said lower level split dimension less than a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys less than said lower level split value.

64. The database of claim 62 wherein lower level data objects having a key associated with said lower level split dimension greater than a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys greater than said lower level split value.

65. The database of claim 62 wherein lower level data objects having a key associated with said lower level split dimension equal to a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys equal to said lower level split value.

66. The database of claim 57 wherein N is one and said upper level split node further comprises at least one space occupied by a first equal bit and at least one space occupied by a second equal bit.

67. The database of claim 66 wherein upper level data objects having a key associated with said upper level split dimension less than or equal to a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys less than or equal to said upper level split value.

68. The database of claim 66 wherein upper level data objects having a key associated with said upper level split dimension greater than a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys greater than said upper level split value.

69. The database of claim 66 wherein any equal bit having an association with a pointer pointing to a lower level split node is set.

70. The database of claim 57 wherein M is two and said lower level split node further comprises at least one space occupied by a first equal bit and at least one space occupied by a second equal bit.

71. The database of claim 70 wherein lower level data objects having a key associated with said lower level split dimension less than or equal to a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys less than or equal to said lower level split value.

72. The database of claim 70 wherein lower level data objects having a key associated with said lower level split dimension greater than a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys greater than said lower level split value.

73. The database of claim 57 wherein each of said upper level and lower level subtrees have a predetermined capacity for data objects.

74. A router for forwarding data packets, said router comprising:

a) a searchable multi-dimensional index tree, said multi-dimensional index tree comprising

i) a upper level comprising;

A) an upper level split node having at least one split value, said upper level split node having pointers pointing to each upper level subtree, and said upper level split node having at least one pointer pointing to a split node in a lower level;

B) at least N upper level subtrees, each of said upper level subtrees being associated with an upper level split value;

C) a plurality of indexed upper level data objects, each of said upper level data objects having a plurality of keys, each of said keys being associated with a different split dimension; and

wherein each of said upper level data objects are indexed into said upper level subtrees on the basis of a key within said upper level data objects, said key being associated with a split dimension for said upper level; and

ii) a lower level comprising;

A) at least one lower level split node having at least one split value, said lower level split node having pointers pointing to each lower level subtree;

B) at least M lower level subtrees, each of said lower level subtrees being associated with a lower level split dimension;

C) a plurality of indexed lower level data objects, each of said lower level data objects having a plurality of keys, each of said keys being associated with a different split dimension; and

wherein each of said lower level data objects are indexed into said lower level subtrees on the basis of a key within said lower level data objects, said key being associated with a split dimension for said lower level, said lower level split dimension being different than said upper level split dimension; and

b) a search engine for searching said index tree to find an indexed data object matching a received data packet.

75. The router of claim 74 wherein N is two and M is three, and wherein upper level data objects having a key associated with said upper level split dimension less than a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys less than said upper level split value, and wherein upper level data objects having a key associated with said upper level split dimension greater than a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys greater than said upper level split value, and wherein upper level data objects having a key associated with said upper level split dimension equal to a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys equal to said upper level split value, and wherein lower level data objects having a key associated with said lower level split dimension less than a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys less than said lower level split value, and wherein lower level data objects having a key associated with said lower level split dimension greater than a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys greater than said lower level split value, and wherein lower level data objects having a key associated with said lower level split dimension equal to a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys equal to said lower level split value.

76. The router of claim 74 wherein N is one, M is two, and said each of said upper level and lower level split nodes further comprise at least one space occupied by a first equal bit and at least one space occupied by a second equal bit, and wherein upper level data objects having a key associated with said upper level split dimension less than or equal to a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys less than or equal to said upper level split value, and wherein upper level data objects having a key associated with said upper level split dimension greater than a split value in said upper level split node are indexed into an upper level subtree reserved for upper level data objects having keys greater than said upper level split value, and wherein any equal bit having an association with a pointer pointing to a lower level split node is set, and wherein lower level data objects having a key associated with said lower level split dimension less than or equal to a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys less than or equal to said lower level split value, and wherein lower level data objects having a key associated with said lower level split dimension greater than a split value in said lower level split node are indexed into a lower level subtree reserved for lower level data objects having keys greater than said lower level split value.

77. The router of claim 74 further comprising an index builder for building said multi-dimensional index tree, said index builder comprising:

i) means for placing a data object into an appropriate leaf node, said leaf node having a predetermined capacity for data objects, each of said data objects having a plurality of keys, each of said keys being associated with a split dimension;

ii) means for dividing said leaf node into N subtrees when said leaf node is filled with a number of data objects exceeding said capacity, each of said subtrees having a predetermined capacity for data objects, wherein N is at least two;

iii) means for indexing said data objects in said excessively-filled leaf node into an appropriate subtree on the basis of a first split dimension if said data objects in said excessively-filled leaf node can be identifiably separated on the basis of said first split dimension or on the basis of a different split dimension if said data objects in said excessively-filled leaf node cannot be identifiably separated on the basis of said first split dimension; and

iv) means for repeating said functions of means i), ii), and iii) until all data objects presented for indexing have been placed, wherein each of said subtrees is treated as a leaf node on each successive pass.

78. The router of claim 74 wherein said data objects are IP packet classification rules.

79. The router of claim 78 wherein said IP packet classification rules have keys associated with a plurality of split dimensions, said split dimensions comprising a destination address, a source address, a destination port, a source port, and a protocol.

80. The router of claim 78 further comprising a forwarding engine, said forwarding engine switching data packets in layer 3 of the TCP/IP protocol.

81. The router of claim 78 further comprising a forwarding engine, said forwarding engine switching data packets in layer 4 of the TCP/IP protocol.

82. The router of claim 78 further comprising a forwarding engine, said forwarding engine providing differentiated service on the basis of a matching IP packet classification rule.