Subject: [manet] ZRP Should it be reversed

From: "Yasser A. Lotfy" <[email-masked]>
Date: Tue, 06 Aug 2002 18:32:24 -0400

Good day everybody,

Just have some thoughts on ZRP, it employes proavtive component IARP on the local level, and reactive component IERP on the global (wider) level. This provides the protocol with a situation where every node has to probatively update it's local tables, therefore no real advantage for the battery life since you can not go to sleep mode.

Now the question is, why don't we reverse that? if the local updates are reactive, and only global updates are proactive, then a good knowldge of the network "skeleton" is available. I mean why not pro/reac instead of reac/pro, I assume you already went through this before, there must be a good reason.

Any idea out there?

Yasser

__________________________________________________________
Win a First Class Trip to Hawaii to Vacation Elvis Style!
http://r.lycos.com/r/sagel_mail/http://www.elvis.lycos.com/sweepstakes

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

---

From: Prince Samar <[email-masked]>
Date: Wed, 7 Aug 2002 02:07:52 -0400 (EDT)

Hi Yasser,

>Just have some thoughts on ZRP, it employes proavtive component IARP on
>the local level, and reactive component IERP on the global (wider) level.
>This provides the protocol with a situation where every node has to
>probatively update it's local tables, therefore no real advantage for the
>battery life since you can not go to sleep mode.

On the contrary, a node can use the local topology information provided by 
the IARP to decide if its absence would compromise network connectivity. 
Intelligent node participation/sleep mode algorithms can be developed 
based on this information. e.g.,
 
  Pearlman, M.R., Deng, J., Liang, B., and Haas, Z.J., "Elective 
  Participation in Ad Hoc Networks based on Energy Consumption," to 
  appear in Globecom 2002, November 2002.

>Now the question is, why don't we reverse that? if the local updates are
>reactive, and only global updates are proactive, then a good knowldge of
>the network "skeleton" is available. I mean why not pro/reac instead of
>reac/pro, I assume you already went through this before, there must be a
>good reason.

The Zone Routing framework uses the local topology information to provide 
a multicasting query distribution service, called bordercasting (BRP). In 
bordercasting, only a subset of the network nodes need to be queried and, 
thus, its more efficient than flooding. This bordercasting service is used 
by the globally reactive IERP to efficiently query the network to find a 
route to the destination. 

There are many other advantages of maintaining the topology of the local 
neighborhood of a node. Once a route has been discovered, changes in local 
connectivity can be quickly identified, allowing for either proactive 
route repair or proactive route shortening. 

  Pearlman, M.R., Haas, Z.J. and S.I. Mir, "Using Routing Zones to Support 
  Route Maintenance in Ad Hoc Networks," IEEE WCNC 2000, Chicago, IL, 
  Sept. 2000.

Local multi-hop feedback of link layer acknowledgments can be used to 
discover and reliably use unidirectional links.

  Pearlman, M.R., Haas, Z.J. and B.P. Manvell, "Discovering and Reliably 
  Communicating over Unidirectional Links in Ad Hoc Networks," IEEE WCNC 
  2000, Chicago, IL, Sept. 2000.

By identifying overlaps in local connectivity, broadcast message can be 
distributed to all nodes more efficiently (e.g., OLSR's multipoint relay).

One simple reason why making global updates proactive may not be practical 
is that the size of the whole network may be large (and without clear 
boundaries), causing significant amount of proactive update traffic. 
Also, knowledge about a link breakage between two nodes in one part of the 
network may not be such a useful piece of information in other parts of 
the network.

Hope this helps,
Prince.

---

From: Prince Samar <[email-masked]>
Date: Wed, 7 Aug 2002 02:07:52 -0400 (EDT)

Hi Yasser,

 

Hope this helps,
Prince.

---

From: lorry <[email-masked]>
Date: Wed, 07 Aug 2002 22:46:20 +0800

Hi, Prince,

> route to the destination. 

I read the latest drafts about ZRP and I wonder if BRP could be improved in some extent. Now, BRP propagates in a hop-by-hop way. Say, A-B-C-D-E are five neighbor nodes and ZRP radious is 2. Then if node A wants to find E, it first bordercasts, then B bordercasts, then C finds E in its local scope and response to A. My question is, why should an intermediate node (node B in the example) bordercasts? I think as long as only the border nodes resume bordercasts, the destination can be reached all the same. Just as in this case, B doesn't need to bordercasts so that routing becomes more efficient. Also, if the routing metric is hop count, this method should always work, since the route with least hop count can't be missed. Assuming that each node keeps its complete local information and no node transmits a same bordercast packet more than once, this conclusion can be proved. If your answer is that BRP is designed like this just for supporting various routing metrics, then I take b!
ack the question. But I want get a confirm from you. Or are there any other reasons that I have not thought of? Thanks a lot!

Ruiliang Chen

---

From: lorry <[email-masked]>
Date: Wed, 07 Aug 2002 22:46:20 +0800

Hi, Prince,

Ruiliang Chen

---

From: Prince Samar <[email-masked]>
Date: Wed, 7 Aug 2002 13:50:45 -0400 (EDT)

Hi Ruiliang,

>I read the latest drafts about ZRP and I wonder if BRP could be improved
>in some extent. Now, BRP propagates in a hop-by-hop way. Say, A-B-C-D-E
>are five neighbor nodes and ZRP radious is 2. Then if node A wants to
>find E, it first bordercasts, then B bordercasts, then C finds E in its
>local scope and response to A. My question is, why should an intermediate
>node (node B in the example) bordercasts? I think as long as only the
>border nodes resume bordercasts, the destination can be reached all the
>same. Just as in this case, B doesn't need to bordercasts so that routing
>becomes more efficient. Also, if the routing metric is hop count, this
>method should always work, since the route with least hop count can't be
>missed. Assuming that each node keeps its complete local information and
>no node transmits a same bordercast packet more than once, this
>conclusion can be proved. If your answer is that BRP is designed like
>this just for supporting various routing metrics, then I take back the
>question. But I want get a confirm from you. Or are there any other
>reasons that I have not thought of? Thanks a lot!

If I understand correctly, the method you have described is exactly how 
the previous version of BRP worked. In this method, only the peripheral 
nodes bordercast again, but the intermediate nodes still have to forward 
the query along the previous bordercasting node's bordercast tree -- so 
that B would forward the query to C which is a peripheral node of A. For 
query control, this forwarding is done at the routing layer so that the 
intermediate nodes can mark the effective "coverage" of the query. Also, 
each node maintains an extended routing zone so that an intermediate node 
can reconstruct the previous bordercasting node's bordercast tree and 
identify the next hop downstream nodes in the bordercast tree.

The new version of BRP is different as follows. When an intermediate node 
(node B in the example) receives the query, instead of reconstructing the 
previous bordercasting node's (node A's) bordercasting tree, it (node B) 
constructs its own bordercast tree to its "uncovered" peripheral nodes 
(node D in the example). It then sends the query to the next hop neighbors 
in its bordercast tree (node C). When node C receives the query, it finds 
that the destination (node E) belongs to its routing zone and sends a 
reply back to the source (node A).
 
Thus, even when the intermediate nodes do not bordercast, they still 
construct a bordercast tree -- the difference between the two methods lies 
in whether the node constructs the previous bordercasting node's 
bordercast tree or its own bordercast tree.

In the new version, as a node does not need to reconstruct the previous 
bordercasting node's bordercast tree, the need for maintaining an extended 
routing zone is eliminated. This leads to significant reduction in the 
proactive component of the routing control traffic.

Also, the new version is easier to deal with analytically. For example, 
its now easy to show that a node will not forward a route query more than 
once. In the previous version, this was not clear.

Let me know if you have any questions.

Regards,
Prince.

---

From: Prince Samar <[email-masked]>
Date: Wed, 7 Aug 2002 13:50:45 -0400 (EDT)

Hi Ruiliang,

 

Regards,
Prince.