Transcript Link State Routing – Computing New Routes

Network Layer – Routing 2
Dr. Sanjay P. Ahuja, Ph.D.
Fidelity National Financial Distinguished Professor of CIS
School of Computing, UNF
Adaptive or Dynamic Routing

There are three main strategies:

Isolated Adaptive: Each node has only local information and decision is
taken at each node (distributed control).

Distance Vector Routing: Each node receives information from adjacent
nodes and there is distributed control.

Link State Routing: Each node receives information from all other nodes
and there is distributed control.
Distance Vector Routing


Each node exchanges its delay vectors with its neighbor
nodes.
Based on this information a node tries to estimate the
delay situation throughout the network.

E.g. RIP of the Internet (originally used in the ARPANET)
Drawbacks:
Although this algorithm converges to the correct answer, it
may do so slowly. It reacts rapidly to good news, but
leisurely to bad news. This is also referred to as the Countto-Infinity problem.
Also, Distance Vector Routing does not scale well as the
delay vectors get too big as the network size increases.

Distance Vector Routing - Example
3
9
9
Distance Vector Routing
Measured delay from Node 1 to its neighbors are as follows:
Node 2: 2
Node 3: 5
Node 4: 1
Node 1’s routing table
Delay Vectors (D2,
Node 1’s routing table
before update
D3, D4 from neighbors) after update
(using Dijkstra’s algorithm)

Destination
node
Delay (Cost)
Next node
D2
D3
D4
1
0
-
2
3
1
2
2
2
0
3
2
3
5
3
3
0
4
1
4
2
5
6
3
6
8
3
Destination
node
Delay (Cost)
Next node
1
0
-
2
2
2
2
3
3
4
2
0
4
1
4
3
1
1
5
2
4
5
3
3
6
4
4
Drawback of Distance Vector Routing:
Count-to-Infinity Problem

Although this approach to routing converges to the correct answer, it
may do so slowly. It reacts rapidly to good news, but leisurely to bad
news.
Good news of a path
to A spreads quickly
Bad news of no path to A
is learned slowly
Link State Routing


1.
2.
3.
4.
5.
Distance Vector does not scale well as the delay vectors get too big as
the network size increases. It also experiences the Count-to-Infinity
Problem. Hence it has been replaced by Link State Routing on the
Internet.
Link State Routing has 5 parts. Each router must:
Discover its neighbors and learn their network addresses.
Send a HELLO packet to its neighbors. The response packet
contains the neighbor’s IP address.
Measure the delay or cost to each of its neighbors.
Send an ECHO packet to its neighbors and measure the RTT.
Delay = RTT/2.
Construct a packet (Link State Packet (LSP)) telling all it just learnt.
Send this packet to all other routers.
Compute the shortest path to every other router using Dijkstra’s
algorithm.
Link State Routing – Building LSP
packets

Building LSP packets

A router builds a LSP packet containing identity of sender,
sequence # and age of packet, and list of neighbors along with
delays to reach them.
Network
LSP for each node
Link State Routing – Distributing Link
State Packets (LSPs)

Flooding is used to ensure that all routers in the subnet receive LSP
packets.

Each LSP contains a sequence #. Receiving routers keep track of
<Source Router, Sequence #> pairs they see.

If a router crashes and comes back up later, it starts with sequence #
0. So the next packet will be rejected as being obsolete. To prevent
this, the age is included in the LSP.
Link State Routing – Computing New
Routes

Once a router has accumulated a full set of LSPs, it can construct the
entire subnet graph because every link is represented. Then it runs
Dijkstra’s algorithm to determine the shortest path to all other
routers.

E.g. of Link State Routing is Open Shortest Path First (OSPF) in the
Network Layer in the Internet.
Differences between Distance Vector
and Link State Routing
1.
The delay vector in Distance Vector Routing contains delay
information to get to all other routers but is sent only to its
neighboring nodes.
2.
The LSP in Link State Routing only contains delay information to
get to its neighboring nodes but is sent to out to all other
routers in the subnet.
3.
Link State Routing is more scalable because its LSPs only contain
delay information to the neighboring nodes rather than all other
routers.