> > You stopped reading too soon. ;-P > > This paper does indeed work on directed graphs; the paragraph you cited > was laying down previous work upon which this paper builds. >
Sorry Matt, just seeing that you called this out as well. Apparently Gmail thought you were a dirty spammer. :) On Mon, Aug 18, 2025 at 2:22 PM Matthew Petach <[email protected]> wrote: > > You stopped reading too soon. ;-P > > This paper does indeed work on directed graphs; the paragraph you cited > was laying down previous work upon which this paper builds. > > However, the weakness in this paper lies further down in the heart of it > on page 4: > > > Total order of Paths. Like in many papers on shortest path algorithms, we > make the following assumption > for an easier presentation of our algorithm: > Assumption 2.1. All paths we obtain in this algorithm have different > lengths. > > > I don't know of many networks that choose link costs to ensure resulting > uniqueness of the cumulative cost through the path. Indeed, ECMP is taken > to be an assumption for most IGPs we use in the real world. > > It's a cute paper, and reading through the algorithms presented, it takes > an interesting hybrid approach to identifying 'pivot' vertices that are > more interesting to explore first to speed up pruning of uninteresting > edges; but it relies on the assumption given above that all paths have > different lengths so you can unambiguously prune vertices that are greater > than the current best path length. In our highly-ECMP-dependent networks, > that assumption falls flat on its face, and the pruning step fails. > > Note further that the data structure proposed in Lemma 3.3 at the bottom > of page 6 makes the assumption explicit, that updating the structure > involves only a single insertion or update at each iteration because path > lengths are unique, so trying to relax the uniqueness assumption would > involve tossing out their insertion-efficient storage structure as well. > > Interesting, but not really currently applicable to modern IP networks. > > Unlike what another old-timer might sometimes say, I do *not* encourage my > competitors to implement this algorithm in their routing hardware. ;-P > > Matt > > > > On Mon, Aug 18, 2025, 07:27 Tom Beecher via NANOG <[email protected]> > wrote: > >> > >> > TLDR: Dijkstra got defeated after 40 years. It will be interesting to >> see >> > what convergence times will look like with this implemented. >> >> >> Good case study of why you can't TLDR science. From the paper directly , >> emphasis on the last sentence mine : >> >> Dijkstra’s algorithm also produces an ordering of vertices by distances >> > from the source as a byproduct. A recent contribution by Haeupler, >> Hladík, >> > Rozhoň, Tarjan and Tětek [HHR+24] showed that Dijkstra’s algorithm is >> > optimal if we require the algorithm to output the order of vertices by >> > distances. If only the distances and not the ordering are required, a >> > recent result by Duan, Mao, Shu and Yin [DMSY23] provided an O(m √ log n >> > log log n)-time randomized SSSP algorithm for undirected graphs, better >> > than O(n log n) in sparse graphs. ***** However it remains to break >> such a >> > sorting barrier in directed graphs. ***** >> >> >> 1. Dijkstra wasn't 'defeated'. There have been many algorithms that >> outperformed Dijkstra's under specific cases. >> 2. OSPF and IS-IS are directed graphs. This algorithm outperforms Dijkstra >> on *undirected* graphs. >> >> >> On Sun, Aug 17, 2025 at 11:57 PM Ryan Hamel via NANOG < >> [email protected]> >> 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. >> > >> > Different formats of the same research paper: >> > >> > >> > * >> > https://arxiv.org/pdf/2504.17033 >> > * >> > https://dl.acm.org/doi/pdf/10.1145/3717823.3718179 >> > >> > Kind regards, >> > >> > Ryan Hamel >> > >> > _______________________________________________ >> > NANOG mailing list >> > >> > >> https://lists.nanog.org/archives/list/[email protected]/message/RPNTZTJEGQJ6WMI4AKOFUUOVFP4CP7AC/ >> > >> _______________________________________________ >> NANOG mailing list >> >> https://lists.nanog.org/archives/list/[email protected]/message/X56R5NAPCVAR4NSGFLWQ2UZB5ZQT4F5H/ > > _______________________________________________ NANOG mailing list https://lists.nanog.org/archives/list/[email protected]/message/DEU3HWVSF323SZLTJOCFZDSOSTEQCDCP/
