METHOD, DEVICE AND COMPUTER PROGRAM PRODUCT FOR REPRESENTING A PARTITION OF N W-BIT INTERVALS ASSOCIATED TO D-BIT DATA IN A DATA COMMUNICATIONS NETWORK

摘要

The present invention relates to a method for routing in a data communications network, comprising the steps of providing in a storage having a certain amount of storage capacity, a datagram forwarding data structure provided for indicating where to forward a datagram in said network, which data structure is in the form of a block tree, or fixed stride trie, comprising at least one leaf and possibly a number of nodes including partial nodes, said data structure having a height, corresponding to a number of memory accesses required for lookup in an arbitrary partition comprising n intervals, 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 by using a technique for scheduling maintenance work that are selectable from: vertical segmentation and bucket list maintenance, step 203, further comprising the step of using a certain maximum amount of storage capacity for storing a maximal number of keys having a particular size, step 204.