Subject: [manet] Some functional issues concerning DYMO protocol operation

From: "Lars Kristensen" <[email-masked]>
Date: Thu, 18 Oct 2007 15:24:42 +0200

We have recently been working with formal modelling and verification of the
DYMO protocol. Our aim is to construct a complete model of the protocol
version 10 and verify key behavioural properties related to the operation of
the protocol 

As part of our initial modelling and verification, we have come across the
following issues in version 10 the DYMO Internet draft.

1) When processing a routing message and the node is a DYMO router for the
target node (draft, Sect. 5.3.4, page 20), it may respond with a RREQ flood
(a RREQ addressed to oneself). It is not clear to us which information to
put in the RREQ message, e.g., the originator address, hop limit, and
sequence number of the RREQ. Also, it is unclear to us why this option is
available?

2) When retransmitting a RREQ message (draft, Sect. 5.4, page 20), it is not
explicitly stated whether the node sequence number is increased. If the
sequence number is not increased when retransmitting it could cause a
problem in the following way:

A RREQ R1 is sent and lost before it reaches its target. Prior to
retransmitting R1 another RREQ R2 (for a different target) with a higher
sequence number is sent. When R1 is retransmitted, nodes who have seen R2
will consider R1 to be stale. This means that a route to the target of R1
will not be established.

It might be a solution to simply create a new RREQ when retransmitting. In
this case, the last sentence in the second paragraph of section 5.4:

"If a route is not created within RREQ_WAIT_TIME, ThisNode may again try to
discover a route by issuing another RREQ." 

can be replaced by:

"If a route is not created within RREQ_WAIT_TIME, ThisNode may again try to
discover a route by incrementing OwnSeqNum by one and retransmitting the
RREQ with OrigNode.AddTLV.SeqNum set to the new OwnSeqNum.

3) In the description of the data structure route table entry (draft, Sect.
4.1) it is suggested that the address field can contain more than one node.
It is not clear to us why this is the case.

4) The DYMO draft 10th revision introduces the concept of distance in
addition to hop count. As we understand it, the idea is that distance is a
more general metric, but in the routing message processing (draft, Sect.
5.3.4) it is always incremented by one. Why is the distance incremented by
one and not by some general metric?

5) When judging the usefulness of routing information (draft, Sect. 5.2.1,
the node being targeted is not taken into account. To us it looks like a new
request with a higher sequence number can make an older request for another
target node stale. This is because the sequence number in the old message is
less than the sequence number found in the routing table. It might be a
problem when two requests for different target nodes are sent (almost)
simultaneously since they might overtake each other.

A concrete example the following: Consider two RREQs R1 and R2 for two
different target nodes and assume R2 has a higher sequence number than R1.
The two RREQs are sent (almost) simultaneously. It might be the case that R2
arrives first at the surrounding nodes, e.g., because of overtaking on the
network. If this is the case, R1 (arriving after R2) will be considered
stale because R2 has a higher sequence number than R1. If they both use the
same timeout this might keep happening, and the route being requested via R1
will not be discovered. We have not been able to find a mechanism in the
current DYMO specification that copes with this issue.

6) We have investigated the judgement of routing information. We found that
it is possible for a routing message to be both inferior and loop-possible
at the same time e.g. if you have a RREQ with Node.Dist=3 and Route.Dist=1.
It is not a major problem since both messages are discarded (draft, sect.
5.3.4), but it shows that the classification of routing information is not
exclusive.

A paper describing our initial work in more detail can be found via:

http://www.daimi.au.dk/CPnets/workshop07/cpn/papers/Paper13.pdf  

/Lars

Lars Michael Kristensen
Associate Professor, PhD
Department of Computer Science, 
University of Aarhus, Denmark
Tel: +45 8942 5686
WWW: www.daimi.au.dk/~kris/

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

---

From: "Ian Chakeres" <[email-masked]>
Date: Sat, 20 Oct 2007 12:59:24 +0530

Thank you very much for the comments on the DYMO draft. You have
supplied lots of good suggestions.

More comments inline.

> sequence number of the RREQ. Also, it is unclear to us why this option is

Using a RREQ will flood routing information throughout the network on
how to reach the RREQ originator (which in this case would be the
TargetNode). Using a RREQ instead of a RREP will still get the
principal RREQ originator information about ThisNode (the principal
RREQ target).

I have reversed the order (since RREP would likely be the preferred
operation), and added to the text to indicate the target address of
the RREQ.  When I submit the next revision, please review this text
(and others below) and provide additional suggestions.

> RREQ with OrigNode.AddTLV.SeqNum set to the new OwnSeqNum.

Instead of the above suggested text, I directly refer the reader to
the section titled "RREQ Creation", which discusses incrementing of
OwnSeqNum.

> It is not clear to us why this is the case.

If the route is a prefix route, it denotes a subnet of addresses
(nodes). If the text is unclear, can you please suggest a fix?

> one and not by some general metric?

DYMO-10 does not state that the distance be incremented by one, but by
"more than one" or "at least one".  I believe the current text leaves
sufficient room for implementors to choose a larger distance
increments to influence the routes chosen. If you have a specific
suggestion for text changes, just email them to me.

> current DYMO specification that copes with this issue.

If you have a simple suggestion to solve this problem, please provide
it. In practice I have not run into this issue too much, but I agree
it could happen.

> 5.3.4), but it shows that the classification of routing information is not

Excellent catch.

The exact text for each these classifications is challenging. Can you
see a simple way to exclude the loop-possible case from the inferior
case while not complicating the loop-possible case dramatically (text
or pseudo-code)?

---

From: "Lars Kristensen" <[email-masked]>
Date: Wed, 24 Oct 2007 15:11:12 +0200

Ian,

>operation), and added to the text to indicate the target address of the 
>RREQ.  When I submit the next revision, please review this text (and 
>others below) and provide additional suggestions.

OK. We will take a closer look at the text in the next version and try to
incorporate this into our model.  

>Instead of the above suggested text, I directly refer the reader to the 
>section titled "RREQ Creation", which discusses incrementing of 
>OwnSeqNum.

We considered making a reference to section 5.3.1 (as you propose). We
decided to propose the more direct formulation since 5.3.1 specifies how to
set all fields of the RREQ - and it is only the originators sequence number
that has to be modified when retransmitting. Hence, 5.3.1 contains a lot of
text that is not required for implementing the retransmission.   
 
>(nodes). If the text is unclear, can you please suggest a fix?

Your comment clarifies it. A suggestion for making this more explicit would
be to describe Route.Address by:

"The IP (host or network) destination address of the node(s) associated with
the routing table entry"

>sufficient room for implementors to choose a larger distance increments 
>to influence the routes chosen. If you have a specific suggestion for 
>text changes, just email them to me.

Having checked DYMO-10, we see that the description of Node.AddTLV.Dist is:

"A metric of the distance to reach the associated Node.Address. This field
is incremented by at least one at each intermediate DYMO router, except the
TargetNode.AddTLV.Dist.  The TargetNode's distance information is not
modified."

This is fine, but seems be inconsistent with the description in Sect 3.4 on
RM processing which states the following:

"For each address (except the TargetNode) in the RM that includes
AddTLV.Dist information, the AddTLV.Dist information is incremented by one
(1)."

>it. In practice I have not run into this issue too much, but I agree it 
>could happen.

At the moment we do not have a simple suggestion for solving this problem.
The problem is also less likely to occur now that OwnSeqNum is incremented
when a RREQ is retransmitted. 

>case while not complicating the loop-possible case dramatically (text 

We currently do not have sufficient intuition on the classification in order
to suggest a good solution to this. It is of course easy to rewrite the
formulas to ensure that the classes become disjoint, but that defeats the
purpose of having the classification. Perhaps it is such that there is
routing information which is rightly considered both inferior and
loop-possible. As long as it is ensured that routing information that falls
into more than one class is treated in the same way this is not a problem in
practice. 

Lars

---

From: "Ian Chakeres" <[email-masked]>
Date: Thu, 25 Oct 2007 10:23:01 +0530

Comments inline.

> "The IP (host or network) destination address of the node(s) associated with

Good suggestion. I've included it.

> AddTLV.Dist information, the AddTLV.Dist information is incremented by one

I've fixed this to say "incremented by at least one (1)".

> >case while not complicating the loop-possible case dramatically (text

I will try to address this issue in the next revision. I agree it
would be nice if they are clearly disjoint.

Thanks again for your comments.
Ian