Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper

From: "Green, David B RDECOM CERDEC STCD SRI" <[email-masked]>
Date: Thu, 6 Jan 2005 15:22:29 -0500

Roy,
To expound on the "other constraints" you mentioned in this statement:
"So far from what I have seen, the SI-CDS algo's need at least an
order of magnitude higher computational power. It might to useful
to quantify that for a reasonable size network. Also there are
other constraints (e.g. all nodes are assumed to be running same
algo) which may make it prohibitive in deployments."

As a note, in a tradeoff between computational power vs. number of transmissions 
necessary to flood routing information, I think you will find using computational power to pre-determine the optimal path is cheap when compared to the cost of extra transmissions on most radios. Throughput, low delay, and transmission power costs are at premium in most actual MANET nodes. If it takes an order of magnitude longer to compute an optimal path in a CPU, the delay and power costs will generally be far cheaper than the cost 
of an extra transmission on the network. We recently modeled data compression as a tradeoff 
in CPU time vs. transmission time in JTRS-type radios and found the transmission cost (delay & power consumption)  for a single extra transmission was several order's of magnitude higher than the CPU cost to reduce the number of transmissions. 

Transmission cost for each radio datagram must factor:

IP Header 
UDP or TCP Header   
Security Header  
Radio Network Header 
Radio Link Layer Header  
Modem Framing 
CRC  FEC 
Waveform Framing  
Power Amp Tuning Time
Synchronization Probe Overhead   
Channel Acquisition (RTS/CTS)   
Frame Acknowledge (ACK)
Average Contention Interval  

OPNET does have the ability to model CPU usage so we compared CPU time costs to the cost of the number of data transmissions on the network and found a several orders of magnitude delta for data compression in some cases. As a caveat - our compression time performance was linear with respect to the data set size while path algorithms are exponential or logarithmic to the number of nodes in the data set. However, I think you will still have a large tradeoff delta between computation costs vs. transmission costs. 

David Green 
CERDEC Site Manager
SRI International
Office: (732) 532-6715
Mobile: (732) 693-6500

-----Original Message-----
From: Abhay Roy [mailto:[email-masked]]
Sent: Wednesday, January 05, 2005 1:06 PM
To: Richard Ogier
Cc: [email-masked]
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper

Richard,

Thanks for the example. One of the confusions I have had is when
we call it SI-CDS. It's still source dependent, it's just that
nodes are doing computation from every one of it's neighbor's
perspective.

Are there really any source independent CDS algo's? In my mind
that will be something where a node elects itself as an Active
relay irrespective of where the source of flood comes from. The
algo you describe below does seem to fall in that category. If
yes, we should perhaps use different terminology (SD-CDS /
SI-CDS?) to distinguish them.

One other thing which we have not discussed much is, how to adapt
these CDS algo's to work with reliable flooding. Note that we have
agreed to focus only on reliable flooding right now. The proposal
we made has a notion of non-active relay. In short, if you are not
active, you assume to be non-active and using PushbackInterval's
try to suppress flooding if someone else is already doing it.

We can use the same notion with CDS algo's and assume that the
rest of the nodes are non-active, but do become active if needed.

Some questions inline..

On 12/23/04-0800 at 8:02am, Richard Ogier writes:

> Hi Roy,
>
> Here is an example where MPRs result in 3 times
> as many transmissions as a SI-CDS.
>
>     5
>  /  |  \
> 1-- 6-- 3
> |   |   |
> 2-- 7-- 4
>  \  | /
>     8
>
> Node 5 is the source.
> The MPRs that forward LSAs from node 5 are {1, 6, 3, 2, 7, 4}.
> The SI-CDS is {6, 7}, obtained using the algorithm below
> which runs in O(d^2) time using a modified BFS algorithm,
> where d is the number of neighbors.
>
> The drawback of MPRs in this case is that they are required to provide
> min-hop paths, whereas a SI-CDS does not have this requirement.
> Of course, this is a special example, and simulations will tell us
> what happens on average.

Agree. I am curious to see how this works with various mobility
scenario's and reliable flooding constraints.

> But even if the SI-CDS were the same size as the MPR set,
> I would favor the SI-CDS because of several other advantages,
> such as faster convergence.

So far from what I have seen, the SI-CDS algo's need at least an
order of magnitude higher computational power. It might to useful
to quantify that for a reasonable size network. Also there are
other constraints (e.g. all nodes are assumed to be running same
algo) which may make it prohibitive in deployments.

> I plan to submit a draft next week that
> presents a family of CDS algorithms, including the one below,
> along with some simulation results.
>
> Minimal CDS Algorithm
>
> 1. If node i has a larger value of (RtrPri, RID) than any of its
> neighbors, then node i selects itself as a DR.

Do you really mean DR here? We are working with an assumption that
the MANET interface is a p2mp interface, so no DR/BDR election.
Maybe you mean elects itself as "active"?

If I have 2 nodes with (100, 1.1.1.1) and (10, 2.2.2.2), which one
is larger? I guess I don't understand the need for RtrPri above.

Also this step seems arbitrary in electing a relay v/s say "If I
have a higher degree than any of my neighbors".

> 2. Else, let j be the neighbor of node i that has the largest
> value of (RtrPri, RID).  If there exists a path (with one or more
> hops, based on node i's 2-hop neighbor information) from node j to
> each other neighbor of node i, using only intermediate nodes
> that have a larger value of (RtrPri, RID) than node i,
> then node i does not select itself as a DR; otherwise node i
> selects itself as a DR.

This almost sounds like we have to run a constrained SPF rooted at
j for each of neighbors of i.

Regards,
-Roy-

> Happy Holidays!
> Richard
>
>
> Abhay Roy wrote:
>
> > Hi Tao,
> >
> > It's good to hear from you first hand on this topic. What may be
> > useful to further this discussion is an example or two, where we can
> > demostrate that the improved algorithm comes up with a smaller set. In
> > my mind, it's still very fuzzy how this happens ;)
> >
> > Also, since we are going to be doing simulations under Tom's GTNetS
> > tool, we will need to include Tao's algorithm in there.
> >
> > Regards,
> > -Roy-
> >
> > On 12/21/04-0500 at 1:05pm, Tao Lin writes:
> >
> >> Hi Madhavi,
> >>
> >> Just one comment on the paragraph in your email (see
> >> below).
> >>
> >> If a CDS algorithms only requires that all nodes are
> >> broadcasting their neighbor lists to their neighbors,
> >> we can 99.99% sure that all nodes work 'ideally'.
> >> This is because the information it requires is the
> >> minimized information set (which is also included in
> >> the information required for source dependent CDS
> >> algorithms).  If this cannot be guaranteed, those
> >> source dependent algorithms will also fail.
> >> Furthermore, even if somehow a hello message is lost,
> >> neighboring nodes can recover from that lost at the
> >> next hello time.
> >>
> >> Therefore, the source-independent algorithm using only
> >> 2-hop neighbor information can work at least as
> >> 'independently' as other source-dependent algorithms.
> >>
> >> Have a great day!
> >>
> >>   Tao
> >>
> >> --- "Madhavi W. Chandra" <[email-masked]> wrote:
> >>
> >>> On another note, is it fair to say that a
> >>> source-independent CDS
> >>> algorithm is actually more *dependent* on all of the
> >>> nodes behaving
> >>> 'ideally'...running the same selection algorithm,
> >>> agreeing on their
> >>> IDs, etc....whereas a source-dependent overlapping
> >>> relays/MPR
> >>> algorithm is more flexible?
> >>>
> >>> Regards,
> >>> Madhavi
> >>>
> >>
> >>
> >>
> >> ______________________________________________________________________
> >> Post your free ad now! http://personals.yahoo.ca
> >>
> >> _______________________________________________
> >> Ospf-wireless-design mailing list
> >> [email-masked]
> >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >>
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
>

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: Richard Ogier <[email-masked]>
Date: Fri, 07 Jan 2005 09:21:15 -0800

Roy,

Please see my comments and answers below.
Many of your questions will be answered in more detail
in the draft I will be submitting in a few days.

>nodes are doing computation from every one of it's neighbor's
In the algorithm I describe below, node i is doing computation
from the perspective of only one neighbor, the one with maximum
value of (RtrPri, RID).

>SI-CDS?) to distinguish them.

Yes, the CDS computed by each algorithms in my draft is SI.
A CDS is just a set of nodes.  If different CDS's are computed
for different sources, then that should be made clear.
I have not seen an algorithm that explicitly computes a SD-CDS.
For example, if we are talking about the set of nodes that transmit
a given LSA using MPRs, then this set is SD, but is also
dependent on the order in which a node receives LSAs, so the CDS
is not explicitly computed in advance.

Perhaps a more important distinction is whether the relays
(whether CDS or MPR) select themselves, or are selected
by neighbors.

>rest of the nodes are non-active, but do become active if needed.
My new draft will cover this. But in my draft, backup CDS nodes are
computed in advance, and are selected to provide biconnectivity.
My draft will give more details, but I will include a summary of
features at the end of this message.

>order of magnitude higher computational power.
>
The CDS algorithm described in my email, and the ones in my draft
that result in the smallest CDS, require only O(d^2) time,
where d is the number of neighbors.
It is not possible to do beter then this, since it requires
this much time just to process all neighbors' Hellos.
Dijkstra also requires more time than this, since d^2 < d*n = m,
where n is the number of nodes and m is the number of edges.
Also, consider how many orders of magnitude faster today's
procesors compared to the 80s, when Dijkstra was first used
in OSPF.  My draft also proposes an optional CDS algorithm
that runs in O(n^3) time, but even this should be acceptable,
since the bottleneck in MANETs is bandwidth, not processing.

>It might be useful
First of all, consider the DR selection algorithm of OSPF.
It requires that all nodes in the broadcast network agree
that the router with maximum (RtrPri, RID) should be the DR
(unless there is already an existing DR). The algorithms
in my draft also give preference for routers with the largest
value of (RtrPri, RID), and in fact they generalize OSPF's
DR selection algorithm. So, the use of a SI-CDS is quite
consistent with the philosophy of OSPF.
Morever, you will see in my draft that there is a lot of
flexibility possible, given the preference for such routers.

(Obviously, we don't need to allow each router to run
any algorithm it wants.)

However, MPRs have a serious limitation that is
illustrated by my example. MPRs must be selected to
provide flooding along min-hop paths.
They cannot trade off path optimality to reduce
the size of the relay set.

>Maybe you mean elects itself as "active"?
I really want to use the term DR here, because is generalizes
the OSPF concept of a DR.  Consider a 1-hop MANET network, which
is equivalent to a wireless broadcast network  In such a network,
the CDS algorithms I propose will select the same DR and
Backup DR as OSPF would in a broadcast network.

>is larger? I guess I don't understand the need for RtrPri above.
This will become clear in my draft. RtrPri can depend on node degree,
or neighbor stability, or willingness to relay, etc.

>have a higher degree than any of my neighbors".
I guess I just answered this above, since RtrPri can depend on degree.
I would rather not insist that all nodes choose RtrPri in the same way,
to allow flexibility while ensuring interoperability. Besides,
some CDS algorithms perform better when node degree is not used.

>j for each of neighbors of i.
No, just a single (modified) SPF rooted at the single neighbor j.
That is how I get O(d^2).

Here is a summary of features from my draft to be submitted in
a few days:

  - The document presents a family of interoperable CDS algorithms,
    which allow a tradeoff between path optimality and CDS size.
    Simulation results are presented to show this tradeoff.

  - The CDS algorithms are based only on 2-hop neighbor information,
    to provide fast convergence following topology changes.

  - The CDS algorithms are interoperable because the CDS computed by
    each algorithm contains a minimal, source-independent CDS called
    the "Essential" CDS. The Essential CDS can be computed in O(d^2)
    time, where d is the number of neighbors.

  - The Essential CDS is very scalable, as shown by the simulation
    results in Section 10. In a 300 node network with average degree
    64 and diameter 5, the Essential CDS consists of only 23 (8%) of
    the nodes on average.

  - The Essential CDS provides a minimal, source-independent set
    of relays for flooding LSAs (or other flooded packets).
    The flooding procedure also allows source-dependent flooding
    (using previous-hop information) as an option, if it is desired
    to flood packets along min-hop paths.

  - For improved CDS stability, each algorithm in the family has a
    "persistent" version, in which a router in the CDS remains in
    the CDS until it becomes redundant.

  - Generalizes the OSPF concept of a Designated Router (DR) and
    Backup DR to MANETs. The set of DRs forms a CDS, and the set of
    DRs and Backup DRs forms a biconnected CDS for robustness.
    When applied to a broadcast network, the persistent version of
    each algorithm computes the same DR and Backup DR as OSPF.

  - Adjacencies are formed only between CDS nodes (DRs and Backup DRs)
    and their neighbors, as in legacy OSPF.

  - Provides a flexible choice of which neighbors to include in LSAs,
    from a minimum set of neighbors adjacent to DRs and Backup DRs,
    to the full network topology.

Regards,
Richard