Subject: [Manet-dt] [Fwd: Re: DYMO SeqNum Decisions]

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 25 Aug 2006 16:36:30 -0700

Oops, I forgot to include the design team on this e-mail...  resending ...

-- 
Please address return e-mail to [email-masked]

Subject: Re: DYMO SeqNum Decisions
From: "Charles E. Perkins" <[email-masked]>
To: ext Ian Chakeres <[email-masked]>
Date: Fri, 25 Aug 2006 16:35:25 -0700

Hello Ian,

ext Ian Chakeres wrote:
> Charlie, the problem may not happen often in practice - but it can
> happen. We don't want DYMO to ever result in blackholes where RREP are
> consistently discarded.
O.K. Agreed -- but the solution for the unusual case does not
have to be as efficient as for the usual case.
>
> A RREP originator does not know the route the RREP will traverse.
> Therefore, it must increment its sequence number before sending the
> RREP.
Well, it does know the route if we are doing path accumulation.
But, continuing on as if we are not ...
>
> Pedro & Fran ran into seq num problems last year. During IETF 65 Ramon
> identified another sequence number issue related to this discussion.
> Both had problems with RREP being blackholed.
Were those problems caused by the scenario outlined in recent e-mails?
>
> If we force intermediate nodes to examine information about the target
> (last known seqnum and hopcnt) we might be able to know something at
> the target node about the route traversed. But we still need to ensure
> that a RREQ will reach the target, and I think any such logic could
> result in RREQ blackholing.
I think I am missing something here, unfortunately.  Can you say
just a little more about when the blackholing would occur?
>
> FYI: A RREP does not contain information to identify the RREQ that
> caused its generation.
A node can see whether the RREP is heading towards a source in its
table of recent RREQs.  The table of recent RREQs can have information
about the requested destination (and probably should anyway).  This
is enough for the intermediate node to make the decision.
>
> Charlie, I am interested in seeing your proposal for DYMO intermediate
> node replies.
So am I!

Regards.
Charlie P.

> On 8/25/06, Charles E. Perkins <[email-masked]> wrote:
>>
>>
>> Hello Ian,
>>
>> The only way this could happen, is if the RREP
>> were to follow a reverse route that was longer than
>> an existing route at an intermediate node.  Does this
>> happen in practice very often?  I'd be surprised!
>>
>> Anyway, we can be pretty darned sure that the
>> sequence number in an incoming RREP will be at
>> least equal to what the node already has.  If not,
>> an error message should be displayed.
>>
>> If it does turn out, surprisingly, to be common
>> that RREPs are dropped for the reason you
>> have identified, then we still have a way out.
>>
>> There is a table of recent RREQs stored in the node's
>> memory somewhere.  That table can be consulted upon
>> arrival of a RREP, to see if the node has previously
>> relayed a RREP message for the corresponding RREQ.
>> If the intermediate node has NOT previously sent
>> a corresponding RREP, then we should probably
>> specify that it should send the RREP.
>>
>> I wonder about whether, in this case, the intermediate
>> node should reduce the hop count and maintain the
>> same next hop information, or whether it should
>> keep the same hop count information and change its
>> next hop and other route table information accordingly.
>>
>> But it's all a moot point if the error case does not
>> arise.  I seem to remember that something came up
>> last year in simulations that Fran and Pedro were
>> running, which is relevant to this point.
>>
>> Regards,
>> Charlie P.
>>
>>
>> ext Ian Chakeres wrote:
>> > If a RREP is slated to traverse a node that has some information about
>> > the the RREP originator then the information in the RREP must be
>> > considered fresh (or superior) to create/update a route. Otherwise,
>> > the RREP will be discarded/ignored.  The only way to ensure that the
>> > RREP is fresh is for the RREP originator to increment its sequence
>> > number, since RREP originator's don't know the state of routing tables
>> > in the nodes that the RREP will traverse.
>> >
>> > Do you see a way around this?
>> >
>> > Ian
>> >
>> > On 8/25/06, Charles E. Perkins <[email-masked]> wrote:
>> >>
>> >> Hello Ian,
>> >>
>> >> I am mystified about why there is a problem.
>> >>
>> >> First, if a node receives a RREQ, it is almost guaranteed
>> >> that the RREQ comes from a neighbor that can route to
>> >> the source.
>> >>
>> >> Second, there is no restriction that prevents a node
>> >> from checking whether the RREQ has a fresh seq #
>> >> for the source.  We could specify that the RREQ
>> >> be discarded if the seq # is older than some information
>> >> that the intermediate node has about the source.
>> >>
>> >> I do like the idea of inserting this requirement
>> >> into DYMO.
>> >>
>> >> I also think it would be very interesting to identify
>> >> when the problem (unroutable RREP) actually occurs
>> >> in simulation.  I would issue an error message in
>> >> capital letters and characterize the conditions under
>> >> which the problem occurs.
>> >>
>> >> Regards,
>> >> Charlie P.
>> >>
>> >>
>> >> ext Ian Chakeres wrote:
>> >> > I've been thinking about situation when a node must increment its
>> >> > SeqNum when sending a RREP.
>> >> >
>> >> > Currently RREQ are not modified in flight (as they are
>> >> > re-forwarded/broadcast), a feature that I think is a very 
>> important -
>> >> > and a feature must be supported at the minimum.
>> >> >
>> >> > If a nodes forwards a RREQ that means that the routing information
>> >> > contained about the originator was sufficient to create/update a 
>> route
>> >> > to the originator. It does not examine or check the information 
>> about
>> >> > the RREQ target.
>> >> >
>> >> > When the RREQ reaches the target, the target knows the sequence 
>> number
>> >> > that the originator knew when the RREQ was issued. The target also
>> >> > knows the distance (hopcount) to the originator.
>> >> >
>> >> > Since it does not know information about the routing tables in
>> >> > intermediate nodes (particularly the sequence number and hopcnt 
>> about
>> >> > itself), it must increment its sequence number. If it doesn't then
>> >> > there is the possibility that the RREP will be dropped as it 
>> traverses
>> >> > the network back to the originator.
>> >> >
>> >> > Does anyone have a way around this issue, or can you suggest 
>> something
>> >> > I'm missing?
>> >> >
>> >> > Thanks.
>> >> > Ian
>> >> >
>> >> > On 8/12/06, Ian Chakeres <[email-masked]> wrote:
>> >> >> As an exercise in ensuring dymo sequence numbers work properly, 
>> I've
>> >> >> created a few slides discussing important dymo sequence number
>> >> >> decisions.
>> >> >>
>> >> >> Pages 1 & 2 talk about judging routing information usefulness. The
>> >> >> goal is to not have loops, while not requiring nodes to increment
>> >> >> their OwnSeqNum unless absolutely necessary. Incrementing 
>> OwnSeqNum
>> >> >> essentially disqualifies existing routing information in the 
>> network
>> >> >> that may not be bad.
>> >> >>
>> >> >> Pages 3 & 4 talk about incrementing OwnSeqNum. Since nodes issuing
>> >> >> RREQ don't know the state of routing tables at intermediate nodes,
>> >> >> they need to increment their sequence number. Otherwise, receiving
>> >> >> nodes might discard this information. The target on the other hand
>> >> has
>> >> >> more information from the RREQ message (last known values and some
>> >> >> information about the route traversed). The target can use this
>> >> >> information to optimize sequence number incrementing.
>> >> >>
>> >> >> Intermediate nodes that append their routing information have two
>> >> >> options, updating their sequence number and ensure it will be
>> >> fresh at
>> >> >> other nodes, or not.  If the sequence number is not incremented it
>> >> >> might not be considered fresh by intermediate nodes. It is not 
>> clear
>> >> >> what the recommended procedure should be. Please make a 
>> suggestion. I
>> >> >> suggest incrementing OwnSeqNum.
>> >> >>
>> >> >> Page 5 talks about the cases when an Intermediate node could 
>> reply.
>> >> >> Currently we don't define intermediate node replies, but it is a
>> >> >> useful concept. One more thing, I've introduced a concept "MaxAge"
>> >> >> which is the maximum amount of time a piece of routing information
>> >> can
>> >> >> be maintained. This is to assist in reboots, by having a hard
>> >> deadline
>> >> >> on the maximum amount of time that a node must wait before
>> >> >> participating.
>> >> >>
>> >> >> Please review the flowcharts and let me know if something doesn't
>> >> make
>> >> >> sense or is wrong.
>> >> >>
>> >> >> Ian Chakeres
>> >> >>
>> >> >>
>> >> >>
>> >>
>> >>
>> >> --
>> >> Please address return e-mail to [email-masked]
>> >>
>> >>
>>
>>
>> -- 
>> Please address return e-mail to [email-masked]
>>
>>
>>
>>

-- 
Please address return e-mail to [email-masked]

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 25 Aug 2006 17:02:00 -0700

Hello again Ian,

A few follow-on comments...

ext Ian Chakeres wrote:
> Both these problems were because the RREP originator was not
> incrementing its sequence number.
That formulation prejudices the outcome.  I will interpret it to mean that,
both problems would be solved if the RREP originator would
increment its sequence number.  But the problem is _caused_ by
some other occurence.  It is this true cause of the problem that
I want to know more about.

> This condition would occur whenever an intermediate node discarded a
> RREQ (due to new rules) and it was the only route to the target.
Do you mean the new DYMO rules?  Or, which ones specifically?

---

From: "Ian Chakeres" <[email-masked]>
Date: Fri, 25 Aug 2006 16:47:30 -0700

Comments inline.

On 8/25/06, Charles E. Perkins <[email-masked]> wrote:
> ---------- Forwarded message ----------

> is enough for the intermediate node to make the decision.

We currently do not maintain any table of RREQ, and I think this is
small problem. I am updating the draft to deal with it and we can
discuss the solution after you take a look.

---

From: "Ian Chakeres" <[email-masked]>
Date: Fri, 25 Aug 2006 17:16:55 -0700

Comments inline.

> I want to know more about.

"The problem"  is that RREP were not being considered as fresh or
superior, and therefore dropped.

I would like to find a solution that does not require the RREQ target
(RREP originator) to increment its sequence number, but I have not
found one yet.

Finding such a solution appears difficult, since the target does not
know the state of routing tables in nodes along the path from the RREP
originator to the RREP target (RREQ originator).

I am querying you and others to propose a solution that would solve
"The problem". Hopefully, one that does not require the RREP
originator to increment its seqnum.

One other note lower.

> Do you mean the new DYMO rules?  Or, which ones specifically?

A possible set of new processing rules associated with dropping RREQ
based on the target's last know sequence number and hop count that
would allow the RREQ target to know something about the route
traversed.

I do think blackholing could occur if this (new processing rules) were
implemented.

Ian

---

From: mase <[email-masked]>
Date: Mon, 28 Aug 2006 10:03:37 +0900

Dear Ian and Charlie,

When an intermediate node receives a RREQ and it has a valid route to the 
destination and its destination sequence number is  greater than or equal 
to the sequence number, the node can behave as 1) or 2).
1) If an intermediate node is allowed to issue a RREP, it does so.
2) If it is not allowed to issue a RREP, it simply re-broadcasts the RREQ.

I think that you are discussing the case of 2. Here is a concern, as 
pointed by Ian, that when this node receives the RREP, it may discard the 
RREP because it already has the valid route with the destination sequence 
number, that is same as or greater than that included in the RREP, if the 
destination have not incremented its sequence number when it received the RREQ.

If this understanding is correct, I would propose the following solution.
When the intermediate node receives the RREP, it compares its content with 
its valid route to the destination. If the destination sequence number of 
the route is same or greater than that in the RREP, the node modifies the 
RREP so that it becomes consistent with its route information. (As if it 
creates RREP in the case of 1))

In this solution, the RREP includes the same information as that issued by 
this node in case 1). No copy of RREQ is required. No discarding of RREP 
occurs. Note that this modification method must be used only in the case of 
2), where RREP is delivered in a manner of unicast  from the destination to 
the source. Thus, an intermediate node receives the RREP only once for a 
given RREQ.  In the case 1), some nodes may simultaneously issues RREPs for 
the given RREQ and modification of RREP is not allowed.

Do you think that this solution is workable?

Cheers,
Kenichi

---

From: "Ian Chakeres" <[email-masked]>
Date: Sun, 27 Aug 2006 21:05:35 -0700

An intermediate node might not have a good route (the route might have
broken). In this scenario, the intermediate node cannot fill in the
RREP, since it does not have a good route. In this case, if the
sequence number is not higher (or equal with additional logic
including the hop count) then the RREP will be dropped. One more thing
to keep in mind, I currently do not see a way to predict the state
(sequence number and hopcount) required to create a good route at the
intermediate nodes.

Also, I would like  to avoid modifying packets'/messages' information
while in flight. Any modification to information added by the
originator would make end to end security extremely difficult if
message signing were used.

Ian

---

From: "Pedro M. Ruiz" <[email-masked]>
Date: Mon, 28 Aug 2006 13:48:23 -0700

Hi all,

Sorry for late answer, it took me a while to go through the whole 
thread, and check old e-mails with our previous discussions on this same 
issue.

I do remember we discussed quite a lot about this issue after Paris 
IETF. There were different solutions being proposed and simulated. I do 
remember Fran sent out the graphs of the different schemes...

Let me recapitulate so that other people in MANET-DT can get some context...

As Ian mentioned, the issue is that RREPs are being blackholed by some 
intermediate nodes. This may happen due to mobility, just changing the 
length of the reverse path back to the source.

We simulated two alternatives. first one was my proposal to increase 
OwnSeqNo when creating a RREP (I know we don't want this) and second one 
was Charlie's porposal of allow RREPs to be propagated if seqnos are 
equal and hopcount no more than 1 hop longer. The reason for the 
condition of 1 hop was to avoid creating loops.

The performance shown in the simulations was almost the same for both 
schemes. Thus, we decided to include the second alternative in v3 of the 
DYMO draft.

Even with these changes, I pointed out some time ago that blackholes 
could still happen when topology changes include a more than
2 hops difference between the intermediate node and the node sending the 
RREP.

Fran simulated a solution in which we allow a RREPs to go back to the 
source if seqnos were equal, regardless of the hop count and simulation 
results where as good as the two previous alternatives. I remember we 
were discussing whether allowing those RREP to be propagated could 
create a loop, and AFAIR, we didn't find a case in which that would 
happen. It seems that it was safe to allow those RREPs to be propagated 
without creating a loop. I think this is very similar to what Charlie 
said about having a local table where recent RREQs are stored.

Wouldn't that be a valid solution?

Regards,

--Pedro

-- 
---------------------------------------------------------------------
Pedro M. Ruiz, Ph.D.                    E-mail: [email-masked]
Fac. Informatica, Univ. of Murcia       Phone:  +34968364335
Campus de Espinardo s/n                 Fax:    +34968364151
E-30100, Espinardo, Murcia              www: ants.dif.um.es/~pedrom/
SPAIN
---------------------------------------------------------------------