Scribd
Upload
7 views5 pages

Link State and BGP Routing Algorithms

The document discusses link state routing algorithms, specifically Dijkstra's Shortest Path algorithm, which involves maintaining tentative and confirmed lists to determine the shortest path to neighbors. It also covers the Open Shortest Path First (OSPF) protocol, detailing message types and authentication methods. Additionally, it introduces the Border Gateway Protocol (BGP), the primary inter-domain routing protocol that uses a path-vector algorithm to manage network reachability across autonomous systems.

Uploaded by

saniyanoorfathima14907
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views5 pages

Link State and BGP Routing Algorithms

The document discusses link state routing algorithms, specifically Dijkstra's Shortest Path algorithm, which involves maintaining tentative and confirmed lists to determine the shortest path to neighbors. It also covers the Open Shortest Path First (OSPF) protocol, detailing message types and authentication methods. Additionally, it introduces the Border Gateway Protocol (BGP), the primary inter-domain routing protocol that uses a path-vector algorithm to manage network reachability across autonomous systems.

Uploaded by

saniyanoorfathima14907
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Link state routing algorithm

Explore the fundamental networking protocols that power modern


communication and data exchange, from routing algorithms to transport
layer protocols.
Link State Routing
Algorithm
Dijkstra's Shortest Path routing Algorithm

1. Each host maintains two lists, known as Tentative and Confirmed.


2. Initialize the Confirmed list with an entry for the Node (Cost = 0).
3. Node just added to the Confirmed list is called Next. Its LSP is
examined.
4. For each neighbor of Next, calculate the cost to reach each neighbor
as Cost (Node to Next) + Cost (Next to Neighbor).

(a) If Neighbor is neither in Confirmed nor in Tentative list, then add


(Neighbor, Cost, NextHop) to the Tentative list.

(b) If the Neighbor is in the Tentative list, and the Cost is less than the
existing cost, then replace the entry with (Neighbor, Cost, NextHop).

[Link] the Tentative list is empty then Stop, otherwise move the least cost
entry from the Tentative list to Confirmed list. Go to Step 2
Open Shortest Path First
(OSPF) Protocol
Version represents the current version, i.e., 2.

Type - represents the type (1-5) of OSPF message.

Type 1- "hello" message,

Type 2-request,

Type 3 - send

Type 4 acknowledge the receipt of link state messages,

Type 5 reserved

SourceAddr identifies the sender

Areald-32-bit identifier of the area in which the node is located

Checksum-16-bit Internet checksum

Authentication type-1 (simple password), 2 (cryptographic


authenticatic

Authentication - contains password or cryptographic checksum.


Path Vector Routing
Algorithm: Border Gateway
Protocol (BGP)
The Figure below shows a small internet with only five nodes.

Each source has created its own spanning tree that meets its policy.

The policy imposed by all sources is to use the minimum number of


nodes to reach a desti

The spanning tree selected by A and E is such that the communication


does not pass through middle node

Similarly, the spanning tree selected by B is such that the communication


does not pass thoug middle node.
Border Gateway
Protocol
The border gateway protocol version (BGP) is the only inter-
domain routin protocol used in the internet today

BGP4 is based on the path-vector algorithm. it provides


infrmation about the reachability of network on the internet

BGP views the internet as a set of autonomouse system


interconnected arbitarily

You might also like