DC topology
From SambaWiki
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