[SensorNetArch] Two idea for today

[David Culler]

The degree of flexibility in this naming scheme is the size of each 
sibling field >= ceiling(number of children).  For any subtree, the root 
of the subtree can take on children as long as the number doesn't exceed 
the field size that the root of that subtree established.  If that bound 
is exceeded, the entire subtree must be renamed.

Subtree renaming is always possible without affecting the rest of the tree.

A parent change causes the entire subtree to be renamed.

Gilman Tolle wrote:

> So, you've built this trivial network. C's name is then 011001. How,
> then, will this name remain valid when the network becomes
> 
> D -> B -> C
> 10   10    01
> 
> C's routable name is now 101001, and any messages sent to 011001 will
> be delivered to the wrong node.
> 
> I'm definitely interested in finding a way around this...I just don't
> see it right now.
> 
> Perhaps nodes could "cover for each other", by maintaining some state
> about each others' previous child numbers. Or, parents could maintain
> some "historical" references, to delay the need for renumbering until
> it is absolutely necessary.
> 
> But, if the messages to be routed are infrequent enough, adaptivity is
> not really necessary. A rough tree could be built quickly, and then
> used to route messages, and then a new tree could be built again
> later.
> 
> Gil
> 
> On Mon, 07 Mar 2005 17:10:16 -0800, Philip Levis <pal at eecs.berkeley.edu> wrote:
> 
>>On Mar 7, 2005, at 4:17 PM, Gilman Tolle wrote:
>>
>>
>>>Because this is such a popular idea (I've worked on it also), the
>>>question then becomes "why aren't we using it?".
>>>
>>>Establishing the names is easy -- just build a tree and set up the
>>>numbering. Adaptation is hard. Responding to the fact that changing a
>>>parent requires renaming all descendants, and changing the number of
>>>bits used to represent children requires renaming all children's
>>>descendents.
>>>
>>
>>While adaptation can cause a node's name to change, it might not need
>>to be aware of this, as its name is in relation to another. E.g.,
>>imagine this trivial network:
>>
>>  A -> B -> C
>>01   10   01
>>
>>Where A has root name 01, B has child name 10 and C has child name 01.
>>
>>All C needs to know is that it is a child of B and its name is 01. If B
>>changes its parent (say, to D), then C does not need to know this. When
>>does C need to know its network-wide name? All routing/naming decisions
>>are resolved locally... generating a node's fully name is just storing
>>the route taken up the tree.
>>
>>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'
>>
>>
> 
> _______________________________________________
> SensorNetArch mailing list
> SensorNetArch at Millennium.Berkeley.EDU
> http://Mail.Millennium.Berkeley.EDU/mailman/listinfo/sensornetarch