From mailman-bounces@ietf.org Wed Dec 1 05:58:34 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA12710 for ; Wed, 1 Dec 2004 05:58:34 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CZSHF-0005NZ-Eo for ospf-wireless-design-archive@ietf.org; Wed, 01 Dec 2004 06:04:05 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CZRhC-0006W0-FC for ospf-wireless-design-archive@ietf.org; Wed, 01 Dec 2004 05:26:50 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Subject: lists.ietf.org mailing list memberships reminder From: mailman-owner@ietf.org To: ospf-wireless-design-archive@ietf.org X-No-Archive: yes Message-ID: Date: Wed, 01 Dec 2004 05:05:07 -0500 Precedence: bulk X-BeenThere: mailman@lists.ietf.org X-Mailman-Version: 2.1.5 List-Id: Mailman site list X-List-Administrivia: yes Sender: mailman-bounces@ietf.org Errors-To: mailman-bounces@ietf.org X-Spam-Score: 0.3 (/) X-Scan-Signature: 3e15cc4fdc61d7bce84032741d11c8e5 Content-Transfer-Encoding: 7bit This is a reminder, sent out once a month, about your lists.ietf.org mailing list memberships. It includes your subscription info and how to use it to change it or unsubscribe from a list. You can visit the URLs to change your membership status or configuration, including unsubscribing, setting digest-style delivery or disabling delivery altogether (e.g., for a vacation), and so on. In addition to the URL interfaces, you can also use email to make such changes. For more info, send a message to the '-request' address of the list (for example, mailman-request@lists.ietf.org) containing just the word 'help' in the message body, and an email message will be sent to you with instructions. ********************************************************************** NOTE WELL: Any submission to the IETF intended by the Contributor for publication as all or part of an IETF Internet-Draft or RFC and any statement made within the context of an IETF activity is considered an "IETF Contribution". Such statements include oral statements in IETF sessions, as well as written and electronic communications made at any time or place, which are addressed to: o the IETF plenary session, o any IETF working group or portion thereof, o the IESG, or any member thereof on behalf of the IESG, o the IAB or any member thereof on behalf of the IAB, o any IETF mailing list, including the IETF list itself, any working group or design team list, or any other list functioning under IETF auspices, o the RFC Editor or the Internet-Drafts function All IETF Contributions are subject to the rules of RFC 3667 and RFC 3668. Statements made outside of an IETF session, mailing list or other function, that are clearly not intended to be input to an IETF activity, group or function, are not IETF Contributions in the context of this notice. Please consult RFC 3667 for details. ******************************************************************************* If you have questions, problems, comments, etc, send them to mailman-owner@lists.ietf.org. Thanks! Passwords for ospf-wireless-design-archive@ietf.org: List Password // URL ---- -------- ospf-wireless-design@lists.ietf.org uxefev https://www1.ietf.org/mailman/options/ospf-wireless-design/ospf-wireless-design-archive%40ietf.org From ospf-wireless-design-bounces@ietf.org Mon Dec 20 13:25:56 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA21105; Mon, 20 Dec 2004 13:25:55 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgSNb-0007vQ-BO; Mon, 20 Dec 2004 13:35:36 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgSBH-00029C-LG; Mon, 20 Dec 2004 13:22:51 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgSA5-0001qK-G0 for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 13:21:37 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA20879 for ; Mon, 20 Dec 2004 13:21:34 -0500 (EST) Received: from rtp-iport-1.cisco.com ([64.102.122.148]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgSJN-0007pO-LI for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 13:31:14 -0500 Received: from rtp-core-2.cisco.com (64.102.124.13) by rtp-iport-1.cisco.com with ESMTP; 20 Dec 2004 13:29:53 -0500 X-BrightmailFiltered: true X-Brightmail-Tracker: AAAAAA== Received: from mchandra-u10.cisco.com (mchandra-u10.cisco.com [64.102.48.252]) by rtp-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id iBKIL29E013825; Mon, 20 Dec 2004 13:21:03 -0500 (EST) Received: (mchandra@localhost) by mchandra-u10.cisco.com (8.11.2/CISCO.WS.1.2) id iBKIL2V11040; Mon, 20 Dec 2004 13:21:02 -0500 (EST) Date: Mon, 20 Dec 2004 13:21:02 -0500 From: "Madhavi W. Chandra" To: ospf-wireless-design@ietf.org Message-ID: <20041220182102.GC11017@cisco.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4i X-Spam-Score: 0.0 (/) X-Scan-Signature: 79899194edc4f33a41f49410777972f8 Subject: [Ospf-wireless-design] Tao Lin paper X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: 9182cfff02fae4f1b6e9349e01d62f32 Hi All, I'm hoping one of you can shed some light on the Tao Lin paper, section III-D. In this paper, I'm assuming that the Willingness parameter for MPRs is the same, so it doesn't come into play in the MPR computation. And as the paper says, MPR_Coverage=1, so there are no redundant relays in the set. But, why is the 'modified' OLSR set so much smaller than the MPR set? Put another way, which nodes would be included in the MPR set that wouldn't be included in the modified-OLSR set, especially since the MPR set does an overall pruning at the end of its selection algorithm. Thanks! -Madhavi _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 16:40:27 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA12199; Mon, 20 Dec 2004 16:40:27 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgVPr-00067y-8b; Mon, 20 Dec 2004 16:50:08 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgUyh-0002zF-8o; Mon, 20 Dec 2004 16:22:03 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgUiY-0000HI-Oj for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 16:05:22 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA04484 for ; Mon, 20 Dec 2004 16:05:20 -0500 (EST) Received: from blv-smtpout-01.boeing.com ([130.76.32.69]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgUrs-0003Sl-Ny for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 16:15:01 -0500 Received: from stl-av-01.boeing.com ([192.76.190.6]) by blv-smtpout-01.boeing.com (8.9.2.MG.10092003/8.8.5-M2) with ESMTP id NAA26914; Mon, 20 Dec 2004 13:03:53 -0800 (PST) Received: from XCH-NWBH-02.nw.nos.boeing.com (localhost [127.0.0.1]) by stl-av-01.boeing.com (8.11.3/8.11.3/MBS-AV-LDAP-01) with ESMTP id iBKL3ps07598; Mon, 20 Dec 2004 15:03:52 -0600 (CST) Received: from XCH-NW-27.nw.nos.boeing.com ([192.48.4.101]) by XCH-NWBH-02.nw.nos.boeing.com with Microsoft SMTPSVC(6.0.3790.211); Mon, 20 Dec 2004 13:03:45 -0800 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="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: FW: [Ospf-wireless-design] Tao Lin paper Date: Mon, 20 Dec 2004 13:03:44 -0800 Message-ID: <6938661A6EDA8A4EA8D1419BCE46F24C04522A0A@xch-nw-27.nw.nos.boeing.com> Thread-Topic: [Ospf-wireless-design] Tao Lin paper Thread-Index: AcTmxP26i8gzHkurTYG/cTwMMvG4/QAEdpIA From: "Henderson, Thomas R" To: "Tao Lin" X-OriginalArrivalTime: 20 Dec 2004 21:03:45.0011 (UTC) FILETIME=[6467FC30:01C4E6D7] X-Spam-Score: 0.0 (/) X-Scan-Signature: bb8f917bb6b8da28fc948aeffb74aa17 Content-Transfer-Encoding: quoted-printable Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: 7baded97d9887f7a0c7e8a33c2e3ea1b Content-Transfer-Encoding: quoted-printable I have forwarded this to Tao Lin, who has agreed to participate in our discussions on this topic. =20 -----Original Message----- From: Madhavi W. Chandra [mailto:mchandra@cisco.com] Sent: Monday, December 20, 2004 10:21 AM To: ospf-wireless-design@ietf.org Subject: [Ospf-wireless-design] Tao Lin paper Hi All, I'm hoping one of you can shed some light on the Tao Lin paper, section III-D. In this paper, I'm assuming that the Willingness parameter for MPRs is the same, so it doesn't come into play in the MPR computation. And as the paper says, MPR_Coverage=3D1, so there are no redundant relays in the set. But, why is the 'modified' OLSR set so much smaller than the=20 MPR set? Put another way, which nodes would be included in the MPR set that wouldn't be included in the modified-OLSR set, especially since the MPR set does an overall pruning at the end of its=20 selection algorithm. Thanks! -Madhavi _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 17:04:36 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA16200; Mon, 20 Dec 2004 17:04:35 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgVnE-0007UZ-Hb; Mon, 20 Dec 2004 17:14:17 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgVHX-0007fi-59; Mon, 20 Dec 2004 16:41:31 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgV6B-0008QB-Vj for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 16:29:48 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA10192 for ; Mon, 20 Dec 2004 16:29:45 -0500 (EST) Received: from pop-a065d14.pas.sa.earthlink.net ([207.217.121.252]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgVFW-0005RA-Ca for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 16:39:26 -0500 Received: from dialup-4.243.137.218.dial1.sanfrancisco1.level3.net ([4.243.137.218] helo=earthlink.net) by pop-a065d14.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1CgV68-0003aG-00; Mon, 20 Dec 2004 13:29:44 -0800 Message-ID: <41C74405.4040802@earthlink.net> Date: Mon, 20 Dec 2004 13:28:37 -0800 From: Richard Ogier User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202) X-Accept-Language: en-us MIME-Version: 1.0 To: "Madhavi W. Chandra" Subject: Re: [Ospf-wireless-design] Tao Lin paper References: <20041220182102.GC11017@cisco.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Scan-Signature: 82c9bddb247d9ba4471160a9a865a5f3 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.1 (/) X-Scan-Signature: 02ec665d00de228c50c93ed6b5e4fc1a Content-Transfer-Encoding: 7bit > Madhavi W. Chandra wrote: > >Hi All, > >I'm hoping one of you can shed some light on the Tao Lin paper, >section III-D. > >In this paper, I'm assuming that the Willingness parameter for >MPRs is the same, so it doesn't come into play in the MPR >computation. And as the paper says, MPR_Coverage=1, so there are >no redundant relays in the set. > >But, why is the 'modified' OLSR set so much smaller than the >MPR set? Put another way, which nodes would be included in the >MPR set that wouldn't be included in the modified-OLSR set, especially >since the MPR set does an overall pruning at the end of its >selection algorithm. > >Thanks! >-Madhavi > Madhavi, From Lin's description of OLSR: "The RNS for a source node is the MPR set of that node, combined with the MPR sets of nodes in the MPR set of that source node, and so on until this RNS covers all the nodes in the network." It looks like Lin is assuming that a node always forwards an LSA that is received from an MPR selector, even if the same LSA was previously received from a non-MPR selector, as long as the node has not previously *forwarded* the same LSA. As has been discussed on the OSPF list, this is not very efficient. A node only needs to forward an LSA when its *first* (non-duplicate) reception is from an MPR selector (except in some rare cases that can be handled by having non-MPR nodes retransmit the LSA when an ACK is not heard). I think OLSR does it the efficient way. Thus, Lin's RNS (relay node set) is probably larger than the set of nodes that actually forward the LSA when forwarding is done efficiently. Another possible advantage of Lin's CDS is that nodes with the smallest degree are preferred (with tie broken by node ID). Since all neighbors agree on this degree, there is more agreement among neighbors regarding the selection of CDS nodes. Whereas in OLSR each node selects MPRs independently, so that the total number of MPRs is likely to be larger than the total number of CDS nodes. Richard _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 17:12:14 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA17629; Mon, 20 Dec 2004 17:12:13 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgVud-0007o9-Lc; Mon, 20 Dec 2004 17:21:55 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgVg1-0008R8-Gs; Mon, 20 Dec 2004 17:06:49 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgVQO-0002ET-46 for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 16:50:40 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA13987 for ; Mon, 20 Dec 2004 16:50:37 -0500 (EST) Received: from pop-a065d19.pas.sa.earthlink.net ([207.217.121.253]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgVZi-0006hD-Tc for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 17:00:19 -0500 Received: from dialup-4.243.137.218.dial1.sanfrancisco1.level3.net ([4.243.137.218] helo=earthlink.net) by pop-a065d19.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1CgVQI-000162-00; Mon, 20 Dec 2004 13:50:34 -0800 Message-ID: <41C748E7.8090509@earthlink.net> Date: Mon, 20 Dec 2004 13:49:27 -0800 From: Richard Ogier User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202) X-Accept-Language: en-us MIME-Version: 1.0 To: "Henderson, Thomas R" Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper References: <6938661A6EDA8A4EA8D1419BCE46F24C04522A0A@xch-nw-27.nw.nos.boeing.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Scan-Signature: bdc523f9a54890b8a30dd6fd53d5d024 Content-Transfer-Encoding: 7bit Cc: Tao Lin , ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.1 (/) X-Scan-Signature: 3002fc2e661cd7f114cb6bae92fe88f1 Content-Transfer-Encoding: 7bit Henderson, Thomas R wrote: >I have forwarded this to Tao Lin, who has agreed to participate >in our discussions on this topic. > In that case, I will repeat my message so Tao can see it. Tao, Please let me know if you agree or disagree. Madhavi, From Lin's description of OLSR: "The RNS for a source node is the MPR set of that node, combined with the MPR sets of nodes in the MPR set of that source node, and so on until this RNS covers all the nodes in the network." It looks like Lin is assuming that a node always forwards an LSA that is received from an MPR selector, even if the same LSA was previously received from a non-MPR selector, as long as the node has not previously *forwarded* the same LSA. As has been discussed on the OSPF list, this is not very efficient. A node only needs to forward an LSA when its *first* (non-duplicate) reception is from an MPR selector (except in some rare cases that can be handled by having non-MPR nodes retransmit the LSA when an ACK is not heard). I think OLSR does it the efficient way. Thus, Lin's RNS (relay node set) is probably larger than the set of nodes that actually forward the LSA when forwarding is done efficiently. Another possible advantage of Lin's CDS is that nodes with the smallest degree are preferred (with tie broken by node ID). Since all neighbors agree on this degree, there is more agreement among neighbors regarding the selection of CDS nodes. Whereas in OLSR each node selects MPRs independently, so that the total number of MPRs is likely to be larger than the total number of CDS nodes. Richard > > >-----Original Message----- >From: Madhavi W. Chandra [mailto:mchandra@cisco.com] >Sent: Monday, December 20, 2004 10:21 AM >To: ospf-wireless-design@ietf.org >Subject: [Ospf-wireless-design] Tao Lin paper > > >Hi All, > >I'm hoping one of you can shed some light on the Tao Lin paper, >section III-D. > >In this paper, I'm assuming that the Willingness parameter for >MPRs is the same, so it doesn't come into play in the MPR >computation. And as the paper says, MPR_Coverage=1, so there are >no redundant relays in the set. > >But, why is the 'modified' OLSR set so much smaller than the >MPR set? Put another way, which nodes would be included in the >MPR set that wouldn't be included in the modified-OLSR set, especially >since the MPR set does an overall pruning at the end of its >selection algorithm. > >Thanks! >-Madhavi > > > >_______________________________________________ >Ospf-wireless-design mailing list >Ospf-wireless-design@lists.ietf.org >https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > >_______________________________________________ >Ospf-wireless-design mailing list >Ospf-wireless-design@lists.ietf.org >https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 17:30:53 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA19534; Mon, 20 Dec 2004 17:30:53 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgWCh-0008Im-9d; Mon, 20 Dec 2004 17:40:35 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgW0P-0006vj-K5; Mon, 20 Dec 2004 17:27:53 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgV5l-00085k-Bz for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 16:29:21 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA10014 for ; Mon, 20 Dec 2004 16:29:18 -0500 (EST) Received: from web52606.mail.yahoo.com ([206.190.39.144]) by ietf-mx.ietf.org with smtp (Exim 4.33) id 1CgVF3-0005Kw-Ut for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 16:38:59 -0500 Received: (qmail 765 invoked by uid 60001); 20 Dec 2004 21:28:48 -0000 Message-ID: <20041220212848.763.qmail@web52606.mail.yahoo.com> Received: from [198.70.231.66] by web52606.mail.yahoo.com via HTTP; Mon, 20 Dec 2004 16:28:48 EST Date: Mon, 20 Dec 2004 16:28:48 -0500 (EST) From: Tao Lin Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper To: "Henderson, Thomas R" In-Reply-To: <6938661A6EDA8A4EA8D1419BCE46F24C04522A0A@xch-nw-27.nw.nos.boeing.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam-Score: 0.0 (/) X-Scan-Signature: 34d35111647d654d033d58d318c0d21a X-Mailman-Approved-At: Mon, 20 Dec 2004 17:27:52 -0500 Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: e1b0e72ff1bbd457ceef31828f216a86 Hi All, I didn't register in the OSPF-wireless-design email list so I think I missed previous discussions. Based on Madhavi's email, I would like to share some of my quick thought. The willingness is the same in that paper and the MPR sets are minimized since MPR_Coverage=1. Finding a small CDS for a connected network is an NP problem. Therefore, people proposed approximation algorithms to find small CDSs. Generally, the more complicated the algorithm is, the smaller size of CDS it can get. The MPR selection algorithm in OLSR requires O(n), here n is the node degree. And the algorithm I proposed at least requires O(n^2). So this causes the difference. If the number of neighbors is a huge number, then the MPR algorithm can run faster than O(n^2) algorithms. However, the size of a connected wireless network over one wireless channel is limited. So there is no big difference between the algorithm in my paper and the MPR algorithm introduced by OLSR. Source dependent CDS algorithms usually need to exchange some kind of decisions so that all neighboring nodes will decide to be in the final CDS or not. For example, in the MPR algorithm proposed by OLSR, nodes select MPR sets first and exchange their MPR sets with neighbors. After that, a node becomes a CDS node if its MPRS is non-empty. So, there is a delay in this decision making procedure. On the other hand, those source independent CDS algorithms in which nodes make decisions by themselves do not have this delay. Thus, when the network topology changes, a routing protocol running over a source dependent algorithm requires longer converge time than the one running over a source independent algorithm. Corret me if what I said is wrong and welcome more discussions. Tao --- "Henderson, Thomas R" wrote: > I have forwarded this to Tao Lin, who has agreed to > participate > in our discussions on this topic. > > -----Original Message----- > From: Madhavi W. Chandra [mailto:mchandra@cisco.com] > Sent: Monday, December 20, 2004 10:21 AM > To: ospf-wireless-design@ietf.org > Subject: [Ospf-wireless-design] Tao Lin paper > > Hi All, > > I'm hoping one of you can shed some light on the Tao > Lin paper, > section III-D. > > In this paper, I'm assuming that the Willingness > parameter for > MPRs is the same, so it doesn't come into play in > the MPR > computation. And as the paper says, MPR_Coverage=1, > so there are > no redundant relays in the set. > > But, why is the 'modified' OLSR set so much smaller > than the > MPR set? Put another way, which nodes would be > included in the > MPR set that wouldn't be included in the > modified-OLSR set, especially > since the MPR set does an overall pruning at the end > of its > selection algorithm. > > Thanks! > -Madhavi > > > > _______________________________________________ > Ospf-wireless-design mailing list > Ospf-wireless-design@lists.ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > ______________________________________________________________________ Post your free ad now! http://personals.yahoo.ca _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 17:51:33 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA21153; Mon, 20 Dec 2004 17:51:33 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgWWh-0000PU-DI; Mon, 20 Dec 2004 18:01:15 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgWKM-0002TN-LE; Mon, 20 Dec 2004 17:48:30 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgWFc-0001AH-22 for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 17:43:36 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA20518 for ; Mon, 20 Dec 2004 17:43:33 -0500 (EST) Received: from web52610.mail.yahoo.com ([206.190.39.148]) by ietf-mx.ietf.org with smtp (Exim 4.33) id 1CgWOw-0000A9-I1 for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 17:53:15 -0500 Received: (qmail 36326 invoked by uid 60001); 20 Dec 2004 22:43:04 -0000 Message-ID: <20041220224304.36324.qmail@web52610.mail.yahoo.com> Received: from [198.70.231.66] by web52610.mail.yahoo.com via HTTP; Mon, 20 Dec 2004 17:43:04 EST Date: Mon, 20 Dec 2004 17:43:04 -0500 (EST) From: Tao Lin Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper To: Richard Ogier , "Henderson, Thomas R" In-Reply-To: <41C748E7.8090509@earthlink.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam-Score: 0.0 (/) X-Scan-Signature: 00e94c813bef7832af255170dca19e36 Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: d185fa790257f526fedfd5d01ed9c976 Please see my in-line comments below. > > From Lin's description of OLSR: > > "The RNS for a source > node is the MPR set of that node, combined with the > MPR sets > of nodes in the MPR set of that source node, and so > on until > this RNS covers all the nodes in the network." > > It looks like Lin is assuming that a node always > forwards > an LSA that is received from an MPR selector, even > if the same LSA > was previously received from a non-MPR selector, as > long as the > node has not previously *forwarded* the same LSA. > As has been discussed on the OSPF list, this is not > very efficient. > A node only needs to forward an LSA when its *first* > (non-duplicate) > reception is from an MPR selector (except in some > rare cases that > can be handled by having non-MPR nodes retransmit > the LSA when > an ACK is not heard). I think OLSR does it the > efficient way. > Thus, Lin's RNS (relay node set) is probably larger > than the set of > nodes that actually forward the LSA when forwarding > is done efficiently. > I would have to say that my original statement on MPR selection based CDS is not accurate enough (and thanks to OLSR group for pointing this out in my discussions with them). In fact, if a node receives a broadcast message that is received from an MPR selector and is the "first-seen" message, this node will do the re-broadcast. So I should say in the MPR-based CDS algorithm, a node becomes a potential CDS if it has a non-empty MPR selector set. Whether or not it is a real CDS depends on the order of broadcasts in the wireless network. This is what really happens in OLSR-enabled network. Still, the complexity of MPR-based algorithm is O(n) and usually, a O(n^m) algorithm may generate smaller size of CDSs (m>1). Have a nice day! Tao > Another possible advantage of Lin's CDS is that > nodes with the > smallest degree are preferred (with tie broken by > node ID). Since > all neighbors agree on this degree, there is more > agreement among > neighbors regarding the selection of CDS nodes. > Whereas in OLSR > each node selects MPRs independently, so that the > total number of > MPRs is likely to be larger than the total number of > CDS nodes. > > Richard > ______________________________________________________________________ Post your free ad now! http://personals.yahoo.ca _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 22:20:54 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id WAA10151; Mon, 20 Dec 2004 22:20:54 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgajO-0006JD-Lj; Mon, 20 Dec 2004 22:30:38 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgaXb-0005Lu-7s; Mon, 20 Dec 2004 22:18:27 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgaWj-00055z-9N for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 22:17:33 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id WAA10000 for ; Mon, 20 Dec 2004 22:17:30 -0500 (EST) Received: from pop-a065c28.pas.sa.earthlink.net ([207.217.121.205]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cgag6-0006Eo-VK for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 22:27:15 -0500 Received: from dialup-4.243.134.43.dial1.sanfrancisco1.level3.net ([4.243.134.43] helo=earthlink.net) by pop-a065c28.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1CgaWe-0003sn-00; Mon, 20 Dec 2004 19:17:29 -0800 Message-ID: <41C795B1.5070305@earthlink.net> Date: Mon, 20 Dec 2004 19:17:05 -0800 From: Richard Ogier User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202) X-Accept-Language: en-us MIME-Version: 1.0 To: Tao Lin Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper References: <20041220212848.763.qmail@web52606.mail.yahoo.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 2.9 (++) X-Scan-Signature: a1852b4f554b02e7e4548cc7928acc1f Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 2.9 (++) X-Scan-Signature: 93e7fb8fef2e780414389440f367c879 Content-Transfer-Encoding: 7bit Please see my comments below. Tao Lin wrote: >Hi All, > >I didn't register in the OSPF-wireless-design email >list so I think I missed previous discussions. Based >on Madhavi's email, I would like to share some of my >quick thought. > >The willingness is the same in that paper and the MPR >sets are minimized since MPR_Coverage=1. > >Finding a small CDS for a connected network is an NP >problem. Therefore, people proposed approximation >algorithms to find small CDSs. Generally, the more >complicated the algorithm is, the smaller size of CDS >it can get. The MPR selection algorithm in OLSR >requires O(n), here n is the node degree. And the >algorithm I proposed at least requires O(n^2). So >this causes the difference. If the number of > O(n^2) should be acceptable, where n is the number of neighbors, since Dijkstra's algorithm already requires more than this. However, I would not be happy with O(n^3) or higher. > >neighbors is a huge number, then the MPR algorithm can >run faster than O(n^2) algorithms. However, the size >of a connected wireless network over one wireless >channel is limited. So there is no big difference >between the algorithm in my paper and the MPR >algorithm introduced by OLSR. > >Source dependent CDS algorithms usually need to >exchange some kind of decisions so that all >neighboring nodes will decide to be in the final CDS >or not. For example, in the MPR algorithm proposed by >OLSR, nodes select MPR sets first and exchange their >MPR sets with neighbors. After that, a node becomes a >CDS node if its MPRS is non-empty. So, there is a >delay in this decision making procedure. On the other >hand, those source independent CDS algorithms in which >nodes make decisions by themselves do not have this >delay. Thus, when the network topology changes, a >routing protocol running over a source dependent >algorithm requires longer converge time than the one >running over a source independent algorithm. > Right. I have been pointing this out as an advantage of SI-CDS algorithms. (Faster recovery from link failures.) However, this delay can also be avoided by using self-selected MPRs, in which MPRs select themselves based only on 2-hop neighbor information. This is closely related to self-selected CDS nodes. (The same algorithm can be used, except that the router maintains the set of neighbors that depend on the router to relay advertisements.) This is also how TBRPF nodes decide which advertisements to forward, i.e., TBRPF uses self-selected MPRs. Richard > > >Corret me if what I said is wrong and welcome more >discussions. > > Tao > > --- "Henderson, Thomas R" > wrote: > >>I have forwarded this to Tao Lin, who has agreed to >>participate >>in our discussions on this topic. >> >>-----Original Message----- >>From: Madhavi W. Chandra [mailto:mchandra@cisco.com] >>Sent: Monday, December 20, 2004 10:21 AM >>To: ospf-wireless-design@ietf.org >>Subject: [Ospf-wireless-design] Tao Lin paper >> >>Hi All, >> >>I'm hoping one of you can shed some light on the Tao >>Lin paper, >>section III-D. >> >>In this paper, I'm assuming that the Willingness >>parameter for >>MPRs is the same, so it doesn't come into play in >>the MPR >>computation. And as the paper says, MPR_Coverage=1, >>so there are >>no redundant relays in the set. >> >>But, why is the 'modified' OLSR set so much smaller >>than the >>MPR set? Put another way, which nodes would be >>included in the >>MPR set that wouldn't be included in the >>modified-OLSR set, especially >>since the MPR set does an overall pruning at the end >>of its >>selection algorithm. >> >>Thanks! >>-Madhavi >> >> >> >>_______________________________________________ >>Ospf-wireless-design mailing list >>Ospf-wireless-design@lists.ietf.org >> >https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > >> >> > >______________________________________________________________________ >Post your free ad now! http://personals.yahoo.ca > >_______________________________________________ >Ospf-wireless-design mailing list >Ospf-wireless-design@lists.ietf.org >https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Mon Dec 20 23:27:52 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id XAA13670; Mon, 20 Dec 2004 23:27:52 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgbmD-0007fL-Ex; Mon, 20 Dec 2004 23:37:37 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgbbr-0006t3-93; Mon, 20 Dec 2004 23:26:55 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgbbe-0006my-1a for ospf-wireless-design@megatron.ietf.org; Mon, 20 Dec 2004 23:26:42 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id XAA13649 for ; Mon, 20 Dec 2004 23:26:39 -0500 (EST) Received: from rtp-iport-1.cisco.com ([64.102.122.148]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cgbl2-0007dt-Cz for ospf-wireless-design@ietf.org; Mon, 20 Dec 2004 23:36:24 -0500 Received: from rtp-core-1.cisco.com (64.102.124.12) by rtp-iport-1.cisco.com with ESMTP; 20 Dec 2004 23:35:03 -0500 X-BrightmailFiltered: true X-Brightmail-Tracker: AAAAAA== Received: from fruitpie.cisco.com (IDENT:mirapoint@fruitpie.cisco.com [64.102.16.27]) by rtp-core-1.cisco.com (8.12.10/8.12.6) with ESMTP id iBL4Q8Eu024725; Mon, 20 Dec 2004 23:26:08 -0500 (EST) Received: from [192.168.2.4] (rtp-vpn3-241.cisco.com [10.82.216.241]) by fruitpie.cisco.com (MOS 3.4.6-GR) with ESMTP id BED45411; Mon, 20 Dec 2004 20:19:14 -0800 (PST) Message-ID: <41C7A442.5010403@cisco.com> Date: Mon, 20 Dec 2004 23:19:14 -0500 From: Acee Lindem User-Agent: Mozilla Thunderbird 0.9 (Windows/20041103) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Richard Ogier Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper References: <20041220212848.763.qmail@web52606.mail.yahoo.com> <41C795B1.5070305@earthlink.net> In-Reply-To: <41C795B1.5070305@earthlink.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Scan-Signature: 789c141a303c09204b537a4078e2a63f Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: d16ce744298aacf98517bc7c108bd198 Content-Transfer-Encoding: 7bit See my comments inline. Richard Ogier wrote: > Please see my comments below. > > Tao Lin wrote: > >> Hi All, >> >> I didn't register in the OSPF-wireless-design email >> list so I think I missed previous discussions. Based >> on Madhavi's email, I would like to share some of my >> quick thought. >> >> The willingness is the same in that paper and the MPR >> sets are minimized since MPR_Coverage=1. >> >> Finding a small CDS for a connected network is an NP >> problem. Therefore, people proposed approximation >> algorithms to find small CDSs. Generally, the more >> complicated the algorithm is, the smaller size of CDS >> it can get. The MPR selection algorithm in OLSR >> requires O(n), here n is the node degree. And the >> algorithm I proposed at least requires O(n^2). So >> this causes the difference. If the number of >> > O(n^2) should be acceptable, where n is the number of neighbors, > since Dijkstra's algorithm already requires more than this. I'm not sure that this is a case where all N are created equal :^). When you are computing the shortest path (as opposed to all non-looping paths) the Dijkstra algorithm is O(m + nlog(n)) where m and n are respectively the number of nodes and edges in the graph. Can anyone point to code implementing the SI-CDS O(n^2) algorithm? > However, I would not be happy with O(n^3) or higher. > >> >> neighbors is a huge number, then the MPR algorithm can >> run faster than O(n^2) algorithms. However, the size >> of a connected wireless network over one wireless >> channel is limited. So there is no big difference >> between the algorithm in my paper and the MPR >> algorithm introduced by OLSR. >> >> Source dependent CDS algorithms usually need to >> exchange some kind of decisions so that all >> neighboring nodes will decide to be in the final CDS >> or not. For example, in the MPR algorithm proposed by >> OLSR, nodes select MPR sets first and exchange their >> MPR sets with neighbors. After that, a node becomes a >> CDS node if its MPRS is non-empty. So, there is a >> delay in this decision making procedure. On the other >> hand, those source independent CDS algorithms in which >> nodes make decisions by themselves do not have this >> delay. Thus, when the network topology changes, a >> routing protocol running over a source dependent >> algorithm requires longer converge time than the one >> running over a source independent algorithm. >> > Right. I have been pointing this out as an advantage > of SI-CDS algorithms. (Faster recovery from link failures.) > However, this delay can also be avoided by > using self-selected MPRs, in which MPRs select > themselves based only on 2-hop neighbor information. > This is closely related to self-selected CDS nodes. > (The same algorithm can be used, except that the > router maintains the set of neighbors that depend > on the router to relay advertisements.) > This is also how TBRPF nodes decide which advertisements > to forward, i.e., TBRPF uses self-selected MPRs. > > Richard > > >> >> >> Corret me if what I said is wrong and welcome more >> discussions. >> >> Tao >> >> --- "Henderson, Thomas R" >> wrote: >> >>> I have forwarded this to Tao Lin, who has agreed to >>> participate >>> in our discussions on this topic. >>> -----Original Message----- >>> From: Madhavi W. Chandra [mailto:mchandra@cisco.com] >>> Sent: Monday, December 20, 2004 10:21 AM >>> To: ospf-wireless-design@ietf.org >>> Subject: [Ospf-wireless-design] Tao Lin paper >>> >>> Hi All, >>> >>> I'm hoping one of you can shed some light on the Tao >>> Lin paper, >>> section III-D. >>> >>> In this paper, I'm assuming that the Willingness >>> parameter for >>> MPRs is the same, so it doesn't come into play in >>> the MPR >>> computation. And as the paper says, MPR_Coverage=1, >>> so there are >>> no redundant relays in the set. >>> >>> But, why is the 'modified' OLSR set so much smaller >>> than the MPR set? Put another way, which nodes would be >>> included in the >>> MPR set that wouldn't be included in the >>> modified-OLSR set, especially >>> since the MPR set does an overall pruning at the end >>> of its selection algorithm. >>> >>> Thanks! >>> -Madhavi >>> >>> >>> >>> _______________________________________________ >>> Ospf-wireless-design mailing list >>> Ospf-wireless-design@lists.ietf.org >>> >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >> >>> >>> >> >> ______________________________________________________________________ >> Post your free ad now! http://personals.yahoo.ca >> >> _______________________________________________ >> Ospf-wireless-design mailing list >> Ospf-wireless-design@lists.ietf.org >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >> > > > > _______________________________________________ > Ospf-wireless-design mailing list > Ospf-wireless-design@lists.ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Tue Dec 21 01:06:05 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id BAA20272; Tue, 21 Dec 2004 01:06:05 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgdJF-0001ds-3f; Tue, 21 Dec 2004 01:15:49 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgd9T-0006s5-BV; Tue, 21 Dec 2004 01:05:43 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgd8E-0006eY-6l for ospf-wireless-design@megatron.ietf.org; Tue, 21 Dec 2004 01:04:26 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id BAA19910 for ; Tue, 21 Dec 2004 01:04:25 -0500 (EST) Received: from pop-a065d01.pas.sa.earthlink.net ([207.217.121.248]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgdHc-0001YY-Ka for ospf-wireless-design@ietf.org; Tue, 21 Dec 2004 01:14:09 -0500 Received: from dialup-4.243.131.219.dial1.sanfrancisco1.level3.net ([4.243.131.219] helo=earthlink.net) by pop-a065d01.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1Cgd7v-0004xw-00; Mon, 20 Dec 2004 22:04:07 -0800 Message-ID: <41C7BC92.5030908@earthlink.net> Date: Mon, 20 Dec 2004 22:02:58 -0800 From: Richard Ogier User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202) X-Accept-Language: en-us MIME-Version: 1.0 To: Acee Lindem Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper References: <20041220212848.763.qmail@web52606.mail.yahoo.com> <41C795B1.5070305@earthlink.net> <41C7A442.5010403@cisco.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 2.9 (++) X-Scan-Signature: 0e9ebc0cbd700a87c0637ad0e2c91610 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 2.9 (++) X-Scan-Signature: 48472a944c87678fcfe8db15ffecdfff Content-Transfer-Encoding: 7bit Hi Acee, Please see my comments below. Acee Lindem wrote: > See my comments inline. > > Richard Ogier wrote: > >> Please see my comments below. >> >> Tao Lin wrote: >> >>> Hi All, >>> >>> I didn't register in the OSPF-wireless-design email >>> list so I think I missed previous discussions. Based >>> on Madhavi's email, I would like to share some of my >>> quick thought. >>> >>> The willingness is the same in that paper and the MPR >>> sets are minimized since MPR_Coverage=1. >>> >>> Finding a small CDS for a connected network is an NP >>> problem. Therefore, people proposed approximation >>> algorithms to find small CDSs. Generally, the more >>> complicated the algorithm is, the smaller size of CDS >>> it can get. The MPR selection algorithm in OLSR >>> requires O(n), here n is the node degree. And the >>> algorithm I proposed at least requires O(n^2). So >>> this causes the difference. If the number of >>> >> O(n^2) should be acceptable, where n is the number of neighbors, >> since Dijkstra's algorithm already requires more than this. > > > I'm not sure that this is a case where all N are created equal :^). When > you are computing the shortest path (as opposed to all non-looping > paths) the Dijkstra algorithm is O(m + nlog(n)) where m and n are > respectively the number of nodes and edges in the graph. Can > anyone point to code implementing the SI-CDS O(n^2) algorithm? Let's denote the degree by d, so that we are talking about O(d^2). One possible CDS algorithm computes min-hop paths from the maximum RID neighbor to each other neighbor, using only neighbors (or the router itself) as intermediate nodes, giving preference to intermediate nodes with larger RIDs. (Node degree can be used instead of RID.) The router selects itself as a CDS node if it belongs to one of the computed paths. This can be done using BFS with running time O(d^2). This is at most O(m) since d^2 < d * n = m. Now, whether a CDS computed in this way is adequate is another question. I am sure simulations will be conducted to investigate this. If a CDS algorithm that requires O(d^3) results in better performance, the question will be whether O(d^3) is too much. Richard > > >> However, I would not be happy with O(n^3) or higher. >> >>> >>> neighbors is a huge number, then the MPR algorithm can >>> run faster than O(n^2) algorithms. However, the size >>> of a connected wireless network over one wireless >>> channel is limited. So there is no big difference >>> between the algorithm in my paper and the MPR >>> algorithm introduced by OLSR. >>> >>> Source dependent CDS algorithms usually need to >>> exchange some kind of decisions so that all >>> neighboring nodes will decide to be in the final CDS >>> or not. For example, in the MPR algorithm proposed by >>> OLSR, nodes select MPR sets first and exchange their >>> MPR sets with neighbors. After that, a node becomes a >>> CDS node if its MPRS is non-empty. So, there is a >>> delay in this decision making procedure. On the other >>> hand, those source independent CDS algorithms in which >>> nodes make decisions by themselves do not have this >>> delay. Thus, when the network topology changes, a >>> routing protocol running over a source dependent >>> algorithm requires longer converge time than the one >>> running over a source independent algorithm. >>> >> Right. I have been pointing this out as an advantage >> of SI-CDS algorithms. (Faster recovery from link failures.) >> However, this delay can also be avoided by >> using self-selected MPRs, in which MPRs select >> themselves based only on 2-hop neighbor information. >> This is closely related to self-selected CDS nodes. >> (The same algorithm can be used, except that the >> router maintains the set of neighbors that depend >> on the router to relay advertisements.) >> This is also how TBRPF nodes decide which advertisements >> to forward, i.e., TBRPF uses self-selected MPRs. >> >> Richard >> >> >>> >>> >>> Corret me if what I said is wrong and welcome more >>> discussions. >>> >>> Tao >>> >>> --- "Henderson, Thomas R" >>> wrote: >>> >>>> I have forwarded this to Tao Lin, who has agreed to >>>> participate >>>> in our discussions on this topic. -----Original Message----- >>>> From: Madhavi W. Chandra [mailto:mchandra@cisco.com] >>>> Sent: Monday, December 20, 2004 10:21 AM >>>> To: ospf-wireless-design@ietf.org >>>> Subject: [Ospf-wireless-design] Tao Lin paper >>>> >>>> Hi All, >>>> >>>> I'm hoping one of you can shed some light on the Tao >>>> Lin paper, >>>> section III-D. >>>> >>>> In this paper, I'm assuming that the Willingness >>>> parameter for >>>> MPRs is the same, so it doesn't come into play in >>>> the MPR >>>> computation. And as the paper says, MPR_Coverage=1, >>>> so there are >>>> no redundant relays in the set. >>>> >>>> But, why is the 'modified' OLSR set so much smaller >>>> than the MPR set? Put another way, which nodes would be >>>> included in the >>>> MPR set that wouldn't be included in the >>>> modified-OLSR set, especially >>>> since the MPR set does an overall pruning at the end >>>> of its selection algorithm. >>>> >>>> Thanks! >>>> -Madhavi >>>> >>>> >>>> >>>> _______________________________________________ >>>> Ospf-wireless-design mailing list >>>> Ospf-wireless-design@lists.ietf.org >>>> >>> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >>> >>>> >>>> >>> >>> ______________________________________________________________________ >>> Post your free ad now! http://personals.yahoo.ca >>> >>> _______________________________________________ >>> Ospf-wireless-design mailing list >>> Ospf-wireless-design@lists.ietf.org >>> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >>> >> >> >> >> _______________________________________________ >> Ospf-wireless-design mailing list >> Ospf-wireless-design@lists.ietf.org >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >> > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Tue Dec 21 10:19:45 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA18461; Tue, 21 Dec 2004 10:19:45 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cglx9-0006MR-Ap; Tue, 21 Dec 2004 10:29:35 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cglh7-0004c3-Al; Tue, 21 Dec 2004 10:13:01 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CglfQ-00047x-AG for ospf-wireless-design@megatron.ietf.org; Tue, 21 Dec 2004 10:11:16 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA17649 for ; Tue, 21 Dec 2004 10:11:14 -0500 (EST) Received: from s2.itd.nrl.navy.mil ([132.250.83.3]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cglou-000688-7h for ospf-wireless-design@ietf.org; Tue, 21 Dec 2004 10:21:04 -0500 Received: from smtp.itd.nrl.navy.mil (smtp.itd.nrl.navy.mil [132.250.86.3]) by s2.itd.nrl.navy.mil (8.12.10+Sun/8.12.8) with SMTP id iBLFAXbc028874; Tue, 21 Dec 2004 10:10:33 -0500 (EST) Message-Id: <200412211510.iBLFAXbc028874@s2.itd.nrl.navy.mil> Received: (from SEXTANT [132.250.92.22]) by smtp.itd.nrl.navy.mil (SMSSMTP 4.0.5.66) with SMTP id M2004122110103207700 ; Tue, 21 Dec 2004 10:10:32 -0500 From: "Joe Macker" To: "'Richard Ogier'" , "'Madhavi W. Chandra'" Subject: RE: [Ospf-wireless-design] Tao Lin paper Date: Tue, 21 Dec 2004 10:13:59 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook, Build 11.0.5510 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 In-Reply-To: <41C74405.4040802@earthlink.net> Thread-Index: AcTm3+4aYZLNWAWeQ4K49jzTMNzMWQAjef6A X-Spam-Score: 0.8 (/) X-Scan-Signature: 3002fc2e661cd7f114cb6bae92fe88f1 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.8 (/) X-Scan-Signature: f66b12316365a3fe519e75911daf28a8 Content-Transfer-Encoding: 7bit Richard: Good comments.. Re. Your last thought. In the NRL OLSR implementation we broke ties via degree so there was some potential correlation in the election process, this is an old trick from the clustering work of the 1980s, it didn't seem to be that significant in the more scaled case (20-100 nodes) still a good idea in general. See the MILCOM 04 paper, that looks at RNS sizes for a few algorithms. We had hoped some simple election heuristics would signficantly reduce the common shared CDS set. Perhaps there is more work to do here. -----Original Message----- From: ospf-wireless-design-bounces@lists.ietf.org [mailto:ospf-wireless-design-bounces@lists.ietf.org] On Behalf Of Richard Ogier Sent: Monday, December 20, 2004 4:29 PM To: Madhavi W. Chandra Cc: ospf-wireless-design@ietf.org Subject: Re: [Ospf-wireless-design] Tao Lin paper > Madhavi W. Chandra wrote: > >Hi All, > >I'm hoping one of you can shed some light on the Tao Lin paper, section >III-D. > >In this paper, I'm assuming that the Willingness parameter for MPRs is >the same, so it doesn't come into play in the MPR computation. And as >the paper says, MPR_Coverage=1, so there are no redundant relays in the >set. > >But, why is the 'modified' OLSR set so much smaller than the >MPR set? Put another way, which nodes would be included in the >MPR set that wouldn't be included in the modified-OLSR set, especially >since the MPR set does an overall pruning at the end of its selection >algorithm. > >Thanks! >-Madhavi > Madhavi, From Lin's description of OLSR: "The RNS for a source node is the MPR set of that node, combined with the MPR sets of nodes in the MPR set of that source node, and so on until this RNS covers all the nodes in the network." It looks like Lin is assuming that a node always forwards an LSA that is received from an MPR selector, even if the same LSA was previously received from a non-MPR selector, as long as the node has not previously *forwarded* the same LSA. As has been discussed on the OSPF list, this is not very efficient. A node only needs to forward an LSA when its *first* (non-duplicate) reception is from an MPR selector (except in some rare cases that can be handled by having non-MPR nodes retransmit the LSA when an ACK is not heard). I think OLSR does it the efficient way. Thus, Lin's RNS (relay node set) is probably larger than the set of nodes that actually forward the LSA when forwarding is done efficiently. Another possible advantage of Lin's CDS is that nodes with the smallest degree are preferred (with tie broken by node ID). Since all neighbors agree on this degree, there is more agreement among neighbors regarding the selection of CDS nodes. Whereas in OLSR each node selects MPRs independently, so that the total number of MPRs is likely to be larger than the total number of CDS nodes. Richard _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Tue Dec 21 13:02:03 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA04665; Tue, 21 Dec 2004 13:02:03 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgoUF-0002dX-Gm; Tue, 21 Dec 2004 13:11:56 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgoEv-0006ft-4e; Tue, 21 Dec 2004 12:56:05 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgo5u-0004n6-LU for ospf-wireless-design@megatron.ietf.org; Tue, 21 Dec 2004 12:46:46 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA03544 for ; Tue, 21 Dec 2004 12:46:43 -0500 (EST) Received: from rtp-iport-2.cisco.com ([64.102.122.149]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgoFP-00029A-7j for ospf-wireless-design@ietf.org; Tue, 21 Dec 2004 12:56:36 -0500 Received: from rtp-core-2.cisco.com (64.102.124.13) by rtp-iport-2.cisco.com with ESMTP; 21 Dec 2004 12:46:14 -0500 X-BrightmailFiltered: true X-Brightmail-Tracker: AAAAAA== Received: from mchandra-u10.cisco.com (mchandra-u10.cisco.com [64.102.48.252]) by rtp-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id iBLHkCgE014217; Tue, 21 Dec 2004 12:46:12 -0500 (EST) Received: (mchandra@localhost) by mchandra-u10.cisco.com (8.11.2/CISCO.WS.1.2) id iBLHkC811462; Tue, 21 Dec 2004 12:46:12 -0500 (EST) Date: Tue, 21 Dec 2004 12:46:12 -0500 From: "Madhavi W. Chandra" To: Tao Lin Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper Message-ID: <20041221174612.GB11454@cisco.com> References: <6938661A6EDA8A4EA8D1419BCE46F24C04522A0A@xch-nw-27.nw.nos.boeing.com> <20041220212848.763.qmail@web52606.mail.yahoo.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20041220212848.763.qmail@web52606.mail.yahoo.com> User-Agent: Mutt/1.4i X-Spam-Score: 0.0 (/) X-Scan-Signature: 2beba50d0fcdeee5f091c59f204d4365 Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: dbb8771284c7a36189745aa720dc20ab HI All, On Mon, Dec 20, 2004 at 04:28:48PM -0500, Tao Lin wrote: > Hi All, > > I didn't register in the OSPF-wireless-design email > list so I think I missed previous discussions. Based > on Madhavi's email, I would like to share some of my > quick thought. > > The willingness is the same in that paper and the MPR > sets are minimized since MPR_Coverage=1. > > Finding a small CDS for a connected network is an NP > problem. Therefore, people proposed approximation > algorithms to find small CDSs. Generally, the more > complicated the algorithm is, the smaller size of CDS > it can get. The MPR selection algorithm in OLSR > requires O(n), here n is the node degree. And the > algorithm I proposed at least requires O(n^2). So > this causes the difference. If the number of > neighbors is a huge number, then the MPR algorithm can > run faster than O(n^2) algorithms. However, the size > of a connected wireless network over one wireless > channel is limited. So there is no big difference > between the algorithm in my paper and the MPR > algorithm introduced by OLSR. > > Source dependent CDS algorithms usually need to > exchange some kind of decisions so that all > neighboring nodes will decide to be in the final CDS > or not. For example, in the MPR algorithm proposed by > OLSR, nodes select MPR sets first and exchange their > MPR sets with neighbors. After that, a node becomes a > CDS node if its MPRS is non-empty. So, there is a > delay in this decision making procedure. On the other > hand, those source independent CDS algorithms in which > nodes make decisions by themselves do not have this > delay. Thus, when the network topology changes, a > routing protocol running over a source dependent > algorithm requires longer converge time than the one > running over a source independent algorithm. > > Corret me if what I said is wrong and welcome more > discussions. OK...this helps. I was trying to understand why the CDS set was showing to be so much smaller than the MPR set...but, I guess the comparison was skewed. In any case, as with most things, it's always a tradeoff...and we need to investigate it more. I'm not convinced that we should trade off complexity for convergence, especially when we can mitigate the effect of delayed convergence. With overlapping relays, the backup relays would go into action if the active overlapping relays do not transmit or ACKs are not heard. So, convergence is not as delayed...and complexity is still linear. It's not clear to me that the CDS is significantly smaller than an overlapping set to warrant the added complexity. Actually, in many/most cases it seems that it would be the same, especially with the pruning in the overlapping relay algorithm or MPR algorithm. Anyway, simulations can help us see this more clearly. On another note, is it fair to say that a source-independent CDS algorithm is actually more *dependent* on all of the nodes behaving 'ideally'...running the same selection algorithm, agreeing on their IDs, etc....whereas a source-dependent overlapping relays/MPR algorithm is more flexible? Regards, Madhavi > Tao > > --- "Henderson, Thomas R" > wrote: > > I have forwarded this to Tao Lin, who has agreed to > > participate > > in our discussions on this topic. > > > > -----Original Message----- > > From: Madhavi W. Chandra [mailto:mchandra@cisco.com] > > Sent: Monday, December 20, 2004 10:21 AM > > To: ospf-wireless-design@ietf.org > > Subject: [Ospf-wireless-design] Tao Lin paper > > > > Hi All, > > > > I'm hoping one of you can shed some light on the Tao > > Lin paper, > > section III-D. > > > > In this paper, I'm assuming that the Willingness > > parameter for > > MPRs is the same, so it doesn't come into play in > > the MPR > > computation. And as the paper says, MPR_Coverage=1, > > so there are > > no redundant relays in the set. > > > > But, why is the 'modified' OLSR set so much smaller > > than the > > MPR set? Put another way, which nodes would be > > included in the > > MPR set that wouldn't be included in the > > modified-OLSR set, especially > > since the MPR set does an overall pruning at the end > > of its > > selection algorithm. > > > > Thanks! > > -Madhavi > > > > > > > > _______________________________________________ > > Ospf-wireless-design mailing list > > Ospf-wireless-design@lists.ietf.org > > > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > > > > ______________________________________________________________________ > Post your free ad now! http://personals.yahoo.ca > > _______________________________________________ > Ospf-wireless-design mailing list > Ospf-wireless-design@lists.ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Tue Dec 21 13:27:36 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA06158; Tue, 21 Dec 2004 13:27:36 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cgoso-0003CE-C4; Tue, 21 Dec 2004 13:37:29 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgoRF-0001Gy-FR; Tue, 21 Dec 2004 13:08:49 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CgoOr-0000pw-GN for ospf-wireless-design@megatron.ietf.org; Tue, 21 Dec 2004 13:06:21 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA05204 for ; Tue, 21 Dec 2004 13:06:18 -0500 (EST) Received: from web52601.mail.yahoo.com ([206.190.39.139]) by ietf-mx.ietf.org with smtp (Exim 4.33) id 1CgoYM-0002k4-RO for ospf-wireless-design@ietf.org; Tue, 21 Dec 2004 13:16:11 -0500 Received: (qmail 47393 invoked by uid 60001); 21 Dec 2004 18:05:47 -0000 Message-ID: <20041221180547.47390.qmail@web52601.mail.yahoo.com> Received: from [198.70.231.66] by web52601.mail.yahoo.com via HTTP; Tue, 21 Dec 2004 13:05:47 EST Date: Tue, 21 Dec 2004 13:05:47 -0500 (EST) From: Tao Lin Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper To: "Madhavi W. Chandra" , ospf-wireless-design@ietf.org In-Reply-To: <20041221174612.GB11454@cisco.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam-Score: 0.0 (/) X-Scan-Signature: 21c69d3cfc2dd19218717dbe1d974352 X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: 50a516d93fd399dc60588708fd9a3002 Hi Madhavi, Just one comment on the paragraph in your email (see below). If a CDS algorithms only requires that all nodes are broadcasting their neighbor lists to their neighbors, we can 99.99% sure that all nodes work 'ideally'. This is because the information it requires is the minimized information set (which is also included in the information required for source dependent CDS algorithms). If this cannot be guaranteed, those source dependent algorithms will also fail. Furthermore, even if somehow a hello message is lost, neighboring nodes can recover from that lost at the next hello time. Therefore, the source-independent algorithm using only 2-hop neighbor information can work at least as 'independently' as other source-dependent algorithms. Have a great day! Tao --- "Madhavi W. Chandra" wrote: > On another note, is it fair to say that a > source-independent CDS > algorithm is actually more *dependent* on all of the > nodes behaving > 'ideally'...running the same selection algorithm, > agreeing on their > IDs, etc....whereas a source-dependent overlapping > relays/MPR > algorithm is more flexible? > > Regards, > Madhavi > ______________________________________________________________________ Post your free ad now! http://personals.yahoo.ca _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Tue Dec 21 15:40:14 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA17591; Tue, 21 Dec 2004 15:40:14 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CgqxL-0006v8-2E; Tue, 21 Dec 2004 15:50:07 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgqla-00050f-DO; Tue, 21 Dec 2004 15:37:58 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Cgql4-0004iZ-St for ospf-wireless-design@megatron.ietf.org; Tue, 21 Dec 2004 15:37:27 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA17415 for ; Tue, 21 Dec 2004 15:37:24 -0500 (EST) Received: from pop-a065d19.pas.sa.earthlink.net ([207.217.121.253]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cgqub-0006r7-LD for ospf-wireless-design@ietf.org; Tue, 21 Dec 2004 15:47:18 -0500 Received: from dialup-4.243.137.13.dial1.sanfrancisco1.level3.net ([4.243.137.13] helo=earthlink.net) by pop-a065d19.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1Cgqjx-0001sl-00; Tue, 21 Dec 2004 12:36:18 -0800 Message-ID: <41C88937.2090501@earthlink.net> Date: Tue, 21 Dec 2004 12:36:07 -0800 From: Richard Ogier User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202) X-Accept-Language: en-us MIME-Version: 1.0 To: "Madhavi W. Chandra" Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper References: <6938661A6EDA8A4EA8D1419BCE46F24C04522A0A@xch-nw-27.nw.nos.boeing.com> <20041220212848.763.qmail@web52606.mail.yahoo.com> <20041221174612.GB11454@cisco.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Scan-Signature: 2857c5c041d6c02d7181d602c22822c8 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.1 (/) X-Scan-Signature: 67c1ea29f88502ef6a32ccec927970f0 Content-Transfer-Encoding: 7bit Please see my comments below. Madhavi W. Chandra wrote: > >In any case, as with most things, it's always a tradeoff...and we need >to investigate it more. I'm not convinced that we should trade off >complexity for convergence, especially when we can mitigate the effect >of delayed convergence. With overlapping relays, the backup relays >would go into action if the active overlapping relays do not transmit >or ACKs are not heard. So, convergence is not as delayed...and >complexity is still linear. > The complexity must be at least O(d^2)where d is the degree, since it takes that much time just to look at each neighbor's neighbors. Some CDS algorithms also have this complexity. But you are right that the MPR algorithm is linear in the number of links, rather than nodes. Also, the additional burden put on backup relays due to the slower convergence might result in increased overhead due to retransmissions. But I agree that simulations will help us answer some of these questions. Richard >It's not clear to me that the >CDS is significantly smaller than an overlapping set to warrant the >added complexity. Actually, in many/most cases it seems that it would >be the same, especially with the pruning in the overlapping relay >algorithm or MPR algorithm. > >Anyway, simulations can help us see this more clearly. > >On another note, is it fair to say that a source-independent CDS >algorithm is actually more *dependent* on all of the nodes behaving >'ideally'...running the same selection algorithm, agreeing on their >IDs, etc....whereas a source-dependent overlapping relays/MPR >algorithm is more flexible? > >Regards, >Madhavi > >> Tao >> >> --- "Henderson, Thomas R" >> wrote: >> >>>I have forwarded this to Tao Lin, who has agreed to >>>participate >>>in our discussions on this topic. >>> >>>-----Original Message----- >>>From: Madhavi W. Chandra [mailto:mchandra@cisco.com] >>>Sent: Monday, December 20, 2004 10:21 AM >>>To: ospf-wireless-design@ietf.org >>>Subject: [Ospf-wireless-design] Tao Lin paper >>> >>>Hi All, >>> >>>I'm hoping one of you can shed some light on the Tao >>>Lin paper, >>>section III-D. >>> >>>In this paper, I'm assuming that the Willingness >>>parameter for >>>MPRs is the same, so it doesn't come into play in >>>the MPR >>>computation. And as the paper says, MPR_Coverage=1, >>>so there are >>>no redundant relays in the set. >>> >>>But, why is the 'modified' OLSR set so much smaller >>>than the >>>MPR set? Put another way, which nodes would be >>>included in the >>>MPR set that wouldn't be included in the >>>modified-OLSR set, especially >>>since the MPR set does an overall pruning at the end >>>of its >>>selection algorithm. >>> >>>Thanks! >>>-Madhavi >>> >>> >>> >>>_______________________________________________ >>>Ospf-wireless-design mailing list >>>Ospf-wireless-design@lists.ietf.org >>> >>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >> >>> >>> >>______________________________________________________________________ >>Post your free ad now! http://personals.yahoo.ca >> >>_______________________________________________ >>Ospf-wireless-design mailing list >>Ospf-wireless-design@lists.ietf.org >>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >> > >_______________________________________________ >Ospf-wireless-design mailing list >Ospf-wireless-design@lists.ietf.org >https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Wed Dec 22 11:36:51 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA10370; Wed, 22 Dec 2004 11:36:51 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Ch9dY-0003g3-EL; Wed, 22 Dec 2004 11:46:56 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Ch9LX-00082w-HZ; Wed, 22 Dec 2004 11:28:19 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1Ch9K5-00070H-Ft for ospf-wireless-design@megatron.ietf.org; Wed, 22 Dec 2004 11:26:49 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA08539 for ; Wed, 22 Dec 2004 11:26:44 -0500 (EST) Received: from s2.itd.nrl.navy.mil ([132.250.83.3]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Ch9Tj-0003N0-VH for ospf-wireless-design@ietf.org; Wed, 22 Dec 2004 11:36:49 -0500 Received: from smtp.itd.nrl.navy.mil (smtp.itd.nrl.navy.mil [132.250.86.3]) by s2.itd.nrl.navy.mil (8.12.10+Sun/8.12.8) with SMTP id iBMGQ8bc017425; Wed, 22 Dec 2004 11:26:08 -0500 (EST) Message-Id: <200412221626.iBMGQ8bc017425@s2.itd.nrl.navy.mil> Received: (from SEXTANT [132.250.92.22]) by smtp.itd.nrl.navy.mil (SMSSMTP 4.0.5.66) with SMTP id M2004122211260714384 ; Wed, 22 Dec 2004 11:26:07 -0500 From: "Joe Macker" To: "'Madhavi W. Chandra'" , "'Tao Lin'" Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper Date: Wed, 22 Dec 2004 11:29:38 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook, Build 11.0.5510 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 In-Reply-To: <20041221174612.GB11454@cisco.com> Thread-Index: AcTnhzbYZL89hwzzSjOixOpapXbs+gAtONIw X-Spam-Score: 0.8 (/) X-Scan-Signature: 93238566e09e6e262849b4f805833007 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.8 (/) X-Scan-Signature: 9466e0365fc95844abaf7c3f15a05c7d Content-Transfer-Encoding: 7bit On another note, is it fair to say that a source-independent CDS algorithm is actually more *dependent* on all of the nodes behaving 'ideally'...running the same selection algorithm, agreeing on their IDs, etc....whereas a source-dependent overlapping relays/MPR algorithm is more flexible? Regards, Madhavi ------------------------------ Madhavi: There are many tradeoffs, I would agree you point out one. For instance, you can easily have difference election heuristics at different nodes assuming you meet the basic requirements of a localized 2-hop CDS. There is likely "no one size fits all" for every scenario, but I assume our job is to converge on an approach. There is alot to be said for "source dependent" approaches but this might not be the goal for OSPF-MANET. _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Wed Dec 22 15:27:00 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA00282; Wed, 22 Dec 2004 15:27:00 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChDEI-0001s1-Ky; Wed, 22 Dec 2004 15:37:06 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChCyq-0000ZN-TZ; Wed, 22 Dec 2004 15:21:08 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChCwz-0007Uv-Pz for ospf-wireless-design@megatron.ietf.org; Wed, 22 Dec 2004 15:19:13 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA29406 for ; Wed, 22 Dec 2004 15:19:11 -0500 (EST) Received: from sj-iport-2-in.cisco.com ([171.71.176.71] helo=sj-iport-2.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChD6g-0001d5-F4 for ospf-wireless-design@ietf.org; Wed, 22 Dec 2004 15:29:17 -0500 Received: from sj-core-2.cisco.com (171.71.177.254) by sj-iport-2.cisco.com with ESMTP; 22 Dec 2004 12:24:05 -0800 Received: from mira-sjc5-b.cisco.com (IDENT:mirapoint@mira-sjc5-b.cisco.com [171.71.163.14]) by sj-core-2.cisco.com (8.12.10/8.12.6) with ESMTP id iBMKIVdP014987; Wed, 22 Dec 2004 12:18:31 -0800 (PST) Received: from irp-view9.cisco.com (irp-view9.cisco.com [171.70.65.147]) by mira-sjc5-b.cisco.com (MOS 3.4.5-GR) with ESMTP id BAA93158; Wed, 22 Dec 2004 12:29:30 -0800 (PST) Date: Wed, 22 Dec 2004 12:18:35 -0800 (PST) From: Abhay Roy To: Tao Lin Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper In-Reply-To: <20041221180547.47390.qmail@web52601.mail.yahoo.com> Message-ID: References: <20041221180547.47390.qmail@web52601.mail.yahoo.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Spam-Score: 0.0 (/) X-Scan-Signature: 52f7a77164458f8c7b36b66787c853da Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: 4b800b1eab964a31702fa68f1ff0e955 Hi Tao, It's good to hear from you first hand on this topic. What may be useful to further this discussion is an example or two, where we can demostrate that the improved algorithm comes up with a smaller set. In my mind, it's still very fuzzy how this happens ;) Also, since we are going to be doing simulations under Tom's GTNetS tool, we will need to include Tao's algorithm in there. Regards, -Roy- On 12/21/04-0500 at 1:05pm, Tao Lin writes: > Hi Madhavi, > > Just one comment on the paragraph in your email (see > below). > > If a CDS algorithms only requires that all nodes are > broadcasting their neighbor lists to their neighbors, > we can 99.99% sure that all nodes work 'ideally'. > This is because the information it requires is the > minimized information set (which is also included in > the information required for source dependent CDS > algorithms). If this cannot be guaranteed, those > source dependent algorithms will also fail. > Furthermore, even if somehow a hello message is lost, > neighboring nodes can recover from that lost at the > next hello time. > > Therefore, the source-independent algorithm using only > 2-hop neighbor information can work at least as > 'independently' as other source-dependent algorithms. > > Have a great day! > > Tao > > --- "Madhavi W. Chandra" wrote: >> On another note, is it fair to say that a >> source-independent CDS >> algorithm is actually more *dependent* on all of the >> nodes behaving >> 'ideally'...running the same selection algorithm, >> agreeing on their >> IDs, etc....whereas a source-dependent overlapping >> relays/MPR >> algorithm is more flexible? >> >> Regards, >> Madhavi >> > > > > ______________________________________________________________________ > Post your free ad now! http://personals.yahoo.ca > > _______________________________________________ > Ospf-wireless-design mailing list > Ospf-wireless-design@lists.ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Wed Dec 22 17:34:11 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA12633; Wed, 22 Dec 2004 17:34:11 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChFDO-0005yS-HS; Wed, 22 Dec 2004 17:44:19 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChErq-0004MR-00; Wed, 22 Dec 2004 17:22:02 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChElL-0002vh-Af for ospf-wireless-design@megatron.ietf.org; Wed, 22 Dec 2004 17:15:19 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA10100 for ; Wed, 22 Dec 2004 17:15:16 -0500 (EST) Received: from s2.itd.nrl.navy.mil ([132.250.83.3]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChEv6-0005QX-1b for ospf-wireless-design@ietf.org; Wed, 22 Dec 2004 17:25:24 -0500 Received: from smtp.itd.nrl.navy.mil (smtp.itd.nrl.navy.mil [132.250.86.3]) by s2.itd.nrl.navy.mil (8.12.10+Sun/8.12.8) with SMTP id iBMMEibc003464; Wed, 22 Dec 2004 17:14:44 -0500 (EST) Message-Id: <200412222214.iBMMEibc003464@s2.itd.nrl.navy.mil> Received: (from SEXTANT [132.250.92.22]) by smtp.itd.nrl.navy.mil (SMSSMTP 4.0.5.66) with SMTP id M2004122217144316309 ; Wed, 22 Dec 2004 17:14:43 -0500 From: "Joe Macker" To: "'Abhay Roy'" , "'Tao Lin'" Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper Date: Wed, 22 Dec 2004 17:18:15 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook, Build 11.0.5510 Thread-Index: AcToZLXwzY0H3EHmQ7egof6Sq45L/QADkA1g In-Reply-To: X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-Spam-Score: 0.8 (/) X-Scan-Signature: 10ba05e7e8a9aa6adb025f426bef3a30 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.8 (/) X-Scan-Signature: a2c12dacc0736f14d6b540e805505a86 Content-Transfer-Encoding: 7bit Tao: >From my reading of your paper, it counts the total MPR relay set (not what set would be actually used in a single flodding instance).. This may have been fair in context because your goal was developiong a source independent variant, but it may confuse many readers since this is not the number of relays used by a single flooding instance. I verified some of this against an analytical model we have of (total elected MPRs/independent of source) vs. (average MPRs used per flooding instance) that we developed for one of our flooding studies. Am I off-base here? -Joe -----Original Message----- From: ospf-wireless-design-bounces@lists.ietf.org [mailto:ospf-wireless-design-bounces@lists.ietf.org] On Behalf Of Abhay Roy Sent: Wednesday, December 22, 2004 3:19 PM To: Tao Lin Cc: ospf-wireless-design@ietf.org Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper Hi Tao, It's good to hear from you first hand on this topic. What may be useful to further this discussion is an example or two, where we can demostrate that the improved algorithm comes up with a smaller set. In my mind, it's still very fuzzy how this happens ;) Also, since we are going to be doing simulations under Tom's GTNetS tool, we will need to include Tao's algorithm in there. Regards, -Roy- On 12/21/04-0500 at 1:05pm, Tao Lin writes: > Hi Madhavi, > > Just one comment on the paragraph in your email (see below). > > If a CDS algorithms only requires that all nodes are broadcasting > their neighbor lists to their neighbors, we can 99.99% sure that all > nodes work 'ideally'. > This is because the information it requires is the minimized > information set (which is also included in the information required > for source dependent CDS algorithms). If this cannot be guaranteed, > those source dependent algorithms will also fail. > Furthermore, even if somehow a hello message is lost, neighboring > nodes can recover from that lost at the next hello time. > > Therefore, the source-independent algorithm using only 2-hop neighbor > information can work at least as 'independently' as other > source-dependent algorithms. > > Have a great day! > > Tao > > --- "Madhavi W. Chandra" wrote: >> On another note, is it fair to say that a source-independent CDS >> algorithm is actually more *dependent* on all of the nodes behaving >> 'ideally'...running the same selection algorithm, agreeing on their >> IDs, etc....whereas a source-dependent overlapping relays/MPR >> algorithm is more flexible? >> >> Regards, >> Madhavi >> > > > > ______________________________________________________________________ > Post your free ad now! http://personals.yahoo.ca > > _______________________________________________ > Ospf-wireless-design mailing list > Ospf-wireless-design@lists.ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Wed Dec 22 20:10:00 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA22734; Wed, 22 Dec 2004 20:10:00 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChHeC-000173-H8; Wed, 22 Dec 2004 20:20:08 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChHTY-0000fZ-Ol; Wed, 22 Dec 2004 20:09:08 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChHPP-0008H9-QR for ospf-wireless-design@megatron.ietf.org; Wed, 22 Dec 2004 20:04:51 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA22333 for ; Wed, 22 Dec 2004 20:04:49 -0500 (EST) Received: from stl-smtpout-01.boeing.com ([130.76.96.56]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChHZ8-0000wk-Mm for ospf-wireless-design@ietf.org; Wed, 22 Dec 2004 20:14:58 -0500 Received: from stl-av-01.boeing.com ([192.76.190.6]) by stl-smtpout-01.boeing.com (8.9.2.MG.10092003/8.8.5-M2) with ESMTP id TAA22683; Wed, 22 Dec 2004 19:04:10 -0600 (CST) Received: from XCH-NWBH-02.nw.nos.boeing.com (localhost [127.0.0.1]) by stl-av-01.boeing.com (8.11.3/8.11.3/MBS-AV-LDAP-01) with ESMTP id iBN148s16409; Wed, 22 Dec 2004 19:04:09 -0600 (CST) Received: from XCH-NW-27.nw.nos.boeing.com ([192.48.4.101]) by XCH-NWBH-02.nw.nos.boeing.com with Microsoft SMTPSVC(6.0.3790.211); Wed, 22 Dec 2004 17:04:08 -0800 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.0.6603.0 Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper Date: Wed, 22 Dec 2004 17:04:08 -0800 Message-ID: <6938661A6EDA8A4EA8D1419BCE46F24C06648C5E@xch-nw-27.nw.nos.boeing.com> Thread-Topic: FW: [Ospf-wireless-design] Tao Lin paper Thread-Index: AcTnoV/+A5Q8fxpMQFi4uF2dCFBaGQA6XDXQ From: "Henderson, Thomas R" To: "Richard Ogier" X-OriginalArrivalTime: 23 Dec 2004 01:04:08.0697 (UTC) FILETIME=[4E6B4E90:01C4E88B] X-Spam-Score: 0.0 (/) X-Scan-Signature: d6b246023072368de71562c0ab503126 Content-Transfer-Encoding: quoted-printable Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.0 (/) X-Scan-Signature: 93238566e09e6e262849b4f805833007 Content-Transfer-Encoding: quoted-printable >=20 > But I agree that simulations will help us answer some > of these questions. >=20 On that note, we plan to distribute an open-source-based simulator to the design team sometime shortly after the new year (probably the first week of January). If you are interested in getting a=20 pre-release snapshot, please contact me. In a nutshell, the simulator implements the overlapping relays code within the quagga OSPFv3 implementation, and can also be compiled and run as an executable (quagga router). We are working through=20 the initial validation and benchmarking of the performance, and trying to document things well, so that interested design team members can run their own simulations. The next step for us will be to look at the SI-CDS alternatives. Tom _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design From ospf-wireless-design-bounces@ietf.org Thu Dec 23 11:29:07 2004 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA23153; Thu, 23 Dec 2004 11:29:07 -0500 (EST) Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChVzn-0000Be-Gp; Thu, 23 Dec 2004 11:39:24 -0500 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChVlt-0002Bb-Hu; Thu, 23 Dec 2004 11:25:01 -0500 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1ChVTt-000542-Ve for ospf-wireless-design@megatron.ietf.org; Thu, 23 Dec 2004 11:06:26 -0500 Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA21607 for ; Thu, 23 Dec 2004 11:06:23 -0500 (EST) Received: from pop-a065c32.pas.sa.earthlink.net ([207.217.121.247]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1ChVdo-0007wH-7Q for ospf-wireless-design@ietf.org; Thu, 23 Dec 2004 11:16:40 -0500 Received: from dialup-4.243.128.54.dial1.sanfrancisco1.level3.net ([4.243.128.54] helo=earthlink.net) by pop-a065c32.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1ChVSn-00064C-00; Thu, 23 Dec 2004 08:05:18 -0800 Message-ID: <41CAEBFE.2080703@earthlink.net> Date: Thu, 23 Dec 2004 08:02:07 -0800 From: Richard Ogier User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202) X-Accept-Language: en-us MIME-Version: 1.0 To: Abhay Roy Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper References: <20041221180547.47390.qmail@web52601.mail.yahoo.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.1 (/) X-Scan-Signature: 5d7a7e767f20255fce80fa0b77fb2433 Content-Transfer-Encoding: 7bit Cc: ospf-wireless-design@ietf.org X-BeenThere: ospf-wireless-design@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: OSPF Wireless Design Team List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: ospf-wireless-design-bounces@ietf.org Errors-To: ospf-wireless-design-bounces@ietf.org X-Spam-Score: 0.1 (/) X-Scan-Signature: b22590c27682ace61775ee7b453b40d3 Content-Transfer-Encoding: 7bit Hi Roy, Here is an example where MPRs result in 3 times as many transmissions as a SI-CDS. 5 / | \ 1-- 6-- 3 | | | 2-- 7-- 4 \ | / 8 Node 5 is the source. The MPRs that forward LSAs from node 5 are {1, 6, 3, 2, 7, 4}. The SI-CDS is {6, 7}, obtained using the algorithm below which runs in O(d^2) time using a modified BFS algorithm, where d is the number of neighbors. The drawback of MPRs in this case is that they are required to provide min-hop paths, whereas a SI-CDS does not have this requirement. Of course, this is a special example, and simulations will tell us what happens on average. But even if the SI-CDS were the same size as the MPR set, I would favor the SI-CDS because of several other advantages, such as faster convergence. I plan to submit a draft next week that presents a family of CDS algorithms, including the one below, along with some simulation results. Minimal CDS Algorithm 1. If node i has a larger value of (RtrPri, RID) than any of its neighbors, then node i selects itself as a DR. 2. Else, let j be the neighbor of node i that has the largest value of (RtrPri, RID). If there exists a path (with one or more hops, based on node i's 2-hop neighbor information) from node j to each other neighbor of node i, using only intermediate nodes that have a larger value of (RtrPri, RID) than node i, then node i does not select itself as a DR; otherwise node i selects itself as a DR. Happy Holidays! Richard Abhay Roy wrote: > Hi Tao, > > It's good to hear from you first hand on this topic. What may be > useful to further this discussion is an example or two, where we can > demostrate that the improved algorithm comes up with a smaller set. In > my mind, it's still very fuzzy how this happens ;) > > Also, since we are going to be doing simulations under Tom's GTNetS > tool, we will need to include Tao's algorithm in there. > > Regards, > -Roy- > > On 12/21/04-0500 at 1:05pm, Tao Lin writes: > >> Hi Madhavi, >> >> Just one comment on the paragraph in your email (see >> below). >> >> If a CDS algorithms only requires that all nodes are >> broadcasting their neighbor lists to their neighbors, >> we can 99.99% sure that all nodes work 'ideally'. >> This is because the information it requires is the >> minimized information set (which is also included in >> the information required for source dependent CDS >> algorithms). If this cannot be guaranteed, those >> source dependent algorithms will also fail. >> Furthermore, even if somehow a hello message is lost, >> neighboring nodes can recover from that lost at the >> next hello time. >> >> Therefore, the source-independent algorithm using only >> 2-hop neighbor information can work at least as >> 'independently' as other source-dependent algorithms. >> >> Have a great day! >> >> Tao >> >> --- "Madhavi W. Chandra" wrote: >> >>> On another note, is it fair to say that a >>> source-independent CDS >>> algorithm is actually more *dependent* on all of the >>> nodes behaving >>> 'ideally'...running the same selection algorithm, >>> agreeing on their >>> IDs, etc....whereas a source-dependent overlapping >>> relays/MPR >>> algorithm is more flexible? >>> >>> Regards, >>> Madhavi >>> >> >> >> >> ______________________________________________________________________ >> Post your free ad now! http://personals.yahoo.ca >> >> _______________________________________________ >> Ospf-wireless-design mailing list >> Ospf-wireless-design@lists.ietf.org >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design >> > > _______________________________________________ > Ospf-wireless-design mailing list > Ospf-wireless-design@lists.ietf.org > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design > _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design