[Manet-dt] Re: DYMO SeqNum Decisions - Use a message

["Ian Chakeres" <[e-mail]>]

Here is a possible solution.

If a RREP is not found to be fresh or superior - because its sequence
number and hop count information are not sufficient, then the
intermediate node unicasts a message (hop-by-hop) to the RREP
originator.

When the RREP originator receives this message, it knows to increment
its sequence number must be incremented and reissue a RREP.

On one hand - I don't really like this solution, since it requires
introduction and processing of a new message type. On the other, I
think it could eliminate the RREP blackholing problem without
incrementing the sequence number at the destination.

There might be some issues with this scheme, if intermediate nodes issue RREPs.

What do you think?

Ian


On 8/28/06, Pedro M. Ruiz <[e-mail]> wrote:
>
>
>  Hi Ian,
>
>  I guess I was not specific enough. When I said propagate the RREP back, didn't mean updating routing entries at intermediate nodes with that information. That is, if seqnos are equal an hop count is worse there is no reason to update a valid route entry with this one, which happens to be worse. I think this detail may prevent the loop from being formed. But I need to think more about it.
>
>  Of course, I agree that it may sound weird to propagate such a RREP, but it is the only way I see off the top of my head to avoid RREPs being blacklisted without the destination increasing its OwnSeqNum.
>
>  I'll try to find some time tomorrow to finally find out whether loops can appear even if we allow those RREP to propagrate without updating route entries.
>
>
>  Regards,
>
>  --Pedro
>
>  Ian Chakeres wrote:
>
>
> I am hesitant to have DYMO accept RREP information regardless of the hop count.
>
>  Here is an example showing a routing loop.
>
>  Each of the arrows represents multiple hops. Solid arrows represent
>  routing table entries, while empty arrows are RREP messages.
>
>  In the starting state RREQ have been disseminated by nodes X & Y. Due
>  to some messages losses the two routes shown are discovered. Node Z
>  routes through node X to reach node Y. Node Z routes through node Y to
>  reach node X.
>
>  If node Z issues RREP to nodes X & Y. The RREP will traverse (remember
>  these are multihop paths) the other node first. When the two RREPs
>  (with identical sequence numbers) travel between nodes X & Y, each
>  node will create a route pointing toward the other creating a routing
>  loop.
>
>  Ian Chakeres
>
>  On 8/28/06, Pedro M. Ruiz <[e-mail]> wrote:
>
> 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
>
>  Ian Chakeres wrote:
>
>  > Comments inline.
>  >
>  > On 8/25/06, Charles E. Perkins <[e-mail]> wrote:
>  >
>  >>
>  >> Hello again Ian,
>  >>
>  >> A few follow-on comments...
>  >>
>  >> ext Ian Chakeres wrote:
>  >> >> > 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?
>  >> >
>  >> > 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.
>  >
>  >
>  > "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.
>  >
>  >> >> > 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?
>  >> >
>  >> > 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?
>  >
>  >
>  > 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
>  >
>  >> --
>  >> Please address return e-mail to [e-mail]
>  >>
>  >>
>  >
>  > _______________________________________________
>  > Manet-dt mailing list
>  > [e-mail]
>  > https://www1.ietf.org/mailman/listinfo/manet-dt
>  >
>
>
>  --
>  ---------------------------------------------------------------------
>  Pedro M. Ruiz, Ph.D.                    E-mail: [e-mail]
>  Fac. Informatica, Univ. of Murcia       Phone:  [phone]
>  Campus de Espinardo s/n                 Fax:    [phone]
>  E-30100, Espinardo, Murcia              www: ants.dif.um.es/~pedrom/
>  SPAIN
>  ---------------------------------------------------------------------
>
>
>
>
>    ________________________________

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

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