# Need help understanding Link State Routing

I'm trying to fully understand the Link State Routing protocol since I want to code a program which creates a routing table for every node of a network, represented with a weighted graph. I know that to use Dijkstra's algorithm I have to know the full topology of the network.

I'll try to make an example: If I have node A connected to node B, node B connected to node C and node C connected to node D, how could A ever know about the existence of node D if the only information it gets is the Link State Packet from B, which tells “I'm connected to A and C”? Even after B knows that C is connected to D, B will keep telling A only its adjacent connections, so A will never know of any other nodes other than B (directly connected) and C (connected through B)

I know there's something I'm missing, any help will be greatly appreciated!

• I would suggest reading the RFCs, like RFC2328 , there's should be all information you need in...
– JFL
Commented Sep 11, 2015 at 10:37
• Did any answer help you? if so, you should accept the answer so that the question doesn't keep popping up forever, looking for an answer. Alternatively, you could provide and accept your own answer. Commented Aug 12, 2017 at 17:45

LSAs/LSPs (OSPF vs IS-IS speak) are flooded through the network. You are indeed correct that a LSP (I prefer ISIS) only contains information for adjacent nodes + certain IP reachability info from the node that sourced the LSP but flooding solves this and allows you to gain a full picture of the network.

You can look at the LSP DB in a router. Here's some output from a virtual environment I'm working with:

``````tsroot@R2-4> show isis database
LSP ID                      Sequence Checksum Lifetime Attributes
R1-1.00-00                      0x1e   0x6880    52429 L1
R1-2.00-00                     0x122   0x17c4    62130 L1
R1-3.00-00                     0x320   0xca73      542 L1
R1-4.00-00                     0x3b8   0x9e67      761 L1
R2-1.00-00                     0x26a   0x90cd    62131 L1 L2
R2-2.00-00                     0x398   0x9ea4    62130 L1 L2
R2-4.00-00                     0x3ce   0x8ecb      793 L1 L2 Attached
R2-5.00-00                     0x2b4   0xa3b0    62137 L1 L2
R2-6.00-00                     0x26b   0x78d3    62028 L1 L2
R1-5.00-00                     0x1a4   0x285f    62131 L1
R1-6.00-00                     0x1cc   0x6069    61984 L1
11 LSPs
``````

We can see that we have received LSPs from all other routers in this topology and obviously we also have our local information (R2-4).

It's possible to look in more detail of the LSP:

``````tsroot@R2-4> show isis database R1-1 extensive

R1-1.00-00 Sequence: 0x1e, Checksum: 0x6880, Lifetime: 52351 secs
IPV6 Unicast IS neighbor: R2-1.00          Metric:       30
Two-way fragment: R2-1.00-00, Two-way first fragment: R2-1.00-00
IPV6 Unicast IS neighbor: R2-2.00          Metric:       30
Two-way fragment: R2-2.00-00, Two-way first fragment: R2-2.00-00
V6 IPV6 Unicast prefix: 2001:db8::13/128   Metric:        0 Internal Up
V6 IPV6 Unicast prefix: 2001:db8:1:13:11::/112 Metric:       30 Internal Up
V6 IPV6 Unicast prefix: 2001:db8:1:13:12::/112 Metric:       30 Internal Up

Header: LSP ID: R1-1.00-00, Length: 156 bytes
Allocated length: 284 bytes, Router ID: 0.0.0.0
Remaining lifetime: 52351 secs, Level: 1, Interface: 330
Estimated free bytes: 257, Actual free bytes: 128
Aging timer expires in: 52351 secs
Protocols: IPv6

Packet: LSP ID: R1-1.00-00, Length: 156 bytes, Lifetime : 65531 secs
Checksum: 0x6880, Sequence: 0x1e, Attributes: 0x1 <L1>
NLPID: 0x83, Fixed length: 27 bytes, Version: 1, Sysid length: 0 bytes
Packet type: 18, Packet version: 1, Max area: 0

TLVs:
Speaks: IPV6
Topology: ipv6 unicast
Hostname: R1-1
IPV6 UnicastIS neighbor: R2-2.00, Metric: default 30
IPV6 UnicastIS neighbor: R2-1.00, Metric: default 30
IPV6 UnicastIPv6 prefix: 2001:db8::13/128 Metric 0 Up
IPV6 UnicastIPv6 prefix: 2001:db8:1:13:11::/112 Metric 30 Up
IPV6 UnicastIPv6 prefix: 2001:db8:1:13:12::/112 Metric 30 Up
No queued transmissions

tsroot@R2-4>
``````

And we can see that includes adjacency information with metric to reach those neighbours:

``````   IPV6 Unicast IS neighbor: R2-1.00          Metric:       30
IPV6 Unicast IS neighbor: R2-2.00          Metric:       30
``````

There's info about the directly connected IP prefixes:

``````   V6 IPV6 Unicast prefix: 2001:db8::13/128   Metric:        0 Internal Up
V6 IPV6 Unicast prefix: 2001:db8:1:13:11::/112 Metric:       30 Internal Up
V6 IPV6 Unicast prefix: 2001:db8:1:13:12::/112 Metric:       30 Internal Up
``````

From this information we can then compute the shortest path by starting the tree at our own node (R2-4). It's also possible to deduce loop free backup paths by rooting the tree at an adjacent node. This is called LFA (Loop Free Alternatives) and is a way of achieving IP FRR (Fast Re-Route).

The flooding of LSPs happens verbatim. Ie the LSP is not even interpreted before being flooded. It is therefore important that the size of an LSP is equal or smaller in size to the link in the network with the lowest MTU.

I think you mean LSA, not LSP. What you're missing is unique RIDs (Router IDs). If you look at a type 1 LSA in an OSPF LSDB (Link State Database) you will see that an LSA contains within it an RID and all adjacent nodes for that RID.

So in your example, node D advertises an LSA with all its adjacent neighbors and OSPF-enabled interfaces to C. C then advertises its own LSA plus node D's LSA to B etc.

So RIDs allow routers to uniquely identify other link-state routers in the same domain even if they're not directly adjacent

• LSP is valid when talking about IS-IS. Commented Sep 11, 2015 at 16:29
• I think that LSP/LSA (I'm not so savvy) only contains information about adjacent nodes: if not, then I think it is not that kind of packet. The question is much simpler: is it right that the LSP travels through the network? It should be, but I have to be sure. Commented Sep 11, 2015 at 23:12