[net2-wg] Meeting notes, 12/22/05

[Philip Levis]

Participants: Om, Jonathan, Henri, Kyle, Phil.
Date: 12/22/05
Agenda: Dissemination, Collection, Development plan


Phil: Let's start with dissemination.

Om: TinyDB and Task and Surge all have dissemination. It would be nice if they
could build dissemination on top of these mechanisms. If you think of a query
as a key, then you need to be able to generate dynamic keys. Phil said that 
you could do this, but I'd like to hear how.

Kyle: My concerns were about simplicity of interfaces and RAM consumption,
which Phil addresses. The second concern was whether there would be
separate intefaces for disseminators and listeners. That could make life 
a bit earlier. I was a bit concerned about how version numbers could be
handled and using AM address to break ties.

Phil: Jonathan, can you talk about that?

Jonathan: The original proposal was based on the idea that you need
consistency across the network. So you need a unique identifier, to
eventually reach consisitency.

Kyle: So two nodes are disseminating.

Jonathan: Yes. Two nodes are dissemnating, and you might need a way
to figure out inconsistencies.

Kyle: So it's a "user may have made a mistake, let's protect them" issue.

Jonathan: Yes. You can generate stuff out of band, when you have
multiple base stations. E.g., if you want to speed propagation. So what
you do is generate the full identifier mechanism out of band, and then
place it on the base nodes for injection. 

Phil: The issue is when two nodes both decide they want to propagate
a new version. Most systems these days require that you generate new
values out of band, but that seems like a limitation that could be 
problematic in the long-term. But nodes generating version numbers
can result in conflicts: node A generates X.5 and node B generates X.5,
but the values are different. So you need to resolve the conflict through
AM id: they'll eventually become consistent.

Henri: It's not a problem when there are two base stations that want to 
disseminate two different keys?

Phil: No, shouldn't be.

Kyle: One approach is to concate the node ID onto the key itself... but that
would preclude dissemination from multiple base stations.
E.g., x.3, x.4.

Phil: The out of band can handle that.

Om: So we don't say anything about how this is done out of band? How do we 
specify this interaction.

Kyle: Well, I agree the 2-to-1 doesn't buy a lot of simplicity is pretty
straight forward. But there's the tradeoff between RAM cost and code
simplicity. 

Phil: We definitely need to do this. Kyle, do you want to talk about the
interface?

Om: We're hitting code space much more than RAM on TMotes these days.

Phil: Berkeley has had the same problem.

Jonthan: There are rumors that TI is going to put out a chip that solves
the code size problem. Something like 8K RAM, 128K ROM. Just assuming that
we push the boundary isn't that good, from a deployment standpoint.

Phil: Joe Polastre has said that more code space is definitely on the
horizon, but RAM isn't. Telos motes are something like 40% of the F1611
parts, so no pressure on TI to build bigger RAM units. But more code
space is needed, and cheap, so that should be showing up soon.

Kyle: Right. So how long should TinyOS 2 last? Does anybody have a sense
of the energy cost of RAM with comparison to other parts of the system?

Jonathan: RAM is a big deal. 

Phil: 128K for 5 years is 1/2 a AA, if you believe a press release from
2002 on a brand new technology. So we're not going to see lots of MB,
but more RAM might be possible in the future, if the pressure is there.

Om: How do you do TinyDB/TASK/Surge?

Jonathan: The way that Drip works is you query the network (or a node) to say
"give me the tuple that describes this query," or whatever Drip's data item is.
You increment and spit out the version number. You could assign an address
to the originator of the query. I think this is a better approach than
keeping it off-network.

Om: So if I want multiple queries, then I have multiple query IDs?

Jonathan: So Gil has talked about 2 options. 1) Every query has its own
data structure, pre-allocated. 2) Less reliable: keeps a cache.

Phil: So you support a static number of queries.

Om: So you can say, I want at most 5 queries, then define 5 disseminators,
and allocate for those 5. This is similar to the message pool situation. 
Even if you have five pools, you're not limited to five nodes as your
destinations. So if you have five static structures, then you can re-use
that disseminator.

Phil: TinyDB vs Mate, dynamic versus static. The dynamic approach
allows better usage of resources (less wasted RAM), but requires a user
in the loop, as a query might just not work.

Om: So hopefully we'll use this interface, that will help people build
applications. So a sample Surge built on top of this. 

Phil: So what do you people think the right next step is?

Jonathan: I would say go and write it.

Om: I'm OK with that.

Kyle: One loose end: the interface between external.  

Phil: In paralllel, or serially? Do you want to toss out a proposal?

Kyle: I don't think it will take long, but let's do it offline.

Phil: OK, we can then reach consensus on the mailing list.

Om: What about SP?

Phil: The feeling in the T2 WG is that it's too early for SP. Pushing
for a 2.0 release is too fast. It's a big deal, and deserves a lot of
throught and effort.

Om: So we won't use SP at the time... but let's ask about collection.
Collection is based on the SP implementation? 

Jonathanan: I haven't looked at the code in 7-8 months. We slammed the 
code together in 14 days with almost zero comments. So there wasn't a whole
lot of premeditated thinking going on, we just went and did it. It's 
pretty unreadable code. We could do a much better design.

Om: Will this form the basis of the next implementation?

Jonathan: Throw the code away: clean slate.

Henri: SP will shoot for a more leisurely pace. Will this working group
be involved?

Phil: Yes. I think it might be a cross-WG collaboration, as it matters
to both the T2 WG and the net2WG. It is clear that this WG has to be
involved.

Phil: Do we want to move forward to collection?

Om: Yes. So you have a routing header and a forwarding header. But can 
you have any further interaction? We need to resolve that. Also,
in MintRoute, when forwarder calls SelectRoute, it not only fetches
the parent, but also resets some routing state. Will this interaction
be possible. Was there any consensus on a richer interaction between
forwarding and routing. 

Kyle: There hasn't been any further discussion since last week. My
sense is that whatever interaction is needed, we could add. We could
always add further functionality.

Phil: The one issue there is the coupling between routing and
forwarding engines. The interfaces need to allow composition.

Om: When you call select route, if the message is looping, you reset
some of the routing state. So if you detect a loop, it changes the 
routing state.

Kyle: That's pretty fundaemental to distance-vector.

Om: That kind of stuff would be difficult to do. If we don't allow 
forwarding state to trigger state change in the forwarding module,
that might make things like this difficult.

Phil: But what about the upper interfaces? That seemed like the
point that was unresolved from last time.

Om: We've said that interface that apps will use look pretty good,
mostly like what's there now.

Kyle: No surprises there. Something similar to send.

Phil: Intercept?

Kyle: Yes. At the routing layer, for applications to use.

Phil: Om, can you send out a collection signature? Even if it's simple,
it will give people something solid to look at and work against, etc.

Om: Sure.

Henri: Neighbor tables, etc. What is the goal here? An initial SP-like
interface?

Om: I'm sure it's necessary to make it very general.

Kyle: I'm thinking we want to be friendly to quality-aware routing
algorithms.

Om: Sure, but do we want multiple protocols to be able to use the same
table?

Kyle: RAM means we want to share this state.

Phil: Do you want information from the link layer?

Kyle: Sure, not link-independent, but many indicators from the radio.

Om: Do we need to plan for a situation where there might be multiple
receivers of this information? 

Kyle: I suspect yes.

Om: So we need to design it in a way to share such information. Multiiple
producers as well.

Phil: Building a completely general neighbor table that allows protocols
to specify policies and algorithms
can be really hard. Berkeley has been working a  while on this. There are
lots of considerations. Another approach is to say that the table has
a specific entry membership/policy algorithm, and that protocols can
use it if they want. Encapsulate the algorithm, provide an ADT abstraction.

Kyle: Incorporating some sort of hints could be good.

Phil: Yes, could also make things much harder. I just think it's OK to
build something solid but not completely general, so people can get
collection going.

Phil: What's the best way to proceed with putting together implementations.
I am going to work on dissemination.

Kyle: I'm happy to start hacking. It will start us thinking.

Om: I might need a little bit of help in the beginning. Jonathan can
contact me offline.

Phil: Henri can start working on send pool, that will guide later discussion.

Henri: I'm on the same page there. Sounds like a good idea.

Phil: Meet next on the 5th? 29th is a holiday!

























 
-------------- next part --------------

Phil


-------

"We shall not cease from exploration
And the end of all our exploring
Will be to arrive where we started
And know the place for the first time."

- T. S. Eliot,  'Little Gidding'