Subject: [RTG-DIR] Rtg Directorate review of draft-chroboczek-babel-routing-protocol-04

From: Ross Callon <[email-masked]>
Date: Fri, 1 Oct 2010 12:49:47 -0400

Hello.
I have been selected as the Routing Directorate reviewer for this draft. The Routing Directorate seeks to review all routing or routing-related drafts as they pass through IETF last call and IESG review. The purpose of the review is to provide assistance to the Routing ADs. For more information about the Routing Directorate, please see http://www.ietf.org/iesg/directorate/routing.html
Although these comments are primarily for the use of the Routing ADs, it would be helpful if you could consider them along with any other comments that you receive, and strive to resolve them through discussion or by updating the draft.
Document: draft-chroboczek-babel-routing-protocol-04
Reviewer: Ross Callon
Review Date: October 1, 2010
Intended Status: Experimental
Summary:
I have some minor concerns about this document that I think should be resolved before publication.
Comments:
This is a very interesting document which describes an experimental protocol with interesting capabilities. Given the complexity of a routing protocol, this is well written and relatively easy to understand.
It is appropriate that this is experimental. It is not clear to me why the world needs another routing protocol, although experiments can be useful. There are a number of SHOULD's in the document which are entirely appropriate as SHOULD's for an experimental protocol, but which IMHO would want to become either MUST's or be removed for a standards track document.

I believe that this document should have the standard warning that it is not a product of the IETF and is not a candidate for standardization at any level.

Major Issues:
None.
Minor Issues:
- General: It might be worth mentioning somewhere that loop-free routing does not strictly speaking ensure that one or more individual data packets won't visit the same node twice (which some might think of as a loop). For example, suppose that routing could respond infinitely fast and always took the shortest path to the destination. Suppose furthermore that the entire network consisted of four nodes (A, B, C, D), and four links (A-B, B-C, C-D, and A-D). Suppose that node A has a packet destined for node C, and selects the path via B for a particular data packet (therefore forwarding the data packet from A to B). As the packet arrives at B, the link B-C fails. In this case since routing is instant and always correct, node B knows to forward the packet back to A, and A then knows to forward it to D (which forwards it to C). Thus while routing was perfect and never had a network-wide set of forwarding tables that created a loop, packets may still travel on a path, during network changes, that some might call a loop.

Similarly, with the Babel protocol, if a node prefers an update with a longer distance but newer sequence number (apparently true as explained in 3.5.1), then a similar issue could occur even in the absence of topology changes when a node originates an update with a new (larger) sequence number, if the update propagates much more quickly on some paths than on others (for example, due to one node which propagates routing updates very slowly, but which is on the shortest path from some points in the network to the node originating the update). In this case if the routing updates propagate faster than packets are forwarded (possible with large packets over small links if the routers give preference to routing updates - for example under the principle that there isn't much point in forwarding a packet if it is going in the wrong direction), then some packets might start off following the shortest path, then an update with a newer sequence number but following a longer path might overtake the packets causing them to be routed over the different longer path, then the update following the shortest path might overtake the packets causing them to return to the original shortest path. If we assume that the periodicity of sequence number changes is much slower than the time required to deliver a data packet, then any such looping will be brief and transitory (and the packets will be delivered after a short loop, assuming TTL doesn't expire).

- Section 1.1, first paragraph: I don't think that the Babel routing protocol is "black hole" free, at least if you define "black hole" as a router in a network that has no route, for some period of time, to a particular destination. I do understand that black holes will not persist indefinitely. Specifically, you describe events where a node notices that it has no feasible route to a particular destination. Isn't this the definition of "black hole"? I do understand that at this point it will *try* to send an explicit request to the source for a new sequence number -- and that somewhere in the network will be a router which is able to send the explicit request. However, it will take some time for the request to arrive and for the route announcement (with updated sequence number) to propagate back to the node that was without a feasible route. Doesn't this mean that black holes will not persist indefinitely, but can occur for some period of time? I do also understand that you avoid counting to infinity, which is of course a very good thing to avoid (and which makes possible the "fairly arbitrary metrics" which you are able to use).

- Section 1.1, third bullet item (that reads "any routing black-holes that may appear after a mobility event are corrected in a time at most proportional to the network's diameter."). I think that this is true *unless* the set of one or more "explicit requests to the source for a new sequence number" (described in 2.6) are all lost. Given that the requests should be repeated if an update with a new sequence number doesn't show up, this seems to be as close to reliable delivery as you can get in this case (since there could be many nodes which are requesting the updated sequence number at the same time, and there might be no reverse path other than flooding available for many or most of them - eg due to same failure which causes the infeasibility event). However, if they all happen to be lost, then you might need to wait for a timeout at the source of the route advertisement to cause the new sequence number to occur.

- Section 1.2: Under "limitations", you could mention that since Babel is a distance vector routing protocol it does not provide each router with a full map of the topology. This prevents it from being applicable in certain traffic engineering applications (reference OSPF-TE and IS-IS-TE) and potentially in PCE applications.

- Section 2.6, second paragraph: "When a node detects that it is suffering from a potentially spurious starvation, it sends an explicit request to the source for a new sequence number". It is probably worth mentioning that in general for some or even many nodes there will be no way to route the explicit request back to the source, but that for each possible failure there will be at least one (and possibly more) nodes that experience spurious starvation but nonetheless have a (non-feasible but shortest available) route that will work to route a packet back to the source. I can see that it is undesirable to attempt to send this packet reliably, since many of the packets won't be routable, and probably more importantly because the same failure might cause routing in the backward direction to be similarly temporarily disrupted. However, this has the unfortunate effect that the explicit requests are not sent reliably, and at least in principle might be lost. This implies that in some cases "black holes" may exist for as long as it takes for a node to originate a routing update with an updated sequence number on its own based on timeout. These explicit requests might therefore want to be given high priority. I see in a later section that the requests SHOULD be repeated if there is no routing updated with an updated sequence number for a period of time. You might want to say this briefly (one sentence) here in 2.6. Alternately 2.6 might just want to contain a forward reference to 3.8.

- Section 3.2.1 mentions that sequence numbers are incremented whenever a node receives a request for a new sequence number. Given that these requests are not sent reliably, it is probably a good idea for the node to also update its sequence number periodically, and to mention this in this section. (Assuming that sequence numbers already area updated periodically based on timeout, this becomes an editorial comment.)

- In section 3.2.6 you talk about the table of pending segno requests. I apologize if I am just being slow but when first reading this I managed to lose context of what this table is for. After finishing the paper, I think that this section relates to forwarding the explicit requests for a node to increase its sequence number. However, if this is the case I don't understand the triplet (neigh, seqno, neighbour). First of all what is "neigh" and what is "neighbor". Secondly, shouldn't the node or prefix for which we are requesting an updated sequence number be included in this somewhere? Some more explanation seems to be needed for this section.

- Section 3.7.4: "Since Babel does not suffer from routing loops, split horizon with poison reverse SHOULD NOT be used." I am not sure that anyone (other than I) remembers this, but I was the one who originally came up with the idea of poison reverse (which I just blurted out at a RIP WG meeting, and then later regretted that I hadn't patented the idea first). The reason for poison reverse with RIP is that there was previously no way to withdraw a route, and thus the only way to say that a route had gone away was to simply not advertise it, and wait for it to timeout from your neighbors. This was of course horridly slow. Poison reverse is therefore simply the equivalent to your route withdrawal. As such this sentence doesn't seem to make much sense.

Nits:
- Abstract: Strictly speaking, Babel is not quite loop-free (as you explain in the introduction). Perhaps "nearly loop-free" might be more precise. (the same issue applies to the first sentence of section 2).

- Section 1.1, first sentence: Later on you explain situations where there could be very short-lived loops or black holes (at least by my understanding of the term "black hole"). Thus perhaps rather than "it does not cause routing pathologies such as" you might say "it strongly limits the duration of routing pathologies such as".

- Section 1.2, first paragraph, last sentence, you probably should include IS-IS in the list of other routing protocols.

- Very minor, section 2.4, I am pretty sure that "parametrised" is misspelled. I think that it should be either "parameterised" or "parameterized" (-ize in US use, and apparently either -ise or -ize in England and other English speaking countries depending upon which country and which dictionary you use).

- In section 2.5 you introduce the notion of sequence numbers, so that an update is feasible if either the sequence number is larger (newer), or the distance from the next hop to the destination (originator of the update) is less than the previous distance from here to the destination. Do you actually prefer routes with a newer sequence number to an older route, or do you prefer routes with smaller distances to the destination, and use the sequence number only to determine feasibility? I didn't quite figure this out until section 3.5.1 (where I discovered that my original expectation is right). You might want to briefly clarify this in section 2.5.

- Section 3.5.2, "gove" should be "give"

Note:
- You are entirely correct in your use of MUST, SHOULD, etc notation, and it is interpreted in accordance to the status of the document. Thus, if anyone claims that they implement your protocol, then they must do the things that you list as MUST. However, since this is (appropriately) an experimental protocol, no one is required to implement it. For some reason the issue of using MUST, ... in non-standards track document keeps coming up, but you are correct in doing so.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 07 Oct 2010 18:15:17 +0200

Dear Mr. Callon,

Thank you very much for your thoughtful review of
draft-chroboczek-babel-routing-protocol-04.

I agree with most of your comments, for which many thanks.  In the
following, I'm only replying to those points that I disagree with, or
that otherwise deserve being discussed.

Please let me know whether I should produce a -05 now, or whether
I should wait for some further event.

1. Why a new protocol
*********************

> It is not clear to me why the world needs another routing protocol,
> although experiments can be useful.

While the world certainly doesn't need a new routing protocol for
stable, well-administered wired networks, Babel has been shown to be
suitable for networks built with sticks and pieces of string ("wireless
mesh networks").  Much of the research in this area (AODV/DYMO, OLSR) is
about designing protocols based on all-new principles; Babel takes the
opposite approach, by just being distance-vector with some refinements.

So please think of Babel as a proof of the statement that plain old DV
can be made to work in mesh networks.  It is certainly not meant to
compete with OSPF.

2. About blackholes
*******************

> - Section 1.1, first paragraph: I don't think that the Babel routing
>   protocol is "black hole" free, at least if you define "black hole"
>   as a router in a network that has no route, for some period of time,
>   to a particular destination. I do understand that black holes will
>   not persist indefinitely.

Agreed -- Babel ensures that blackholes will not persist indefinitely.
This is just a way of saying that Babel eventually converges to an
acceptable configuration.  I'll fix this.

(Since the draft leaves the route selection policy to the
implementation, Babel does not, in general, converge to a tree of
shortest paths, although it certainly does if route selection prefers
smaller metrics.)

> - Section 1.1, third bullet item (that reads "any routing black-holes
>   that may appear after a mobility event are corrected in a time at
>   most proportional to the network's diameter."). I think that this is
>   true *unless* the set of one or more "explicit requests to the
>   source for a new sequence number" (described in 2.6) are all lost.

You are right, this assumes that the number of requests is such that the
probability of that happening is negligible.  I have no objection to
making that explicit.

3. About requests and seqnos
****************************

As you've justly noted, the mechanisms used for avoiding starvation are
the most tricky parts of Babel.  The algorithms described in the draft
are certainly not the only ones that work; however, they are the ones
currently implemented in Babel, and they have been shown to work
reasonably well in practice.

This is to say that while improvements are doubtless possible, this
draft is meant to describe the set of algorithms currently implemented;
and I'd be unwilling to describe any behaviour in the draft unless it's
been implemented and the implementation's behaviour evaluated experimentally.

> It is probably worth mentioning that in general for some or even many
> nodes there will be no way to route the explicit request back to the
> source, but...

Seeing it written down in your words is extremely helpful.  Thanks for
this paragraph.

> - Section 3.2.1 mentions that sequence numbers are incremented
>   whenever a node receives a request for a new sequence number. Given
>   that these requests are not sent reliably, it is probably a good
>   idea for the node to also update its sequence number periodically,
>   and to mention this in this section. (Assuming that sequence numbers
>   already area updated periodically based on timeout, this becomes an
>   editorial comment.)

As explained by private mail, this is not the case -- unlike in DSDV,
a node never spontaneously increases its seqno.  I'll make that clear.

> - In section 3.2.6 you talk about the table of pending segno requests
>   [...]  I don't understand the triplet (neigh, seqno, neighbour). [...]
>   Some more explanation seems to be needed for this section.

This is a typo, as you suspected.  I'll fix and expand this section.

4. About poison reverse
***********************

> - Section 3.7.4: "Since Babel does not suffer from routing loops,
> split horizon with poison reverse SHOULD NOT be used." [...] I was the
> one who originally came up with the idea of poison reverse [...]

(Shakes hands.)

> Poison reverse is therefore simply the equivalent to your route
> withdrawal.  As such this sentence doesn't seem to make much sense.

Hmm.  I was under the impression that poison reverse is more than just
explicit retractions, since it consists in advertising a reverse
unreachable route for an unbounded amount of time.  However, I have no
strong feelings about this sentence, please let me know if you if you
insist that it should be removed.

5. About being loop-free
************************

> Nits: - Abstract: Strictly speaking, Babel is not quite loop-free (as
> you explain in the introduction).

Well, Babel is loop-free in a mesh network (only host routes) with at
most on Internet gateway.  Since this is the only case that the existing
literature on mesh networking even considers, Babel is loop-free in the
same sense as, say, DSDV or AODV/DYMO are loop-free.

> Perhaps "nearly loop-free" might be more precise. (the same issue
> applies to the first sentence of section 2)

I'll do that.

Thanks again for your review,

                                        Juliusz

---

From: Ross Callon <[email-masked]>
Date: Thu, 7 Oct 2010 19:59:54 -0400

Thanks for the response. I just wanted to quickly let you know that I am on travel, and thus won't be able to give you a detailed response for a few days (probably Sunday or Monday). 

Thanks, Ross

-----Original Message-----
From: Juliusz Chroboczek [mailto:[email-masked]] 
Sent: Thursday, October 07, 2010 12:15 PM
To: Ross Callon
Cc: Adrian Farrel; Stewart Bryant; [email-masked]
Subject: Re: Rtg Directorate review of draft-chroboczek-babel-routing-protocol-04

Dear Mr. Callon,

1. Why a new protocol
*********************

2. About blackholes
*******************

4. About poison reverse
***********************

(Shakes hands.)

5. About being loop-free
************************

I'll do that.

                                        Juliusz

---

From: Ross Callon <[email-masked]>
Date: Wed, 13 Oct 2010 23:41:53 -0400

Regarding whether to update the document: Strictly speaking, my authority in reviewing this document is solely as an advisor to the routing ADs. Thus it is actually up to you and the routing ADs what if anything you do with these comments. That being said, I think that it is reasonable for you to update the document based on these comments and our email exchange, and I would be very surprised if the routing ADs felt differently. Also, you might want to get this in before the ID cutoff date (which is quite soon) -- alternately you would need to wait until the IETF starts in Beijing (whether you are there or not). 

I am fine with your comments, and have only two additional points (one of which is an agreement with a proposed update from your email). 

Regarding section 3.7.4, I agree with your suggestion in your email below to remove the sentence (which is actually its own paragraph) which reads: 

   Since Babel does not suffer from routing loops, split horizon with
   poison reverse SHOULD NOT be used.

In section 3.8.2.1 (Avoiding Starvation), you specify that "In order to compensate for packet loss, a node SHOULD repeat such a request a small number of times if no route becomes feasible within a short time."  I continue to be concerned that it is possible, although admittedly a rare event, that all such requests will be lost, resulting in a stuck routing state. Of course I also see that we don't want to keep retransmitting seqno requests forever in the case that a destination has actually gone away and will never return.  It would seem to me that this sort of problem (stuck routing to the node which is still in the network) is most likely when the network is going through some sort of ugly near-partition where the network is partitioned for a very short period of time, or is almost partitioned in the sense that a link that corrects a potential partition comes up at pretty much the same time that the link that would have caused the potential partition fails. I am thinking that some discussion of this might want to be added. One possible approach might be along the lines of:

      In principle, if all seqno requests are lost, it may be possible for the 
      network to get stuck in a state where no feasible route exists to a 
      particular destination and all nodes have stopped retransmitting seqno
      requests for that destination. Depending upon operational results, future
      versions of this document might require that nodes with no feasible route
      to a particular destination, but which have neighbors who are advertising
      routes to that destination (which therefore must be unfeasible), continue
      to transmit seqno requests on a low-frequency basis until either a
      feasible route is received, or the node no longer has a neighbor
      advertising a (non-feasible) route to the destination. 

Thanks, Ross

-----Original Message-----
From: Juliusz Chroboczek [mailto:[email-masked]] 
Sent: Thursday, October 07, 2010 12:15 PM
To: Ross Callon
Cc: Adrian Farrel; Stewart Bryant; [email-masked]
Subject: Re: Rtg Directorate review of draft-chroboczek-babel-routing-protocol-04

Dear Mr. Callon,

1. Why a new protocol
*********************

2. About blackholes
*******************

4. About poison reverse
***********************

(Shakes hands.)

5. About being loop-free
************************

I'll do that.

                                        Juliusz

---

From: Stewart Bryant <[email-masked]>
Date: Thu, 14 Oct 2010 11:54:35 +0100

I agree with Ross here.

Please update the document.

Thanks

Stewart

-- 
For corporate legal information go to:

http://www.cisco.com/web/about/doing_business/legal/cri/index.html

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 18 Oct 2010 14:16:11 +0100

Juliusz

I apologize for my earlier email (I am relatively new to the AD role). 
As this is an independent  stream document the content needs to be 
agreed between you and the RFC editor. I can only request changes to the 
document. However I believe that the changes need to address Ross's 
concerns would significantly improve the document, and would request 
that you make them.

Thanks

Stewart

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 18 Oct 2010 19:48:38 +0200

> I apologize for my earlier email [...] However I believe that the
> changes need to address Ross's concerns would significantly improve
> the document

I'm not sure what you're apologising for -- your feedback is very much
appreciated.  I've got a few urgent things to do right now (October is
not the most easy time of the year for us University lecturers), but
I'll certainly submit a -05 in time for the deadline.

Ross said:

> I believe that this document should have the standard warning that it
> is not a product of the IETF and is not a candidate for standardization
> at any level.

Could you please provide me with the suitable boilerplate?

Thanks,

                                        Juliusz

---

From: Adrian Farrel <[email-masked]>
Date: Mon, 18 Oct 2010 21:42:33 +0100

Hi,

> Could you please provide me with the suitable boilerplate?

Don't worry about that. It is something that the RFC Editor will drop in 
right at the last minute if he agrees with the IESG that it should be there. 
We'll take care of suggesting it, and he'll take care of inserting it.

Cheers,
Adrian

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 18 Oct 2010 16:45:40 -0400

I believe we no longer add such warning boilerplate.  Instead, the 
document heading is clear as to what the track and intention of the 
document is.
Yes, at one time the IESG asked for such warning on all documents.

Yours,
Joel

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 26 Oct 2010 01:45:39 +0200

Dear Ross, dear all,

I have just submitted draft-chroboczek-babel-routing-protocol-05, which
implements all but two of Ross's suggestions.

Some discussion of the two exceptions follows.

> - It might be worth mentioning somewhere that loop-free routing does
> not strictly speaking ensure that one or more individual data packets
> won't visit the same node twice (which some might think of as a loop).

I've failed to do that.  On the one hand, just mentioning it in passing
has a very "oh, by the way, did I mention that" feel to it; on the other
hand, this document is clearly not the right place for an extended
chapter about the different notions of loop-freeness.  Rather than
a half-baked paragraph, I've simply decided to leave it as is.

> - Section 1.2: Under "limitations", you could mention that since Babel
> is a distance vector routing protocol it does not provide each router
> with a full map of the topology. This prevents it from being
> applicable in certain traffic engineering applications (reference
> OSPF-TE and IS-IS-TE) and potentially in PCE applications.

Since I know more or less nothing about TE, I feel a little
uncomfortable citing your suggested references.  The obvious
workaround -- just mentioning that the global topology is not flooded,
with either no further comments or the usual sentence or two about
debugging networks -- feels awkward and unconvincing.  Hence, I've
simply omitted this suggestion.

                                        Juliusz Chroboczek

---

From: Stewart Bryant <[email-masked]>
Date: Tue, 26 Oct 2010 18:57:58 +0100

> simply omitted this suggestion.
There are many applications that may wish to take advantage of the
knowledge of the topology, not just TE.

You could say:

====
Since Babel is a distance vector routing protocol it does not provide
each router with a full map of the topology. In the case where a
network application, such as TE, needs some knowledge beyond its
immediate neighborhood, Babel would need to be enhanced to deliver
that knowledge, possibly by including knowledge of the application within
the Babel protocol.

====

I have some direct experience of this. As an intellectual exercise we
decided to make notvia fast reroute work with RIP. Conventional wisdom
was that since this needed knowledge of the network topology we could not
make this work. The trick was to flood the re-route information everywhere
and by selective address filtering get RIP to do the calculation for us.

I can't remember off hand, but do you note that the normal problem
with DV, and hence the reason that we went to LS is that LS converges
much faster then DV.

All these remarks are review that you are of course free to include or
not.

When you have a version that you are happy to proceed with I will
process it through the IESG, which will be some time after the next
IETF.

- Stewart

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Oct 2010 18:30:24 +0200

> knowledge of the topology, not just TE.

I have no doubts about that; however, I have no personal experience with
such applications, and anything I know about it is pure hearsay; for
that reason, I'd be a little nervous about including anything on this
subject in a document of which I am the author.

> process it through the IESG, which will be some time after the next

I've re-read the current version, and I am happy with it.  I'd be
grateful if you could process it.

Thanks,

                                        Juliusz