DC topology

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