Routing Protocols

In Routing Protocol, Routing is the process of selecting paths in a network along which to send data on physical traffic. In different network operating system the network layer perform the function of protocol routing. In TCP/IP the IP protocol is the ability to form connections between different physical networks with the help of a Routing Protocol.

A system that performs this function is called an IP router. This type of device attaches to two or more physical networks and forwards packets between the networks. When sending data to a remote destination, a host passes packet to a local router.

The router forwards the packet toward the final destination. They travel from one router to another until they reach a router connected to the destination’s LAN segment. Each router along the end-to-end path selects the next hop device used to reach the destination. The next hop represents the next device along the path to reach the destination.

It is located on a physical network connected to this intermediate system. Because this physical network differs from the one on which the system originally received the datagram, the intermediate host has forwarded (that is, routed) the packets from one physical network to another.

There are two types of routing algorithm :

• Static
• Dynamic

Static Routing : Static routing uses pre-programmed definitions representing paths through the network. Static routing is manually performed by the network administrator. The administrator is responsible for discovering and propagating routes through the network.

These definitions are manually programmed in every routing device in the environment. After a device has been configured, it simply forwards packets out the predetermined ports. There is no communication between routers regarding the current topology of the network. In small networks with minimal redundancy, this process is relatively simple to administer.

Dynamic Routing : Dynamic routing algorithms allow routers to automatically discover and maintain awareness of the paths through the network. This automatic discovery can use a number of currently available dynamic routing protocols.

Following are the routing algorithms for networks :

• Distance Vector Algorithm
• Link State Algorithm
• Path Vector Algorithm
• Hybrid Algorithm

Distance Vector Routing: Distance vector algorithms use the Bellman- Ford algorithm. Distance vector algorithms are examples of dynamic routing protocols. Algorithms allow each device in the network to automatically build and maintain a local routing table or matrix.

Routing table contains list of destinations, the total cost to each, and the next hop to send data to get there. This approach assigns a number, the cost, to each of the links between each node in the network. Nodes will send information from point A to point B via the path that results in the lowest total cost i.e. the sum of the costs of the links between the nodes used.

The algorithm operates in a very simple manner. When a node first starts, it only knows of its immediate neighbours, and the direct cost involved in reaching them. The routing table from the each node, on a regular basis, sends its own information to each neighbouring node with current idea of the total cost to get to all the destinations it knows of.

The neighboring node(s) examine this information, and compare it to what they already ‘know’; anything which represents an improvement on what they already have, they insert in their own routing table(s). Over time, all the nodes in the network will discover the best next hop for all destinations, and the best total cost. The main advantage of distance vector algorithms is that they are typically easy to implement and debug. They are very useful in small networks with limited redundancy. When one of the nodes involved goes down, those nodes which used it as their next hop for certain destinations discard those entries, and create new routing-table information.

They then pass this information to all adjacent nodes, which then repeat the process. Eventually all the nodes in the network receive the updated information, and will then discover new paths to all the destinations which they can still “reach”.

Link State Routing : A link state is the description of an interface on a router and its relationship to neighboring routers. When applying link-state algorithms, each node uses as its fundamental data a map of the network in the form of a graph.

To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra’s algorithm.

The result is a tree rooted at the current node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.

Shortest-Path First (SPF) Algorithm : The SPF algorithm is used to process the information in the topology database. It provides a tree representation of the network. The device running the SPF algorithm is the root of the tree.

The output of the algorithm is the list of shortest-paths to each destination network. Because each router is processing the same set of LSAs, each router creates an identical link state database. However, because each device occupies a different place in the network topology, the application of the SPF algorithm produces a different tree for each router.

Path Vector Routing : Distance vector and link state routing are both intra-domain routing protocols. They are used inside an autonomous system, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in Inter-domain routing. Distance vector routing is subject to instability if there are more than few hops in the domain. Link state routing needs huge amount of resources to calculate routing tables. It also creates heavy traffic because of flooding. Path vector routing is used for inter-domain routing. It is similar to Distance vector routing.

In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and sends information to its neighboring speaker nodes in neighboring autonomous systems. The idea is the same as Distance vector routing except that only speaker nodes in each autonomous system can communicate with each other.

The speaker node sends information of the path, not the metric of the nodes, in its autonomous system or other autonomous systems. The path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are sends information as destination addresses and path descriptions to reach those destinations.

A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations. The path, expressed in terms of the domains traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. The path represented by the smallest number of domains becomes the preferred path to reach the destination. The main advantage of a path vector protocol is its flexibility.

Hybrid Routing : This algorithm attempt to combine the positive attributes of both distance vector and link state protocols. Like distance vector, hybrid algorithm use metrics to assign a preference to a route. However, the metrics are more accurate than conventional distance vector algorithm.

Like link state algorithms, routing updates in hybrid algorithm are event driven rather than periodic. Networks using hybrid algorithm tend to converge more quickly than networks using distance vector protocols. Finally, algorithm potentially reduces the costs of link state updates and distance vector advertisements.