# Routing Mechanisms for Interconnection Networks

**Routing mechanism** – determines the path a message takes from source to sink.

- Input: source and sink nodes
- Output: One or more paths from source to sink
- Types of routing mechanisms:
**Minimal**– Always selects the shortest path between source and sink. Can lead to congestion.**Non-minimal**– May route along a longer path to avoid congestion.**Deterministic**– Selects a unique path based on source and sink, ignoring info about the network. Results in uneven use of resources.**Adaptive**– Determines a path from source to sink based on information about the network.

**Dimension Ordered Routing**(minimal and deterministic) – assigns successive channels for traversal by a message based on a numbering scheme determined by the dimensions of the channel.**XY-routing**– uses a 2-D mesh.- To reach P
_{Dy,Dx}from P_{Sy,Sx}, traverse a minimal route from P_{Sy,Sx}to P_{Sy,Dx}then traverse a minimal route from P_{Sy,Dx}to P_{Dy,Dx}. - The length of this path is |S
_{x}– D_{x}| + |S_{y}– D_{y}|.

- To reach P
**E-cube routing**– uses a hypercube- Compute the exclusive-or of P
_{s}and P_{d}(P_{s}⊕ P_{d}). Traverse from P_{s}to P_{i}along the dimension corresponding to the lowest ‘1’ bit in P_{s}⊕ P_{d}. Repeat this process, replacing P_{s}with P_{i}, P_{i+1}, … until P_{d}is reached. - The minimum distance is the number of ones in P
_{s}⊕ P_{d}.

- Compute the exclusive-or of P