# US 2012/0084459 A1 · Content Router Forwarding Plane Architecture

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084459 A1
- Document ID: US20120084459A1
- Status: Published application
- Kind: A1
- Application number: 13/022,412
- Filed: 2011-02-07
- Published: 2012-04-05
- Earliest claimed: 2010-10-04
- Assignees: Futurewei Technologies, Inc.
- Inventors: Jianming Wu; Guangyu Shi
- Web page: https://patentgrep.com/patent/US20120084459A1

## CPC

- H04L 45/7453: using hashing
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A router forwarding plane comprising a bloom filter stored on a first tier storage medium, and a forwarding information log associated with the bloom filter and stored on a second tier storage medium. Also disclosed is a network component comprising a receiver configured to receive a content comprising a general name prefix, a first tier storage medium configured to store a plurality of bloom filters associated with a plurality of general name prefixes and a plurality of corresponding ports, a logic circuitry configured to compute a plurality of signatures based on the general name prefix of the received content, and a transmitter configured to forward the received content on at least one of the ports that are associated with at least one of the bloom filters if the general name prefix is a member of the at least one of the bloom filters.

## Claims

### Claim 1

A router forwarding plane comprising:
a bloom filter stored on a first tier storage medium; and
a forwarding information log associated with the bloom filter and stored on a second tier storage medium.

### Claim 2 (depends on 1)

The apparatus of claim 1 further comprising a counting bloom filter associated with the bloom filter and stored on a third tier storage medium, wherein the first tier storage medium has a faster access speed and a smaller storage capacity than the third tier storage medium, and wherein the third tier storage medium has a faster access speed and a smaller storage capacity than the second tier storage medium.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the bloom filter supports routing at a bit rate of about 3.2 terabits per second (Tbps) for relatively small content packets in the order of kilobytes (KB), a bit rate of about eight petabits per second (Pbps) for relatively large content in the order of megabytes (MB), or both.

### Claim 4 (depends on 1)

The apparatus of claim 1 further comprising a counting bloom filter associated with the bloom filter and stored on a third tier storage medium, wherein the first tier storage medium comprises a Dynamic Random Access Memory (DRAM), the third tier storage medium comprises a Solid State Drive (SSD), and the second tier storage medium comprises a Hard Disk Drive (HDD).

### Claim 5 (depends on 1)

The apparatus of claim 1 further comprising a counting bloom filter associated with the bloom filter and stored on a third tier storage medium, wherein the first tier storage medium comprises a Dynamic Random Access Memory (DRAM), the third tier storage medium comprises a Phase-Change Memory (PCM), and the second tier storage medium comprises a Solid State Drive (SSD).

### Claim 6 (depends on 1)

The apparatus of claim 1 further comprising a counting bloom filter associated with the bloom filter and stored on a third tier storage medium, wherein the first tier storage medium, the second tier storage medium, and the third tier storage medium are located on a commodity server, and wherein the bloom filter, the counting bloom filter and the forwarding information log are components hosted on the commodity server.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein the bloom filter is associated with a single port on the router.

### Claim 8 (depends on 1)

The apparatus of claim 1 further comprising a counting bloom filter associated with the bloom filter and stored on a third tier storage medium, wherein the bloom filter is associated with a plurality of ports on the router, and wherein the first tier storage medium or the third tier storage medium comprises a port preference table that indicates a preferred forwarding port from the ports associated with the bloom filter.

### Claim 9

A network component comprising:
a receiver configured to receive a content comprising a general name prefix;
a first tier storage medium configured to store a plurality of bloom filters associated with a plurality of general name prefixes and a plurality of corresponding ports;
a logic circuitry configured to compute a plurality of signatures based on the general name prefix of the received content; and
a transmitter configured to forward the received content on at least one of the ports that are associated with at least one of the bloom filters if the general name prefix is a member of the at least one of the bloom filters.

### Claim 10 (depends on 9)

The network component of claim 9, wherein a plurality of general name prefixes are members of a single bloom filter that is associated with a single port, and wherein the single bloom filter comprises a plurality of bits that are set to indicate a plurality of signatures that correspond to the members.

### Claim 11 (depends on 9)

The network component of claim 9, wherein a plurality of ports are associated with a single bloom filter, and wherein the received content is forwarded on the ports that are associated with the single bloom filter if the general name prefix of the received content is a member of the single bloom filter.

### Claim 12 (depends on 9)

The network component of claim 9, wherein the signatures are computed using a plurality of hashing functions that correspond to the signatures, wherein the same hashing functions are used for a plurality of received general name prefixes, and wherein different signatures are computed for different general name prefixes.

### Claim 13 (depends on 9)

The network component of claim 9 further comprising a second tier storage medium configured to store a plurality of counting bloom filters associated with the bloom filters, wherein each one of the counting bloom filters indicates a quantity of members for each signature in one corresponding bloom filter.

### Claim 14 (depends on 13)

The network component of claim 13, wherein each one of the counting bloom filters comprises a subset of bits for each signature that comprises a value that indicates a current quantity of members corresponding to the signature, and wherein the value is increased by one when a member that has a corresponding signature is added to a port associated with the bloom filter and is decreased by one when a member that has a corresponding signature is removed from a set of members of the port.

### Claim 15 (depends on 13)

The network component of claim 13 further comprising a third tier storage medium configured to store a forwarding information log that is used to reconstruct at least some portion of the counting bloom filters, the bloom filters, or both upon system failures.

### Claim 16 (depends on 15)

The network component of claim 15, wherein the counting bloom filters, the bloom filters, or both are recovered at a relatively short time window of about few seconds with respect to a content forwarding process.

### Claim 17

A computer-implemented method comprising:
receiving an item of content;
obtaining a general content prefix from the content;
querying a plurality of bloom filters to find at least one match for the general content prefix; and
forwarding the content on at least one port associated with at least one bloom filter matching the general content prefix.

### Claim 18 (depends on 17)

The method of claim 17 further comprising:
selecting a preferred port that is associated with the general content prefix in a port preference table if the general content prefix is matched with a plurality of ports associated with a plurality of bloom filters; and
forwarding the content on the preferred port.

### Claim 19 (depends on 17)

The method of claim 17 further comprising:
computing a plurality of signatures for a new general content prefix using a plurality of hashing functions;
setting a plurality of bits that correspond to the computed signatures in a bloom filter that is associated with a port assigned to the new general content prefix; and
increasing by one a plurality of counters corresponding to the signatures in a counting bloom filter that is associated with the bloom filter and the port.

### Claim 20 (depends on 17)

The method of claim 17 further comprising:
computing a plurality of signatures for general content prefix that is a member of a bloom filter and previously assigned to a port associated with the bloom filter;
clearing a plurality of bits that correspond to the computed signatures in the bloom filter that is associated with the port; and
decreasing by one a plurality of counters corresponding to the signatures in a counting bloom filter that is associated with the bloom filter and the port.

### Claim 21

A router forwarding plane comprising:
a counting bloom filter stored on a first tier storage medium; and
a forwarding information log associated with the counting bloom filter and stored on a second tier storage medium.

### Claim 22 (depends on 21)

The apparatus of claim 21, wherein the first tier storage medium comprises a Solid State Drive (SSD), and the second tier storage medium comprises a Hard Disk Drive (HDD).

### Claim 23 (depends on 21)

The apparatus of claim 21, wherein the first tier storage medium comprises a Phase-Change Memory (PCM), and the second tier storage medium comprises a Solid State Drive (SSD).

### Claim 24 (depends on 21)

The apparatus of claim 21, wherein the first tier storage medium and the second tier storage medium are located on a commodity server, and wherein the counting bloom filter and the forwarding information log are components hosted on the commodity server.
