American Journal of Engineering and Technology Management
Volume 1, Issue 3, October 2016, Pages: 25-30

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

Email address:

(U. I. Akpan)
(E. H. Johnson)

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


1. Introduction

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 [1]. 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 [2]. 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 [2]. 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 [2].

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 [2].

Routers running EIGRP must become neighbours before exchanging routing information. To dynamically discover neighbours, EIGRP routers use the multicast address of 224.0.0.10. 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 [2].

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 [2].

1.4.1. Bandwidth

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.

1.4.2. Delay

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.

1.4.3. Reliability

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.

1.4.4. Load

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.

Table 1. Common IGRP and EIGRP Metrics.

Medium Bandwidth Delay
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 [1] 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.

Table 2. System Parameters.

Path No. Of Hops Minimum Bandwidth Average Bandwidth
A-B-E-F-G 4 20Mbps 50Mbps
A-B-F-G 3 56Kbps 23.35Mbps
A-B-D-F-G 4 10Mbps 43.75Mbps
A-D-F-G 3 1.5Mbps 48.83Mbps
A-D-B-E-F-G 5 1.5Mbps 38.3Mbps
A-D-B-F-G 4 56Kbps 15.38Mbps
A-C-D-F-G 4 64Kbps 61.2Mbps
A-C-D-B-E-F-G 6 64Kbps 48.3Mbps

The network configuration used for the analysis of the proposed SPFA is as shown in figure 2.

Figure 1. Network Configuration for ISPFA Analysis.

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.

Table 3. Packet Size vs. Link Delay.

Packets size Link Delay (ISPFA) Link Delay (new)
10000 0.009971 0.004077
50000 0.174854 0.061191
100000 0.662207 0.224397
150000 1.462061 0.489616
200000 2.574414 0.85685
250000 3.999268 1.326098
300000 5.736621 1.89736
350000 7.786475 2.570636
400000 10.14883 3.345926
450000 12.82368 4.223231
500000 15.81104 5.202549
550000 19.11089 6.283882
600000 22.72324 7.467229
650000 26.6481 8.75259
700000 30.88545 10.13997
750000 35.4353 11.62936
800000 40.29766 13.22076
850000 45.47251 14.91418
900000 50.95986 16.70961
950000 56.75972 18.60705
1000000 62.87207 20.60652
1050000 69.29692 22.70799
1100000 76.03428 24.91148
1150000 83.08413 27.21698
1200000 90.44648 29.6245
1250000 98.12134 32.13403

Figure 2. Packet Size against Link Delay for the new and existing Algorithms.

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.

Table 4. Packet size vs. EIGPRT TDM.

Packets size TDM (ISPFA) TDM (new)
10000 1001.369 632.5584
50000 5022.843 3172.897
100000 10085.69 6371.058
150000 15188.53 9594.481
200000 20331.37 12843.17
250000 25514.21 16117.12
300000 30737.06 19416.33
350000 35999.9 22740.81
400000 41302.74 26090.55
450000 46645.58 29465.55
500000 52028.43 32865.81
550000 57451.27 36291.34
600000 62914.11 39742.14
650000 68416.95 43218.19
700000 73959.8 46719.51
750000 79542.64 50246.09
800000 85165.48 53797.94
850000 90828.32 57375.04
900000 96531.17 60977.41
950000 102274 64605.05
1000000 108056.9 68257.95
1050000 113879.7 71936.11
1100000 119742.5 75639.53
1150000 125645.4 79368.22
1200000 131588.2 83122.17
1250000 137571.1 86901.38
1300000 143593.9 90705.85
1350000 149656.7 94535.59
1400000 155759.6 98390.6
1450000 161902.4 102270.9

Figure 3. Effect of Packet Size on EIGRPT Total Delay Metrics.

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.

Table 5. Improvement of the Proposed SPFA over Existing per Packet Size.

Packets size Link Delay (existing) Link Delay (ISPFA) Improvement per size
10000 0.009971 0.004077 2.445671
50000 0.174854 0.061191 2.857512
100000 0.662207 0.224397 2.951051
150000 1.462061 0.489616 2.986138
200000 2.574414 0.85685 3.00451
250000 3.999268 1.326098 3.015816
300000 5.736621 1.89736 3.023475
350000 7.786475 2.570636 3.029007
400000 10.14883 3.345926 3.03319
450000 12.82368 4.223231 3.036462
500000 15.81104 5.202549 3.039095
550000 19.11089 6.283882 3.041255
600000 22.72324 7.467229 3.043062
650000 26.6481 8.75259 3.044596
700000 30.88545 10.13997 3.045911
750000 35.4353 11.62936 3.047055
800000 40.29766 13.22076 3.048059
850000 45.47251 14.91418 3.048945
900000 50.95986 16.70961 3.049734
950000 56.75972 18.60705 3.050442
1000000 62.87207 20.60652 3.051077
1050000 69.29692 22.70799 3.051654
1100000 76.03428 24.91148 3.052178
1150000 83.08413 27.21698 3.052658
1200000 90.44648 29.6245 3.053097
1250000 98.12134 32.13403 3.053502

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.

5. Conclusion

In this paper, improved shortest path algorithm (ISPFA) for enhanced interior gateway routing protocol proposed earlier in [1] 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.


References

  1. U. I. Akpan, U. E. Udoka and E. H. Johnson, "Improved Shortest Path First Algorithm for Enhanced Interior Gateway Routing Protocol (EIGRP)," American Journal of Intelligent Systems 2016, 6 (2): 31-41 DOI: 10.5923/j.ajis.20160602.01.
  2. R. Devi, B. Sumathi, T. Gandhimathi, and G. Alaiyarasi, "Performance Metrics of MANET in Multi-Hop Wireless Ad-Hoc Network Routing Protocols," International Journal of Computational Engineering Research (IJCER) ISSN. 2250-3005.
  3. M. Sportack, "IP Routing Fundamentals," 2nd ed. California: Cisco Press. pp. 23, 1999.
  4. C. Xianhui and J. C. Lee, "VoIP Performance over Different Interior Gateway Protocols," International Journal of Communication Networks and Information Security (IJCNIS), 1 (1): 34-39, 2009.
  5. D. C. Cox, "Wireless Personal Communications: What is it?" IEEE Personal Communications, vol. 2, no. 2, pp. 20-35, 1995.
  6. T. F. Johansson, "Bandwidth efficient AMR Operation for VoIP," IEEE Proceedings of the Workshop on speech Coding, 3, 150-152, 2002.
  7. L. Cidon and M. Sidi, "A Multi-Station Packet-Radio Network," Performance Evaluation, 8 (1): 65-72, 1988.
  8. J. C. Bolot, "Characterizing End-to-End Packet Delay and Loss in the Internet," ACM SIGCOMM, 2(4): 289–98, 1993.
  9. R. L. Carter, and M. E. Crovella, "Measuring Bottleneck Link Speed in Packet-Switched Networks," Proc. Perf. Eval. 27(28): 297–318 1996.
  10. M. Jain, and C. Dovrolis, "End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP Throughput," ACM SIGCOMM., 34, 295–308, 2002.
  11. A. M. Mark, "Voice over IP Technologies: Building the Converged Network," 2nd ed. New York: John Wiley and Sons, Inc. pp. 234-237, 2002.
  12. A. R. Nohl, and G. Molnar, "The convergence of the OSPF Routing Protocol," Periodica Polytechnica Electrical Engineering, 47(1-2): 89-100, 2002.
  13. M. Rashed, and M. Kabir, "A Comparative Study of Different Queuing Techniques in VOIP, Video Conferencing and File Transfer," Daffodil International University Journal of Science and Technology, 5 (1), 37-47, 2010.
  14. S. G. Thorenoor, "Dynamic Routing Protocol Implementation Decision between EIGRP, OSPF and RIP Based on Technical Background using OPNET Modeler," 2010 Second International Conference on Computer and Network Technology (ICCNT 2010), 191-195.
  15. B. A. Forouzan, "TCP/IP Protocol Suite", McGraw-Hill Education Press. P. 269. ISBN 0-073-37604-3. Retrieved on March 25, 2009.
  16. V. Paxson,"End-to-End Internet Packet Dynamics," IEEE/ACM Trans. Net., 7 (3): 277-292, 1996.
  17. T. Lammle, (2011). Cisco Certified Network Associate Study Guide, Wiley Publishing, Inc., Seventh Edition.
  18. K. Archana, S. Reena and A. Dayanand, " Performance Analysis of Routing Protocols for Real Time Application," International Journal of Advanced Research in Computer and Communication Engineering. 3 (1): 23- 25, 2014.
  19. J. E Padgett, C. G Gunther and T. Hattori, "Overview of Wireless Personal Communications," IEEE Communications Magazine, pp. 28-41, 1995.
  20. B. Fortz and M. Thorup, "Optimizing OSPF/IS–IS weights in a changing world," IEEE Journal on Selected Areas in Communications, vol. 20, no. 4, pp. 756 767, May 2002.

Article Tools
  Abstract
  PDF(344K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931