In IP networks, a routing protocol usually carries packets by transferring them between different nodes. When considering a network, routing is took place by hopping one-hop or multi hop and thus it is defined as transmitting information between source and destination. There are two facilities for Routing protocols: to select routes between different nodes of the source/destination and to effectively transmit data to a particular destination. Routing protocols are used to illustrate 1) the way of communication between routers, 2) to learn existing routes, 3) constructing routing tables, 4) making routing decisions and sharing information among neighbor routers. The routers are used mainly by connecting several networks and providing packet forwarding to different networks. The main idea for routing protocols is to establish the best path from the source to the destination. A routing algorithm employs several metrics which are used to resolve the best method of reaching to a given network and those are established either on a single or on several properties of the path. For conventional routing protocol, networks are classified as Link State Routing Protocols and Distance Vector Routing Protocols. The conventional routing protocol is usually used for other types of communication networks such as Wireless Ad-Hoc Networks, Wireless Mesh Networks, etc. This chapter will mainly present several types of routing protocols, network roles and characteristics and also some routing methods.
In order to provide efficient and reliable routing, we need to describe several desirable properties which are obtained from the routing protocols:
The protocol does not need to depend on any centralized node for the routing purpose, for instance; a distributed operation. There is a key advantage for using such approach and that is a failure of link can occur anytime.
The routing protocol routes should ensure a loop free route and the advantage of using such routes is to obtain the available bandwidth efficiently.
The protocol is suppose to converge very fast, i.e., the time needed for all the routers in the network should be small so that the routing specific information can be known easily.
Demand Based Operation
The protocol should be reactive, i.e., the protocol should offer routing at the time the node requires saving by means of valuable network resources.
The protocol ensures a secured transmission of the data to a given destination.
The routing protocol should be responsible of maintaining multiple routes in a network. In case of failure of links or any congestion, the routing is performed through the multiple routes which are obtained in the routing table. Thus it saves the important time needed to discover a new route.
Quality of Service (QoS)
In design consideration of protocol, it should offer some class of QoS based on its intended network use. The routing protocols used in the current network are not able to meet the requirements mentioned above. Each protocol has the differance in some way.
2.3 Metrics and Routing
The measurements of path cost usually depend on the metric parameters. To choose the best path, routing protocols will take the route which has the least metric value (or cost).
2.3.2 Purpose of a metric
There are scenarios where routing protocols learn about more than one route to the same destination. In order to select the best available paths, routing protocols are needed to be evaluated and then distinguished among these paths. Therefore, different metrics are used. A metric is defined as a value utilized by the routing protocols which is used to allocate a cost for reaching the destination. Metrics determine the best path in case of multiple paths present in the same destination. There are different ways we can calculate metrics for each routing protocol. For instance; EIGRP uses a combination of bandwidth, reliability and delay, load. And OSPF uses bandwidth while RIP (Routing Information Protocol) uses hop count.
2.3.3 Metric Parameters
Different metrics are used by different routing protocols and
two different protocols may be considered of choosing different paths to same destination . In IP routing protocols, the following metrics are seen to be used mostly :
Hop count: It counts the number of routers for which a packet traverse in order to reach the destination.
Bandwidth: The path with highest bandwidth is preferred in case of using it as a metric.
Load: It is described as the traffic utilization of a defined link. The link with the lowest load is considered as the best path if the load is used as a metric.
Delay: It is the time measurement for a packet to pass through a path. The least delay is considered for selecting the best path.
Reliability: It Calculates the link failure probability and it can be calculated from earlier failures or interface error count. Highest reliability is given importance for selecting the best path.
Cost: the network administrator or Internet Operating System (IOS) estimates the cost to specify an ideal route. Cost can be represented either as a metric or a combination of metrics.
2.4 Hop Count versus Bandwidth
A packet travels throughout several numbers of the routers and this number of the routers represent as Hop count. Each router corresponds to one hope count. Distance vector routing protocol uses the path that has the smallest number of hop. Bandwidth is used as metric in many kinds of routing protocols, e.g., OSPF. The path with highest bandwidth value is selected as best path for routing . When we choose hop count as the metrics, the suboptimal routes will always be preferred by the routers.
It can be seen from Figure 2.1, the routing protocol uses hop count as a metric and the router R1 will select suboptimal route directly through R2 so that it arrives at PC2. On the other hand, when there is a routing protocol such as OSPF, R1 will select the shortest distance according to the available bandwidth. Thus, R1 chooses the link through R3.
ROUTER R1 ROUTER R2
Figure 2.1: Hop Count versus Bandwidth
2.5 Administrative Distance
Administrative Distance (AD) illustrates the rate of trustiness of packet which is received by the receiver and expressed by the integers (0 to 255), where 0 denotes very trusted and 255 denotes that traffic flow on the path is zero. AD determines the routing source which is to be used in the network and the routers determine the routes that has to be included in the routing table.
When the router finds out a route from several routing source, the determination of the route depends on the AD of the source routes. The AD containing the lowest value
must have the preference for the route source and the most preferred AD is considered as zero .
The classification of routing protocols are defined as:
Static and dynamic routing protocols
Classful and Classless routing protocols
Distance Vector and Link State routing protocols
2.7 Static versus Dynamic Routing
In static routing, the routing table follows manual construction and fixed routes at router boot time. The network administrators inform the routing table when a new network needs to be added or canceled in the AS. Static routing is mainly used for small networks. By changing the network topology, static routing starts showing poor performance. It usually provides more control for the system administrator in order to control the whole network. Also it has simple functionality and these are the main advantages of using static routing. However, it has some drawbacks too: it is very tough to contain rapid network topology changes and also hard to have a manual setup procedure. On the other hand, the routing tables are formed automatically in dynamic routing protocols so that neighboring routers exchange messages with each other and among them, the best routes are calculated using own metrics and rules. The best route selection procedure is conducted based on bandwidth, link cost, hop number, delay and the protocols usually updates these values.
This routing protocol offers an advantage by helping the network administrator to overcome the time consumption needed for maintaining and configuring routes. However, it has a disadvantage by having diversity problems, for instance; routing loops and route instabilities.
2.8 Classful and Classless Routing
Based on the subnet mask, routing protocols are divided into classful and classless routing.
2.8.1 Classful Routing
In classful routing, subnet masks perform the same functionality all through the network topology and such kind of protocol does not send information of the subnet mask. If a router receives a route, it will perform the following function :
Routers use the same subnet mask which are directly connected to the interface of the major network .
When the router is not directly connected to interface of the same major network, it applies classful subnet mask to the route.
Classful routing protocols are not used widely because:
It can not support Variable Length Subnet Masks VLSM (VLSM)
It can not include routing updates.
It is not able to be used in sub-netted network.
It can not support discontinuous networks.
It is possible to employ classful routing protocols in today's networks but not in all scenarios due to not including the subnet mask.
Figure 2.2 shows a classful routing protocol used in the network where the subnets mask is same all through the network. RIPv1 and IGRP are examples of routing protocols.
Figure 2.2: Classful Routing with Same Subnet Mask
2.8.2 Classless Routing
ROUTER R1 ROUTER R3
Figure 2.3: Classless Routing with Different Subnet Masks
In classless routing, the subnet mask can be changed in network topology and in
the subnet mask and the routing updates are included. Most networks don't depend on classes for being allocated these days and also for determining the subnet mask, the value of the first octet is not used. Classless routing protocols support nonadjacent networks.
Figure 2.3 showing a network used as classless routing and different
subnet mask are used in the same topology. RIPv2, EIGRP, IS-IS, OSPF and BGP are examples those are the part of the classless routing family of protocols.
2.9 Distance Vector Routing
Distance vector routing protocol presents routes as a function of distance and direction vectors where the distance is represented as hop count metrics and direction is represented as exit interface. In DVR, the Bellman Ford algorithm is used for the path calculation where the nodes are taken position of the vertices and the links. In DVR, for each destination, a specific distance vector is maintained for all the nodes used in the network. The distance vector comprises of destination ID, shortest distance and next hop. Here each node passes a distance vector to its neighbor and informs about the shortest paths. Thus, they discover routes coming from the adjacent nodes and advertise those routes from their own side. Each node depends on its neighboring nodes for collecting the route information. The nodes are responsible for exchanging the distance vector and the time needed for this purpose can vary from10 to 90 seconds. When a node, in a network path, accepts the advertisement of the lowest cost from its neighbors, the receiving node then adds this entry to the routing table.
2.9.1 Methods of Routing
Distance vector routing protocol uses the Bellman Ford algorithm for identifying the best path. For calculating the best network path, different methods are used by the Distance Vector (DV) routing protocols.
But, for all DV routing protocols, the main characteristic of such algorithms is found to be same. For identifying the best path in a network, various route metrics are used to calculate the direction and the distance. For example, EIGRP uses the diffusion update algorithm for calculating the cost which needs to reach a destination. Routing Information Protocol (RIP) uses hope count for choosing the best path and IGRP determines the best path by taking information of delay and bandwidth availability . In DV routing protocol, the router maintains a list of known routes in a table and during the time of booting, the router initializes the routing table to identify the destination in a table and thus assigns the distance in that network. This measurement is taken place in hops. In DV, routers do not know the information of the entire path. In its place, the router knows the information about the direction and the interface from where the packets are forwarded .
2.9.2 Properties of Distance Vector Routing
The properties of DV routing protocol are given below 
DV routing protocol describes its routing table where all neighbors are directly connected with the table at a regular period.
New information should put in Each routing table instantly when the routes become unavailable.
DV routing protocols are easy and efficient in smaller networks and thus require little management.
DV routing is mainly based on hop counts vector.
The DV algorithm is iterative.
A fixed subnet masks length is used.
2.9.3 Advantages and Disadvantages of DV Routing
DV routing protocol experiences the counting problem to infinity. On the other hand, Bellman Ford algorithm can not prevent routing loops and this is the main disadvantage of this . The advantages of DV routing protocols are:
easy and efficient in smaller networks.
Requires of little management.
The main disadvantages of DV routing protocols:
Experiences in creating loops.
Lack of metrics variety.
Being impossible for hierarchical routing.
Worse performance in large networks.
Few techniques are used for overcoming the limitations of DV routing protocols. They are : Split horizon rule which is a one of the methods used to diminish the routing loops and to enhance the convergence speed. Triggered update which is run by the specific timers and thus is able to increases the response of the protocol.
2.10 Link State Routing
Link State Routing (LSR) protocols are also known as Shortest Path First (SPF) protocol where the function of each router is to determine the shortest path among the network. Each router, in LSR, is seen to be maintained a database called link state database and that database is mainly used to describe the topology of the AS.
The Link State Advertisements (LSA) is responsible for exchanging the routing information among the nodes. The information of the neighbors is found in each LSA of a node and any link change information of the neighbor's node is communicated through LSAs by flooding. Usually the nodes observe the change when the LSAs are received. Then the routes are calculated again and resent to their neighbors. As a result, all nodes can maintain an identical database where they describe the topology of the networks. These databases provide information of the link cost in the network and then a routing table is formed. This routing table explains about the forwarded packets and also indicates the set of paths and their link cost. Dijkstra's algorithm is used for calculating the path and cost for each link. The link cost is set by the network operator and it is represented as the weight or length of that particular link. The load balancing performance is attained after assigning the link cost. Thus link congestion of the network resources can be evaded. Therefore, a network operator can change the routing by varying the link cost. Normally the weights are left with the default values and it is suggested to inverse of the link's capacity and then assigns the weight of a link on it. Though LSR protocols have better flexibility, they are found to be complicated compared to the DV protocols. The link state protocols lessen overall broadcast traffic and are able to make a better routing decision.
Two of the most common types of LSR protocols are OSPF and IS-IS. OSPF determines the shortest distance between nodes and for this issue; it uses the weight of the link. These protocols will be discussed in details in chapter 4.
2.10.1 Methods of Routing
Each router is responsible for accomplishing the following process .
Each router learns about directly connected networks and its own links.
Each router must have a connection with its directly connected adjacent networks and this is usually performed through HELLO packet exchanges.
Each router must send link state packets which contains the state of the links.
Each router stores a link state packet copy which is received by its neighbors.
Each router independently establishes the best path for the topology.
2.10.2 Properties of LSR
Each router keeps the same database.
Convergence speed is as fast as the database updating time.
Large networks split into sub areas.
Include multiple paths to destination.
Each router supports the full graph by taking the update from other routers.
Faster non loop convergence.
Support a accurate metrics.
2.10.3 Advantages and Disadvantages of LSR
In LSR protocols , routers calculate routes independently and also they are independent on the calculation of intermediate routers. The important advantages of link state routing protocols are:
Offer very fast reaction while there is a change in connectivity.
The packet size is very small.
The main problems of link state routing are:
Huge memory requirements.
ineffective under mobility for link changes.