Graph contraction

Part B in GUID-ABC44393-68ED-4C09-B6FC-CAE665A4CC4E.html#GUID-ABC44393-68ED-4C09-B6FC-CAE665A4CC4E___TOPO_SPLIT_APDX_DATA_MODEL_23810 represents the working devices and links for graph contraction.

As explanation, a common abstraction for relational networks is a graph, in which entities are represented by vertices, and observed relationships between the entities are represented as edges that connect the vertices. In addition, the vertices and edges may be attributed by weights to describe the strength of the vertices and the connections.

For the managed IP network that is to be split into domains, the devices in the network are the graph’s vertices, and the network connections between the devices are the graph’s edges. The weight of a device is proportional to the number of connections to the device, where a higher number indicates a larger number of connections.

Other weights, or attributes, of a device are ManagedAdapterWeight, UnmanagedAdapterWeight, and PerfAdapterWeight, which pertain to a device’s managed, unmanaged, and performance-managed network adapters, respectively. Performance-managed network adapters belong to devices that are to have their components polled every minute. The higher the weight for a particular type of network adapter, the higher the probability that network adapters of that type will be distributed evenly across the domains.

To construct the graph, that is, to partition the devices into domains, the Kernighan-Lin algorithm starts by selecting one device (node) for each domain. From there, the algorithm uses a nearest-neighbor approach to assign the remaining devices to the domains. The neighborhood of a device is the set of all adjacent devices, including the device, itself.

For each device, the Kernighan-Lin algorithm considers the device’s neighbors and evaluates the gain in modularity that would occur by moving the device from its current domain to the domain of one of its neighbors. The device is then placed in the domain for which this gain is maximum until no individual move can improve the modularity.

For an incremental topology split, the Kernighan-Lin algorithm assigns a new device to a previously defined domain by looking only at the device’s neighborhood, or the set of devices that are two hops away, without redoing a full topology split. At the same time, the algorithm tries to improve the device-to-domain mapping by moving single devices into different domains, which explains why devices are sometimes moved to different domains during an incremental topology split.