3.3.c [i] Distance vector
The name distance vector is derived from the fact that routes are advertised as vectors of (distance, direction), where distance is defined in terms of a metric and direction is defined in terms of the next-hop router. For example, “Destination A is a distance of 7 hops away, in the direction of next-hop router Y.” As that statement implies, each router learns routes from its neighboring routers’ perspectives and then advertises the routes from its own perspective . Because each router depends on its neighbors for information, which the neighbors in turn may have learned from their neighbors, and so on, distance vector routing is sometimes also referred to as “routing by rumor.”
Adam, Paul (2014-07-12). All-in-One CCIE V5 Written Exam Guide (Kindle Locations 2650-2655). . Kindle Edition.
3.3.c [ii] Link state
Link state routing protocols are like a roadmap. They have a complete picture of the network. The reason is that unlike the routing-by-rumor approach of distance vector, link state routers have firsthand information from all their peer routers. Each router originates information about itself, its directly connected links, and the state of those links. This information is passed around from router to router, each router making a copy of it, but never changing it. The ultimate objective is that every router has identical information about the internetwork, and each router independently calculates its own best paths.
Adam, Paul (2014-07-12). All-in-One CCIE V5 Written Exam Guide (Kindle Locations 2659-2663). . Kindle Edition.
3.3.c [iii] Path vector
A path vector protocol is a routing protocol which maintains the path information that gets updated dynamically. Updates which have looped through the network and returned to the same node are easily detected and discarded. This algorithm is sometimes used in Bellman– Ford routing algorithms to avoid “Count to Infinity” problems. BGP is an example of a path vector protocol.
Adam, Paul (2014-07-12). All-in-One CCIE V5 Written Exam Guide (Kindle Locations 2668-2670). . Kindle Edition.
3.3.c (i) Distance vector
3.3.c (ii) Link state
3.3.c (iii) Path vector
Distance – hop or metric Vector – direction
periodic transmission of entire routing table
mathematical comparison using measurement of distance
limited by hop count
ex. OSPF IS-IS
sends local connection information to all nodes on the internetwork
forms adjacencies with and sends link state information to same protocol speaking connected neighbors
about the state of it’s own links
constructs a view of the entire topology with this information
DUAL (Diffusing Update Algrithm)
exhibits characteristics of both link state and DV
subset of DV
constructs lists of passed AS paths to establish metrics and remain loop free
attributes are employed to affect sending and reception of traffic
3.3.c [ii] Link state
in his own words…
Construct [a] tree of minimum total length between the n nodes. (The tree is a graph with one and only one path between every two nodes.)
In the course of the construction that we present here, the branches are divided into three sets:
I. the branches definitely assigned to the tree under construction (they will be in a subtree);
II. the branches from which the next branch to be added to set I, will be selected;
III. the remaining branches (rejected or not considered).
The nodes are divided into two sets:
A. the nodes connected by the branches of set I,
B. the remaining nodes (one and only one branch of set II will lead to each of these nodes).
We start the construction by choosing an arbitrary node as the only member of set A, and by placing all branches that end in this node in set II. To start with, set I is empty. From then onwards we perform the following two steps repeatedly.
Step 1: The shortest branch of set II is removed from this set and added to set I. As a result, one node is transferred from set B to set A.
Step 2: Consider the branches leading from the node, which has just been transferred to set A, to the nodes that are still in set B. If the branch under construction is longer than the corresponding branch in set II, it is rejected; if it is shorter, it replaces the corresponding branch in set II, and the latter is rejected.
We then return to step 1 and repeat the process until sets II and B are empty. The branches in set I form the tree required.
doyle’s take on it:
1 A router initializes the Tree database by adding itself as the root. This entry shows the
router as its own neighbor, with a cost of 0.
2 All triples in the link state database describing links to the root router’s neighbors are
added to the Candidate database.
3 The cost from the root to each link in the Candidate database is calculated. The link
in the Candidate database with the lowest cost is moved to the Tree database. If two
or more links are an equally low cost from the root, choose one.
4 The Neighbor ID of the link just added to the Tree database is examined. With the
exception of any triple whose Neighbor ID is already in the Tree database, triples in the
link state database describing that router’s neighbors are added to the Candidate database.
5 If entries remain in the Candidate database, return to step 3. If the Candidate database is
empty, terminate the algorithm. At termination, a single Neighbor ID entry in the Tree
database should represent every router, and the shortest path tree is complete.