Subject: questions on routing in bluetooth

From: [email-masked]
Date: Sat, 1 Apr 2000 12:51:27 +0530

Hi All:

 I was just following the mails over the last few days on routing
 in adhoc networks. Can somebody pour some light on what can be the
 major issues for routing in Bluetooth kind of adhoc network, where
 nodes are charaterized by low or zero mobility? Is it worthwhile
 to talk about the same issues of rothing in adhoc networks,
 when we talk about routing in Scatternet formed by multiple
 Piconets? The AODV or some proactive kind of protocols, if used,
 may have to be tweaked appropriately because of the Master slave
 Pico-cellular architecture. So, can a Clusterhead routing kind of
 thing work well here or there may be drawbacks when applied to BT?

thanks,
supratim/ibm irl

*********************************************************************
SUPRATIM DEB
Phone:+91-11-6861100 (Extn:146)
E-mail: [email-masked]

Office:
IBM India Research Lab
Block 1, IIT Delhi, Hauz Khas , New Delhi- 110 016
28 deg 54 min North,  77 deg 13 min East

---

From: Charlie Perkins <[email-masked]>
Date: Sun, 16 Apr 2000 07:41:57 -0700

Hello,

Sorry for the long delay in answering.

My understanding is that, first, Bluetooth nodes need to set
up a master/slave interconnection between first-hop neighbors.
After that time, I believe that AODV (and, for that matter,
other manet protocols) are applicable to Bluetooth for managing
multi-hop routes through scatternets.

The more interesting question surrounds the way in which
service discovery might be handled.  A few months ago,
I proposed and then rather quickly retracted a way to adjoin
service request details as part of AODV's path discovery
algorithm.  The idea was that a node might wish to find a
route to a particular service instead of a particular IP address.
I retracted the proposal because everyone seemed to hate it,
since it represented a kind of layer violation.

Maybe this idea should be reconsidered.  If so, I am willing
to make a separate Internet Draft containing the details about
Service Request/Reply under AODV.  An alternative would
be to adapt Service Location Protocol for manet; I do not
think there is very much that needs to be done for that to work.

Regards,
Charlie P.

---

From: campbell <[email-masked]>
Date: Sun, 16 Apr 2000 12:51:22 -0400

Hi Charlie:

I think there is a danger in the line of thought that
MANET is a pure 'routing vehicle' and all value added gets
piggybacked or integrated in the protocols. 

There is a separation of concerns here. Your alternative
proposal (below) recognizes that.

Best,
Andrew

---

From: [email-masked]
Date: Mon, 17 Apr 2000 18:38:30 +0200

We have detected that AODV may enter into a permanent deadlock if a
permanent assymmetric link exists. This case may occur since power control
may lead to large discrepancies between transmission powers. 

We think that there are two ways to cope with that problem with "on demand"
protocols.

One way is to permanently check link symmetry via periodic hellos. The node
shall ignore RREQ packets when received from assymmetric nodes.

Another way is for each node to maintain a "black list" were assymmetric
neighbors are listed. A neighbor node will be detected as assymmetric if
the update packet transmission fails (this supposes that MAC layer
acknowledges unicast packets). A node is listed in black list during a
black_list_holding_time and then the information is discarded (this
information cannot be refreshed). A node shall ignore all RREQ packets
received from an assymmetric neighbor, i.e. during the time where the
neighbor node is listed in black list. 

What do you think?

Philippe

---

From: Nikos Triantafillis <[email-masked]>
Date: Mon, 17 Apr 2000 19:29:17 +0100

>may lead to large discrepancies between transmission powers. 

Personally I would be interested to know the hows and the whys of this
permanent deadlock.

>We think that there are two ways to cope with that problem with "on demand"

Is the deadlock problem only a problem with AODV? Or have you also looked at
other protocols too?

>neighbor node is listed in black list. 

I may be missing something but doesn't that mean that the network and the
nodes will be able to take advantage of bidirectional links only? If it does
mean that, do we want such constrain in an ad hoc routing protocol? Do we need
to look at on mobile ad hoc network routing with unidirectional links too
perhaps? I know this has been brought up and debated in the list before but
I'm still not convinced that it is or should be outside of the scope of this
WG.

Thanks,

Nick

PS:BTW if anyone out there has seen a formal proof or reasoning on the loop
and deadlock free properties of the ad hoc routing protocols that have been
proposed so far in the group or a performance evaluation of any of the
protocols in the presence of unidirectional links, please send me a pointer.

---

From: "Samir R. Das" <[email-masked]>
Date: Mon, 17 Apr 2000 14:43:20 -0400

> may lead to large discrepancies between transmission powers.

True, AODV will not work in presense of asymmetric links without
any modification.

> shall ignore RREQ packets when received from assymmetric nodes.

I assume that you want to mean that the neighbor will tell you
via hello whether 
it can hear you.  So the hello messages will contain the one-hop
neighbors
for it to work.  Yes, I think it will work.

> neighbor node is listed in black list.

I am not sure I follow you here.  If you are using MAC layer
acks, then you
are implicitly working with only symmetric links.  An asymmetric
link will appear
to you as no link. Why do you need to do anything additional?

> Philippe

Samir

---

From: [email-masked]
Date: Tue, 18 Apr 2000 11:57:40 +0200

Dear Nikos,

We don't think it is specific to AODV, other protocols based on route
discovery via flooding may also be concerned. About the principle of using
unidirectional link for routing, this is another story and I don't discuss
this topic. However unicast transmissions need bidirectional links on IEEE
802.11 and HIPERLAN.

Our aim is to discuss about a possible improvement of AODV in case of
permanent assymmetric links. We tried to keep the "on demand" spirit (i.e.
no periodic hellos). I don't know if we are succesful. 

About the problem, there is no global deadlock of the protocol and maybe we
are wrong. It seems that some nodes may never get access to some
destinations. For example assume that the source A has a lot of power (for
example a powered fixed station or something equivalent on a vehicle) and a
chain of low power nodes B, C, D, ...

A----B----C----D----E----F----G---H--- 
 \............>

Links between A and B, B-C, C-D, etc, are symmetric links. But nodes A has
unidirectional links to C and D (C and D hear A but are not heared by A). 

If A wants a route to F (or G, H,...) it floods a RREQ. The RREQ is
simultaneously received by B, C and D which list A as precursor. Forward
from B and C are ignored by C and D. D forwards to E and then E to F. F
returns via the reverse route which fails on the link D-A. If A repeats the
flooding again, then the failure will occur again. 

The idea of the "black list" is that when D will detect that it has an
assymmetric link with A (e.g. by receiving no ACK from IEEE 802.11 MAC
layer), D will never forward any broadcast packet directly received from A.
Doing so D will forward RREQ exclusively received from C. The problem with
the black list is that this kind of information cannot be updated and the
entries must be timed out. 

Does it make sense?

Philippe

---

From: Laura Feeney <[email-masked]>
Date: Tue, 18 Apr 2000 12:11:20 +0200

Hi, 

I think there is some confusion here about what people mean when they
say "assuming symmetric links".  A situation involving asymmetric
wireless connectivity is something that happens at the physical layer.

Using IEEE 802.11, this means that a broadcast message sent by host A
is received at host B, but a broadcast message sent by host B is not
received at host A.  Host A can't send a point-to-point message to
host B because B can't send the CTS/ACK to host A.

Even if an ad hoc routing protocol does not "use" this asymmetric
link, it exists and the protocol can get tripped up by it, especially
in on-demand route discovery.

In the case of AODV, this means that a sequence of (broadcast)
route_request messages can ``discover'' a route along which the
(point-to-point) route_reply message can't be sent because it is
dropped at the asymmetric link.  If the destination continues to
respond to route_requests which have traveled via this link, the
source will reinitiate the route discovery process in vain.

I recall having a discussion about this with David Maltz some time ago
and he suggested that DSR can avoid this problem by having the
destination reply to all route_requests.  For DSR, this has the
advantage of distributing additional topology information.  (I'm
sorry, David, I don't remember whether we talked about this in person
or online; so stomp on me if I'm misquoting you. :-)

Laura

>>>>> "Samir R. Das" <[email-masked]> writes:

Samir> [email-masked] wrote:
>>  We have detected that AODV may enter into a permanent deadlock if
>> a permanent assymmetric link exists. This case may occur since
>> power control may lead to large discrepancies between transmission
>> powers.

Samir> True, AODV will not work in presense of asymmetric links
Samir> without any modification.

>> We think that there are two ways to cope with that problem with "on
>> demand" protocols.
>> 
>> One way is to permanently check link symmetry via periodic
>> hellos. The node shall ignore RREQ packets when received from
>> assymmetric nodes.

Samir> I assume that you want to mean that the neighbor will tell you
Samir> via hello whether it can hear you.  So the hello messages will
Samir> contain the one-hop neighbors for it to work.  Yes, I think it
Samir> will work.

>> Another way is for each node to maintain a "black list" were
>> assymmetric neighbors are listed. A neighbor node will be detected
>> as assymmetric if the update packet transmission fails (this
>> supposes that MAC layer acknowledges unicast packets). A node is
>> listed in black list during a black_list_holding_time and then the
>> information is discarded (this information cannot be refreshed). A
>> node shall ignore all RREQ packets received from an assymmetric
>> neighbor, i.e. during the time where the neighbor node is listed in
>> black list.

Samir> I am not sure I follow you here.  If you are using MAC layer
Samir> acks, then you are implicitly working with only symmetric
Samir> links.  An asymmetric link will appear to you as no link. Why
Samir> do you need to do anything additional?

>> Philippe

Samir> Samir

-- 
Laura Marie Feeney				[email-masked]
Visiting Researcher				http://www.sics.se/
Computer and Network Architectures Lab	 	Tel: +46 8 633 15 09 
Swedish Institute of Computer Science		Mobile: +46 70 246 56 63     
Box 1263, SE-164 29 KISTA, SWEDEN		Fax: +46 8 751 72 30

---

From: [email-masked]
Date: Tue, 18 Apr 2000 13:48:51 +0200

Hmm, I think AODV destination also reply to all RREQ's. But I don't think
it solves the problem. In the example I give, the destination receives only
one RREQ and it is a wrong one. 

Philippe

---

From: George Aggelou <[email-masked]>
Date: Tue, 18 Apr 2000 12:27:28 +0100

Nikos 
> nodes will be able to take advantage of bidirectional links only? 

Nick,

My understanding is that "yes" and I do not fully agree with Philippe
here as this can put alot of constraints on the routing protocol and on
the MAC protocol as well.

> If it does
> perhaps? 

My opinion is "yes and no".. At first, remember that among the factors
which could make a wireless link unidirectional are interference and
differing radio capabilities. 
I believe it really depends on the depth you are willing to simulate a
MANET routing protocol. That is, along with the routing protocol does
your simulator incorporate MAC and PHY layer stuff as well? If so, I
believe that asymmetry in wireless links is a factor that should be
taken into account as it does influence the relative performance of MAC
_and_ hence of the routing protocol as well. An open issue though is
*how much* this affects the performance of a routing protocol. 
If now your simulator does not include any such stuff from MAC and PHY
layers, then I don;t see the real benefit of messing around with link
asymmetry wich is a concern caused from wireless channel conditions and
power fluctuations.

> protocols in the presence of unidirectional links, please send me a pointer.

About loop-freedom you can see the appendix of DSDV paper from Charlie
and Pravin Bhagwat at SIGCOMM 1994 (hope 'm correct for the year..:)

Regards,
George A.

-- 
*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.     
George Aggelou			     	
Centre for Communications Systems Research   
Mobile Communications Research Group      		
University of Surrey  		     

http://www.ee.surrey.ac.uk/Personal/G.Aggelou
*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.

---

From: [email-masked]
Date: Tue, 18 Apr 2000 16:33:16 +0200

>the MAC protocol as well.

I probably missed something here. I just said that AODV (DSR?) in its
present form may have problems if there is a permanent asymmetric link in
the network and there are remedies for that when detected. The question
whether AODV can take advantage of asymmetric links is another question.  

Philippe

---

From: George Aggelou <[email-masked]>
Date: Wed, 19 Apr 2000 12:43:24 +0100

> A----B----C----D----E----F----G---H---

Hallo Philippe,

A few thoughts on your comments:

a) Asymmetric link and unidirectional link are two different things. A
link between nodes A and B is asymmetric when the data rate from A to B
is different from this from B to A. Unidirectional link has to do with
the transmission powers of the two nodes. A link  between A and B is
deemed as unidirectional when A for example is within B's transmission
range while B not, due to differing transmission capabilities or
wireless channel impairments. 

b) A few words on your comment: "It seems that some nodes may never get
access to some destinations", with no intend to harm AODV..-:) 
There is an inherent concern on the way query quenching works in some of
the existing MANET protocols (including AODV and DSR for example), as it
may happen that a RREQ message may never reach its destination. This is
not only due to the different power transmission levels of the nodes
(this is not a problem specific to AODV as you also mention, but also to
any MANET routing protocol I believe), but because the neighbors of the
RREQ's destination may always have fresh routing info about that node
and send RREPs on its behalf. Apart from being a concern, is this a
problem then? I believe yes! Apart from load balancing concerns at high
loads and incorrect routes carried in RREPs (see the MobiComm98 paper
from Maltz/Broch), a scenario that comes in my mind that _could_ be
problematic using query quenching schemes is QoS-based routing. As
reservations need to be established on an end-to-end basis (see RSVP),
then an end-to-end routing protocol is also required.
(and a bit of RDMAR publicity...-:) You may want to have a look on our
RDMAR protocol
(http://www.ee.surrey.ac.uk/Personal/G.Aggelou/publications.html) where
Route Discovery is an end-to-end process and problems related to
incorrect RREPs  as well as to reservation set-up are avoided.

Thanks and Happy Easter!
George A.

---

From: [email-masked]
Date: Wed, 19 Apr 2000 14:43:04 +0200

Samir,

As far as I know, MAC layers use ack only for unicast packets not for
broadcast packets. But route request RREQ are broadcast packets and it
seems that bidirectional link are not checked during broadcast transmissions. 

Philippe

---

From: [email-masked]
Date: Wed, 19 Apr 2000 16:02:35 +0200

Dear George,

Yes you are right, with your definition of asymmetric links, the problem
arises with unidirectional links. Sorry for the confusion!

By query quenching you mean that B may generate a RREP after A's RREQ? But
this implies that B have before asked for a route to F. In the example I
gave, it is not even clear that B will be able to get a route to F if its
own RREQ's go via A. 
 
Thanks, I will look at RDMAR.

Philippe