From rick.taylor@cassidian.com Fri Dec 2 01:26:09 2011 Return-Path: X-Original-To: manet@ietfa.amsl.com Delivered-To: manet@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BA79F21F96FC for ; Fri, 2 Dec 2011 01:26:09 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IJG4gZxlE-cn for ; Fri, 2 Dec 2011 01:26:09 -0800 (PST) Received: from mail-dotnet4.eads.net (mail-dotnet4.eads.net [193.56.40.77]) by ietfa.amsl.com (Postfix) with ESMTP id 200C521F973E for ; Fri, 2 Dec 2011 01:24:55 -0800 (PST) Received: from unknown (HELO fr-gate2.mailhub.intra.corp) ([53.154.16.34]) by mail-dotnet4.eads.net with ESMTP; 02 Dec 2011 10:24:50 +0100 Received: from f8562vs5.main.fr.ds.corp ([10.37.8.22]) by fr-gate2.mailhub.intra.corp with Microsoft SMTPSVC(5.0.2195.7381); Fri, 2 Dec 2011 10:24:50 +0100 Received: from f8561vs4.main.fr.ds.corp ([10.37.8.21]) by f8562vs5.main.fr.ds.corp with Microsoft SMTPSVC(6.0.3790.4675); Fri, 2 Dec 2011 10:24:50 +0100 Received: from SUKNPT8108.cogent-dsn.local ([10.81.0.121]) by f8561vs4.main.fr.ds.corp with Microsoft SMTPSVC(6.0.3790.4675); Fri, 2 Dec 2011 10:24:50 +0100 Received: from SUKNPT8106.cogent-dsn.local ([10.80.1.216]) by SUKNPT8108.cogent-dsn.local with Microsoft SMTPSVC(6.0.3790.4675); Wed, 30 Nov 2011 15:59:08 +0000 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.5 Date: Wed, 30 Nov 2011 16:00:59 -0000 Message-ID: <7B31B0093014224A843C10C0CCE92AC1029D95A2@SUKNPT8106.cogent-dsn.local> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: RFC5444 packet sequence numbers and acknowledgement Thread-Index: AcyveUDKRuAV9mU9TcyrfjLNZwnrrA== From: "Rick Taylor" To: X-OriginalArrivalTime: 30 Nov 2011 15:59:08.0404 (UTC) FILETIME=[FE491340:01CCAF78] X-TM-AS-Product-Ver: SMEX-8.0.0.4194-6.500.1024-18554.006 X-TM-AS-Result: No--15.247000-0.000000-31 X-TM-AS-User-Approved-Sender: Yes X-TM-AS-User-Blocked-Sender: No Subject: [manet] RFC5444 packet sequence numbers and acknowledgement X-BeenThere: manet@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Mobile Ad-hoc Networks List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 02 Dec 2011 09:26:09 -0000 Hi, I have been taking a close look at RFC5444 for use in MANET routing protocols, using the OLSRv2 and DLEP drafts as usage guides and have a query regarding acknowledgements. DLEP in particular uses specific Message TLVs to acknowledge receipt of messages, i.e. Neighbour Up --> Neighbour Up ACK. What confuses me however is that RFC5444 packets can have a sequence number, but there appears to be no guidance on the use of packet TLVs to request or supply acknowledgement to the receipt of a packet? Now I understand that message level acknowledgement is semantically different from packet level, as in "I have not only received your packet, but also understood your message and processed it", but I am left wondering if there is a case for a generic "I have received your packet and delivered its contents to the relevant protocol stacks" packet TLV that can be added to any reply packets. I also understand that some protocols do not care if some messages are not delivered or delivered out of order, but sometimes protocols do care, and is the correct approach to add matching message_ACK TLVs for those messages, rather than adding a common mechanism that covers "One or more of the messages in this packet require acknowledgement, please respond"? I don't want to open a huge discussion over selective ACKs, NACKs, windowing, throttling, etc. as my gut reaction would be "send your packets via a more reliable protocol", but in the case of one or two messages of many within a protocol requiring acknowledgement, I feel doubling-up message TLVs seems wasteful. Regards, Rick Taylor Software Engineer, Mobile IP Node Cassidian Systems From charles.perkins@earthlink.net Thu Dec 15 14:48:05 2011 Return-Path: X-Original-To: manet@ietfa.amsl.com Delivered-To: manet@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D6C5811E80A5 for ; Thu, 15 Dec 2011 14:48:05 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.598 X-Spam-Level: X-Spam-Status: No, score=-2.598 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, OBSCURED_EMAIL=0.001] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hqQTxuauaVcW for ; Thu, 15 Dec 2011 14:48:04 -0800 (PST) Received: from elasmtp-banded.atl.sa.earthlink.net (elasmtp-banded.atl.sa.earthlink.net [209.86.89.70]) by ietfa.amsl.com (Postfix) with ESMTP id 3A15511E808A for ; Thu, 15 Dec 2011 14:48:03 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=dk20050327; d=earthlink.net; b=k5TP3efYdCAC5nsMEqZctNM/F1ts+P64bZTsvRnfugRdtK46pValgg3m7iQKGp8I; h=Received:Message-ID:Date:From:Organization:User-Agent:MIME-Version:To:CC:Subject:Content-Type:Content-Transfer-Encoding:X-ELNK-Trace:X-Originating-IP; Received: from [138.111.58.2] (helo=[172.17.96.31]) by elasmtp-banded.atl.sa.earthlink.net with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.67) (envelope-from ) id 1RbK5m-0007O5-Jq; Thu, 15 Dec 2011 17:47:59 -0500 Message-ID: <4EEA791B.2070305@earthlink.net> Date: Thu, 15 Dec 2011 14:47:55 -0800 From: "Charles E. Perkins" Organization: Wichorus Inc. User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:8.0) Gecko/20111105 Thunderbird/8.0 MIME-Version: 1.0 To: jch@pps.jussieu.fr Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-ELNK-Trace: 137d7d78656ed6919973fd6a8f21c4f2d780f4a490ca6956d5d4673fe7faad86fad351144eca22c5bb9c577ad0438f41350badd9bab72f9c350badd9bab72f9c X-Originating-IP: 138.111.58.2 Cc: Manet Subject: [manet] Babel (RFC 6126) questions X-BeenThere: manet@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Mobile Ad-hoc Networks List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 15 Dec 2011 22:48:06 -0000 Hello Julius, I have looked at Babel, which seems to be very interesting work. While reading the RFC, I started to wonder about various aspects of the protocol. I probably have missed some important points, but anyway I hope you would not mind answering some questions and comments. ========================================================= - The initial discussion doesn't properly account for multidimensional metrics = for metrics with continuous values, no total order = to fit the discussion, need to reformulate DSDV metric. For instance, [((2^96)/(seq.number)) + (# of hops)] would probably work for networks with diameter < 2^32 and 32-bit sequence numbers. Let's call that metric M_cep. Later in the document, the proper 2-dimensional DSDV metric is introduced and it seems to work well for Babel also. But until that time, we need a single-dimensional metric in order to apply to the examples. - BGP feasibility criterion does not seem at all drastic ...? - Definition of "DSDV-feasibility": "a route is feasible only when its metric at the local node would be no larger than the metric of the currently selected route, i.e., an announcement carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A)" - Using M_cep, the feasibility condition works. - Definition of "Babel-feasibility": "An update sent by a neighbour B of A is feasible when the metric D(B) advertised by B is strictly smaller than A's feasibility distance, i.e., when D(B) < FD(A)." - "Suppose that node A obeys DSDV-feasibility; then D(A) is nonincreasing, hence at all times D(A) <= FD(A)" --> This leads one to believe that at some times they are not the same, so that at some times A has not advertised its best route to the destination. --> Then the next paragraph does make sense. - However, note that node A is prevented from accepting a feasible update from B in many circumstances -- namely whenever D(B) < FD(A) but (C(A, B) + D(B)) > D(A) - This definition means that the language in the document is nonintuitive, and thus error prone. As an example, the last paragraph in section 2.4 does NOT state whether or not node A has accepted announcement D(B), and so one has to imagine additional conditions which were not explicitly stated in order to maintain consistency. I guess it has to do with keeping track of multiple feasible routes in case one goes bad. In this case, maybe in order to avoid wrong intuition, it would be reasonable to explicitly state that feasible route updates can be used if needed in the future even if they do not improve D(A). - The first figures in section 2.5 do not properly represent DSDV-feasibility when metric M_cep is used. - "Note that while sequence numbers are used for determining feasibility, they are not necessarily used in route selection: a node will normally ignore the sequence number when selecting a route" --> This doesn't properly account for metric M_cep --> Basically, it is a mistake to ignore the sequence number since the almost inevitable result is lengthier convergence - In section 2.8, it would seem better for A to observe that B is its next hop to C, and for corrective action to be taken. Moreover, I am not yet persuaded that this consequence results from the prefix lengths. - I didn't see the difference between asking for a new sequence number from a destination, versus sending a RREQ including a flag requiring an RREP from the destination. And, I didn't see the advantage of prohibiting intermediate nodes to send "feasible" RREPs. - In section 3.5.1, the sequence number has to be checked even for retractions. An old retraction is not feasible if the same neighbor has advertised a more recent feasible route. Or else one must assume that packets from neighbors are always received in order. - The suggestion to enforce hold times results from the argument in Section 2.8 which doesn't seem bulletproof to me. I reckon the node(s) receiving the retraction will trigger an update to the retractor if they have another feasible route. - I guess that the definition of "unfeasible route" is one like that specified in section 3.5.5. - "routes with a small metric should be preferred over routes with a large metric;" --> this is the definition of metric... - "switching router-ids should be avoided" --> compared to what? - "routes through stable neighbours should be preferred over routes through unstable ones;" --> requires definition of unstable neighbor - "stable routes should be preferred over unstable ones" --> requires definition of unstable route! - "switching next hops should be avoided" --> compared to what? For these points, I think it's appropriate to keep in mind that measuring route stability is quite problematic with anything more than very slow mobility. DSDV had various problems with this. - I gather that "seqno requests" replace DSDV/AODV RREQ. Neither section 3.8.1.1 nor section 3.8.1.1 can be used by nodes that have not yet acquired routes to any destinations. This means that there is a problem for the network to initially be formed: From section 3.8.1.2: "When a node receives a seqno request for a given router-id and sequence number, it checks whether its routing table contains a selected entry for that prefix; if no such entry exists, or the entry has infinite metric, it ignores the request." ================================================================ Regards, Charlie P. From jch@pps.jussieu.fr Fri Dec 16 09:08:24 2011 Return-Path: X-Original-To: manet@ietfa.amsl.com Delivered-To: manet@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E442021F84D7 for ; Fri, 16 Dec 2011 09:08:24 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.161 X-Spam-Level: X-Spam-Status: No, score=0.161 tagged_above=-999 required=5 tests=[AWL=2.409, BAYES_00=-2.599, HELO_EQ_FR=0.35, OBSCURED_EMAIL=0.001] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UcSwJhrleoij for ; Fri, 16 Dec 2011 09:08:24 -0800 (PST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by ietfa.amsl.com (Postfix) with ESMTP id 9B82F21F8495 for ; Fri, 16 Dec 2011 09:08:23 -0800 (PST) Received: from hydrogene.pps.jussieu.fr (hydrogene.pps.jussieu.fr [134.157.168.1]) by shiva.jussieu.fr (8.14.4/jtpda-5.4) with ESMTP id pBGH77j3078267 ; Fri, 16 Dec 2011 18:07:20 +0100 (CET) X-Ids: 168 Received: from lanthane.pps.jussieu.fr (lanthane.pps.jussieu.fr [134.157.168.57]) by hydrogene.pps.jussieu.fr (Postfix) with ESMTPS id 5E393C12DD; Fri, 16 Dec 2011 18:07:06 +0100 (CET) Received: from jch by lanthane.pps.jussieu.fr with local (Exim 4.77) (envelope-from ) id 1RbbFS-0006M2-6n; Fri, 16 Dec 2011 18:07:06 +0100 From: Juliusz Chroboczek To: "Charles E. Perkins" References: <4EEA791B.2070305@earthlink.net> Date: Fri, 16 Dec 2011 18:07:06 +0100 In-Reply-To: <4EEA791B.2070305@earthlink.net> (Charles E. Perkins's message of "Thu, 15 Dec 2011 14:47:55 -0800") Message-ID: <7ity50qwcl.fsf@lanthane.pps.jussieu.fr> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Miltered: at jchkmail.jussieu.fr with ID 4EEB7ABB.002 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)! X-j-chkmail-Enveloppe: 4EEB7ABB.002/134.157.168.1/hydrogene.pps.jussieu.fr/hydrogene.pps.jussieu.fr/ Cc: Manet Subject: Re: [manet] Babel (RFC 6126) questions X-BeenThere: manet@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Mobile Ad-hoc Networks List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 16 Dec 2011 17:08:25 -0000 Pleased to meet you, Charles. I've spent many a happy hour over your papers. > I have looked at Babel, which seems to be very interesting work. Thanks for the kind words. It would be great if some of my ideas could be useful to the Manet group. > While reading the RFC, I started to wonder about various aspects of > the protocol. I'll treat your individual comments in detail below. Before I do, it is worthwile to spell out three important design criteria that I used in Babel: 1. Babel is carefully optimised for simplicity of implementation. In particular, when designing Babel I rejected any feature that I couldn't implement by myself over the week-end. Should I have allowed myself more (notably kernel-side support), Babel would have ended up much more similar to AODV, and perhaps would I have used AODV in the first place. This discipline has one pleasant consequence, which is that the "babeld" sample implementation is portable to Linux since 2.4 and to some BSD variants; in particular, it takes 20 minutes to set up a Babel router using OpenWRT, even on hardware that's only supported by old kernel versions. 2. Babel is a proactive protocol, and periodic route dumps are compulsory. At the core of Babel, there's a nucleus similar to RIP (albeit with an explicit Hello/IHU subprotocol). While this means that an idle Babel router causes a moderate amount of traffic, it also implies that any deadlock will be resolved by the next broadcast. This allows me to ignore some of the "never happen in practice" edge cases that you rightly mention -- if they do actually happen, heck, you'll just wait 20 seconds for the next periodic broadcast. It also solves the problem of bootstrapping. 3. Babel is derived from DSDV, EIGRP and AODV. The basic approach was to start with DSDV, and steal ideas freely from EIGRP and AODV whenever I felt that DSDV was being suboptimal. (I've tried to be careful with giving credit, please let me know by private mail if you feel I haven't been diligent enough.) > ========================================================= > - The initial discussion doesn't properly account for > multidimensional metrics > = for metrics with continuous values, no total order > = to fit the discussion, need to reformulate DSDV metric. > For instance, [((2^96)/(seq.number)) + (# of hops)] > would probably work for networks with diameter < 2^32 > and 32-bit sequence numbers. Babel distinguishes between the metric m (which is just the number of hops in your particular example, but can be ETX or a weird experimental interference-sensitive value), and the distance d = (s,m) (a two- dimensional space ordered lexicographically). Metrics are used by route selection, distances are used for determining feasibility. This is what I feel is one of the main innovations in Babel w.r.t. DSDV and AODV -- the fact that seqnos are not used for route selection. More about this below. > - "Suppose that node A obeys DSDV-feasibility; then D(A) > is nonincreasing, hence at all times D(A) <= FD(A)" > --> This leads one to believe that at some times they > are not the same, so that at some times A has not > advertised its best route to the destination. That's right. Small fluctuations in the metric, as well as seqno increases, don't necessarily trigger sending an update (second paragraph of 3.4.1). (With ETX, small fluctuations in the metric happen basically at every hello exchange, so this is an important feature. An alternative would be to artificially smoothen the metric, but the current solution is both simpler and more elegant.) > - This definition means that the language in the document > is nonintuitive, and thus error prone. [...] In this case, > maybe in order to avoid wrong intuition, it would be > reasonable to explicitly state that feasible route > updates can be used if needed in the future even if > they do not improve D(A). You're absolutely right, point taken. > - The first figures in section 2.5 do not properly represent > DSDV-feasibility when metric M_cep is used. Yep. We're only going to introduce seqnos later in that section. > - "Note that while sequence numbers are used for determining > feasibility, they are not necessarily used in route selection: a node > will normally ignore the sequence number when selecting a route" > --> This doesn't properly account for metric M_cep > --> Basically, it is a mistake to ignore the sequence number > since the almost inevitable result is lengthier convergence As mentioned above, this is what I feel is one of the main innovations in Babel. With non-trivial metrics (ETX, or the weird experimental thing used in Babel-Z), or when various nodes use different time constants, there is not necessarily a strong correlation between higher seqnos and better routes. For that reason, Babel ignores seqnos in route selection. (Earlier versions of the sample implementation did take seqnos into account, and that was found to be a mistake. The RFC is ambiguous in its advice on this subject, since it reflects an earlier stage of my understanding.) > - In section 2.8, it would seem better for A to observe that > B is its next hop to C, and for corrective action to be taken. > Moreover, I am not yet persuaded that this consequence results > from the prefix lengths. I fully agree that this is the least satisfactory part of Babel. If you have any good ideas for an alternative algorithm, I'm very much interested. > - I didn't see the difference between asking for a new sequence > number from a destination, versus sending a RREQ including > a flag requiring an RREP from the destination. And, I didn't > see the advantage of prohibiting intermediate nodes to send > "feasible" RREPs. Sorry if that's not stated clearly enough. Intermediate nodes are allowed to satisfy a seqno request ("send a feasible RREP" in AODV terminology). What they are not allowed is increasing the seqno -- any seqno must be a copy of a seqno produced by the source. (As a side note, the AODV terminology is somewhat misleading when applied to Babel. Due to the proactive nature of the protocol, route updates are not necessarily replies to a request.) > - In section 3.5.1, the sequence number has to be checked > even for retractions. An old retraction is not feasible if > the same neighbor has advertised a more recent feasible route. > Or else one must assume that packets from neighbors are > always received in order. Recall that a node can reboot and lose its state, including its seqno number. (The sample implementation attempts to save its seqno to stable storage, but routers can and do crash, and we also run babeld on routers with no useful stable storage.) In order to clear any old state from the network, we want a retraction to be obeyed unconditionally. So yes, we assume that link-local packets don't routinely get reordered. In the unlikely case they do get reordered (e.g. due to FSTP reconver- gence or to link-layer ARQ), the next periodic broadcast will cause us to recover (note that retractions do not update the feasibility distance). (Please let me know if you know of other sources of link-local packet reordering, whatever the link technology, and whether you have any statistics on how often they happen.) > - "routes with a small metric should be preferred over routes with a > large metric;" > --> this is the definition of metric... No, Babel is carefully designed to decouple the local route-selection policy from what happens on the wire. The metric is what is carried by the updates, and a local policy can override the metric. Compare this to BGP, where the path length is often overridden by local policy. > For these points, I think it's appropriate to keep in mind that > measuring route stability is quite problematic with anything more than > very slow mobility. I know that now (after trying and failing to use route stability), but I didn't at the time I wrote the RFC. I would word this paragraph differently now. > Neither section 3.8.1.1 nor section 3.8.1.1 can be > used by nodes that have not yet acquired routes to > any destinations. This means that there is a problem > for the network to initially be formed: Bootstrapping is done by waiting for a periodic update. The protocol also has provisions for sending a wildcard request at boot (last paragraph of 3.8.1.1 and 3.8.2.4), but unless it's done carefully, it causes broadcast storms when a whole network reboots. (Again, I'd word these sections differently now.) Thanks again for your comments, and please let me know if you have any further suggestions. -- Juliusz P.S. Permission to forward your mail to the babel-users list?