[net2-wg] 5/18 notes

Thu May 18 10:02:02 PDT 2006

(Inline as well as an attachment)

Attendance: Arsalan, Henri, Om, Rodrigo, Sukun, Joe, Geoff Mainland

Rodrigo: Let's start with the status of collection. Om and I have been
testing tree formation with link estimation on TOSSIM with some
topologies. We found a few bugs, but it's getting much better. I've
built a tree that has a nice degree distribution. Next step is to
check that the trees are being built OK. I've also tested building a
forest.

Om: Using the latest estimator?

Rodrigo: Yes. But I haven't looked at the actual quality of the
topologies. Next step is the forwarding part. Since this is basically
MintRoute, it's possible to form longer loops. I don't think the
forwarding engine takes that into account right now.

Phil: It doesn't.

Rodrigo: One approach is getNextHops(), to get a list of possible
nodes, in order of preference. You could keep track of recent packets,
and could blacklist based on loops.

<interjection to get member list>

Rodrigo: Martin Turon is now a member.

Rodrigo, OK, so, the tree formation will currently allow some loops,
and we were talking about how to cope with that in the forwarding
engine.

Phil: DMYSO has a way of doing this?

Om: Pro-actively finding a loop and breaking it?

Rodrigo: Approach is taken by DSDV. You put a sequence number that the
root increments. Basically a node keeps track of the last number it
saw and forward it. Only updates distance on a new sequence number.
The way that avoids loops is that a packet forwarded by you has that
sequence number. This will avoid loops.

Om: And we don't do that?

Rodrigo: No, I was just porting MintRoute. For this to work, each root
has to have its own counter, and you have to carry both the root ID and
the sequence number.

Phil: So this would break the anycast.

Om: Doesn't MintRoute have sequence numbers?

Rodrigo: Yes, but every node has them and it's for link estimation. The
tree sequence numbers are only from roots.

Om: We're not doing this because of state concerns? It seems like not
having loops is a desirable property.

Rodrigo: I think we're not doing this because we want to get something
out the door. But this does mean that the forwarding engine has to
be able to get multiple next hops.

Joe: I recommend putting the header field in now, if you think you'll
need
it. Changing packet formats later is always annoying to users: you have
to regenerate MIGs, database setups, etc.

Phil: What would the cost be?

Rodrigo: Two bytes, one for root ID, one for sequence number. But this
would only be in control messages. Joe, you mentioned that Boomerang
keeps 3 parents around. How do you select them?

Joe: It's configurable. It uses Phil's interfaces from 1.x, with some
modifications from Jason Hill, where you can specify the transmission
number -- this is the 12th time I'm transmitting the message. You then
get the recommended destination address.

Rodrigo: Which do we prefer, get multiple next hops, or what Joe
talked about?

Om: It sounds like one is a forwarding policy, while another is a parent
selection policy?

Phil: What's the difference between forwarding policy and parent
selection policy?

Rodrigo: The getNextHops is supposed to capture this. If you want to
completely decouple the policy, the interface becomes more complex.

Phil: route selection

Om: Forwarding engine just knows how many times it has failed.

Phil: But that relates to link quality.

Rodrigo: If the forwarding engine tries to forward and fails, that's
very valuable. It should be communicated to the link estimator, which
would eventually trickle up to the routing engine.

Om: As is, this wouldn't work, as the link estimator only uses
information from packets sent through it. This sounds like what Phil
was recommending a long time ago.

Rodrigo: But let's get back to loops. Loop information is in the
forwarding engine. Keep a hash, an identifier, etc. Maybe we should
skip this mess and just go with the loop-free things.

Om: Joe, you had said that loops aren't necessarily bad.

Joe: We do sequence numbers on every node.

Rodrigo: It's not that you ever ruled it out; you don't have anything
against root-based sequence numbers.

Joe: Correct.

Om: What about the spatial diversity argument?

Joe: I still think there's something valuable in detecting a loop, in
that you can select other neighbors that are different in time or
space.  A loop gives you absolute knowledge. It may be that it broke
somewhere in the middle, and if you send it differently next time, it
will work. We use a TTL field based on transmissions.

Rodrigo: What do you do when it expires?

Joe: We make a note of it, and expect the PC to request it later.

Phil: Cache, or non-volatile?

Joe: Right now, we just cache it. Eventually we will do it
non-volatile on the source node.

Om: But this is all data messages; we were talking about control
messages.

Joe: We do use synchronization.

Om: What synchronization?

Joe: It's in Boomerang. tos/lib/netsynch.

Rodrigo: Just to conclude this part. The first thing is that the tree
can have loops, or be loop-free. In the former, you need alternative
hops.

Om: You need alternative hops in either case, in case a link went
down.

Rodrigo: Right. So in either case you need to get alternative hops.

Om: But the list of parents may have changed. So you might ask for
an alternate parent and get the same one!

Phil: How about you can tell the link estimator, "Please don't give me
this address!" There are questions of how long this lasts.

Rodrigo: I'm tempted to leave this to the forwarding engine.

Phil: It just seems like the forwarding engine is making routing
decisions.

Om: If the forwarding engine has multiple choices, it's making a
routing decision.

Rodrigo: Let's move on. We're in general agreement that we need a
mechanism to choose an alternate route. The question is where this
boundary lies.

Om: Phil's observation is true: the forwarding engine is playing a
role in route selection.

Rodrigo: The other thing that popped up this week was neighbor-table
management. We decided to go with an SP-like approach, where you get
a signal that there's an eviction, and you can respond.

Om: But insertion isn't there. We'll put new links in probation.  If
it's a good link, then we'll get estimates and it can stay in the
table.

Rodrigo: With this interface, we can move on to the link service
manager, the outside module that prevents churn.

Om: Would we need that for the beta release?

Rodrigo: Since we only have one client, we can test it like that. Does
that sound like a reasonable approach from the SP people? Are we
re-inventing SP?

Joe: As long as you acknowledge that you're borrowing from it, fine
by me.

Om: I think that these discussions are validating some of the
decisions made in SP.

Joe: It will also make it easier to switch over to an SP
implementation in the future.

Om: So I think the decision is that we'll have insert() in the
manager.

Rodrigo: Do we have any news on testing dissemination?

Henri: I'm waiting on information of when to do this.

Sukun: I've done a few tests, it seems to work, I need to run a larger
scale test.

Henri: What about collection? Would early next week be a good time to
do this?

Rodrigo: Yes.

Henri: I'll find a day.

Rodrigo: What about a simple collection application? We have
apps/tests/TestTreeRouting. It just builds a tree, doesn't interact
with the world or anything. The next step is to integrate the
forwarding engine.

Phil: I'll communicate with Kyle and we'll put something together.

Om: I think all of the functionality is there. It will just be testing
now.

Phil: Let's not underestimate how long that will take! The T2 group is
very excited about dissemination and collection being ready for the
beta.

Rodrigo: Do we think that there will be any problems with putting
dissemination and collection together?

Phil: I was planning the collection app to have a simple dissemination
value, the packet send rate. So you can turn a knob. I think that AM's
fair queueing should make it work OK.  It might actually be very hard
to cause the network to saturate, as the forwarding engine has backoff
built in. If a packet isn't ACKed, it waits some time (100ms or so)
before sending again.

Om: why not do this at a lower layer?

Phil: What if you are sending to a different node? Then you might not
want to back off. Instituting a uniform policy is problematic. The
forwarding engine has additional information.

Rodrigo: OK, let's test the parts separately, and integrate over the
weekend.

-------------- next part --------------
Arsalan, Henri, Om, Rodrigo, Sukun, Joe, Geoff Mainland