Routing Protocols: Classification of Routing Protocols

Classification of Routing Protocols

Distance vectorExamples: Routing Information Protocol Version 1 (RIPv1), RIPv2, Interior Gateway Routing Protocol (IGRP) Features periodic transmission of entire routing tables to directly connected neighbors Mathematically compares routes using some measurement of distance Features hop-count limitation



Link StateExamples: Open Shortest Path First (OSPF), Intermediate System- to- Intermediate System (IS-IS). Sends local connection information to all nodes in the internetwork. Forms adjacencies with neighboring routers that speak the same protocol; sends local link information to these devices. Note that although this is flooding of information to all nodes, the router is sending only the portion of information that deals with

the state of its own links. Each router constructs its own complete “picture” or “map” of the network from all of the information received.



Hybrid
Example: Enhanced Interior Gateway Routing Protocol (EIGRP) Features properties of both distance vector and link-state routing protocols



Path vector protocolExample: Border Gateway Protocol (BGP). Path vector protocols are a subset of distance vector protocols; BGP uses “path vectors” or a list of all the autonomous systems a prefix has crossed to make metric decisions and to ensure a loop free environment. In addition to the autonomous system path list, an administrator can use many other factors to affect the forwarding or receipt of traffic using BGP.

Routing Protocols: EIGRP Concepts

EIGRP Concepts

Successor

A successor for a particular destination is a next hop router that satisfies these two conditions:
it provides the least distance to that destination
it is guaranteed not to be a part of some routing loop

The first condition can be satisfied by comparing metrics from all neighboring routers that advertise that particular destination, increasing the metrics by the cost of the link to that respective neighbor, and selecting the neighbor that yields the least total distance. The second condition can be satisfied by testing a so-called Feasibility Condition for every neighbor advertising that destination. There can be multiple successors for a destination, depending on the actual topology.

The successors for a destination are recorded in the  topology table and afterwards they are used to populate the routing table as next-hops for that destination.


Feasible Successor

A feasible successor for a particular destination is a next hop router that satisfies this condition:
it is guaranteed not to be a part of some routing loop

Thus, every successor is also a feasible successor. However, in most references about EIGRP the term "feasible successor" is used to denote only those routers which provide a loop-free path but which are not successors (i.e. they do not provide the least distance). From this point of view, for a reachable destination there is always at least one successor, however, there might not be any feasible successors.
Active and Passive State

A destination in the topology table can be marked either as Passive or Active. A Passive state is a state when the router has identified the successor(s) for the destination. The destination changes to Active state when current successor no longer satisfies the Feasibility Condition and there are no feasible successors identified for that destination (i.e. no backup routes are available).


Reported Distance and Feasible Distance

Reported Distance (RD) is the total metric along a path to a destination network as advertised by an upstream neighbor

A Feasible Distance (FD) is the lowest known distance from a router to a particular destination.

This diagram shows the example of Feasible and Reported distance of EIGRP network topolgy description as above

*Feasibility Condition

If, for a destination, a neighbor router tells us that it is closer to the destination than we have ever been, then this neighbor lies on a loop-free route to this destination.
In exact terms, every neighbor that satisfies the relation RD < FD for a particular destination is on a loop-free route to that destination.

Routing Protocols: EIGRP Metric

EIGRP Metric

Bandwidth

Minimum Bandwidth (in kilobits per second) along the path from router to destination network

Load

Load (number in range 1 to 255; 255 being saturated)

Delay

Total Delay (in 10s of microseconds) along the path from router to destination network

Reliability

Reliability (number in range 1 to 255; 255 being the most reliable)

MTU

Minimum path Maximum Transmission Unit (MTU) (never used in the metric calculation)

Formula

Metric = 256*([K1*Bw + K2*Bw/(256-Load) + K3*Delay]*[K5/(Reliability + K4)])

The default is for K1 and K3 to be set to 1, and the rest to zero, effectively reducing the above formula to (Bandwidth + Delay) * 256.