This table contains the learned networks and
associated ports for those networks. Routers use routing
protocols to manage information received from other routers,
information learned from the configuration of its own
interfaces, along with manually configured routes.The routing
protocol learns all available routes, places the best routes
into the routing table, and removes routes when they are no
longer valid. The router uses the information in the routing
table to forward routed protocol packets. The routing algorithm
is fundamental to dynamic routing. Whenever the topology of a
network changes because of growth, reconfiguration, or failure,
the network knowledgebase must also change. The network
knowledgebase needs to reflect an accurate consistent view of
the new topology. When all routers in an internetwork are
operating with the same knowledge, the internetwork is said to
have converged. Fast convergence is desirable because it
reduces the period of time in which routers would continue to
make incorrect routing decisions. Autonomous systems (AS)
provide the division of the global internetwork into smaller
and more manageable networks. Each AS has its own set of rules
and policies and an AS number that will uniquely distinguish it
from other autonomous systems throughout the world. Web
Links Introduction to Routing Protocols
http://www.cisco.com/networkers/ nw00/pres/ 2204.pdf
Content 6.2 Dynamic Routing Overview
6.2.4 Identifying the classes of routing protocols
Most routing algorithms can be classified into one of two
categories: - distance vector
- link-state
The distance vector routing approach determines the
direction (vector) and distance to any link in the
internetwork. The link-state approach, also called shortest
path first, recreates the exact topology of the entire
internetwork. Web Links Routing Algorithms
http://www.broadband-help.com/ guestarticles/ routingalg/
Algorithm.htm
Content 6.2 Dynamic
Routing Overview 6.2.5 Distance vector routing
protocol features Distance vector routing algorithms pass
periodic copies of a routing table from router to router. These
regular updates between routers communicate topology changes.
Distance vector based routing algorithms are also known as
Bellman-Ford algorithms.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), which 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,
distance vector algorithms do not allow a router to know the
exact topology of an internetwork as each router only sees its
neighbor routers. Each router that uses distance vector routing
begins by identifying its own neighbors. The interface that
leads to each directly connected network is shown as having a
distance of 0. As the distance vector network 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 towards 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 following the best path. Web Links Routing
Protocols - Distance Vector http://www.firewall.cx/
index.php?c=distance_vector
Content 6.2
Dynamic Routing Overview 6.2.6 Link-state
routing protocol features The second basic algorithm used
for routing is the link-state algorithm. Link-state algorithms
are also known as Dijkstras algorithm or as SPF (shortest path
first) algorithms. Link-state routing algorithms maintain a
complex database of topology information. The distance vector
algorithm has nonspecific information about distant networks
and no knowledge of distant routers. A link-state routing
algorithm maintains full knowledge of distant routers and how
they interconnect.Link-state routing uses:
- Link-state advertisements (LSAs) – A link-state
advertisement (LSA) is a small packet of routing information
that is sent between routers.
- Topological database
– A topological database is a collection of information
gathered from LSAs.
- SPF algorithm – The
shortest path first (SPF) algorithm is a calculation performed
on the database resulting in the SPF tree.
- Routing
tables – A list of the known paths and interfaces.
Network discovery processes for link state
routing
LSAs are exchanged between routers starting
with directly connected networks for which they have direct
information. Each router in parallel with the others constructs
a topological database consisting 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, consisting of all possible paths to each network in the
link-state protocol internetwork. It then sorts these paths
Shortest Path First (SPF). 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 router that first becomes aware of a
link-state topology change forwards the information so that all
other routers can use it for updates. This involves sending
common routing information to all routers in the internetwork.
To achieve convergence, each router keeps track of its neighbor
routers, the router name, 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 the
router receives an LSA, the database is updated with the most
recent information and computes a map of the internetwork using
the accumulated data and calculates the shortest path to other
networks using the SPF algorithm. Each time an LSA packet
causes a change to the link-state database, SPF recalculates
the best paths and updates the routing table. Link-state
concerns: - Processor overhead
- Memory
requirements
- Bandwidth Consumption
Routers
running link-state protocols require more memory and perform
more processing than distance vector routing protocols. Routers
must have sufficient memory to be able to hold all the
information from the various databases, the topology tree, and
the routing table. Initial link-state packet flooding consumes
bandwidth. During the initial discovery process, all routers
using link-state routing protocols send LSA packets to all
other routers. This action floods the internetwork and
temporarily reduces bandwidth available for routed traffic
carrying user data. After this initial flooding, link-state
routing protocols generally require only minimal bandwidth to