Subject: [manet] Discussion on draft

From: Philip Levis <[email-masked]>
Date: Thu, 27 Mar 2008 20:43:12 -0700

I'd like to start a discussion on draft-levis-roll-overview-protocols.  
In particular, Section 5.8 has a table of several existing protocols  
and their properties. This table is really going to be critical in  
ROLL's assessment of existing technologies and protocols, so we want  
to make sure that

1) It has the relevant data points to compare (protocols/rows)
2) It distills what the important properties are(columns)
3) It accurately captures the properties of the values in question  
(cells are accurate)

Let's start with 1), as it's probably the simplest. Are there any  
protocols that we should be including that aren't there? Trying to  
cover every single minor protocol tweak is a recipe for disaster, but  
protocols that differ significantly from those currently there, either  
in mechanism or in properties, are important to include.

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

---

From: "Mischa Dohler" <[email-masked]>
Date: Mon, 31 Mar 2008 12:14:56 +0200

Dear Phil, dear all,

Sorry to start a new thread but my email does not quite fit into recent
discussions.

I and my colleagues at France Telecom support Phil's initiative of
identifying the right set of protocols. However, personally, I am not quite
sure why only link-state and distance-vector based protocols are listed. 

WSNs not only offer but also require different approaches - this had also
been stated in recent discussions and we would like some canonical versions
of these protocols to feature in the overview draft. 

My colleague Thomas Watteyne (cc'ed) has summarized some approaches based on
"virtual/relative/approximate coordinates" (many terms for the same idea) as
follows:
- First, there is a set of propositions which infer the nodes "approximate
coordinates" from a set of location aware anchor nodes. (Greedy) geographic
routing protocols can then run on top of these coordinates, although the
delivery ratio is rather low.
- "Relative coordinates" can be inferred from a set of location-unaware
anchor nodes. Coordinates are in fact a vector of distances (e.g. in hops)
to these anchors. Protocols such as Vcap (infocom'06) and Gspring (ICNP'07)
function this way. The good news is that delivery ratios on those relative
coordinates are higher than if the same nodes knew their real coordinates
(!). Drawback is that they need some sort of initialization, identification
of the anchor nodes. Also, coordinate refreshing procedures seem not to be
published.
- Recently, the use of completely virtual coordinates has been proposed.
These coordinates are randomly initialized when a node is booted. Whenever a
node sends a message, it updates its virtual coordinate as a function of its
neighbors' ones. A near-greedy geographic routing protocol is then used on
top of these coordinates. Simulation results show that the network converges
to a state where path length in number of hops exceeds the optimal one by a
few percent. 

Whilst these approaches may not be of use for industrial or home automation,
we are pretty sure that they are vital for urban applications as network
lifetimes are significantly increased.

Regards,
Mischa.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Philip Levis
Sent: Friday, March 28, 2008 4:43 AM
To: [email-masked]; manet manet
Subject: [Roll] Discussion on draft

Phil
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Philip Levis <[email-masked]>
Date: Mon, 31 Mar 2008 09:36:12 -0700

> sure why only link-state and distance-vector based protocols are  

Because they are existing IETF protocols with RFCs.

> of these protocols to feature in the overview draft.

The purpose of this draft is to survey IETF protocols, so that we can  
then judge how best to move forward towards defining a protocol for  
WSNs. Its purpose is expressly *not* to survey research, other  
standards body, and custom protocols. That would be part of a next  
step, if the WG reaches consensus that existing solutions are  
insufficient.

> of the anchor nodes. Also, coordinate refreshing procedures seem not  

All of these results are from high-level simulators which use a unit- 
disk model for radio connectivity. Their claims therefore need to be  
taken with a grain of salt. Among other things, they do not consider  
any kind of temporal dynamics.

There is a long literature of coordinate embedding approaches for  
wireless as well as wired networks. Just in the past few years, before  
the two you cite above, there is GEM (SenSys '03), Vivaldi (SIGCOMM  
'04), and BVR (NSDI '05). When it comes to scalable routing  
approaches, the state of the art in research today is S4 (NSDI '07),  
which uses compact routing techniques to ensure O(sqrt(n)) routing  
state with a maximum routing stretch of 3 and, in simulation and  
simple testbed experiments, an observed average routing stretch of  
1.1. Recent work on compact routing has shown there is a fundamental  
tradeoff between routing state and stretch; while geometric or  
coordinate approaches enable nodes to have O(1) routing state, their  
stretch is unbounded.

Phil

---

From: "Mischa Dohler" <[email-masked]>
Date: Tue, 1 Apr 2008 10:52:39 +0200

Phil: "Its purpose is expressly *not* to survey research, other  
standards body, and custom protocols."

Mischa: Ok, we will kick in later then.

(Phil: "All of these results are from high-level simulators which use a
unit-disk model for radio connectivity. Their claims therefore need to be  
taken with a grain of salt. Among other things, they do not consider  
any kind of temporal dynamics."

Mischa: We are very aware of this and our approaches do not consider unit
disk and also cater for high network dynamicity - and - they work very well.

Phil: "Recent work on compact routing has shown there is a fundamental  
tradeoff between routing state and stretch; while geometric or  
coordinate approaches enable nodes to have O(1) routing state, their  
stretch is unbounded."

Mischa: Ok, thanks for pointing this out.)

-----Original Message-----
From: Philip Levis [mailto:[email-masked]] 
Sent: Monday, March 31, 2008 6:36 PM
To: [email-masked]
Cc: [email-masked]; 'manet manet'; [email-masked]
Subject: Re: [Roll] Discussion on draft

Phil