What is the idea behind link state routing?

There are two main classes of the routing protocols out of which one is the link state routing protocol on which we shall focus in this article. The other class of the routing protocols is the distance vector routing protocols.

In computer communications, the link state routing protocol is applied in the packet switching networks. 

We can give two main examples of the link state routing protocol namely:

1. IS – IS i.e., intermediate system to intermediate system and
2. OSPF i.e., the open shortest path first

Almost every switching node is capable of performing the link – state routing in the network. Switching nodes can be defined as the nodes that can forward the packets. We call these nodes as routers in the internet.

Idea behind the Link State Routing

 

- A map is constructed by every node concerning its connectivity with the network. 

- This map is actually in a graph’s form. 

- This graph shows all the connections that exist between the various nodes in the graph. 

- The next “best logical path” is then calculated independently by each node to every destination in the network based up on its possibility. 

- The routing table of the node will then be formed by this collection of the best paths.

- This is in total contrast with the second class of the routing protocols.

- In the distance vector routing protocols, the routing table of a node is also shared by its neighbors whereas in the link state routing protocol, only the connectivity related information is passed between the nodes. 

- The simplest configuration of the link state routing protocols is the one that has no area. 

- This implies that each node possesses a map of the whole network. 

- The first main stage involves providing map of the network to each node. 

For doing the following, subsidiary steps are followed:

1. Determination of the neighboring nodes: Each node determines to which all neighboring nodes it is connected to. Also, it needs to know whether over the links through which it is connected are fully working or not. A reach-ability protocol is used for accomplishing this task. This protocol is run regularly but in separation from the neighboring nodes.
2. Distribution of the map information: The link state advertisement is the short message that is made by the node in case of some modification in the connectivity periodically.

- The above obtained set of such link state advertisements is used for the creation of the map of the entire network. 

- The second stage involves production of the routing tables through the map inspection. 

This again involves a number of steps:

1. Calculation of the shortest paths: Shortest path from one node to other nodes is determined by running a shortest path routing algorithm over the entire map. The commonly used algorithm is the Dijkstra’s algorithm.
2. Filling the routing table: The table is filled with best shortest paths obtained in the above step for every two nodes.  
3. Optimizations: We gave a glance of the simple form of this algorithm but in practical applications this form is used along with a number of optimizations. Whenever a change is detected in the network connectivity, the shortest path tree has to be immediately recomputed and then the routing table must be recreated. A method was discovered by the BBN technologies for recomputing only the affected part of the tree.

- Routing loops can be formed if working of the nodes using the exactly same map is not proper. 

- For adhoc networks such as the mobile networks, the optimized form of the protocol i.e., the optimized link state routing protocol is used. 

What is meant by an optimal route?

- For selecting a path or route, a routing metric has to be applied to a number of routes so as to select the best out of them. 

- This best route is called the optimal route with respect to the routing metric used. 

- This routing metric is computed with the help of the routing algorithms in computer networking.

- It consists of information such as network delay, hop count, network delay, load, MTU, path cost, communication cost, reliability and so on.

- Only the best or the optimal routes are stored in the routing tables that reside in the memory of the routers. 

- The other information is stored in either the topological or the link state databases. 

- There are many types of routing protocol and each of them has a routing metric specific to it. 

- Some external heuristic is required to be used by the multi-protocol routers for selecting between the routes determined using various routing protocols. 

- For example, the administrative distance is the value that is attributed to all the routes in Cisco routers. 

- Here, smaller distances mean that the protocol is a reliable one. 

- Host specific routes to a certain device can be set up by the local network admin. 

- This will offer more control over the usage of the network along with better overall security and permission for testing. 

- This advantage comes handy especially when it is needed to debug the routing tables and the connections. 

In this article we discuss about the optimal routes. 

- With the growing popularity of the IP networks as the mission critical tools for business, the need for methods and techniques using which the network’s routing posture can be monitored is increasing.

- Many routing issues or even incorrect routing can lead to undesirable effects on the network such as downtime, flapping or performance degradation. 

- Route analytic are the techniques and tools that are used for monitoring the routing in a network. 

The performance of the network is measured using the following 2 factors:

1. Throughput or the Quantity of service: This includes the amount of data that is transmitted and time it takes to transfer.
2. Average packet delay or Quality of service: This includes the time taken by a packet to arrive at its destination and the response of the system to the commands entered by the user.

- There is always a constant battle between the fairness and optimality or we can say between quantity of service and quality of service. 

- For optimizing the throughput, the paths existing between the nodes have to be saturated and the response time from source point to destination point must be noticed. 

For finding the optimal routes, we have two types of algorithms namely:

1. Adaptive Algorithms: These algorithms are meant for the networks in which the routes change in a dynamic manner. Here the information regarding the route to be followed is obtained at the run time itself from adjacent as well as the all other routers. The routes change whenever there is a change in the load, change in the topology and every delta T seconds.
2. Non – adaptive algorithms: These algorithms the same routes cannot be followed every time. Therefore the measurements that were made for the previous condition cannot be used for the current condition. The routes thus obtained are called static routes and are computed at the boot time.

Finding optimal routes requires following the principle of optimality according to which the optimal path between an intermediate router and the destination router lies on the same route from the source to the destination route. 

What is optimality principle?

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. 

Now 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:

1. Non – adaptive or static algorithms
2. 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¹⁰⁰. 

- 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.

What are network layer design issues?

- The network layer i.e., the third layer of the OSI model is responsible for facilitating the exchange of the individual information or data pieces between hosts over the network. 

- This exchange only takes place between the end devices that are identified. 

- For accomplishing this task, 4 processes are used by the network layer and these are:

Ø  Addressing

Ø  Encapsulation

Ø  Routing

Ø  Decapsulation

In this article we focus up on the design issues of the network layer. 

- For accomplishing this task, the network layer also need s to have knowledge about the communication subnet’s topology and select the appropriate routes through it. 

- Another thing that the network layer needs to take care of is to select only those routers that do not overload the other routers and the communication lines while leaving the other lines and router in an idle state.

Below mentioned are some of the major issues with the network layer design:

1. Services provided to the layer 4 i.e., the transport layer.
2. Implementation of the services that are connection oriented.
3. Store – and  - forward packet switching
4. Implementation of the services that are not connection oriented.
5. Comparison of the data-gram sub-nets and the virtual circuits.

- The sender host sends the packet to the router that is nearest to it either over a point-to-point carrier link or LAN. 

- The packet is stored until its complete arrival for the verification of the check sum. 

- Once verified, the packet is then transmitted to the next intermediate router. 

- This process continues till the packet has reached its destination. 

- This mechanism is termed as the store and forward packet switching.

The services that are provided to the transport layer are designed based up on the following goals:

1. They should be independent of the router technology.
2. Shielding from the type, number and topology of the routers must be provided to the transport layer.
3. The network addresses that are provided to the transport layer must exhibit a uniform numbering plan irrespective of whether it’s a LAN or a WAN.

Now based up on the type of services that are offered, there is a possibility for two different organizations.

Offered service is Connection-less: 

- The packets are individually introduced in to the sub-net and the routing of the packets is done independently of each other. 

- It does not require any advance set up. 

- The sub-net is referred to as the data gram sub-net and the packets are called data-grams.

Offered service is connection-oriented: 

- In this case the router between the source and the destination must be established prior to the beginning of the transmission of the packets. 

- Here, the connection is termed as the virtual circuit and subnet as the “virtual circuit subnet” or simply VC subnet.

- Choosing a new router every time is a thing to be avoided and this is the basic idea behind the use of the virtual circuits. 

- Whenever we establish a connection, a route has to be selected from source to destination. 

- This is counted as a part of the connection setup only. 

- This route is saved in the routers tables that are managed by the routers and is then used by the flowing traffic. 

- On the release of connection, the VC is automatically terminated. 

- In case of the connection oriented service, an identifier is contained in each packet which tells the virtual circuit to which it belongs.

- In data-gram sub-net circuit setup is not required whereas it is required in the VC circuit. 

- The state info is not held by the routers in the data gram subnet whereas router table space is required for each VC for each connection.