Interior Routing Protocols

2.a.The Basics

In order to form a network, in most cases people start by connecting the endpoint devices (PCs, tablets, smartphones, servers, printers etc.) through their network interface cards (NICs) to switches or wireless access-points. In this fashion Local Area Networks are created, which operate mainly at the Data-Link Layer (Layer 2) of the OSI networking model (Sendra, et al., 2011).

Yet, how different local area networks connect? The solution is to implement routing. Routing is the process of selecting a path to a destination and is performed by routing devices (routers, Layer 3 switches or servers) at the Network Layer (Layer 3) of the OSI networking model. The packets are examined and they are “routed” to their destination by taking into account the Layer 3 destination address. Although routing has been performed initially by servers, later on it was assigned specialized equipment namely routers (Doyle, 2001).

And how routers operate? First of all, routers are connected to multiple networks. When they receive a packet on one of their interfaces they examine whether the packet is destined to the same network this interface belongs to. In this case, they simply ignore the packet. But if the packet is destined for a different network, then they perform a lookup operation, searching through their routing table, in other words a local database, to find an exit interface to forward the packet. Therefore a router performs two operations, a lookup process to find a route in their routing table, and a switch operation to take a packet from one interface and encapsulate it again to be sent to a different interface (Kurose & Ross 2004).

The most crucial part: how are routing tables created? At first, the router inserts to the routing table all the different networks that are directly attached to it and are operational. Then it inserts all networks that are configured by the administrator through static route commands. Finally, if a dynamic protocol is configured and running, the router inserts all routes learned through this protocol into the routing table. If all above steps are performed, then the routing table is dynamic and changes whenever there is an update in the network topology (Medhi & Ramasamy, 2007).

Dynamic protocols are divided in different categories based on whether they operate inside or outside an autonomous system (interior or exterior gateway protocols), or on whether they implement a distance-vector or link-state protocol. An autonomous system is a set of routers that operate under the same administrative control and can encompass a very large number of routing devices. Examples of interior gateway protocols are: RIPv1 and RIPv2, IGRP, EIGRP, OSPF and IS-IS while the industry standard in exterior gateway protocols is the BGP (Medhi & Ramasamy, 2007; Kurose & Ross, 2004).

2.b.Distance Vector Routing and Routing Challenges

By the term distance-vector routing is meant that routing decisions are made based on vectors of routes (along with the corresponding distances) learned by directly connected neighboring routing devices. It is a fact that routers that implement distance-vector routing do not know the entire network topology but only have knowledge of the distance from the destination network and the direction that traffic must be forwarded. Routing protocols that belong to the distance vector category are: RIPv1m RIPv2, IGRP and EIGRP (Xu, Dai & Garcia-Luna-Aceves, 1997).

By the term direction is meant that a route is discovered by the interface of a router and by the term distance is meant the “cost” to reach a network destination. This “cost” can be measured in “hops” (routing devices) in the case of the RIP protocol or through a composite metric in the case of IGRP and EIGRP, taking into account factors such as bandwidth, delay, load and reliability (Vutukury & Garcia-Luna-Aceves, 2001).

One of the main characteristics of distance-vector routing is that updates are sent periodically to all interfaces. These updates may contain the whole routing table or a part of it (partial updates). When a participating router receives such an update, it compares to what it already knows in its routing table, encompasses all new information, renews existing information and then floods what it knows to its neighbors (Pei et al., 2004).

This type of routing has some inherent problems concerning the creation of routing loops, in the case that multiple paths exist to a destination. This happens since distance-vector routing is called routing-by-rumor. Each router does not have an explicit idea about the whole network topology but believes what its neighbors are telling him. Various ways have been developed to deal with this problem and these can be summarized to: counting to infinity, split-horizon and poison reverse. Since these are not a topic of this thesis they are not further analyzed (Rakheja et al., 2012).

2.c.Link-State Routing

By the term link-state routing is meant that routing decisions are made individually on each router based on a network graph that exists in its memory. This graph contains the connections of all nodes on the autonomous system (all existing operational links). This topology information permits each router to calculate the best path or paths to all different networks in a system, which are then placed on the routing table. A main characteristic of this process is that a router needs not to update periodically its neighbors but only when an event occurs (new router discovered or sudden link failure). Routing protocols that belong to the link-state category are: OSPF and IS-IS (Liu & Reddy, 2004).

Link-state routing starts with the neighbor discovery phase where every router exchanges hello packets to find the neighbors on all operational links and maintain relationships with them. Afterwards, each router floods its connected links, so that all the routers inside the autonomous system learn the links and those who are producing these. All these links end in a link topology table maintained by each router. This table along with the neighbor table allows each router to form a complete topological view of the network (Haas & Pearlman, 2001).

The final stage is the execution of an algorithm which produces the shortest path to each link on the network, based on the link cost parameter. A network graph is created and the router starts executing a shortest path algorithm by putting itself as the root of the output tree. The final output of the algorithm, which runs independently on each router, populates the routing tables inside the autonomous system. A characteristic feature of the algorithm is that alterations in the topology lead to the re-computation of the shortest path algorithm and as a result to a CPU and memory burden (Hinds, Atojoko & Zhu, 2013).

This type of routing has an inherent advantage over distance-vector routing. Since all routers have knowledge of the whole topology, and in particular the same view of the network topology, the formation of routing loops is more difficult to happen.

2.a.The OSPF Protocol

2.d.1.Description

Open Shortest Path First is an Interior Gateway Routing Protocol for Internet Protocol (IP) networks and its research originated from a working group of the Internet Engineering Task Force (IETF) as early as the 1970s, with some implementations on the Arpanet. OSPF belongs to the link state routing protocol family and is used in order to distribute routing information within a single Autonomous System. It must be noted that the name of this protocol depicts its two main characteristics. The first word Open refers to the fact that the protocol was developed using the open and public RFC (Request for Comments) process and the SPF (Shortest Path First) refers to the well-known algorithm by Dijkstra which dynamically determines the shortest path through a network. In 1989, the first OSPF version was created (OSPFv1) and drafted in RFC 1131. In 1991, the second version (OSPFv2) was drafted and revised in RFC 1583, 2178 and 2328. Finally, in 1997 the OSPFv3 for IPv6 was released in RFC 2740 (Moy, 1998; Ferguson & Moy, 2008).

2.d.2. Message Encapsulation

In general, an OSPF message is encapsulated in a packet as followed (Graziani & Jonson, 2008):

Data Link Frame Header IP Packet Header OSPF Packet

Header

OSPF packet Type
1. Mac Source Address (Address of sending interface)

2. Mac Destination Address (Multicast address: 01-00-5E-00-00-05 or 01-00-5E-00-00-06)

1.IPv4 Source Address (Address of sending interface)

2.IPv4 Destination Address (Multicast: 224.0.0.5 / 224.0.0.6 and Protocol field 89)

Type Code

1.Router ID

2.Area ID

1. Hello Packet

2. Database Description

3. Link state request

4. List state update

5. List state acknowledgement

Table 2.d. 1: Encapsulated OSPF Message

More specifically, the OSPF Packet Header is included with every OSPF packet and is encapsulated in an IP packet with a Protocol field of 89 while the destination address is either the multicast address 224.0.0.5 or the 224.0.0.6. The OSPF Packet Header is depicted in the table below (Graziani & Jonson, 2008; Ferguson & Moy, 2008):

Version Number

version 2 for IPv4 version 3 for IPv6

Type

Hello, DBD, LSR, LSU, LSAck

Packet Length

Length of the OSPF packet in bytes including the standard OSPF header.

Router ID

Router ID of the source router.

Area ID

Area ID -32 bit number – where the packet originated.

Checksum

It is used in order to check the integrity and ensures that the OSPF packet is not corrupted during transmission including the header.

AuType

Describes the type of OSPF packet authentication

0  no authentication

1 simple authentication, clear text password

2 encrypted message digest key MD5

Authentication

The 64bit field which is used for the authentication of the OSPF packet in order to participate in the routing domain.

Authentication

Table 2.d. 2: OSPF Packet Header

Furthermore, OSPF uses five different packet types. Each one serves a different purpose (Ferguson & Moy, 2008). These are:

1. Hello Packet
2. DataBase Description (DBD)
3. Link State Request (LSR)
4. List State Update (LSU)
5. List State Acknowledgement (LSAck)

Table 2.d. 3: OSPF Packet Types

  1. Hello Packet (OSPF Type 1 packet) is used to discover the neighbors and exchange the routing databases. Through this packet, certain parameters are advertised and when their match is accomplished the adjacent router becomes neighbor. Furthermore, Hello packets are utilized as a keep-alive mechanism. Specifically, Hello packets are sent periodically to their neighbors in order to obtain bidirectional communication. If a router does not receive Hello packets from its neighbor in a particular interval (Dead interval), then the neighbor declared down (presumed dead) and all the information acquired through it is invalidated. It must be stressed that on Broadcast or NBMA networks, the Designated (DR) and Backup Designated Routers (BDR) routers are being elected through Hello packets (Graziani & Jonson, 2008).
Network Mask

The network mask of the originating interface is composed of 32 bits which describes how it is related to the sending interface.

Hello Interval

The interval among the routers when they exchange information in order to obtain adjacency in specified in number of seconds (default 10 seconds).

(By default the interval retransmission is 5 seconds.)

Options

Determines optional capabilities such as E-bit (bit flag) that indicates the area type in which the interface operates (1=normal, 0=stub).

Router Priority

This field is used on Broadcast and NBMA networks in order to determine the election of DR & BDR based on the highest priority number. If the priority is assigned to 1, the higher priority router is elected as the DR. In the special case that the priority is 0, then the corresponding does not participate in the election process. This field is considered non-preemptive after the completion of the election.

Router Dead Interval

The timer that signifies inactive or dead adjacencies. It is the interval in which a router does not receives another router’s Hello packets (by default 40 seconds).

Designated Router (DR)

This Router ID is assigned to the DRs RID.

Backup Designated Router (BDR)

After the election of the DR as router is elected ad BDR. Its RID is put in this field

List of Neighbor(s)

The neighboring router IDs from which valid Hello packets were received in the last Dead Interval time.

Table 2.d. 4: OSPF Hello Packet

  1. DataBase Description Packets (OSPF Type 2 packets) are exchanged when an adjacency is formed providing the link state Database topological content. The receiving router verifies the local link state Database through a poll-response procedure between master and slave routers.
  2. Link State Request Packets (OSPF Type 3 packets) are used to request more information about the topological Database after the exchange of the Database Description packets with the neighboring routers. This constitutes the last stage for the creation of the adjacency.
  3. List State Update Packets (OSPF Type 4 packets) purpose is to flood the link state advertisement. Several Link State Updates are included in a single Link State Update.
  4. List State Acknowledgement Packet (OSPF Type 5 packet) are sent and received in order to make the flooding of the multiple link state advertisements via the LSU packets reliable.

A summary table of the Link State Advertisements

Link State Advertisement (LSA) Types # Description
1 Router LSAs
2 Network LSAs
3,4 Summary LSAs
5 Autonomous System External LSAs

Table 2.d. 5: LSAs

Router LSAs (Type 1) are generated by all routers for each area that belong to. These are only flooded within a particular area and in no case they cross areas.

Network LSAs (Type 2) are generated by the Designated Routers and describe all routers that are connected in a specific segment of the network. They are flooded only within the area. 

Summary LSAs (Type 3 and 4) are generated by Area Border Routers (ABRs) in order to advertise inter-area routes to the other areas in an Autonomous System. Type 3 messages (summary links) aggregate routes between areas, while Type 4 messages describe routers through which the ASBR can be reached. With Type 4 messages all routers are aware of routers that lead outside the Autonomous System.

External LSAs (Type 5) are generated by ASBRs in order to inform all routers on external routes to the Autonomous System. These routes are redistributed in OSPF and are flooded all over except the stub areas.

2.d.3.The Routing Metric – Cost

The OSPF protocol uses as its metric the cost of an interface. This is inversely proportional to the bandwidth of the interface. It is profound that the higher the bandwidth of an interface the lower the cost.

The cost of an interface in OSPF routing protocol is determined by the formula above. It should be mentioned that the value of 108 is equal to 100.000.000 in bps and the cost of an interface is measured by default based on the bandwidth. Moreover, the cost would be easily attained if the reference bandwidth is divided by the interface bandwidth (Cisco, 2005).

2.d.4.Algorithm and Operation

OSPF is a link state routing protocol which implements the shortest path first algorithm to determine the path with the least costs to all known destinations. The shortest path to all destinations are calculated using the Dijkstra algorithm which provides an optimal solution considerably convoluted. Several processes of the algorithm are detailed below:

  • Each link has an associated cost and the objective is for each router to have a complete database of all the links that exist on the network.
  • A link-state advertisement is generated by the router whenever a change in an attached network occurs or during initialization.
  • LSAs are being exchanged through the flooding procedure between all routers. Each router stores the identical link-state update that has received, in its link-state database and afterwards propagates the link-state update to other routers.
  • When the creation of the link-state database in every router is accomplished, the router running the Dikjstra algorithm, creates a shortest path tree to all destinations.
  • If something changes in the network, such as a flapping interface or a change in link costs, the link-state protocol propagates these throughout the network, allowing all routers to keep-up to date their topological information (Graziani & Jonson, 2008; Ferguson & Moy, 2008).

In order for each router to create its routing table, it utilizes the neighbor table, the topological information and the shortest-path first algorithm. It assumes that itself is the starting point and calculates a loop-free topology by running the SFP algorithm, examining in turn all the topological information learned by adjacent routers. In the following figure is depicted how a physical topology is transformed to a tree.

 

2.d.5.Convergence

The convergence of the OSPF protocol is extremely fast, compared to all other internal gateway protocols. It is consisted of three factors, which must be careful taken into account, when designing an OSPF network. These are (Goyal et al., 2012):

  • Detection of a topology modification – this is the time needed by OSPF to detect a link or interface change or even worse failure.
  • Establishment of a new adjacency or revocation of an existing one – in response to a change in the network.
  • Propagation of a change in the network – this time entails the generation of LSA messages and their flooding throughout the network (or better the area).
  • SPF tree calculations – this is the time spent by each router in order to run the SPF algorithm and provide a loop-free topology.
  • Forwarding table creation – this is the time needed for the router to create the routing table.

Thus the total time needed for OSPF to converge is:

Convergence Time = Change Propagation Time + SPF Execution Time + Routing Table Creation Time + Failure Detection Time

In a typical convergence situation the average time needed for a router to propagate the Link State Advertisements and run the SPF algorithm is slightly less than 1 second. In parallel, the default time for the SPF algorithm to rerun (delay timer) is 5 seconds. This provides the lower boundary for the convergence of the OSPF protocol in its default settings. The upper boundary is determined by factors such as the size of the networks, size of the topology database and of course, the type of failure. In the worst case, a link fails without an alternative route existing, thus leading to the protocol waiting for the dead timer to expire introducing a 40 second delay in the default situation.

2.d.6.DRs and BDRs

Depending on the network type, mainly in multi-access networks, the OSPF process may lead to the election of a DR (Designated Router) and a BDR (Backup Designated Router). These roles are the focal points for the exchange of OSPF information, reducing the full adjacency relationships between routers connected on a multi-access medium. Each non-DR or non-BDR router forms a full adjacency relationship only with the DR and BDR, exchanging routing information only with these two routers on the network segment. Therefore the role of the DR is to distribute the updated topology information to all routers on the same segment leading to a significant reduction in routing traffic.

In order to accommodate the aforementioned process, two multicast IP addresses are used: 224.0.0.6 is used by all routers on a segment to inform the DR and BDR on any topology changes, while 224.0.0.5 is used by the DR to send Link State Updates to all routers on the segment.

The factors that determine the router that wins the DR/BDR election process are the following:

  1. The router with the highest priority becomes the DR on the multi-access segment. By default all routers have a priority of 1 and a priority of 0 enforces the router not to participate in the election process.
  2. The router with the highest Router ID becomes the DR. In this point it must be mentioned that the Router ID is determined in order of significance by:
  3. the commend router-id which sets the Router ID to a particular value or
  4. the largest IP address of the loopback interfaces configured on the router or
  • the largest IP address of the active interfaces configured on the router.

The router with the second highest priority or Router ID becomes the BDR.

In order to enforce the stability of the OSPF process:

  • When a BDR becomes DR, a new election takes place so as a BDR to be elected.
  • The factors presented above are taken into account when electing a new BDR.
  • If a router is being introduced in the network with highest priority after the election of the DR and BDR it cannot be elected until one of the DR and BDR routers fail (Cisco, 2005).

Figure 2: OSPF BR

2.d.7.     Hierarchical Structure Operation

OSPF is a hierarchical routing protocol segmenting the entire network into smaller areas. These are logical groups of routers, thus providing the capability of reduced instability, topology update containment as well as shorter routing tables. It must be stressed that when a network is constituted by more than one area, the OSPF protocol imposes some restrictions. Specifically, OSPF is composed of a centralized backbone network the Area 0 which links all the other lower areas within the hierarchy. All these areas must be physically connected to the backbone area in order to exchange routing information (each area stores a distinct link-state database). This is forwarded to the backbone area which afterwards floods this information to the other areas, thus decreasing the traffic between the different parts of the autonomous system. It must be noted that an area can be implemented either in the IP address format (0.0.0.0) or the decimal format (0). In the case that an area is not physically connected to the backbone area, a virtual link is required to be configured (Graziani & Jonson, 2008; Ferguson & Moy, 2008).

In order to accommodate better configuration and tuning of the protocol, different area types have been defined. These are:

i. Backbone Area

The Backbone Area constitutes the logical and physical core structure of an OSPF network and is accountable on distributing all routing information between non-backbone areas while it is situated at the center of all areas. It must be noticed that backbone must be contiguous and the connectivity could be established and maintained through the configuration of virtual links. Moreover, all OSPF areas have to be directly connected to the backbone area even through a virtual link.

ii.Stub Area

Stub Area is restricted in receiving route advertisements external to the autonomous system (AS), therefore the database size is reduced even more. Even so, stub area receives information about networks from other areas of the same OSPF domain. Basic features that are associated with stub area are elaborated below:

  • Stub area permits inter & intra area routes.
  • Stub area prohibits flooding of external LSAs.
  • A default route is defined inside stub areas.
  • OSPF routes inside the stub area must configured as stub routers.

iii.Not-So-Stubby Area (NSSA)

A Not-So-Stubby Area (NSSA) is a continuation of stub area that allows autonomous system external route infiltration into the stub area sending them to other areas without being capable of receiving external routes from other areas as well as importing external addresses. Distinguishing features of Not-So-Stubby Area are quoted below:

  • Autonomous System Boundary Router injects Type 7 LSA external addresses.
  • Area Border Router Type7 LSAs are converted into Type5 LSAs at NSSA, which are flooded to other areas.
  • NSSA allows summary LSAs.
  • NSSA prohibits external LSAs.

 

iv.Totally Stubby Area

A Totally Stubby Area is resemble to a stub area being physically connected to the backbone area from which only receives default route. Totally stubby area reaches other networks by a default route which is the only Type-3 LSA advertised into the area. Certain characteristics are presented as following:

  • Summarized routes such as Inter-area (IA) are not allowed into totally stubby area.
  • Intra-area routes are prohibited into totally stubby area.
  • The default route is permitted as a summary route reducing system resource usage due to the fact that the route processor supports less routing decisions.

v. Totally (NSSA) Not-So-Stubby Area

A Totally Not-So-Stubby Area is a combination of a TSA and a NSSA where only the default route is allowed from the backbone area (0.0.0.0) as well as the injection of external information in the local area with the ASBR and traverse. An area could be characterized as totally and NSSA presenting the features as following:

  • Summarized routes Type 3, 4 or 5 LSAs are not flooded in totally NSSA.
  • External routes are prohibited except the default route as summary route.
  • Area Border Router Type7 LSAs are converted into Type5 LSAs at NSSA, which are flooded to other areas (Shamim, et al., 2002).

vi. Transit Area

The transit area includes two or more OSPF border routers which get through network traffic from one adjacent area to another.

A Summary table of the OSPF areas and the restrictions

Areas Restrictions
Normal None
Stub Type 5 AS-external LSAs are prohibited.
NSSA Type 5 AS-external LSAs are prohibited.

ABR Type7 LSAs are converted into Type5 LSAs at NSSA are allowed.

Totally Stub Type 3, 4 or 5 LSAs are prohibited except the default summary route.
NSSA Totally Stub Type 3, 4 or 5 LSAs are prohibited except the default summary route.

ABR Type7 LSAs are converted into Type5 LSAs at NSSA are allowed.

Table 2.d. 6: OSPF Areas

2.d.8. Advantages and Disadvantages

In the following table the main advantages and drawbacks of the OSPF protocol have been summarized.

Advantages Disadvantages
ü  OSPF routing protocol is open in contrast to proprietary Cisco protocol as EIGRP. –        OSPF configuration is complex to be accomplished as well as to troubleshoot like other protocols.
ü  Loop free routes are always determined by OSPF. –        Link-state scaling problems mainly attributed to LSA flooding.
ü  When changes occur in the network they are propagated quickly throughout the network. –        The SFP algorithm imposes a large CPU load.
ü  It uses multicasting 224.0.0.5 in order to send periodically small hello packets verifying link operation without transferring the entire routing table, thus conserving network bandwidth. –        More memory is demanded to maintain the adjacency, routing and topology tables.
ü  It supports Variable Length Subnet Masks (VLSM) and CIDR through manual summarization. –        Unable to support unequal cost load balance.
ü  OSPF is a hierarchical protocol utilizing area 0 (autonomous System) as the top of the hierarchy.  
ü  It utilizes cost as the metric.  
ü  It is more suitable for large scaled networks.  
ü  It uses low bandwidth.  
ü  Multiple routes are supported.  
ü  Route exchanges are minimized and the size of routing table is shortened by the area architecture.  
ü  OSPF does not have hop count limitations.  
ü  OSPF packet is indicated by the IP header 89.  
ü  Packets are routed based on their type of service field.  

Table 2.d. 7: OSPF Advantages and Disadvantages

2.b.The EIGRP Protocol

2.e.1.Description

The Enhanced Interior Gateway Routing Protocol is a CISCO dynamic proprietary protocol for the Internet Protocol (IP), IPX and Appletalk networks designed by CISCO Systems at the University of California at Santa Cruz in 1992. However, in 2013 CISCO published it as an open standard. EIGRP belongs to the distance vector routing protocol family characterized as the more advanced of its kind due to the fact that it is more scalable in medium and large scaled networks. Despite the fact that it belongs to the distance vector family, it carries link state protocol features and is publicly characterized as a hybrid distance vector protocol. It must be stressed that is used in order to distribute routing information within the same Autonomous System sending incremental updates, minimizing the amount of work on the router as well as of data that is required to be transmitted. The most important feature of EIGRP that should be stressed is that it uses both equal-cost load balancing (ECLB) as well as unequal-cost load balancing. The former takes place in the same way as in the IGRP and OSPF. In other words, in networks with multiple equal-cost paths to the same route destination, rationally load-share traffic equally among these paths occurs. However, EIGRP is the only protocol that makes intrinsically equal & unequal cost load balancing. This happens through the use of the variance parameter. The EIGRP has the ability to combine successor routes with feasible successor routes (that exist in the topology table) in order to implement unequal-cost load balancing (Cisco, 2005; Albrightson, Garcia-Luna-Aceves, & Boyle, 2011).

2.e.2. Message Encapsulation

The following table presents the encapsulation of an EIGRP packet inside a Data Link frame (Cisco, 2007).

Data Link Frame Header IP Packet Header EIGRP Packet

Header

Type/Length/Value (TLV) Types
1. Mac Source Address (Address of sending interface)

2. Mac Destination Address (Multicast address: 01-00-5E-00-00-0A)

1.IPv4 Source Address (Address of sending interface)

2.IPv4 Destination Address (Multicast: 224.0.0.10 and Protocol field 88)

Opcode for EIGRP packet type

Autonomous System Number

General TLV Types: 0x0001=EIGRP Parameters

0x0003=Sequence

0x0004=Software Version

0x0005=Next Multicast Sequence

IP-Specific TLV Types:

0x0102=Internal Routes

0x0103=IP External Routes

Table 2.e. 1: Encapsulated EIGRP Message

More specifically, the EIGRP Packet Header is encapsulated in an IP packet with a Protocol field of 88 while the destination address is the multicast address 224.0.0.10. The EIFRP Packet Header is depicted in the table below (Leahy, 2015):

Version Number

version 1 for IPv4 & IPv6

OPCode (Operation Code)

Indicates the EIGRP packet type where

1=Update, 2=Reserved, 3=Query,4=Reply,5=Hello, 6=IPX-SAP, 10=SIA Query & 11=Reply Query

Checksum

Computed for the entire EIGRP packet precluding the IP header.

Flags

A 32 bits field utilized only for two flags:

First bit (0x00000001) known as initialized (init) bit indicates a new neighbor relationship

Second bit (0x00000002) known as conditional receive bit is utilized in the proprietary reliable multicasting algorithm.

Sequence  

A 32 bits field utilized by the Reliable Transport Protocol (RTP).

Acknowledgement

Ensures security and reliability for message passing.

AS Number

Identifies the EIGRP domain. A gateway may be used in more than one AS, thus separate routing tables are related to each AS not to mention are precisely specified.

Type / Value / Length

This field includes header’s information concerning the type (binary alphanumeric code) and states a variable field determined by the type which is the value as well as the length of the frame.

Table 2.e. 2: EIGRP Packet Header

Furthermore, EIGRP uses six different packet types. Each one serves a different purpose. These are (Leahy, 2015):

Hello Are sent via multicast in order to identify neighbors (unreliable)
Acknowledgment Are sent via unicast to confirm reliable delivery of EIGRP packets  (unreliable)
Updates Are sent via RTP & unicast in order to convey reachability of destinations (reliable)
Queries Are sent via RTP & multicast requesting routing information, for instance the status of the route for fast convergence (reliable)
Replies Are sent via RTP & unicast in response to Query packets (reliable)
Requests Are sent via multicast or unicast in order to collect distinguish information about the neighbors (unreliable)

Table 2.e. 3: EIFRP Packet Types

2.e.3.     The Routing Metric – Composite Metric

EIGRP associates six different vector metrics with each route and takes into account only four of them in order to compute the composite metric.

Bandwidth Minimum Bandwidth along the path from a router to the destination.
Load Number which ranges from 1 to 255
Total Delay Delay along the path from a router to the destination.
Reliability Number which ranges from 1 to 255
MTU Maximum Transmission Unit is never used in the metric calculation.
Hop Count Number of routers a packet passes through the network. Ho count is never used in the metric calculation.

Table 2.e. 4: EIGRP Metrics

EIGRP computes routing metrics using the minimum bandwidth on the path to a destination network as well as the total delay. It must be stressed that four vector metrics such as bandwidth, reliability, delay and load are being associated in order to compute the Composite metric for the determination of the preferred route (successor). The minimum bandwidth and the total delay metrics are defined from the values that have been set up on the interfaces of the routers in the path to the destination network using the following formula in order the EIGRP routing metric to be calculated (Cisco, 2015; Albrightson, Garcia-Luna-Aceves, & Boyle, 2011):

The default values for K weights are: K1 = 1, K2 = 0, K3 =1, K4 = 0, K5 = 0

Considering that the K2, K4 and K5 weights are zero by default, effectively the EIGRP metric formula leads to proceed in the following form:

(bandwidth + delay) * 256

 

Where Bandwidth and Delay are valued with the following calculations:

Bandwidth = 107 / Value of the bandwidth interface command (Constitutes the link with the least amount of Bandwidth).

Delay = Value of the delay interface command (Is related to each interface in milliseconds and becomes cumulative while a specific route crosses router after router).

2.e.4.     Algorithm and Operation

EIGRP supports IPv4 classless addressing and utilizes the DUAL algorithm in order to create the routing table. Both the algorithm and data structure (Neighbor Table & Topology Table) will be analyzed below:

Neighbor Table

EIGRP routers obtain information about the state of the adjacent neighbors and their IP addresses. Every time new neighbors are discovered their IP address and interface are recorded and stored in the neighbors’ table (data structure). While the neighbor sends Hello packets, it also advertises the Hold Time to determine whether the neighbor is operational and reachable. It must be noted that the ASN (Autonomous System Number), Subnet Number and K values must be identical in order for the neighbor adjacency to be formed. Hello packets are sent to the multicast address every 5 seconds on LAN interfaces & every 60 seconds on WAN interfaces to verify that the neighbor relationship is still active. If the Hold Time Interval passes (hold-down timer by default is 15 seconds) due to the fact that a Hello packet wasn’t heard within this, the DUAL algorithm is forced to run taking into account the topology changes. Furthermore, the neighbor table contains essential information for the RTP (Reliable Transport Protocol) mechanism in order to pair acknowledgements with their corresponding data packets. It must be stressed that round trip timers are stored in the neighbor table in order to evaluate an optimal retransmission interval (Graziani & Jonson, 2008).

Diffusion Update ALgorithm (DUAL)

EIGRP uses the DUAL (Diffusing Update ALgorithm) or else DUAL FSM (finish-state machine) which ensures that each route will be loop-free calculated in order for routing loops to be avoided. This algorithm responds promptly in changes that might occur in the routing topology and adjusts dynamically the routing tables. The factors that contribute in the loop-free routes mechanism are being analyzed below (Xu, Dai & Garcia-Luna-Aceves, 1997):

  1. Feasible Distance (FD) is the best EIGRP metric or else the lowest cost along a path to a destination network with the participation of the route metric that has been advertised by the neighbor, listed in the routing table.
  2. Reported Distance (RD) / Advertised Distance (AD) is the total cost of the route as advertised by the neighbor & needed along the path to the destination network.
  • Successor also known as current Successor (or primary route) is the route with the lowest Feasible Distance guarantying a loop-free path to a destination. The successor routes are installed in the routing table in order to be used for forwarding packets.
  1. Feasible Successor (FS) is the backup route with reported distance less than the feasible distance. The FD of the Feasible Successor is greater than the FD of the Successor, however it’s Advertised Distance (AD) must be lower than the FD of the Successor. These routes are stored in the topology table and are promoted immediately when the Successor route fails.
  2. Feasibility Condition (FC) is the condition that provides loop-free routes to a destination with the contribution of the Successor and Feasible Successor routes. Feasibility Condition states that the Reported Distance must be lesser than the Feasible Distance [RD < FD] in order for a route to become a feasible Successor (Cisco, 2015).

Topology Table

EIGRP topology table includes all learned routes to a destination advertised by neighboring routers. Specifically, the topology table stores routes and their metrics, Successors and Feasible Successors as well as locally connected subnets. It must be noticed that routes in the topology table are usable by the router only when they are active and inserted into the routing table or have a higher AD than an equivalent path. For every reachable network, the topology table contains the total delay, reliability and path loading, the lowest bandwidth on the path (the weakest link), the feasible and reporting distance and finally the route source (Graziani & Jonson, 2008).

2.e.5.     Convergence

Convergence starts when two routers become neighbors. This dynamic learning happens through the exchange of hello packets (default hello timer is 5 seconds on high-bandwidth links and 60 seconds on slower links). The outcome of this neighbor discovery is the creation of the neighboring tables with all the additional features as described in previous sections.

At that point the neighboring routers exchange routing information and build their corresponding topology tables. In a next step they employ the DUAL algorithm to calculate the feasible and reported distances, and of course the successor and feasible successor routers. The latter routes may exist in the case the feasibility condition is met, thus providing loop-free alternatives to the successor route.

The feasible successor routes and their existence is utmost significant to the EIGRP convergence process. When a successor (primary route) fails, then the EIGRP process (Sankar & Lancaster, 2014):

  • checks for a feasible successor and if one is found then it is immediately promoted to a successor and is inserted in the routing table
  • If a feasible successor does not exist, then the EIGRP process marks the failed route as ACTIVE in the topology table and starts sending query packets to all neighbor routers to find an alternate route to the network that failed. If these neighbors do not have an alternate route then they mark this failed route as ACTIVE in their topology tables, and generate query packets which they forward to their neighboring routers and so on. In case a router knows an alternate path, he responds to the query packets and all routers converge through a recursive process. In the case no router responds, the routers keep this route as ACTIVE until the corresponding EIGRP timers expire, but until then they all are Stuck-In-Active (SIA).

The aforementioned convergence process poses a threat to the scaling of an EIGRP network in an arbitrary way. When the number of routers in an EIGRP network grows to the number of hundreds, then the stuck in active situation may bring the network to its knees. In that case, a strict design must be implemented both in organizational structure and in route summarization.

Summarizing all the above points, in order for a network designer to make EIGRP convergence quicker he must:

  • Implement shorter timers. In this way, routers can form relationships faster and detect dead neighbors more efficiently.
  • Provide Route Summarization through the hierarchical structure of the network. In this way, when a query arrives at an EIGRP router which features a summarized route, he immediately replies to this query, thus terminating quicker the stuck-in-active situation.
  • Configure route filtering, so that a router will immediately respond to an EIGRP query with an inaccessible message reply, terminating again the SIA and helping in removing a non-existing route from all routing tables.
  • Configure stub routers in remote locations so that central routers not require forward any queries to these.

2.e.6.     Advantages and Disadvantages

In the following table the main advantages and drawbacks of the EIGRP protocol have been summarized.

Advantages Disadvantages
ü  It uses multicasting 224.0.0.10 in order to send hello packets verifying link operation without transferring the entire routing table, thus conserving network bandwidth. –        EIGRP summarizes routes at the classful boundaries automatically by default. This feature can be revoked with the no auto-summary command.
ü  Loop-free routes due to Feasibility Condition. –        Cisco’s proprietary protocol (only one part is open-source since 2013)
ü  It supports Variable Length Subnet Masks (VLSM) and CIDR allowing routes to be automatically summarized on a network. –        Full mesh adjacency relationship in a broadcast network where routers exchange information with others.
ü  Easy to configure.

 

–        Difficulty to manage big hierarchical networks.
ü  Fast Convergence due to the Dual algorithm. EIGRP router stores all neighboring tables so as to adapt very fast to alternate routes. –        Routers from other vendors are not able to use EIGRP and therefore protocol redistribution must be configured inside the autonomous system
ü  EIGRP depends on Reliable Transport Protocol (RTP) in order EIGRP packets delivery to all neighbors to be achieved properly. –        In the case of an arbitrary design, when the network grows significantly in size, stuck-in-active occasions may lead to slow convergence.
ü  EIGRP packet is indicated by the IP header 88. –        Triggers must be contained through summarization.
ü  Always back up routes via Feasible Successors.  
ü  Trigger updates notify when changes occur in the network.  
ü  Supports summarization in any interface with the benefit of the routing table decrease.  
ü  Efficient use of traffic through equal cost multipath (ECMP) and unequal cost load balancing.  
ü  EIGRP supports multiple network layer 3 protocols such as IP, IPX & Apple-Talk.  
ü  Superior scaling for large dynamic multipoint (DM) deployments.  
Scammycollege CO.
Scammycollege CO.

Networks & Security College Assignment Solutions.

Comments are closed.

//]]>