[Search] [txt|pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02                                                      
INTERNET-DRAFT                       Zygmunt J. Haas,  Cornell University
                                     Marc R. Pearlman, Cornell University
                                     Prince Samar,     Cornell University


Expires in six months on December 2001                          June 2001

      The Bordercast Resolution Protocol (BRP) for Ad Hoc Networks
                     <draft-ietf-manet-zone-brp-01.txt>

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC 2026, except the right to
   produce derivative works is not granted.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time. It is inappropriate to use Internet-Drafts as reference material
   or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   Distribution of this memo is unlimited.



Abstract

   The Bordercast Resolution Protocol (BRP) provides the bordercasting
   packet delivery service used to support network querying applications.
   The BRP uses a map of an extended routing zone, provided by the local
   proactive Intrazone Routing Protocol (IARP), to construct bordercast
   (multicast) trees, along which query packets are directed. Within the
   context of the hybrid ZRP, the BRP is used to guide the route requests
   of the global reactive Interzone Routing Protocol (IERP).  The BRP
   employs special query control mechanisms to steer route requests away
   from areas of the network that have already been covered by the query.
   The combination of multicasting and zone based query control makes
   bordercasting an efficient and tunable service that is more suitable
   than flood searching for network probing applications like route
   discovery.





Haas, Pearlman, Samar         Expires December 2001            [Page   i]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001


                                Contents

   Status of this Memo . . . . . . . . . . . . . . . . . . . . . .  i
   Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . .  i

   Applicability Statement . . . . . . . . . . . . . . . . . . .  iii
       A. Networking Context   . . . . . . . . . . . . . . . . .  iii
       B. Protocol Characteristics and Mechanisms  . . . . . . .  iii

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . .  1

   2.  Routing Zone Based Querying . . . . . . . . . . . . . . . .  2

   3.  Query Control Mechanisms  . . . . . . . . . . . . . . . . .  3

   4.  Bordercast Resolution Protocol (BRP) Implementation . . . .  4
       A. Packet Format  . . . . . . . . . . . . . . . . . . . . .  5
       B. Data Structures  . . . . . . . . . . . . . . . . . . . .  6
       C. Interfaces . . . . . . . . . . . . . . . . . . . . . . .  6
       D. State Machine  . . . . . . . . . . . . . . . . . . . . .  7
       E. Pseudocode Implementations . . . . . . . . . . . . . . .  8

   5.  References  . . . . . . . . . . . . . . . . . . . . . . . . 11

   Authors' Information  . . . . . . . . . . . . . . . . . . . . . 13
   MANET Contact Information . . . . . . . . . . . . . . . . . . . 13

























Haas, Pearlman, Samar         Expires December 2001            [Page  ii]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

Applicability Statement

A.  Networking Context

   Bordercasting is an efficient multicast packet delivery service used
   for guiding queries through the network.  When each node proactively
   tracks the topology of its surrounding extended routing zone, queries
   can be directed to the edge of the node's routing zone rather than
   blindly being relayed to *all* neighbors.  Special routing zone based
   query control mechanisms steer query packets away from regions of the
   network that have already been covered by the query.

   Within the context of ad hoc network routing, bordercasting is
   proposed as a more efficient and tunable alternative to broadcasting
   of route request messages for reactive (on-demand) routing protocols.
   We refer to any reactive routing protocol that bordercasts route
   requests as an Interzone Routing Protocol (IERP).  The link state
   information needed to support bordercasting is provided by a local
   proactive Intrazone Routing Protocol (IARP).  Thus, a routing protocol
   based on bordercasting is actually hybrid reactive/proactive.  For a
   properly chosen routing zone radius, IARP's cost of tracking routing
   zone topology is more than justified by the resulting savings in route
   discovery overhead through bordercasting.


B.  Protocol Characteristics and Mechanisms

   The Bordercast Resolution Protocol (BRP) is a packet delivery service,
   not a full featured routing protocol.  Bordercasting is enabled by a
   local proactive Intrazone Routing Protocol (IARP) and supports a
   global reactive Interzone Routing Protocol (IERP).  The character-
   istics of the IARP and IERP are summarized in their corresponding
   Internet drafts.



















Haas, Pearlman, Samar         Expires December 2001            [Page iii]

INTERNET DRAFT         Bordercast Resolution Protocol           June 2001


1. Introduction

   The design of ad hoc network routing protocols is influenced by link
   instability (due to node mobility) and limitations in available
   bandwidth and transmission power.  Traditional wired networks use
   proactive routing protocols, like OSPF [7] and RIP [15], to maintain
   up-to-date routes to all networks nodes.  More efficient proactive
   routing protocols have been developed for ad hoc networks [1][5][8]
   [9][14].  However, continuously tracking the frequent topology changes
   in a practical ad hoc network can still produce an overwhelming amount
   of control traffic.  Even worse, most of the acquired route
   information expires before it is ever used, making the proactive
   control traffic a poor investment of bandwidth.  In contrast, reactive
   routing protocols [6][10][13] only initiate a global, query-based,
   route discovery as routes are needed.  While some delay is incurred
   for route acquisition, the amount of overhead traffic is generally
   much less than proactive routing protocols, because routing information
   is not wasted.  For this reason, reactive protocols are generally
   viewed as being more suitable than proactive routing protocols for the
   power/bandwidth limited mobile ad hoc network.

   Although a global proactive routing protocol may overwhelm an ad hoc
   network's resources, a LIMITED SCOPE proactive routing protocol can
   be used to benefit a global reactive routing protocol.
   This hybrid routing approach forms the basis for the Zone Routing
   Protocol (ZRP) framework [4].

   The cost for each node to proactively track the topology of its
   surrounding R-hop neighborhood (routing zone) can be justified by
   improved route discovery efficiency and more effective route
   maintenance [11][12].  Routes to local destinations are immediately
   available, avoiding route discoveries.  When the global route
   discovery is needed, the routing zones can be used to efficiently
   guide route queries outward through bordercasting, rather than blindly
   relaying queries from neighbor to neighbor.  The proactive maintenance
   of routing zones also helps improve the quality and survivability of
   discovered routes, by making them more robust to changes in network
   topology.  Once routes have been discovered, routing zone offers
   enhanced, real-time, route maintenance.  Link failures can be bypassed
   by multiple hop paths within the routing zone.  Similarly, sub-optimal
   route segments can be identified and traffic re-routed along shorter
   paths.









Haas, Pearlman, Samar         Expires December 2001            [Page   1]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

   The bordercasting packet delivery service is provided by the
   Bordercast Resolution Protocol (BRP).  The BRP uses a map of an
   extended routing zone, provided by the local proactive Intrazone
   Routing Protocol (IARP) [2], to construct bordercast (multicast) trees
   along which query packets are directed.  (Within the context of the
   hybrid ZRP, the BRP is used to guide the route requests of the global
   reactive Interzone Routing Protocol (IERP) [3]).  The BRP employs
   special query control mechanisms to steer route requests away from
   areas of the network that have already been covered by the query.  The
   combination of multicasting and zone based query control makes
   bordercasting an efficient and tunable service that is more suitable
   than flood searching for network probing applications like route
   discovery.


2. Routing Zone Based Querying

   We illustrate the basic operation of routing zone based route
   discovery through a simple (but as we will see, inefficient) IERP
   implementation.  The source node, in need of a route to a destination
   node, first checks whether the destination lies within its routing
   zone.  (This is possible since every node knows the content of its
   routing zone).  If a path to the destination is known, no further
   route discovery processing is required.  On the other hand, if the
   destination is not within the source's routing zone, the source
   bordercasts a route query to all of its peripheral nodes.  Upon
   receipt of the route query, each peripheral nodes executes the same
   algorithm.  If the destination lies within its routing zone, a route
   reply is sent back to the source, indicating the route to the
   destination.  If not, this node forwards the query to ITS peripheral
   nodes.  This process continues until the query has spread throughout
   the network.

                              +---+
                     +---+    | F |
             +---+---| C |----+---+-----+---+    +---+
             | D |   +---+              | E |----| H |
             +---+     |      +---+-----+---+    +---+
                     +---+----| B |                |
                     | A |    +---+-----+---+    +---+
                     +---+              | G |    | I |
                                        +---+    +---+
                                          |
                                        +---+
                               +---+    | J |
                               | C |----+---+----+---+    +---+
                               +---+             | K |----| L |
                                                 +---+    +---+




Haas, Pearlman, Samar         Expires December 2001            [Page   2]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

   In the example illustrated above, node A has data to send to node L.
   Assuming each node's zone radius is 2 hops, node L does not lie within
   A's routing zone (which does include B,C,D,E,F,G).  Therefore, A
   bordercasts a routing query to its peripheral nodes: D,F,E and G.
   Each one of these peripheral nodes checks whether L exists in its
   routing zone. Since L is not found in any of these nodes routing
   zones, the nodes bordercast the request to their peripheral nodes.
   In particular, G bordercasts to K, which recognizes that L is in its
   routing zone and returns the requested route (L-K-G-A) to the query
   source (A).

   The one-to-many nature of bordercasting lends itself to a multicast
   implementation.  One approach is for a node to compute its bordercast
   (multicast) tree and append the corresponding packet forwarding
   instructions to the bordercast packet.  Alternatively, each node may
   re-construct the bordercast tree of its interior routing zone members,
   by proactively maintaining the topology of an "extended" zone.  In
   particular, if IARP maintains an "extended" routing zone of radius
   2R-1 hops (while queries are still directed at peripheral nodes of an
   "inner" routing zone of radius R hops), bordercast messages can be
   relayed without the need for explicit directions from the bordercast
   source.


3. Query Control Mechanisms

   Bordercasting has the potential to provide global querying that is
   more efficient than flooding.  To achieve this efficiency, the
   protocol should be able to terminate a query packet *before* it is
   delivered to a peripheral node in a region of the network already
   covered by the query.  The capability of providing this level of
   query control is significantly limited when bordercast messages are
   relayed to peripheral nodes over multiple hops by the network layer.

   To prevent redundant querying, nodes should be able to detect when the
   routing zones that they belong to have been covered by a query.
   Clearly, a node that bordercasts a route query is aware that its own
   zone has been covered.  If bordercast queries are relayed by IP, then
   the query will not be detected again until it reappears at the target
   peripheral nodes.  On the other hand, if query forwarding is performed
   within the routing protocol, then all nodes in the bordercast tree will
   detect the query (QD1).  Further query detection is possible in shared
   channel networks if the underlying MAC layer packet delivery is through
   neighbor broadcast or if promiscuous mode operation is enabled.  In
   this case, nodes may "overhear" a query even if they do not belong to
   the bordercast tree (QD2).






Haas, Pearlman, Samar         Expires December 2001            [Page   3]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

   Standard flood search protocols terminate query packets that are
   targeted for (or arrive at) previously queried *nodes*.  We can extend
   this idea to the BRP by discarding route queries before they arrive at
   targeted peripheral nodes belonging to a previously queried *routing
   zone*.  More precisely, a node will not relay a packet down a branch
   of the bordercast tree if each of the branch's downstream "leaves"
   (peripheral nodes) either lies inside the routing zone of a previous
   bordercasted node, or if this node has already relayed the query to
   that peripheral node.  This scheme, which we refer to as Early
   Termination (ET), relies on the aforementioned Query Detection to
   identify which routing zone nodes have already bordercast a query.
   The "extended" routing zone maintained by the IARP is then used to
   determine the members of these previously bordercasted nodes' routing
   zones.


4.  Bordercast Resolution Protocol (BRP) Implementation

   The BRP provides the "bordercasting" packet delivery service, here
   used to forward IERP route queries.  Queries are relayed from a
   bordercasting node outward to its peripheral nodes, along a
   bordercast (multicast) tree.  Although the intended targets of
   the bordercast are the peripheral nodes, the BRP delivers the
   bordercast query up to the higher layer application (eg. the IERP)
   at EVERY hop.  This is necessary for applications that use
   bordercasting, but are generally not "routing zone aware".

   When the BRP receives a bordercast query packet, it marks the interior
   nodes of the previous bordercasting node as having been "covered" by
   the query.  If this node is the peripheral node of the previous
   bordercaster, it assumes the role of bordercaster and marks the
   interior nodes of its own routing zone as "covered".  If future query
   messages are received, they will be steered away from the covered
   regions.

   After performing query detection, the node determines which downstream
   branches of the bordercaster's bordercast tree are to be pruned. A
   branch is pruned from the tree if all downstream peripheral nodes have
   been covered by the query.  This "early termination" helps steer the
   query outward, away from regions of the network that have already been
   covered by the query.  The remaining downstream peripheral nodes are
   marked as covered, and the links to downstream neighbors are recorded
   as outgoing links.

   The BRP delivers the query up to the higher layer application (IERP).
   After some processing, the application may return an updated query
   back to the BRP.  The BRP will then relay the query on the selected
   outgoing links.




Haas, Pearlman, Samar         Expires December 2001            [Page   4]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

   A.  Packet Format

                        1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       Query Source Address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Query Destination Address                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Query ID            |       R E S E R V E D         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Prev Bordercast Address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    |            E N C A P S U L A T E D     P A C K E T            |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


        * Query Source Address         (node_id)           (32 bits)
                IP address of the node that initiates the query.

        * Query Destination Address    (node_id)           (32 bits)
                IP address of the node that is the ultimate query
                destination.

        * Query ID                   (unsigned int)        (16 bits)
                Sequence number which, along with the Query Source
                Address uniquely identifies any BRP query in the network.

        * Query Extension              (char)              (8 bits)
                Indicates whether query should be forwarded to
                query destination.

        * Prev Bordercast Address      (node_id)           (32 bits)
                IP address of the most recent bordercasting node

        * Encapsulated Packet          (packet)

        *** note:  Within the context of the BRP, the Query Source
                   Address, Query Destination Address and Query ID
                   can assume the same values as corresponding
                   fields in the encapsulated query packet.
                   These BRP fields can be eliminated AS LONG AS:
                           (a) The BRP has read access to the contents of
                               the encapsulated packet.
                           (b) The BRP knows the format of the query
                               packet.




Haas, Pearlman, Samar         Expires December 2001            [Page   5]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

    B.  Data Structures
        B.1  IARP Routing Table          (see IARP specification)

        B.2  IARP Link State Table       (see IARP specification)

        B.3  Detected Query Cache

             +------------------------|--------------------------+
             |  Query  |   Query  ID  | BRP_cache_ID |   Prev    |
             |  Source |              |              |Bordercast |
             |(node_id)|(unsigned int)|(unsigned int)| (node_id) |
             |---------+--------------|--------------+-----------+
             |         |              |              |           |
             |         |              |--------------+-----------+
             |         |              |              |           |
             |---------+--------------|--------------+-----------+
             |         |              |              |           |
             |         |              |--------------+-----------+
             |         |              |              |           |
             +------------------------|--------------+-----------+

        B.4  Query Coverage

             +------------------------|---------------+
             |  Query  |   Query ID   |     graph     |
             |  Source |              |               |
             |(node_id)|(unsigned int)|  (net graph)* |
             |---------+--------------|---------------|
             |         |              |               |
             |---------+--------------|---------------|
             |         |              |               |
             |---------+--------------|---------------|

     * net_graph is a data structure that represents the connectivity of the
       extended routing zone, and whether each extended routing zone member
       has been covered by the query.

    C.  Interfaces

        C.1  Higher Layer (IERP)
            C.2.1  Send(packet, BRP_cache_ID)
                Used by the IERP to request packet transmission.

        C.2  Lower Layer (IP)
            C.2.1  Deliver(packet)
                Used by IP to deliver packet to BRP






Haas, Pearlman, Samar         Expires December 2001            [Page   6]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001


    D.  State Machine

      The BRP protocol consists of only one state (IDLE).  Therefore,
      no state transitions need to be specified. The BRP immediately
      acts upon an event and then returns back to the IDLE state.

      Notes: 1) X is used as a label for the node running this state
                machine.

      D.1
            Event:   A query is received from the higher layer (IERP).
                     An intrazone route to the query destination exists.

            Action:  If X has not already relayed the query to the
                     destination, X sends the query packet to the
                     next hop to the query destination.

      D.2
            Event:   A query is received from the higher layer (IERP).
                     An intrazone route to the query destination
                     DOES NOT exist.

            Action:  X constructs the bordercast tree of the previous
                     bordercaster.  X prunes branches leading to covered
                     peripheral nodes.  The remaining downstream
                     peripheral nodes are marked as covered and the
                     query packet is forwarded to the remaining
                     downstream neighbors.

      D.3
            Event:   A query is received from IP.

            Action:  Mark the interior nodes of the previous bordercaster
                     as covered.  If X is a peripheral node of the
                     previous bordercaster, it becomes the new previous
                     bordercaster.

                     X records its BRP state in the Detected Query Cache
                     and schedules (with a random jitter) delivery of the
                     enapsulated query to the higher layer (i.e. IERP).











Haas, Pearlman, Samar         Expires December 2001            [Page   7]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

    E.  Pseudocode Implementation

        We define two complimentary operations on packets:
        extract(packet) and load(packet)

            extract (packet)
                  extracts the fields of the BRP packet to the following
                  variables: {source, query_id, prev_bordercst,
                              encap_packet)

            load (packet)
                loads the values of the aforementioned variables into
                the fields of the BRP packet.


        E.1  Send(encap_packet, BRP_cache_ID)

             // If BRP_cache_ID is not NULL, then this is an existing
             // query that is being relayed and BRP state is extracted
             // from the Detected Queries Cache and Query Coverage
             // Table.  Otherwise, this is a new query and BRP state
             // is initialized.
             if(BRP_cache_ID)
             {
                source     = Detected_Queries[BRP_cache_ID].source;
                query_id   = Detected_Queries[BRP_cache_ID].query_id;
                prev_bcast = Detected_Queries[BRP_cache_ID].prev_bcast;
                coverage   = Query_Coverage[source,query_id].init();
             }
             else
             {
                source     = MY_ID;
                query_id   = MY_BORDERCAST_ID++;
                prev_bcast = MY_ID;
                Query_Coverage[source,query_id] =
                                 new_net_graph(IARP_link_state_table);
                coverage   = Query_Coverage[source,query_id];

                // Mark the previous bordercast's (here, the query
                // source's) interior routing zone nodes as covered.
                prev_bcast_int_nodes =
                         construct_routing_zone(coverage, prev_bcast);
                record_query_coverage(coverage, prev_bcast_int_nodes);
             }








Haas, Pearlman, Samar         Expires December 2001            [Page   8]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

             if((EXIST)IARP_route_table[query_dest])
             {
                 // Route to destination is KNOWN

                 // If the query destination is not already covered,
                 // select next hop to query destination as the
                 // outgoing neighbor.
                 if(!covered(coverage, query_dest))
                     out_neighbors =
                               IARP_Route_Table[query_dest].next_hop;
                 else
                     out_neighbors = {};

                 // Mark the query destination as covered
                 record_query_coverage(coverage, query_dest);
             }
             else
             {
                 // Route to destination is UNKNOWN

                 // Construct the previous bordercaster's bordercast
                 // tree.  Identify the subtree that is downstream from
                 // this node.  Prune branches from the subtree that
                 // lead to *covered* peripheral nodes.  Mark the
                 // subtree's remaining peripheral nodes as covered.
                 // and the remaining neighbors as outgoing neighbors.

                 bordercast_tree =
                         construct_bordercast_tree(coverage, prev_bcast);
                 out_peripheral_nodes =
                        bordercast_tree.my_downstream_peripheral_nodes();
                 out_neighbors =
                                bordercast_tree.my_dowstream_neighbors();


                 // Mark DOWNSTREAM peripheral nodes as covered
                 record_query_coverage(coverage, out_peripheral_nodes);
             }

             // Relay query packet to outgoing neighbors.
             load(packet);
             send(packet,out_neighbors, IP);










Haas, Pearlman, Samar         Expires December 2001            [Page   9]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

        E.2  Deliver(packet)

             extract(packet);

             // Load the known coverage of this query
             if(!(EXISTS) Query_Coverage[source, query_id])
             {
                 Query_Coverage[source,query_id] =
                       new_net_graph(IARP_link_state_table);
             }
             coverage = Query_Coverage[source, query_id];

             // mark the previous bordercaster's interior
             // routing zone nodes as covered.
             bordercast_tree =
                   construct_bordercast_tree(coverage, prev_bcast);
             record_query_coverage(coverage, prev_bcast_int_nodes);

             // If this node is the previous bordercaster's peripheral
             // node, then this node becomes the new previous
             // bordercaster and this node's interior routing zone
             // nodes are marked as covered.
             if(is_peripheral_node(prev_bcast, MY_ID))
             {
                  prev_bcast = MY_ID;
                  prev_bcast_int_nodes =
                              construct_routing_zone(prev_bcast);
                  record_query_coverage(coverage,
                                           prev_bcast_int_nodes);
             }

             // Record BRP "state" in Detected Queries Cache, so that
             // the query can be properly forwarded when returned by
             // the higher layer app (IERP)
             BRP_cache_ID++;
             add(Detected_Queries[source,query_id],
                                              (BRP_cache_ID, prev_bcast);
             schedule(remove(Detected_Queries[BRP_cache_ID]),
                                                     MAX_QUERY_LIFETIME);
             schedule(deliver(encap_packet, BRP_cache_ID), RELAY_JITTER);












Haas, Pearlman, Samar         Expires December 2001            [Page  10]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001

5. References

[1]   Garcia-Luna-Aceves, J.J. and Spohn, M., "Efficient Routing in
              Packet-Radio Networks Using Link-State Information,"
              WCNC '99, September 1999.

[2]   Haas, Z.J., Pearlman, M.R. and Samar, P., "Intrazone Routing
              Protocol (IARP)," IETF Internet Draft,
              draft-ietf-manet-iarp-01.txt, June 2001.

[3]   Haas, Z.J., Pearlman, M.R. and Samar, P., "Interzone Routing
              Protocol (IERP)," IETF Internet Draft,
              draft-ietf-manet-ierp-01.txt, June 2001.

[4]   Haas, Z.J., Pearlman, M.R. and Samar, P., "Zone Routing Protocol
              (ZRP)," IETF Internet Draft, draft-ietf-manet-zrp-04.txt,
               January 2001.

[5]   Jacquet, P., Muhlethaler, P., Qayyum A., Laouiti A., Viennot L.,
              and Clausen T., "Optimized Link State Routing Protocol,"
              IETF Internet Draft, draft-ietf-manet-olsr-03.txt,
              November 2000.

[6]   Johnson, D.B. and Maltz, D.A., "Dynamic Source Routing in Ad-Hoc
              Wireless Networks," in Mobile Computing, edited by T.
              Imielinski and H. Korth, chapter 5, pp. 153-181,
              Kluwer, 1996.

[7]   Moy, J., "OSPF Version 2," INTERNET DRAFT STANDARD, RFC 2178,
              July 1997.

[8]   Murthy, S. and Garcia-Luna-Aceves, J.J., "An Efficient Routing
              Protocol for Wireless Networks," MONET, vol. 1, no. 2,
              pp. 183-197, October 1996.

[9]   Ogier, R. "Efficient Routing Protocols for Packet-Radio Networks
              Based on Tree Sharing," MoMUC '99, November 1999.

[10]  Park, V.D. and Corson, M.S., "A Highly Adaptive Distributed
              Routing Algorithm for Mobile Wireless Networks,"
              IEEE INFOCOM'97, Kobe, Japan, 1997.

[11]  Pearlman, M.R. and Haas, Z.J., "Determining the Optimal
              Configuration for the Zone Routing Protocol," IEEE JSAC,
              August, 1999.

[12]  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.



Haas, Pearlman, Samar         Expires December 2001            [Page  11]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001


[13]  Perkins, C.E. and Royer, E.M., "Ad Hoc On-Demand Distance
              Vector Routing," IEEE WMCSA'99, New Orleans, LA, Feb. 1999

[14]  Perkins, C.E. and Bhagwat, P., "Highly Dynamic
              Destination-Sequenced Distance-Vector Routing (DSDV) for
              Mobile Computers," ACM SIGCOMM, vol.24, no.4, October 1994.

[15]  Postel, J., "Internet Protocol," RFC 791, Sept. 1981.











































Haas, Pearlman, Samar         Expires December 2001            [Page  12]


INTERNET DRAFT         Bordercast Resolution Protocol           June 2001


Authors' Information

   Zygmunt J. Haas
   Wireless Networks Laboratory
   323 Frank Rhodes Hall
   School of Electrical Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   tel: (607) 255-3454, fax: (607) 255-9072
   Email: haas@ee.cornell.edu

   Marc R. Pearlman
   389 Frank Rhodes Hall
   School of Electrical Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   tel: (607) 255-0236, fax: (607) 255-9072
   Email: pearlman@ee.cornell.edu

   Prince Samar
   372 Frank Rhodes Hall
   School of Electrical Engineering
   Cornell University
   Ithaca, NY 14853
   United States of America
   tel: (607) 255-9068, fax: (607) 255-9072
   Email: samar@ee.cornell.edu


 The MANET Working Group contacted through its chairs:

   M. Scott Corson
   Institute for Systems Research
   University of Maryland
   College Park, MD 20742
   (301) 405-6630
   corson@isr.umd.edu

   Joseph Macker
   Information Technology Division
   Naval Research Laboratory
   Washington, DC 20375
   (202) 767-2001
   macker@itd.nrl.navy.mil





Haas, Pearlman, Samar         Expires December 2001           [Page   13]