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

A classifier device for representing a partition of n w-bit intervals associated to d-bit data in a data communications network in a data communications network, which device comprises:

• a storage for storing a datagram forwarding data structure provided for indicating where to forward a datagram in a network, which data structure is in the form of a tree 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 looking up a largest stored non-negative integer smaller than or equal to a query key;
• means for 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;
• and
• means for 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, which device further comprises means arranged to partition the storage such that the storage is designated to store keys of different sizes, wherein the storage, being a memory, is partitioned such that n1*w1+n2*w2 . . . +nn*wn=S, where n1*W1 is the number of keys of size w1, n2*W2 is the number of keys of size w2, nn*Wn is the number of keys of size wn and S is the total amount of storage available.