Subject: RE: ZRP :question on query detection (fwd)

From: Marc Pearlman <[email-masked]>
Date: Wed, 20 Jun 2001 13:15:32 -0400 (EDT)

Hi Prasad,

First, take a look at the following paper, scheduled to appear in
Transactions on Networking, August 2001:

"The Performance of Query Control Schemes for the Zone Routing Protocol",
Z.J. Haas and M.R. Pearlman
(http://www.ee.cornell.edu/~haas/Publications/tn8.ps)

This paper describes various query control mechanisms (including QD and
ET), and provides illustrative examples.

If you visualize route request (RREQ) messages propagating through the
network, you can divide the network into two regions: covered and
uncovered.  Loosely speaking, the covered region marks where the RREQ has
been, while the uncovered region marks where the RREQ has not yet
appeared.  The objective of is to send RREQs outward into the *uncovered*
region, and not back into the *covered* region.

In broadcast-based route discovery, nodes that receive the RREQ are
covered -  those that have not received the RREQ are uncovered.  We extend
this concept to bordercasting (ZRP) by addressing the role of routing
zones.  In particular, a node is covered if it belongs to the routing zone
of a node that bordercasts the RREQ.  All other nodes in the network are
uncovered.  This is a powerful property, because it means that nodes can
be covered without actually having to receive a RREQ.

This leads into my brief explanation of QD and ET, which are complementary
query control mechanisms for ZRP.  As I stated above, the objective of
query based route discovery protocols is to relay the RREQs to the
uncovered regions and away from the covered regions.  In ZRP, this means
that relaying nodes need to be able to identify covered regions of the
network (Query Detection = QD) and terminate messages that are headed for
those covered regions (Early Termination = ET)

In Query Detection (QD), a node examines each received RREQ and identifies
the most recent bordercaster of the RREQ.  That bordercaster, and *its
entire routing zone*, are marked as covered.  The distinction between QD1
and QD2 has to do with which RREQ messages a node is able to
receive/examine.   At a minimum (QD1), a node receives (and examines) the
messages that it relays from a bordercaster to its peripheral node(s).  In
QD2, a node may receive any RREQ transmitted in its neighborhood, thanks
to a shared broadcast channel.  More received messages == bettery query
detection.

RREQs are relayed from a bordercaster to its peripheral nodes along a
bordercast (multicast) tree. The relaying nodes in the bordercast tree use
Early Termination (ET) to identify *covered* downstream peripheral nodes
and prune them from the bordercast tree (see note at bottom).  The pruning of
covered peripheral nodes serves to steer the RREQ outward.

I hope this sheds some light on the operation of ZRP and its query control
mechanisms.  Let me know if I you'd like me to address any of these issues
in more detail.

regards,

Marc

Note:  in the current incarnation of bordercasting, the rules for ET
pruning are a little more complicated than described above.  Covered nodes
that are not strictly inside (ie. not peripheral) a covered routing zone
need to be dealt with specially (see BRP ID draft or cited ToN paper for
details).  This is to avoid a possible starvation condition that can occur
when two bordercasters forward a RREQ to the same peripheral node at
approximately the same time (the two RREQ "threads" might effectively
cancel each other out).

The Early Termination criteria, as specified in the BRP draft and ToN
paper, provides provably correct ZRP operation.

We have also developed a modifed version of bordercasting / query
control.  This eliminates the starvation problem, allowing ET to simply
prune all covered peripheral nodes, without special consideration.  I
believe Prince Samar described this "MZRP" at the last MANET WG meeting.

 > Hi friends,
 >  I am implementing ZRP protocol for ad hoc networks. i have a
 > question on boarder Resolution Protocol (BRP) which is
 > implemented as a part of ZRP.
 > The <draft-ietf-manet-zone-brp-00.txt> says that Query
 > controle mechanisms can be used to efficiently steer the
 > route query packets.
 > I am not able to understand the concepts of QD1 , QD2 and
 > also Early Termination (ET).
 > Can any one help me by explaining  these concepts with some examples.
 > Your help is heighly appreciated.
 >
 > Thanks in advance
 > PRASAD
 > SAMSUNG, India
 > Bangalore
 > India.
 >
 >

---

From: [email-masked]
Date: Thu, 21 Jun 2001 18:51:13 +0900

Hi Marc,
              Thank you very much for your clarification and it helped us to a great extent.

     We still have some doubts on following topic.
   
    1. Extended routing zone  -  what is the scope of this extended routing zone and the concept of (2R-1).

     We will be looking forward for your clarification.

Thanks & Regards,
Prasad.

       Hi Prasad,

regards,

Marc

> Your help is heighly appreciated.

/--------------------------------< Header >--------------------------------/
Date: Wed, 20 Jun 2001 13:15:32 -0400 (EDT)
From: Marc Pearlman <[email-masked]>
To: [email-masked]
cc: [email-masked], Zygmunt Haas <[email-masked]>,
        Prince Samar <[email-masked]>
Subject: RE: ZRP :question on query detection (fwd)

---

From: Marc Pearlman <[email-masked]>
Date: Fri, 22 Jun 2001 07:20:50 -0400 (EDT)

Hi Prasad,

 >     1. Extended routing zone  -  what is the scope of this
 > extended routing zone and the concept of (2R-1).
 >
 >

To understand where the (2*R-1) EXTENDED routing zone comes from, we need
to determine how much local topology each node must know in order to
support R hop bordercast (ie. bordercast to peripheral nodes that are R
hops away).

Consider a bordercasting node X.

  I.  A bordercasting node X needs to:
     (a) identify its interior nodes (for Query Detection (QD) / Early 
Termination (ET))
     (b) identify its downstream peripheral nodes (for QD/ET)
     (c) construct its R hop bordercast tree.

To meet criteria a-c, it is sufficient for X to know its surrounding R hop
topology.

  However...

  II.  Each interior node Y of X's routing zone must be able to:
     (a) identify X's interior nodes (for QD/ET)
     (b) identify X's peripheral nodes that are downstream of Y (for QD/ET)
     (c) construct X's R hop bordercast tree.

To meet criteria a-c, X's interior nodes (which are no more than R-1 hops
from X) need to know their surrounding (R)+(R-1) == 2*R-1 hop topology.

  III.  Each peripheral node Z of X's routing zone must be able to:
     (a) identify X's interior nodes (for QD/ET)

      (note:  Conditions (b) and (c) do not apply since Z is the target leaf
		in X's bordercast tree)

To meet this criterion, X's peripheral nodes (which are R hops from X)
need to know their surrounding (R)+(R-1) == 2*R-1 hop topology.

Taking the maximum of the local topology requirements from conditions I,II
and III, we find that bordercasting to R hop peripheral nodes can be
supported if each node proactively tracks the topology of its surrounding
(2*R-1) hop EXTENDED routing zone.

Having said all this, it is worth mentioning that ZRP can be modified to
reduce (and in some cases eliminate) the 2*R-1 hop EXTENDED routing zone
requirement.  For example, X could append a map of its bordercast tree (or
even entire routing zone) to its bordercast RREQ packet.  This "source
directed bordercast" eliminates the need for relaying nodes to reconstruct
X's bordercast tree on their own.  Query Detection / Early termination can
function correctly given a reduced view of X's routing zone.  However,
this degrades the steering capability of the query control mechanisms.
Finally, re-bordercasting can occur before the RREQ reaches X's peripheral
node.  (For example, re-bordercasting occurs at every hop in MZRP.)
This also degrades query steering capability somewhat, but it reduces the
EXTENDED routing zone requirement to R+1 hops (and actually eliminates
the need for EXTENDED routing zones on systems that don't use/have
MAC broadcast).

The point is that there is no free lunch.  We can reduce IARP's burden of
tracking an extended routing zone.  However, it adds some overhead to the
reactive route discovery process.  Our experience to date has been that
these modifications don't have much effect on the overall ZRP traffic
load.  However, there are some secondary benefits (eg. reduced
computational load, less complicated protocol implementation, easier
analysis, etc.) that make some of the aforementioned approaches
attractive.

regards,

Marc

 > > > ---------- Forwarded message ----------
 > > > Date: Thu, 21 Jun 2001 18:51:13 +0900
 > > > From: [email-masked]
 > > > To: [email-masked]
 > > >     1. Extended routing zone  -  what is the scope of this
 > > > extended routing zone and the concept of (2R-1).
 > > >

 > > > /--------------------------------< Header
 > > > >--------------------------------/
 > > > Received: from imail02.samsung.co.kr (imail02.samsung.co.kr
 > > > [101.1.3.102])
 > > > by gp_xman. (8.8.8H1/8.8.8) with ESMTP id CAA09132
 > > > for <prasad@[101.1.3.30]>; Thu, 21 Jun 2001 02:18:09 +0900 (KST)
 > > > Received: from ee.cornell.edu (anise.ee.cornell.edu [128.84.239.14])
 > > > by imail02.samsung.co.kr (8.8.8/8.8.8) with ESMTP id CAA13382
 > > > for <[email-masked]>; Thu, 21 Jun 2001 02:12:51
 > > > +0900 (KST)
 > > > Received: from descartes (descartes.ee.cornell.edu [128.84.236.60])
 > > > by ee.cornell.edu (8.9.3/8.9.1) with ESMTP id NAA04781;
 > > > Wed, 20 Jun 2001 13:16:06 -0400 (EDT)
 > > > Message-ID:
 > > > <[email-masked]>
 > > > MIME-Version: 1.0
 > > > Content-Type: TEXT/PLAIN; charset=US-ASCII
 > > >
 > > >
 > >
 > >
 >