Note
Access to this page requires authorization. You can try signing in or changing directories.
Access to this page requires authorization. You can try changing directories.
The following methods process the site graph and compute the minimum-cost spanning tree.
-
/***** GetSpanningTreeEdges *****/ /* Calculate the spanning tree and return the edges that include the * vertex for the local site. * INOUT: g - Site graph. * OUT: componentCount - Set to the number of graph components * calculated by Kruskal's algorithm. If 1, all sites are * connected by a spanning tree. Otherwise, one or more sites * could not be connected in a spanning tree. * RETURNS: Edges that include the vertex for the local site. */ GetSpanningTreeEdges(INOUT GRAPH g, OUT int componentCount) : SET<MULTIEDGE> { /* Phase I: Run Dijkstra's algorithm and build up a list of * internal edges, which are really just shortest-paths * connecting colored vertices. */ LET internalEdges be an empty sequence of INTERNALEDGE FOR each s in g.EdgeSets LET edgeType be NULL GUID FOR each v in g.Vertices REMOVE all items from v.EdgeIDs ENDFOR FOR each edge e in g.Edges such that s.EdgeIDs contains e.ID SET edgeType to e.Type FOR each vertex v in g.Vertices such that e.VertexIDs contains v.ID APPEND e to v.Edges ENDFOR ENDFOR /* Run Dijkstra's algorithm with just the red vertices as * the roots */ CALL Dijkstra(g, edgeType, FALSE) /* Process the minimum-spanning forest built by Dijkstra, * and add any inter-tree edges to our list of internal * edges */ CALL ProcessEdgeSet(g, s, internalEdges) /* Run Dijkstra's algorithm with red and black vertices as * the root vertices */ CALL Dijkstra(g, edgeType, TRUE) /* Process the minimum-spanning forest built by Dijkstra, * and add any inter-tree edges to our list of internal * edges */ CALL ProcessEdgeSet(g, s, internalEdges) ENDFOR /* Process the implicit empty edge set */ CALL SetupVertices(g) CALL ProcessEdgeSet(g, NULL, internalEdges) /* Phase II: Run Kruskal's Algorithm on the internal edges. */ LET outputEdges be the result of Kruskal(g, internalEdges) /* Phase III: Post-process the output: * - Traverse tree structure to find one-way black-black edges * - Determine the component structure */ FOR each v in g.Vertices IF v.Color = COLOR.RED SET v.DistToRed to 0 ELSEIF there exists a path from v to a COLOR.RED vertex SET v.DistToRed to the length of the shortest such path ELSE SET v.DistToRed to MAX DWORD ENDIF ENDFOR SET componentCount to CountComponents(g) LET stEdgeList be CopyOutputEdges(g, outputEdges) RETURN stEdgeList } /***** GetBridgeheadDC *****/ /* Get a bridghead DC. * IN: siteObjectGUID - objectGUID of the site object representing * the site for which a bridgehead DC is desired. * IN: cr - crossRef for NC to replicate. * IN: t - interSiteTransport object for replication traffic. * IN: partialReplicaOkay - TRUE if a DC containing a partial * replica or a full replica will suffice, FALSE if only * a full replica will suffice. * IN: detectFailedDCs - TRUE to detect failed DCs and route * replication traffic around them, FALSE to assume no DC * has failed. * RETURNS: nTDSDSA object for the selected bridgehead DC, or NULL if * none is available. */ GetBridgeheadDC(IN GUID siteObjectGUID, IN crossRef cr, IN interSiteTransport t, IN bool partialReplicaOkay, IN bool detectFailedDCs) : nTDSDSA { LET bhs be the result of GetAllBridgeheadDCs(siteObjectGUID, cr, t, partialReplicaOkay, detectFailedDCs) IF bhs is empty RETURN NULL ELSE RETURN bhs[0] ENDIF } /***** GetAllBridgeheadDCs *****/ /* Get all bridghead DCs satisfying the given criteria. * IN: siteObjectGUID - objectGUID of the site object representing * the site for which bridgehead DCs are desired. * IN: cr - crossRef for NC to replicate. * IN: t - interSiteTransport object for replication traffic. * IN: partialReplicaOkay - TRUE if a DC containing a partial * replica or a full replica will suffice, FALSE if only * a full replica will suffice. * IN: detectFailedDCs - TRUE to detect failed DCs and route * replication traffic around them, FALSE to assume no DC * has failed. * RETURNS: nTDSDSA objects for available bridgehead DCs. */ GetAllBridgeheadDCs(IN GUID siteObjectGUID, IN crossRef cr, IN interSiteTransport t, IN bool partialReplicaOkay, IN bool detectFailedDCs) : SEQUENCE OF nTDSDSA { LET bhs be an empty sequence of nTDSDSA objects LET s be the site object such that s!objectGUID = siteObjectGUID LET k be an object such that s!lDAPDisplayName = nTDSDSA and classSchema in s!objectClass LET allDCsInSite be the sequence of objects o that are descendants of s such that o!objectCategory = k FOR each dc in allDCsInSite IF t!bridgeheadServerListBL has one or more values and t!bridgeheadServerListBL does not contain a reference to the parent object of dc Skip dc ENDIF IF dc is in the same site as the local DC IF a replica of cr!nCName is not in the set of NC replicas that "should be present" on dc or a partial replica of the NC "should be present" but partialReplicaOkay = FALSE Skip dc ENDIF ELSE IF an NC replica of cr!nCName is not in the set of NC replicas that "are present" on dc or a partial replica of the NC "is present" but partialReplicaOkay = FALSE Skip dc ENDIF ENDIF IF AmIRODC() and cr!nCName corresponds to default NC then Let dsaobj be the nTDSDSA object of the dc IF dsaobj.msDS-Behavior-Version < DS_BEHAVIOR_WIN2008 Skip dc ENDIF ENDIF IF t!name ≠ "IP" and the parent object of dc has no value for the attribute specified by t!transportAddressAttribute Skip dc ENDIF IF BridgeheadDCFailed(dc!objectGUID, detectFailedDCs) = TRUE Skip dc ENDIF APPEND dc to bhs ENDFOR IF bit NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED is set in s!options SORT bhs such that all GC servers precede DCs that are not GC servers, and otherwise by ascending objectGUID ELSE SORT bhs in a random order ENDIF RETURN bhs } /***** BridgeheadDCFailed *****/ /* Determine whether a given DC is known to be in a failed state. * IN: objectGUID - objectGUID of the DC's nTDSDSA object. * IN: detectFailedDCs - TRUE if and only if failed DC detection is * enabled. * RETURNS: TRUE if and only if the DC should be considered to be in a * failed state. */ BridgeheadDCFailed(IN GUID objectGUID, IN bool detectFailedDCs) : bool { IF detectFailedDCs is FALSE RETURN FALSE ENDIF IF bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set in the options attribute of the site settings object for the local DC's site RETURN FALSE ENDIF IF a tuple z exists in the kCCFailedLinks or kCCFailedConnections variables such that z.UUIDDsa = objectGUID, z.FailureCount > 1, and the current time - z.TimeFirstFailure > 2 hours RETURN TRUE ENDIF RETURN FALSE } /***** SetupVertices *****/ /* Setup the fields of the vertices that are relevant to Phase I * (Dijkstra's Algorithm). For each vertex, set up its cost, * root vertex, and component. This defines the shortest-path * forest structures. * INOUT: graph - Site graph. */ SetupVertices(INOUT GRAPH g) { FOR each v in g.Vertices IF v.Color = COLOR.WHITE SET v.ReplInfo.Cost to MAX DWORD SET v.RootID to NULL GUID SET v.ComponentID to NULL GUID ELSE SET v.ReplInfo.Cost to 0 SET v.RootID to v.ID SET v.ComponentID to v.ID ENDIF SET v.ReplInfo.Interval to 0 SET v.ReplInfo.Options to 0xFFFFFFFF SET v.ReplInfo.Schedule to NULL SET v.HeapLocation to STHEAP_NOT_IN_HEAP SET v.Demoted to FALSE ENDFOR } /***** Dijkstra *****/ /* Run Dijkstra's algorithm with the red (and possibly black) vertices * as the root vertices, and build up a shortest-path forest. * INOUT: g - Site graph. * IN: edgeType - Type of the edges in the current edge set. * IN: fIncludeBlack - If this is true, black vertices are also used * as roots. */ Dijkstra(INOUT GRAPH g, IN GUID edgeType, IN bool fIncludeBlack) { LET vs be the result of SetupDijkstra(g, edgeType, fIncludeBlack) WHILE vs is not empty LET c be the least ReplInfo.Cost of any vertex in vs LET u be the vertex in vs with the least ID of all vertices with ReplInfo.Cost = c REMOVE u from vs FOR each e in g.Edges such that u.EdgeIDs contains e.ID FOR each vertexId in e.VertexIDs LET v be the vertex in g.Vertices such that v.ID = vertexId CALL TryNewPath(g, vs, u, e, v) ENDFOR ENDFOR ENDWHILE } /***** SetupDijkstra *****/ /* Build the initial sequence for use with Dijkstra's algorithm. It * will contain the red and black vertices as root vertices, unless * these vertices accept no edges of the current edgeType, or unless * black vertices are not being including. * INOUT: g - Site graph. * IN: edgeType - Type of the edges in the current edge set. * IN: fIncludeBlack - If this is true, black vertices are also used * as roots. * RETURNS: Sequence of vertices. */ SetupDijkstra(INOUT GRAPH g, IN GUID edgeType, IN bool fIncludeBlack) : SEQUENCE<VERTEX> { CALL SetupVertices(g) LET vs be an empty sequence of VERTEX FOR each v in g.Vertices IF v.Color = COLOR.WHITE Skip v ENDIF IF (v.Color = COLOR.BLACK and fIncludeBlack = FALSE) or v.AcceptBlack does not contain edgeType or v.AcceptRedRed does not contain edgeType /* If black vertices are not being allowing, or if this * vertex accepts neither red-red nor black edges, then * 'demote' it to a WHITE vertex for the purposes of Phase * I. Note that the 'Color' member of the vertex structure * is not changed. */ SET v.ReplInfo.Cost to MAX DWORD SET v.RootID to NULL GUID SET v.Demoted to TRUE ELSE APPEND v to vs ENDIF ENDFOR RETURN vs } /***** TryNewPath *****/ /* Helper function for Dijkstra's algorithm. A new path has been found * from a root vertex to vertex v. This path is (u->root, ..., u, v). * Edge e is the edge connecting u and v. If this new path is better * (in this case cheaper, or has a longer schedule), update v to use * the new path. * INOUT: g - Site graph. * INOUT: vs - Vertices being evaluated. * IN: u - Vertex connected by e to v. * IN: e - Edge between u and v. * INOUT: v - Vertex connected by e to u. */ TryNewPath(INOUT GRAPH g, INOUT SEQUENCE<VERTEX> vs, IN VERTEX u, IN MULTIEDGE e, INOUT VERTEX v) { LET newRI be an empty REPLINFO LET fIntersect be the result of CombineReplInfo(g, u.ReplInfo, Edge.ReplInfo, OUT newRI) IF newRI.Cost > v->ReplInfo.Cost RETURN ENDIF IF newRI.Cost < v.ReplInfo.Cost and fIntersect = FALSE RETURN ENDIF LET newDuration be the total duration newRI.Schedule shows as available LET oldDuration be the total duration v.ReplInfo.Schedule shows as available IF newRI.cost < v.ReplInfo.Cost or newDuration > oldDuration /* The new path to v is either cheaper or has a longer * schedule. Update v with its new root vertex, cost, and * replication info. */ SET v.RootID to u.RootID SET v.ComponentID to u.ComponentID SET v.ReplInfo to newRI APPEND v to vs ENDIF } /***** CombineReplInfo *****/ /* Merge schedules, replication intervals, options and costs. * INOUT: g - Site graph. * IN: a - Replication info to combine with b. * IN: b - Replication info to combine with a. * OUT: c - Combination of a and b. * RETURNS: TRUE if schedules intersect, FALSE if they don't. */ CombineReplInfo(INOUT GRAPH g, IN REPLINFO a, IN REPLINFO b, OUT REPLINFO c) : bool { LET s be the schedule that is the intersection of a.Schedule and b.Schedule, such that a given time is available in c if and only if that time is available in both a.Schedule and b.Schedule IF s has no available time RETURN FALSE ENDIF IF a.Cost + b.Cost overflows SET c.Cost to MAX DWORD ELSE SET c.Cost to a.Cost + b.Cost ENDIF SET C.Interval to maximum of a.Interval and b.Interval SET C.Options to a.Options BITWISE-AND b.Options SET C.Schedule = s RETURN TRUE } /***** ProcessEdgeSet *****/ /* After running Dijkstra's algorithm to determine the shortest-path * forest, examine all edges in this edge set. Find all inter-tree * edges, from which to build the list of 'internal edges', which * will later be passed on to Kruskal's algorithm. * INOUT: g - Site graph. * IN: s - Edge set, or NULL for the implicit edge set with no edges. * INOUT: internalEdges - Sequence to which to add new internal edges. */ ProcessEdgeSet(INOUT GRAPH g, IN MULTIEDGESET s, INOUT SEQUENCE<INTERNALEDGE> internalEdges) { IF s = NULL FOR each e in g.Edges FOR each v in g.Vertices such that e.VertexIDs contains v.ID CALL CheckDemoteOneVertex(v, e.Type) ENDFOR CALL ProcessEdge(g, e, internalEdges) FOR each v in g.Vertices such that e.VertexIDs contains v.ID CALL UndemoteOneVertex(v) ENDFOR ENDFOR ELSE FOR each e in g.Edges such s.EdgeIDs contains e.ID CALL ProcessEdge(g, e, internalEdges) ENDFOR ENDIF } /***** CheckDemoteOneVertex *****/ /* Demote one vertex if necessary * INOUT: v - Vertex to check and possibly demote. * IN: edgeType - Type of edge being processed. */ CheckDemoteOneVertex(INOUT VERTEX v, IN GUID edgeType) { IF v.Color = COLOR.WHITE RETURN ENDIF IF v.AcceptBlack does not contain edgeType and v.AcceptRedRed does not contain edgeType /* If this vertex accepts neither red-red nor black edges, * then 'demote' it to a WHITE vertex for the purposes of * Phase I. Note that the 'Color' member of the vertex * structure is not changed. */ SET v.ReplInfo.Cost to MAX DWORD SET v.RootID to NULL GUID SET v.Demoted to TRUE ENDIF } /**** UndemoteOneVertex ******/ /* Clear the demoted state of a vertex * INOUT: v - Vertex to 'undemote'. */ UndemoteOneVertex(INOUT VERTEX v) { IF v.Color = COLOR.WHITE RETURN ENDIF SET v.ReplInfo.Cost to 0 SET v.RootID to v.ID SET v.Demoted to FALSE } /***** ProcessEdge *****/ /* After running Dijkstra's algorithm, this function examines a * multi-edge and adds internal edges between every tree connected by * this edge. * INOUT: g - Site graph. * IN: e - Multi-edge to examine. * INOUT: internalEdges - Sequence to which to add any new internal * edges. */ ProcessEdge(INOUT GRAPH g, IN MULTIEDGE e, INOUT SEQUENCE<INTERNALEDGE> internalEdges) { /* Find the best vertex to be the 'root' of this multi-edge. */ LET vs be a sequence containing each vertex v such that e.VertexIDs contains v.ID SORT vs such that RED vertices precede BLACK vertices, a vertex with lower ReplInfo.Cost precedes a vertex with higher ReplInfo.Cost if both vertices have the same Color, and a vertex with a lower ID precedes a vertex with higher ID if both vertices have the same Color and ReplInfo.Cost LET bestV be vs[0] /* Add to internalEdges an edge from every colored vertex to bestV.*/ FOR each vertex v in g.Vertices such that e.VertexIDs contains v IF v.ComponentID ≠ NULL GUID and v.RootID ≠ NULL GUID Skip v ENDIF /* Only add this edge if it is a valid inter-tree edge. * (The two vertices must be reachable from the root vertices, * and in different components.) */ IF bestV.ComponentID ≠ NULL GUID and bestV.RootID ≠ NULL GUID and v.ComponentID ≠ NULL GUID and bestV.RootID ≠ NULL GUID and bestV.ComponentID ≠ v.ComponentID CALL AddIntEdge(g, internalEdges, e, bestV, v) ENDIF ENDFOR } /***** AddIntEdge *****/ /* Add an edge to the list of edges that will be processed with * Kruskal's. * The endpoints are in fact the roots of the vertices to pass in, so * the endpoints are always colored vertices. * INOUT: g - Site graph. * INOUT: internalEdges - Sequence to which to add the new internal * edge. * IN: e - Existing edge being examined. * IN: v1 - Vertex to connect with new internal edge. * IN: v2 - Vertex to connect with new internal edge. */ AddIntEdge(INOUT GRAPH g, INOUT SEQUENCE<INTERNALEDGE> internalEdges, IN MULTIEDGE e, IN VERTEX v1, IN VERTEX v2) { /* The edge that is passed on to Kruskal's algorithm actually goes * between the roots of the two shortest-path trees. */ LET root1 be the vertex in g.Vertices such that root1.ID = v1.RootID LET root2 be the vertex in g.Vertices such that root2.ID = v2.RootID /* Check if both endpoints will allow this type of edge */ IF root1.Color = COLOR.RED and root2.Color = COLOR.RED LET redRed be TRUE ELSE LET redRed be FALSE ENDIF IF redRed = TRUE IF root1.AcceptRedRed does not contain e.Type or root2.AcceptRedRed does not contain e.Type RETURN ENDIF ELSE IF root1.AcceptBlack does not contain e.Type or root2.AcceptBlack does not contain e.Type RETURN ENDIF ENDIF /* Combine the schedules of the path from root1 to v1, root2 to * v2, and edge e */ LET ri be an empty REPLINFO LET ri2 be an empty REPLINFO IF CombineReplInfo(g, v1.ReplInfo, v2.ReplInfo, OUT ri) = FALSE or CombineReplInfo(g, ri, e.ReplInfo, OUT ri2) = FALSE RETURN ENDIF /* Set up the internal simple edge from root1 to root2 */ LET newIntEdge be an empty INTERNALEDGE 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 /* Sort newIntEdge's vertices by ID */ IF newIntEdge.V1ID > newIntEdge.V2ID Swap newIntEdge.V1ID and newIntEdge.V2ID ENDIF IF internalEdges does not contain an INTERNALEDGE that is identical to newIntEdge APPEND newIntEdge to internalEdges ENDIF } /***** Kruskal *****/ /* Run Kruskal's minimum-cost spanning tree algorithm on the internal * edges (that represent shortest paths in the original graph between * colored vertices). * INOUT: g - Site graph. * INOUT: internalEdges - Edges between trees. * RETURNS: Spanning tree edges for the vertex representing the local * DC's site. */ Kruskal(INOUT GRAPH g, INOUT SEQUENCE<INTERNALEDGE> internalEdges) : SEQUENCE<MULTIEDGE> { FOR each v in g.Vertices REMOVE all items from v.EdgeIDs ENDFOR SORT internalEdges by (descending RedRed, ascending ReplInfo.Cost, descending available time in ReplInfo.Schedule, ascending V1ID, ascending V2ID, ascending Type) LET numExpectedTreeEdges be the count of vertices v in g.Vertices such that v.Color = COLOR.RED or v.Color = COLOR.WHITE LET cSTEdges be 0 LET outputEdges be an empty sequence of MULTIEDGE WHILE internalEdges is not empty and cSTEdges < numExpectedTreeEdges LET e be internalEdges[0] /* Cycles in the spanning tree must be prevented. If edge e * is to be added, its endpoints must be in different * components. */ LET comp1 be the return of GetComponentID(g, e.V1ID) LET comp2 be the return of GetComponentID(g, e.V2ID) IF comp1 ≠ comp2 /* Add spanning tree edge. */ INCREMENT cSTEdges by 1 CALL AddOutEdge(g, outputEdges, e) /* Combine the two connected components. */ LET v be the vertex in g.Vertices such that v.ID = comp1 SET v.ComponentID to comp2 ENDIF REMOVE e from internalEdges ENDWHILE RETURN outputEdges } /***** GetComponentID *****/ /* Returns the id of the component containing vertex v by traversing * the up-tree implied by the component pointers. * INOUT: g - Site graph. * INOUT: v - Vertex for which the component ID is desired. * RETURNS: The component ID of v. */ GetComponentID(INOUT GRAPH g, INOUT VERTEX v) : GUID { /* Find root of the up-tree created by component pointers */ LET u be v WHILE u.ComponentID ≠ u.ID LET id be u.ComponentID SET u to the vertex in g.Vertices such that u.ID = id ENDWHILE LET root be u.ID /* Compress the path to the root */ SET u to v WHILE u.ComponentID ≠ u.ID LET id be u.ComponentID LET w be the vertex in g.Vertices such that w.ID = id SET u.ComponentID to root SET u to w ENDWHILE RETURN root } /***** AddOutEdge *****/ /* A new edge, e, has been found for the spanning tree edge. Add this * edge to the list of output edges. * INOUT: g - Site graph. * INOUT: outputEdges - Sequence to which to add the output edge. * IN: e - Edge to add. */ AddOutEdge(INOUT GRAPH g, INOUT SEQUENCE<MULTIEDGE> outputEdges, IN INTERNALEDGE e) { LET v1 be the vertex in g.Vertices such that v1.ID = e.V1ID LET v2 be the vertex in g.Vertices such that v2.ID = e.V2ID /* Create an output multi edge */ LET ee be an empty MULTIEDGE SET ee.Directed to FALSE APPEND v1.ID to ee.VertexIDs APPEND v2.ID to ee.VertexIDs SET ee.Type to e.Type SET ee.ReplInfo to e.ReplInfo APPEND ee to outputEdges /* Also add this new spanning-tree edge to the edge lists of * its endpoints. */ APPEND ee to v1.EdgeIDs APPEND ee to v2.EdgeIDs } /***** CountComponents *****/ /* Count the number of components. A component is considered to be a * bunch of colored vertices that are connected by the spanning tree. * Vertices whose component id is the same as their vertex id are the * root of a connected component. * * When a root of a component has been found, record its 'component * index'. The component indices are a contiguous sequence of numbers * that uniquely identify a component. * * INOUT: g - Site graph. * RETURNS: Number of components. */ CountComponents(INOUT GRAPH g) : int { LET numComponents be 0 FOR each v in g.Vertices IF v.Color = COLOR.WHITE Skip v ENDIF LET compId be the result of GetComponentID(g, v) IF compId = v.ID /* It's a component root */ SET v.ComponentIndex to numComponents Increment numComponents by 1 ENDIF ENDFOR RETURN numComponents } /***** CopyOutputEdges *****/ /* Copy all spanning tree edges from outputEdges that contain the * vertex for DCs in the local DC's site. * INOUT: g - Site graph. * IN: outputEdges - All spanning tree edges. * RETURNS: Spanning tree edges for DCs in the local DC's site. */ CopyOutputEdges(INOUT GRAPH g, IN SEQUENCE<MULTIEDGE> outputEdges) : SEQUENCE<MULTIEDGE> { LET s be an empty sequence of MULTIEDGE LET vid be the objectGUID of site object for the local DC's site FOR each e in outputEdges LET v be the vertex in g.Vertices such that v.ID = e.VertexIDs[0] LET w be the vertex in g.Vertices such that w.ID = e.VertexIDs[1] IF v.ID = vid or w.ID = vid /* Check if this edge meets the criteria of a 'directed * edge'. */ IF (v.Color = COLOR.BLACK or w.Color = COLOR.BLACK) and v.DistToRed ≠ MAX DWORD SET e.Directed to TRUE /* Swap the vertices so that e->vertexNames[0] is * closer to a red vertex than e->vertexNames[1]. */ IF w.DistToRed < v.DistToRed Swap e.VertexIDs[0] and e.VertexIDs[1] ENDIF ENDIF APPEND e to s ENDIF ENDFOR RETURN s }