BioCAM®

BioCAM® by Oricane is a family of network search algorithms and management software for the next generation network equipment.

 

BioCAM® Search

The BioCAM® Search Algorithm accelerates classification and forwarding of Internet traffic, providing a high-speed-high-density alternative to Ternary Content-Addressable Memories (TCAMs). The BioCAM® Search Algorithm has native support for IPv4/IPv6 Longest Prefix Match (LPM) and IPv4/IPv6 Multi Field Classification (MFC) for ACL/SDN type classification.

BioCAM® Manager

BioCAM® Manager is a software toolkit provided by Oricane. It interfaces via an Open Flow compatible Control Plane API which exposes the core MFC and LPM functionality and easily connects to SDN Controllers, ACL Managers and Routing Daemons. BioCAM® Manager’s responsibility is to build, update, and maintain the data structures on the device without interfering with the Data Plane operation.

It features automated adversarial algorithm analysis and on-the-fly optimization to achieve the best performance-compression-trade-off at all times. BioCAM® Manager features a Hardware Abstraction Layer (HAL) to connect to the device through several architectural layers depending on the target system architecture.

 

Longest Prefix Matching

BioCAM® supports high-speed-high-density Longest Prefix Matching (LPM) with guaranteed search speed and density. The BioCAM® Forwarding Information Base (FIB) Configuration is tailored for each target scenario while taking into account block size (i.e. burst size, cache line size, memory access width), tick rate (i.e. burst rate, memory clocking), maximum prefix size and maximum number of prefixes. Larger block size yields a tighter search cost budget, i.e. maximum number of memory accesses, and thus higher guaranteed search speed, whereas larger maximum prefix size requires a slightly higher search cost budget. For a given configuration, both the search speed and density is guaranteed. That is, even a prefix set deliberatively crafted to break the algorithm will not bust the search cost- or memory budget…, not even if the prefix is crafted by an adversary with full knowledge of how the algorithm works.

Example: In a system with 64-byte block size (e.g. DDR3 with 64-byte burst), BioCAM® packs 14 million IPv4 prefixes into 122 Mbyte of memory and performs the LPM search in at most three (3) memory accesses. The corresponding for IPv6 is: 5,7 million (up to) 64-bit prefixes in 108 Mbyte and LPM search in at most five (5) memory accesses and 3 million (up to) 128-bit prefixes in 119 MB and LPM search in at most eight (8) memory accesses.

BioCAM® LPM Search runs on standard PC platforms where it takes advantage of the large burst size, cache hierarchy and huge memory to achieve moderate search speed represent very large prefix sets. It has also been ported to proprietary multi-core NPUs where the tight search cost budget contributes to fully saturate the memory interfaces and achieve very high search speeds.

 

Multiple Field Classification

BioCAM® supports high-speed-high-density Multiple Field Classification (MFC) featuring excellent trade-off between search speed and table density. While MFC is considerably more complex than LPM when dealing with large density requirements and tight memory constraints, BioCAM® features a method of partitioning entries into clusters where each cluster is stored compactly yet supporting fast search achieved by combining a large variety of proprietary tree compression techniques. As with LPM, BioCAM® for MFC also benefits from larger block size that facilitates more aggressive tree compression and higher search speed but is less sensitive to larger entries than BioCAM® for LPM. In the current version, BioCAM® supports up to 512-bit ternary search, i.e. each bit in a 512-bit entry is zero, one or wildcard, but can easily be extended to support larger entries if the application requires. In the basic search, the query key is fully specified, meaning no wildcard bits, and the search result consists of all entries that matches from which a winner is typically selected using a tie removal criteria (e.g. priority of entries). The core algorithm does however also support search where the query key contains wildcards thus potentially causing all store entries to match.

Example: In a system with 64-byte block size (e.g. DDR3 with 64-byte burst), BioCAM® MFC can represent several million 512-bit entries and support a search cost budget of four (4) to eight (8) memory accesses. The storage overhead for representing the search structure is negligible compared to the memory required to represent the entries.

BioCAM® MFC Search runs on standard PC platforms where it takes advantage of the large burst size, cache hierarchy and huge memory to achieve moderate search speed represent very large prefix sets. It has also been ported to proprietary multi-core NPUs where the tight search cost budget contributes to fully saturate the memory interfaces and achieve very high search speeds.