# Dimension-Order Topology Types

## Overview

The dimension-order topology is a topology where the arrangement of the routers
are described by their location in a dimensional space. The topology has a
hierarchical structure where dimension *n* is composed of structures from
dimension *n-1*. One or more endpoint nodes are connected to a router.

## k-ary n-cube

A *k*-ary *n*-cube topology consists of *k ^{n}* routers arranged in
an

*n*-dimensional cube with

*k*routers along each dimension. Each router is assigned an

*n*-digit radix-

*k*address {a

_{n−1}, ..., a

_{0}} and is connected to all routers with addresses that differ by ±1(mod

*k*) in exactly one address digit. Each dimension is constructed using

*k*

*k*-ary (

*n-1*)-cubes. The channels between the routers can be unidirectional or bidirectional. In practice, the channels are bidirectional.

### Ring Topology

**Figure Ring_4ary_1cube_example. A ring
topology with four routers, also known as a 4-ary 1-cube topology.**

The ring topology is a special instance of the *k*-ary *n*-cube, where *n* is
equal to one. Figure Ring_4ary_1cube_example shows a
ring topology with four routers, also known as a 4-ary 1-cube topology. The
dotted lines show the connectivity between routers 0 and k-1 for a dimension.

### Symmetric Torus Topology

**Figure
Symmetric_Torus_4ary_2cube_example.
A symmetric torus topology with four routers along each dimension, also known as
a 4-ary 2-cube topology.**

The symmetric torus topology is a special instance of the *k*-ary *n*-cube,
where n is equal to two. Figure
Symmetric_Torus_4ary_2cube_example shows a
symmetric torus topology with four routers along each dimension, also known as a
4-ary 2-cube topology. Router (3,0) has address 3 in a dimension and 0 in the
other dimension. The dotted lines show the connectivity between routers 0 and
k-1 for a dimension.

**Figure
4ary_2cube_construction_example. The
construction of a symmetric torus (4-ary 2-cube) topology using 4-ary 1-cubes.**

Figure 4ary_2cube_construction_example shows the construction of a symmetric torus (4-ary 2-cube) topology using 4-ary 1-cubes (ring topologies).

### multi-radix n-cube

A multi-radix *n*-cube is a generalized form of a *k*-ary *n*-cube topology
where the radix (number of router nodes) for each dimension is explicitly
stated. Each router is assigned an *n*-digit where the digit at index *i* has
the radix of dimension *i*. A 2,3-ary 2-cube describes a grid-like topology with
a radix of 2 in one dimension and radix of 3 in the other dimension.

**Figure 2,3-ary_2cube_example. A 2,3-ary
2-cube topology example.**

Figure 2,3-ary_2cube_example shows a 2,3-ary 2-cube
topology example. The dotted lines show the connectivity between router 0 and
router radix_{i }- 1 for each dimension.

## k-ary n-mesh

A *k*-ary *n*-mesh is a *k*-ary *n*-cube topology with the connection from
address a_{k−1} to address a_{0} omitted in each dimension.

### Line

**Figure Line_4ary_1mesh_example. A line
topology with four routers, also known as a 4-ary 1-mesh topology.**

The line topology is a special instance of the *k*-ary *n*-mesh, where *n* is
equal to one. Figure Line_4ary_1mesh_example shows a
line topology with four routers, also known as a 4-ary 1-mesh topology. Compared
to the ring topology in Figure
Ring_4ary_1cube_example, the connection from router
0 to router 3 is omitted.

### Symmetric Mesh

**Figure
Symmetric_Mesh_4ary_2mesh_example. A
symmetric mesh topology with four routers along each dimension, also known as a
4-ary 2-mesh topology.**

The symmetric torus mesh is a special instance of the *k*-ary *n*-mesh, where
*n* is equal to two. Figure
Symmetric_Mesh_4ary_2mesh_example shows a
symmetric mesh topology with four routers along each dimension, also known as a
4-ary 2-mesh topology. Router (1,2) has address 1 in a dimension and 2 in the
other dimension. Compared to the torus topology in Figure
Symmetric_Torus_4ary_2cube_example, the
connections between the pair of routers [(0,0), (0,3)], [(1,0), (1,3)], [(2,0),
(2,3)], [(3,0), (3,3)], [(0,0), (3,0)], [(0,1), (3,1)], [(0,2), (3,2)], and
[(0,3), (3,3)] are omitted.

### multi-radix n-mesh

Similar to the multi-radix *n*-cube, a multi-radix *n*-mesh is a generalized form of
a *k*-ary *n*-mesh topology where the radix (number of router nodes) for each
dimension is explicitly stated. Each router is assigned an *n*-digit where the
digit at index *i* has the radix of dimension *i*. A 2,3-ary 2-mesh describes a
grid-like topology with a radix of 2 in one dimension and radix of 3 in the
other dimension.

**Figure 2,3-ary_2mesh_example. A 2,3-ary
2-mesh topology example.**

Figure 2,3-ary_2mesh_example shows a 2,3-ary 2-mesh topology example. Compared to the multi-radix n-cube topology in Figure 2,3-ary_2cube_example, the connections from the pair of routers [(0,0), (0,2)], [(1,0), (1,2)], [(0,0), (1,0)], [(0,1), (1,1)] and [(0,2), (1,2)] are omitted.

## Cheat Sheet

- A
*k*-ary*n*-cube topology consists of*k*routers arranged in an n-dimensional cube with k router nodes along each dimension. Each router is assigned an^{n}*n*-digit radix-*k*address {a_{n−1}, ..., a_{0}} and is connected to all routers with addresses that differ by ±1 (mod k) in exactly one address digit. Each dimension is constructed using*k**k*-ary (*n*-1)-cubes where there are*k*routers in the first dimension. - A multi-radix n-cube is a generalized form of a
*k*-ary*n*-cube topology where the radix (number of routers) for each dimension is explicitly stated. Each router is assigned an*n*-digit where the digit at index*i*has the radix of dimension*i*. - A
*k*-ary*n*-mesh is a*k*-ary*n*-cube topology with the connection from address a_{k−1}to address a_{0}omitted in each dimension. - Similar to the multi-radix
*n*-cube, a multi-radix n-mesh is a generalized form of a*k*-ary*n*-mesh topology where the radix (number of routers) for each dimension is explicitly stated. Each router is assigned an*n*-digit where the digit at index*i*has the radix of dimension*i*. - Channel direction can be unidirectional or bidirectional.
- Ring: k-ary 1-cube
- Symmetric Torus: k-ary 2-cube
- Line: k-ary 1-mesh
- Symmetric Mesh: k-ary 2-mesh

## References

William James Dally and Brian Patrick Towles. 2004. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.