W-bit intervals partition representing method for use in classifier device, involves partially updating layered data structure to schedule maintenance work i.e. vertical segmentation and bucket list maintenance

摘要

The method involves providing datagram forwarding data structure in a memory. A location for forwarding a datagram in data communication network is indicated by the data structure, where a height of the data structure corresponds to a number of memory accesses required for lookup in an arbitrary partition. A worst storage cost is controlled using partial block tree compaction, virtual blocks, bit push pulling, block aggregation or split block trees and variations. A layered data structure is partially updated to schedule maintenance work i.e. vertical segmentation and bucket list maintenance. Independent claims are also included for the following: (1) a system for representing a partition of n w-bit intervals associated to d-bit data in a data communication network (2) a computer program product comprising instructions for performing a method for representing a partition of n w-bit intervals associated to d-bit data in a data communication network.