Optimality Principle in Network Topology

Introduction :

A general statement is made about optimal routes without regard to network topology or traffic. This statement is known as the optimality principle( Bellman,1975).

Statement of the optimality principle :

It states that if the router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route.  Call the route from I to J r1 and the rest of the route r2. it could be concatenated with r1 to improve the route from I to K, contradicting our statement that r1r2 is optimal only if a route better than r2 existed from J to K. 

Sink Tree for routers :

 We can see that the set of optimal routes from all sources to a given destination from a tree rooted at the destination as a directed consequence of the optimality principle. This tree is called a sink tree and is illustrated in fig(1).

Description of figure :

 In the given figure the distance metric is the number of hops. Therefore, the goal of all routing algorithms is to discover and use the sink trees for all routers.   

(a) A network

(b) A sink tree for router B

The sink tree is not unique also other trees with the same path lengths may exist. If we allow all of the possible paths to be chosen, the tree becomes a more general structure called a DAG (Directed Acyclic Graph). DAGs have no loops. We will use sink trees as a convenient shorthand for both cases. we will take technical assumption for both cases that the paths do not interfere with each other so, for example, a traffic jam on one path will not cause another path to divert.

Conclusion :

 The sink tree does not contain any loops, so each packet will be delivered within a finite and bounded number of hops. In practice, life is not quite easy. Links and routers can go on and come back up during operation, so different routers may have different ideas about the current topology. Also, we have found the issue of whether each router has to individually acquire the information on which to base its sink tree computation or whether this information is collected by some other means. Sink tree and the optimality principle provide a benchmark against which other routing algorithms can be measured.