This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
The Internets network layer also contains routing protocols that determine the routes that datagrams take between sources and destinations. The Internet has many routing protocols.The Internet is network of networks and within a network, the network administrator can run any routing protocol desired. Although the network layer contains both the IP protocol and numerous routing protocols, it is often simply referred to as the IP layer, reflecting that fact that IP is the glue that binds the Internet together.
In IP networks, the main task of a routing protocol is to carry packets forwarded from one node to another. In a network, routing can be defined as transmitting information from a source to a destination by hopping one-hop or multi hop. Routing protocols should provide at least two facilities: selecting routes for different pairs of source/destination nodes and, successfully transmitting data to a given destination.
Routing protocols are used to describe how routers communicate to each other, learn available routes, build routing tables, make routing decisions and share information among neighbors. Routers are used to connect multiple networks and to provide packet forwarding for different types of networks. The main objective of routing protocols is to determine the best path from a source to a destination. A routing algorithm uses different metrics based on a single or on several properties of the path in order to determine the best way to reach a given network. Conventional routing protocols used in interior gateway networks are classified as Link State Routing Protocols and Distance Vector Routing Protocols. There are also other classifications of routing protocols, i.e., dynamic or static, reactive or proactive, etc. The conventional routing protocols can be used as a basis for building up other protocols for other types of communication networks such as Wireless Ad-Hoc Networks, Wireless Mesh Networks, etc. This chapter introduces different types of routing protocols, routing methods, network roles and characteristics.
2.2 Desirable Properties
To provide efficient and reliable routing, several desirable properties are required from the routing protocols:
The protocol should not depend on any centralized node for routing, i.e., distributed operation. The main advantage of this approach is that in such a network a link may fail anytime.
The routes provided by the routing protocol should guarantee a loop free route. The advantage of loop free routes is that in these cases the available bandwidth can be used efficiently.
The protocol should converge very fast, i.e., the time taken for all the routers in the network to know about routing specific information should be small.
Demand Based Operation
The protocol should be reactive, i.e., the protocol should provide routing only when the node demands saving thus valuable network resources.
The protocol should ensure that data will be transmitted securely to a given destination.
The routing protocol should maintain multiple routes. If a link fails or congestion occurs then the routing can be done through the multiple routes available in the routing table saving thus valuable time for discovering a new route.
Quality of Service (QoS)
The protocol design should provide some class of QoS depending upon its intended network use. Not all routing protocols used in current networks meet the above requirements. Each protocol differs in some way.
2.3 Path Determination
Routing protocols use metrics to evaluate what path will be the best for a packet to travel. A metric is a standard of measurement, such as path bandwidth, that is used by routing algorithms to determine the optimal path to a destination. To aid the process of path determination, routing algorithms initialize and maintain routing tables, which contain route information. Route information varies depending on the routing algorithm used.
Routing algorithms fill routing tables with a variety of information. Destination/next hop associations tell a router that a particular destination can be reached optimally by sending the packet to a particular router representing the "next hop" on the way to the final destination. When a router receives an incoming packet, it checks the destination address and attempts to associate this address with a next hop. Figure 2-1 depicts a sample destination/next hop routing table.
Figure 2-1 Destination/Next Hop Associations Determine the Data's Optimal Path
Routing tables also can contain other information, such as data about the desirability of a path. Routers compare metrics to determine optimal routes, and these metrics differ depending on the design of the routing algorithm used. A variety of common metrics will be introduced.
Routers communicate with one another and maintain their routing tables through the transmission of a variety of messages. The routing update message is one such message that generally consists of all or a portion of a routing table. By analyzing routing updates from all other routers, a router can build a detailed picture of network topology. A link-state advertisement, another example of a message sent between routers, informs other routers of the state of the sender's links. Link information also can be used to build a complete picture of network topology to enable routers to determine optimal routes to network destinations.
2.4 Metrics and Routing
The path cost can be measured based on metric parameters of the path. To determine the best path among all the available routes, routing protocols will select the route with the smallest metric value (or cost). Every routing protocol has its own metric calculation.
2.4.2 Purpose of a metric
There are scenarios where routing protocols learn about more than one route to the same destination. To select the best among the available paths, routing protocols should be able to evaluate and distinguish among these paths. Hence, for this purpose, different metrics are used. A metric is a value utilized by the routing protocols to assign a cost to reach the destination or remote network. When there are multiple paths to the same destination, metrics are used to determine which path is the best. Calculation of metrics for each routing protocol is done in different ways. For example EIGRP uses a combination of bandwidth, load, reliability and delay. OSPF uses bandwidth while Routing Information Protocol (RIP) uses hop count.
2.4.3 Metric Parameters
Routing tables contain information used by switching software to select the best route. But how, specifically, are routing tables built? What is the specific nature of the information that they contain? How do routing algorithms determine that one route is preferable to others? Routing algorithms have used many different metrics to determine the best route. Sophisticated routing algorithms can base route selection on multiple metrics, combining them in a single (hybrid) metric. All the following metrics have been used:
â€¢ Path length
â€¢ Communication cost
Path length is the most common routing metric. Some routing protocols allow network administrators to assign arbitrary costs to each network link. In this case, path length is the sum of the costs associated with each link traversed. Other routing protocols define hop count, a metric that specifies the number of passes through internetworking products, such as routers, that a packet must take en route from a source to a destination.
Reliability, in the context of routing algorithms, refers to the dependability (usually described in terms of the bit-error rate) of each network link. Some network links might go down more often than others. After a network fails, certain network links might be repaired more easily or more quickly than other links. Any reliability factors can be taken into account in the assignment of the reliability ratings, which are arbitrary numeric values usually assigned to network links by network administrators.
Routing delay refers to the length of time required to move a packet from source to destination through the internetwork. Delay depends on many factors, including the bandwidth of intermediate network links, the port queues at each router along the way, network congestion on all intermediate network links, and the physical distance to be travelled. Because delay is a conglomeration of several important variables, it is a common and useful metric.
Bandwidth refers to the available traffic capacity of a link. All other things being equal, a 10-Mbps Ethernet link would be preferable to a 64-kbps leased line. Although bandwidth is a rating of the maximum attainable throughput on a link, routes through links with greater bandwidth do not necessarily provide better routes than routes through slower links. For example, if a faster link is busier, the actual time required to send a packet to the destination could be greater.
Load refers to the degree to which a network resource, such as a router, is busy. Load can be calculated in a variety of ways, including CPU utilization and packets processed per second. Monitoring these parameters on a continual basis can be resource-intensive itself.
Communication cost is another important metric, especially because some companies may not care about performance as much as they care about operating expenditures. Although line delay may be longer, they will send packets over their own lines rather than through the public lines that cost money for usage time.
2.5 Hop Count versus Bandwidth
Hop count is defined as the number of routers a packet needs to travel through that path before it arrives at the destination. Each router represents one hope count. Distance vector routing protocols such as RIP use the path with smallest number of hops from multiple paths that exists to reach a destination. 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 . If we use hop count as the metric, the routers will choose suboptimal routes.
For example, consider Figure 2.2. When the routing protocol uses hop count as a metric, the router R1 will select suboptimal route directly through R2 to arrive at PC2. However, in routing protocol such as OSPF, R1 will choose the shortest path depending on the bandwidth. R1 chooses the link through R3.
Figure 2.2: Hop Count versus Bandwidth
2.6 Administrative Distance
Administrative Distance (AD) describes the rate of trustiness of packet received at the receiver. It is expressed by integers (0 to 255), where 0 means very trusted and, 255 means no traffic flow on the path. AD is used for the purpose of determining which routing source to be used. The routers must determine which routes to be included in the routing table before using that route during forwarding packet.
At the time when the router learns a route about the same network from more than one routing source, the determination of the route used in the routing table is based on the AD of the source routes. The AD with the lowest value will have precedence as the route source. The most preferred AD is zero and only the directly connected network has zero AD, and it cannot be altered.
Routing protocols can be classified as:
Static and dynamic routing protocols
Classful and Classless routing protocols
Distance Vector and Link State routing protocols
2.8 Static versus Dynamic Routing
In static routing, the routing table is constructed manually and routes are fixed at router boot time. The network administrator updates the routing table whenever a new network is added or deleted within the AS. Static routing is used only for small networks. It has bad performance when the network topology changes. The main advantages of static routing are its simplicity and the fact that it provides more control for the system administrator to control the whole network. The main disadvantages of static routing are as follows: it is impossible to accommodate rapid network topology changes and it is hard to setup all the routes manually. In dynamic routing protocols, the routing tables are created automatically in such a way that adjacent routers exchange messages with each other and the best routes are computed using own rules and metrics. The selection of best routes is based on specific metrics such as link cost, bandwidth, number of hops and delay and these values are updated by using protocols which propagate route information.
The main advantage of this type of routing protocols is that it helps the network administrator to overcome the time consumed in configuring and maintaining routes. The drawback of dynamic routing is that it may create diverse problem such as route instabilities and routing loops.
2.9 Classful and Classless Routing
Routing protocols can also be divided into classful and classless routing based upon the subnet mask.
2.9.1 Classful Routing
In classful routing, subnet masks are the same throughout the network topology and such a protocol does not send information of the subnet mask in its routing updates. When a router receives a route, it will do the following :
Routers which are directly connected to the interface of the major network uses the same subnet mask.
Applies classful subnet mask to the route when the router is not directly connected to interface of the same major network.
Classful routing protocols are not used widely because:
It does not support Variable Length Subnet Masks VLSM (VLSM) for hierarchical addressing.
It is not able to include routing updates.
It cannot be used in sub-netted network.
It is not able to support discontiguous networks.
Classful routing protocols can still be employed in today's networks but may not be used in all scenarios since they do not include the subnet mask.
Figure 2.3 shows a network using classful routing protocol in which the subnet mask is same throughout the network. RIPv1 and IGRP are examples of routing protocols that belong to the classful routing family of protocols.
Figure 2.3: Classful Routing with Same Subnet Mask
2.9.2 Classless Routing
Figure 2.4: Classless Routing with Different Subnet Masks
In classless routing, the subnet mask can vary in network topology and in the routing updates and the subnet mask together with the network address are included. Most networks today are not allocated based on classes and the value of the first octet is not used to determine the subnet mask. Classless routing protocols support discontiguous networks.
Figure 2.4 shows a network using classless routing in which different subnet mask are used within the same topology. RIPv2, EIGRP, OSPF, IS-IS and BGP are examples that belong to the classless routing family of protocols.
2.10 Distance Vector Routing
As the name indicates, distance vector routing protocol advertise routes as a vector of distance and direction. Here, the distance is represented in terms of hop count metrics and direction is represented by the next hop router or exit interface. DVR is based upon the Bellman Ford algorithm. In DVR, the paths are calculated using the Bellman Ford algorithm where a graph is built in which nodes takes position of the vertices and the links between the nodes takes position of the edges of the graph.
In DVR, each node maintains a distance vector for each destination. The distance vector consists of destination ID, next hop and shortest distance. In this protocol, each node sends a distance vector to its neighbors periodically informing about the shortest paths. Hence, each node discovers routes from its neighboring nodes and then advertises the routes from its own side. For information about the routes each node depends upon its neighbor which in turn depends on their neighboring nodes and so on.
Distance vectors are periodically exchanged by the nodes and the time may vary from10 to 90 seconds. For every network path, when a node receives the advertisement from its neighbors indicating the lowest-cost, the receiving node adds this entry to its routing table and re-advertise it on its behalf to its neighbors.
2.10.1 Methods of Routing
Distance vector routing protocol is one kind of protocol that uses the Bellman Ford algorithm to identify the best path. Different Distance Vector (DV) routing protocols use different methods to calculate the best network path. However, the main feature of such algorithms is the same for all DV routing protocols. To identify the best path to any link in a network, the direction and distance are calculated using various route metrics.
EIGRP uses the diffusion update algorithm for selecting the cost for reaching a destination. Routing Information Protocol (RIP) uses hope count for selecting the best path and IGRP uses information about delay and availability of bandwidth as information to determine the best path .
The main idea behind the DV routing protocol is that the router keeps a list of known routes in a table. During booting, the router initializes the routing table and every entry identifies the destination in a table and assigns the distance to that network. This is measured in hops. In DV, routers do not have information of the entire path to the destination router. Instead, the router has knowledge of only the direction and the interface from where the packets could be forwarded .
2.10.2 Properties of Distance Vector Routing
The properties of DV routing protocol include 
DV routing protocol advertise its routing table to all neighbours that are directly connected to it at a regular periodic interval.
Each routing tables needs to be updated with new information whenever the routes fail or become unavailable.
DV routing protocols are simple and efficient in smaller networks and require little management.
DV routing is base on hop counts vector.
The algorithm of DV is iterative.
It uses a fixed subnet masks length.
2.10.3 Advantages and Disadvantages of DV Routing
DV routing protocol suffers from the problem of count to infinity and Bellman Ford algorithm has a problem of preventing routing loops . The advantages of DV routing protocols are:
Simple and efficient in smaller networks.
Easy to configure
Requires little management.
The main disadvantages of DV routing protocols:
Results in creating loops.
Have slow convergence.
Problems with scalability.
Lack of metrics variety.
Being impossible for hierarchical routing.
Bad performance for large networks.
Few techniques exist to minimize the limitations of DV routing protocols. They are :
Split horizon rule
It is a one of the methods to eliminate routing loops and increase the convergence speed. Triggered update It uses specific timers and increases the response of the protocol.
2.11 Link State Routing
Link State Routing (LSR) protocols are also known as Shortest Path First (SPF) protocol where each router determines the shortest path to each network. In LSR, each router maintains a database which is known as link state database. This database describes the topology of the AS. Exchange of routing information among the nodes is done through the Link State Advertisements (LSA).
Each LSA of a node contains information of its neighbors and any change (failure or addition of link) in the link of the neighbors of a node is communicated in the AS through LSAs by flooding. When LSAs are received, nodes note the change and the routes are recomputed accordingly and resend through LSAs to its neighbors. Therefore, all nodes have an identical database describing the topology of the networks.
These databases contain information regarding the cost of each link in the network from which a routing table is derived. This routing table describes the destinations a node can forward packets to indicating the cost and the set of paths. Hence, the paths described in the routing table are used to forward all the traffic to the destination.
Dijkstra's algorithm is used to calculate the cost and path for each link. The cost of each link can also be represented as the weight or length of that link and is set by the network operator. By suitably assigning link costs, it is possible to achieve load balancing. If this is accomplished, congested links and inefficient usage of the network resources can be avoided. Hence, for a network operator to change the routing the only way is to change the link cost.
Generally the weights are left to the default values and it is recommended to assign the weight of a link as the inverse of the link's capacity. Since there is no simple way to modify the link weights so as to optimize the routing in the network, finding the link weights is known to be NP-hard. LSR protocols offer greater flexibility but are complex compared to DV protocols. A better decision about routing is made by link state protocols and it also reduces overall broadcast traffic.
The most common types of LSR protocols are OSPF and IS-IS. OSPF uses the link weight to determine the shortest path between nodes. These protocols will be discussed briefly in chapter 4.
2.11.1 Methods of Routing
Every router will accomplish the following process .
Every router learns about directly connected networks to it and its own links.
Every router must meet its directly connected neighbor networks. This can be done through HELLO packet exchanges.
Every router needs to send link state packets containing the state of the links connected to it.
Every router stores the copy of link state packet received from its neighbors.
Every router has a common view of the network topology and independently determines the best path for that topology.
2.11.2 Properties of LSR
Each router maintains identical database.
Converges as fast as the database is updated.
Possibility of splitting large networks into sub areas.
Supports multiple paths to destination.
Each router maintains the full graph by updating itself from other routers.
Fast non loop convergence.
Support a precise metrics.
2.11.3 Advantages and Disadvantages of LSR
In LSR protocols , routers compute routes independently and are not dependent on the computation of intermediate routers. The main advantages of link state routing protocols are:
React very fast to changes in connectivity.
The packet size sent in the network is very small.
The main problems of link state routing are:
Large amounts of memory requirements.
Much more complex.
Inefficient under mobility due to link changes.
 Rick Graziani and Allan Jonson, "Routing protocols and concepts: CCNA exploration companion guide," Pearson Education. London, 2008.
. James F. Kurose and Keith W. Ross, "Computer Networking - A Top-down Approach Featuring the Internet", Third Edition, Addison-Wesley,2000
 Douglas E. Comer, "Internetworking with TCP/IP, Principles, Protocols and Architecture," 5th ed. Vol.1, Pearson Prentice Hall, 2006.
 Tony Larsson and Nicklas Hedman, "Routing Protocols in Wireless Ad-hoc Networks-A simulation Study (Master's thesis)," Dept. Com. & Eng., Luleå Univ., Stockholm, 1998.
 Talal Mohamed Jaffar, "Simulation-Based Routing Protocols Analysis (Thesis)," Ph.D., Dept. Elect. Eng., Georgia Institute of Technology, 2007.
 Jeff Doyle. (2001, Nov 16). "Dynamic Routing Protocols," http://www.informit.com/articles/
 Online source. (2004, Aug 27), "Advanced IP Addressing Management", CiscoSystems, http://www.informit.com/articles/