[Ospf-manet] Re: Regarding OSPF MDR
Richard Ogier <rich.ogier@earthlink.net> Mon, 05 March 2007 16:45 UTC
Return-path: <ospf-manet-bounces@ietf.org>
Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HOGJh-0007L5-Cj; Mon, 05 Mar 2007 11:45:41 -0500
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HOGJf-0007Ky-OW for ospf-manet@ietf.org; Mon, 05 Mar 2007 11:45:39 -0500
Received: from pop-savannah.atl.sa.earthlink.net ([207.69.195.69]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HOGJR-0005af-0P for ospf-manet@ietf.org; Mon, 05 Mar 2007 11:45:39 -0500
Received: from dialup-4.245.100.190.dial1.sanjose1.level3.net ([4.245.100.190]) by pop-savannah.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HOGJO-000103-00 for ospf-manet@ietf.org; Mon, 05 Mar 2007 11:45:23 -0500
Message-ID: <45EC4923.2000600@earthlink.net>
Date: Mon, 05 Mar 2007 08:45:23 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: ospf-manet@ietf.org
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 3f3e54d3c03ed638c06aa9fa6861237e
Subject: [Ospf-manet] Re: Regarding OSPF MDR
X-BeenThere: ospf-manet@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Discussions of OSPFv3 extensions supporting MANET <ospf-manet.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-manet>, <mailto:ospf-manet-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/ospf-manet>
List-Post: <mailto:ospf-manet@ietf.org>
List-Help: <mailto:ospf-manet-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-manet>, <mailto:ospf-manet-request@ietf.org?subject=subscribe>
Errors-To: ospf-manet-bounces@ietf.org
All, I ran some simulations using the modified min-cost LSA algorithm that is described in the updated MDR draft draft-ogier-manet-ospf-extension-09.txt (submitted yesterday). I announced plans to modify the min-cost LSA algorithm a few months ago, so this update is not in response to Philippe's recent comments regarding the old version. However, the new min-cost LSA algorithm does address some of Philippe's recent comments, for example: o Neighbor advertisements are symmetric: if a neighbor j advertises router i, then router i advertises neighbor j. o The updated min-cost LSA algorithm uses only information from Hellos received from neighbors, and no longer uses LSAs from neighboring routers. There is nothing wrong with using LSAs, except that using both Hellos and LSAs adds complexity, so this was done to keep the algorithm simple. o All links have the same cost; no penalty is added to the cost of links to neighbors that are not fully synchronized. This is not really a change, since routers still have the option of adding such as penalty, but I wanted to avoid any possible claims of unfairness. One criticism that Philippe might still have is that the algorithm requires O(d^3) time if run from scratch. However, it requires only O(d^2) time for a single topology change, so I think this is acceptable, since a router rarely needs to run the algorithm from scratch. I am still open to the possibility of using LSA reduction based on the "path-MPR" approach, since this can indeed reduce the size of LSAs as Philippe claims. However, based on the results for delivery ratio presented below, my main concern is that the path-MPR approach might not be as robust (possible reasons are given below). For the simulations, I used INRIA's GTNetS code with MPR LSA reduction and MPR adjacency reduction. I used the following parameters for both INRIA and MDR, to agree with INRIA's report. Both protocols also used the database exchange summary list optimization. Max velocity: 16 m/s Pause time: 1s HelloInterval: 2 s DeadInterval: 6 s RxmtInterval: 7 s MinLSInterval: 5 s MinLSArrival: 1 s As I mentioned previously, in INRIA's code, only the router with the largest RID in the network is a synch router. This does not agree with draft-baccelli-ospf-mpr-ext-02.txt, which says a router is a synch router if it has the largest (willingness, RID) in its neighborhood. The updated ospf6d directory and Makefile for OSPF-MDR can be found at home.earthlink.net/~ogier/ospf6d_mdr.tar.gz home.earthlink.net/~ogier/Makefile (All CFLAGS involving MPRs are commented out in the Makefile, since they might interfere with the operation of OSPF-MDR.) I ran simulations with 40, 60, 80, and 100 nodes, with range = 250 m. The results are summarized below, and detailed results for 100 nodes are given at the end of the message. MDR 40 nodes 60 nodes 80 nodes 100 nodes --- -------- -------- -------- -------- Total Overhead (kbps) 114.45 235.20 397.86 611.34 LSU overhead (kbps) 38.42 67.78 106.46 149.76 LS Ack overhead (kbps) 37.09 91.62 157.23 266.15 DD overhead (kbps) 10.06 21.14 39.37 57.58 Adjacencies/node 2.67 2.92 2.87 2.38 Adj changes/node/sec 0.04 0.04 0.05 0.04 Avg LSAs out of sync 0.81 0.69 0.43 0.43 Delivery ratio 0.931 0.934 0.936 0.934 INRIA 40 nodes 60 nodes 80 nodes 100 nodes ----- -------- -------- -------- -------- Total Overhead (kbps) 160.80 369.07 670.03 1174.08 LSU overhead (kbps) 27.97 58.66 100.02 177.27 LS Ack overhead (kbps) 49.15 109.55 183.28 294.12 DD overhead (kbps) 51.21 138.09 277.72 537.95 (9 x MDR) Adjacencies/node 16.37 21.08 26.49 31.78 Adj changes/node/sec 0.25 0.29 0.34 0.42 (10 x MDR) Avg LSAs out of sync 1.79 1.78 1.61 1.66 Delivery ratio 0.849 0.845 0.867 0.844 For 100 nodes, INRIA's DD overhead is 9.34 times that of MDR, resulting in almost 2 times as much total overhead. Also, INRIA's solution has a much lower delivery ratio (.844 versus .934 for 100 nodes). I don't know if this is a bug, but if not, my best guess is that this results from a combination of advertising barely enough links (no redundancy) and a longer delay to update LSAs following a link failure (due to the delay required to update and report MPRs as has been discussed). So, even though OSPF-MDR advertises more neighbors in LSAs, maybe these larger LSAs are necessary for robustness. The overhead for unicast LSUs is very low for MDR (13.65 kbps for 100 nodes), indicating that it will not help much to use multicast LSA retransmissions in MDR. In large networks, MDR's largest overhead component is LS Ack overhead, but this will be reduced to 0 if the non-ackable LSA option is used, at the cost of some additional multicast LSU transmissions. I plan to experiment with this option. Richard ------------------------------ Detailed results for 100 nodes MDR: ./random_waypoint_manet-opt seed=1 num_nodes=100 pktrate=10 wireless_interface=2 wireless_flooding=2 velocity=16 radio_range=250 pause_time=1 HelloInterval=2 RxmtInterval=7 DeadInterval=6 AckInterval=2000 BackupWaitInterval=500 TwoHopRefresh=3 AdjConnectivity=1 LSAFullness=1 start_time=1800 stop_time=2700 Neighbor statistics (at physical layer): -------------------------------------------------- Number of nodes: 100 Neighbor threshold distance (m): 250.00 Average neighbor density (neighbors/# of nodes): 0.65 Average neighbor changes/time (changes/sec/node): 0.84 OSPFv3 Statistics | Packets Bytes Kbps ---------------------------------------------------- Hello | 45000 15462092 137.44 LSAck | 43579 29941584 266.15 LSR | 664 46104 0.41 DBDESC | 9130 6478252 57.58 LSU | 53945 16848024 149.76 LSUfld | 47795 15312504 136.11 LSUuni | 6150 1535520 13.65 LSUcol | 38 15236 0.14 LSUrxmt | 5234 1205800 10.72 LSUdbex | 693 275356 2.45 LSUstale| 185 39128 0.35 | Total | 152318 68776056 611.34 OSPF Network Characteristics -------------------------------------------------- OSPF 2way_neighbors/node: 64.35 OSPF 2way_neighbor_changes/node/sec: 1.37 avg_sec/OSPF 2way neighbor_life: 102.29 OSPF adjacencies/node: 2.38 OSPF adjacency_changes/node/sec: 0.04 avg_LSAsOutSync: 0.43 Secs per router-LSA origination: 5.62 Router-LSA hopcount/Router-LSA installs: 2.33 Route changes/node/sec: 54.98 Accumulated adjacencies/node: 0.08 Flooding Statistics -------------------------------------------------- relaysel/node: 3.61 avg_sec/relaysel_life: 44.42 suppressed_LSAs: 1413794 relay_flood_LSAs: 91878 nonrelay_flood_LSAs: 5151 Topology Reduction Statistics -------------------------------------------------- Advertized neighbors: 112786 Total FULL neighbors: 1002857 User Traffic Analysis -------------------------------------------------- UDP sends: 8897 pkts, 604996 bytes UDP receives: 8311 pkts, 565148 bytes UDP forwards: 3191 pkts, 216988 bytes Delivery Ratio: 0.934 -------------------------------------------------- INRIA: ./random_waypoint_manet-opt seed=1 num_nodes=100 pktrate=10 wireless_interface=2 wireless_flooding=1 TopoReduc velocity=16 pause_time=1 radio_range=250 HelloInterval=2 RxmtInterval=7 DeadInterval=6 PushbackInterval=3500 AckInterval=500 MinLSInterval=5 start_time=1800 stop_time=2700 Neighbor statistics (at physical layer): -------------------------------------------------- Number of nodes: 100 Neighbor threshold distance (m): 250.00 Average neighbor density (neighbors/# of nodes): 0.65 Average neighbor changes/time (changes/sec/node): 0.84 OSPFv3 Statistics | Packets Bytes Kbps ---------------------------------------------------- Hello | 45000 15352104 136.46 LSAck | 111118 33088368 294.12 LSR | 38618 3180936 28.27 DBDESC | 77256 60519168 537.95 LSU | 102987 19943140 177.27 LSUfld | 40608 5252344 46.69 LSUuni | 62379 14690796 130.58 LSUcol | 20 6344 0.06 LSUrxmt | 0 0 0.00 LSUdbex | 38402 12007948 106.74 LSUstale| 23957 2676504 23.79 | Total | 374979 132083716 1174.08 OSPF Network Characteristics -------------------------------------------------- OSPF 2way_neighbors/node: 65.42 OSPF 2way_neighbor_changes/node/sec: 0.87 avg_sec/OSPF 2way neighbor_life: 163.41 OSPF adjacencies/node: 31.78 OSPF adjacency_changes/node/sec: 0.42 avg_LSAsOutSync: 1.66 Secs per router-LSA origination: 5.46 Router-LSA hopcount/Router-LSA installs: 1.92 Route changes/node/sec: 20.26 Accumulated adjacencies/node: 5.17 Sync Node changes: 0.00 Flooding Statistics -------------------------------------------------- relaysel/node: 1.99 avg_sec/relaysel_life: 7.08 suppressed_LSAs: 0 relay_flood_LSAs: 44823 nonrelay_flood_LSAs: 0 relay_flood_LSAs retransmissions: 4905 Neighborhood Statistics -------------------------------------------------- Hello received: 2617968 Inactivity calls: 35125 Topology Reduction Statistics -------------------------------------------------- Advertized neighbors: 51408 Total FULL neighbors: 1099248 User Traffic Analysis -------------------------------------------------- UDP sends: 8897 pkts, 604996 bytes UDP receives: 7510 pkts, 510680 bytes UDP forwards: 2183 pkts, 148444 bytes Delivery Ratio: 0.844 -------------------------------------------------- _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet
- RE: [Ospf-manet] Re: Regarding OSPF MDR Dearlove, Christopher (UK)
- [Ospf-manet] Re: Regarding OSPF MDR Richard Ogier