Hypercube internetwork topology

Key takeaways

Hypercube internetwork topology belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Hypercube internetwork topology to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Hypercube internetwork topology from memory before moving on to harder problems.

Reference excerpt

In computer networking, hypercube networks are a type of network topology used to connect and route data between multiple processing units or computers. Hypercube networks consist of 2m nodes, which form the vertices of squares to create an internetwork connection. A hypercube is basically a multidimensional mesh network with two nodes in each dimension. Due to similarity, such topologies are usually grouped into a k-ary d-dimensional mesh topology family, where d represents the number of dimensions and k represents the number of nodes in each dimension.

Topology Hypercube interconnection network is formed by connecting N nodes that can be expressed as a power of 2. This means if the network has N nodes it can be expressed as :

N = 2 m {\displaystyle N=2^{m}}

where m is the number of bits that are required to label the nodes in the network. So, if there are 4 nodes in the network, 2 bits are needed to represent all the nodes in the network. The network is constructed by connecting the nodes that just differ by one bit in their binary representation. This is commonly referred to as Binary labelling. A 3D hypercube internetwork would be a cube with 8 nodes and 12 edges. A 4D hypercube network can be created by duplicating two 3D networks, and adding a most significant bit. The new added bit should be ‘0’ for one 3D hypercube and ‘1’ for the other 3D hypercube. The corners of the respective one-bit changed MSBs are connected to create the higher hypercube network. This method can be used to construct any m-bit represented hypercube with (m-1)-bit represented hypercube.

E-Cube routing Routing method for a hypercube network is referred to as E-Cube routing. The distance between two nodes in the network can be given by Hamming weight of (number of ones in) the XOR-operation between their respective binary labels. The distance between Node 1 (represented as ‘01’) and Node 2 (represented as ‘10’) in the network given by:

H a m m i n g _ w e i g h t ( 01 ⊕ 10 ) = H a m m i n g _ w e i g h t ( 11 ) = 2 {\displaystyle {\mathsf {Hamming\_weight}}(01\oplus 10)={\mathsf {Hamming\_weight}}(11)=2}

E-Cube routing is a static routing method that employs XY-routing algorithm. This is commonly referred to as deterministic, dimension-ordered routing model. E-Cube routing works by traversing the network in the kth dimension, where k is the least significant non-zero bit in the result of calculating distance. For example, let the sender's label be 00 and the receiver's label be 11. So, the distance between them is 11 and the least significant non-zero bit is the LSB bit. Figuring out which way to go for a 0 or 1 is determined by XY routing algorithm.

Metrics Different measures of performance are used to evaluate the efficiency of a hypercube network connection against various other network topologies.

Degree This defines the number of immediately adjacent nodes to a particular node. These nodes should be immediate neighbors. In case of a hypercube the degree is m.

Diameter This defines the maximum number of nodes that a message must pass through on its way from the source to the destination. This basically gives us the delay in transmitting a message across a network. In case of a hypercube the diameter is m.

Average distance The distance between two nodes defined by the number of hops in the shortest path between two particular nodes. It is given by the formula -

d a = ∑ d = 1 r ( d . N d ) N − 1 {\displaystyle d_{a}=\sum _{d=1}^{r}{(d.N_{d}) \over N-1}}

In case of hypercubes the average distance is given as m/2.

Bisection width This is the lowest number of wires that you should cut in order to divide the network into two equal halves. It is given as 2m-1 for hypercubes.

See also Hypercube (communication pattern)

References

Illustrations

Worked examples

Example 1 — a first encounter with Hypercube internetwork topology

Start with the simplest possible case. Write down what Hypercube internetwork topology claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Hypercube internetwork topology before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Hypercube internetwork topology ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Hypercube internetwork topology

In research: Hypercube internetwork topology appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Hypercube internetwork topology in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Hypercube internetwork topology is common in secondary-school and first-year university syllabi. It links to neighbouring topics Network topology, so understanding it makes those chapters shorter.
In everyday life: Look for Hypercube internetwork topology outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Hypercube internetwork topology in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Hypercube internetwork topology means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Hypercube internetwork topology out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Hypercube internetwork topology in simple terms?

In computer networking, hypercube networks are a type of network topology used to connect and route data between multiple processing units or computers. Hypercube networks consist of 2m nodes, which form the vertices of squares to create an internetwork connection.

Why does Hypercube internetwork topology matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Hypercube internetwork topology?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Hypercube internetwork topology.