Patent ID: 8364803
Filing Date: 2013-01-29
Classification: H04L

Abstract:
1. A method for representing a partition of n w-bit intervals associated to d-bit data in a data communications network, said method comprising the steps of: providing in a memory storage device, a datagram forwarding data structure provided for indicating where to forward a datagram in said network, which data structure is a combination of a static block tree (SBT), and a fixed stride trie (FST) to obtain a static hybrid tree, comprising combining the SBT and FST according to a framework that involves algorithm analysis, and storing keys and associated data in the static hybrid tree, reducing worst storage cost by using a technique for reduction of worst case storage cost that are selectable from: partial block tree compaction, virtual blocks, bit push pulling, block aggregation or split block trees, and variations thereof, wherein the technique for reduction of worst case storage cost comprises sub-steps of: performing compaction at each level, starting at level t, and completing the same when the partial node at level 1 has been compacted, wherein mi is the number of additional elements that can be stored in the partially utilized block at level i and j the level of the next partial node to be compacted, wherein initially, before compaction begins, mi=B−ni for all i=1 . . . t and j=t−1, wherein compaction at level i is performed by repeatedly moving the next partial node to the current memory block, wherein this is repeated as long as nj<=mi, wherein for each node moved, mi is decreased by nj followed by decreasing j by 1, wherein mj has to be decreased to B before decreasing j since moving the node at level j effectively frees the whole block at level j, wherein if mi>0 when compaction halts, some space is available, in the current block, for some of the elements from the next partial node but not for the whole node, wherein the first mi elements from the next partial node are moved to the current memory block, which becomes full, and the last nj−mi elements are moved to the beginning of the next memory block, i.e. the block at level i−1, followed by decreasing mi−1 by nj−mi and increasing mj to B, wherein i is increased by 1 and compaction continues at the next level, wherein the final compacted representation is obtained by repeatedly moving the rightmost node to the leftmost free block until all free blocks are occupied; and updating the layered data structure partially by using a technique for scheduling maintenance work that are selectable from: vertical segmentation and bucket list maintenance.