Subject: Comments on draft-chandra-ospf-manet-ext-01.txt

From: Richard Ogier <[email-masked]>
Date: Mon, 2 Aug 2004 13:04:13 -0700

I have some comments and questions for the draft
draft-chandra-ospf-manet-ext-01.txt.
(Unfortunately, I could not make it to the meeting this week.)

I see that the following requirement has been added to 2.3.5:

 "The first Hello packet with a particular SCS number MUST contain the
 full state associated with that SCS number, and thus MUST NOT set the
 'N' bit in the State Check Sequence TLV."

Assuming that the Hello is multicast to all neighbors, does the
"full state" include all neighbors?  Or does it include
only the neighbors that recently changed state?

If the former is the case, then the Hellos are not incremental.
If the latter is the case, then I am not sure exactly
how "full state" is defined for an incremental Hello.

 From Section 2.3.6 (Receiving Hellos), I see that the initial
Hello for a new SCS number (with the N bit not set) must
be received correctly by all neighbors, and a neighbor must
send a Hello request if it discovers that it missed the
initial Hello for a given SCS number.
This concerns me, because in a MANET, a node will typically
miss a large percentage of Hellos, and thus will have to
unicast a large number of Hello requests to each neighbor.

It is possible to design the Hello protocol so that it is
OK to miss 2 out of 3 Hellos (for example) without having
to send a Hello request. TBRPF (RFC 3684) does by reporting
each neighbor change in 3 (or k) consecutive Hellos, so that
each neighbor will either learn about the state change,
or will declare the neighbor lost after missing 3 consecutive
Hellos from the neighbor. (To detect this, the Hello sequence
number is incremented with each transmitted Hello.)

Another issue is that, because different nodes can have different
transmission ranges, it is possible for a node to have many 1-way
neighbors that never become 2-way. Unfortunately, your incremental
Hellos will have to report all of these 1-way neighbors forever
in Hellos. In TBRPF, when a 1-way neighbor is discovered, it is
reported in at most 3 Hellos. (The correctness proof for TBRPF
shows that this works, and TBRPF has been throroughly tested.)

I am not trying to promote TBRPF, but am just pointing out some
potential advantages of the TBRPF Hello protocol.
Perhaps simulations should be conducted to compare these two
methods for using incremental Hellos.

I have a few additional quick comments on the draft.

There is a typo in the last bullet of 2.3.4.2:
"I bit" should be "N bit".

In Section 2.4.7 (Flooding and Relay Decisions), the first step
upon receiving an LSA from an adjacent speaker is as follows:

1.   If the node is an active overlapping relay for the adjacent
     speaker, then the router MUST immediately relay any information
     received from the adjacent speaker.

This could cause inifinite looping, since two nodes could be
overlapping relays (MPRs) for each other. I guess you mean either:
(a) the LSA is relayed if it has not already been relayed, or
(b) the LSA is relayed if it has not already been received.
The inefficiency of doing (a) has already been discussed on
this mailing list, as well as the possible incorrectness of
doing (b).

My final comment regards the use of MPRs instead of a CDS
for flooding.  This choice has been discussed, and I think
this is still an open question, but let me know if you have
concluded that MPRs is preferable.
As a review, I will list some advantages of using a CDS:

1. A CDS is simpler and is a more natural generalization of
   a DR, since each CDS node relays all LSAs (independent
   of which neighbor the LSA was received from).

2. Each node can decide whether it is a CDS node based only
   on Hellos and LSAs originated from neighbors, without having
   to compute MPRs, or to add a new TLV to report MPRs. (The DR field
   of a Hello can be used to identify a CDS node instead.)

3. A full adjacency needs to be established only between
   each CDS node and its neighbors.

Regards,
Richard Ogier

---

From: Russ White <[email-masked]>
Date: Tue, 3 Aug 2004 10:43:13 -0400

> full state associated with that SCS number, and thus MUST NOT set the 'N'
> bit in the State Check Sequence TLV."
>
> Assuming that the Hello is multicast to all neighbors, does the "full
> state" include all neighbors?  Or does it include only the neighbors that
> recently changed state?

"Full state" should probably be changed here. It's actually the full change
state, or rather all the changes occurring since the last SCS change.

> From Section 2.3.6 (Receiving Hellos), I see that the initial Hello for a
> new SCS number (with the N bit not set) must be received correctly by all
> neighbors, and a neighbor must send a Hello request if it discovers that
> it missed the initial Hello for a given SCS number. This concerns me,
> because in a MANET, a node will typically miss a large percentage of
> Hellos, and thus will have to unicast a large number of Hello requests to
> each neighbor.
>
> It is possible to design the Hello protocol so that it is OK to miss 2
> out of 3 Hellos (for example) without having to send a Hello request.
> TBRPF (RFC 3684) does by reporting each neighbor change in 3 (or k)
> consecutive Hellos, so that each neighbor will either learn about the
> state change, or will declare the neighbor lost after missing 3
> consecutive Hellos from the neighbor. (To detect this, the Hello sequence

If you do this, you don't need the sequence numbers at all. I'm concerned
about this on several fronts, though....

First, if you are losing two out of three hellos on a regular basis, the
link quality is likely to be so low that it's unusable for passing data
traffic. Second, even if you lose two out of three hellos, you must also
always miss the specific hello with a state change. So, the only place I
see advertising all state changes for three hellos as being more efficient
than the incremental hello mechanism outlined in the draft is this: If you
always have a state change in at least one out of every three hello's, and
the hello with the state change information is always lost. While this
seems possible in some short term situations, I find it stretching to think
this would happen so consistently that it's always better to send the state
change information three times.

> neighbors that never become 2-way. Unfortunately, your incremental Hellos
> will have to report all of these 1-way neighbors forever in Hellos. In
> TBRPF, when a 1-way neighbor is discovered, it is reported in at most 3
> Hellos. (The correctness proof for TBRPF shows that this works, and TBRPF
> has been throroughly tested.)

?? Then how does TBRPF form an adjacency in this situation?

A---B

A sees B, but B doesn't see A. This condition lasts for 90 seconds, long
enough for A to report B, without B seeing A's hello's. Now, B moves
somewhat closer, and starts reporting A in it's hellos. Of course, at this
point, B has no idea A can see it, and thus two way state will never be
reached.

If there's a solution to this, then we could easily adapt it to the
incremental hello solution, as well, just for one-way neighbors, without
using the "advertise three times and drop" rule. You could state that as
soon as A sees its own router id in B's hellos, it begins to advertise in
its hello's until full state is reached. Note you couldn't use the three
anddrop rule in this case, because it's entirely possible the first three
hello's A originates with B's router id before two way state is acheived
could be dropped, thus leaving the two devices forever in one way state,
with no way out.

> This could cause inifinite looping, since two nodes could be overlapping
> relays (MPRs) for each other. I guess you mean either: (a) the LSA is
> relayed if it has not already been relayed, or (b) the LSA is relayed if
> it has not already been received. The inefficiency of doing (a) has
> already been discussed on this mailing list, as well as the possible
> incorrectness of doing (b).

?? The normal OSPF flooding rules are applied here, so you would not get
into a flooding loop.

:-)

Russ

__________________________________
[email-masked] CCIE <>< Grace Alone

---

From: Richard Ogier <[email-masked]>
Date: Tue, 3 Aug 2004 23:41:30 -0700

>change information three times.
It depends on the scenario, being more beneficial to do this in very
dense networks with highly mobile nodes. If a node has 100 highly mobile
neighbors, it could easily have a state change with almost every hello,
and if a node misses 25% of the hellos from its neighbors, it would have
to unicast 25 hello requests for each hello interval. But it occurred to
me that you could do this anyway, i.e., send each state change 2 or 3
times(with the N bit not set), as an option. Simulations would be
helpful to evaluate the benefit of doing this.

>point, B has no idea A can see it, and thus two way state will never be

Sure it will, because node A will then see that B is reporting A in its
hellos, and will again report B in its hellos.  This is step 4b in
Section 7.4 of RFC 3684.  (However, this does not prove correctness.
The correctness proof is nontrival.)

>and drop rule in this case, because it's entirely possible the first three

That won't happen with TBRPF, because if B misses those 3 hellos
from A, then B will declare A to be lost, and will report the loss
of A in 3 hellos (and A will either receive one of those 3 hellos
or will declare B to be lost).  You can see how the proof might
be nontrival, so I am including it at the end of this message.

>?? The normal OSPF flooding rules are applied here, so you would not get

OK, then you are indeed doing (b), which should work fine in your case
(since you allow non-MPR nodes to relay LSAs when necessary).

Richard

>Russ

Correctness Proof for TBRPF Neighbor Discovery

The TBRPF Neighbor Discovery (TND) protocol, described in RFC 3684,
uses differential HELLO messages, which report only *changes*
in the status of links. This results in HELLO messages that
are much smaller than those of other link-state protocols such
as OSPF, in which each node must report all of its neighbors in
HELLO messages at least once per HELLO interval.

Since TND uses differential HELLO messages, its correctness is not
obvious, because HELLO messages are not sent reliably, and thus a
HELLO that reports a change in the status of a link to a neighbor
might not be received by the neighbor.

We first review some aspects of TND that will help to understand
the proof.  Although TND supports multiple interfaces, TND is run
separately on each interface, so without loss of generality we
consider only one interface.

In TND, each node must broadcast (to all neighbors) at least one
HELLO message every HELLO_INTERVAL seconds.  Each HELLO message
includes three (possibly empty) lists: the NEIGHBOR REQUEST list
includes neighbors whose status has recently changed to 1-WAY,
the NEIGHBOR REPLY list includes neighbors whose status has recently
changed to 2-WAY, and the NEIGHBOR_LOST list includes neighbors
whose status has recently changed to LOST.

When a node i changes the status of a link (i,j), it includes the
neighbor address j in the appropriate list
(NEIGHBOR REQUEST/REPLY/LOST) in NBR_HOLD_COUNT (NHC, typically 3)
consecutive HELLOs, or until it receives a reply from node j
(whichever comes first). This ensures that node j will either
receive one of these HELLOs, or will miss NHC consecutive HELLOs
from node i. In the latter case, node j will declare the link
(j,i) to be LOST.

TND employs hysteresis as follows.  A node i must receive at least
HELLO_ACQUIRE_COUNT (HAC, typically 2) of the last
HELLO_ACQUIRE_WINDOW (HAW, typically 3) HELLOs sent by node j
before changing the status of link (i,j) from LOST (or nonexistent)
to 1-WAY or 2-WAY.  However, once the link (i,j) becomes 1-WAY
or 2-WAY, node i changes its status to LOST only if it misses NHC
consecutive HELLOs from node j, or if it receives a HELLO from
node j which includes node i in the NEIGHBOR LOST list.
(A node detects that NHC consecutive HELLOs were missed either
based on the HELLO sequence number of by not receiving any
HELLO for NBR_HOLD_TIME seconds).

Definition: We say that link (i,j) satisfies the 1-WAY condition
at time t, if there exists a time t' < t such that node i received
HAC of the last HAW HELLOs from node j at time t', and node i did
not miss any NHC consecutive HELLOs from node j during the time
interval [t', t].

It is clear from the description of TND that if a link (i,j) satisfies
the 1-WAY condition, then node i considers the link to be either 1-WAY
or 2-WAY. It is also clear that if a link (i,j) does not satisfy the
1-WAY condition, then node i considers the link to be LOST (or
nonexistent).  However, it is not clear, for example, that node i
will correctly detect a change in the status of link (i,j) from 2-WAY
to 1-WAY. This example is covered by the unidirectional case in
the following theorem, which proves the correctness of TND by
considering the three possible cases: bidirectional, unidirectional,
and lost in both directions.

Theorem. Consider two nodes i and j at a given time t.
(a) Bidirectional case: If links (i,j) and (j,i) have both satisfied
the 1-WAY property for at least 2*NHC*HELLO_INTERVAL seconds, then
both nodes i and j consider the link between them to be 2-WAY.

(b) Unidirectional case: If link (i,j) has satisfied the 1-WAY
property for at least NHC HELLO intervals, and (j,i) has failed
to satisfy the 1-WAY property for at least HNC*HELLO_INTERVAL
seconds, then node i considers the link (i,j) to be 1-WAY, and
node j considers the link (j,i) to be LOST.

(c) LOST in both directions: If links (i,j) and (j,i) both fail to
satisfy the 1-WAY property, then both nodes i and j consider the
link between them to be LOST.

Proof. Case (c) is trivial since, as mentioned above, if link (i,j)
does not satisfy the 1-WAY property, then node i must consider
the link to be LOST.

Now consider case (a). Since links (i,j) and (j,i) both satisfy the
1-WAY condition at time t, both nodes i and j must consider the
link between them to be 1-WAY or 2-WAY.  Let t' be the last time
that either node changed the link status from LOST/nonexistent
to 1-WAY or 2-WAY, and assume without loss of generality that this
status change occured at node i.  (There must be such a time since
the status of each link is initially LOST/nonexistent.)
It follows that (i,j) and (j,i) both satisfied the 1-WAY condition
during the interval [t', t], which by the Theorem's assumption
implies that t - t' is at least 2*NHC*HELLO_INTERVAL seconds. Since
the link status at node j was 1-WAY or 2-WAY at time t', node i must
have received a HELLO message from node j at time t', which could
not have included node i in the LOST list.  In response, node i
included node j in the REQUEST or REPLY list in its next NHC HELLOs
after time t', or until it saw itself in the REPLY list of a HELLO
message sent by node j.  If the latter case occured, then the status
at node j at some time after t' was 2-WAY, and upon receiving this
message, node i then changed the link status to 2-WAY which would
imply that the link status at both nodes is still 2-WAY at time t,
since a link status cannot change from 2-WAY unless one of the two
nodes declares the neighbor LOST.

If the former case occured, then node j would have received one of
the NHC HELLO messages (by time t' + NHC*HELLO_INTERVAL), since
otherwise it would have changed the link status to LOST.  Node j
would therefore respond by setting the link status to 2-WAY and
including node i in the REPLY list in its next NHC HELLOs, and
node i would have received one of these NHC HELLOs (by time
t' + 2*NHC*HELLO_INTERVAL < t), since otherwise it would have changed
the link status to LOST.  Upon receiving one of these HELLOs, node i
would have changed the link status to 2-WAY. Again, this implies that
the link status at both nodes is still 2-WAY at time t, since a state
cannot transition from 2-WAY unless one of the two nodes declares
the neighbor LOST.

Now consider case (b). Since link (j,i) fails to satisfy the 1-WAY
condition, then (as mentioned above) node j must consider the link
to be LOST at time t.  We consider two subcases: (b1) link (j,i)
never satisfied the 1-WAY condition, i.e., was always LOST;
and (b2) link (j,i) satisfied the 1-WAY condition at some time in
the past.  If subcase (b1) is true, then node j would never include
node i in the REQUEST or REPLY list of any transmitted HELLO.
As a result, node i could not have changed the status of link (i,j)
to 2-WAY.  Therefore, since link (i,j) satisfies the 1-WAY condition
(implying that node i must consider the link to be 1-WAY or 2-WAY),
node i must consider the link to be 1-WAY.

Now suppose subcase (b2) is true, and let t' be the last time that
node j changed the status of link (j,i) from 1-WAY or 2-WAY to LOST.
Then node j must have included node i in the LOST list in its next
NHC HELLOs after time t'. Node i either received one of these HELLOs,
or missed NHC consecutive HELLOs; in either case node i must have
considered the link to be LOST at some time between time t' and
time t.  Since node j considered the link to be LOST during the
entire interval [t', t], it could not have included node i in the
REQUEST or REPLY list of any transmitted HELLO during this interval.
Therefore, as in subcase (b1), node i could not have changed the status
of link (i,j) to 2-WAY.  Therefore, since link (i,j) satisfies the
1-WAY condition, node i must consider the link to be 1-WAY.
This establishes case (b) and completes the proof of the theorem.