Patent ID: 8401015

Claim:
A classifier device for representing a partition of n w-bit intervals associated to d-bit data 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 first 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 means for updating the layered data structure partially including by using a second technique for scheduling maintenance work that are selectable from: vertical segmentation and bucket list maintenance, wherein the means for reducing worst storage cost and the means for updating the layered data structure partially are implemented in a classification chip comprising classifier lookup structure.