10
$\begingroup$

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 are the diameter, average distance and bisection bandwidth of this topology? How do these compare to other kinds of topologies, in terms of cost (links) & benefit?

I have heard of a "star of stars" topology, which I think is similar, but not identical, to this. If anything, this seems to be more of a "ring of rings", or something along those lines. Naturally, tweaks could be made to the definition of this topology, and more advanced questions could be asked (for instance, we could assign different bandwidths to links introduced at earlier stages, or discuss scheduling or data placement for such a topology). More generally, I am also interested in any good references for exotic or little-studied network topologies (regardless of practicality).

Again, apologies if this demonstrates ignorance of relevant research results, and any insights are appreciated.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.