ORDER-P - AN ALGORITHM TO ORDER NETWORK PARTITIONINGS

A network partitioning occurs when failures fragment the network into at least 2 sub-networks. This causes the network performance to degrad e; many techniques have been proposed to combat this degradation. The number of possible partitionings in a fully connected network of n nod es is greater than 2n, for large n. Thus, analysis of partitioning-res ilient algorithms is extremely difficult due to the difficulty of comp uting 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 Enu meration (MPSE) algorithm of Li & Silvester. By looking at only the mo st probable partitionings, the performance of the network can be estim ated 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 partiti onings. However, three algorithms (Order, Order-II, NewOrder) that gen erate network states in order of their decreasing state probabilities are known, for dual-mode (up/down) components. We improvised these alg orithms to generate the most probable network partitionings and then c ompared them with Order-P. Order-P has a lower computational complexit y than all of the three improvised algorithms. Order-P is applied in t he real world and demonstrates its value in performance modeling of di stributed 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 part itionings obtained using Order-P are estimates, we believe that the ap proximation is close enough, and we substantiate this with an example. A methodology to compute performance measures under conditions of net work partitioning has also been proposed, and corroborated with exampl es in the domain of distributed database systems.