Order-P: An algorithm to order network partitionings

Abstract

A network partitioning occurs when failures fragment the network into at least 2 sub-networks. This causes the network performance to degrade; many techniques have been proposed to combat this degradation. The number of possible partitionings in a fully connected network of n nodes is greater than 2n, for large n. Thus, analysis of partitioning-resilient algorithms is extremely difficult due to the difficulty of computing the probabilities of occurrence of the partitionings. We propose an algorithm that orders network partitionings in decreasing order of probability. This algorithm is similar to the Most Probable State Enumeration (MPSE) algorithm of Li & Silvester. By looking at only the most probable partitionings, the performance of the network can be estimated well. This approach also gives bounds on the network performance. Two distinct equally-important goals have been attained in this paper: Algorithm Order-P is proposed; it generates network partitionings in the order of their decreasing probabilities of occurrence. We are not aware of any other algorithm that specifically orders network partitionings. However, three algorithms (Order, Order-II, NewOrder) that generate network states in order of their decreasing state probabilities are known, for dual-mode (up/down) components. We improvised these algorithms to generate the most probable network partitionings and then compared them with Order-P. Order-P has a lower computational complexity than all of the three improvised algorithms. Order-P is applied in the real world and demonstrates its value in performance modeling of distributed systems. With this algorithm, performance modeling of fairly large systems, hitherto unattempted due to large computational costs, is feasible. Although the probabilities of occurrence of various partitionings obtained using Order-P are estimates, we believe that the approximation is close enough, and we substantiate this with an example. A methodology to compute performance measures under conditions of network partitioning has also been proposed, and corroborated with examples in the domain of distributed database systems.