Routing in Message Passing Networks

• Routing is defined as the techniques used for a message to select a path over the network channels.
• The identification of a set of permissible paths that may be used by a message to reach its destination, and a function, $\nu$, that selects one path from the set of permissible paths.
• A routing technique is said to be adaptive if, for a given source and destination pair, the path taken by the message depends on network conditions, such as network congestion.
• Contrary to adaptive routing, a deterministic routing technique, determines the path using only the source and destination, regardless of the network conditions.
  • Although simple, deterministic routing techniques make inefficient use of the bandwidth available between the source and destination.
• Routing techniques can also be classified based on the method used to make the routing decision as
  • centralized (self), the routing decisions regarding the entire path are made before sending the message. Centralized routing requires complete knowledge of the status of the rest of the nodes in the network.
  • distributed routing, each node decides by itself which channel should be used to forward the incoming message. Distributed routing requires knowledge of only the status of the neighboring nodes.
• Examples of the deterministic routing algorithms include the e-cube or dimension order routing used in the mesh and torus multicomputer networks and the XOR routing in the hypercube.