In
computer networking
A computer network is a collection of communicating computers and other devices, such as printers and smart phones. In order to communicate, the computers and devices must be connected by wired media like copper cables, optical fibers, or b ...
, hypercube networks are a type of
network topology
Network topology is the arrangement of the elements (Data link, links, Node (networking), nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, ...
used to connect and route data between multiple
processing units or computers. Hypercube networks consist of
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
* Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines ...
s, 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 -ary -dimensional mesh topology family, where represents the number of dimensions and 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 :
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
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two values (0 and 1) for each digit
* Binary function, a function that takes two arguments
* Binary operation, a mathematical op ...
representation. This is commonly referred to as Binary labelling. A 3D hypercube internetwork would be a cube with 8 nodes and 12
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
s. 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
The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the mo ...
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:
E-Cube routing is a
static routing
Static routing describes a process by which routing is configured with fixed values that do not change at runtime unless manually edited. Static routes are used with and without dynamic Routing protocols and usually share the same routing table a ...
method that employs XY-routing
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
. This is commonly referred to as
Deterministic
Determinism is the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...
,
Dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...
Ordered
Routing
Routing is the process of selecting a path for traffic in a Network theory, network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched ...
model. E-Cube routing works by traversing the network in the k
th 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 -
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 2
m-1 for Hypercubes.
See also
*
Hypercube (communication pattern)
References
{{Network topologies
Network topology