Subject: Re: About TBRPF

From: Richard <[email-masked]>
Date: Sun, 10 Sep 2000 16:32:59 -0700

Amir,

Here is the rest of my reply to your questions.

For the sake of others who might not be familiar with how TBRPF 
does reliable link-level transmission of update messages, I will 
give a brief overview.  An update message can be sent in UNICAST 
mode to a single neighbor, or in BROADCAST mode to all neighbors.
If there is only one intended recipient (i.e., child) for a particular 
update message, then it might be better to send it in UNICAST mode.  
The mode can be different for different update sources, since there 
is a different set of children for each source.  Also, the mode for 
a given update source can change dynamically between UNICAST and 
BROADCAST if the number of children for the source changes.  
TBRPF achieves reliable unicast using ACKs (unless this is already 
provided by the link layer) and reliable broadcast using NACKs.  

UNICAST mode may be useful even in single-channel networks 
(without receiver-directed codes/frequencies) because reliable 
unicast is usually cheaper than reliable broadcast.  It is also 
possible to simply use BROADCAST mode for all updates.  (We have 
not yet conducted experiments to determine whether it is better 
to switch between the two modes in single-channel networks.)

The link sequence numbers (LSEQ) of messages sent in UNICAST mode 
are independent of those sent in BROADCAST mode, which is why a node 
waits for all unicast messages for a particular source to be ACKed 
before switching to BROADCAST mode for that source (so that the 
children can process the messages in the correct order).  (If a link 
to a child goes down, then of course the node stops waiting for ACKs.)

We did not think that waiting for ACKs would be a problem, since 
there is only a single child in UNICAST mode, and the mode should not
change very frequently.  Even if it does, this can be dampened by 
waiting for some time after the number of children decreases to 
one before switching to UNICAST mode.  Also, if it is determined
that it is better to use UNICAST mode when there is only one child, 
then the cost of using UNICAST mode for two children while waiting 
for ACKs should should be small.

However, to answer your question, TBRPF can be modified to avoid 
waiting for all unicast update messages (for a given source) to be 
ACKed before switching to BROADCAST mode.  This can be done by 
retransmitting the unACKed unicast messages in BROADCAST mode.  
Some details need to be worked out to make sure the children can
reorder messages that are received out of order, but it can be done, 
and we will consider it for the next version of TBRPF.

You are correct that the current version of TBRPF was designed to
take advantage of unicast (receiver-directed) channels, if they
are available in addition to the common broadcast channel.
We are currently working on modifications to TBRPF to improve its 
efficiency when there is a single channel.  These modifications 
might include sending NACKs and retransmitted update messages in 
BROADCAST mode, and combining Heartbeat messages with HELLO messages.

Richard

> Amir,
> 
> You ask some interesting questions, and I would like to think 
> about them before sending a full response (soon).  For now, 
> I will answer the easier ones:
> 
> Our implementation uses a single-channel 802.11 interface (WaveLAN).
> The UNICAST mode in such a network is still useful when there is
> only one intended recipient, since it is easier/cheaper to do reliable 
> unicast than reliable broadcast.
> 
> Regarding the simulation results (which are from my MOMUC'99 paper)
> we used both the unicast model (where a separate copy of each
> packet is sent to each neighbor) and the broadcast model (where a 
> single copy is sent to all neighbors).  The 85% reduction in overhead 
> compared to flooding is for the unicast model.  For the broadcast model 
> the reduction was 60%.  We assumed that a link is reliable when it is up, 
> so we don't have results for unreliable links.
> (TBRPF uses NACKs to achieve reliable link-level broadcast.)
> 
> I want to think more about your questions regarding switching between
> BROADCAST and UNICAST modes.  One thing I can say now:
> When a node switches from BROADCAST mode to UNICAST mode for a particular 
> source, it is likely that there is only one child for that source, 
> and only that child must be sent the END_OF_BROADCAST message.
> 
> Richard
> 
> 
> > Hi Richard,
> > 
> > I have the impression that TBRPF is tuned keeping in view the dual
> > channel availability (unicast+broadcast), although it works also for a
> > single, multiple access channel. Does your implementation use
> > dual-channel radio interfaces ?
> > 
> > Does the single shared channel assumption impacts the protocol ?
> > While using a single, shared channel, is it possible to avoid overhead
> > of sending END_OF_BROADCAST message to EACH child individually
> > (section 5.2.2) while switching from BROADCAST to UNICAST mode, for
> > the next packet ?  Similarly, before switching from UNICAST to
> > BROADCAST mode, is it necessary to wait for acknowledgments of all the
> > unicast packets sent (section 5.2.2) ?
> > 
> > Moreover, while comparing TBRPF with an efficient version of flooding
> > (section 1, paragraph 5) do you use the model of sending a separate
> > copy of a packet to each neighbor, for broadcasts (unicast flooding) ?
> > (where you obtained the performance gain of 85%). How the reliability
> > of the channel impacts TBRPF ? (Generally, unicast packets are sent
> > reliably, but not the broadcast packets).
> > 
> > Amir