<div dir="auto">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. <div dir="auto"><br></div><div dir="auto">I would not be surprised if there were optimizations that could be done on the code though</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, May 24, 2020, 4:41 AM yanhc519 <<a href="mailto:yanhc519@163.com">yanhc519@163.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

    

<div>
<div style="line-height:1.6;font-family:'\0082f9\0065b9','\005fae\008f6f\0096c5\009ed1','sans-serif'"><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">Hi all.</span></font></font></span><br><br><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">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*</span></font></font></span><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">log2(V)) where E is the number of edges and V is the number of vertices. </span></font></font></span><br><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">I have measured the running time of spf calculation in the embeded processor with small E and V, i.e. </span></font></font></span><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">E=1 and V=2.</span></font></font></span><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)"> The measured spf running time is 10 milliseconds.</span></font></font></span><br><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">My goal is to evaluate the spf running time in a large network e.g. </span></font></font></span><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">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 </span></font></font></span><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">computational complexity O(E*</span></font></font></span><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">log2(V)) and measurement in small network?</span></font></font></span><br><span style="background-color:rgb(255,255,255)"><font style="font-size:15px"><font style="color:rgb(36,39,41)"><span style="background-color:rgb(255,255,255)">Thanks in advance.</span></font></font></span><br><br><font style="color:rgb(0,0,0)">yan<br></font><br><br></div>
</div>
_______________________________________________<br>
frog mailing list<br>
<a href="mailto:frog@lists.frrouting.org" target="_blank" rel="noreferrer">frog@lists.frrouting.org</a><br>
<a href="https://lists.frrouting.org/listinfo/frog" rel="noreferrer noreferrer" target="_blank">https://lists.frrouting.org/listinfo/frog</a><br>
</blockquote></div>