DC topology: Difference between revisions

From SambaWiki
No edit summary
No edit summary
Line 232: Line 232:
end
end
return the sequence of vertices
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>
</pre>

Revision as of 23:33, 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

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