# US 7,653,753 B2 · Method and apparatus for content-based packet routing using compact filter storage and off-line pre-computation

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

- Number: US 7,653,753 B2
- Document ID: US7653753B2
- Status: Granted
- Kind: B2
- Application number: 10/400,465
- Filed: 2003-03-28
- Published: 2003-12-04
- Granted: 2010-01-26
- Earliest claimed: 2002-03-28
- Assignees: Precache Inc.
- Inventors: Tsu-Wei Chen; Alex W. P. Fung; David S. Rosenblum; Ping-Fai Yang
- Web page: https://patentgrep.com/patent/US7653753B2

## CPC

- H04L 45/306: {Route determination based on the nature of the carried application}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method and apparatus provide for content-based routing of packets in a publish-subscribe network. A packet is received via the network. A map specifying computed filter coverage in an attribute space is accessed. Content of the packet is inspected for a routing decision for the packet. The map is used for the routing decision for the packet. The packet is routed based upon the inspected content of the packet and the map. A router for content-based routing of packets in a publish-subscribe network, comprising modules for performing this method is provided. A network including a plurality of such routers is provided. A computer-readable medium including instructions for performing this method is provided.

## Claims

### Claim 1

A method for content-based routing of packets in a publish-subscribe network including an intelligent router, the method comprising:
receiving a packet at said intelligent router in the network;
said intelligent router accessing a map specifying filter coverage in an attribute space;
said intelligent router inspecting content of the packet for use in a routing decision for the packet;
using the map to assist in said intelligent router's routing decision for the packet;
said intelligent router making a routing decision based upon the inspected content of the packet and the map;
routing, by said intelligent router, the packet based upon the routing decision; and
computing filter coverage;
wherein computing filter coverage includes spatially quantizing attribute space into a grid comprising grid cells.

### Claim 2 (depends on 1)

The method of claim 1, wherein the making a routing decision step further includes matching the content to a corresponding description.

### Claim 3 (depends on 2)

The method of claim 2, wherein the matching step includes using a plurality of conjunctive filters in order to identify a match.

### Claim 4 (depends on 2)

The method of claim 2, wherein the matching step includes performing attribute tests.

### Claim 5 (depends on 1)

The method of claim 1, wherein the making a routing decision step includes using the map online.

### Claim 6 (depends on 1)

The method of claim 1, further comprising precomputing filter coverage off-line or with background processing.

### Claim 7 (depends on 1)

The method of claim 1, further comprising precomputing filter coverage wherein the precomputing step includes approximating and reducing filter expressions.

### Claim 8 (depends on 1)

The method of claim 1, wherein the computing filter coverage includes:
combining filter coverage information and the grid; and
generating the map based on a union of actions predicated by filter coverage information in each grid cell.

### Claim 9 (depends on 1)

A router for content-based routing of packets in a publish-subscribe network, comprising modules for executing the method recited in claim 1.

### Claim 10 (depends on 9)

A network comprising a plurality of routers according to claim 9.

### Claim 11 (depends on 1)

A computer-readable medium comprising instructions for performing the method recited in claim 1.

### Claim 12

A method for use in content-based routing of packets on a network including an intelligent router, the method comprising:
(a) said intelligent router spatially quantizing attribute space, wherein the spatially quantizing step creates a grid including grid cells;
(b) said intelligent router identifying the grid cells covered by a plurality of filters, wherein each filter has at least one predicated attribute; and
(c) said intelligent router updating a content-based routing (CBR) table with action rules predicated by the plurality of filters that cover the grid cells identified in step (b).

### Claim 13 (depends on 12)

The method of claim 12, further comprising the step of:
determining if one or more distinct filters are inserted or removed from a node; and
executing steps (b) and (c) at the node based on a determination that one or more distinct filters are inserted or removed from the node.

### Claim 14 (depends on 12)

The method of claim 12, further comprising the steps of:
receiving published packets; and
plotting the received packets to the grid.

### Claim 15 (depends on 14)

The method of claim 14, wherein for packets plotted to grid cells that are completely covered by the computed filter coverage information, the method further comprises:
checking the CBR table to determine routing actions for packets plotted to the completely covered grid cells.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
determining if the network traffic is above a set threshold; and,
routing the published packets based on the determined routing actions, if the network traffic is determined to be above the set threshold.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
performing leakage reduction, if the network traffic is determined to be at or below the set threshold.

### Claim 18 (depends on 17)

The method of claim 17, wherein the performing leakage reduction step includes one-dimension exact matching.

### Claim 19 (depends on 17)

The method of claim 17, wherein the performing leakage reduction step includes cross-producting.

### Claim 20 (depends on 17)

The method of claim 17, wherein the performing leakage reduction step includes the formation of multiple grids and CBR tables according to the full set of subset of the permutations of a limited number and a variety of attributes.

### Claim 21 (depends on 16)

The method of claim 16, further comprising:
determining if there are any reduced filter predicates or packets plotted to partially covered grid cells, if the network traffic is determined to be at or below the set threshold;
performing predicate-by-predicate filter matching to determine routing actions for any reduced filter predicates and any packets plotted to partially covered grid cells, if there are determined to be reduced filter predicates or packets plotted to partially covered grid cells; and,
routing the packets based on determined routing actions.

### Claim 22 (depends on 12)

The method of claim 12, further comprising reducing filter expressions.

### Claim 23 (depends on 12)

The method of claim 12, wherein step (a) includes adaptive quantizing the attribute space.

### Claim 24 (depends on 23)

The method of claim 23, wherein the adaptive quantizing step adaptively quantizes the attribute space based on packet distribution information.

### Claim 25 (depends on 12)

The method of claim 12, wherein the spatially quantizing step spatially quantizes the attribute space based on packet distribution information.

### Claim 26 (depends on 12)

The method of claim 12, wherein the spatially quantizing step updates the grid based on packet distribution information.

### Claim 27 (depends on 12)

The method of claim 12, wherein step (c) generates or updates an action bit mask for a grid cell that is covered by the computer filter coverage information.

### Claim 28 (depends on 12)

The method of claim 12, wherein step (c) generates or updates a linked list of action for a grid cell that is covered by the computer filter coverage information.

### Claim 29 (depends on 12)

The method of claim 12, further comprising updating parameters for covered cells in the CBR table, wherein the parameters include statistical information about the filter distribution.

### Claim 30 (depends on 12)

The method of claim 12, further comprising collecting statistical information about packet distribution, wherein the packet distribution information is used in step (a).

### Claim 31 (depends on 12)

The method of claim 12, wherein steps (a) through (c) are performed offline.

### Claim 32 (depends on 12)

The method of claim 12, further comprising performing content based routing (CBR), wherein only the CBR table and the rules in the CBR table are used to perform the CBR.

### Claim 33 (depends on 12)

A computer-readable medium comprising instructions for performing the method recited in claim 12.