Network partition: Difference between revisions
mNo edit summary |
|||
| Line 6: | Line 6: | ||
== Network Partition for Optimization == |
== Network Partition for Optimization == |
||
[[File:Network Partition for Optimization.pdf|alt=Network Partition|thumb|Network partition with discarding of the most irrelevant interactions between |
[[File:Network Partition for Optimization.pdf|alt=Network Partition|thumb|Network partition with discarding of the most irrelevant interactions between elements <ref name="Network partition">{{cite journal|author1=Ignatov, D.Yu.|author2=Filippov, A.N.|author3=Ignatov, A.D.|author4=Zhang, X.|title=Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks|journal=Proc. ISP RAS|date=2017|volume=28|pages=141–152|doi=10.15514/ISPRAS-2016-28(6)-10|arxiv=1701.06595|url=https://arxiv.org/pdf/1701.06595.pdf}}</ref>]] |
||
To break a [[NP-hardness|NP-hard]] task of network optimization down into subtasks the network can be decomposed into relatively independent subnets. In order to perform partition, network is firstly represented with the weighted complete graph, where each vertex corresponds to a network element and each edge has weight equals to the rank of correlation between pair of correspondent elements. Then the most irrelevant interactions between elements of network are removed. Based on remaining connections, the network is further split into relatively independent subnets. The result of splitting process can be a set of alternative splits, where every split consists of all possible non-overlapping subnets within network.<ref name="Network partition" /> The optimization of subnets retrieved form the large network can be performed independently on computer cluster. |
To break a [[NP-hardness|NP-hard]] task of network optimization down into subtasks the network can be decomposed into relatively independent subnets. In order to perform partition, network is firstly represented with the weighted complete graph, where each vertex corresponds to a network element and each edge has weight equals to the rank of correlation between pair of correspondent elements. Then the most irrelevant interactions between elements of network are removed. Based on remaining connections, the network is further split into relatively independent subnets. The result of splitting process can be a set of alternative splits, where every split consists of all possible non-overlapping subnets within network.<ref name="Network partition" /> The optimization of subnets retrieved form the large network can be performed independently on computer cluster. |
||
Revision as of 09:40, 2 October 2017
A network partition refers to network decomposition into relatively independent subnets for their separate optimization as well as network split due to the failure of network devices. In both cases the partition-tolerant behavior of subntes is expected. This means that even after network is partitioned into multiple sub-systems, it still works correctly.
For example, in a network with multiple subnets where nodes A and B are located in one subnet and nodes C and D are in another, a partition occurs if the switch between the two subnets fails. In that case nodes A and B can no longer communicate with nodes C and D, but all nodes A-D work the same as before.
Network Partition for Optimization
To break a NP-hard task of network optimization down into subtasks the network can be decomposed into relatively independent subnets. In order to perform partition, network is firstly represented with the weighted complete graph, where each vertex corresponds to a network element and each edge has weight equals to the rank of correlation between pair of correspondent elements. Then the most irrelevant interactions between elements of network are removed. Based on remaining connections, the network is further split into relatively independent subnets. The result of splitting process can be a set of alternative splits, where every split consists of all possible non-overlapping subnets within network.[1] The optimization of subnets retrieved form the large network can be performed independently on computer cluster.
As a CAP trade-off
The CAP Theorem is based on three trade-offs: Consistency, Availability, and Partition tolerance. Partition tolerance, in this context, means the ability of a data processing system to continue processing data even if a network partition causes communication errors between subsystems.[2]
External links
References
- ^ a b Ignatov, D.Yu.; Filippov, A.N.; Ignatov, A.D.; Zhang, X. (2017). "Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks" (PDF). Proc. ISP RAS. 28: 141–152. arXiv:1701.06595. doi:10.15514/ISPRAS-2016-28(6)-10.
- ^ Stonebraker, Michael (April 5, 2010). "Errors in Database Systems, Eventual Consistency, and the CAP Theorem". Communications of the ACM.