Network Routing

2Basic Routing Algorithms

• 2.1 Introduction to Routing Algorithms
• 2.2 Routing Strategies
  • 2.2.1 Non‐Adaptive Algorithms
  • 2.2.2 Adaptive Algorithms
  • 2.2.3 Flooding
• 2.3 Static Shortest Path Routing Algorithms
• 2.4 Dynamic Shortest Path Routing Algorithms
• 2.5 Stochastic Routing Algorithms
• References
• Abbreviations/Terminologies
• Questions
• Exercises

2.1 Introduction to Routing Algorithms

Communication patterns can be classified on the basis of a number of source and destination nodes participating in the communication process. The two major communication models are point‐to‐point communication and collective communication [1]. In point‐to‐point communication there is only one source and one destination for each message. In a network, as per the information handling pattern, there can be only one source–destination pair at a point in time or many such one‐to‐one message passing source–destination pairs can communicate simultaneously. A special case of point‐to‐point communication, referred to as ‘permutation routing’, can also exist where a node can be source of one message and destination for another message at any time instance. In collective communication there can be multiple sources as well as multiple destinations.

As there can be various combinations of single source or multiple sources with single destination or multiple destinations, it leads to one‐to‐all, all‐to‐one, and all‐to‐all communication modes in collective communication. The one‐to‐one combination is not considered, as this becomes point‐to‐point ...