Re: [Ospf-wireless-design] new material to review and discuss
Richard <rich.ogier@earthlink.net> Wed, 27 October 2004 07:02 UTC
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 DAA10949; Wed, 27 Oct 2004 03:02:47 -0400 (EDT)
Received: from megatron.ietf.org ([132.151.6.71]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CMi3N-0006wO-RO; Wed, 27 Oct 2004 03:17:06 -0400
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CMhoc-00011x-2g; Wed, 27 Oct 2004 03:01:50 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1CMhnm-0000qu-LB for ospf-wireless-design@megatron.ietf.org; Wed, 27 Oct 2004 03:00:58 -0400
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 DAA10784 for <ospf-wireless-design@ietf.org>; Wed, 27 Oct 2004 03:00:56 -0400 (EDT)
Received: from pop-a065c28.pas.sa.earthlink.net ([207.217.121.205]) by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CMi1a-0006uf-PD for ospf-wireless-design@ietf.org; Wed, 27 Oct 2004 03:15:15 -0400
Received: from sdn-ap-004castocp0021.dialsprint.net ([63.187.32.21] helo=earthlink.net) by pop-a065c28.pas.sa.earthlink.net with esmtp (Exim 3.33 #1) id 1CMhne-00058E-00; Wed, 27 Oct 2004 00:00:51 -0700
Message-ID: <417F479D.8030001@earthlink.net>
Date: Wed, 27 Oct 2004 00:00:45 -0700
From: Richard <rich.ogier@earthlink.net>
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" <thomas.r.henderson@boeing.com>
Subject: Re: [Ospf-wireless-design] new material to review and discuss
References: <6938661A6EDA8A4EA8D1419BCE46F24C0452271F@xch-nw-27.nw.nos.boeing.com>
Content-Type: text/plain; charset="us-ascii"; format="flowed"
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.2 (/)
X-Scan-Signature: fcb459c204557d9509ce9c1b55d771f1
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 <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, <mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, <mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.2 (/)
X-Scan-Signature: 913ee11e7c554f7d4da75d500826397e
Content-Transfer-Encoding: 7bit
Thomas, Please see my comments below for Section 3.2 of your document draft-manet-ospf-design-team-00-pre2 Overall, it is very good. First I want to comment on your sentence: > MPRs are also sometimes referred to as source-dependent CDS, while > the use of the term CDS typically means source-independent CDS. I'm glad you clarified this. So the main issue is whether we want the relays to be source-dependent or source-independent. Actually, there are different ways of defining a CDS in terms of MPRs, depending on the forwarding rule. (E.g., does an MPR forward any packet that was received from an MPR selector, or only if the first neighbor that transmitted the packet is an MPR selector, or only if the min ID neighbor that transmitted the packet is an MPR selector, etc.) > 3.2.1.2 Self-selected MPRs > > Regarding whether MPRs are self-selected versus selected by the > originators themselves, the tradeoff seems to be some increase in > complexity (i.e., processing steps) to self-select them, versus a > need to use extra fields in Hello or other messages to notify a > neighbor that it has been selected. However, it may require that > OSPF Hellos be modified to provide two-hop information anyway. For > example, consider if each node provided its two-hop neighbor > information to all of its one hop neighbors. Rather than the node > running the MPR selection algorithm and notifying the selected one > hop neighbor, each neighbor could run the algorithm on the node's > behalf, and decide whether it would have been selected by the node. > But the current OSPF Hello only provides one-hop neighbor information > for the sending node. Actually, the OSPF Hello does not even provide one-hop neighbor information, since it does not say whether each neighbor is 2-way. As in Cisco's protocol and in TBRPF, each node can inform its neighbors of all of its 2-way neighbors in its self-originated LSA. In that way, each node learns about all of its neighbors' neighbors (2-hop neighbors). It would be unnecessarily bandwidth consuming for each node to report all of its 2-hop neighbors (which would result in each node knowing its 3-hop neighbors). > > > A minimum-ID algorithm described in [9] requires O(m^4) computation > when run as a self-selecting algorithm rather than O(m^2) or O(m) > using the MPR selector approach. However, it has also been pointed A min-ID self-selecting algorithm exists which requires only O(n^3) using the Floyd-Warshall algorithm to compute shortest paths from each neighbor to each other neighbor, where n is the number of neighbors. I don't think this is too large. Another such algorithm requires only O(n^2) computations by computing shortest paths from each neighbor to only the min-ID neighbor. > > out by Ogier that, analogous to including the selected DR in Hello > messages, it may be useful to announce whether a node has selected > itself as an MPR for one of its neighbors, to reduce the frequency of > MPR changes. > > 3.2.1.3 Cisco Overlapping Relays > > As described in [4], the proposed "overlapping relays" algorithm is > based on the OLSR MPR algorithm, with the following optimization. > Neighbors that are selected as what OLSR would call MPRs are called > "active" overlapping relays, and all other neighbors are "non-active" > overlapping relays, with respect to a given two-hop neighbor of the > > > > Henderson (ed.) Expires April 13, 2005 [Page 9] > > Internet-Draft Summary of MANET OSPF Proposals October 2004 > > > message originator. The active relays behave like OLSR MPRs, but the > non-active relays of message originator monitor whether the two-hop > neighbor in fact acknowledged the transmission. If no ack is > received, then one of the non-active relays will attempt to > retransmit the message, based on some time interval and jitter to > avoid all non-active relays from attempting to recover the loss at > the same time. > > Other than this reliability optimization, it seems that the proposed > Cisco approach inherits the properties described above regarding > OLSR-style MPRs. As presently defined, it also incurs a delay in > notifying a neighbor that it has become active (the so-called > "opt-in" method above), but this is mitigated by the protection > offered by non-active neighbors, so all that might happen is a slight > increase in flooding delay. > > 3.2.1.4 CDS algorithms > > At the end of Section 6 of [5], Richard Ogier argues that CDS may be > preferable to MPR for OSPF, since it more naturally fits with the > concept of OSPF DR with fewer changes needed to OSPF packets, and > because it offers opportunities to optimize database synchronization > techniques. > > Specifically, some researchers (e.g., [10]) have shown simulation > results that show smaller size relay node sets when using CDS, > although in the author's opinion, this evidence may be > scenario-dependent and does not strongly favor one or the other. It > has been argued that CDS algorithms are potentially simpler as well, > since the decision to forward is not based on the originator of the > previous transmission. CDS may not forward along min-hop paths from > the message originator, although the difference in path length is > probably only one hop, if at all, and methods may exist to allow > min-hop flooding (e.g., [10]). > > If a node is self-selecting itself as a CDS, it most likely does so > with an assumption that neighbors are running the identical or > similar algorithm (in much the same way that the distributed > computation of Dijkstra's algorithm requires that all nodes > consistently apply it). In a MANET environment, some nodes may not > be as willing to select themselves as CDS, due to issues such as > energy reserve. Richard Ogier suggested in [5] that the Router > Priority field may be used to indicate "willingness" to relay traffic > and become a CDS node, but there is no specific description of how > this might work. Likewise, it is not clear how sensitive a CDS > self-selection algorithm would be to neighbors using consistent > algorithms, and hence, how easy it would be to evolve the heuristics > in an incremental deployment scenario. OSPF requires all nodes to run the same shortest-path algorithm, so requiring all nodes to run the same CDS algorithm is consistent with OSPF's philosophy. > > > > > Henderson (ed.) Expires April 13, 2005 [Page 10] > > Internet-Draft Summary of MANET OSPF Proposals October 2004 > > > Related to the issue of knowing the ROS is the issue of optimized > database synchronization. Another benefit of CDS or MPRs that know > their ROS is that these "special nodes" can take responsibility for > synchronization, much as an existing OSPF DR, rather than requiring > pair-wise synchronization between nodes. > > Although there are several heuristics for CDS construction that have > been proposed, one interesting one presented by INRIA (in [9]) can be > used to transform the set of MPRs into a CDS, if the nodes have some > agreed-upon knowledge of the total-order of the network (such as > increasing router ID). Ogier has done some simulation evaluation of > this algorithm in [10] and shown simulation results that it performs > worse than an algorithm based on two-hop neighbor information. I also want to point out that MPR selection involves *more* than 2-hop neighbor information, since each node computes its MPRs based on 2-hop neighbor information and then informs its neighbors of its MPR selection (so the selection of an MPR may depend on information about nodes that are 3 hops from the MPR itself). The CDS algorithms that I am considering depend only on 2-hop neighbor information. Also, having to first compute MPRs and then inform neighbors of the selection results in slower response to topology changes. > > > 3.2.1.5 Summary > > In the past, there has been simulation evidence presented that > favored MPRs over CDS, and vice versa, in terms of bandwidth > efficiency. In the absence of better data, it is the author's > opinion that, from the standpoint of bandwidth efficiency, MPRs > versus CDS will not make a whole lot of difference, especially when > metrics like robustness are considered that might favor some > redundancy in transmissions anyway. Both techniques seek to minimize > as much as possible the number of transmissions required to > disseminate the information, and different scenarios will yield > different winners, but in most cases, the differences seem to be a > few percent. Instead, the design decision should probably be driven > by which mechanism fits best (is least disruptive) to the existing > OSPF implementation. > > There have been arguments put forward, principally by Richard Ogier, > that CDS-based flooding is a better fit for OSPF than is MPR-based, > because CDS selection algorithms do not necessarily require changes > to OSPF message formats, because CDS is analogous to Designated > Router, because they may have simpler construction algorithms (for > this point, the author has not seen any proof), and because the fact > that a CDS does not care about the originator of a message, which may > help if the database synchronization procedures are ever optimized > for a MANET. Therefore, in the author's opinion, despite not having > a concrete CDS-based proposal on the table, the OSPF MANET design > team should consider this issue more carefully. > > 3.2.2 Discussion of reliability > > It seems to the author that the decision to focus on reliable > mechanisms first is non-contentious. The author has suggested > partiality to mechanisms that allow the introduction of a periodic, > non-acked LSA dissemination mode in the future. > > > > Henderson (ed.) Expires April 13, 2005 [Page 11] > > Internet-Draft Summary of MANET OSPF Proposals October 2004 > > > Richard Ogier has proposed that unreliable (periodic) operation may > be a hybrid option of an overall reliable mechanism. A Boeing > simulation study described in [7] suggested that it may be difficult > to correctly estimate the need to be in one mode or another. Since > that time, Richard Ogier has revised his proposal in this regard, as > discussed in Section 5 of [5]. Richard's current proposal is not > based on receiver suppression of ACKs but instead is sender-based and > suggests setting a new option bit in the header to make the LSA > "non-ackable" within the wireless domain whenever new LSAs are being > generated fast enough (i.e., close to MinLSInterval), with hysteresis > applied to avoid flapping between modes. > > Baker suggested the use of next-hop reflooding as an implicit ACK in > [1], although Ogier pointed out that this only applied to nodes in > the relay set; non-relay nodes still have to ACK. > > In Section 6 of [5], Richard Ogier suggests a reliable flooding > technique based on modification of Database Description (DD) packets. > It calls for special nodes (either CDS nodes or MPR nodes) to > periodically broadcast headers of all the LSAs for which it is It should be clarified that these LSAs headers are contained within DD packets that are broadcast to all neighbors periodically (similar to the sequence numbers packets of IS-IS). > > responsible for forwarding, and for all other nodes to broadcast a DD > packet with the header of its own router LSA. This is in contrast to > unreliable flooding of the LSAs themselves. Nodes that detect a > missing LSA can still use the LSR to request it, after some backoff > time. This is analogous to IS-IS Complete Sequence Number (CSN) > packets [11]. The technique is in contrast to the OLSR-like approach > in the Boeing proposal, which periodically refloods all LSAs. > Variations of this approach are possible and discussed by Richard > Ogier, such as repeating the original LSA transmission multiple > times, or CDS redundancy. INRIA also proposed such a mechanism of > periodic informational database signature broadcasts in [6]. > > Last, it should be pointed out (as Richard has) that the selection of > RNS sets is not completely independent of the decision whether LSA > dissemination is reliable or periodic. A purely OLSR-style MPR RNS > is susceptible to some lost packets when used in a reliable mode, > unless non-relay nodes are used as backups, as is proposed for the > Cisco overlapping relays technique. > > 3.3 Neighbor discovery and synchronization > > This section discusses the process of neighbor discovery, adjacency > forming, and database synchronization. > > In a MANET, the number of neighbors can become large, causing > quadratic scaling problems. Fred Baker suggests in [1] that the > number of adjacencies might be reduced. More recently, the proposal > by Cisco advocates the use of differential or incremental Hellos > > > > Henderson (ed.) Expires April 13, 2005 [Page 12] > > Internet-Draft Summary of MANET OSPF Proposals October 2004 > > > (also suggested by the MANET TBRPF protocol). Some simulations > conducted by Boeing and discussed in [7] suggest that differential > Hellos contribute second-order savings in bandwidth, but the benefits > might actually be larger than those described by Boeing when the > network is very dense. One potential benefit of differential Hellos > is that the Hello transmissions can be aperiodic. > > For the same reason that differential Hellos might be useful, so too > might a reduction in the number of neighbors with which a MANET node > becomes adjacent. OSPF does this already for broadcast interfaces. > Fred Baker in [1] suggested that nodes might want to limit the number > of neighbors. Richard Ogier in [5] also suggested that if there are > special nodes such as Multipoint Relays (MPRs) and Connected > Dominating Sets (CDS) in the network, that non-relay nodes might want > to synchronize only with these relay nodes (Ogier redefined the > concept of adjacency in this context). When using unreliable > flooding as in [3], no database synchronization occurs; nodes do not > progress past state 2-Way on a MANET interface. It would be good to point out what happens if the periodic DD packet method is used for reliable flooding. In this case (similar to IS-IS), a new neighbor of a CDS node (or MPR) will receive the periodic DD packets and send a LS Request if the CDS node has a more recent LSA. This is similar to Clausen's proposal (both are inspired by IS-IS) but is simpler and closer to OSPF. Regards, Richard > > > Taking the synchronization process a step further, Thomas Clausen and > INRIA suggested in [6] that a much more compact representation of > OSPF databases than an enumeration of LSA headers might be possible > using signatures (hashes) of parts of the OSPF database. For > example, nodes could compare top-level signatures of their database, > and only if they differed would additional signatures start to be > compared, until the discrepancy was narrowed down. The draft > describes an algorithm called Tunstall Splitting to generate prefix > signatures of different parts of the database, which can be further > segregated by age of the LSAs. _______________________________________________ Ospf-wireless-design mailing list Ospf-wireless-design@lists.ietf.org https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
- [Ospf-wireless-design] new material to review and… Henderson, Thomas R
- Re: [Ospf-wireless-design] new material to review… Acee Lindem
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- Re: [Ospf-wireless-design] new material to review… Richard
- RE: [Ospf-wireless-design] new material to review… Henderson, Thomas R
- Re: [Ospf-wireless-design] new material to review… Acee Lindem
- Re: [Ospf-wireless-design] new material to review… Thomas Heide Clausen
- Re: [Ospf-wireless-design] new material to review… Madhavi W. Chandra
- Re: [Ospf-wireless-design] new material to review… Richard
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- Re: [Ospf-wireless-design] new material to review… Acee Lindem
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- RE: [Ospf-wireless-design] new material to review… Thomas Heide Clausen
- Re: [Ospf-wireless-design] new material to review… Madhavi W. Chandra
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- RE: [Ospf-wireless-design] new material to review… Henderson, Thomas R
- RE: [Ospf-wireless-design] new material to review… Thomas Heide Clausen
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- RE: [Ospf-wireless-design] new material to review… Henderson, Thomas R
- RE: [Ospf-wireless-design] new material to review… Abhay Roy
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- RE: [Ospf-wireless-design] new material to review… Henderson, Thomas R
- RE: [Ospf-wireless-design] new material to review… Henderson, Thomas R
- Re: [Ospf-wireless-design] new material to review… Madhavi W. Chandra
- Re: [Ospf-wireless-design] new material to review… Joe Macker
- RE: [Ospf-wireless-design] new material to review… Henderson, Thomas R
- Re: [Ospf-wireless-design] new material to review… Joe Macker