[Manet-dt] Re: DYMO SeqNum Decisions

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

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.

A RREP originator does not know the route the RREP will traverse.
Therefore, it must increment its sequence number before sending the
RREP.

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.

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.

FYI: A RREP does not contain information to identify the RREQ that
caused its generation.

Charlie, I am interested in seeing your proposal for DYMO intermediate
node replies.

Ian


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

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