A
network consists of nodes which require communicating with other on various
grounds. This communication is established via communication channels that
exist between them. The communication involves data transfers. In a network a
node may or may not have a link with every other node in the network.

**Applications that require communicating over a network include:**

1. Telecommunication
network applications such as POTS/ PSTN, local area networks (LANs),
internet, mobile phone networks and so on.

2. Distributed
system applications

3. Parallel
system applications

- As
we mentioned above, each and every node might not be linked with every other nodes
since for doing so a lot of wires and cables are required which will the whole
network more complicated.

- Therefore, we bring in the concept of the intermediate
nodes.

- The data transmitted by the source node is forwarded to the destination
by these intermediate nodes.

**N**

**ow the problem that arises is which path or route will be the best to use i.e., the path with the least cost.**

- This is determined
using the routing process.

- The best path thus obtained is called the optimal
route.

- Today, we have a number of algorithms available for determining the
optimal path.

**These algorithms have been classified in to two major types:**

- Non
– adaptive or static algorithms
- Adaptive
or dynamic algorithms

## Concept of Optimality Principle

- This is the principle
followed while determining the optimal router between the two routes.

The
general statement of the principle of optimality is stated below:

**“An optimal policy has the property that whatever the initial state and initial decision are, the remaining decision must constitute an optimal policy with regard to the state resulting from the first decision.”**

- This
means if P is an optimal state that results in another state say Q, and then
the portion of the original from that state to this state i.e., from P to Q
must be optimum.

- This only means the optimality of the part of the optimal
policy is preserved. - The initial state and the final state are the most
important parts of the optimum.

- Consider an example, suppose we have problem
with 3 inputs and 26 states. - Here, the state is associated with the optimum and
the total cost is associated with the optimum policy.

- If brute force method is
used for 3 inputs and 100 stages we have the total number of computations as 3

^{100}.
- That means for solving this problem, a super computer is required.

- Therefore, the approach used for solving this problem is a parallel processing approach.

- Here, for the each state the least step is computed and stored during the
programming.

- This reduces the number of possibilities and hence reducing the
amount of computation.

- The
problems become complex if the initial and the final states are undefined. - It
is necessary for the problem to follow the principle of optimality in order to
use the dynamic programming.

- This implies that whatever the state may be, the
decisions that follow must be optimal in regard with the state obtained from
the previous decision.

- This property is found in combinatorial problems but
since they use a lot of time and memory, this method is inefficient for them.

- These
problems can be solved efficiently if some sort of best first search and
pruning technique is applied.

**- In regard to the routing in networks, it follows from the optimality principle if a router B lies between router A and C which lie on an optimal path, then the path between the router B and C is also an optimal path and lies on the same path.**

- Sink tree is formed as a result of all optimal routes which is the
ultimate goal of all the routing algorithms.

## No comments:

Post a Comment