Patent attributes
A method and system for tracking data packets that utilizes a tree data structure with a recursive pruning algorithm that collapses the branches of the tree that represent contiguous ranges or regions to maintain a minimally optimum memory size. Each contiguous region is identified by a node, which includes the start and end range of packets. Each node further includes left and right pointer elements, which point to adjacent lower and higher nodes, respectively. When a packet sequence number is not contiguous with any other sequence numbers previously received, a new node is created that contains only a single value range. When a new packet is received that has a contiguous sequence number (i.e., immediately preceding or succeeding sequence number), the original node is updated so as to reflect the new contiguous range. Additionally, if this new contiguous range is contiguous with another node's range, the two nodes are “collapsed” into a new single node containing the new expanded contiguous range. Furthermore, the algorithm can quickly and efficiently determine whether there are any missing packets by simply determining if there is only a single node remaining after a designated “last packet” has been received.
