Category Archives: Routing Protocol Algorithm

Distance, Link State and Path Vector?

Distance Vector:
Route information is passed hop-by-hop through the network and a calculation is performed at each hop – a distributed calculation using local information. Each router along a route is dependent on the router before it to perform its calculations correctly and then correctly pass along the results.

When a router advertises the prefixes it learns to its neighbors it’s basically saying, “I know how to reach these destinations.” And because each distance vector router knows only what its neighbors tell it, and has no “view” of the network beyond the neighbors, the protocol is vulnerable to loops.

Link State:
Every link state router floods information about itself, its links, and its neighbors to every other router. From this flooded information each router builds an identical link state database. Each router then independently runs a shortest-path-first calculation on its database – a local calculation using distributed information – to derive a shortest-path tree. This tree is a sort of map of the shortest path to every other router.

One of the advantages of link state protocols is that the link state database provides a “view” of the entire network, preventing most routing loops.

Path Vector:
A path vector protocol does not rely on the cost of reaching a given destination to determine whether each path available is loop free or not. Instead, path vector protocols rely on analysis of the path to reach the destination to learn if it is loop free or not.

A path vector protocol guarantees loop free paths through the network by recording each hop the routing advertisement traverses through the network.

RIP/IGRP:

EIGRP:
An older definition of eigrp is that it is a hybrid routing protocol; sharing the best qualities of distance vector and link state. Actually there are no link state qualities to eigrp and it has more correctly come to be known as an “advanced distance vector” protocol based on a distributed form of the bellman-ford algorithm. Vectors of distance are exchanged between nodes, and resultant distances between nodes, but an overall picture of the topology is not assembled, as in link state.

OSPF:
Ospf, like is-is is a link state protocol. Both are based on dijkstra’s algrithm, also known as distributed database protocols, each router originates information about itself, it’s directly connected links, and states of those links… thus link state… they pass this information and make copies of it between routers, but never change it… this makes for identical views of the overall network topology…

As jeff doyle puts it, “distance vector is a road sign while link state is a road map”, in his book which compares ospf and isis…

According to john t moy, rfc 2328.
The OSPF protocol is based on link-state or SPF technology.
This is a departure from the Bellman-Ford base used by traditional
TCP/IP internet routing protocols.
In a link-state routing protocol, each router maintains a
database describing the Autonomous System’s topology. This
database is referred to as the link-state database. Each
participating router has an identical database.

BGP/IS-IS:

Reference:
http://www.informit.com/articles/article.aspx?p=331613&seqNum=2
https://www.networkworld.com/article/2348778/cisco-subnet/my-favorite-interview-question.html

Advertisements