k-Connectivity detection and restoration are important problems in graph theory and computer networks. A graph is k-connected if it remains connected after removing k-1 arbitrary nodes. The k-connectivity is an important property of a distributed system because a k-connected network can tolerate k-1 node failures without losing the network connectivity. To achieve the k-connectivity in a network, we need to determine the current connectivity value and try to increase connectivity if the current k is lower than the desired value. This chapter reviews the central and distributed algorithms for detecting and restoring the k-connectivity in graphs and distributed systems. The algorithms will be compared from complexity, accuracy and efficiency perspectives.
TopIntroduction
The connectivity is one of the key properties in all networks. A network is said to be connected if there is at least one path between every node. Most of the computer networks such as LANs and WANs have communication infrastructures (e.g. cables, switches and routers) and provide high reliability from the connectivity perspective. However it is not possible to prepare a communication infrastructure in all environments, whereas using ad hoc or mobile wireless sensor networks is inevitable or affordable in some applications. In this kind of networks there is no communication infrastructure and all nodes communicate with each other using some intermediate nodes. These kinds of networks provide lower connection reliability, because failure in some nodes can cut off the packet flow in the network.
A network is called 1-connected if there is at least one path between every pair of nodes and there exists at least one node, which its removal, divides the network to separated segments. Such a node is called cut vertex. Having a 1-connected topology puts the network in high division risk. There are many researches that have been made to find and resolve the cut vertices in a network (Atay & Bayazit, 2010)(Dagdeviren & Akram, 2014)(Tarjan, 1972). In ad hoc and wireless sensor networks, for example, the nodes typically are battery powered and it is possible that some nodes die due to energy consumptions caused by packet transmissions. A k-connected network can tolerate and remain connected if k-1 arbitrary nodes stop working. Figure 1 shows a network with k=2. The nodes that their removal from graph decrease k are referred as MinCut set. In Figure 1 the red nodes with thick circles belong to MinCut set and removing any of them can reduces the disjoint path count while a failure in normal (black) nodes does not affect k.
Figure 1. A sample network with k=2
TopDefinitions
The following symbols and terms have been used to explain and analysis the proposed algorithms in the next sections.
- •
The network is modeled as an undirected graph G=(V,E) where V is the set of vertices that represents the nodes and E is the set of edges that indicates the links between nodes.
- •
dv indicates the number of links connected to v or the degree of v in G.
- •
d is the minimum degree of G. It means that all nodes in G have at least d neighbors.
- •
D is the network diameter which is the length of the longest short path between two nodes.
- •
∆ is the maximum degree in G. So we have ∆=max(dv: v∈V).
TopConcepts Of Complex Networks
Generally most of the networks in real systems do not follow neither a specific topology pattern nor a random graph model such as Erdos and Renyi model (Erdos,1959). These kinds of the networks, which are referred as complex networks, have the most frequency in the biological, social and technological networks (Newman, 2003). Although complex networks have no regular structure or randomness, they have some common properties which are used as metrics to analyze them. These properties provide a global view of the network structure and usually affect each other or network functionality in various ways. In this section some of the key properties of complex networks and their effect on connectivity are presented.