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

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

Comments inline.

On 8/25/06, Charles E. Perkins <[e-mail]> wrote:
> ---------- Forwarded message ----------
> From: "Charles E. Perkins" <[e-mail]>
> To: ext Ian Chakeres <[e-mail]>
> Date: Fri, 25 Aug 2006 16:35:25 -0700
> Subject: Re: DYMO SeqNum Decisions
>
> 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?

Both these problems were because the RREP originator was not
incrementing its sequence number.

> >
> > 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.

> >
> > 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.

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.

> >
> > 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 <[e-mail]> 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 <[e-mail]> 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 <[e-mail]> 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 [e-mail]
> >> >>
> >> >>
> >>
> >>
> >> --
> >> Please address return e-mail to [e-mail]
> >>
> >>
> >>
> >>
>
>
> --
> Please address return e-mail to [e-mail]
>
>
>
>
> _______________________________________________
> Manet-dt mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/manet-dt
>
>
>

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