On Mon, 18 Aug 2025 at 06:57, Ryan Hamel via NANOG <nanog@lists.nanog.org> wrote:
I was scrolling LinkedIn and came across a post that mentioned a research paper: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
TLDR: Dijkstra got defeated after 40 years. It will be interesting to see what convergence times will look like with this implemented.
I don't think it has practical implications for ISIS/OSPF networks, on a small network with under 300 nodes ISIS SPF costs like 25ms, flooding takes longer. I'm not sure how much cheaper this is, maybe I'm butchering this. If we assume 300 nodes and 900 edges. irb(main):002:0> (900+300) * Math.log(300) # (the paper claims 𝑂(𝑚+𝑛log 𝑛), while ISIS book by Abe Martey claims O(m log m) or O(m log n) for non-highly meshed (which is what I used to estimate in real life with good results, which is somewhat less than what the paper suggests for Djikstra) => 6844.538969587441 irb(main):001:0> 900 * 2/3*Math.log(300) => 3422.2694847937205 Absolutely insane improvement, if (doubtful) I'm not butchering this. But still largely immaterial in practice in this application, but I'm sure in many other Djikstra applications this kind of win can be meaningful. I don't understand the paper and can't tell what we are losing in terms of CPU time needed or DRAM needed, as the improvement makes assumptions about the environment which may not be true. -- ++ytti