From ospf-manet-bounces@ietf.org Fri Feb 02 13:34:15 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HD3El-0002xP-1C; Fri, 02 Feb 2007 13:34:15 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HD3Ej-0002qo-1T for ospf-manet@ietf.org; Fri, 02 Feb 2007 13:34:13 -0500 Received: from concorde.inria.fr ([192.93.2.39]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HD3Eg-0007cK-IG for ospf-manet@ietf.org; Fri, 02 Feb 2007 13:34:13 -0500 Received: from [192.168.112.191] (sphinx.lix.polytechnique.fr [129.104.11.1]) (authenticated bits=0) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l12IY2i4020490 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Fri, 2 Feb 2007 19:34:02 +0100 Message-ID: <45C38419.7070208@inria.fr> Date: Fri, 02 Feb 2007 19:34:01 +0100 From: Philippe Jacquet User-Agent: Thunderbird 1.5.0.9 (Macintosh/20061207) MIME-Version: 1.0 To: Richard Ogier Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> In-Reply-To: <45BD37DF.1050005@earthlink.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed X-Miltered: at concorde with ID 45C3841A.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by concorde.inria.fr id l12IY2i4020490 X-Spam-Score: 0.0 (/) X-Scan-Signature: 37af5f8fbf6f013c5b771388e24b09e7 Cc: ospf-manet@ietf.org X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Dear Richard, The simulation code about minCost LSA (in ospf6_neighbor.c, in int=20 ospf6_mdr_update_adv_neighbors(struct ospf6_interface *oi)) contains the=20 sequence of instructions: // Determine costs to j and k (as would be advertised in LSA) if (onj->state =3D=3D OSPF6_NEIGHBOR_FULL) costj =3D 10; else costj =3D 11; if (onk->state =3D=3D OSPF6_NEIGHBOR_FULL) costk =3D 10; else costk =3D 11; I understand that it implicitly gives priority to full neighbors.=20 Instead of artificially distorting link cost, could it not be an idea to=20 be more explicit in the draft by using the sentence (page 55-56 in=20 clause 5) b) and c): If HCM(j,i) + metric(i,k) < HCM(j,u) + LCM(u,k), or if u does not exist and HCM(j,i) + metric(i,k) < HCM(j,k), or if k is a full=20 neighbor, add k to the set of advertised neighbors. But of course it will not be possible to know about the adjacencies=20 between the other nodes (u,k) or (j,u), other than by specific=20 advertizement via a specific TLV in hellos. I also have difficulties to see how the option OSPF6_LSA_FULLNESS_MINHOP=20 (LSAFullness=3D1?) works. It seems that the link cost distortion causes t= o=20 advertize no more than the full neighbors (like in LSAFullness=3D0?) and=20 not the minCost path as specified in the MDR draft. It seems that=20 OSPF6_LSA_FULLNESS_MINHOP2PATHS (LSAFullness=3D2) is the right option tha= t=20 provides shortest path. Therefore when you run the code with option=20 LSAFullness=3D1, one would not get mincost LSA's -- is that correctly=20 understood? Philippe Richard Ogier a =E9crit : > Emmanuel, >=20 > Regarding your simulation results, it looks like using > MPR adjacency reduction does not reduce overhead much, > and based on the simulation results I presented recently, > MDR with adjacency reduction has much lower overhead. >=20 > I think you would have to make major changes to your draft > before it is competitive with MDR. For example, you will at > least have to select MPRs (and "path MPRs" for LSAs) to be more > stable, which has not yet been described in your draft. >=20 > The MDR draft does not need major changes, but I am making > changes to improve readability, to simplify the BMDR algorithm, > and other minor changes such as improving min-cost LSAs. > This does not change the core methods for flooding and adjacency > reduction, which have been stable for about two years. >=20 > My point was that, since MPR adjacency reduction is not scalable, > the main contributions of your draft are MPR LSA reduction > and multicast retransmitted LSAs (the latter of which is not > new and was considered in version 00 of the MDR draft), and > that these two contributions do not by themselves constitute > an OSPF extension, but are techniques that can be applied > to either ORs or MDRs. >=20 > I mentioned that I will experiment with multicast retransmitted > LSAs to see if they improve the performance of MDRs in some > scenarios, and if they do they can be included as an option. > This would be a minor change to the MDR draft. >=20 > After we have both finalized our drafts, we should continue > our discussion then, and perform a fair simulation comparison. > Until then, I suggest we take a break from this discussion. >=20 > Richard >=20 >=20 >=20 > Emmanuel Baccelli wrote: >=20 >> Dear Richard, >> >> We agree that there is no need to argue. The MPR-OSPF is a consistent >> extension of OSPFv3 that uses flooding reduction, topology reduction a= nd >> adjacency reduction based on MPR, with a stable specification ready fo= r >> experimental status. >> >> You suggest that you could introduce some changes in MDR, taking >> advantage of the experimental status. We do not think that it is neede= d >> to introduce the major changes you mentionned (such as including MPR >> topology reduction or multicast) since they are already featured in th= e >> MPR-OSPF extension. However, if you think MDR needs major changes, the= n >> MDR is not ready for experimental status. >> >> Emmanuel >> >> >> _______________________________________________ >> Ospf-manet mailing list >> Ospf-manet@ietf.org >> https://www1.ietf.org/mailman/listinfo/ospf-manet >> >=20 >=20 > _______________________________________________ > Ospf-manet mailing list > Ospf-manet@ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-manet >=20 >=20 _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Mon Feb 05 11:08:47 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HE6OX-0003vt-4F; Mon, 05 Feb 2007 11:08:41 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HE6OW-0003vo-Eb for ospf-manet@ietf.org; Mon, 05 Feb 2007 11:08:40 -0500 Received: from pop-knobcone.atl.sa.earthlink.net ([207.69.195.64]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HE6OV-00010u-6k for ospf-manet@ietf.org; Mon, 05 Feb 2007 11:08:40 -0500 Received: from dialup-4.246.93.156.dial1.sanjose1.level3.net ([4.246.93.156]) by pop-knobcone.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HE6OP-0003ti-00; Mon, 05 Feb 2007 11:08:35 -0500 Message-ID: <45C75684.5060107@earthlink.net> Date: Mon, 05 Feb 2007 08:08:36 -0800 From: Richard Ogier 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: Aniket Desai Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report References: <6.2.3.4.2.20070131171954.0284c1a8@mailserver.opnet.com> In-Reply-To: <6.2.3.4.2.20070131171954.0284c1a8@mailserver.opnet.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 538aad3a3c4f01d8b6a6477ca4248793 Cc: ospf-manet@ietf.org X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org > Hello, > > From the previous emails, it seemed that Dr. Ogier suggested the use > of simulations as a "tie breaker" to even administer a proposal to > experimental status. Simulations may not be the most accurate > representation of the reality to the last bit, but they provide > sufficient framework to cheaply evaluate and compare different > proposals against each other. I believe it should be possible to > design a series of parametric runs (changing node density, changing > mobility, changing network size, changing radio range etc etc.) to > extensively compare all the proposals against each other. All the > criticism about considering only a single/limited set of scenarios > gets nullified when one has conducted a parametric run, and I don't > see any way other than the simulations to do this. > > Thanks, > > Aniket Aniket, I agree that simulations should be a part of the evaluation process. Most people agreed at the last IETF meeting that simulations are important, so we already have consensus on this point. For example, if implementations show that all solutions perform about the same for 50 nodes in a number of scenarios, but simulations show that one scales much better to 100 or more nodes, then that is important evidence that should be considered, and could be used to "break a tie". Simulations are not perfect, but will have some inaccuracy. For example, if a simulation model is found to predict overhead with 25% accuracy (compared to a real implementation), and simulation results show that protocol A has 75% less overhead than protocol B, that is a significant result. It is interesting that Emmanuel is presenting results for at most 50 nodes, whereas it has already been shown that MDR is scalable to more than 100 nodes. 50-node networks are not very challenging, now that we can support 100 nodes. We need to simulate larger networks in order to stress the protocols and determine which protocols are really scalable. I ran some simulations with up to 100 nodes, using Emmanuel's latest code release. I will present these results in my next message. Richard _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Mon Feb 05 11:16:31 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HE6W7-000157-Aw; Mon, 05 Feb 2007 11:16:31 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HE6W6-000151-Qh for ospf-manet@ietf.org; Mon, 05 Feb 2007 11:16:30 -0500 Received: from pop-cowbird.atl.sa.earthlink.net ([207.69.195.68]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HE6W4-0002HL-GG for ospf-manet@ietf.org; Mon, 05 Feb 2007 11:16:30 -0500 Received: from dialup-4.246.93.156.dial1.sanjose1.level3.net ([4.246.93.156]) by pop-cowbird.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HE6W3-0002N4-00 for ospf-manet@ietf.org; Mon, 05 Feb 2007 11:16:27 -0500 Message-ID: <45C7585D.7060105@earthlink.net> Date: Mon, 05 Feb 2007 08:16:29 -0800 From: Richard Ogier 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 Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report References: <45C065EA.9040906@inria.fr> In-Reply-To: <45C065EA.9040906@inria.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 4b800b1eab964a31702fa68f1ff0e955 X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Emmanuel and all, I ran some simulations to compare INRIA's solution with MPR LSA reduction and adjacency reduction to MDR with min-cost LSAs and 1-connected adjacencies. I noticed that you used my database exchange optimization (by defining OSPF6_MANET_MDR_FLOOD_DD in Makefile). http://www.ietf.org/internet-drafts/draft-ietf-ospf-dbex-opt-00.txt I guess you forgot to mention this. This reduces DD overhead by about 50%, and therefore reduces the difference between INRIA and MDR overhead, but it does not change the fact that DD overhead increases much faster with MPR adjacency reduction than with MDR, as the number of nodes increases. So the difference in overhead is still quite dramatic in larger networks, as the results below show. I used your GTNetS code with MPR LSA reduction and MPR adjacency reduction. I used the following parameters for both INRIA and MDR, to agree with your report: Max velocity: 16 m/s Pause time: 1s HelloInterval: 2 s DeadInterval: 6 s RxmtInterval: 7 s MinLSInterval: 5 s MinLSArrival: 1 s AckInterval: 500 ms (Your report does not mention PushbackInterval, but it was set to 3500 msec in your perl file, so I used that value.) The database exchange summary list optimization was used with both INRIA and MDR. I ran simulations with 40, 60, 80, and 100 nodes, with range = 250 m. The results for 40 nodes agree with your graphs (for overhead and delivery ratio). The results are summarized below. MDR 40 nodes 60 nodes 80 nodes 100 nodes --- -------- -------- -------- -------- Total Overhead (kbps) 72.50 138.84 252.79 370.76 LSU overhead (kbps) 17.57 29.02 49.82 65.88 LS Ack overhead (kbps) 17.31 36.66 73.46 118.57 DD overhead (kbps) 10.50 21.52 38.97 54.60 Adjacencies/node 2.66 3.02 2.83 2.41 Adj changes/node/sec 0.05 0.04 0.05 0.04 Avg LSAs out of sync 0.48 0.35 0.30 0.24 Delivery ratio 0.939 0.941 0.935 0.938 INRIA 40 nodes 60 nodes 80 nodes 100 nodes ----- -------- -------- -------- -------- Total Overhead (kbps) 160.80 369.07 670.03 1174.08 (3 x MDR) 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 (10 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 about 10 times that of MDR, resulting in 3 times as much total overhead. But there seems to a problem (perhaps a bug) with INRIA's code, since INRIA has a much lower delivery ratio, and a much larger number of LSAs out of sync than MDR. Richard _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Tue Feb 06 13:21:00 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HEUw7-0000D1-RH; Tue, 06 Feb 2007 13:20:59 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HEUw6-0000Cu-El for ospf-manet@ietf.org; Tue, 06 Feb 2007 13:20:58 -0500 Received: from pop-borzoi.atl.sa.earthlink.net ([207.69.195.70]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HEUw5-00033L-6D for ospf-manet@ietf.org; Tue, 06 Feb 2007 13:20:58 -0500 Received: from dialup-4.245.102.66.dial1.sanjose1.level3.net ([4.245.102.66]) by pop-borzoi.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HEUw2-0007TU-00; Tue, 06 Feb 2007 13:20:55 -0500 Message-ID: <45C8C704.8020908@earthlink.net> Date: Tue, 06 Feb 2007 10:20:52 -0800 From: Richard Ogier 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: Philippe Jacquet Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> In-Reply-To: <45C38419.7070208@inria.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 5011df3e2a27abcc044eaa15befcaa87 Cc: ospf-manet@ietf.org X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Philippe, As I mentioned, the min-cost LSA algorithm will be modified in the next draft update, which may affect some of your comments, so I prefer that you comment on the updated version when it comes out. (I don't plan any MDR presentation at the Prague meeting, so the next draft update might not come until after the meeting.) Also note that the simulation results will not be affected significantly by modifying the min-cost LSA algorithm, since the LSU overhead will remain low. The main issue addressed by the simulations is the large overhead when MPR adjacency reduction is used. I address your comments below. Philippe Jacquet wrote: > Dear Richard, > > The simulation code about minCost LSA (in ospf6_neighbor.c, in int > ospf6_mdr_update_adv_neighbors(struct ospf6_interface *oi)) contains > the sequence of instructions: > > // Determine costs to j and k (as would be advertised in LSA) > if (onj->state == OSPF6_NEIGHBOR_FULL) costj = 10; > else costj = 11; > if (onk->state == OSPF6_NEIGHBOR_FULL) costk = 10; > else costk = 11; > > I understand that it implicitly gives priority to full neighbors. > Instead of artificially distorting link cost, could it not be an idea > to be more explicit in the draft by using the sentence (page 55-56 in > clause 5) b) and c): I don't agree that this artificially distorts link costs. I think it is a good idea to give fully synchronized neighbors a lower cost, simply because they are more likely to provide good routes. Actually, I would not fix the cost at 10 or 11, but would add 1 to the metric of any neighbor that is not Full. The draft does not specify how to select metrics, so the implementation is free to do this. > > If HCM(j,i) + metric(i,k) < HCM(j,u) + LCM(u,k), or if u does > not exist and HCM(j,i) + metric(i,k) < HCM(j,k), or if k is a full > neighbor, add k to the set of advertised neighbors. Step 4 already adds all Full neighbors to the set of advertised neighbors, so your modification has no effect. (The goal is that if node i advertises Full neighbor k, then node u should not advertise k if it is not Full.) > > But of course it will not be possible to know about the adjacencies > between the other nodes (u,k) or (j,u), other than by specific > advertizement via a specific TLV in hellos. That is why it is useful to add 1 to the metric of neighbors that are not Full. Actually, the DNL (dependent neighbor list) TLV implies information about other adjacencies, and the updated min-cost LSA algorithm may use this information. However, these details have a small effect on performance, compared to adjacency reduction. > > > I also have difficulties to see how the option > OSPF6_LSA_FULLNESS_MINHOP (LSAFullness=1?) works. It seems that the > link cost distortion causes to advertize no more than the full > neighbors (like in LSAFullness=0?) The use of 11 instead of 10 for a link metric would not affect the number of hops in computed paths, unless the path has at least 10 hops. (A 10-hop path with all links having metric 11 would have the same length as an 11-hop path with all links having metric 10.) Since Full neighbors alone do not provide min-hop paths, some non-Full neighbors will also have to be advertised. Maybe I do not understand your question. In any case, it might be better to wait for the updated min-cost LSA algorithm. Richard > and not the minCost path as specified in the MDR draft. It seems that > OSPF6_LSA_FULLNESS_MINHOP2PATHS (LSAFullness=2) is the right option > that provides shortest path. Therefore when you run the code with > option LSAFullness=1, one would not get mincost LSA's -- is that > correctly understood? > > Philippe > _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Fri Feb 09 05:57:04 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFTRA-00015O-6q; Fri, 09 Feb 2007 05:57:04 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFTR8-0000xg-AG for ospf-manet@ietf.org; Fri, 09 Feb 2007 05:57:02 -0500 Received: from discorde.inria.fr ([192.93.2.38]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HFTR6-0001cs-Ub for ospf-manet@ietf.org; Fri, 09 Feb 2007 05:57:02 -0500 Received: from [128.93.17.56] (monteverdi.inria.fr [128.93.17.56]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l19AuhnZ015850 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 9 Feb 2007 11:56:44 +0100 Message-ID: <45CC536A.5050507@inria.fr> Date: Fri, 09 Feb 2007 11:56:42 +0100 From: Emmanuel Baccelli User-Agent: Thunderbird 1.5.0.9 (Macintosh/20061207) MIME-Version: 1.0 To: ospf-manet@ietf.org Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 45CC536B.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam-Score: 0.0 (/) X-Scan-Signature: cf4fa59384e76e63313391b70cd0dd25 X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Dear Richard, Your simulation results are comparing apples and oranges. MPR-OSPF synchronizes each link that is advertized in LSAs so that routing loops are avoided, and advertizes enough links so that shortest paths can be derived. On the other hand, MDR provides much different link and path properties. For this reason, the quick overhead comparison you are making is not relevant. Moreover, we think it is futile to elaborate on your simulation results since we've been looking at your code and it is not apparent that it corresponds to what is described in the MDR draft. Emmanuel _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Fri Feb 09 10:52:27 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFY31-00072D-NM; Fri, 09 Feb 2007 10:52:27 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFY2z-00071w-JF for ospf-manet@ietf.org; Fri, 09 Feb 2007 10:52:25 -0500 Received: from concorde.inria.fr ([192.93.2.39]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HFY2y-0005vv-7t for ospf-manet@ietf.org; Fri, 09 Feb 2007 10:52:25 -0500 Received: from [128.93.62.246] (dhcp-rocq-246.inria.fr [128.93.62.246]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l19FqFVR006651 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Fri, 9 Feb 2007 16:52:16 +0100 Message-ID: <45CC98B1.8060907@inria.fr> Date: Fri, 09 Feb 2007 16:52:17 +0100 From: Philippe Jacquet User-Agent: Thunderbird 1.5.0.9 (Macintosh/20061207) MIME-Version: 1.0 To: Richard Ogier References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> In-Reply-To: <45C8C704.8020908@earthlink.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 45CC98AF.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam-Score: 0.0 (/) X-Scan-Signature: a7d6aff76b15f3f56fcb94490e1052e4 Cc: ospf-manet@ietf.org Subject: [Ospf-manet] 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Dear Richard, We have studied the MDR code and draft. 1. The algorithm described in the MDR draft does not provide the feature it claims: minimum cost paths in the routing table. Links are not guaranteed to be symmetrically advertized and, consequently, part of the LSAs will systematically be killed by backlink check. 2. Making a nodes LSA dependent of other nodes LSA is a source of circular dependancy. 3. The code for minCost LSA in the GTNet MDR-implementation does not implement the algorithm which is described in the MDR draft: For the option used in the simulations which you presented lately (LSAFullness=1), the code has three embedded loops that in the end make a node i to advertize a link to a node j if and only if i is the closest node to j. But this does not result in shortest path advertizements. 4. The GTNet MDR implementation artificially distorts link metrics as a way of expressing both the actual cost and the property (synchronized or not) of the link as one. This approach is, not specified in the MDR draft, so also on this point the GTNet MDR implementation and the MDR draft exhibit a significant discrepency. The preliminary conclusions are, therefore: - that the algorithms and the claims of the MDR draft do not correspond with each other; - that the MDR draft and the GTNet MDR implementation do not correspond with each other; and so: - that the simulation results presented from GTNet for the MDR-OSPF proposal correspond NEITHER to the MDR draft algorithms NOR to the properties claimed by the MDR draft. Sincerely, Philippe _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Fri Feb 09 14:55:21 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFbq4-000153-Tl; Fri, 09 Feb 2007 14:55:20 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFbq4-00014s-0b for ospf-manet@ietf.org; Fri, 09 Feb 2007 14:55:20 -0500 Received: from pop-cowbird.atl.sa.earthlink.net ([207.69.195.68]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HFbpy-0004qC-R9 for ospf-manet@ietf.org; Fri, 09 Feb 2007 14:55:19 -0500 Received: from dialup-4.245.97.53.dial1.sanjose1.level3.net ([4.245.97.53]) by pop-cowbird.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HFbpt-0007W4-00; Fri, 09 Feb 2007 14:55:10 -0500 Message-ID: <45CCD19B.9070604@earthlink.net> Date: Fri, 09 Feb 2007 11:55:07 -0800 From: Richard Ogier 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: philippe.jacquet@inria.fr References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr> In-Reply-To: <45CC98B1.8060907@inria.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 3a4bc66230659131057bb68ed51598f8 Cc: ospf-manet@ietf.org 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Philippe, As I mentioned, the MDR draft will be updated soon, and will include a modified algorithm for min-cost LSAs. So, PLEASE hold your criticisms of min-cost LSAs until you see the updated version! You are correct that the simulation results may be different with the updated min-cost LSA algorithm, so I will rerun the simulations once OSPF-MDR is updated. Hopefully, you will also have some improvements to MPR-OSPF by then (e.g., to improve the low delivery ratio). However, the largest contributor to overhead in MPR-OSPF is DD overhead, 10 times larger than MDR for 100 nodes, and this result is NOT affected by the choice of LSAs. I respond to your comments below. Philippe Jacquet wrote: > Dear Richard, > > We have studied the MDR code and draft. > > 1. The algorithm described in the MDR draft does not provide the > feature it claims: minimum cost paths in the routing table. Links are > not guaranteed to be symmetrically advertized and, consequently, part > of the LSAs will systematically be killed by backlink check. As I mentioned a few months ago, the min-cost LSA algorithm will be modified to ensure links are symmetrically advertised. The next draft update will include this modification. Once the min-cost LSA algorithm is modified, we can do another simulation comparison, so the LSU overhead can be compared fairly. Also, we can compare MPR-OSPF to OSPF-MDR, using path-MPR-based LSAs for both protocols. (Note that path-MPRs are not really MPRs, since they do not provide multipoint relaying.) This allows us to compare the two flooding approaches independently of the LSA algorithm. Note that OSPF-MDR can use either min-cost LSAs or path-MPR-based LSAs, so the LSA algorithm is decoupled from the flooding mechanism. > > 2. Making a nodes LSA dependent of other nodes LSA is a source of > circular dependancy. No. Node i decides not to advertise a link to neighbor j if neighbor u is already advertising j (and node i cannot provide a better path to j). There is nothing wrong with this. Maybe you are thinking about what happens if several routers decide to add j at the same time, which would result in redundant advertisements. This is one of the things that will be improved in the updated version of min-cost LSAs, using information from Hellos. > > > 3. The code for minCost LSA in the GTNet MDR-implementation does not > implement the algorithm which is described in the MDR draft: For the > option used in the simulations which you presented lately > (LSAFullness=1), the code has three embedded loops that in the end > make a node i to advertize a link to a node j if and only if i is the > closest node to j. But this does not result in shortest path > advertizements. The MDR draft states that min-cost routing is provided only if Hellos include metric information, which is optional (See the 4th paragraph of Appendix C.) Otherwise, we have min-hop routing if all metrics are equal, or metrics can be used to give preference to some links, e.g. to Full links. So we get something that is better than min-hop but not exactly min-cost. Anyway, the updated version of the min-cost LSA algorithm will always provide min-cost routing. Again, you are criticizing an old version of an algorithm that I have already said I plan to update. (Note that LSA reduction was not considered a goal until recently, so I did not focus on that until recently.) Also, the LSA algorithm is decoupled from the flooding mechanism. If we decide that path-MPR-based LSAs are better, then I would be happy to use them with OSPF-MDR. But my main point is that MPR-based adjacency reduction generates much more overhead than MDR-based adjacency reduction. Richard > > 4. The GTNet MDR implementation artificially distorts link metrics as > a way of expressing both the actual cost and the property > (synchronized or not) of the link as one. This approach is, not > specified in the MDR draft, so also on this point the GTNet MDR > implementation and the MDR draft exhibit a significant discrepency. > > The preliminary conclusions are, therefore: > > - that the algorithms and the claims of the MDR draft do not > correspond with each other; > > - that the MDR draft and the GTNet MDR implementation do not > correspond with each other; > > and so: > > - that the simulation results presented from GTNet for the MDR-OSPF > proposal correspond NEITHER to the MDR draft algorithms NOR to the > properties claimed by the MDR draft. > > Sincerely, > > Philippe > > _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Sat Feb 10 13:24:15 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFwtT-0004IB-Nt; Sat, 10 Feb 2007 13:24:15 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFwtS-0004Hz-1q for ospf-manet@ietf.org; Sat, 10 Feb 2007 13:24:14 -0500 Received: from pop-gadwall.atl.sa.earthlink.net ([207.69.195.61]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HFwtQ-0007Z5-9u for ospf-manet@ietf.org; Sat, 10 Feb 2007 13:24:14 -0500 Received: from dialup-4.246.93.209.dial1.sanjose1.level3.net ([4.246.93.209]) by pop-gadwall.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HFwtN-0000fg-00; Sat, 10 Feb 2007 13:24:09 -0500 Message-ID: <45CE0DC7.80707@earthlink.net> Date: Sat, 10 Feb 2007 10:24:07 -0800 From: Richard Ogier 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: Philippe Jacquet References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr> In-Reply-To: <45CC98B1.8060907@inria.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 8b30eb7682a596edff707698f4a80f7d Cc: ospf-manet@ietf.org 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Philippe, I didn't reply to the following comment, because I thought I already addressed it in my previous email. But I will add a few comments. > 4. The GTNet MDR implementation artificially distorts link metrics as > a way of expressing both the actual cost and the property > (synchronized or not) of the link as one. This approach is, not > specified in the MDR draft, so also on this point the GTNet MDR > implementation and the MDR draft exhibit a significant discrepency. I guess the word "artificial" is the opposite of "natural", and the use of such vague words has already been discussed. It is acceptable to allow the link metric to depend on link quality, as you know (since OLSR does this). Link quality can be measured in many ways. For example, if n consecutive Hellos have been received from the neighbor, the link metric can be decreased to represent good link quality. Similarly, if database exchange has been completed with the neighbor, so that its state becomes Full, this implies the link is likely to have better quality, so we can decrease the link metric slightly to prefer it over non-Full neighbors. Since you are bothered that this is not specified in the MDR draft, I can add something like the following to the next draft update: "The router MAY add a small penalty to the metric of links to neighbors that are not Full". Also, we can run simulations both with and without this technique, after the updated version of OSPF-MDR has been implemented in GTNetS. Richard _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Mon Feb 12 04:30:13 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HGXVl-0000Vj-07; Mon, 12 Feb 2007 04:30:13 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HGXVk-0000Vd-2M for ospf-manet@ietf.org; Mon, 12 Feb 2007 04:30:12 -0500 Received: from smtp1.bae.co.uk ([20.133.0.11]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HGXVh-0006v0-Ls for ospf-manet@ietf.org; Mon, 12 Feb 2007 04:30:12 -0500 Received: from smtpc.greenlnk.net (smtpc.greenlnk.net [10.15.160.220]) by smtp1.bae.co.uk (Switch-3.1.10/Switch-3.1.10) with ESMTP id l1C9TwFi002313 for ; Mon, 12 Feb 2007 09:29:58 GMT Received: from glkas0002.GREENLNK.NET (glkas0002.greenlnk.net [10.15.184.52]) by smtpc.greenlnk.net (Switch-3.1.9/Switch-3.1.9) with ESMTP id l1C9TvSC008818 for ; Mon, 12 Feb 2007 09:29:58 GMT Received: from glkms0002.GREENLNK.NET ([10.15.184.2]) by glkas0002.GREENLNK.NET with InterScan Message Security Suite; Mon, 12 Feb 2007 09:29:58 -0000 Received: from glkms2122.GREENLNK.NET ([10.15.184.26]) by glkms0002.GREENLNK.NET with Microsoft SMTPSVC(5.0.2195.6713); Mon, 12 Feb 2007 09:29:58 +0000 X-MimeOLE: Produced By Microsoft Exchange V6.0.6603.0 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: [Ospf-manet] Re: Regarding OSPF MDR Date: Mon, 12 Feb 2007 09:29:57 -0000 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: [Ospf-manet] Re: Regarding OSPF MDR Thread-Index: AcdNQMSb6xGi+m+0Q2ah/QTQMM0RTwBRty7g From: "Dearlove, Christopher \(UK\)" To: X-OriginalArrivalTime: 12 Feb 2007 09:29:58.0297 (UTC) FILETIME=[5CCF8090:01C74E88] X-Spam-Score: 0.0 (/) X-Scan-Signature: 93238566e09e6e262849b4f805833007 X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org From: Richard Ogier [mailto:rich.ogier@earthlink.net]=20 >It is acceptable to allow the link metric to depend on link >quality, as you know (since OLSR does this). If by OLSR you mean RFC 3626 (or the OLSRv2 draft) then, no, the link metric does not depend on link quality. Link quality may cause a link not to be used, but if a link is used then it has a metric of one. That isn't to say that this isn't a possible extension, but it's not in the actual specification of OLSR. Please note that I'm not saying anything for or against any of the proposals being addressed, just commenting on this one specific point. ******************************************************************** This email and any attachments are confidential to the intended recipient and may also be privileged. If you are not the intended recipient please delete it from your system and notify the sender. You should not copy it or use it for any purpose nor disclose or distribute its contents to any other person. ******************************************************************** _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Wed Feb 14 09:38:39 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HHLHL-0006wf-QZ; Wed, 14 Feb 2007 09:38:39 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HHLHL-0006wa-7O for ospf-manet@ietf.org; Wed, 14 Feb 2007 09:38:39 -0500 Received: from concorde.inria.fr ([192.93.2.39]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HHLHJ-0004S1-Ow for ospf-manet@ietf.org; Wed, 14 Feb 2007 09:38:39 -0500 Received: from [192.168.112.191] (sphinx.lix.polytechnique.fr [129.104.11.1]) (authenticated bits=0) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1EEbxux032467 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 14 Feb 2007 15:38:00 +0100 Message-ID: <45D31ECA.50007@inria.fr> Date: Wed, 14 Feb 2007 15:38:02 +0100 From: Philippe Jacquet User-Agent: Thunderbird 1.5.0.9 (Macintosh/20061207) MIME-Version: 1.0 To: Richard Ogier References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr> <45CCD19B.9070604@earthlink.net> In-Reply-To: <45CCD19B.9070604@earthlink.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed X-Miltered: at concorde with ID 45D31EC7.003 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by concorde.inria.fr id l1EEbxux032467 X-Spam-Score: 0.0 (/) X-Scan-Signature: 8f374d0786b25a451ef87d82c076f593 Cc: ospf-manet@ietf.org 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Dear Richard, In contrast to the claims of the MDR draft, the code (available on the=20 Boeing WWW-site and used for the simulations in the milcom06-paper) does=20 not provide min-hop path, regardless of backlink check, cost metric and=20 cost distortion. Since the LSA reduction in MDR is still not mature and certainly not=20 tested (since no code is available), it is misleading to advertise the=20 simulations with anything else but the full LSA option. Notice that I have not had time to check the MDR simulation code=20 thoroughly beyond minCost LSAs, so there may be other potential problems=20 and discrepancies with what is specified in the I-D elsewhere which I=20 have not yet detected. Sincerely, Philippe Richard Ogier a =E9crit : > Philippe, >=20 > As I mentioned, the MDR draft will be updated soon, and > will include a modified algorithm for min-cost LSAs. > So, PLEASE hold your criticisms of min-cost LSAs > until you see the updated version! >=20 > You are correct that the simulation results may > be different with the updated min-cost LSA algorithm, > so I will rerun the simulations once OSPF-MDR is updated. > Hopefully, you will also have some improvements to MPR-OSPF > by then (e.g., to improve the low delivery ratio). > However, the largest contributor to overhead in MPR-OSPF is > DD overhead, 10 times larger than MDR for 100 nodes, > and this result is NOT affected by the choice of LSAs. >=20 > I respond to your comments below. >=20 > Philippe Jacquet wrote: >=20 >> Dear Richard, >> >> We have studied the MDR code and draft. >> >> 1. The algorithm described in the MDR draft does not provide the=20 >> feature it claims: minimum cost paths in the routing table. Links are=20 >> not guaranteed to be symmetrically advertized and, consequently, part=20 >> of the LSAs will systematically be killed by backlink check. >=20 >=20 > As I mentioned a few months ago, the min-cost LSA algorithm > will be modified to ensure links are symmetrically advertised. > The next draft update will include this modification. >=20 > Once the min-cost LSA algorithm is modified, we can do another > simulation comparison, so the LSU overhead can be compared > fairly. Also, we can compare MPR-OSPF to OSPF-MDR, using > path-MPR-based LSAs for both protocols. > (Note that path-MPRs are not really MPRs, since they do > not provide multipoint relaying.) > This allows us to compare the two flooding > approaches independently of the LSA algorithm. > Note that OSPF-MDR can use either min-cost LSAs > or path-MPR-based LSAs, so the LSA algorithm is > decoupled from the flooding mechanism. >=20 >> >> 2. Making a nodes LSA dependent of other nodes LSA is a source of=20 >> circular dependancy. >=20 >=20 > No. Node i decides not to advertise a link to neighbor j if > neighbor u is already advertising j (and node i cannot provide > a better path to j). There is nothing wrong with this. > Maybe you are thinking about what happens if several routers > decide to add j at the same time, which would result in > redundant advertisements. This is one of the things that > will be improved in the updated version of min-cost LSAs, > using information from Hellos. >=20 >> >> >> 3. The code for minCost LSA in the GTNet MDR-implementation does not=20 >> implement the algorithm which is described in the MDR draft: For the=20 >> option used in the simulations which you presented lately=20 >> (LSAFullness=3D1), the code has three embedded loops that in the end=20 >> make a node i to advertize a link to a node j if and only if i is the=20 >> closest node to j. But this does not result in shortest path=20 >> advertizements. >=20 >=20 > The MDR draft states that min-cost routing is provided only if Hellos > include metric information, which is optional (See the 4th paragraph > of Appendix C.) Otherwise, we have min-hop routing if all metrics > are equal, or metrics can be used to give preference to some links, > e.g. to Full links. So we get something that is better > than min-hop but not exactly min-cost. Anyway, the updated > version of the min-cost LSA algorithm will always provide > min-cost routing. Again, you are criticizing an old version of > an algorithm that I have already said I plan to update. > (Note that LSA reduction was not considered a goal until > recently, so I did not focus on that until recently.) >=20 > Also, the LSA algorithm is decoupled from the flooding mechanism. > If we decide that path-MPR-based LSAs are better, then I would > be happy to use them with OSPF-MDR. > But my main point is that MPR-based adjacency reduction generates > much more overhead than MDR-based adjacency reduction. >=20 > Richard >=20 >> >> 4. The GTNet MDR implementation artificially distorts link metrics as=20 >> a way of expressing both the actual cost and the property=20 >> (synchronized or not) of the link as one. This approach is, not=20 >> specified in the MDR draft, so also on this point the GTNet MDR=20 >> implementation and the MDR draft exhibit a significant discrepency. >> >> The preliminary conclusions are, therefore: >> >> - that the algorithms and the claims of the MDR draft do not >> correspond with each other; >> >> - that the MDR draft and the GTNet MDR implementation do not >> correspond with each other; >> >> and so: >> >> - that the simulation results presented from GTNet for the MDR-OSPF >> proposal correspond NEITHER to the MDR draft algorithms NOR to the >> properties claimed by the MDR draft. >> >> Sincerely, >> >> Philippe >> >> >=20 >=20 _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Thu Feb 15 15:07:22 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HHmsw-0004Bv-2s; Thu, 15 Feb 2007 15:07:18 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HHmsu-0004AX-1W for ospf-manet@ietf.org; Thu, 15 Feb 2007 15:07:16 -0500 Received: from pop-knobcone.atl.sa.earthlink.net ([207.69.195.64]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HHmss-0004bR-P0 for ospf-manet@ietf.org; Thu, 15 Feb 2007 15:07:16 -0500 Received: from dialup-4.245.99.6.dial1.sanjose1.level3.net ([4.245.99.6]) by pop-knobcone.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HHmsq-0001T7-00; Thu, 15 Feb 2007 15:07:12 -0500 Message-ID: <45D4BD6A.3000009@earthlink.net> Date: Thu, 15 Feb 2007 12:07:06 -0800 From: Richard Ogier 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: Philippe Jacquet References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr> <45CCD19B.9070604@earthlink.net> <45D31ECA.50007@inria.fr> In-Reply-To: <45D31ECA.50007@inria.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 14582b0692e7f70ce7111d04db3781c8 Cc: ospf-manet@ietf.org 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Philippe, Philippe Jacquet wrote: > Dear Richard, > > In contrast to the claims of the MDR draft, the code (available on the > Boeing WWW-site and used for the simulations in the milcom06-paper) > does not provide min-hop path, regardless of backlink check, cost > metric and cost distortion. It is because of the backlink check that it does not provide min-hop paths, since the old min-cost LSA algorithm did not advertise neighbors symmetrically. (Note that min-COST routing would require Hellos to advertise neighbor costs, which is an option not implemented in GTNetS.) As I pointed out, INRIA's original code for MPR-OSPF did not even perform a backlink check (but has now been corrected). Frankly, I think it would be better if we could omit the backlink check, but that would not be compatible with legacy OSPF. The cost "distortion" is simply a small penalty to favor the use of synchronized links, and does not affect the hop length for paths less than 10 hops. Also, this penalty is optional. The updated min-cost LSA problem (to be announced soon), will advertise neighbors symmetrically and will always provide min-cost paths. > > Since the LSA reduction in MDR is still not mature and certainly not > tested (since no code is available), it is misleading to advertise the > simulations with anything else but the full LSA option. I don't agree. For example, one can use the "minimal LSA" option with MDR, which allows only synchronized links to be used for routing. This does not provide min-hop or min-cost routing, but some applications may be willing to trade off path optimality to achieve much lower overhead. Also, I am sure you would not object if MDR uses path-MPR-based LSAs. I plan to compare path-MPR-based LSAs to the updated min-cost LSA algorithm, and I would be happy to use whichever method turns out to perform better. You are focusing on LSAs, which are decoupled from flooding and adjacency reduction in OSPF-MDR. You are right that my simulation results did not provide a fair comparison of LSU overhead, but they *did* provide a fair comparison of synchronization (DD) overhead, since the choice of LSAs have no effect on DD overhead (assuming that each router originates an LSA). I plan to compare the following three protocols: 1. MPR-OSPF (with path-MPR-based LSAs) 2. OSPF-MDR with path-MPR-based LSAs 3. OSPF-MDR with the updated min-cost LSA algorithm. Comparing 1 and 2 will allow the flooding and adjacency reduction methods to be compared independently of the choice of LSAs. Comparing 2 and 3 will determine which LSA algorithm performs better with OSPF-MDR. Also, we can try using multicast LSA retransmissions with OSPF-MDR. For fairness, any technique that is used with one protocol and that can be used to improve the performance of the other protocol, should be used by both protocols. In order for MPR-OSPF to provide min-cost paths (based on metrics), you will have to select "path MPRs" and advertise these and link costs in Hellos, along with MPRs. Your Appendix C describes a Path MPR Selection Heuristic, which is not implemented in GTNetS. So I guess we are both experimenting with LSA algorithms that are not yet mature. That is fine, since the need for LSA reduction was not considered a goal until relatively recently. That is why Cisco's OR/SP drafts do not specify an algorithm for LSA reduction. Richard P.S. BTW, the min-cost LSA algorithm could be called "path-MPR-source-based LSAs". I.e., a router selects MPR sources (equivalent to MPR selectors) instead of MPRs. But I think using the term MPR in both cases is inappropriate, since path-MPRs are not used for multipoint relaying. I prefer the more generic term "selected advertised neighbors". _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Mon Feb 19 12:36:29 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HJCRB-00036r-L9; Mon, 19 Feb 2007 12:36:29 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HJCRA-00036j-J0 for ospf-manet@ietf.org; Mon, 19 Feb 2007 12:36:28 -0500 Received: from pop-cowbird.atl.sa.earthlink.net ([207.69.195.68]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HJCR8-0005g7-AL for ospf-manet@ietf.org; Mon, 19 Feb 2007 12:36:28 -0500 Received: from dialup-4.245.103.179.dial1.sanjose1.level3.net ([4.245.103.179]) by pop-cowbird.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HJCQy-0000ha-00; Mon, 19 Feb 2007 12:36:17 -0500 Message-ID: <45D9E011.1010600@earthlink.net> Date: Mon, 19 Feb 2007 09:36:17 -0800 From: Richard Ogier 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: Philippe Jacquet References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr> <45CCD19B.9070604@earthlink.net> <45D31ECA.50007@inria.fr> <45D4BD6A.3000009@earthlink.net> In-Reply-To: <45D4BD6A.3000009@earthlink.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 41c17b4b16d1eedaa8395c26e9a251c4 Cc: ospf-manet@ietf.org Subject: [Ospf-manet] Regarding MPR-OSPF X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org Philippe, I noticed two possible problems with your GTNetS code for MPR-OSPF. The first one regards the following code in need_adjacency(): #ifdef OSPF6_MANET_MPR_ADJ_REDUC_OSPF_MPR if (on->ospf6_if->synchNode) return 1; if (ospf6_lookup_relay_selector(on->ospf6_if, on->router_id)) return 1; else return 0; #endif //OSPF6_MANET_MPR_ADJ_REDUC_OSPF_MPR The above code code says that the router forms an adjacency with a neighbor only if the router is a synch node or the neighbor is an MPR selector. This can cause unidirectional adjacencies, as explained below. (A similar problem with the OSPF-MDR code was discovered and corrected over a year ago.) Suppose node i forms an adjacency with node j either because node i is a synch node or node j is an MPR selector. Suppose that node j later misses a few Hellos from node i, so that node j changes the state of neighbor i to Down and then to 2-Way, without sending a Hello that indicates neighbor i is Down (or perhaps node j sends one such Hello that is not received by i). Node j does not consider node i adjacent, since j is not a synch node and i is not an MPR selector. (The need_adjacency() condition is not symmetric.) Also suppose that node i never misses any Hellos from node j (or misses only one Hello from j). Then node i will still think node j is fully adjacent, even though node j does not consider node i adjacent. Thus, a unidirectional adjacency can exist. Therefore, it is necessary for the need_adjacency condition to be symmetric. I.e., node i should consider node j adjacent if and only if node j considers node i adjacent. More specifically, need_adjacency() should also return true if the neighbor is a synch node or an MPR. (Notice that the need_adjacency condition is symmetric in RFC 2328.) The other problem I noticed regards the selection of synch routers. Your GTNetS code does not agree with your draft. In your code, only one router in the entire network (area) is selected as a synch node, i.e., the one with the largest RID. This does not agree with your draft, which says: > A router decides it is a synch router if and only if: > o the router is a wireless router that has the highest willingness > in its neighborhood (in case of ties, the router that also has the > greatest ID is elected). Also, what if the router with the largest (willingness, RID) is not a MANET router? And what if you have multiple MANET interfaces, in addition to non-MANET interfaces? I think you are safer if you consider only MANET neighbors on a given interface when deciding whether a router is a synch router (as in your draft). I realize that this would result in more adjacencies and more overhead, but it may also improve robustness. Also, if you select only a single synch router (as in your code), it is not clear how to extend this to multiple interfaces or networks that include non-MANET interfaces. Please let us know which rule you plan to use for selecting synch routers. Richard _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet From ospf-manet-bounces@ietf.org Tue Feb 20 14:53:56 2007 Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HJb3k-00089o-DQ; Tue, 20 Feb 2007 14:53:56 -0500 Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HJb3j-00089i-3p for ospf-manet@ietf.org; Tue, 20 Feb 2007 14:53:55 -0500 Received: from mailgate-internal1.sri.com ([128.18.84.103]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1HJb3h-0007Lz-Jd for ospf-manet@ietf.org; Tue, 20 Feb 2007 14:53:55 -0500 Received: from localhost (HELO mailgate-internal1.SRI.COM) (127.0.0.1) by mailgate-internal1.sri.com with SMTP; 20 Feb 2007 19:53:46 -0000 Received: from mercury.esd.sri.com ([128.18.26.21]) by mailgate-internal1.SRI.COM (SMSSMTP 4.1.11.41) with SMTP id M2007022011534614502 for ; Tue, 20 Feb 2007 11:53:46 -0800 Received: from earthlink.net ([128.18.40.95]) by mercury.esd.sri.com (iPlanet Messaging Server 5.2 HotFix 1.25 (built Mar 3 2004)) with ESMTP id <0JDS001U61XTGT@mercury.esd.sri.com> for ospf-manet@ietf.org; Tue, 20 Feb 2007 11:53:53 -0800 (PST) Date: Tue, 20 Feb 2007 11:53:38 -0800 From: Richard Ogier To: ospf-manet@ietf.org Message-id: <45DB51C2.9050109@earthlink.net> MIME-version: 1.0 Content-type: text/plain; charset=ISO-8859-1; format=flowed Content-transfer-encoding: 7BIT X-Accept-Language: en-us, en User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Spam-Score: 0.0 (/) X-Scan-Signature: 538aad3a3c4f01d8b6a6477ca4248793 Subject: [Ospf-manet] LSA reduction X-BeenThere: ospf-manet@ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions of OSPFv3 extensions supporting MANET List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ospf-manet-bounces@ietf.org All, Since there has been recent focus on LSA reduction, I want to give some background and explain what the MDR draft specifies regarding LSA reduction. First, as stated in Section 9.2, the MDR draft allows any choice of LSAs subject to the following two requirements: (1) A router MUST include all Full neighbors in its router-LSA. (2) A router MUST NOT include any non-routable neighbors in its LSA. Any LSA choice satisfying the above requirements is therefore compliant with the MDR draft (including the LSA methods implemented in GTNetS whether or not they provide shortest paths). This allows much flexibility in the choice of neighbors to advertise in LSAs. When several design team members were planning to proceed with a standards-track draft based on MDRs (last year), there was agreement that we should keep LSAs flexible, and that specific LSA choices/algorithms would be the subject of future work. Although the MDR draft described some choices for LSAs (minimal LSAs, min-cost LSAs, MDR full LSAs, and full LSAs), these were only suggested choices, not requirements. These specific methods (except for the extreme cases of minimal LSAs and full LSAs) were not going to be included in the planned standards-track draft, and are not going to be included in the experimental draft. The recent focus on LSA reduction, and on providing minimum-cost routing, is therefore a topic that was considered future work by many of us (and certainly not the main focus of the OSPF-MANET work). I think now is a good time to do this "future" work. INRIA has already made some progress in this area, and a method for LSA reduction will soon be decided for OSPF-MDR. One of the questions that needs to be answered is the following: Q: Should the OSPF extension be *required* to always provide minimum-cost routing, or should suboptimal routing be allowed as an option in order to reduce overhead? In any case, the MDR draft will describe a method for LSA reduction that provides minimum-cost routing. I am currently experimenting with a few candidate methods and one of them will be included in the next revision of the MDR draft. Richard _______________________________________________ Ospf-manet mailing list Ospf-manet@ietf.org https://www1.ietf.org/mailman/listinfo/ospf-manet