University of Florida Research Foundation, Incorporated

Ut-battelle, Inc.

Sartaj Kumar Sahni

Haibin Lu

Sanjay Ranka

Jonathan Gang Li

Wencheng Lu

Srijit Kamath

Jatinder Palta

Yan Li

Xinyan Zha

Narayana Kamath

Nageswara Sirikonda Venkata Rao

Tania Banerjee

Kun Suk Kim

Jantinder Palta

Eun-Sung Jung

A publish/subscribe system is described that can adjust to provide high performance for diverse application environments through an attribute structure based on predicates of a subscription, each attribute structure with one or more buckets to which attribute values of a subscription may be stored. Various data structures can be used in the attribute structure to locate the buckets containing the subscriptions. The data structures selected for each subscription are based on the attribute type and predicate operators of the subscription.

Efficient publish/subscribe systems

The subject invention provides a data structure and method for IP lookups, insertions, and deletions using a dynamic tree bitmap structure (DTBM) that utilizes an array of child pointers for each node instead of the typical TBM approach using one pointer to an array of children.

Dynamic tree bitmap for IP lookup and update

A method to compress an unoptimized Aho-Corasick automaton is provided that can be used in network intrusion detection systems. Embodiments of the subject method use bitmaps with multiple levels of summaries as well as aggressive path compaction. By using multiple levels of summaries, a popcount can be determined with as few as 1 addition.

Efficient intrusion detection

A connection-oriented network includes a control server. The control server receives requests to establish and utilize dedicated channels in the network. The control server utilizes various scheduling methods and algorithms to determine channels based on the request's requirements and resources of the network. For example, the control server may determine a channel based on: (i) a specified bandwidth in a specified time slot, (ii) highest available bandwidth in a specified time slot, (iii) earliest available time with a specified bandwidth and duration, and (iv) all available time slots with a specified bandwidth and duration.

Method and systems for bandwidth scheduling and path computation for connection-oriented networks

Ternary content-addressable memories (TCAMs) may be used to obtain a simple and very fast implementation of a router's forwarding engine. The applicability of TCAMs is, however, limited by their size and high power requirement. The present invention provides an improved method and associated algorithms to reduce the power needed to search a forwarding table using a TCAM. Additionally, the present invention teaches how to couple TCAMs and high bandwidth SRAMs so as to overcome both the power and size limitations of a pure TCAM forwarding engine. By using one of the novel TCAM-SRAM coupling schemes (M-12Wb), TCAM memory is reduced by a factor of about 5 on IPv4 data sets and by a factor of about 2.5 on IPv6 data sets; TCAM power requirement is reduced by a factor of about 10 on IPv4 data sets and by a factor of about 6 on IPv6 data sets.

Low power ternary content-addressable memory (TCAMs) for very large forwarding tables

A recursively partitioned static router-table, the data structure incorporating a first-level partition including subtries and an auxiliary trie. A node of the subtrie includes a path Q(N) from the root R of a trie T to a root N of the subtrie, a stride s for a next-level partition, a mask that characterizes a next-level perfect hash function, and a pointer to the hash table for the next-level partition. At least one of the trie T, the first-level partition, the auxiliary trie, and the next-level partition is represented by a base structure selected from the group consisting of MBT and HSST.

Recursively partitioned static IP router tables

A computer-implemented method of classifying packets of data transmitted over a data communications network includes providing a memory-storable packet classifier rule defined by a plurality of filters, each filter uniquely corresponding to a 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. A system including a combination of hardware and software modules is provided for carrying out the method. A computer-readable storage medium is also provided for storing a computer program for carrying out the method.

Succinct representation of static packet classifiers

A system for classifying data packets transmitted over a data communications network based upon a set of predetermined prefixes associated with destination addresses of the data packets is provided. The includes a data structure stored in an electronic memory. The data structure is a prefix-in-B-tree (PIBT) data structure and/or a range-in-B-tree (RIBT) data structure, the at least one data structure comprising a plurality of nodes based upon the set of predetermined prefixes. The system also includes a determination module for determining a match between one or more of the plurality of nodes and a destination address of a particular data packet.

System and methods for packet filtering

A method and associated systemfor delivering intensity-modulated radiation therapy (IMRT) uses variable feathering field splitting for intensity modulated fields of large size. A processor controls a beam-shaping device that splits the radiation beam into a plurality of radiation fields delivered to a patient. The processor in cooperation with the beam-shaping device implements a variable feathering method which includes providing an intensity matrix for the treatment of a patient, the intensity matrix having a plurality of rows and columns for spanning a prescribed radiation field including a prescribed field width. The prescribed width is compared to a maximum field width provided by the radiation treatment system. The intensity matrix is split into a plurality of spatially overlapping intensity submatrices by variably feathering the intensity matrix when the prescribed width exceeds the maximum field width, Radiotherapy is then provided to the patient using a leaf sequencing method to generate the submatrices.

Variable feathering field splitting for intensity modulated fields of large size

An improved system and method is provided for packet routing in dynamic router tables. Specifically, the invention provides a method, computer system, and computer readable media for using Priority Search Trees (PSTs) to match, insert, and delete rules in dynamic routing tables in O(log n) time. In a first embodiment, for a dynamic router table consisting of n pairs of tuples, each tuple comprising an address prefix and next-hop information, the invention provides a system and method, using a PST, for inserting a new tuple, deleting an existing tuple, and searching for the tuple with the longest matching prefix for destination address, wherein each operation is performed in O(log n) time. In a second embodiment, for a dynamic router table consisting of n pairs of tuples, each tuple comprising a range of destination addresses and next-hop information, the invention provides a system and method, using a PST and a set of red-black priority search tree (RBPST), for inserting a new tuple, deleting an existing tuple, and searching for the tuple with the most specific matching range, wherein each operation is performed in O(log n) time. The invention can be implemented in numerous ways to improve dynamic router table performance, including as a system, a device, a method, or a computer readable medium.

O(log n) dynamic router tables for prefixes and ranges

An improved system and method is provided for packet routing in dynamic router tables. Specifically, the invention relates to a method and system for using tree data structures to select the highest priority rule that matches a destination address in dynamic Internet packet routing tables. In an embodiment, a data structure called BOB (binary tree on binary tree) for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address is disclosed. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. When an n-rule router table is represented using BOB, the highest-priority rule that matches a destination address may be found in O(logn) time; a new rule maybe inserted and an old one deleted in O(log n) time. For the case when all rule filters are prefixes, the data structure PBOB (prefix BOB) permits highest-priority matching as well as rule insertion and deletion in O(W) time, where W is the length of the longest prefix, each. When all rule filters are prefixes and longest-prefix matching is to be done, the data structures LMPBOB (longest matching-prefix BOB) permits longest-prefix matching in O(W) time; rule insertion and deletion each take O(log n) time. On practical rule tables, BOB and PBOB perform each of the three dynamic-table operations in O(log n) time and with O(log n) cache misses. The number of cache misses incurred by LMPBOB is also O(log n).

Dynamic IP router tables using highest-priority matching

Systems and methods for improving the performance of dynamic router table data structures are provided. The invention relates to methods and systems for partitioning prefixes or prefix-based intervals. In one embodiment, priority search tree router data structures are applied to prefix partitions of the present invention. In another embodiment, basic-interval tree and prefix tree data structures are applied to interval partitions of the present invention.

Partitioning methods for dynamic router tables

A method is provided to improve the performance of dynamic router-table designs. Specifically, the invention relates to a method and system for partitioning prefixes at each node of a partitioning tree into 2+1 partitions using the next s bits of the prefixes. Prefixes that have a length less than s are placed into partition &#x2212;1, with the remaining prefixes falling into the remaining partitions that correspond to the value of their first s bits. Prefix partitioning may be controlled using either static rule tables or by dynamic rule tables. In one embodiment, binary tree on binary tree (BOB) data structures are applied to a partition of the present invention. In another embodiment, prefix binary tree on binary tree (PBOB) data structures are applied to a partition of the present invention. In a further embodiment, a dynamic longest-matching prefix binary tree on binary tree-table (LMPBOB) is applied to a partition of the present invention.

Prefix partitioning methods for dynamic router tables

A method of delivering intensity modulated radiation therapy (IMRT) is disclosed. An intensity profile for the treatment of a patient is provided which spans a prescribed field width and includes a discrete profile having intensity values at each of a plurality of sample points bounded by the prescribed width. The prescribed width is compared to a maximum field width provided by the radiation treatment system. The intensity profile is split into a plurality of intensity profile portions, each having respective widths less than the maximum width if the prescribed width is greater than the maximum width. The prescribed field is also divided into a plurality of different profile portion split arrangements. A monitor unit (MU) efficiency is calculated for each of the arrangements. One of the arrangements is selected for delivery by the system using a leaf sequencing method.

Field splitting for intensity modulated fields of large size

A method of delivering radiation treatment using multi-leaf collimation includes the step of providing a radiation fluence map which includes an intensity profile. The fluence map is converted into a preliminary leaf sequence, wherein the preliminary leaf sequence minimizes machine on-time and is generated without leaf movement constraints. The leaf movement constraint is imposed on the preliminary leaf sequence. At least one constraint elimination algorithm is then applied, the algorithm adjusting the preliminary leaf sequence to minimize violations of the constraint while providing the desired fluence map and minimized radiation on-time. The method can be applied to SMLC and DLMC systems, and can include adjustment for the tongue-and-groove effect.

Growing community of inventors

Gainesville, FL, United States of America

Sartaj Kumar Sahni