OSPF downheap LSA

In an OSPF topology, when a better path is found by OSPF, you may see a syslog message that uses the term "downheap" like so:

*Dec 20 01:24:37.637: OSPF-1 INTRA: Processing link 1, id 192.168.12.1, link data 192.168.12.1, type 2 
*Dec 20 01:24:37.637: OSPF-1 SPF : Add better path to LSA ID 192.168.12.1, gateway 192.168.12.1, dist 1 
*Dec 20 01:24:37.638: OSPF-1 INTRA: Putting LSA on the clist LSID 192.168.12.1, Type 2, Adv Rtr. 1.1.1.1 
*Dec 20 01:24:37.638: OSPF-1 SPF : Add path: next-hop 192.168.12.1, interface GigabitEthernet0/0 *Dec 20 01:24:37.638: OSPF-1 INTRA: Downheap [LSA](/lsa) ID 192.168.12.1, Type 2, Adv 1.1.1.1 on clist from index 1 to 1

The term downheap comes from heap data structure theory, a theory that involves how binary trees are manipulated. Because OSPF uses the Shortest Path First (SPF) methodology using Dijkstra’s algorithm, it uses heap data structure theory.

When the topology changes, the nodes that comprise the tree structure are modified. This modification must be reflected in the tree construct that OSPF has created. The terms “upheap” and “downheap” are used to refer to how nodes are kept in order when changes occur to the tree.

Upheap refers to the process by which the order of the nodes in the tree (heap order) is restored after a new node has been added.

Downheap refers to the process by which the order of the nodes in the tree (heap order) is restored after a node is removed.

Links:

https://forum.networklessons.com/t/ospf-spf-scheduling-and-throttling/1948/13?u=lagapides