Patent ID: 7948980
Filing Date: 2011-05-24
Classification: H04L

Abstract:
1. A computer-implemented method of classifying packets of data transmitted over a data communications network, the method comprising: providing a memory-storable packet classifier rule defined by a plurality of filters, each filter uniquely corresponding to one of a plurality of actions to be taken in transmitting the data packets over the data communications network; and classifying a data packet according to the packet classifier rule by generating at least one supernode trie subject to a predetermined constraint for reducing accesses to a memory in which the packet classifier rule is stored, wherein generating the at least one supernode trie comprises constructing a minimum height shape-shifting trie (SST) by pruning descendents of a node x in a binary trie T visited during a traversal of T, wherein the pruned descendents of x are mapped into supernodes that form one or more hanging SSTs of the minimum height SST being constructed, the one or more SSTs being left hanging SSTs or right hanging SSTs, wherein constructing the minimum height SST comprises: comparing a maximum SST height in the left hanging SSTs that hang from x when x is visited to a maximum SST height in the right hanging SSTs that hang from x when x is visited, wherein: when the maximum SST height in the left hanging SSTs is equal to the maximum SST height in the right hanging SSTs: when the maximum SST height in the left hanging SSTs is less than the maximum SST height in the right hanging SSTs: when the maximum SST height in the left hanging SSTs is greater than the maximum SST height in the right hanging SSTs: else not pruning T at x.