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