US 2022/0070282 A1 · METHODS, SYSTEMS, AND MEDIA FOR NETWORK MODEL CHECKING USING ENTROPY BASED BDD COMPRESSION

Abstract

Methods, systems and media for network model checking using entropy based binary decision diagram (BDD) compression are described. Two related compression techniques are described: bit level reduction to reduce the number of bits required for each network field according to its nature, and field level reduction to reduce the size of the BDD tree by finding a near-optimum ordering of the fields in the BDD space. These two techniques, separately or together, may alleviate the state explosion problem the limits application of BDD based model checking. The two techniques complement each other synergistically, particularly in the domain of computer network checking and verification.

Claims20

Dependent claims

A method for generating a binary decision diagram (BDD) for checking a computer network model, the method comprising:

identifying one or more network entities of the computer network model;
identifying a plurality of fields of the computer network model;
for each field, identifying a plurality of values for the field as the union of the values for the field specified by each network entity;
calculating an entropy value for each field based on the plurality of values for the field;
and
ordering a plurality of variables of the BDD based on the entropy values of the fields corresponding to the variables.

3 more elements

A system comprising:

one or more processor devices;
and
a memory storing instructions which, when executed by the one or more processor devices, cause the system to generate a binary decision diagram (BDD) for checking a computer network model by:
identifying one or more network entities of a computer network model;
identifying a plurality of fields of the computer network model;
for each field, identifying a plurality of values for the field as the union of the values for the field specified by each network entity;
calculating an entropy value for each field based on the plurality of values for the field;
and
ordering a plurality of variables of the BDD based on the entropy values of the fields corresponding to the variables.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application

17/008,269Filed 31 Aug 2020

Published

3 Mar 2022

Term ends

Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 41/145
Network analysis or design: involving simulating, designing, planning or modelling of a network
H04L 41/084
Configuration setting: configuration by using pre-existing information, e.g. using templates or copying from other elements
H04L 41/0866
Configuration management of networks or network elements: checking the configuration
H04L 69/04
Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass:…

Methods, systems, and media for network model checking using entropy based bdd compression

Life of this patent

Methods, systems, and media for network model checking using entropy based bdd compression

Life of this patent

Abstract

Claims20