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 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]