File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Order-P: An algorithm to order network partitionings

TitleOrder-P: An algorithm to order network partitionings
Authors
Issue Date1994
Citation
Ieee Transactions On Reliability, 1994, v. 43 n. 2, p. 310-320 How to Cite?
AbstractA 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.
Persistent Identifierhttp://hdl.handle.net/10722/155002
ISSN
2015 Impact Factor: 2.287
2015 SCImago Journal Rankings: 1.930
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorBanerjee, Sujataen_US
dc.contributor.authorLi, Victor OKen_US
dc.date.accessioned2012-08-08T08:31:28Z-
dc.date.available2012-08-08T08:31:28Z-
dc.date.issued1994en_US
dc.identifier.citationIeee Transactions On Reliability, 1994, v. 43 n. 2, p. 310-320en_US
dc.identifier.issn0018-9529en_US
dc.identifier.urihttp://hdl.handle.net/10722/155002-
dc.description.abstractA 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.en_US
dc.languageengen_US
dc.relation.ispartofIEEE Transactions on Reliabilityen_US
dc.titleOrder-P: An algorithm to order network partitioningsen_US
dc.typeArticleen_US
dc.identifier.emailLi, Victor OK:vli@eee.hku.hken_US
dc.identifier.authorityLi, Victor OK=rp00150en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/24.295014en_US
dc.identifier.scopuseid_2-s2.0-0028445524en_US
dc.identifier.volume43en_US
dc.identifier.issue2en_US
dc.identifier.spage310en_US
dc.identifier.epage320en_US
dc.identifier.isiWOS:A1994NW83300025-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridBanerjee, Sujata=7404545046en_US
dc.identifier.scopusauthoridLi, Victor OK=7202621685en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats