Subject: [manet] Re: RE : others cretaria in MANET routing protocol

From: [email-masked]
Date: Mon, 04 Mar 2002 10:11:55 -0800

> 
> I'll argue that hop count in and of itself is a poor indicator.  Consider 
> the following
> 
>          A--------------------->B
>           ---------->C--------->
> 
> B and C can both hear A; C hears A with an excellent S/N Ratio and B hears 
> A with a poor signal to noise ratio, such that a small percentage of 
> packets (less than some threshold measured in percent) can actually 
> traverse A->B. I will argue that A->C->B is much kinder to the application 
> than A->B, so adding a hop creates a significantly improved route even 
> though the smaller hop count would be nice.
> 
> It seems to me that hop count might be a tie-breaker amount routes of equal 
> robustness, not the other way around.

I agree that MANET routing protocols should allow the selection of 
paths that are shortest w.r.t. a metric (which OSPF does).  This metric 
can take into account signal strength, reliability, bandwidth, link 
stability, etc.  The following example shows why computing a shortest 
path w.r.t. a metric is better than simply deciding whether or not
to use an adjacent link based on whether the link quality is above
or below certain thresholds (e.g., using hysteresis).

       .9   .9   .9
     2 -- 3 -- 4 -- 5
 .9 /                 \ .9 
   1                  10
.89 \                 / 1.0
     6 -- 7 -- 8 -- 9
       1.0  1.0  1.0  

Node 1 wants to select the best path to node 10.
The numbers indicate the reliability for each link.
(Actually, the negative log of the reliability would be
used so that the metric is additive.)
Consider a protocol (which could be OLSR or TBRPF) that selects a 
min-hop path subject to a link quality threshold, and suppose that 
the threshold is .9.  That protocol would use the upper path,
which has reliability .9 * .9 * .9 * .9 * .9 = .59.
However, a protocol that takes into account the metric
of each link along the path would use the lower path, which 
has a much better reliability of .89 * 1 * 1 * 1 * 1 = .89.

Also, it is possible that the *only* path to some node is
one that uses a poor quality but usable link. If only hysteresis
is used, that node would be unreachable (even if an urgent message
must be sent to that node).  It is better to *allow* the use of
of a poor quality link, but select paths based on a link metric so 
that a poor quality link is used only if necessary.

Hop count is also an important objective for MANETs because a packet 
that travels more hops consumes more bandwidth.
Assuming that Dijkstra's algorithm is used by a link-state routing 
protocol to compute shortest paths, the following link cost (used
by TBRPF) will achieve a tradeoff between minimizing the number of 
hops and minimizing a metric:

  c(u,v) = 1 + COEFF * metric(u,v)

If COEFF is very large, then hop count is used only as a tie breaker,
and if COEFF is very small, then the metric is used as a tie breaker.  

We used metrics in the original (full-topology) version of TBRPF,
but dropped them in the partial-topology version in order to
reduce overhead.  We are adding them back as an option in TBRPF
version 05 (submitted last week) because (1) our simulations
(which can be found at www.erg.sri.com/projects/tbrpf)
show that TBRPF generates much less routing overhead than OLSR,
and the inclusion of 8-bit metrics in topology updates increases this 
overhead by only a small amount; and (2) our laboratory experiments
show that the use of metrics can improve performance.

I should also mention that TBRPF version 05 supports multiple 
interfaces and network prefixes.  However, no major changes have 
been made to the core protocol.

Richard

P.S. I thought about the possibility of modifying OLSR so that it 
computes shortest paths w.r.t. a link metric (instead of computing 
min-hop paths subject to the quality of each link being above some 
threshold).  It is not as easy to do this in OLSR, because of the 
requirement that paths must use links (u,v) such that v selected u as 
a multipoint relay (except for the first hop).  This requirement 
severely reduces the path choices, so that the shortest path w.r.t. 
a given metric (other than the hop metric) is not likely to 
satisfy this requirement.

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: [email-masked]
Date: Mon, 04 Mar 2002 10:11:55 -0800

.9   .9   .9
     2 -- 3 -- 4 -- 5
 .9 /                 \ .9 
   1                  10
.89 \                 / 1.0
     6 -- 7 -- 8 -- 9
       1.0  1.0  1.0  

Richard

---

From: Laurent Viennot <[email-masked]>
Date: Tue, 5 Mar 2002 10:41:29 +0100

Concerning costs on links, I would argue that the situation is very
different from classical link state. Indeed, with radio media, two
different links may interact. Consider for example links A--B and
C--D where each of A,B,C,D can hear each other. If you want your cost
to reflect the available bandwidth then a cost per link is not very
meaningful.

We have already thought about introducing costs in OLSR, there are
simple ways to do that. One of our conclusion considering the above
remark is that putting costs on links is not always meaningful. A
better choice would be to put a cost on interfaces (to reflect for
example the medium utilization around the interface or the power
available on the node).

Two remarks about using power level information :

Considering power saving paths, recall that you may gain on the
emission of packets but the reception is also very costly. A node
consumes power when listening (even when non packet is received).  A
better way of saving power seems to allow nodes to go in sleep mode
from time to time.

Concerning the use of S/N ratio as a cost on links, it seems to me a
heavy solution where a simple link hysteresis is sufficient. Under a
certain threshold, the link is not usable and above a certain
threshold the link will work fine independently from the S/N ratio. So
the matter with the use of S/N information is more to select correct
links than using S/N ratio as a cost function.

laurent

---

From: Laurent Viennot <[email-masked]>
Date: Tue, 5 Mar 2002 10:41:29 +0100

laurent

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 5 Mar 2002 12:08:24 +0100

I don't see the problem. It suffices that the node selects its MPR nodes on
the shortest paths (with respect to the considered metric) to its 2-hop
neighbors. This is pretty straightforward.

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 5 Mar 2002 12:08:24 +0100

Philippe

---

From: [email-masked]
Date: Tue, 05 Mar 2002 19:25:17 -0800

> neighbors. This is pretty straightforward.

Yes, I agree it is straightforward if you are willing 
to give up your heuristic that attempts to minimize the 
number of MPRs.  But then of course you will have more MPRs, 
which could increase overhead.  

Also (as you know) unless you assume that link costs are symmetric
(which is not a good assumption), each node needs to compute
the shortest path to each 2-hop neighbor using the link costs
for the *reverse* links (from the 2-hop neighbors), since 
data packets travel in the reverse direction along these paths.
This seems to require that each node report the link costs
for both its outgoing links and incoming links.

Richard

---

From: [email-masked]
Date: Tue, 05 Mar 2002 19:25:17 -0800

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 6 Mar 2002 11:27:23 +0100

Dear Richard,

You are just defining a different metric to the *coverage cost* of MPR and
this leads to a straightforward adaptation of the heuristic. Nothing very
surprising in this. About increasing the overhead I think it is a possible
outcome, since you want to optimize the network in something else than the
hop count and the number of retransmissions. I expect that you will also
have to report more nodes and increase your overhead as well (unless you
take your strange option of full tree report that anyhow rise your overhead
to a maximum).

If OLSR were taking a metric option, the link costs would likely be
advertized in TC packets. But as Laurent explained, we don't think link cost
is a good option since links are not isolated. Furthermore link cost would
likely change frequently and link cost advertizement update would incur a
lot of overhead (any new traffic will affect costs of all links of all the
nodes one hop away from the route).

One realistic design could be to affect the cost on a per node and per
interface basis as Laurent explained. My two cents: in order to limit the
update overhead one could set the interface cost to the nominal capacity of
the interface. But there is the endless issue on how to standardize an
interface cost...

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 6 Mar 2002 11:27:23 +0100

Dear Richard,

Philippe

---

From: [email-masked]
Date: Wed, 06 Mar 2002 11:11:28 -0800

Philippe,

> take your strange option of full tree report that anyhow rise your overhead

Strange option?  I don't see anything strange about having
a node report its full source tree.
Our simulations show that having each TBRPF node report its
full source tree increases routing control traffic by about 50%
(including IP/MAC headers), so that even with this option (which 
also simplifies the protocol), TBRPF still generates less control 
traffic than OLSR, even though TBRPF sends HELLOs twice as frequently.

> nodes one hop away from the route).

Advertising a 4-bit link cost for each advertised link would
increase overhead by at most 4/32 = 12.5%, and actually much
less than this if you count packet headers.
You can control the overhead for reporting link costs by
reporting them only periodically, not whenever they change.
(I.e., you would report the link cost only when you would
normally report the link anyway.) 

> the interface. But there is the endless issue on how to standardize an

I agree that a cost per node and per interface would be good, as I 
have discussed with my coworkers several months ago.
In fact, TBRPF also allows wired interfaces (e.g., to a point-to-point
link or an Ethernet), which would have a lower cost than
a wireless interface.

But I think that link costs are also useful, as I believe the
example I gave two days ago shows (in which using link costs 
increases the end-to-end reliability from .59 to .89). 
Link costs are also useful if power control is used, since the power 
required to reach a neighbor depends on the distance to that neighbor.

Richard

---

From: [email-masked]
Date: Wed, 06 Mar 2002 11:11:28 -0800

Philippe,

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 7 Mar 2002 19:00:02 +0100

----- Original Message -----
From: <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>
Sent: Wednesday, March 06, 2002 8:11 PM
Subject: Re: [manet] Re: RE : others cretaria in MANET routing protocol

> traffic than OLSR, even though TBRPF sends HELLOs twice as frequently.
By strange I just minded that it seems to implicitly acknowledge
unreliability in TBRPF. This change was introduced in your January
submission and was never commented. It seems to be redundant and maybe in
conflict with the older option of reporting additional links. Does it add to
the provability of the protocol?

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 7 Mar 2002 19:00:02 +0100

----- Original Message -----
From: <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>
Sent: Wednesday, March 06, 2002 8:11 PM
Subject: Re: [manet] Re: RE : others cretaria in MANET routing protocol

Philippe

---

From: [email-masked]
Date: Fri, 08 Mar 2002 11:25:22 -0800

Philippe,

<SNIP> 

> the provability of the protocol?

You try to find (or imply) fault where there is none. The option in 
which a node can report its full source tree is just a very simple 
way to report additional links, thus potentially increasing 
robustness in highly mobile networks.
It is not in conflict with the other option, which allows a node
to report links that are not in its source tree.  As long as each node 
reports the minimum information (i.e., its reportable subtree), it can 
report additional links that it knows about.

TBRPF is correct with or without these options, and our simulations 
show that it performs very well even if only the minimum information 
is reported.  Sending the minimum information minimizes overhead,
which improves scalability and allows TBRPF to be used in low-bandwidth
radios such as those used by the military.  But if sufficient bandwidth
is available in a highly mobile network, it makes sense to allow
additional topology information to be reported to improve robustness.

Richard

---

From: [email-masked]
Date: Fri, 08 Mar 2002 11:25:22 -0800

Philippe,

<SNIP> 

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Mon, 11 Mar 2002 18:35:55 +0100

Richard,

I am not looking for errors. This would be a very unpleasant task and the
protocol is far too complex for that. I am just looking for proofs. Unlike
OLSR, TBRPF is not known to be proven. OLSR proofs are rather simple. There
is nothing in the optimisations we have introduced so far that don't go
along OLSR proofs of correctness. Do you have a proof of TBRPF correctness?
I have just some doubts that obsolete topology informations may endlessly
circulate in the network and your complex optimisation process may
potentially increase this risk. I was wondering if  a simpler version of the
protocol without optimisation may have helped you to figure out a proof of
correctness.

Philippe

----- Original Message -----
From: <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>
Sent: Friday, March 08, 2002 8:25 PM
Subject: Re: [manet] Re: RE : others cretaria in MANET routing protocol

<SNIP>

---

From: "Philippe Jacquet" <[email-masked]>
Date: Mon, 11 Mar 2002 18:35:55 +0100

Richard,

Philippe

----- Original Message -----
From: <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>
Sent: Friday, March 08, 2002 8:25 PM
Subject: Re: [manet] Re: RE : others cretaria in MANET routing protocol

<SNIP>

---

From: "Tao Lin" <[email-masked]>
Date: Mon, 11 Mar 2002 17:20:45 -0500

TBRPF provides information for only one path (or maybe two, like an optional
choice indicated in the TBRPF draft) per destination. In a network with
heavy multicast traffic load, I think it might have more congestions with
TBRPF protocol. Are there any multicast extensions for TBRPF or studies on
this topic?

Thanks!

Tao Lin

---

From: "Tao Lin" <[email-masked]>
Date: Mon, 11 Mar 2002 17:20:45 -0500

Thanks!

Tao Lin

---

From: [email-masked]
Date: Tue, 12 Mar 2002 13:30:36 -0800

Tao,

> TBRPF protocol. Are there any multicast extensions for TBRPF or studies on

Yes, you can find our multicast extension to TBRPF at the the TBRPF web site: 
http://www.erg.sri.com/projects/tbrpf/docs/tbrpf_multicast.doc

We also have a flooding extension which is described in our updated draft:
http://ietf.org/internet-drafts/draft-ietf-manet-tbrpf-05.txt

It may also be possible to adapt multicast protocols developed for
other link-state routing protocols, or to use one that is independent
of the underlying routing protocol.  However, my understanding is that
multicast is not currently within the manet scope.

Richard

---

From: [email-masked]
Date: Tue, 12 Mar 2002 13:30:36 -0800

Tao,

Richard

---

From: [email-masked]
Date: Tue, 12 Mar 2002 14:37:21 -0800

Philippe,

The correctness proof for TBRPF is given below.
The property that prevents topology information from endlessly
circulating is the "reporting neighbor rule" (defined below).
This is the same concept that ensures correctness for SPTA
[Bertsekas and Gallager, Data Networks, 1987].  

TBRPF is not really very complex. In fact, the Update_Routes() 
procedure is just a variant of Dijkstra's algorithm, and can be 
implemented so that its running time is the same order as Dijkstra's.
Actually, in some ways TBRPF is simpler than OLSR, which I will discuss
in a later email.  Some aspects of TBRPF may be a little more complex 
than OLSR, but this should be acceptable if it results in significantly
better performance/efficiency.

First I will review some aspects of TBRPF that will help to understand 
the proof. Let RN(i) denote the reportable node set RN that is computed 
by node i. A neighbor j is in RN(i) if and only if there exists another 
neighbor k that is not a neighbor of j, such that node i is the node 
with the smallest ID through which node k can reach node j in 2 hops.  
RN is computed by the procedure Update_RN(), which simply computes 
min-hop paths, up to 2 hops, from each neighbor to each other neighbor.

Each node reports part of its source tree T, called its reportable 
subtree RT, to neighbors in periodic and differential updates.  A node 
uses RN to determine which part of T to report, as follows: A node 
reports all of its adjacent links, and reports only the branches of T 
that are rooted at neighbors in RN.  Each node i maintains the 
reportable subtree RT_j reported by each neighbor j. 

The procedure Update_Routes() is a variant of Dijkstra's algorithm that 
computes min-hop paths to all nodes, and also updates the topology graph
TG, which consists of the links that are "believable". A link (u,v) is
believable if and only if it is reported by the next hop p(u) on the 
min-hop path to node u. This is similar to SPTA, which also does not 
use sequence numbers, maintains the topology reported by each neighbor,
and maintains a set of "believable" links. 
However, in SPTA each node reports the full topology, whereas in TBRPF 
each node reports only part of its source tree.

The paths computed by Update_Routes() have the following two properties
which are important to ensure correctness: 

(1) Reporting neighbor rule: A link (u,v) can be in a computed path (to
any destination) only if it is reported by the next hop p(u) on the path
(i.e., only if it is in TG).

(2) The predecessor (next-to-last node) on the min-hop path to any node
is selected to have the minimum ID. As a result, the computed paths are 
"lexicographic" min-hop paths, defined as follows.

Definition. A min-hop path from node i to node u, with nodes 
i = v_1,..., v_n = u, is said to be a "lexicographic" min-hop path if,
for each m = 2,..., n-1, node v_m has the minimum ID of any predecessor 
to node v_{m+1} in any min-hop path from node i to node v_{m+1}.

A link (u,v) can actually remain in TG for a few seconds 
(PER_UPDATE_INTERVAL) after it is no longer reported by p(u), but this 
does not affect the proof below, since this is only a temporary 
violation of the reporting neighbor rule.

The following proof is similar to the proof of SPTA, and is also similar
to the proof of PTSP [MOMUC '99], which also does not use sequence numbers
and has each node report only part of its source tree.

Theorem 1. If no topology changes occur after some time t_0, then within
some finite time after t_0, the source tree T computed by each node will
contain min-hop paths to all reachable nodes.

Proof. The proof will be by induction on the number of hops m.

Induction hypothesis: For each m = 1,2,..., there exists some finite 
time t_m after which each node (1) has computed a lexicographically 
minimum min-hop path to each node u that is m or fewer hops away, 
and (2) has not computed a path of m or fewer hops to any node that 
is more than m hops away (or is unreachable).

The hypothesis is trivially true for m = 1, since each node knows its 
set of neighbors.  (We assume that neighbor discovery is done correctly.)

Now suppose the hypothesis is true for some m >= 1.  We will show that 
it is true for m+1, which will prove the theorem by induction.

Since each node reports its reportable subtree RT in periodic 
updates, any link that remains in RT is received by all neighbors within 
finite time.  Conversely, since topology information from neighbors 
expires after TOP_HOLD_TIME, if a node removes a link from RT, then
all neighbors will know it is removed within this time interval.

Let i be any node, and let u be any node that is exactly m+1 hops from 
node i. Let P be the lexicographic min-hop path from node i to node u. 
Let j be the second node (next hop), let k be the third node, and let 
w be the next-to-last node on P.

Since node u is m hops from node j, the induction hypothesis for m 
implies that node j has computed the lexicographic min-hop path to 
node u, which by the definition of lexicographic must equal the part
of P from j to u. Also by the definition of lexicographic, node j is 
the next hop from node i to node k having the smallest ID, implying 
that k is in RN(j), so that node j is reporting the branch of its 
source tree rooted at node k. In particular, node j is reporting 
the link (w,u).

Consider the point in Update_Routes() after all m-hop paths have been
computed. By the induction hypothesis for m, node i has computed a 
lexicographic min-hop path to each node that is m or fewer hops away, 
including node w, and has not computed a path having m or fewer hops 
to any node that is more than m hops away.  As a result, since node j 
is reporting link (w,u) and since w is the minimum ID predecessor to 
node u, Update_Routes() will add link (w,u) to its source tree, so that 
its computed path to u is P.  This proves the first part of the 
induction hypothesis for m+1.

To prove the second part, let v be any node that is more than m+1 
hops away from node i, and suppose that node i has computed a path Q 
to node v.  By the reporting neighbor rule, the second node k on Q
must be reporting the part of Q from k to v.  Since node v is more 
than m hops away from node k, by the induction hypothesis for m, 
the path computed by k to node v must have more than m hops, implying 
that path Q has more than m+1 hops.  This proves the second part of 
the induction hypothesis for m+1, thus proving the theorem.

Richard

---

From: [email-masked]
Date: Tue, 12 Mar 2002 14:37:21 -0800

Philippe,

Richard