| 摘要 |
The present invention relates to 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 (102), a datagram forwarding data structure (10) provided for indicating where to forward a datagram in said network, which data structure (10) is in the form of a tree comprising at least one leaf (11) and possibly a number of nodes (13) including partial nodes, said data structure (10) having a height (h), corresponding to a number of memory accesses required for looking up a largest stored non-negative integer smaller than or equal to a query key, step 201, 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, step 202, updating the layered data structure partially including by using a technique for scheduling maintenance work that are selectable from: vertical segmentation and bucket list maintenance, and providing a hybrid structure by using a technique that are selectable from cluster monitoring, path compression, prefix pointer encoding to provide a static hybrid block tree, step 203. |
