# US 2008/0186974 A1 · System and method to process data packets in a network using stateful decision trees

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

- Number: US 2008/0186974 A1
- Document ID: US20080186974A1
- Status: Published application
- Kind: A1
- Application number: 11/551,932
- Filed: 2006-10-23
- Published: 2008-08-07
- Earliest claimed: 2006-10-23
- Assignees: Cisco Technology, Inc.
- Inventors: Sumeet Singh; George Varghese; Flavio Giovanni Bonomi; Jonathan J. Chang
- Web page: https://patentgrep.com/patent/US20080186974A1

## CPC

- H04L 47/10: Flow control; Congestion control
- H04L 45/742: {Route cache; Operation thereof}
- H04L 45/7459: using Bloom filters
- H04L 47/22: Traffic shaping
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L 43/50: Testing arrangements
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method and device to process a packet received by a network device is described. The method may comprise analyzing the packet to identify at least one set of a plurality of sets, mapping the at least one set to at least one functional unit, and performing functionality associated with the at least one functional unit. Analyzing the packet to identify at least one of a plurality of sets may comprise determining when the packet includes at least one set identifier, and identifying the at least one set based on the at least one set identifier. A set status identifier may be defined for each set, the set status identifier indicating when set identifiers associated with a corresponding set are detected in the packet. The device may be a router, switch or any other device that processes digital data e.g., packet data including packets headers, payload or the like.

## Claims

### Claim 1

A method for processing a packet received by a network device, the method comprising:
analyzing the packet to identify when the packet is associated with at least one set of a plurality of sets;
when the packet is associated with the at least one set, mapping the at least one set to at least one functional unit; and
performing functionality associated with the at least one functional unit.

### Claim 2 (depends on 1)

The method of claim 1, wherein analyzing the packet comprises using a plurality of tests, each test corresponding to at least one set, and the method comprises associating the packet with the at least one set based on an outcome of the test.

### Claim 3 (depends on 2)

The method of claim 2, in which each test comprises:
extracting a packet identifier from the packet using a mask corresponding to the at least one set;
determining if the extracted packet identifier corresponds to a set identifier of the at least one set; and
associating the packet with the at least one set when the extracted packet identifier corresponds to the set identifier.

### Claim 4 (depends on 3)

The method of claim 3, which includes using a Bloom filter to define the mask corresponding to each set.

### Claim 5 (depends on 3)

The method of claim 3, which includes using a Bloom filter to define a mask that corresponds to a plurality of sets.

### Claim 6 (depends on 1)

The method of claim 1, in which analyzing the packet to identify at least one of the plurality of sets comprises:
determining when the packet includes at least one set identifier; and
identifying the at least one set based on the at least one set identifier.

### Claim 7 (depends on 6)

The method of claim 6, which comprises:
determining if the packet includes a plurality of set identifiers;
identifying a plurality of corresponding sets each associated with at least one of the plurality of set identifiers; and
mapping each corresponding set to the at least one functional unit.

### Claim 8 (depends on 7)

The method of claim 7, which comprises:
defining a set status identifier for each set, the set status identifier indicating when set identifiers associated with a corresponding set are detected in the packet.

### Claim 9 (depends on 8)

The method of claim 8, which comprises:
combining set status identifiers of the plurality of sets into a sets status string; and
accessing a mapping table using the sets status string to identify the at least one functional unit.

### Claim 10 (depends on 6)

The method of claim 6, in which the functionality comprises associating at least one set identifier with at least one other set of the plurality of sets.

### Claim 11 (depends on 10)

The method of claim 10, in which associating the at least one set identifier comprises:
identifying the at least one other set for updating, the at least one other set for updating being identified by the functional unit;
reading a mask associated with a set used to identify the functional unit; and
adding the set identifier to the at least one other set.

### Claim 12 (depends on 11)

The method of claim 11, which comprises encoding masked bits to provide an encoded identifier.

### Claim 13 (depends on 1)

The method of claim 1, which comprises:
mapping nodes of a decision tree, acyclic decision graph or a data flow analysis (DFA) to the plurality of sets; and
associating a functional unit to provide functionality required at each node.

### Claim 14 (depends on 1)

The method of claim 1, which comprises performing the functionality associated with the at least one functional unit multiple times.

### Claim 15 (depends on 1)

The method of claim 1, which comprises mapping a plurality of different functional units to the same set.

### Claim 16 (depends on 1)

The method of claim 1, in which analyzing the packet to identify the at least one set comprises masking bits in a packet to provide a set identifier.

### Claim 17

A network device to process a received packet, the device comprising:
an analysis module to analyze the packet to identify when the packet is associated with at least one set of a plurality of sets;
at least one functional unit to perform predefined functionality; and
a mapping module to map, when the packet is associated with the at least one set, the at least one set to the at least one functional unit.

### Claim 18 (depends on 17)

The network device of claim 17, in which the analysis module is configured to use a plurality of tests, each test corresponding to at least one set, and to associate the packet with the at least one set based on an outcome of the test.

### Claim 19 (depends on 18)

The network device of claim 18, in which each test:
extracts a packet identifier from the packet using a mask corresponding to the at least one set;
determines if the extracted packet identifier corresponds to a set identifier of the at least one set; and
associates the packet with the at least one set when the extracted identifier corresponds to the set identifier.

### Claim 20 (depends on 19)

The network device of claim 19, wherein the mask is a Bloom filter.

### Claim 21 (depends on 20)

The network device of claim 20, wherein the Bloom filter corresponds to a plurality of sets.

### Claim 22 (depends on 17)

The network device of claim 17, in which the analysis module is configured to:
determine when the packet includes at least one set identifier; and
identify the at least one set based on the at least one set identifier.

### Claim 23 (depends on 22)

The network device of claim 22, in which the analysis module is configured to:
determine if the packet includes a plurality of set identifiers;
identify a plurality of corresponding sets each associated with at least one of the plurality of set identifiers; and
map each corresponding set to at least one functional unit.

### Claim 24 (depends on 23)

The network device of claim 23, in which a set status identifier is defined for each set, the set status identifier indicating when set identifiers associated with a corresponding set are detected in the packet.

### Claim 25 (depends on 24)

The network device of claim 24, in which the set status identifiers of the plurality of sets are combined into a sets status string, and a mapping table is accessible using the sets status string to identify the at least one functional unit.

### Claim 26 (depends on 22)

The network device of claim 22, in which the at least one functional unit is configured to associate at least one set identifier with at least one other set of the plurality of sets.

### Claim 27 (depends on 22)

The network device of claim 22, in which the at least one functional unit is configured to:
identify at least one other set for updating, the other set for updating being identified by the functional unit;
read a mask associated with a set used to identify the at least one functional unit; and
add the set identifier to the at least one other set.

### Claim 28 (depends on 22)

The network device of claim 22, in which masked bits are encoded to provide an encoded identifier.

### Claim 29 (depends on 17)

The network device of claim 17, in which the mapping module is configured to:
map nodes of a decision tree, acyclic decision graph or a data flow analysis (DFA) to the plurality of sets; and
associate a functional unit with functionality required at each node.

### Claim 30 (depends on 17)

The network device of claim 17, in which the functionality associated with the functional unit is performed multiple times.

### Claim 31 (depends on 17)

The network device of claim 17, in which the mapping module is configured to map a plurality of different functional units to the same set.

### Claim 32 (depends on 17)

The network device of claim 17, in which analysis module is configured to identify at least one set of a plurality of sets and mask bits in a packet to provide a set identifier.

### Claim 33 (depends on 17)

The network device of claim 17, which is one of a router and a switch.

### Claim 34

A machine-readable medium embodying instructions which, when executed by a machine, cause the machine to:
analyze a packet to identify when the packet is associated with at least one set of a plurality of sets;
when the packet is associated with at least one set, map the at least one set to at least one functional unit; and
perform functionality associated with the at least one functional unit.

### Claim 35

A network device to process a packet, the device comprising:
means for analyzing the packet to identify when the packet is associated with at least one set of a plurality of sets;
means for mapping, when the packet is associated with at least one set, the at least one set to at least one functional unit; and
means for performing functionality associated with the at least one functional unit.
