Router :
It is a device that forwards
data packets between computer networks
Routing:
Routing
is the process of selecting paths in a network.
Routing Protocol:
The protocol which are used in routing
algorithms is called as routing protocol.
Routing
Algorithm:
The algorithm used for routing
is called by the name Routing algorithms.
Types of Routing
Algorithms
There are 2 types of routing algorithms.
1)Adaptive
2)Non Adaptive
Adaptive:
Change routes dynamically
Gather information at runtime
Nonadaptive:
Static
routes are downloaded at boot time
Link State
Rotuing
·
Also called shortest path first (SPF) forwarding
·
All
routers have tables which contain a representation of the entire network
topology
·
Each router creates a link state packet (LSP)
which contains names (e.g. network addresses) and cost to each of its
neighbours
·
The algorithm requires the following
information:
·
Link state database: List of all the latest LSPs from each router
on the network
·
Path: Tree structure storing previously computed
best paths
·
Data type for nodes: (ID, path cost, port)
·
Tent:
Tree structure storing paths currently being tested and compared
(tentative)
·
Forwarding database: Table storing all IDs that can be reached,
and the port to which messages should be sent
·
This is simply a reduced version of the ‘Path’,
which contains (destination,port) pairs
Dijkstra’s LSR Algorithm:
n Initially,
PATH is just a root containing (this router’s ID, 0, 0)
n For every node placed into path, N:
n For all neighbours M of node N:
n If M is not in TENT, add a node to TENT for M (use the
LSP for N to determine link cost)
n If M is in TENT already, and its cost is lower than an
existing entry for M, replace that entry with information from N’s LSP
n If M is in TENT already, but its cost is higher,
ignore N’s link to M
n Calculate the shortest route in TENT
n If the shortest route has lower cost than the route in
PATH, overwrite the route in PATH with the route in TENT
Example
Solution
Open Shortest Path First (OSPF)
Open Shortest Path First (OSPF) is a link state routing protocol (LSRP) that uses the Shortest Path First (SPF) network communication algorithm (Dijkstra's algorithm) to calculate the shortest connection path between known devices.
OSPF detects changes in the topology, such as link failures, very quickly and converges on a new loop-free routing structure within seconds. It computes the shortest path tree for each route using a method based on Dijkstra's algorithm, a shortest path first algorithm.
The link-state information is maintained on each router as a link-state database (LSDB) which is a tree-image of the entire network topology. Identical copies of the LSDB are periodically updated through flooding on all OSPF routers.
Packet Format
1 1 2 4 4 2 2 8 var
Version number |
Type |
Packet Length |
Router ID |
Area ID |
Checksum |
Authentication Type |
Authentication |
Data |
