
<html>

<head>

    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

</head>

<body>

<div style="line-height:1.6;font-family:'苹方','微软雅黑','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>

</body>

</html>