Depth-First Forwarding (DFF) in Unreliable Networks
draft-cardenas-dff-14

Very many thanks for the hard work to address my Discuss points.

I hope you will find time/energy to sift through my Comments with your AD and document shepherd to apply any that would improve the document.

---

In his Routing Directorate review, Alvaro Retana asked...

> o Section 4.2 reads (last paragraph): "..if a router receives a
>   Packet with DUP = 1 (and RET = 0) that it has already forwarded,
>   the Packet is not considered looping, and successively forwarded to
>   the next router.."  I'm at a loss of why would the router forward
>   the packet if it is a duplicate of one that it has already
>   forwarded.

Ulrich helpfully responded...

> This is necessary for the following reason:
> Imagine a case where after a lost L2 ACK, DUP of the packet is set to
> 1 and a duplicate is created. The duplicate may now during its path 
> again be duplicated if another L2 ACK is lost. However, DUP is already
> set to 1, so there is no way of discerning the duplicate from the
> duplicate of the duplicate. That is not much of a problem, other than
> that loop detection is not possible after the second lost L2 ACK on the
> path of a packet.
> However, if duplicates are simply dropped, it is possible that the
> packet was actually a looping packet (and not a duplicate), and so the
> DFS would be interrupted. The problem is to make sure that this "very 
> instance" of a packet has passed a router before or not (sequence
> number is not enough; source route would be enough, but at a too high
> cost).
> In practice, we have not observed that to be a problem in deployments
> of thousands of routers in a network. There are some duplicates of 
> packets, but not in a considerable amount.

I think this somewhat subtle point would benefit from a little more
explanation in the document (perhaps just include this text).

Maybe, as well, since this is experimental, it would make a useful point
for further research.

---

Section 3 is very useful in setting the scope of the document. I wonder
whether it would be useful to make some references to examples that are
in scope, and some statements about common network types that are
immediately assumed out of scope. For example:

   o  Assumes that the underlying link layer provides means to detect if
      a Packet has been successfully delivered to the Next Hop or not
      (e.g., by L2 ACK messages).

And we can note that 802.15.4 has provision for immediate acks, but many
layer two technologies do not even have an option for assuring delivery.

---

Isn't there a tension in Section 3 between the problem of network 
density as expressed in:

   o  Is designed for networks with little traffic in terms of numbers
      of Packets per second, since each recently forwarded Packet
      increases the state on a router.  The amount of traffic per time
      that is supported by DFF depends on the memory resources of the
      router running DFF, on the density of the network, on the loss
      rate of the channel, and the maximum hop limit for each Packet:
      for each recently seen Packet, a list of Next Hops that the Packet
      has been sent to is stored in memory.  The stored entries can be
      deleted after an expiration time, so that only recently received
      Packets require storage on the router.

And the intension to support dense networks as stated in:

   o  Is designed for dense topologies with multiple paths between each
      source and each destination.

---

In Section 3

      In networks with very stable links (e.g.
      Ethernet)

I think "Ethernet" is too general a term. Many LLNs use a variety of
Ethernet.

---

I agree with other ADs that the mixture of design objectives and 
deployment-limiting assumptions in Section 3 is unhelpful. Perhaps 
separate them out into two sections and make the assumptions more
definitive as limitations?

---

The term "PAN" is used without expansion.

---

More thoughts on storage requirements and list processing...

Section 4 has:

   For each recently forwarded Packet, a router running DFF stores the
   list of Next Hops to which a Packet has been sent.  Packets are
   identified by a sequence number that is included in the Packet
   Header.  This list of recently forwarded Packets also allows for
   avoiding loops when forwarding a Packet.  Entries of the list
   (identified by a sequence number of a Packet) expire after a given
   expiration timeout, and are removed.

There is a problem with the meaning of "list" and "entry". You have a
list of lists :-)

Do you mean that the Next Hop is dropped from the list, or that the
packet's list of next hops is discarded? Should be easy to clarify the
text.

---

The start of Section 4.1 is abrupt and confusing.

   This specification requires a single set on each router, the
   Processed Set. Moreover, a list of bidirectional neighbors must be
   provided by an external neighborhood discovery mechanism, or may be
   determined from the RIB (e.g., if the RIB provides routes to adjacent
   routers, and if these one-hop routes are verified to be
   bidirectional).  The Processed Set stores the sequence number, the
   Originator Address, the Previous Hop and a list of Next Hops, to
   which the Packet has been sent, for each recently seen Packet.
   Entries in the set are removed after a predefined time-out.  Each
   time a Packet is forwarded to a Next Hop, that Next Hop is added to
   the list of Next Hops of the entry for the Packet.

It takes a while to work out "set of what?" You could rephrase for 
clarity.

---

Section 4.1

What is a "bidirectional neighbor"? One might assume that it a neighbor
to and from which data can be passed in a single hop? The text goes on
to talk about "one-hop bidirectional routes".

Is that the moral equivalent to being connected with a bidirectional
link? Probably not in the type of network you are building, so maybe
this term needs to be in the Terminology section.

---

Section 4.2

   DFF requires additional header information in each data Packet by a
   router using this specification.  This information is stored in a
   Packet Header that is specified in this document as LoWPAN header and
   as IPv6 Hop-by-Hop Options extension header respectively, for the
   intended "route-over" and "mesh-under" Modes of Operations.  

1. I think you have "route-over" and "mesh-under" reversed!
2. The first sentence doesn't parse. But also "requires" is unclear.
   I think that the information is needed on a per-packet basis by the
   receiving router, and so it encoded in the packet header.

---

Section 11 has

   A
   smaller list MAY be used, if desired, and the exact selection of the
   size of the candidate Next Hop List is a local decision in each
   router, which does not affect interoperability.

It is true that it does not affect interoperability of the protocol,
but it does affect the ability to deliver data. So it is probable that
some guidance on the "MAY" might be valuable.

---

I am curious to see no discussion of the management of this protocol
or of networks using DFF. I would imagine that since "unexpected"
things may start to happen, diagnostics would be quite useful.

Stephen's first comment, and Pete's comments have me covered.  I'd particularly like to see an answer to the question about reviews from manet, roll, and 6lowpan (though I do see Adrian's comment that a routing directorate review was done, so maybe that covers at least some of that).

I support Martin's DISCUSS on the MTU issue with adding information to packets in transit.

I would think that another metric of interest for experimentation is the overall number of transmissions needed to successfully deliver a packet using DFF as compared to the number needed when a routing protocol is employed.  This would need to incorporate the number of control messages sent as well, in some manner.

There has been a discussion with Gen-ART reviewer Dan Romascanu, and all his issues have been addressed, with the exception of one new question that was posted in e-mail on March 27th. Please take a look at that issue and respond.

Thank you for addressing my concern!

I'm balloting NO OBJECTION on this, but reluctantly as I share Stephen's concern: The writeup is not up to date and the now cognizant AD has not issued a ballot yet. I also wonder why this didn't come out of any WG, even though it was ostensibly reviewed in several. But there is nothing to indicate that it is problematic to run this experiment, so I won't bother ABSTAINing, let alone DISCUSSing it.

Overall, this is a nicely written document.  Thanks!  Couple of minor thoughts below.

"""
P_next_hop_neighbor_list is a list of Addresses of Next Hops to
 which the Packet has been sent previously, as part of the depth-
 first forwarding mechanism, as specified in Section 9.2;
"""

It seems like it would be possible to run this protocol without per-packet state, under two assumptions:
(1) The set of neighbors is preference-ordered 
(2) Communication with neighbors is bidirectional
The document seems to assume both of these.  Under these assumptions, the router could simply take a packet that arrives on interface N (in the preference ordering) and transmit it on interface N+1.  The only issue then is loop detection, which could be done by keeping a list of recently seen serial numbers, a much smaller piece of state.


"""
P_HOLD_TIME - is the time period after which a newly created or
 modified Processed Tuple expires and MUST be deleted.
"""

It's not immediately clear to me why this value is a constant.  Might it be useful for implementations to vary P_HOLD_TIME, for example, reducing P_HOLD_TIME to save space when there are many packets in flight?

- The write-up seems out of date, says "reviews should be
sought from 6lowpan, manet and roll" and that Ralph is the
AD. Did those WG reviews happen?

- Abstract: "DFF assumes...stuff" would be better as "DFF
is designed for ...when stuff" or "The design of DFF
assumes ... stuff" (Sorry, thats a total nit you can
ignore if you want, not sure why it bothers me;-)

- general: Other than for IETF organisational reasons, why
is this IPv6 only?

- general: you say how to process one packet in a router's
queue. What if that router has many queued packets, are
you saying that it ought pick one, do the DFF thing on
that and only even look at a 2nd packet when the DFF
process for the first one is complete. So I'm puzzled
that you don't mention how a DFF-capable router handles
queues. 

- general: If DFF has been "widely deployed" and you
say that then I'd expect a reference that backs that
up.

- general: If this scheme has had significant academic
review (and even the worst routing schemes have, so I
assume this non-worst one also has:-) then I'd expect at
least some reference to the academic literature. If, OTOH,
this is a reasonable routing experiment for which this is
no academic literature, then that seems even more
noteworthy. In any case, when I finally got to appendix B,
I saw some citations. I think moving those up earlier will
help, as would increasing the diversity of the author list
on the cited papers. To be honest, I read the text as
being somewhat optimistic in terms or how widely deployed
DTT might actually be.

- section 8: What happens if the parameters differ in
nodes within the same DFF routing domain?

- section 13: Starting the sequence number from 0 seems
like a bad plan (for DoS resilience). Starting from a
random number would be better.

- 14.1.2: Is OptTypeDFF experimental or what? I'm not
sure what's needed/correct there.

- section 15, I guess this means that the determination of
workable routing domain boundaries is also part of the
experiment really. Better to say that if so in 1.2. And I
think it is so myself. And FWIW, I don't think the text in
this section is that clear - you might be better off to
just say that routing domain egress/exit nodes (D and R2)
need to know or figure out somehow that they are such
nodes.

Thank you for addressing my concerns.