# US 7,613,134 B2 · Method and apparatus for storing tree data structures among and within multiple memory channels > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,134 B2 - Document ID: US7613134B2 - Status: Granted - Kind: B2 - Application number: 12/059,329 - Filed: 2008-03-31 - Published: 2008-07-31 - Granted: 2009-11-03 - Earliest claimed: 2003-01-31 - Assignees: Cisco Technology, Inc. - Inventors: Vijay Rangarajan; Shyamsundar N. Maniyar; William N. Eatherton - Web page: https://patentgrep.com/patent/US7613134B2 ## CPC - H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) - G06F 16/9027: {Trees} - G06F 16/90344: {by using string matching techniques} - H04L 45/54: {Organization of routing tables} - H04L 45/74591: {using content-addressable memories [CAM]} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and apparatus are disclosed for storing tree data structures among and within multiple memory channels, which may be of particular use with, but not limited to tree bitmap data structures. A subtree (or entire tree) typically includes one or more leaf arrays and multiple tree arrays. One or more leaf arrays are typically stored in a first set of memory channels of N+1 sets of memory channels, the N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels. Each of N contiguous levels of the multiple tree arrays are stored in a different one of said N sets of memory channels, wherein each of the multiple tree arrays at a same level of said N contiguous levels is stored in the same memory channel set of said N sets of memory channels. A memory channel for storing a particular level is typically assigned based on one or more current occupancy levels of the memory channels. ## Claims ### Claim 1 A method for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, the method comprising: storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels; and storing each of N contiguous levels of the plurality of tree arrays in a different one of said N sets of memory channels, wherein each of the plurality of tree arrays at a same level of said N contiguous levels is stored in the same memory channel set of said N sets of memory channels; wherein which of said N sets of memory channels to store which of said N contiguous levels of the plurality of tree arrays is determined based on one or more occupancy levels of one or more of said N sets of memory channels, where said one or more occupancy levels correspond to an amount of free space in said one or more of said N sets of memory channels. ### Claim 2 (depends on 1) The method of claim 1, comprising identifying the first set of memory channels of said N+1 sets of memory channels based on an occupancy level of said N+1 sets of memory channels. ### Claim 3 (depends on 2) The method of claim 2, wherein the first set of memory channels includes the most available space of said N+1 sets of memory channels when said identifying the first set of memory channels is performed. ### Claim 4 (depends on 2) The method of claim 2, wherein the first set of memory channels includes the least available space of said N+1 sets of memory channels when said identifying the first set of memory channels is performed. ### Claim 5 (depends on 1) The method of claim 1, comprising selecting a particular memory channel set of said N sets of memory channels to store a particular one of the plurality of tree arrays, the particular memory channel set including the most available space of said N sets of memory channels at time of said selecting the particular memory channel set. ### Claim 6 (depends on 1) The method of claim 1, comprising selecting a particular memory channel set of said N sets of memory channels to store a particular one of the plurality of tree arrays, the particular memory channel set including the least available space of said N sets of memory channels at time of said selecting the particular memory channel set. ### Claim 7 (depends on 1) The method of claim 1, wherein each of said N+1 sets of memory channels comprises a single memory channel. ### Claim 8 (depends on 1) The method of claim 1, wherein said storing one or more leaf arrays includes identifying a block of memory in an unused block data structure. ### Claim 9 (depends on 1) The method of claim 1, wherein said storing one or more leaf arrays includes: identifying that there is no block of memory indicated as available in an unused block data structure; and allocating a new memory page in the first set of memory channels. ### Claim 10 (depends on 1) The method of claim 1, wherein said storing each of N contiguous levels of the plurality of tree arrays includes identifying a block of memory in an unused block data structure. ### Claim 11 (depends on 1) The method of claim 1, wherein said storing each of N contiguous levels of the plurality of tree arrays includes: identifying that there is no block of memory indicated as available in an unused block data structure; and allocating a new memory page in one of said N sets of memory channels. ### Claim 12 (depends on 1) The method of claim 1, further comprising: initiating a memory compaction operation in response to an occupancy or a fragmentation level of at least one of said N sets of memory channels. ### Claim 13 (depends on 12) The method of claim 12, wherein said memory compaction operation includes storing a group of all said tree arrays stored in a single one of said N sets of memory channels which requires a largest storage space of that required by groups of all said leaf arrays stored in any one of the N sets of memory channels in a particular one of said N sets of memory channels having a greatest amount of storage space available for storing tree arrays. ### Claim 14 (depends on 12) The method of claim 12, wherein said memory compaction operation includes: identifying an available space ordering based on an occupancy level of each of said N sets of memory channels; identifying a storage requirement ordering based on the storage requirement of each of the plurality of tree arrays; and storing the plurality of tree arrays in said N sets of memory channels based on the available space and storage requirement orderings. ### Claim 15 (depends on 1) The method of claim 1, further comprising: initiating a memory compaction operation in response to an occupancy or a fragmentation level of the first set of memory channels. ### Claim 16 (depends on 1) The method of claim 1, further comprising: initiating a memory compaction operation in response to an occupancy or a fragmentation level of at least one of said N+1 sets of memory channels. ### Claim 17 (depends on 16) The method of claim 16, wherein said memory compaction operation includes: identifying whether (1) a tree array storage requirement for a group of all said tree arrays stored in a single one of said N sets of memory channels which requires a largest storage space of that required by groups of all said leaf arrays stored in any one of the N sets of memory channels or (2) a leaf array storage requirement for said one or more leaf arrays requires more storage space; and storing the group of said one or more leaf arrays identified as requiring more storage space in a particular one of said N+1 sets of memory channels having a greatest amount of storage space available. ### Claim 18 (depends on 16) The method of claim 16, wherein said memory compaction operation includes: identifying an available space ordering based on an occupancy level of each of said N+1 sets of memory channels; identifying a storage requirement ordering based on the storage requirement of each of the plurality of tree arrays and said one or more leaf arrays; and storing the plurality of tree arrays and said one or more leaf arrays in said N+1 sets of memory channels based on the available space and storage requirement orderings. ### Claim 19 An apparatus for storing a subtree in memory, the subtree including one or more leaf arrays and a plurality of tree arrays, the apparatus comprising: means for storing said one or more leaf arrays in a first set of memory channels of N+1 sets of memory channels, said N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels; and means for storing each of N contiguous levels of the plurality of tree arrays in a different one of said N sets of memory channels, wherein each of the plurality of tree arrays at a same level of said N contiguous levels is stored in the same memory channel set of said N sets of memory channels; wherein which of said N sets of memory channels to store which of said N contiguous levels of the plurality of tree arrays is determined based on one or more occupancy levels of one or more of said N sets of memory channels, where said one or more occupancy levels correspond to an amount of free space in said one or more of said N sets of memory channels. ### Claim 20 (depends on 19) The apparatus of claim 19, comprising means for identifying the first set of memory channels of said N+1 sets of memory channels based on an occupancy level of said N+1 sets of memory channels. ### Claim 21 (depends on 19) The apparatus of claim 19, comprising means for performing a memory compaction operation on the subtree. ### Claim 22 An apparatus for storing items, the apparatus comprising: a first memory channel for storing one or more first level internal nodes of a subtree; a second memory channel for storing one or more second level internal nodes of the subtree, wherein said one or more second level internal nodes are child of said one or more first level internal nodes; a third memory channel for storing one or more third level internal nodes of the subtree, wherein said one or more third level internal nodes are child of said one or more second level internal nodes; a fourth memory channel for storing one or more fourth level internal nodes of the subtree, wherein said one or more fourth level internal nodes are child of said one or more third level internal nodes; a fifth memory channel for storing one or more leaf arrays of the subtree; and a memory manager coupled to the first memory channel, the second memory channel, the third memory channel, the fourth memory channel, and the fifth memory channel; wherein the memory manager stores said one or more leaf arrays of the subtree in the fifth memory channel and stores N contiguous levels of internal nodes in the first, second, third, and fourth memory channels, wherein each internal node at a same level of said N contiguous levels is stored in the same one of the first, second, third, and fourth memory channels; and wherein which of said first, second, third, and fourth memory channels to store which of said N contiguous levels of internal nodes is determined based on one or more occupancy levels of said first, second, third, and fourth memory channels, where said one or more occupancy levels correspond to an amount of free space in one or more of said first, second, third, and fourth memory channels.