DC topology: Difference between revisions
From SambaWiki
(a simpler version of the original document about AD DC topology) |
No edit summary |
||
(5 intermediate revisions by the same user not shown) | |||
Line 78: | Line 78: | ||
end |
end |
||
return the graph |
return the graph |
||
</pre> |
|||
==SetupVertices== |
|||
<pre> |
|||
for each v: all graph vertices |
|||
if v.Color is white |
|||
set v.ReplInfo.Cost to the maximum integer value |
|||
set v.RootID and v.ComponentID to null |
|||
else |
|||
set v.ReplInfo.Cost to 0 |
|||
set v.RootID and v.ComponentID to v.ID |
|||
end |
|||
set v.ReplInfo.Interval to 0 |
|||
set v.ReplInfo.Options to 0xFFFFFFFF |
|||
set v.ReplInfo.Schedule to null |
|||
set v.Demoted to false |
|||
end |
|||
</pre> |
|||
==CheckDemoteOneVertex== |
|||
<pre> |
|||
if v.Color is white |
|||
exit function |
|||
end |
|||
if both v.AcceptBlack and v.AcceptRedRed don't contain edgeType |
|||
set v.ReplInfo.Cost to the maximum integer value |
|||
set v.RootID to null |
|||
set v.Demoted to true |
|||
end |
|||
</pre> |
|||
==UndemoteOneVertex== |
|||
<pre> |
|||
if v.Color is white |
|||
exit function |
|||
end |
|||
set v.ReplInfo.Cost to 0 |
|||
set v.RootID to v.ID |
|||
set v.Demoted to false |
|||
</pre> |
|||
==GetComponentID== |
|||
<pre> |
|||
initialize u with v |
|||
while u.ComponentID isn't u.ID |
|||
set u to the vertex which ID is u.ComponentID |
|||
end |
|||
set root to u.ID |
|||
reset u to v |
|||
while u.ComponentID isn't u.ID |
|||
set w to the vertex which ID is u.ComponentID |
|||
set u.ComponentID to root |
|||
set u to w |
|||
end |
|||
return root |
|||
</pre> |
|||
==CopyOutputEdges== |
|||
<pre> |
|||
create an empty sequence of multiedge |
|||
for each e: outputEdges |
|||
set v to the first vertex of e.VertexIDs |
|||
set w to the second vertex of e.VertexIDs |
|||
if any of v.ID or w.ID is the objectGUID of site object for the local DC's site |
|||
if any of v.Color or w.Color is black, and v.DistToRed isn't the maximum integer value |
|||
set e as directed |
|||
if w.DistToRed < v.DistToRed |
|||
swap the two first elements of e.VertexIDs |
|||
end |
|||
end |
|||
add e to the sequence of multiedge |
|||
end |
|||
end |
|||
return the sequence of multiedge |
|||
</pre> |
|||
==BridgeheadDCFailed== |
|||
<pre> |
|||
if automatic stale server detection is disabled for the local DC's site |
|||
return false |
|||
else if ??? |
|||
return true |
|||
else |
|||
return the condition wether failed DC detection is enabled |
|||
end |
|||
</pre> |
|||
==GetBridgeheadDC== |
|||
<pre> |
|||
run GetAllBridgeheadDCs |
|||
if the return of the previous operation is an empty sequence |
|||
return null |
|||
else |
|||
return the first item of the sequence |
|||
end |
|||
</pre> |
|||
==ColorVertices== |
|||
<pre> |
|||
for each v: all graph vertices |
|||
find a site such that its objectGUID == v.ID |
|||
if the site contains one or more DCs with full replicas of the NC crossRef.nCName |
|||
set v.Color to red |
|||
else if the site contains one or more DCs with partial replicas of the NC crossRef.nCName |
|||
set v.Color to black |
|||
else |
|||
set v.Color to white |
|||
end |
|||
end |
|||
find a graph vertex such that its ID is the objectGUID of the local DC site |
|||
for each v: all graph vertices |
|||
for each t: objectClass=interSiteTransport, child of CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain> |
|||
if localVertex.Color is red and t.name isn't "IP" and crossRef is a domain AD NC, or |
|||
if the graph doesn't have any edge that contains v |
|||
skip this iteration and continue the loop |
|||
end |
|||
run GetBridgeheadDC to find out if a bridgehead DC is available |
|||
if there's no bridgehead DC currently available |
|||
mark that a failed DC was found |
|||
skip this iteration and continue the loop |
|||
end |
|||
add t to v.AcceptRedRed and to v.AcceptBlack |
|||
end |
|||
end |
|||
return a boolean value indicating if some failed DC was found |
|||
</pre> |
|||
==SetupDijkstra== |
|||
<pre> |
|||
run SetupVertices |
|||
create an empty sequence of vertices |
|||
for each v: all graph vertices |
|||
if v.Color is white |
|||
skip this iteration and continue the loop |
|||
end |
|||
if (v.Color is black and black vertices aren't used as roots), or |
|||
if any of v.AcceptBlack and v.AcceptRedRed doesn't contain edgeType |
|||
set v.ReplInfo.Cost to the maximum integer value |
|||
set v.RootID to null |
|||
set v.Demoted to true |
|||
else |
|||
append v to the sequence of vertices |
|||
end |
|||
end |
|||
return the sequence of vertices |
|||
</pre> |
|||
==CombineReplInfo== |
|||
<pre> |
|||
create a schedule that is the intersection of a.Schedule and b.Schedule and store it in s |
|||
if s is an empty schedule |
|||
return false |
|||
end |
|||
if a.Cost + b.Cost overflows |
|||
set c.Cost to the maximum integer value |
|||
else |
|||
set c.Cost to a.Cost + b.Cost |
|||
end |
|||
set c.Interval to the maximum of a.Interval and b.Interval |
|||
set c.Options to a.Options & b.Options |
|||
set c.Schedule to s |
|||
return true |
|||
</pre> |
|||
==TryNewPath== |
|||
<pre> |
|||
create a new replication info object and store it in newRI |
|||
run CombineReplInfo to fill newRI |
|||
if newRI.Cost > v.ReplInfo.Cost, or |
|||
if newRI.Cost < v.ReplInfo.Cost and the call to CombineReplInfo has returned false |
|||
exit function |
|||
end |
|||
calculate the total duration newRI.Schedule shows as available and store it in newDuration |
|||
calculate the total duration v.ReplInfo.Schedule shows as available and store it in oldDuration |
|||
if newRI.Cost < v.ReplInfo.Cost or newDuration > oldDuration |
|||
set v.RootID to u.RootID |
|||
set v.ComponentID to u.ComponentID |
|||
set v.ReplInfo to newRI |
|||
append v to vs |
|||
end |
|||
</pre> |
|||
==Dijkstra== |
|||
<pre> |
|||
run SetupDijkstra to build the inicial vertices sequence and store the result on vs |
|||
while vs isn't empty |
|||
find the vertex with the least cost in vs (if there are more than one vertex with the least cost, pick the one with the least ID) and store this vertex in u |
|||
remove u from vs |
|||
for each e: the graph edges which have u as one of its vertices |
|||
for each v: vertices in e |
|||
run TryNewPath |
|||
end |
|||
end |
|||
end |
|||
</pre> |
|||
==AddIntEdge== |
|||
<pre> |
|||
set root1 as the graph vertex with the same ID as v1.RootID |
|||
set root2 as the graph vertex with the same ID as v2.RootID |
|||
if both root1.Color and root2.Color are red |
|||
set redRed to true |
|||
else |
|||
set redRed to false |
|||
end |
|||
if redRed |
|||
if any of root1.AcceptRedRed or root2.AcceptRedRed doesn't contain e.Type |
|||
exit function |
|||
end |
|||
else |
|||
if any of root1.AcceptBlack or root2.AcceptBlack doesn't contain e.Type |
|||
exit function |
|||
end |
|||
end |
|||
create two empty replication info objects, ri and ri2 |
|||
run CombineReplInfo(v1, v2, ri) and CombineReplInfo(ri, e, ri2) |
|||
if any of the two previous calls returns false |
|||
exit function |
|||
end |
|||
create an empty internal edge and store it in newIntEdge |
|||
set newIntEdge.V1ID to root1.ID |
|||
set newIntEdge.V2ID to root2.ID |
|||
set newIntEdge.RedRed to redRed |
|||
set newIntEdge.ReplInfo to ri2 |
|||
set newIntEdge.Type to e.Type |
|||
if newIntEdge.V1ID > newIntEdge.V2ID |
|||
swap newIntEdge.V1ID and newIntEdge.V2ID |
|||
end |
|||
if internalEdges doesn't contain newIntEdge |
|||
add newIntEdge to internalEdges |
|||
end |
|||
</pre> |
|||
==ProcessEdge== |
|||
<pre> |
|||
create a vertex sequence with the vertices in e, and store it on vs |
|||
sort vs by Color (red < black), ReplInfo.Cost and ID, in that order |
|||
store the first element of vs in bestV |
|||
for each v: graph vertices of e |
|||
if v.ComponentID and v.RootID aren't null |
|||
skip this iteration and continue the loop |
|||
end |
|||
if bestV.ComponentID and bestV.RootID and v.ComponentID and v.RootID aren't null, and bestV.ComponentID isn't v.ComponentID |
|||
run AddIntEdge |
|||
end |
|||
end |
|||
</pre> |
|||
==ProcessEdgeSet== |
|||
<pre> |
|||
if edge set is null |
|||
for each e: graph edges |
|||
for each v: graph vertices of e |
|||
run CheckDemoteOneVertex |
|||
end |
|||
run ProcessEdge |
|||
for each v: graph vertices of e |
|||
run UndemoteOneVertex |
|||
end |
|||
end |
|||
else |
|||
for each e: graph edges associated with the edge set |
|||
run ProcessEdge |
|||
end |
|||
end |
|||
</pre> |
|||
==AddOutEdge== |
|||
<pre> |
|||
find the vertices v1 and v2 on the graph based on e.V1ID and e.V2ID |
|||
create an empty multiedge and store it in ee |
|||
set ee as undirected |
|||
add v1 and v2 to ee.VertexIDs |
|||
copy ee.Type to e |
|||
copy ee.ReplInfo to e |
|||
add ee to outputEdges, v1.EdgeIDs and v2.EdgeIDs |
|||
</pre> |
|||
==Kruskal== |
|||
<pre> |
|||
for each v: graph vertices |
|||
remove all items from v.EdgeIDs |
|||
end |
|||
sort internalEdges by (descending RedRed, ascending ReplInfo.Cost, descending available time in ReplInfo.Schedule, ascending V1ID, ascending V2ID, ascending Type) |
|||
set numExpectedTreeEdges to be the count of red and white graph vertices |
|||
initialize cSTEdges with 0 |
|||
create an empty sequence of multiedges |
|||
while internalEdges isn't empty and cSTEdges < numExpectedTreeEdges |
|||
set e to the first vertex of internalEdges |
|||
run GetComponentID with e.V1ID and store the result in comp1 |
|||
run GetComponentID with e.V2ID and store the result in comp2 |
|||
if comp1 is different from comp2 |
|||
cSTEdges++ |
|||
run AddOutEdge to add e to the sequence of multiedges |
|||
find the vertex in the graph which has its ID = comp1, and set its ComponentID to comp2 |
|||
end |
|||
remove e from internalEdges |
|||
end |
|||
return the sequence of multiedges |
|||
</pre> |
|||
==CountComponents== |
|||
<pre> |
|||
initialize numComponents with 0 |
|||
for each v: graph vertices |
|||
if v.Color is white |
|||
skip this iteration and continue the loop |
|||
end |
|||
run GetComponentID with v |
|||
if the return of the previous operation is v.ID |
|||
set v.ComponentIndex to numComponents |
|||
numComponents++ |
|||
end |
|||
end |
|||
return numComponents |
|||
</pre> |
|||
==GetSpanningTreeEdges== |
|||
<pre> |
|||
for each s: graph edgesets |
|||
for each v: graph vertices |
|||
clear the sequence v.EdgeIDs |
|||
end |
|||
for each e: graph vertices corresponding to s.EdgeIDs |
|||
for each v: graph vertices corresponding to e.VertexIDs |
|||
add e to v.Edges |
|||
end |
|||
end |
|||
run Dijkstra with only the red vertices as roots |
|||
run ProcessEdgeSet to process the forest built by Dijkstra, and accumulate the internal edges |
|||
run Dijkstra with the red and black vertices as roots |
|||
run ProcessEdgeSet to process the forest built by Dijkstra, and accumulate the internal edges |
|||
end |
|||
run SetupVertices |
|||
run ProcessEdgeSet and accumulate the internal edges |
|||
run Kruskal with the internal edges |
|||
for each v: graph vertices |
|||
if v.Color is red |
|||
set v.DistToRed to 0 |
|||
else if v can reach a red vertex |
|||
set v.DistToRed to the distance from v to such red vertex |
|||
else |
|||
set v.DistToRed to the maximum integer value |
|||
end |
|||
end |
|||
run CountComponents on the graph |
|||
run CopyOutputEdges with the output of Kruskal's algorithm |
|||
return the spanning tree returned by the previous operation |
|||
</pre> |
|||
==CreateConnection== |
|||
<pre> |
|||
set rsiteGuid to the objectGUID of the site object ancestor of rbh |
|||
set lsiteGuid to the objectGUID of the site object ancestor of lbh |
|||
run GetAllBridgeheadDCs with rsiteGuid and assuming no DC has failed |
|||
set rbhsAll to the return of the previous operation |
|||
run GetAllBridgeheadDCs with rsiteGuid |
|||
set rbhsAvail to the return of the previous operation |
|||
run GetAllBridgeheadDCs with lsiteGuid and assuming no DC has failed |
|||
set lbhsAll to the return of the previous operation |
|||
run GetAllBridgeheadDCs with lsiteGuid |
|||
set lbhsAvail to the return of the previous operation |
|||
for each cn: nTDSConnection which have the parent DC in lbhsAll and fromServer references a DC in rbhsAll |
|||
if cn was generated by the KCC and it should be used by the DRS and cn.TransportType references interSiteTransport |
|||
if cn.Schedule can be modified by the KCC and cn.Schedule isn't sch |
|||
perform an originating update to set cn.Schedule to sch |
|||
end |
|||
if cn shouldn't use the defaults to determine notification and it should notify the destination DC |
|||
if notifications are disabled between DCs in different sites in siteList in ri |
|||
perform an originating update to clear bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and NTDSCONN_OPT_USE_NOTIFY in cn |
|||
end |
|||
else |
|||
if notifications are enabled between DCs in different sites in siteList in ri |
|||
perform an originating update to set bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and NTDSCONN_OPT_USE_NOTIFY in cn |
|||
end |
|||
end |
|||
if a replication cycle should be performed in the opposite direction at the end of a replication cycle that is using cn |
|||
if a replication cycle shouldn't be performed in the opposite direction at the end of a replication cycle between DCs in different sites in siteList in ri |
|||
perform an originating update to clear bit NTDSCONN_OPT_TWOWAY_SYNC in cn |
|||
end |
|||
else |
|||
if a replication cycle should be performed in the opposite direction at the end of a replication cycle between DCs in different sites in siteList in ri |
|||
perform an originating update to set bit NTDSCONN_OPT_TWOWAY_SYNC in cn |
|||
end |
|||
end |
|||
if compression of the replicated data is disabled in cn |
|||
if the compression of IDL_DRSGetNCChanges response messages sent between DCs in different sites in siteList is enabled in ri |
|||
perform an originating update to clear bit NTDSCONN_OPT_DISABLE_INTERSITE_CONNECTION in cn |
|||
end |
|||
else |
|||
if the compression of IDL_DRSGetNCChanges response messages sent between DCs in different sites in siteList is disabled in ri |
|||
perform an originating update to set bit NTDSCONN_OPT_DISABLE_INTERSITE_CONNECTION in cn |
|||
end |
|||
end |
|||
end |
|||
end |
|||
initialize cValidConnections with 0 |
|||
for each cn: nTDSConnection which have the parent DC in lbhsAll and fromServer references a DC in rbhsAll |
|||
if (cn wasn't generated by the KCC or cn.TransportType references interSiteTransport) and it should be used by the DRS |
|||
run BridgeheadDCFailed with the nTDSDSA object referenced by cn.fromServer |
|||
run BridgeheadDCFailed with cn.parent |
|||
if the return of the two previous operations is false |
|||
cValidConnections++ |
|||
end |
|||
if cn.objectGUID isn't in keepConnections |
|||
add cn.objectGUID to keepConnections |
|||
end |
|||
end |
|||
end |
|||
if cValidConnections is 0 |
|||
initialize opt with NTDSCONN_OPT_IS_GENERATED |
|||
if notifications are enabled between DCs in different sites in siteList in ri |
|||
set bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and NTDSCONN_OPT_USE_NOTIFY in opt |
|||
end |
|||
if a replication cycle should be performed in the opposite direction at the end of a replication cycle between DCs in different sites in siteList in ri |
|||
set bit NTDSCONN_OPT_TWOWAY_SYNC in opt |
|||
end |
|||
if the compression of IDL_DRSGetNCChanges response messages sent between DCs in different sites in siteList is enabled in ri |
|||
set bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in opt |
|||
end |
|||
perform an originating update to create a new nTDSConnection object cn that is a child of lbh, cn.enabledConnection=true, cn.options=opt, cn.transportType is a reference to interSiteTransport, cn.fromServer is a reference to rbh and cn.schedule=sch |
|||
add cn.objectGUID to keepConnections |
|||
end |
|||
</pre> |
|||
==CreateConnections== |
|||
<pre> |
|||
initialized connected with true |
|||
run ColorVertices |
|||
initialize foundFailedDCs with the return of the previous operation |
|||
set localSiteVertex to the local DC's site object |
|||
if localSiteVertex.Color is white |
|||
return true |
|||
end |
|||
create an integer componentCount |
|||
run GetSpanningTreeEdges and set the value of componentCount |
|||
initialize stEdgeList with the return of the previous operation |
|||
if componentCount > 1 |
|||
set connected to false |
|||
end |
|||
for each e: stEdgeList |
|||
if e is directed and its second vertex isn't localSiteVertex |
|||
skip this iteration and continue the loop |
|||
end |
|||
if e's first vertex is localSiteVertex |
|||
set otherSiteVertex to e's second vertex |
|||
else |
|||
set otherSiteVertex to e's first vertex |
|||
end |
|||
set t to the interSiteTransport with objectGUID = e.Type |
|||
run GetBridgeheadDC with otherSiteVertex |
|||
set rbh to the return of the previous operation |
|||
if the local DC is an RODC |
|||
set lbh to the nTDSDSA object of the local DC |
|||
else |
|||
run GetBridgeheadDC with localSiteVertex |
|||
set lbh to the return of the previous operation |
|||
end |
|||
create a new schedule such that it begins when e.ReplInfo.Schedule begins and each subsequent available time is e.ReplInfo.Interval minutes after the previous available time |
|||
run CreateConnection |
|||
end |
|||
return connected |
|||
</pre> |
|||
==CreateIntersiteConnections== |
|||
<pre> |
|||
for each cr: objectClass=crossRef, children of CN=Partitions,CN=Configuration,DC=<domain> |
|||
if cr is disabled and it doesn't represent an AD NC |
|||
skip the iteration and continue the loop |
|||
end |
|||
run SetupGraph to generate a graph |
|||
run CreateConnections to create nTDSConnection objects |
|||
if the previous operation returns FALSE |
|||
mark that the graph isn't all connected |
|||
if the previous call to CreateConnections has found a failed DC |
|||
run CreateConnections again, but now assuming no DC has failed |
|||
end |
|||
end |
|||
end |
|||
return a boolean value indicating if the graph is all connected |
|||
</pre> |
</pre> |
Latest revision as of 19:39, 2 March 2010
Introduction
This is a simpler version of the DC topology algorithm as described by Microsoft at http://msdn.microsoft.com/en-us/library/dd240043(PROT.13).aspx. The goal of this document is to give an overview of the original algorithm, which is rather large.
Main functions
CreateGraph
create an empty graph sort the objectGUIDs in ascending order for each id: objectGUIDs create a vertex with id and add it to the graph end return the new graph
CreateEdge
create an edge set edge.ID to siteLink.objectGUID for each site: siteLink.siteList append site.objectGUID to edge.VertexIDs end set edge.ReplInfo.Cost to siteLink.cost set edge.ReplInfo.Options to siteLink.options set edge.ReplInfo.Interval to siteLink.replInterval if siteLink has schedule set edge.ReplInfo.schedule to siteLink.schedule else set edge.ReplInfo.schedule to null end set edge.type to the corresponding interSiteTransport.objectGUID mark edge as undirected return the new edge
CreateAutoEdgeSet
create an edgeset for each l: all siteLink objects find an edge in the graph such that its ID == l.objectGUID append l to the edgeset if edge.type = interSiteTransport.objectGUID end return the new edgeset
CreateEdgeSet
create an edgeset set edgeset.ID to siteLinkBridge.objectGUID for each l: objects with DN in siteLinkBridge.siteLinkList find an edge in the graph such that its ID == l.objectGUID append l to the edgeset if edge.type = interSiteTransport.objectGUID end return the new edgeset
SetupGraph
run CreateGraph based on the objectGUIDs of all the objects with objectClass=siteLink and children of the DN CN=Sites,CN=Configuration, and obtain a graph for each t: objectClass=interSiteTransport, child of CN=Inter-Site Transports,CN=Sites,CN=Configuration store every objectClass=siteLink, child of t in L for each l: L run CreateEdge to create an edge based on l and add it to the graph end if t doesn't have NTDSTRANSPORT_OPT_BRIDGES_REQUIRED and the local site object doesn't have NTDSTRANSPORT_OPT_W2K3_BRIDGES_REQUIRED run CreateAutoEdgeSet to create an edgeset based on L and add it to the graph else for each b: objectClass=siteLinkBridge, child of t run CreateEdgeSet to create an edgeset based on b and add it to the graph end end end return the graph
SetupVertices
for each v: all graph vertices if v.Color is white set v.ReplInfo.Cost to the maximum integer value set v.RootID and v.ComponentID to null else set v.ReplInfo.Cost to 0 set v.RootID and v.ComponentID to v.ID end set v.ReplInfo.Interval to 0 set v.ReplInfo.Options to 0xFFFFFFFF set v.ReplInfo.Schedule to null set v.Demoted to false end
CheckDemoteOneVertex
if v.Color is white exit function end if both v.AcceptBlack and v.AcceptRedRed don't contain edgeType set v.ReplInfo.Cost to the maximum integer value set v.RootID to null set v.Demoted to true end
UndemoteOneVertex
if v.Color is white exit function end set v.ReplInfo.Cost to 0 set v.RootID to v.ID set v.Demoted to false
GetComponentID
initialize u with v while u.ComponentID isn't u.ID set u to the vertex which ID is u.ComponentID end set root to u.ID reset u to v while u.ComponentID isn't u.ID set w to the vertex which ID is u.ComponentID set u.ComponentID to root set u to w end return root
CopyOutputEdges
create an empty sequence of multiedge for each e: outputEdges set v to the first vertex of e.VertexIDs set w to the second vertex of e.VertexIDs if any of v.ID or w.ID is the objectGUID of site object for the local DC's site if any of v.Color or w.Color is black, and v.DistToRed isn't the maximum integer value set e as directed if w.DistToRed < v.DistToRed swap the two first elements of e.VertexIDs end end add e to the sequence of multiedge end end return the sequence of multiedge
BridgeheadDCFailed
if automatic stale server detection is disabled for the local DC's site return false else if ??? return true else return the condition wether failed DC detection is enabled end
GetBridgeheadDC
run GetAllBridgeheadDCs if the return of the previous operation is an empty sequence return null else return the first item of the sequence end
ColorVertices
for each v: all graph vertices find a site such that its objectGUID == v.ID if the site contains one or more DCs with full replicas of the NC crossRef.nCName set v.Color to red else if the site contains one or more DCs with partial replicas of the NC crossRef.nCName set v.Color to black else set v.Color to white end end find a graph vertex such that its ID is the objectGUID of the local DC site for each v: all graph vertices for each t: objectClass=interSiteTransport, child of CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain> if localVertex.Color is red and t.name isn't "IP" and crossRef is a domain AD NC, or if the graph doesn't have any edge that contains v skip this iteration and continue the loop end run GetBridgeheadDC to find out if a bridgehead DC is available if there's no bridgehead DC currently available mark that a failed DC was found skip this iteration and continue the loop end add t to v.AcceptRedRed and to v.AcceptBlack end end return a boolean value indicating if some failed DC was found
SetupDijkstra
run SetupVertices create an empty sequence of vertices for each v: all graph vertices if v.Color is white skip this iteration and continue the loop end if (v.Color is black and black vertices aren't used as roots), or if any of v.AcceptBlack and v.AcceptRedRed doesn't contain edgeType set v.ReplInfo.Cost to the maximum integer value set v.RootID to null set v.Demoted to true else append v to the sequence of vertices end end return the sequence of vertices
CombineReplInfo
create a schedule that is the intersection of a.Schedule and b.Schedule and store it in s if s is an empty schedule return false end if a.Cost + b.Cost overflows set c.Cost to the maximum integer value else set c.Cost to a.Cost + b.Cost end set c.Interval to the maximum of a.Interval and b.Interval set c.Options to a.Options & b.Options set c.Schedule to s return true
TryNewPath
create a new replication info object and store it in newRI run CombineReplInfo to fill newRI if newRI.Cost > v.ReplInfo.Cost, or if newRI.Cost < v.ReplInfo.Cost and the call to CombineReplInfo has returned false exit function end calculate the total duration newRI.Schedule shows as available and store it in newDuration calculate the total duration v.ReplInfo.Schedule shows as available and store it in oldDuration if newRI.Cost < v.ReplInfo.Cost or newDuration > oldDuration set v.RootID to u.RootID set v.ComponentID to u.ComponentID set v.ReplInfo to newRI append v to vs end
Dijkstra
run SetupDijkstra to build the inicial vertices sequence and store the result on vs while vs isn't empty find the vertex with the least cost in vs (if there are more than one vertex with the least cost, pick the one with the least ID) and store this vertex in u remove u from vs for each e: the graph edges which have u as one of its vertices for each v: vertices in e run TryNewPath end end end
AddIntEdge
set root1 as the graph vertex with the same ID as v1.RootID set root2 as the graph vertex with the same ID as v2.RootID if both root1.Color and root2.Color are red set redRed to true else set redRed to false end if redRed if any of root1.AcceptRedRed or root2.AcceptRedRed doesn't contain e.Type exit function end else if any of root1.AcceptBlack or root2.AcceptBlack doesn't contain e.Type exit function end end create two empty replication info objects, ri and ri2 run CombineReplInfo(v1, v2, ri) and CombineReplInfo(ri, e, ri2) if any of the two previous calls returns false exit function end create an empty internal edge and store it in newIntEdge set newIntEdge.V1ID to root1.ID set newIntEdge.V2ID to root2.ID set newIntEdge.RedRed to redRed set newIntEdge.ReplInfo to ri2 set newIntEdge.Type to e.Type if newIntEdge.V1ID > newIntEdge.V2ID swap newIntEdge.V1ID and newIntEdge.V2ID end if internalEdges doesn't contain newIntEdge add newIntEdge to internalEdges end
ProcessEdge
create a vertex sequence with the vertices in e, and store it on vs sort vs by Color (red < black), ReplInfo.Cost and ID, in that order store the first element of vs in bestV for each v: graph vertices of e if v.ComponentID and v.RootID aren't null skip this iteration and continue the loop end if bestV.ComponentID and bestV.RootID and v.ComponentID and v.RootID aren't null, and bestV.ComponentID isn't v.ComponentID run AddIntEdge end end
ProcessEdgeSet
if edge set is null for each e: graph edges for each v: graph vertices of e run CheckDemoteOneVertex end run ProcessEdge for each v: graph vertices of e run UndemoteOneVertex end end else for each e: graph edges associated with the edge set run ProcessEdge end end
AddOutEdge
find the vertices v1 and v2 on the graph based on e.V1ID and e.V2ID create an empty multiedge and store it in ee set ee as undirected add v1 and v2 to ee.VertexIDs copy ee.Type to e copy ee.ReplInfo to e add ee to outputEdges, v1.EdgeIDs and v2.EdgeIDs
Kruskal
for each v: graph vertices remove all items from v.EdgeIDs end sort internalEdges by (descending RedRed, ascending ReplInfo.Cost, descending available time in ReplInfo.Schedule, ascending V1ID, ascending V2ID, ascending Type) set numExpectedTreeEdges to be the count of red and white graph vertices initialize cSTEdges with 0 create an empty sequence of multiedges while internalEdges isn't empty and cSTEdges < numExpectedTreeEdges set e to the first vertex of internalEdges run GetComponentID with e.V1ID and store the result in comp1 run GetComponentID with e.V2ID and store the result in comp2 if comp1 is different from comp2 cSTEdges++ run AddOutEdge to add e to the sequence of multiedges find the vertex in the graph which has its ID = comp1, and set its ComponentID to comp2 end remove e from internalEdges end return the sequence of multiedges
CountComponents
initialize numComponents with 0 for each v: graph vertices if v.Color is white skip this iteration and continue the loop end run GetComponentID with v if the return of the previous operation is v.ID set v.ComponentIndex to numComponents numComponents++ end end return numComponents
GetSpanningTreeEdges
for each s: graph edgesets for each v: graph vertices clear the sequence v.EdgeIDs end for each e: graph vertices corresponding to s.EdgeIDs for each v: graph vertices corresponding to e.VertexIDs add e to v.Edges end end run Dijkstra with only the red vertices as roots run ProcessEdgeSet to process the forest built by Dijkstra, and accumulate the internal edges run Dijkstra with the red and black vertices as roots run ProcessEdgeSet to process the forest built by Dijkstra, and accumulate the internal edges end run SetupVertices run ProcessEdgeSet and accumulate the internal edges run Kruskal with the internal edges for each v: graph vertices if v.Color is red set v.DistToRed to 0 else if v can reach a red vertex set v.DistToRed to the distance from v to such red vertex else set v.DistToRed to the maximum integer value end end run CountComponents on the graph run CopyOutputEdges with the output of Kruskal's algorithm return the spanning tree returned by the previous operation
CreateConnection
set rsiteGuid to the objectGUID of the site object ancestor of rbh set lsiteGuid to the objectGUID of the site object ancestor of lbh run GetAllBridgeheadDCs with rsiteGuid and assuming no DC has failed set rbhsAll to the return of the previous operation run GetAllBridgeheadDCs with rsiteGuid set rbhsAvail to the return of the previous operation run GetAllBridgeheadDCs with lsiteGuid and assuming no DC has failed set lbhsAll to the return of the previous operation run GetAllBridgeheadDCs with lsiteGuid set lbhsAvail to the return of the previous operation for each cn: nTDSConnection which have the parent DC in lbhsAll and fromServer references a DC in rbhsAll if cn was generated by the KCC and it should be used by the DRS and cn.TransportType references interSiteTransport if cn.Schedule can be modified by the KCC and cn.Schedule isn't sch perform an originating update to set cn.Schedule to sch end if cn shouldn't use the defaults to determine notification and it should notify the destination DC if notifications are disabled between DCs in different sites in siteList in ri perform an originating update to clear bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and NTDSCONN_OPT_USE_NOTIFY in cn end else if notifications are enabled between DCs in different sites in siteList in ri perform an originating update to set bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and NTDSCONN_OPT_USE_NOTIFY in cn end end if a replication cycle should be performed in the opposite direction at the end of a replication cycle that is using cn if a replication cycle shouldn't be performed in the opposite direction at the end of a replication cycle between DCs in different sites in siteList in ri perform an originating update to clear bit NTDSCONN_OPT_TWOWAY_SYNC in cn end else if a replication cycle should be performed in the opposite direction at the end of a replication cycle between DCs in different sites in siteList in ri perform an originating update to set bit NTDSCONN_OPT_TWOWAY_SYNC in cn end end if compression of the replicated data is disabled in cn if the compression of IDL_DRSGetNCChanges response messages sent between DCs in different sites in siteList is enabled in ri perform an originating update to clear bit NTDSCONN_OPT_DISABLE_INTERSITE_CONNECTION in cn end else if the compression of IDL_DRSGetNCChanges response messages sent between DCs in different sites in siteList is disabled in ri perform an originating update to set bit NTDSCONN_OPT_DISABLE_INTERSITE_CONNECTION in cn end end end end initialize cValidConnections with 0 for each cn: nTDSConnection which have the parent DC in lbhsAll and fromServer references a DC in rbhsAll if (cn wasn't generated by the KCC or cn.TransportType references interSiteTransport) and it should be used by the DRS run BridgeheadDCFailed with the nTDSDSA object referenced by cn.fromServer run BridgeheadDCFailed with cn.parent if the return of the two previous operations is false cValidConnections++ end if cn.objectGUID isn't in keepConnections add cn.objectGUID to keepConnections end end end if cValidConnections is 0 initialize opt with NTDSCONN_OPT_IS_GENERATED if notifications are enabled between DCs in different sites in siteList in ri set bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and NTDSCONN_OPT_USE_NOTIFY in opt end if a replication cycle should be performed in the opposite direction at the end of a replication cycle between DCs in different sites in siteList in ri set bit NTDSCONN_OPT_TWOWAY_SYNC in opt end if the compression of IDL_DRSGetNCChanges response messages sent between DCs in different sites in siteList is enabled in ri set bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in opt end perform an originating update to create a new nTDSConnection object cn that is a child of lbh, cn.enabledConnection=true, cn.options=opt, cn.transportType is a reference to interSiteTransport, cn.fromServer is a reference to rbh and cn.schedule=sch add cn.objectGUID to keepConnections end
CreateConnections
initialized connected with true run ColorVertices initialize foundFailedDCs with the return of the previous operation set localSiteVertex to the local DC's site object if localSiteVertex.Color is white return true end create an integer componentCount run GetSpanningTreeEdges and set the value of componentCount initialize stEdgeList with the return of the previous operation if componentCount > 1 set connected to false end for each e: stEdgeList if e is directed and its second vertex isn't localSiteVertex skip this iteration and continue the loop end if e's first vertex is localSiteVertex set otherSiteVertex to e's second vertex else set otherSiteVertex to e's first vertex end set t to the interSiteTransport with objectGUID = e.Type run GetBridgeheadDC with otherSiteVertex set rbh to the return of the previous operation if the local DC is an RODC set lbh to the nTDSDSA object of the local DC else run GetBridgeheadDC with localSiteVertex set lbh to the return of the previous operation end create a new schedule such that it begins when e.ReplInfo.Schedule begins and each subsequent available time is e.ReplInfo.Interval minutes after the previous available time run CreateConnection end return connected
CreateIntersiteConnections
for each cr: objectClass=crossRef, children of CN=Partitions,CN=Configuration,DC=<domain> if cr is disabled and it doesn't represent an AD NC skip the iteration and continue the loop end run SetupGraph to generate a graph run CreateConnections to create nTDSConnection objects if the previous operation returns FALSE mark that the graph isn't all connected if the previous call to CreateConnections has found a failed DC run CreateConnections again, but now assuming no DC has failed end end end return a boolean value indicating if the graph is all connected