Routing Protocols Overview / Path determination

Routing Protocols Overview

Path determination 

6.3.1
This page will explain how a router determines the path of a packet from one data link to another. The router uses two basic functions:

• A path determination function
• A switching function

Path determination occurs at the network layer. The path determination function enables a router to evaluate the paths to a destination and to establish the preferred way to handle a packet. The router uses the routing table to determine the best path and then uses the switching function to forward the packet. -
The switching function is the internal process used by a router to accept a packet on one interface and forward it to a second interface on the same router. A key responsibility of the switching function of the router is to encapsulate packets in the appropriate frame type for the next data link.
Figure illustrates how routers use addressing for these routing and switching functions. The router uses the network portion of the address to make path selections to pass the packet to the next router along the path.
The next page will describe the commands that are used to configure a routing protocol.

Link-state routing protocol features

Link-state routing protocol features 

6.2.6

The other basic algorithm that is used for routing is the link-state algorithm. This page will explain how the link-state algorithm works. The link-state algorithm is also known as Dijkstra's algorithm or as the shortest path first (SPF) algorithm. The link-state routing algorithm maintains a complex database of topology information. The distance vector algorithm has nonspecific information about distant networks and no knowledge of distant routers. The link-state routing algorithm maintains full knowledge of distant routers and how they interconnect. Link-state routing uses the following features: Link-state advertisement (LSA) - a small packet of routing information that is sent between routers Topological database - a collection of information gathered from LSAs SPF algorithm - a calculation performed on the database that results in the SPF tree Routing table - a list of the known paths and interfaces

Network discovery processes for link state routing

When routers exchange LSAs, they begin with directly connected networks for which they have information. Each router constructs a topological database that consists of all the exchanged LSAs. The SPF algorithm computes network reachability. The router constructs this logical topology as a tree, with itself as the root. This topology consists of all possible paths to each network in the link-state protocol internetwork. The router then uses SPF to sort these paths. The router lists the best paths and the interfaces to these destination networks in the routing table. It also maintains other databases of topology elements and status details. The first router that learns of a link-state topology change forwards the information so that all other routers can use it for updates. Common routing information is sent to all routers in the internetwork. To achieve convergence, each router learns about its neighbor routers. This includes the name of each neighbor router, the interface status, and the cost of the link to the neighbor. The router constructs an LSA packet that lists this information along with new neighbors, changes in link costs, and links that are no longer valid. The LSA packet is then sent out so that all other routers receive it. When a router receives an LSA, it updates the routing table with the most recent information. The accumulated data is used to create a map of the internetwork and the SPF algorithm is used to calculate the shortest path to other networks. Each time an LSA packet causes a change to the link-state database, SPF recalculates the best paths and updates the routing table. There are three main concerns related to link-state protocols: Processor overhead Memory requirements Bandwidth consumption Routers that use link-state protocols require more memory and process more data than routers that use distance vector routing protocols. Link-state routers need enough memory to hold all of the information from the various databases, the topology tree, and the routing table. Initial link-state packet flooding consumes bandwidth. In the initial discovery process, all routers that use link-state routing protocols send LSA packets to all other routers. This action floods the internetwork and temporarily reduces the bandwidth available for routed traffic that carries user data. After this initial flooding, link-state routing protocols generally require minimal bandwidth to send infrequent or event-triggered LSA packets that reflect topology changes. This page concludes this lesson. The next lesson will provide an overview of routing protocols. The first page explains how a router performs path determination.

Distance vector routing protocol features

Distance vector routing protocol features 
6.2.5
This page will explain how the distance vector routing protocol is used.
The distance vector routing algorithm passes periodic copies of a routing table from router to router. These regular updates between routers communicate topology changes. The distance vector routing algorithm is also known as the Bellman-Ford algorithm.
Each router receives a routing table from its directly connected neighbor routers. Router B receives information from Router A. Router B adds a distance vector number, such as a number of hops. This number increases the distance vector. Then Router B passes this new routing table to its other neighbor, Router C. This same step-by-step process occurs in all directions between neighbor routers.
The algorithm eventually accumulates network distances so that it can maintain a database of network topology information. However, the distance vector algorithm does not allow a router to know the exact topology of an internetwork since each router only sees its neighbor routers.
Each router that uses distance vector routing first identifies its neighbors. The interface that leads to each directly connected network has a distance of 0. As the distance vector discovery process proceeds, routers discover the best path to destination networks based on the information they receive from each neighbor. Router A learns about other networks based on the information that it receives from Router B. Each of the other network entries in the routing table has an accumulated distance vector to show how far away that network is in a given direction.
Routing table updates occur when the topology changes. As with the network discovery process, topology change updates proceed step-by-step from router to router. Distance vector algorithms call for each router to send its entire routing table to each of its adjacent neighbors. The routing tables include information about the total path cost as defined by its metric and the logical address of the first router on the path to each network contained in the table.
An analogy of distance vector could be the signs found at a highway intersection. A sign points toward a destination and indicates the distance to the destination. Further down the highway, another sign points toward the destination, but now the distance is shorter. As long as the distance is shorter, the traffic is on the best path.
The next page will describe the link-state routing algorithm.