Sunday 27 February 2011

Link State Routing Protocol Operation


Link state routing protocols use Dijkstra’s algorithm, commonly known as Shortest Path First (SPF) algorithm. SPF accumulates each path’s cost along the way form source to destination. Each router chooses the best route that has the least metric.
Upon receiving link state information from other routers, each router builds its own tree topology of the entire network.



  
1-     Routers identify themselves and gather information about other directly connected routers; this is done by exchanging Hello packets from which they can build the Neighbour Table.
2-     After adjacency is established, each router builds its own Link-state Table (LST). LST contains all the information about directly connected links, such as type, state, bandwidth and neighbour ID.
3-     Link state protocols then distribute its LST once a change occurs in the topology, consequently, routers process these updates simultaneously achieving a speedy convergence time.
4-     Routers build up their Link State Database (LSDB) for the entire network within the routing domain, and then each router constructs a logical tree putting itself in the root position.
5-     By using Dijkstra’s SPF algorithm against the LTS, routers can derive the shortest path with the lowest cost and maintain their routing table.

Link State Routing Protocol


In contrast to Distance Vector protocols which use only distance and metric to determine the best path, Link state protocols do not distribute any routes, instead, they exchange the network topology information that describe the network.

Wednesday 23 February 2011

Advantages and Disadvantages of Distance Vector Routing Protocol


Distance Vector is a relatively simple approach and easy to use, implement and maintain and does not require High-level knowledge to deploy. Moreover, it does not demand high bandwidth level to send their periodic updates as the size of the packets are relatively small. 
Furthermore, distance vector protocols do not require a large amount of CPU resources or memory to store the routing data.
The main drawbacks of Distance Vector are limited scalability due to slow convergence time, bandwidth consumption and routing loops.
“Convergence time is the time needed for all routers within a single routing domain to receive, process and build their routing table” (Osterloh, 2002). Because RIP routers must fully process the updates they receive and then wait for 30-second interval before sending route information to their neighbours, convergence time is slow; therefore, it is not suitable for large networks that require very small propagation delay. Another problem is bandwidth consumption, which is caused by the unsolicited periodic update, which takes place every 30 seconds if the network has not changed.
One final problem is the routing loops, which has a severe impact on the overall network performance. A routing loop is defined as a condition in which a packet is continuously retransmitted among several routers without reaching its destination (Graziani & Johnson, 2009). A routing loop occurs when two or more routers have incorrect routing information to a destination network. Routing loops over-utilise the links between routers because of the endless looping traffic, as well as wasting the processor resources for forwarding useless traffic between the network routers. Consequently, routing loops lead to another problem called “ Counting–to-Infinity” which is a condition occur when inaccurate routing updates increase the hop number to “infinity” for a network that no longer exist (Graziani & Johnson, 2009).
However, the routing loops problem has been solved by several approaches. First; by setting a maximum metric value to stop counting to infinity, for instance, RIP has a maximum of 16 hops, so the network with a metric of 16 is considered as unreachable. Second; by using Hold-Down timers; for example, if some routers interfaces reset up and down in a rapid succession, Hold-Down timer prevents the router from quickly reacting to the unstable topology changes. Third, by adding Time to Live (TTL) field in the IP header that can limits the number of hops for a packet across the network before it is discarded. Furthermore, Split Horizon method and route poisoning could also address the routing loops. Split Horizon prevents the advertisement of a network through the interface from which the update came from. In turn, poison reverse offers another mechanism to avoid routing loop. Instead of waiting the hop count to reach infinity metric, whenever a network becomes unavailable, the router directly attached to it send triggered update informing to other routers that the network is unavailable not by omitting it, but by setting the metric value of 16 (in case of RIP). Each router receiving this update will send poison updates to all adjacent routers to indicate that the network is no longer reachable.  Finally, split horizon with poison reverse method. It is a combination of the poison reverse and split horizon mechanisms. The rule states that a router cannot advertise a network to an interface from which the network was learned. In other words, if router A advertise a network  X to router B, when router B sends its periodic update to router A, it will mark network X as unreachable, to tell router B that network X cannot be reached through router A.

Distance Vector Routing Protocols Operation


Routers that use distance vector periodically broadcast their entire routing table to its neighbours even if the network topology has not changed. These periodic updates are sent at regular intervals (normally 30 seconds for RIP and 90 seconds for IGRP).
This is achieved by means of local timer maintained in each router in the network, when the timer expires; a routing information update is sent (Graziani & Johnson, 2009).
 
  Distance Vector Periodic Updates

Distance Vector protocol is mathematically based on Bellman-Ford algorithm. Because of the algorithm simplicity, it has been widely implemented in wide-range network areas such as IP routing and AppleTalk. (Zinin, 2002).  

Saturday 19 February 2011

Distance Vector Dynamic Protocols


Distance Vector is one way to classify a routing protocol based on the algorithm type used to build and sustain their routing tables (Graziani & Johnson, 2009). Largely, Distance Vector routing protocols have been used for many years by network administrators to overcome the problems that arose when using static routing configuration.
It selects the best path based on how far the destination is, regardless of link load, reliability or delay. Normally, Distance is calculated by the number of hops or by a combination of parameters that represent distance. Distance Vector routing protocol include Routing Information protocol (RIP), Interior Gateway Routing Protocol (IGRP) and Enhanced Interior Gateway Routing Protocol (EIGRP)

Introduction to Dynamic Routing Protocols


In large-scale networks, routing protocols play a vital role to keep the network up and running. Routers use dynamic protocols to first learn about the directly connected routers, then learn about routes that have been advertised from other routers and finally build its own list (Routing Table) to be able to determine the best path to destination networks.

A Routing Protocol is a set of procedures based on algorithm that the router uses to exchange routing information with other routers. It provides dynamic reaction mechanism for network topology changes as well as notifying other routers of a change. In addition, dynamic routing protocols will find an alternate path around topology changes to keep the network in operation.

The most common classes of dynamic routing protocols are Distance Vector routing protocols and Link State routing protocols. In Distance Vector protocols, routes are advertised as vectors of distance and direction (Graziani & Johnson, 2009). Distance normally measured by hop count, on the other hand, Direction means the next hop. Some of the well-known Distance Vector protocols are Routing Information Protocol (RIP), Interior Gateway Routing Protocol (IGRP) and Enhanced Interior Gateway Routing Protocol (EIGRP). Routers using Distance Vector protocols periodically send their routing table to neighbouring nodes and then use Bellman-Ford algorithm to process the updates for bath determination. By using this algorithm, routers are not aware of the entire topology of the network; instead, they will only know about the adjacent routers.

In contrast, Link State routing protocol build up a complete view of the network by accumulating information from all the network routers. All routers know the entire map for the network; therefore, they will be able to determine the best path to all destination networks. Routers using Link State protocol do not send periodic updates as is the case with Distance Vector, alternatively, updates are sent whenever there is a change in the topology after the network has been converged. The most common link state protocols are Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

These routing protocols have evolved over the years to meet the demands of changing network requirements. Hence, after the IPv6 innovation, many of these routing protocols developed an enhanced version that support IPv6 routing such as Routing Information protocol Next Generation (RIPng), OSPFv3 and IS-IS (for IPv6).

In the next post, I am going to talk about every and each o the mentioned protocols. 

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | Grants For Single Moms