Topology

A PhysicalTopology is a case class which describes a directed graph, where nodes represent routers, and edges represent unidirectional channels.

trait PhysicalTopology {
  // Number of nodes in this physical topology
  val nNodes: Int

  /** Method that describes the particular topology represented by the concrete
    * class. Returns true if the two nodes SRC and DST can be connected via a
    * directed channel in this topology and false if they cannot.
    *
    *  @param src source point
    *  @param dst destination point
    */
  def topo(src: Int, dst: Int): Boolean

  /** Plotter from TopologyPlotters.scala.
    * Helps construct diagram of a concrete topology. */
  val plotter: PhysicalTopologyPlotter
}

To see how to extend his trait, consider the UnidirectionalTorus1D topology.

/** An n-node network shaped like a torus, with directed channels */
case class UnidirectionalTorus1D(n: Int) extends Torus1DLikeTopology {
  val nNodes = n
  def topo(src: Int, dest: Int) = (dest - src + nNodes) % nNodes == 1
}

The current list of included base topologies is described below. User can always define their own topology.

Topology

Parameters

Diagram

UnidirectionalLine

nNodes: Number of nodes

topo_uniline

BidirectionalLine

nNodes: Number of nodes

topo_biline

UnidirectionalTorus1D

nNodes: Number of nodes

topo_unitorus1d

BidirectionalTorus1D

nNodes: Number of nodes

topo_bitorus1d

Butterfly

kAry: Degree of routers
nFly: Number of stages

topo_butterfly

BidirectionalTree

height: Height of tree
dAry : Degree of routers

topo_tree

Mesh2D

nX: Extent in X-dimension
nY: Extent in Y-dimension

topo_mesh

UnidirectionalTorus2D

nX: Extent in X-dimension
nY: Extent in Y-dimension

topo_unitorus2d

BidirectionalTorus2D

nX: Extent in X-dimension
nY: Extent in Y-dimension

topo_bitorus2d

Additionally, two hierarchical compositional topology generators are provided: TerminalRouter and HierarchicalTopology.

Terminal Router Topologies

The TerminalRouter topology class “wraps” a base topology with a layer of terminal router nodes, which the ingresses and egresses tie to. This reduces the radix of critical routers in the network. This topology class can wrap an arbitrary base topology (including custom topologies).

For example, consider a network where the base topology is a bidirectional line. Wrapping the base BidirectionalLine topology class in the TerminalRouter class “lifts” the terminal points into separate nodes (purple), while preserving the existing topology and routing behavior on the underlying network routers.

Topology

Diagram

BidirectionalLine(4)

topo_noterm

TerminalRouter(BidirectionalLine(4))

topo_term

Note

The TerminalRouter topology must be used with the TerminalRouting routing relation wrapper

Hierarchical Topologies

The HierarchicalTopology class joins a collection of child sub-topologies using a base topology. A HierarchicalSubTopology describes a child sub-topology, as well as the connection to the base topology.

In the first example below, note how the first hierarchical child topology describes a channel between the 0th node on the base topology, and what would be node 2 on the child topology. Here the green nodes are from the base topology, while the blue nodes are from the child topologies.

Note

The TerminalRouter can be combined with HierarchicalTopology, as shown in the second example

Topology

Diagram

HierarchicalTopology(
  base=UnidirectionalTorus1D(4),
  children=Seq(
    HierarchicalSubTopology(0,2,BidirectionalLine(5)),
    HierarchicalSubTopology(2,1,BidirectionalLine(3))
  )
)

topo_hier

TerminalRouter(HierarchicalTopology(
  base=UnidirectionalTorus1D(4),
  children=Seq(
    HierarchicalSubTopology(0,2,BidirectionalLine(5)),
    HierarchicalSubTopology(2,1,BidirectionalLine(3))
  )
))

topo_hierterm

Note

The HierarchicalTopology topology must be used with the HierarchicalRouting routing relation wrapper