Need help understanding Link State Routing

Question

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.

So, in the beginning I have nodes that only know their neighbours and I want to build the LSP database – which represents the full network topology – which every node should know. Every node sends its neighbours the information about the link cost of links pointing to its neighbours and receives from its neighbours the information about the link cost of their conections to adjacent nodes, but how can a node get information about nodes connected to non-adjacent nodes, if the Link State Packet only brings information about adjacent connections and is only communicated to adjacent neighbours? Should the nodes forward the LSPs of other nodes, other than their own LSPs?

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!

Answer 1

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
IS-IS level 1 link-state 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
IS-IS level 1 link-state database:

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:
    Area address: 49.0276 (3)
    Speaks: IPV6
    Topology: ipv6 unicast
    Hostname: R1-1
    IPv6 address: 2001:db8::13
    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

IS-IS level 2 link-state database:

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.

Answer 2

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