Subject: RE: [manet] When GPSR loops on the face?

From: "#ZHOU ZHI#" <[email-masked]>
Date: Sun, 16 Nov 2003 12:22:12 +0800

Hi Casey,

Thanks for your example.

Can I get the following conclusion:
1) If the source and destination are not partitioned, GPSR will also
find the route. 
2) If the source and destination are partitioned, GPSR will lead the
packet to travel around the whole perimeter of the source partition. And
finally the packet will reach the node where it entered perimeter mode.
3) no matter whether source and destination are partioned or not, it is
possible that the packet travels back to the node where enters perimeter
mode and the source, but without being dropped.

If so, from my second conclusion, the traversing loop in GPSR only
occurs in exterior face, doesn't it?
Furthermore, I think the worst situation for GPSR is like the following
figure. Node x is where the packet from S enteres perimeter mode. If the
S section is almost the whole network, the packet will almost travel the
whole perimeter of the network to reach D.
_________
|    D         |
|_______   |
_______|   |_____________________ ... ...
|   x                                           
|   S
|
|
|
|______________________________ ... ...

-----Original Message-----
From: Casey Carter [mailto:[email-masked]] 
Sent: 2003?11?16? 10:47
To: #ZHOU ZHI#
Subject: Re: [manet] When GPSR loops on the face?

Here's an easy one: The network is partitioned into two connected
components, with the source in one partition, and the destination in
another. The packet will traverse the convex hull of the source's
partition.

#ZHOU ZHI# wrote:

> Hi all,
> Can anybody give me an example where GPSR will receive the packet in 
> perimeter mode for the second time? that means that the packet got 
> looped on the current face traversing.
> thanks!
> Zhou Zhi (Mr.)
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Ph.D. student, CeMNeT, SCE
> Nanyang Technological University
> - Home Address:
> Jurong West St 74, Blk 755, #11-56, Singapore 640755 
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

--
Casey Carter
[email-masked]
[email-masked]
AIM: cartec69

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Casey Carter <[email-masked]>
Date: Sun, 16 Nov 2003 12:00:42 -0600

>1) If the source and destination are not partitioned, GPSR will also
Yes: if there is a route, GPSR will find it.

>finally the packet will reach the node where it entered perimeter mode.
Yes: Completing a loop in perimeter mode -- returning to the node where 
you started without ever leaving perimeter mode -- proves that the 
network is partitioned.

>mode and the source, but without being dropped.
For the source, yes this is true.  For the node where it entered 
perimeter mode, the packet will be dropped upon returning unless there 
was a period of greedy mode routing between the two visits.

>occurs in exterior face, doesn't it?
Yes: GPSR switches from one face to the next when when it finds an edge 
of the face that is cut by the line connecting the source and 
destination.  Also, it leaves perimeter mode and returns to greedy mode 
when it finds a node that is closer to the destination than the node 
where it entered perimeter mode.

>whole perimeter of the network to reach D.
This is an O(n) delivery -- the worst case is O(n^2).  The intuiton 
behind the worst case is to layout the network so that perimeter mode 
traverses nearly the whole thing before finding a node a bit closer. 
 Switching to greedy mode gets you a hop closer, at which point you need 
to go back to perimeter mode, and traverse the same path again, but go a 
couple of steps farther than last time to find a node a bit closer. 
 Lather, rinse repeat ;)

There is a beatiful diagram of such a worst case network, and a lot of 
interesting discussion of geo-routing, in "Worst-Case Optimal and 
Average-Case Efficient Geometric Ad-Hoc Routing," Fabian Kuhn et al, 
MobiHoc 2003.

-- 
Casey Carter
[email-masked]
[email-masked]
AIM: cartec69