DC topology: Difference between revisions

From SambaWiki
No edit summary
No edit summary
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>
</pre>


Line 109: Line 211:
end
end
return a boolean value indicating if some failed DC was found
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>
</pre>

Revision as of 05:30, 1 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