Subject: [Manet-dt] DYMO SeqNum Decisions

From: "Ian Chakeres" <[email-masked]>
Date: Sat, 12 Aug 2006 15:39:58 -0700

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
_______________________________________________
Manet-dt mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet-dt

---

From: "Ian Chakeres" <[email-masked]>
Date: Sun, 20 Aug 2006 11:50:59 -0700

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

---

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

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.

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 25 Aug 2006 15:05:39 -0700

Hello Ian,

There is not a definition for "active" route in the DYMO
specification.  I think we should distinguish "active" from
"valid".  The definition of "valid" seems correct.  We can
say that a route is active if it is valid and it has been used.

Then we can say that a RERR is only issued for active
routes.  A RERR does not have to be issued for valid
routes when they are broken.  This behavior is already
in the specification, but with the proper definition for
active I think it is more easily stated.

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 25 Aug 2006 15:21:28 -0700

Hello again Ian,

I have gone through the .pdf file with the circles and
arrows and cases for incrementation logic.

I am currently favoring the design choice that intermediate
nodes should NOT increment their sequence number.
My reasoning is along the lines that, as you state, doing
so makes every downstream node to consider the
information as not only authoritative but pre-emptive
(i.e., all previous data MUST be updated).

Why is this a good thing?  Maybe one of the newer
RREQs would have more hopes, get stuck in a queue,
emerge later, and invalidate a route which was already
working fine along noncongested path components.

On the other hand, RREQs with the same sequence
number and fewer number of hops can also get stuck
in a queue and invalidate working routes with more
hops, but that is behavior that we already would
experience today.

Regards,
Charlie P.

---

From: "Ian Chakeres" <[email-masked]>
Date: Fri, 25 Aug 2006 15:33:09 -0700

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

---

From: "Ian Chakeres" <[email-masked]>
Date: Fri, 25 Aug 2006 15:39:11 -0700

I am currently in the process of refining this very area of the spec.

Here is what I'm thinking (and writing into dymo-06-pre)

Current - routing information that is new, good, and should be
maintained for a while

Recently used - the route has been used for forwarding data recently
and should be maintained for a while

Broken - the link to the next hop broke or a RERR was received that
told me this route isn't good any more

I agree that RERR are only issued for recently used routes. I also
think that only Current and Recently Used routes should actually be in
the forwarding table.

What do you think?
Ian

---

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

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.

---

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

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

---

From: "Koojana Kuladinithi" <[email-masked]>
Date: Mon, 28 Aug 2006 11:11:08 +0200

Hi Ian

I have a small clarification to your slides. You have listed all
lopp-prone, stale & inferior cases (1st & 2nd slides), which we should
drop the RM. 

Isn't that following case is missing ?

"[When Seq Nums are equal]If the route is valid (by examining
Route.ValidTimeout and the current time), then the
      new information is inferior if Node.HopCnt > Route.HopCnt"

Koojana

> -----Original Message-----
> From: Ian Chakeres [mailto:[email-masked]] 
> Sent: 13 August 2006 00:40
> To: [email-masked]; Elizabeth M. Belding (work); Charles 
> E. Perkins (work)
> Subject: [Manet-dt] DYMO SeqNum Decisions
> 
> 
> 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
>

---

From: "Ian Chakeres" <[email-masked]>
Date: Mon, 28 Aug 2006 08:57:43 -0700

I think this case is handled by Node.HopCnt > Route.HopCnt +1
(loop-prone) and Node.HopCnt == Route.HopCnt +1 (inferior/superior),
and Node.HopCnt == Route.HopCnt (inferior/superior).

In this case, the info is only inferior for RREQ.

Ian

I'll send out my new proposed text in a minute.