patternMinor
Analysis of and references for Koch-snowflake-like (and other exotic) network topologies
Viewed 0 times
snowflakeexoticanalysistopologieslikekochforandotherreferences
Problem
In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common network topologies include the mesh, torus, ring, star, tree, etc. These topologies can be studied analytically to determine properties related to their expected performance; such characteristics include diameter (maximal distance between a pair of nodes, in terms of the number of links which must be crossed if such nodes communicate), the average distance between nodes (over all pairs of nodes in the network), and the bisection bandwidth (the worst-case bandwidth between two halves of the network). Naturally, other topologies and metrics exist.
Consider a network topology based on the Koch snowflake. The simplest incarnation of such a topology consists of three nodes and three links in a fully-connected setup. The diameter is 1, average distance is 1 (or 2/3, if you include communications inside a node), etc.
The next incarnation of the topology consists of 12 nodes and 15 links. There are three clusters of three nodes fully, each cluster being fully connected by three links. Additionally, there are the three original nodes, connecting the three clusters using six additional links.
In fact, the number of nodes and links in incarnation $k$ are described by the following recurrence relations:
$$N(1) = 3$$
$$L(1) = 3$$
$$N(k+1) = N(k) + 3L(k)$$
$$L(k+1) = 5L(k)$$
Hopefully, the shape of this topology is clear; incarnation $k$ looks like the $k^{th}$ incarnation of the Koch snowflake. (A key difference is that for what I have in mind, I am actually keeping the link between the 1/3 and 2/3 nodes on successive iterations, so that each "triangle" is fully connected and the above recurrence relations hold).
Now for the question:
Has this network topology been studied, and if so, what is it called? If it has been studied extensively, are there any references? If not, what a
Consider a network topology based on the Koch snowflake. The simplest incarnation of such a topology consists of three nodes and three links in a fully-connected setup. The diameter is 1, average distance is 1 (or 2/3, if you include communications inside a node), etc.
The next incarnation of the topology consists of 12 nodes and 15 links. There are three clusters of three nodes fully, each cluster being fully connected by three links. Additionally, there are the three original nodes, connecting the three clusters using six additional links.
In fact, the number of nodes and links in incarnation $k$ are described by the following recurrence relations:
$$N(1) = 3$$
$$L(1) = 3$$
$$N(k+1) = N(k) + 3L(k)$$
$$L(k+1) = 5L(k)$$
Hopefully, the shape of this topology is clear; incarnation $k$ looks like the $k^{th}$ incarnation of the Koch snowflake. (A key difference is that for what I have in mind, I am actually keeping the link between the 1/3 and 2/3 nodes on successive iterations, so that each "triangle" is fully connected and the above recurrence relations hold).
Now for the question:
Has this network topology been studied, and if so, what is it called? If it has been studied extensively, are there any references? If not, what a
Solution
Not really a straight answer, but I don't have the ability to comment yet. I think you are confusing the Koch snowflake with the Sierpinski gasket/triangle. A Koch topology would just be equivalent to a path. The Sierpinski triangle has the properties you describe.
A quick google shows a wealth of papers and webpages on Sierpinski networks, although there is little agreement on the exact topology.
A quick google shows a wealth of papers and webpages on Sierpinski networks, although there is little agreement on the exact topology.
Context
StackExchange Computer Science Q#149, answer score: 3
Revisions (0)
No revisions yet.