Other

Clarkson University

The University of Arizona

University of Memphis Research Foundation

Yaoqing Diana Liu

Lan Wang

Garegin Grigoryan

Beichuan Zhang

Xin Zhao

James Jianmin Bao

A system and method for FIB aggregation. FIB Aggregation with Quick Selections (FAQS) is a FIB aggregation algorithm that leverages compact data structures and three unique optimization techniques to quickly and incrementally select next hops when handling route updates. As a result, FAQS can run up to 2.53 and 1.75 times faster for IPv4 and IPv6, respectively, than the optimal FIB aggregation algorithm while achieving a near-optimal aggregation ratio. Meanwhile, it consumes much less memory and generates much smaller number of FIB changes when carrying out frequent updates. The performance enhancement of the new algorithm addresses many concerns from ISPs regarding performance issues, and enhances the probability to push FIB aggregation techniques further to the level of production adoption by the industry.

System and method for FIB aggregation

A Forwarding Information Base (FIB) caching system and scheme that selects and generates a minimal number of non-overlapping prefixes for the FIB cache to improve computer-based network communications and operations efficiency, accuracy and speed. Because the cached prefixes do not cover any longer prefixes in the full FIB, the present invention thus avoids cache-hiding issues. The system further comprises a FIB caching updating component that systematically handles cache misses, cache replacement, and routing updates.

Efficient forwarding information base caching system and method

A system and method for building a data structure for determining if multiple routing or forwarding tables yield the same or different forwarding behaviors. VeriTable uses a single tree/trie traversal to quickly check if multiple forwarding tables are forwarding equivalent, yield routing loops, or black holes. VeriTable also uses the Longest Prefix Matching rule for lookups, e.g., checking if route updates in control plane are consistent with the ones in forwarding plane. VeriTable can be applied to network-wide abnormality diagnosis of network problems, such as scalable and efficient forwarding loop detection and avoidance in the data plane of a network. In addition, VeriTable can be extended to handle incremental updates applied to the forwarding tables in a network.

System and method for building a hierarchical data structure

Networking devices and methods for forwarding information base (FIB) aggregation are provided. A networking device includes a processor operable to access entries in a FIB, and aggregate the FIB entries to produce an aggregated FIB with strong forward correctness. In aggregating the FIB entries, the processor is operable to: (a) associate the FIB entries with nodes (n) in a patricia trie; (b) traverse the patricia trie depth-first in post-order and determine for each node a next-hop set, without expanding the trie, by merging what would be the next-hop sets of its imaginary children nodes if there is a complete binary tree; and (c) traverse the patricia trie depth-first in pre-order, select for the root node a next-hop from its next-hop set and include the FIB entry associated with the root node in the aggregated FIB, for each node having a selected next-hop that appears in its child's next-hop set, select that next-hop for the child as its next-hop and exclude the FIB entry associated with the child node from the aggregated FIB, and for each child node which does not have in its next-hop set the selected next-hop of its parent, select a next-hop from its next-hop set and include the FIB entry associated with the child node in the aggregated FIB.

Devices and methods for forwarding information base aggregation

The invention provides a method of performing one- and two-dimensional electrophoresis with or without gel in an automated way. The two dimensional electrophoresis can be performed either separately or continuously. Both electrokinetic and hydrodynamic forces can be used to facilitate sample transfer from the first to the second dimension. The samples can be detected on-line by using common detectors like UV-Vis, laser induced fluorescence (LIF), and mass spectrometry (MS).

Growing community of inventors

Burlingame, CA, United States of America

Yaoqing Diana Liu