# 3.1.1.1.13 NC Replica Graph

This section uses directed graphs to model replication topology. Use
[KNUTH1] section 2.3.4.2 as a reference for the terms *directed graph*, *vertex*,
*arc*, *initial vertex*, *final vertex*, *path*, and *strongly-connected*.

This section introduces concepts that are used in specifying the KCC in section 6.2. The concepts are simplified here because this section ignores the SMTP replication transport [MS-SRPL] and RODCs. Section 6.2 specifies the concepts in full generality.

Associated with each NC replica is a repsFrom
abstract attribute as
specified in [MS-DRSR]
section 5.172.
The value of this attribute is a set of tuples. Each tuple contains a field *uuidDsa*
that contains the objectGUID
of an nTDSDSA
object. The nTDSDSA object represents a DC as specified in section 6.1.

Given a forest and an NC within the forest, define the NC replica graph as follows:

Each DC of the given forest is a vertex of the directed graph.

For each DC

*d*containing a replica of the given NC:Set

*r*to the given NC's repsFrom on the DC*d*, as a sequence in any order.For

*i*in [0 ..*r.length*-1]:*r[i].uuidDsa*is a directed arc to*d*(the final vertex of the arc) from the DC represented by the nTDSDSA object with objectGUID =*r[i].uuidDsa*(the initial vertex of the arc).

Each arc in the directed graph represents a replication relationship. The DC at the final vertex of an arc performs cycles of IDL_DRSGetNCChanges requests ([MS-DRSR] section 4.1.10.1) to the DC at the initial vertex of that arc, applying the results of these requests to update the replica of the given NC at the final vertex. The events that trigger a cycle of IDL_DRSGetNCChanges request over a given arc of the NC replica graph are specified in the next section.

The KCC is an automated management component of Active Directory that controls the repsFrom values on each DC and thereby controls the NC replica graph for each NC. One of the KCC's goals is to keep each NC replica graph of the forest in a good state, defined as follows:

Each DC in the NC replica graph contains a replica of the given NC.

If the DC at the initial vertex of an arc contains a partial replica of the given NC, so does the DC at the final vertex of that arc.

If

*d*is any DC that contains a partial replica of the given NC, there is a path to*d*from some DC that contains a full replica of the given NC.Define

*F*as the set of all DCs that contain full replicas of the given NC. The subgraph of the NC replica graph whose vertex set is*F*is strongly-connected.

For example, the following NC replica graph contains five DCs. DC 1, DC 2, and DC 3 contain full replicas of the given NC and DC 4 and DC 5 contain partial replicas of the given NC.

Figure 3: A sample NC replica graph

Per item 1 in the numbered list above, every DC present in the graph contains a replica of the given NC.

There is an arc from DC 4 to DC 5. DC 4 is the initial vertex of this arc and DC 5 is the final vertex. Per item 2 in the list above, because DC 4 contains a partial replica of the NC, DC 5 also contains a partial replica of the NC.

Per item 3 in the list above, there is a path from DC 1, which contains a full replica of the NC, to both DC 4 and DC 5 that contains a partial replica of the NC.

Per item 4 in the list above, the subgraph of the NC replica graph made by DC 1, DC 2, and DC 3 that contains a full replica of the NC is strongly connected because there is a path from each vertex in the subgraph to every other vertex in the subgraph.

The KCC performs this management by first creating *connection*
objects (specified in section 6.1.1.2.2.1.2.1.2), then
creating repsFrom values from those connection objects (specified in
section 6.2). An administrator can create specially marked connection objects,
with the NTDSCONN_OPT_IS_GENERATED bit not set in the options
attribute, that the KCC will not modify but will use in creating repsFrom
values.