Directed graph based span computation and configuration dispatching

A non-transitory machine readable medium storing a program for determining a span of logical entities in a network comprising a set of logical entities and a set of transport nodes, the span of each logical entity comprising a set of transport nodes requiring configuration data for the logical entity, the program executable by a processing unit, the program comprising sets of instructions for:

• generating a directed graph comprising a plurality of entity nodes and a plurality of edges, each entity node corresponding to a logical network entity, each edge between a pair of entity nodes representing a relationship between a pair of logical network entities corresponding to the pair of entity nodes, each edge having one or two directions, wherein a subset of the entity nodes have assigned spans and an edge direction from a first entity node to a second entity node specifies that a span of the second entity node includes a span of the first entity node;
• determining a span of each entity node based on the direction of the edges of the directed graph and the assigned spans of the subset of the entity nodes;
• based on the determined spans, grouping entity nodes of the directed graph into a plurality of strongly connected group (SCC) sub-graphs such that (i) each entity node in each SCC is accessible from any other entity node in the SCC and (ii) each entity node in each SCC has a same span as each other entity node in the SCC;
• mapping the directed graph into a directed acyclic graph (DAG) by (i) generating a group node for each SCC sub-graph in the directed graph, (ii) assigning the span of each SCC to the corresponding group node of the DAG, and (iii) storing the span of each SCC as the span of the SCC's corresponding group node in order to avoid storing multiple copies of a same span record for each individual entity node in a SCC, thereby reducing the number of stored span records;
• and
• dispatching configuration data for each logical entity to the set of transport nodes in the span of the group node associated with the logical entity.

A system comprising:

• a set of processing units;
• and
• non-transitory machine readable medium storing a program for determining a span of logical entities in a network comprising a set of logical entities and a set of transport nodes, the span of each logical entity comprising a set of transport nodes requiring configuration data for the logical entity, the program executable by a processing unit in the set of processing units, the program comprising sets of instructions for:
• generating a directed graph comprising a plurality of entity nodes and a plurality of edges, each entity node corresponding to a logical network entity, each edge between a pair of entity nodes representing a relationship between a pair of logical network entities corresponding to the pair of entity nodes, each edge having one or two directions, wherein a subset of the entity nodes have assigned spans and an edge direction from a first entity node to a second entity node specifies that a span of the second entity node includes a span of the first entity node;
• determining a span of each entity node based on the direction of the edges of the directed graph and the assigned spans of the subset of the entity nodes;
• based on the determined spans, grouping entity nodes of the directed graph into a plurality of strongly connected group (SCC) sub-graphs such that (i) each entity node in each SCC is accessible from any other entity node in the SCC and (ii) each entity node in each SCC has a same span as each other entity node in the SCC;
• mapping the directed graph into a directed acyclic graph (DAG) by (i) generating a group node for each SCC sub-graph in the directed graph, (ii) assigning the span of each SCC to the corresponding group node of the DAG, and (iii) storing the span of each SCC as the span of the SCC's corresponding group node in order to avoid storing multiple copies of a same span record for each individual entity node in each SCC, thereby reducing the number of stored span records;
• and
• dispatching configuration data for each logical entity to the set of transport nodes in the span of the group node associated with the logical entity.