- Effective routing algorithms have been developed that are capable of routing the messages from one source node to a number of receiving nodes i.e., the multiple destination nodes.
- These algorithms are termed as the multi – destination routing algorithms and the process is therefore called as the multi – destination routing.
- This type of routing has been developed for the minimization of the cost of the network i.e., NC (network cost).
- Network cost can be defined as the sum of all the links’ weights that consist of the routing path.
- There are many heuristic algorithms available for determining the NC min path.
- This problem falls under the category of the NP – complete problems.
- Heuristics are available for the traveling salesman problem and MST (minimum spanning tree) variations.
- Global information is used by both of them.
- Another set of such heuristics is available that uses only shortest paths for reaching the destinations.
- The best worst case performance is exhibited by the MST algorithm.
- However, one study revealed that effectiveness of the simpler heuristics is higher.
- The network cost (NC) is often compared with the destination cost (DC).
- Destination cost is the sum of the cost of all the shortest paths that lead to the destination.
- A scheme of algorithms has been developed for trading off between these two costs i.e., the NC and DC.
- The sender of the transmitted data cannot be taken as a single node in a network where the cooperative communication is supported.
- This asks for the re-investigation of the traditional link concept.
- Any routing scheme thus depending up on this link concept needs to be reconsidered.
- Also, the potential performance gain resulting because of the cooperative communication needs to be exploited.
- Routing often gets complicated for some networks where the selection of the paths is no longer the job of a single entity.
- Rather, a number of entities are involved in the selection of the paths.
- Multiple entities can even select specific parts of a path.
- If these selected paths are chosen by the entities for their own objectives optimization then it can lead to inefficiency or serious complications in the network since they may or may not conflict with the other entities’ objectives.
- This would become clear from the following example, consider traffic moving in a system of roads.
- Now here each driver selects a path that would minimize only his/her traveling time.
- In this kind of routing, there are longer equilibrium routes (i.e., longer than the optimal.) for almost all other drivers.
- This is often termed as the Braess paradox.
- Another example is of the routing the AGVs (automated guided vehicles) by a model on some terminal.
- For prevention of the simultaneous usage of the infrastructure’s same part reservations are made. - This is called as the context – aware routing.
- The internet is divided in to a number of divisions which are nothing but Ass i.e., the autonomous system like ISPs.
- All these systems have control over the routes that lie in their own network at various different levels.
Following steps are involved in multi – destination routing:
1. The BGP protocol is used for selecting the AS – level paths.
2. A sequence of autonomous systems is produced by the BGP protocol via which the packet flow will take place.
3. The neighboring Ass offer multiple paths for each of the AS from which it can choose. Paths are selected based up on the relationships between the neighboring systems.
4. Each selected path refers to multiple corresponding router level paths.