# US 8,751,645 B2 · Lattice based traffic measurement at a switch in a communication network

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

- Number: US 8,751,645 B2
- Document ID: US8751645B2
- Status: Granted
- Kind: B2
- Application number: 13/554,853
- Filed: 2012-07-20
- Published: 2014-01-30
- Granted: 2014-06-10
- Earliest claimed: 2012-07-20
- Assignees: Telefonaktiebolaget L M Ericsson (publ)
- Applicants: Omar Mounaouar; Petko Valtchev; Omar Cherkaoui; Laurent Marchand
- Inventors: Omar Mounaouar; Petko Valtchev; Omar Cherkaoui; Laurent Marchand
- Web page: https://patentgrep.com/patent/US8751645B2

## CPC

- H04L 43/00: Arrangements for monitoring or testing data switching networks
- H04L 43/026: using flow identification
- Y02D 30/50: in wire-line communication networks, e.g. low power modes or reduced link rate
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A lattice of interconnected concepts is constructed from flow entries. Each concept describes a subset of flows and a subset of the flow attributes. Based on user queries, the lattice is used to build disjoint sets of flows referred to as flowsets. Each user query specifies one or more of the flow attributes to be measured. Each flowset includes one or more of the flows to thereby enable sharing of the hardware counters among the flows. One hardware counter is then assigned to each flowset.

## Claims

### Claim 1

A method of assigning hardware counters to flows that pass through a switch in a communication network for performing traffic measurement at the switch, wherein each of the flows is associated with a set of flow attributes, the method comprising the steps of:
constructing, by a processor, a lattice of interconnected concepts from flow entries available at the switch, each concept describing a subset of the flows and a subset of the flow attributes;
receiving by the processor a set of user queries, each user query specifying one or more of the flow attributes to be measured;
identifying disjoint flowsets from the lattice based on the user queries, each flowset comprising one or more of the flows to enable sharing of the hardware counters among the flows; and
assigning one hardware counter to each flowset.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of identifying disjoint flowsets further comprises the steps of:
identifying target concepts in the lattice, each target concept describing one or more flow attributes that match the flow attributes specified by one of the user queries; and
identifying projection concepts in the lattice, the projection concepts comprising intersections of the target concept extents in the lattice.

### Claim 3 (depends on 2)

The method of claim 2, further comprising the steps of:
mapping the flows to a semi-lattice defined by the projection concepts; and
identifying ground concepts based on the mapping, each ground concept defining a group of the flows that form one of the flowsets.

### Claim 4 (depends on 1)

The method of claim 1, wherein the assigned hardware counters are a minimum set of counters for answering the user queries.

### Claim 5 (depends on 1)

The method of claim 1, further comprising the step of incrementally updating the lattice and the disjoint flowsets in response to an update to the flow entries.

### Claim 6 (depends on 5)

The method of claim 5, wherein the update to the flow entries includes adding or deleting a flow, or adding or deleting a flow attribute.

### Claim 7 (depends on 1)

The method of claim 1, wherein the hardware counters are programmable for measuring traffic of any one of the flowsets.

### Claim 8 (depends on 1)

The method of claim 1, wherein constructing a lattice further comprises the steps of:
forming a two-dimensional context from the flow entries, the context having a flow dimension and a flow attribute dimension and a plurality of context entries, each context entry indicating one of the flows and corresponding flow attributes; and
mapping the context to the lattice.

### Claim 9 (depends on 1)

The method of claim 1, further comprising the steps of:
receiving by the processor measurements generated by the hardware counters from the switch; and
providing answers to the user queries based on the measurements.

### Claim 10

A computing device in a communication network, the computing device to assign hardware counters to flows that pass through a switch for performing traffic measurement at the switch, wherein each of the flows is associated with a set of flow attributes, the computing device comprising:
input circuitry to receive flow entries available at the switch and a set of user queries, each user query specifying one or more of the flow attributes to be measured;
a processor coupled to the input circuitry, the processor comprising:
a concept generator module adapted to construct a lattice of interconnected concepts from the flow entries, each concept describing a subset of the flows and a subset of the flow attributes,
a flowset builder module adapted to identify disjoint flowsets from the lattice based on the user queries, wherein each flowset comprises one or more of the flows to enable sharing of the hardware counters among the flows, and
a counter placement module adapted to assign one hardware counter to each flow, and
output circuitry coupled to the processor to output a mapping between flow identifiers and hardware counter identifiers to the switch for assignment of the hardware counters.

### Claim 11 (depends on 10)

The computing device of claim 10, wherein the flowset builder module is further adapted to identify target concepts in the lattice, each target concept describing one or more flow attributes that match the flow attributes specified by one of the user queries, and to identify projection concepts in the lattice, the projection concepts comprising maximum intersections of the target concepts in the lattice.

### Claim 12 (depends on 11)

The computing device of claim 11, wherein the flowset builder module is further adapted to map the flows to the semi-lattice defined by the projection concepts, and to identify ground concepts based on the mapping, each ground concept defining a group of the flows that form one of the flowsets.

### Claim 13 (depends on 10)

The computing device of claim 10, wherein the assigned hardware counters are a minimum set of counters for answering the user queries.

### Claim 14 (depends on 10)

The computing device of claim 10, wherein the processor is further adapted to incrementally update the lattice and the disjoint flowsets in response to an update to the flow entries.

### Claim 15 (depends on 14)

The computing device of claim 14, wherein the update to the flow entries includes adding or deleting a flow, or adding or deleting a flow attribute.

### Claim 16 (depends on 10)

The computing device of claim 10, wherein the hardware counters are programmable for measuring traffic of any one of the flowsets.

### Claim 17 (depends on 10)

The computing device of claim 10, wherein the flowset builder module is further adapted to form a two-dimensional context from the flow entries, the context having a flow dimension and a flow attribute dimension and a plurality of context entries, each context entry indicating one of the flows and corresponding flow attribute, and to map the context to the lattice.

### Claim 18 (depends on 10)

The computing device of claim 10, wherein the processor further comprises a statistics management module adapted to receive measurements generated by the hardware counters from the switch, and to provide answers to the user queries based on the measurements.