Analysis of Improved Shortest Path First Algorithm (Ispfa) for Enhanced Interior Gateway Routing Protocol (Eigrp)
Enyenihi H. Johnson1, Uduak Idio Akpan1, Nornu S. Agbeb2
1Department of Elect/Elect Engineering, Akwa Ibom State University, Ikot Akpaden, Nigeria
2Department of Elect/Elect Engineering, Rivers State Polytechnic, Port Harcourt, Nigeria
To cite this article:
Enyenihi H. Johnson, Uduak Idio Akpan, Nornu S. Agbeb. Analysis of Improved Shortest Path First Algorithm (Ispfa) for Enhanced Interior Gateway Routing Protocol (Eigrp). American Journal of Engineering and Technology. Vol. 1, No. 3, 2016, pp. 25-30. doi: 10.11648/j.ajetm.20160103.11
Received: August 2, 2016; Accepted: August 13, 2016; Published: September 12, 2016
Abstract: The world is experiencing rapid and tremendous growth in computer communication network technology. This technology provides the technical infrastructure, where routing protocols are used to transmit packets across the Internet. Routing protocols specify how routers communicate with each other by spreading information. Enhanced Interior Gateway Routing Protocol (EIGRP) is one of the hybrid protocols, which is based on Interior Gateway Routing Protocol (IGRP). In our work titled "Improved Shortest Path First Algorithm for Enhanced Interior Gateway Routing Protocol (EIGRP)", we proposed an improved shortest path first algorithm (ISPFA) used in enhanced interior gateway routing protocol. This work addressed the end-to-end delay problem associated with the existing routing protocol. In this paper, we carried our comprehensive analysis of the proposed protocol and assessed its comparative performance with existing protocol. The analysis shows average improvement of 36% by the proposed protocol over the existing.
Keywords: Routing Protocol, Delay Metrics, VOIP, EIGRP, ISPFA
Usually, the order in which routers communicate with each other and exchange information is made possible by routing protocol. Routing protocol also enables routers to select routes between any two nodes on a computer network . Routing algorithms are responsible for selecting the best path for the communication a border way we can say that A routing protocol is the language a router speaks with other routers in order to share information about the reach ability and status of network . Sometimes, people have often mistaken routing to bridging. The main difference between routing and bridging is in the layer in which they operate.
In present-day and future routing environments, Enhanced Interior Gateway Routing Protocol (EIGRP) offers benefits and features over historic distance vector routing protocols, such as Routing Information Protocol Version 1 (RIPv1) and Interior Gateway Routing Protocol (IGRP). These benefits include rapid convergence, lower bandwidth utilization, and multiple routed protocol support.
Enhanced Interior Gateway Routing Protocol (EIGRP) is an interior gateway protocol suited for many different topologies and media. In a well-designed network, EIGRP scales well and provides extremely quick convergence times with minimal network traffic.
1.1. Capabilities and Attributes of EIGRP
EIGRP is a Cisco-proprietary protocol which combines the advantages of link-state and distance vector routing protocols . The root of EIGRP is a distance vector routing protocol which has high level of predictability. Compared to some preceding protocol GRP, EIGRP can be easily configured and is adaptable to a wide variety of network topologies. EIGRP is considered an advanced distance vector protocol because of the addition of several link-state features, like the dynamic neighbor discovery (DND). EIGRP is also regarded as an enhanced IGRP as the results of its rapid convergence tendency and loop-free topology guaranteed at all times.
1.1.1. Fast Convergence
To achieve rapid convergence, the EIGRP employs an updating algorithm known as Diffusing Update Algorithm (DUAL). Normally, a router running the EIGRP stores its neighbors’ routing tables in order to quickly adapt to changes which may likely accord in the network. In event that no appropriate route or backup route exists in the local routing table, EIGRP has to query its neighbors in order to discover an alternative route. These queries are propagated until an alternative route is found, or it is determined that no alternative route exists .
1.1.2. Variable-Length Subnet Masking (VLSM) Support
EIGRP advertises a subnet mask for each destination network. This attribute makes it a classless routing protocol. This is one feature that enables EIGRP to support discontinuous subnetworks and VLSM.
1.1.3. Partial Updates
In operation, instead of periodic updates, EIGRP sends partial triggered updates. These updates are sent only when there is a change in path or the metric for a route. This updates contain information about the changed link instead of the entire routing table. Transmission of these partial updates is bounded automatically in order for the routers requiring the information to be updated. This characteristic ensures consumption of significantly less bandwidth by EIGRP than the IGRP.
1.1.4. Neighbour Discovery/Recovery Mechanism
EIGRP's neighbour discovery mechanism enables routers to dynamically learn about other routers on their directly attached networks. Routers also must discover when their neighbours become unreachable or inoperative. This process is achieved with low overhead by periodically sending small hello packets. As long as a router receives hello packets from a neighbouring router, it assumes that the neighbour is functioning, and the two can exchange routing information .
Routers running EIGRP must become neighbours before exchanging routing information. To dynamically discover neighbours, EIGRP routers use the multicast address of 184.108.40.206. Each EIGRP router stores routing and topology information in three tables.
i. Neighbour table which stores information about EIGRP neighbours.
ii. Topology tables which stores routing information learnt from neighbouring routers.
iii. Routing table which stores the best routes.
Administrative distance of EIGRP is 90, which is less than both the administrative distance of RIP and the administrative distance of OSPF, so EIGRP routes will be preferred over these routes. EIGRP uses Reliable Transport Protocol (RTP) for sending messages and calculates its metric by using bandwidth, delay, reliability and load. By default, only bandwidth and delay are used when calculating metric, while reliability and load are set to zero. EIGPR uses the concept of autonomous systems. An autonomous system is a set of EIGRP enabled routers that should become EIGRP neighbours. Each router inside an autonomous system must have the same autonomous system number configured; otherwise routers will not become neighbours.
1.1.5. Feasible and Reported Distance
Feasible Distance (FD) refers to the metric of the best route to reach a network. The router will be listed in the routing table.
Reported distance (RD) refers to the metric advertised by a neighbouring router for a specific route. In other words, it is the metric of the route used by the neighbouring router to reach the network. For instance, EIGRP has been configured on two routers RT1 and RT2. Assuming that RT2 is directly connected to the subnet 10.0.1.0/24 and advertises that subnet (10.0.1.0/24) into EIGRP. Assuming also that RT2's metric to reach that subnet is 28160. When the subnet is advertised to RT1, RT2 informs RT1 that its metric to reach 10.0.1.0/24 is 10. From the RT1's perspective that metric is considered to be the reported distance for that route. RT1 receives the update and adds the metric to the neighbour to the reported distance. That metric is called feasible distance and is stored in RT1's routing table. The feasible and reported distance is displayed in RT1's EIGRP topology table .
1.1.6. Successor and Feasible Successor
A successor is the route with the best metric to reach a destination. That route is stored in the routing table. A feasible successor is a backup path to reach that same destination that can be used immediately if the successor route fails. These backup routes are stored in the topology table. For a route to be chosen as a feasible successor, one condition must be met. A neighbour’s advertised distance (AD) for the route must be less than the successor's feasible distance (FD).
1.2. EIGRP Topology Table
EIGRP topology table contains all learned routes to a destination. The table holds all routes received from a neighbour, successors and feasible successors for every route, and interfaces on which updates were received. The table also holds all locally connected subnets included in an EIGRP process. Best routes (the successors) from the topology table are stored in the routing table. Feasible successors are only stored in the topology table and can be used immediately if the primary route fails.
1.3. Technical Overview of EIGRP
EIGRP offers many advantages over other routing protocols, including the following:
• Support for VLSM— EIGRP is a classless routing protocol and carries the subnet mask of the route in its update.
• Rapid convergence— By using the concept of feasible successors, defined by DUAL, EIGRP is capable of preselecting the next best path to a destination. This allows for very fast convergence upon a link failure.
• Low CPU utilization— Under normal operation, only "hellos" and partial updates are sent across a link. Routing updates are not flooded and are processed only periodically.
• Incremental updates— EIGRP does not send a full routing update; it sends only information about the changed route.
• Scalable— Through the use of VLSM and a complex composite metric, EIGRP networks can be vast in size.
• Easy configuration— EIGRP supports hierarchical network design, but it does not require the strict configuration guidelines, such as the ones needed for OSPF.
• Automatic route summarization— EIGRP will perform automatic summarization on major bit boundaries.
• MD5 route authentication— As of Cisco IOS Software Release 11.3, EIGRP can be configured to perform MD5 password authentication on route updates.
1.4. Enhanced Interior Gateway Routing Protocol (EIGRP) Metrics
EIGRP uses metrics in the same way as IGRP. Each route in the route table has an associated metric. EIGRP uses a composite metric much like IGRP, except that it is modified by a multiplier of 256. It is worthy to note that bandwidth, delay, load, reliability, and MTU are the sub metrics. Like IGRP, EIGRP chooses a route based primarily on bandwidth and delay, or the composite metric with the lowest numerical value. When EIGRP calculates this metric for a route, it calls it the feasible distance to the route. EIGRP calculates a feasible distance to all routes in the network. The following list is a detailed description of the five EIGRP sub-metrics .
Bandwidth is expressed in units of kilobits per second (Kbps). It must be statistically configured to accurately represent the interfaces that EIGRP is running on. For example, the default bandwidth of a 56-kbps interface and a T1 interface is 1544 kbps. To accurately adjust the bandwidth, we use the bandwidth kbps interface subcommand.
Delay is expressed in microseconds. It, too, must be statistically configured to accurately represent the interface that EIGRP is running on. The delay on an interface can be adjusted with the delay time_in_micro-seconds interface subcommand.
Reliability is a dynamic number in the range of 1 to 255, where 255 is a 100 percent reliable link and 1 is an unreliable link.
Load is the number in the range of 1 to 255 that shows the output load of an interface. This value is dynamic and can be viewed using the show interfaces command. A value of 1 indicates a minimally loaded link, whereas 255 indicate a 100 percent loaded link.
1.4.5. The Maximum Transmission Unit
The maximum transmission unit (MTU) is the recorded smallest MTU value in the path, usually 1500. Metric of delay is usually used over bandwidth when influencing routing decisions in IGRP or EIGRP. Changing bandwidth can affect other routing protocols, such as OSPF. Changing delay affects only IGRP and EIGRP.
|100-Mbps ATM||100,000 kbps||100 microsecs|
|Gigabit Ethernet||100,000 kbps||100 microsecs|
|Fast Ethernet||100,000 kbps||100 microsecs|
|FDDI||100,000 kbps||100 microsecs|
|HSSI||45,045 kbps||20,000 microsecs|
|16-Mbps Token Ring||16,000 kbps||630 microsecs|
|10-Mbps Ethernet||10,000 kbps||1000 microsecs|
|T1||1544 kbps||20,000 microsecs|
|DS-0||64 kbps||20,000 microsecs|
|56-kbps media||56 kbps||20,000 microsecs|
EIGRP uses a composite metric (CM) that is derived from the five submetrics. When EIGRP computes the composite metric, it uses a formula that involves five constants or "k" values. The constant values have default value such as the following: By setting K2, K4, and K5 to 0, it essentially nullifies the submetrics of load, reliability, and MTU.
The router calculation of the composite metric will always differ slightly from the result when it is performed by longhand. This is because of the way the router handles floating-point mathematics which results in slight rounding discrepancies.
2. Proposed ISPFA Implementation and Simulation
In  we proposed improved shortest path first algorithm (ISPFA) used in enhanced interior gateway outing protocol. We adopted the EIGRP bandwidth estimation and routing path selection model.
We described EIGRP bandwidth estimation and routing path selection.
Two major delay metrics were considered in the proposed ISPFA. These are: propagation delay and queuing delay. The queuing delay was considered to be closely related to the bottleneck bandwidth and traffic characteristics. In order to avoid inter-dependence among the identified delay metrics, only the propagation delay was used in the delay metric. This helped in simplifying and modifying the delay path computation. Also, we considered the weighted values of different network link characteristics together in order to calculate a metric for routing path selection. These characteristics include:
i. Delay (measured in of microseconds)
ii. Bandwidth (measured in kilobytes per second)
iii. Reliability (in numbers ranging from 1 to 255; 255 being the most reliable)
iv. Load (in numbers ranging from 1 to 255; 255 being considered saturated).
The new SPFA model for EIGRP was found to be
EIGRP TDMNEW = (1)
Where L = packet size, R = transmission rate/link Bw, N = number of nodes, m = link distance, S = link speed, BWavg = the average bandwidth and Bs= file size to be transmitted.
3. System Parameters
This section presents the parameters and their values for the computation of the results. Table 2 details the different paths through which data can be transmitted from source to destination. It also shows minimum bandwidth along each path and the computed average link bandwidths. The different bandwidths are used to calculate EIGRP metrics for selecting the best path. It is assume that a data of size 10Kb is to be transmitted from source to destination as shown in the table 2.
|Path||No. Of Hops||Minimum Bandwidth||Average Bandwidth|
The network configuration used for the analysis of the proposed SPFA is as shown in figure 2.
4. Comparative Analysis of the Proposed SPFA
In this section, we analyse the performance of the proposed ISPFA and compare it with some existing EIGPRT algorithms.
|Packets size||Link Delay (ISPFA)||Link Delay (new)|
Table 3 shows the link delay as a response to packet size for both algorithms. The graphical representation of this is as shown in figure 2. Comparatively, the ISPFA has a reduced link delay over the existing algorithm. Calculations on the above table show that the new formula has over 36% average improvement on delay.
|Packets size||TDM (ISPFA)||TDM (new)|
Table 4 shows increase in EIGRPT total delay metric with increasing packet size for both the existing and new algorithm. Figure 3 shows the graphically comparison of the existing and the new algorithm. It also shows the degree of improvement of the new algorithm over the existing. As expected, the increase in packet size increases the metric values in both cases. This means that the larger the data (increase in number of packets to be transmitted), the higher the TDM. But, the difference is observed in both algorithms. The TDM in ISPFA is reduced to about 36% of that of the existing metric. This also justifies that fact that the new algorithm does better than the existing.
|Packets size||Link Delay (existing)||Link Delay (ISPFA)||Improvement per size|
Table 5 shows the improvement of the proposed ISPFA over existing per packet size link. ISPFA has an average of 3.02 improvements per size over the existing algorithm.
In this paper, improved shortest path algorithm (ISPFA) for enhanced interior gateway routing protocol proposed earlier in  was analysed and compared with existing algorithm. The effects of various network parameters were investigated. It was observed that as the packet size increases, the link transmission delay also increases. The packet size was also observed to have the same effect on the EIGRP Total delay Metric. Though each routing protocol has its own standards to judge a route quality by using metrics like next hop count, bandwidth and delay. The proposed ISPFA algorithm when compared with existing one has a better performance. It was observed that the proposed ISPFA has a smaller end-to-end delay when compared to that of the existing shortest path algorithm used in EIGRP routing protocol. In conclusion, it was established the proposed ISPFA has about 36% average improvement over the existing EIGRP algorithm.