[FROG] How to evaluate ospfv3 shortest path first running time for large networks?

[Donald Sharp]

I don't think we have any measurements here. I'd just run some tests with
different numbers of edges and vertexes.  Then I would extrapolate.

I would not be surprised if there were optimizations that could be done on
the code though

On Sun, May 24, 2020, 4:41 AM yanhc519 <yanhc519 at 163.com> wrote:

> Hi all.
>
> I am using ospfv3 routing in an embeded processor. The most time consuming
> part is the shortest path first(spf, Dijkstra) calculation in ospf6_spf.c.
> Since the spf calculation uses a priority queue, so the computational
> complexity is O(E*log2(V)) where E is the number of edges and V is the
> number of vertices.
> I have measured the running time of spf calculation in the embeded
> processor with small E and V, i.e. E=1 and V=2. The measured spf running
> time is 10 milliseconds.
> My goal is to evaluate the spf running time in a large network e.g. V=800
> and E=1600. Since deploy such a large network in conceptual design phase is
> not practical, so is there an estimation method using the computational
> complexity O(E*log2(V)) and measurement in small network?
> Thanks in advance.
>
> yan
>
>
> _______________________________________________
> frog mailing list
> frog at lists.frrouting.org
> https://lists.frrouting.org/listinfo/frog
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.frrouting.org/pipermail/frog/attachments/20200524/9e9fcafd/attachment.htm>