Net2WG/Notes/20060420

Present: Kyle, Phil, Rodrigo, Joe, Arsalan, Henri, Om Transcript: Kyle

Rodrigo (R): we're working on collection

Phil (P): concur

Rodrigo: let's talk about structure. Idea: main interface is wiring to CollectionC. CollectionC provides Send, Receive, Snoop, Intercept (all address-free), RootControl (sets this node as root, check whether root or not). All these calls are the data path. No multiple tree ids. Maybe multiple roots.

R: ForwardingEngine provides the data path interfaces. Maps address-free send to the data send. ForwardingEngineP provides all this data-path functionality. Buffers msgs for forwarding. Does rexmits, queueing. Can be split later.

R: Interacts with tree through routing interface. Routing interface gives you next hop for pkt. TreeRouting builds tree by exchanging ctl msgs with other nodes (periodic). Needs link estimation.

R: Link estimation: all msgs go thru link estimator module. Provides am send/recv pkt interfaces, adds sequence number to infer drops. Will port MintRoute over to this structure.

Om: this is same as one we discussed 2-3 wks ago?

R: yes, just checked in code

P: looking at interfaces; detail-oriented qs. LinkEstimator has three calls. Why separate forward/reverse?

R: details will be changed by O. Quality will be bi-directional.

P: some function f takes forward, rev lq and turns it into bi-dir lq. what's f?

R: multiply them.

P: why multiply?

R:

P: mapping dependant on underlying structure

R: maybe different if you have link-level retxmits. O?

O: concur

P: why is neighbor a 16-bit index; > 256 nbrs?

R: no, left-over from address.

P: if you refer to nbr with index, how to know what are the set of valid indices?

R: has to be a mapping; will have to think it thru.

R: why need to scan it?

Joe: will integrating with SP help?

P: SP has this data structure with iterator. Would be good if these interfaces could be put on top of SP.

R: forwarding engine never needs to iterate.

P: when next hop is put into packet... where is that?

R: forwarding engine does it. Queries next hop through BasicRouting interface. Puts next hop into packet.

P: i see.

R: from point of view of forwarding engine, it knows about AM addresses.

P: makes sense. so assumption is that routing engine is combining the link estimates and route estimates with tree formation and tree position.

R: yes

P: so then routing engine is built on top of a separate link estimator.

R: yes, other components could use the same link estimator.

P: so how does routing engine map link ids to link address to figure out route metric? where is the point?

R: has to be in a nbr table maintained by the routing engine itself.

P: but it's talking to link estimator in terms of abstract ids. how can routing table maintain mapping:

Joe: Phil's brining up q of what is addressing scheme beyond one hop. How to infer cycles occurred?

R: SP provides mapping.

Joe: SP wouldn't. Only concerned w/link, not addressing scheme. Put address info re where msg has been. I can see us getting into service discovery issues. The network addressing issue is being skirted.

R: don't have SP. Must be fleshed out. Network layer puts src network id in the msg s.t. when other side receives it, it can maintain the mapping.

P: but there's still this... point is that... don't understand how to figure out for a given abstract link tbl id, what's the addr associated with that. Need to know that. There's no way...

R: have to think that through. that's the short answer.

Joe: same Q as Phil. also; how to know it's unique.

R: can assign UIDs to all nodes.

P: if you take as a premise that nodes have UIDs... not assigned.

R: right, not assigned, already existing.

R: have to think it through and post it; good Qs. idea going forward is to port as much of MintRoute into this structure and get it running ASAP.

P: some of these issues will become apparent when you start to impl. not that much code. rather than trying to port MintRoute code,...

R: meant porting the algorithm. because we can spin on what is the best way to form tree...

P: as long as different parts work together, OK if you optimize subcomponents.

R: initial step was to separate...

P: have components. Division of labor? I'm happy to do forwarding engine part. Queues and all that stuff.

O: link estimation

Kyle: work with Phil on forwarding engine?

P: sounds good; fluffiest part is relationship between link estimation and nbr tbl, that might be another spot to dig in.

R: because O is doing link estimator, how do interception of packets feed link estimator, regardless of AM type. Idea is that link estimator provides AM receiver and AM sender just like lower stack already does. So if you wire through link est, your packets will contribute to link estimation. So you can choose to wire thru link est, or directly.

P: thru is tricky term. Have two AM senders which look identical. But if you use it, then packets sent through this interface will contribute to estimation.

R: at least ctrl packets have to go through that. Packet interface will return different values because link estimator...

J: will be really tricky in terms of who is using it... As soon as you duty cycle network, end up losing estimate which you didn't realize you were losing before.

P: how could duty cycling change the estimates?

J: imagine if you had a path along which bulk data is sent. Only nodes essential to path are awake, others sleep. Miss seqnos. False positive losses.

P: yes, if turn off nodes and link estimator is unaware.

J: two approaches: first manage when everyone else is off, other is... (crosstalk)

R: who's "you?"

J: any node

R: which module is managing it?

J: it's a network service that wants to send. Have to make a decision at design time whether to send thru link est module. As long as share info with link of SP, will know when other nodes are awake. Then won't be issue. Alternative approach is only to do it with broadcast addrs. Guaranteed if broadcast then everyone will hear it.

(crosstalk)

P: if you're using seqnos and your pkts are unicast, then unless you have per-dest seqnos, then you'll think bad things, duty-cycling or not.

J: right; need additional set of states

R: simplest approach is bdcast.

J: I'm just providing alternatives, you guys can decide which one you like best.

O: I think broadcast-based estimation is the best idea so far.

J: works as long as you have control traffic, but as soon as you go to an (inaudible) type system, it fails.

R: good point to take into account duty cyclying. Even assumption that can snoop.

O: same problem in my work many years ago with directed diffusion.

R: even in 15.4 code...

J: 2.x tree doesn't do that. can snoop. but i still think it's worthwhile because there are other radios where you can't snoop.

P: R will do routing engine, O doing link est, P & Kyle do forwarding engine.

R: reimpl queued send?

P: yes, has most versions, bugs. really scary to look at logs. might look at Geoff Mainland's code (queues and msg pools for 1.2)

J: Cory wrote @ Berkeley, circular queue lib in C. since not generic, end up sharing program space. implements circular queue.

P: where is it?

J: in system/C dir, in moteiv tos/lib dir.

P: i've had similar lib for TOSSIM.

Kyle: preprocessor-based macros?

J: no, .h file.

P: the one I wrote uses some. can embed structure into lib. avoid having to allocate link entries separately from data structure itself.

O: are we talking about queuued send maintaing contents of pkt rather than pointer?

P: huh?

P: no, forwarding engine has pool, but send queues are just ptrs.

J: we have generic objects pool as well. in 1.2.

P: Geoff has something similar, but we can take a look. may be benefits, drawbacks.

R: pool, can't remove elts?

J: just a pool, we found that needed commands and also events to say when something changed. may be overkill.

R: just need a fifo i think

J: that's for the msg, well maybe , it's possible. a circular fifo queue would work.

P, R: so...

R: so maybe it's not worth doing the mapping if we'll move to a more sophisticated link layer later.

P: will be clear when we start coding.

P: lots of issues. on list or private?

J: so few people can send to list.

O: list is fine.

Henri: would be interested.

O: timeline?

R: will continue work today

(logistics discussion)