Subject: [manet] Re: New DSR Draft

From: Pekka Savola <[email-masked]>
Date: Tue, 2 Apr 2002 13:51:39 +0300 (EEST)

On Sat, 23 Feb 2002, Pekka Savola wrote:
> I'll try to give more concrete feedback within some weeks but I'm not sure
> if that's going to help any as the basic assumptions seem to vary quite a
> bit.

Hello,

I promised I'd come back with more comments.  Some are just my thoughts I 
tried to scribble down when reading the draft.  Hope they help..

- I'm a bit unsure what happens if a packet which has a DSR header but 
also has piggybacked data is in send/maintenance queue.  Is this possible?  
These could in some cases perhaps lead to data being delivered more than 
once to the destination.

- I didn't get a good picture which DSR options can be seen in the same 
DSR header and which not.  Also, as sections in chapter 5 list what IP 
header fields would look like when there are multiple options in a packet, 
the multi-option combinations seem to be less covered than their full 
counterparts.

Some comments based on the text.

1. Introduction

[...] Each data packet sent then carries in its header the
   complete, ordered list of nodes through which the packet will pass,
   allowing packet routing to be trivially loop-free and avoiding the 
   need for up-to-date routing information in the intermediate nodes  
   through which the packet is forwarded. [...]

==> the need for up-to-date information may not necessarily be a bad 
thing.  Now the sources are in charge of that.  Moreover, the sources are 
also in charge of the whole network, as their source routes will be cached 
and used for other communications.

This is quite effective, but can be very dangerous in case of e.g.  
implementation bugs, unforeseen problems (e.g. a source getting out of
sync, and "competing with the cache" with the rest of manet nodes) and
such: one node can pretty much wreck the whole routing fabric without even
trying hard.

[...]  For
   example, DSR does not use any periodic routing advertisement, link
   status sensing, or neighbor detection packets, and does not rely on  
   these functions from any underlying protocols in the network.  This
   entirely on-demand behavior and lack of periodic activity allows
   the number of overhead packets caused by DSR to scale all the way
   down to zero, [...]

==> I see DSR header functions rather equivalent to link status sensing 
(maintenance procedures, Send Queue, etc.) and others above.

   In response to a single Route Discovery (as well as through routing
   information from other packets overheard), a node may learn and cache
   multiple routes to any destination.

==> just a trivial comment: cache management strategies will be quite 
critical.

3.1. Basic DSR Route Discovery

   Node E could instead simply reverse the sequence of hops in the route
   record that it is trying to send in the Route Reply, and use this as 
   the source route on the packet carrying the Route Reply itself.  For 
   MAC protocols such as IEEE 802.11 that require a bidirectional frame 
   exchange as part of the MAC protocol [11], the discovered source
   route MUST be reversed in this way to return the Route Reply since it
   tests the discovered route to ensure it is bidirectional before the  
   Route Discovery initiator begins using the route; this route reversal
   also avoids the overhead of a possible second Route Discovery.

==> This (and various other places in the text, e.g. Appendix A) assumes 
that the link-layer technology, at least from the point of view of 
directionality, must be the same all over the manet, or at least all manet 
nodes know the directionality of each device.

This seems a rather big aasumption.

   When initiating a Route Discovery, the sending node saves a copy of  
   the original packet (that triggered the Discovery) in a local buffer 
   called the "Send Buffer".

==> might this create extra delays in the case of Route Discoveries 
failing too (e.g. link failure, no manet nodes/AP's temporarily in range, 
...) ?

4.1. Route Cache

    -  In DSR, the route returned in each Route Reply that is received
	by the initiator of a Route Discovery (or that is learned from
	the header of overhead packets, as described in Section 6.1.4)
       represents a complete path (a sequence of links) leading to the  
 	destination node.  By caching each of these paths separately,
       a "path cache" organization for the Route Cache can be formed.   
	A path cache is very simple to implement and easily guarantees
	that all routes are loop-free, since each individual route from
       a Route Reply or Route Request or used in a packet is loop-free.
   
==> as pointed above, this puts quite much trust on the sender's cache 
data/cache being up-to-date.  A normal security procedure would be to 
verify received loop-freeness, but here normal security procedures might 
not apply...

5. DSR Header Format

   To add a DSR header to a packet, the DSR header is inserted following
   the packet's IP header, before any following header such as a
   traditional (e.g., TCP or UDP) transport layer header.  Specifically,
   the Protocol field in the IP header is used to indicate that a DSR
   header follows the IP header, and the Next Header field in the DSR
   header is used to indicate the type of protocol header (such as a
   transport layer header) following the DSR header.

==> this has strong implications if packet filtering is perfomed.  First, 
almost all packets will be discarded unless the packet filter/firewall 
supports DSR header processing and has some extra semantics on how to 
proceed past the first, DSR header.  This is similar to issues associated 
with IPv6 packet filtering..

6.2.2. Processing a Received Route Request Option

- [...]  If the node does
       not receive a Reply within some reasonable amount of time, MUST
	silently discard the Route Request packet.

==> perhaps this should be defined more precisely?

	o  If the node does not return a cached Route Reply, then this
           node SHOULD link-layer re-broadcast this copy of the packet,
           with a short jitter delay before the broadcast is sent.  The
           jitter period SHOULD be chosen as a random period, uniformly
           distributed between 0 and BroadcastJitter.

==> is it required that all possible media should support link-layer 
broadcasts?

6.3.6. Salvaging a Packet

   When an intermediate node forwarding a packet detects through Route  
   Maintenance that the next-hop link along the route for that packet is
   broken (Section 6.3), if the node has another route to the packet's  
   IP Destination Address in its Route Cache, the node SHOULD "salvage"
   the packet rather than discarding it.

==> s/discarding/discard/ ?

11. Security Considerations

==> nodes feeding wrong (out-of-date) information, acting by their best
knowledge?

-- 
Pekka Savola                 "Tell me of difficulties surmounted,
Netcore Oy                   not those you stumble over and fall"
Systems. Networks. Security.  -- Robert Jordan: A Crown of Swords

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Yih-Chun Hu <[email-masked]>
Date: Sun, 7 Apr 2002 20:27:36 -0400 (EDT)

Hello,

Thanks for your comments.

>These could in some cases perhaps lead to data being delivered more than 

I guess I don't see how that (multiple data delivery) might happen. 
Obviously it's possible with salvaging, since you might not get the ACK
even when the data gets through, but any local repair mechanism might have
this problem.  Even if it were to happen, we'd still be compliant with the
semantics of IP...

>the multi-option combinations seem to be less covered than their full 

Maybe we could point out in the draft which types could legally be
present. Perhaps I don't understand the concern, since the concept is that
anything can be piggybacked in anything.

>such: one node can pretty much wreck the whole routing fabric without even

The need for up-to-date information at each intermediate node is
problematic, for example, if nodes turn themselves off periodically,
effectively rebooting. Such nodes would not have state consistant with the
rest of the network, and in certain routing protocols, this could cause
routing loops.

I just don't see how you could ever get a routing loop in DSR. Your cache
determines the routes you add to packets. Those routes MUST be loop-free,
since they're finite length, and include a current-address, which is
monotone increasing.

Since each packet carries its own route, it's route is entirely determined
by the (by definition consistant) state at the sender, and no other node's
state.

>(maintenance procedures, Send Queue, etc.) and others above.

And they're all on-demand (not periodic). Maybe I don't understand what
you're trying to say? 

>==> just a trivial comment: cache management strategies will be quite 

Very true. We recommend a specific cache management scheme, called
Link-MaxLife.

>nodes know the directionality of each device.

Not manet-wide. Yes, for your own interfaces, but this is flexibility over
most existing manet routing protocols, which require bidirectionality at
all interfaces. When you put in the special addresses indicating a
bidirectionality switch, the receivers know the directionality of their
receive interface, and can deduce which parts of a source route must be
bidirectional and which ones can have unidirectional links. For example,
when the route A->B->*->C->D->*->E is received at D, it knows whether it's
interface is bidirectional or unidirectional. If it's unidirectional, it
knows A->B is bidirectional, B->C->D is unidirectional. When it sendsi t
out a bidirectional interface, it adds a * to the source route first.

>This seems a rather big aasumption.

It seems rather smaller than assuming that all interfaces are
bidirectional. I don't really want to belabor this point, because I don't
think DSR's unidirectional support is very well tuned, and because the
commodity standard for wireless interfaces these days is 802.11, which
does require bidirectionality.

>failing too (e.g. link failure, no manet nodes/AP's temporarily in range, 

Yes, that's the price you pay for an on-demand protocol. Discovery can
fail. You may have to wait. AODV, ZRP, SSA, ABR, ... all share this
problem.

>verify received loop-freeness, but here normal security procedures might 

No, it doesn't. You pick a route for the packet. You include the route in
the packet. That route is loop-free, regardless of whether or not your
cache is up-to-date.

I also don't see why you couldn't verify loop-freedom if you really cared.
If an address appears twice in the source route, then you've found a loop?

>with IPv6 packet filtering..

True, but that same firewall would also have to support DSR routing to
know the next hop, just like the same firewall would have to support IPv6
routing.

>==> perhaps this should be defined more precisely?

Agreed.

>==> is it required that all possible media should support link-layer 

How else do you do neighbor discovery? This seems like it should be taken
up as a manet-wide issue.

>==> s/discarding/discard/ ?

? This is in the present tense; if I were to say "the node SHOULD discard
the packet rather than salvage it," that doesn't sound quite right.

>==> nodes feeding wrong (out-of-date) information, acting by their best

What's the attacker model? Legitimate nodes failing in Byzantine ways? 
Multiple coordinated attackers with several compromised nodes? We specify
that security considerations are out-of-scope, as in BGP (RFC1771). 
Security in manets are an active area of research...

---

From: Yih-Chun Hu <[email-masked]>
Date: Sun, 7 Apr 2002 20:27:36 -0400 (EDT)

Hello,

Agreed.

---

From: Pekka Savola <[email-masked]>
Date: Mon, 8 Apr 2002 10:16:02 +0300 (EEST)

Hi,

Additional comment I just noticed: 'ACK Destination Address' in
Acknowledgment DSR Option seemed redundant to me, as the dstaddr in IP
header seems to serve exactly the same purpose.  Did I miss something?

I'll respond to some issues below.

> anything can be piggybacked in anything.

.. except for a few exceptions.  I don't see a concern as such here, but a
thing perhaps worth clarifying ("the usual DSR header combinations" or
whatnot).

> by the (by definition consistant) state at the sender, and no other node's

The last paragraph is not entirely true: the route can be affected by e.g. 
an intermediate node salvaging the packet, right?  The maximal salvage 
count does limit how many times this can happen, so this couldn't result 
in an endless loop, but quite often that's a tranistory state in regular 
protocols too.
 
> And they're all on-demand (not periodic). Maybe I don't understand what

Well, I just think that periodicity, as an "only" criterion, is not 
necessarily an usable on.  DSR does similar things like periodic activity, 
with overhead in the form of DSR header, anyway -- at least when there is 
traffic on the wire (e.g. network acknowledgements in route maintenance).

> all interfaces. 

See below.

> When you put in the special addresses indicating a
> bidirectional and which ones can have unidirectional links. 

I have a failure to grasp this.  Do you mean that addressing could be used 
to indicate bidirectionality?  Well, this is one approach, but I don't 
recall this in the draft?

> For example,

I'm not sure what you mean '*' here, so my comment may not be off the
mark.  I fail to see how D could conclude anything of A->B or B->C based
on the bidirectionality of its own link?  (Except if it knows the
directionality based on addresses or similar, but that's one approach I
was implicitly suggesting.)

> bidirectional. 

I disagree, on practical terms: it is a rather big assumption *when* one 
feature of DSR is exactly unidirectionality.  If there is support, the 
support should work.  If there is no support, people who have this as a 
requirement use different protocols.

> I don't really want to belabor this point, because I don't

If this is a practical "non-issue", I wonder if it would make sense to try 
to define the main DSR proposal as bidirectional, and move unidirectional 
parts to a separate draft.

> If an address appears twice in the source route, then you've found a loop?

True, for "loop-freeness" in the traditional meaning.  If one includes 
"inserting too long, very suboptimal paths, which do not have a loop", 
this would be more difficult to verify.  

But I'm not sure of the threat model of this; my main worry was that if a 
source knows a sub-optimal path, and that path will be cached on 
intermediate nodes too, and that way it might be propagated to all nodes 
querying for that destination (replies from the cache).

I'm not all that worried (except for severe implementation bugs) about 
loopfreeness as such, but rather unoptimal paths (which may be "almost 
loops") getting there.

> know the next hop, just like the same firewall would have to support IPv6

The firewall could also work in a bridging mode (which is a bit more rare, 
but we use one too), but you're right.  

I'd add a note in security considerations about this at least, though, 
because supporting DSR routing and supporting DSR header in the firewall 
software are two rather separate issues, and the connection may not be 
apparent.

> the packet rather than salvage it," that doesn't sound quite right.

I was suggesting like:

'the node SHOULD "salvage" the packet rather than discard it.'

, because I find using the -ing form of the verb unnatural here when 
"salvage" does not use that.  But I'm not a native speaker, so you're 
probably right if it sounds better.

> Security in manets are an active area of research...

The attackers have many models, most of which are out of scope here,
especially if one wants byzantine robustness in the case of a captured
node feeding deliberately wrong information.

One particular scenario I mentioned here was that a node that has old
cached data keeps propagating that information to nodes which do route 
requests through it.  Or salvage packets in non-optimal ways.  This could 
lead to a security problem (denial of service).  But perhaps this "cache 
freshness ensurance problem" needs to be addressed elsewhere.

---

From: Pekka Savola <[email-masked]>
Date: Mon, 8 Apr 2002 10:16:02 +0300 (EEST)

Hi,

 

See below.

I was suggesting like:

---

From: Yih-Chun Hu <[email-masked]>
Date: Wed, 10 Apr 2002 19:49:47 -0400 (EDT)

>header seems to serve exactly the same purpose.  Did I miss something?
 
Yep, you can technically piggyback it on something. Same deal with Route
Error Destination Addresses.
 
>thing perhaps worth clarifying ("the usual DSR header combinations" or
 
I guess I should think very carefully about "the prohibited DSR header
combinations." I don't know that there are any; even bizzare things like
source-routed route requests could be interesting (route request up to a
point, where you know the rest of the route from there, or source route a
request out to a certain point, then blossom it from there).
 
>in an endless loop, but quite often that's a tranistory state in regular 
 
Granted. We could prohibit a path from ever looping, but that would also
prohibit backtracking. We don't allow looping (same path over and over
again); we allow backtracking.
 
>traffic on the wire (e.g. network acknowledgements in route maintenance).
 
There are things that other protocols do periodically: neighbor sense,
route discovery, route maintenance, etc. But it does them ONLY when
there's traffic on the wire. We say these are performed "on-demand" as a
characterization of their frequency and efficiency. We also argue why we
think on-demand protocols may be better in certain situations. 
 
>recall this in the draft?
 
Section 7. It's new in -07. (Sorry)
 
>was implicitly suggesting.)
 
* is a "magic" address. So, looking at a source route backwards 
        E<-*<-D<-C<-*<-B<-A
E knows that the directionality of the c->d segment is different from the
directionality of the d->e segment. Similarly, c knows that the
directionality of the a->b segment is different from the directionality of
the b->c segment.
 
>requirement use different protocols.
 
Hmm. Well, since you have to write a driver for an interface, I don't
think that's a huge assumption that you know the directionality of one of
your interfaces. You'd need to know that to decide whether or not you
could even use one of the other protocols.
 
>parts to a separate draft.
 
That's an "I" as a person, not an "I" speaking on behalf of all draft
authors.
 
>querying for that destination (replies from the cache).
 
If you're worried about malicious nodes being "stupid" and using long
routes, I can assure you that there are many worse things that could be
used as attacks. Automatic Route Shortening helps reduce the length of
stale, long routes. Promiscuous overhearing works pretty well too. We have
yet to find a reason that drives us to periodic path discovery to ensure
freshness.
 
>loopfreeness as such, but rather unoptimal paths (which may be "almost 
 
Any on-demand protocol without a periodic rediscovery mechanism has the
same problem; once you set up a route, you don't really bother to look for
a better one.
 
>software are two rather separate issues, and the connection may not be 
 
That's a good idea.
 
>freshness ensurance problem" needs to be addressed elsewhere.
 
You'd eventually get route errors that flush out your cache if you're
returning bogus routes on requests. For example, suppose A has two
disjoint bogus routes to B in its cache, and C does a discovery for B. A
returns a bogus route, C uses it, B forwards the corresponding route
error. Now A only has one disjoint bogus route.
 
Also, with the cache specified in appendix A, routes not actively in use
are eventually timed out.
 
Thanks for the comments,
Yih-Chun

---

From: Yih-Chun Hu <[email-masked]>
Date: Wed, 10 Apr 2002 19:49:47 -0400 (EDT)

That's a good idea.

 
 
Thanks for the comments,
Yih-Chun

---

From: Pekka Savola <[email-masked]>
Date: Thu, 11 Apr 2002 09:28:12 +0300 (EEST)

Hello,

Btw, in section 5:

   The placement of DSR options following the fixed portion of the DSR
   header MAY be padded for alignment.  However, due to the typically
   limited available wireless bandwidth in ad hoc networks, this padding
   is not required, and receiving nodes MUST NOT expect options within a
   DSR header to be aligned.

==> is the wording about the recipient be supposed to be that strict?  IMO 
it's OK to _expect_ the header to be aligned, but the recipient definitely 
MUST NOT _require_ it?

> Error Destination Addresses.

Ok, perhaps these could be clarified, depending on how similar "duplicated 
data due to piggybacking" is currently discussed.  After reading, it wsn't 
obvious to me you could piggyback data _to multiple destinations_ in all 
packets.  Often piggubacking is only used to mean a multiplex transport 
between two nodes.

DST_I = destination in IP header
DST_A = destination in acknowledgement

What are the rules for piggybacking? I assume that from the direction of 
the source, DST_A must be on the path to DST_I, or DST_I?  What if DST_A 
moves off the path, or isn't on the path to begin with?  An intermediate 
node should "remove" piggybacking and send two separate packets?

Piggybacking when the destination is not the same seems like a potentially 
troublesome concept.

> request out to a certain point, then blossom it from there).

Well, at least some cannot be used more than once.  There are probably 
some practical ways how it's usually done.  Just a thought.
  
> Section 7. It's new in -07. (Sorry)

Hmm.  Perhaps this is isn't clear to me as from traditional routing 
background, one always assumes more than one interface.  But isn't this 
issue more generic than one for multiple interfaces only?
> directionality of the a->b segment is different from the directionality of

I don't recall the discussion on how the magic address changes the 
processing of nodes which don't have multiple addresses, btw.

What about the scenario where there are no magic addresses: every node in 
the path has only one interface?   It is clear that the interface must be 
"generally" bidirectional, else it could not do any traffic, but it may 
not need to be birectional to all the neighbors in the range.

> could even use one of the other protocols.

IP layer should be separate from this kind of decisions, but anyway, 
people deploying a MANET and people writing MANET protocols and people 
writing the interface drivers may be very very different.

> used as attacks. 

As said, there are much more viable attacks than this.  But my worry is 
non-malicious, but still "stupid" nodes doing something.

> same problem; once you set up a route, you don't really bother to look for

In some cases it might be very useful, ie. to find fresh new paths before
your current path fails.  But I guess that's more of an ideological
issue..
  
> error. Now A only has one disjoint bogus route.

Good clarification.
  
> are eventually timed out.

Note that this behaviour seems different than original ARP behaviour from 
which Route Req/Route Maintenance originated: with ARP, you re-perform ARP 
*even if* the entry is being used.

---

From: Pekka Savola <[email-masked]>
Date: Thu, 11 Apr 2002 09:28:12 +0300 (EEST)

Hello,

Btw, in section 5:

  

  

Good clarification.

---

From: Yih-Chun Hu <[email-masked]>
Date: Wed, 10 Apr 2002 19:49:47 -0400 (EDT)

That's a good idea.

Thanks for the comments,
Yih-Chun

---

From: Yih-Chun Hu <[email-masked]>
Date: Wed, 10 Apr 2002 19:49:47 -0400 (EDT)

That's a good idea.

Thanks for the comments,
Yih-Chun