Verifying whether connectivity in a composed policy graph reflects a corresponding policy in input policy graphs

A network device, comprising at least:

• a memory;
• a processor executing instructions from the memory to:
• receive a plurality of input policy graphs and a composed policy graph associated with the input policy graphs;
• divide the composed policy graph into a plurality of sub-graphs, each sub-graph comprising a plurality of edges and a plurality of source nodes and destination nodes that the edges are connected to;
• select a first subset of sub-graphs that include, as a source node, a disjoint part of an original source end point group (EPG) for each input policy graph;
• identify a second subset within the first subset of sub-graphs that include, as a destination node, a disjoint part of an original destination EPG for the each input policy graph;
• verify whether connectivity in the composed policy graph reflects a corresponding policy in the plurality of input policy graphs for each sub-graph in the second subset remove, from the second subset of sub-graphs, classifier information associated with the plurality of input policy graphs;
• and
• in response to no input policy graph being associated with the second subset of sub-graphs, indicate that the second subset of sub-graphs are verified.

A non-transitory machine-readable storage medium encoded with instructions executable by at least one processor of an access point, the machine-readable storage medium comprising instructions to:

• receive a plurality of input policy graphs and a composed policy graph associated with the plurality of input policy graphs;
• divide the composed policy graph into a plurality of sub-graphs, each sub-graph comprising a plurality of edges and a plurality of source nodes and destination nodes that the edges are connected to;
• select a subset of sub-graphs that include, as a source node, a disjoint part of an original source end point group (EPG) and, as a destination node, a disjoint part of an original destination EPG for each input policy graph;
• verify whether connectivity in the composed policy graph reflects a corresponding policy in the received input policy graphs for each sub-graph in the subset;
• identify, in the composed policy graph, a first original EPG to which a source endpoint in an input policy graph corresponds and a second original EPG to which a destination endpoint in the input policy graph corresponds;
• indicate an input policy in the composed policy graph in response to both the first original EPG and the second original EPG being associated with the input policy allowing communications between the first and second original EPGs;
• remove, from the subset of sub-graphs, classifier information associated with the plurality of input policy graphs;
• and
• indicate that the subset of sub-graphs are verified in response to no input policy graph being associated with the subset of sub-graphs.