Internet Engineering Task Force Yunjung Yi INTERNET DRAFT UCLA Expires May 14, 2002 Taek Jin Kwon draft-yi-manet-pc-00.txt Telcordia Mario Gerla UCLA 14 November 2001 Passive Clustering in Ad Hoc Networks (PC) Status of the Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. 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 mate- rial 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. Comments should be sent to the author at yjyi@cs.ucla.edu. This draft expires on May 14, 2002. Copyright Notice Copyright (C) The Internet Society (1999-2001). All rights reserved. Abstract This document describes Passive Clustering (PC) protocol that is a cluster formation mechanism designed for mobile ad hoc networks where the resources (e.g., bandwidth, power) are limited and the topology changes dynamically. This protocol, PC, provides an energy-efficient way of partitioning a homogeneous ad hoc network into clusters in a passive way. In other words, PC constructs and maintains clusters Yi, Kwon and Gerla Expires May 14, 2002 [Page 1]
I-D PC 14 November 2001 using on-going data packets instead of extra explicit control mes- sages. The resulting clusters have only one CLUSTER HEAD (a represen- tative node - CH) on the center of each cluster and the transmission range of each CH defines the area of the cluster. With reasonable on-going traffic, PC effectively constructs a cluster architecture that changes adaptively to the node mobility and pro- vides a platform for efficient flooding. Table of Contents Abstract ..................................................... 1 1. Introduction .............................................. 3 2. Terminology ............................................... 5 3. The Assumptions and Requirements .......................... 7 4. Basic Description and Conceptual Data Structures........... 7 4.1. The States of Each Node .............................. 8 4.2. The Data Structures .................................. 10 4.3. The Format of PC Header in IP Option Field ........... 12 5. The Detailed Algorithm ................................... 13 5.1. Packet Processing .................................... 13 5.1.1. Incoming Packet Processing ....................... 14 5.1.2. Outgoing Packet Processing ....................... 15 5.1.2.1. First Declaration Wins Rule ................ 15 5.2. Management ........................................... 16 5.3. The Functions ........................................ 16 5.3.1. Add ClusterHead ................................. 16 5.3.2. Add Gateway ..................................... 17 5.3.3. Add Initial ..................................... 17 5.3.4. Add Neighbor .................................... 17 5.3.5. Check ClusterHead ............................... 18 5.3.6. Check Gateway ................................... 18 5.3.7. Check Initial ................................... 18 5.3.8. Check Neighbor .................................. 18 5.4. Gateway Selection Heuristic .......................... 18 5.4.1. One Gateway Node per Each Pair of CHs ........... 19 5.4.2. The Distributed Gateway Selection Mechanism ..... 20 5.4.3. The Procedure ................................... 20 5.4.3.1. The Processing of Outgoing Packets Member Node 20 5.4.3.2. ReCalculate Member State ................... 23 5.5. The Lowest ID Competition ............................ 24 5.5.1. The CH Give-Up Message .......................... 25 Yi, Kwon and Gerla Expires May 14, 2002 [Page 2]
I-D PC 14 November 2001 5.6. The Timeout Scheme ................................... 25 5.7. The "HELLO" message .................................. 25 6. The Applicability ......................................... 25 6.1. The Applicability to On-demand Routing Protocol ...... 25 6.2. Protocol Characteristics ............................. 26 7. Suggested Parameters ...................................... 27 8. The Discussion and Implementation Consideration ........... 27 8.1. Problems with a Critical Path Loss ................... 27 8.2. The Possible Solutions ............................... 28 8.3. Some Comments ........................................ 29 9. Author's Addresses ........................................ 29 References ................................................... 30 1. Introduction Passive Clustering (PC) dynamically partitions the network in clus- ters interconnected by gateway nodes. This protocol keeps the bene- fits of the cluster architecture. It, however, improves previous cluster formation schemes [1, 2, 3] and removes control overhead of background cluster formation and maintenance using the concept of "passive" construction. PC is an "on demand" protocol. It constructs and maintains the clus- ter architecture only when there are on-going data packets that pig- gyback "cluster-related information" such as the state of a node in a cluster and an IP address of a node. Each node collects neighbor information through promiscuous packet receptions. Thus, PC does not necessitate background overhead of clustering. Active clustering, instead, uses explicit control packets to build and maintain clusters and is working in the background all the time. PC has two innovative mechanisms for the cluster formation: the "First Declaration Wins" rule (chapter 5.1.2.1) and "Gateway Selec- tion Heuristic" (chapter 5.4). With the "First Declaration Wins" rule, a node that first claims to be a CLUSTER HEAD 'rules' the rest of nodes in its clustered area (radio coverage). There is no waiting period (to make sure all the neighbors have been checked) unlike that in all the weight-driven clustering mechanisms [2, 7]. Also, "Gateway Selection Heuristic (chapter 5.4)" provides a procedure to Yi, Kwon and Gerla Expires May 14, 2002 [Page 3]
I-D PC 14 November 2001 elect the minimal number of gateways required to maintain connectiv- ity (including distributed gateway nodes) in a distributed manner. Passive Clustering (PC) contributes several innovative features as compared with "active" clustering schemes. Namely: (1) PC requires only tiny extra control overhead to resolve concurrent claims by com- peting CLUSTER HEADs. (2) PC builds up clusters instantaneously once data packets are generated and start flowing; (3) PC uses a novel, efficient gateway selection heuristic to choose the minimum number of forwarding nodes; (4) PC reduces node power consumption by eliminat- ing the background cluster forming overhead. Exploiting the above-mentioned features, PC can be applied to execute efficient flooding, which is one of the key procedures in ad hoc net- works. Many ad hoc network protocols (e.g., routing, service discovery, etc.) use flooding as the basic mechanism to propagate control mes- sages. In flooding, each node transmits the same message until that packet has been propagated to the entire network. Typically, only a subset of the neighbors is required to forward the message in order to guarantee complete flooding to the entire network. If the node geographic density (the degree of neighbors) is too high, the flooding is very inefficient due to redundant, "superfluous" for- warding. In fact, excessive flooding packets increase link overhead and wireless medium congestion, and degrade the network performance. To improve the scalability of the flooding, an efficient flooding, in which only selected dominant nodes participate in flooding, is neces- sary. More importantly, it is required to choose such dominant nodes with very low overhead. PC leads to efficient flooding in that it provides an energy- efficient clustering (low overhead) and is independent to the number of neighbors (scalable). PC works most effectively in geographically dense and dimensionally large networks. In contrast, other schemes merely proposed for efficient flooding [4, 5] are suffering from huge control message overhead under high mobility situation or den- sity situation. Note that, with reasonable on-going data traffic, PC constructs impromptu "soft-state" clusters, in which nodes do not begin cluster- ing unless they have outgoing or incoming packets generated by some application. They do build up clusters instantly, without any "deployment" latency, however, when data packets start flowing. 2. Terminology Yi, Kwon and Gerla Expires May 14, 2002 [Page 4]
I-D PC 14 November 2001 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [6] The following terms are also used to describe PC: node A MANET router that implements passive clustering, identified by a unique node ID. cluster A cluster consists of a group of nodes within the transmission range of one of them elected as a CLUSTER HEAD. Cluster Member All nodes within a cluster except for the CLUSTER HEAD are called members. A member is considered to "belong to cluster {CH1} " when it has received (overheard) packets from the CLUSTER HEAD "CH1 "of the cluster {CH1}. CLUSTER HEAD (CH) A CLUSTER HEAD (CH) of a cluster is a central node that can be directly reached from each member node of the cluster. Each cluster should have only one CLUSTER HEAD. Chapter 5.1.2.1 explains how to elect a CH. The basic idea of election is that one of candidate CHs claims (declares) as a CH when that node has an outgoing packet. A node can be a can- didate CH only when this node is neither isolated nor a member to any cluster. If two nodes declare as CHs at the same time, then a node with the lower node ID wins the other. Unless a packet sent from another CH comes in, a CH keeps its role as a CH. For the purpose of load-balancing, however, a CH can intentionally give up its role. Note that the traffic tends to be concentrated on CHs and gateway nodes. PC results very stable cluster architecture compared with other clustering mechanisms even with the mobility. The reason why PC is a stable is that PC does not occur cascading effects because member nodes cannot override existing CHs. Topology 1. - : link between two nodes Yi, Kwon and Gerla Expires May 14, 2002 [Page 5]
I-D PC 14 November 2001 (1) (3)-4-(5)-6-(7)-8 (1), (3), (5), (7): CHs 4, 6, 8: Members Topology 2. (1)-3-(4)-5-(6)-7-(8) (1), (4), (6), (8): CHs 3, 5, 7: Members Topology 3. (1)-3-4-(5)-6-(7)-8 (1), (5), (7): CHs 3, 4, 6, 8: Members Figure 1. An Example of Cascading Effect For instance in Figure 1, let's assume that the "Lowest ID" clustering algorithm [7] is used and node "1" moves toward node "3" and becomes a neighbor node of node "3". Then, node "3" should give up the role of CH since node "1" has the lower node ID than node "3". If node "3" gives up the role of CH, then cascading changes will occur. Eventually, the final result will be Topology 2 in Figure 1. In contrast, PC will stop the state change of node "4" since node "4" already knows the existence of CH "5". Instead of changing of the role, node "3" and "4" become distributed gateway (DIST_GW) nodes. Therefore, PC results Topology 3 in Figure 1. gateway node A gateway node of a cluster is one of members and a CH uses this node to communicate with adjacent CHs. Finding enough but minimal number of gateways in a distributed manner is a well- known NP problem. This problem can be induced to the question how a node (CH) chooses optimal dominant set of nodes that cover all nodes that are within two-hops away from the node. Many literatures [4, 5] have provided heuristics for that problem. Those solutions, however, require periodic exchanges of neighbor list. And the control overhead is tightly coupled with the degree of neighbors. Passive Clustering, on the other hand, suggests another heuristic that does not need periodic neighbor exchanges in Chapter 5.4. ORDINARY node Yi, Kwon and Gerla Expires May 14, 2002 [Page 6]
I-D PC 14 November 2001 A member that is not a gateway node is an ORDINARY node. node 'A' is known to node 'B' A node 'A' is known to node 'B' if node 'B' has directly (not through multi-hop nodes) overheard packets from 'A'. 3. The Assumptions and Requirements This section lists the assumptions and requirements of the underlying networks of Passive Clustering. Each MANET node that runs PC is equipped with one wireless media. Each MANET node uses the omni-directional antenna. Each packet that a node sends is broadcast into the region of its radio coverage. Passive Clustering (PC) requires overhearing, intercepting, and manipulating every IP packet. Furthermore, if there is a link between two nodes, then the link is assumed to be "bi-directional". And the maximum radio range of each node is required to be "homogeneous". 4. Basic Description and Conceptual Data Structures The key idea of PC is to exploit on-going data packets and piggyback "cluster-related" information such as the state of a node in a clus- ter and an IP address of a node. Each node participates in clustering by overhearing messages from neighbor nodes and piggybacking own cluster information to outgoing packets. To attach cluster informa- tion, PC adds only 8 or 16 bytes (based on IP V4) to each packet using IP option field. A node does not initiate clustering unless it has outgoing or incom- ing packets. A node before joining a cluster is called the INITIAL node. With incoming or outgoing packets, a node can participate in clusters as a member or a CH based on the states of neighbor nodes. When a node has a packet to send, this node can declare as a CH or a gateway node by stamping its state to the packet. After a successful transmission of that claim packet, every node in this sender's radio coverage can learn the presence of the CH or the gateway node through overhearing that packet. Neighbor nodes of the CH cannot declare as a CH since only one CH is allowed in one cluster, but neighbor nodes of a gateway node may declare as another gateway node based on "Gateway Selection Heuristic" (chapter 5.4). Yi, Kwon and Gerla Expires May 14, 2002 [Page 7]
I-D PC 14 November 2001 To prevent isolated clusters, which consist of only one node, and improve the connectivity of clusters, a node can pronounce as a CH only after it has overheard packets from other nodes. In other words, an INITIAL node cannot declare as the CH without receiving packets from others. A node is called a "candidate CH" (CH_READY node) if it knows more than one neighbor node that is not a CH. Upon promiscuous reception of each packet from a neighbor node, every neighbor node of the sender adjusts its state. An INITIAL node can be a candidate CH if the sender is the non-CH node. Otherwise, this node becomes a member of the new cluster that the CH (sender of the packet) creates. If a CH has heard from another CH, then they compete each other based on the "Lowest ID Competition" (chapter 5.5). When a node fails to keep the role of CH, it sends out a "CH Give-Up Message" (chapter 5.5.1) to notify neighbors of the role change. A member node can be a gateway node or ORDINARY node based on "Gate- way Selection Heuristic" (chapter 5.4). This heuristic reduces the number of gateway nodes in an efficient way and supports distributed gateway scheme. In brief, only one gateway node is allowed for each pair of CHs and a CH should have more than two gateway nodes. Chapter 5.4.1 describes how to decide the role of each member. PC maintains clusters using implicit timeout scheme. Without exchang- ing neighbor information, a node 'A' assumes that another node 'B' is out of its locality if 'B' did not send out any message longer than timeout duration (CLUSTER_TIME_OUT). If a member node detects no live CH (does not belong to any cluster), then it becomes the INITIAL node and starts clustering from the beginning. The implicit timeout mecha- nism, with reasonable offered load, works efficiently to detect dynamic topology changes. 4.1. The States of Each Node There are 2 internal and 5 external states: CH_READY and GW_READY are internal states, and INITIAL_NODE, CLUSTER_HEAD, GW_NODE, DIST_GW, and ORDINARY_NODE are external states. Note that a node uses the internal states to represent the tentative role (candidate CH or can- didate gateway node) of nodes. The internal states should be changed to one of external states at sending a packet, so the internal state of a node is not exposed to neighbor nodes. The description of each state is as follows. 1. INITIAL_NODE When a node is initialized (wakes up), the state of a node is Yi, Kwon and Gerla Expires May 14, 2002 [Page 8]
I-D PC 14 November 2001 set to the INITIAL_NODE. The state of a node that does not belong to any cluster (no CH has not send out messages for CLUS- TER_TIME_OUT) must be the INITIAL_NODE. A node is called an INI- TIAL node if the state of this node is the INITIAL_NODE. 2. CLUSTER_HEAD The state of a node is the CLUSTER_HEAD when a node is the CLUS- TER HEAD. 3. FULL_GW The state of a node is the FULL_GW when a node is the FULL_GW node. A FULL_GW node should be a member of more than two clus- ters at the same time so that this node can be an intermediate node between two cluster heads. When a FULL_GW node sends out a packet, it determines two CHs that this node connects and announces the node IDs of two CHs. 4. ORDINARY_NODE The state of an ORDINARY node. 5. GW_READY The GW_READY is the internal state of a potential gateway (FULL_GW or DIST_GW) node before this node sends out a packet. To guarantee that a node who has declared earlier wins, a poten- tial gateway keeps internal state until it actually pronounces the role. This node is called GW_READY node hereafter. A GW_READY node can change its state to ORDINARY_NODE if it has known (overheard packets from) enough neighbor gateway nodes. When a DIST_GW node sends out a packet, it announces the node ID of primary CH and remote CH to which it knows a path through another gateway. 6. CH_READY The internal state of a potential CLUSTER HEAD before this node has an outgoing packet. To guarantee that a node who has declared earlier wins, a potential gateway keeps internal state until it actually pronounces the role. This node is called CH_READY node hereafter. A CH_READY node cannot declare as a CH if it has received a packet from another CH. 7. DIST_GW The state of a distributed gateway node is DIST_GW. A DIST_GW Yi, Kwon and Gerla Expires May 14, 2002 [Page 9]
I-D PC 14 November 2001 node is a gateway node that connects two clusters. It, however, may not be directly reachable from one of two cluster heads of two clusters (there are two intermediate gateway nodes between two cluster heads). A GW_READY node determines its final state just before it sends out a packet. This node could be an ORDINARY, FULL_GW, or DIST_GW node (chapter 5.4.3.2). Each internal state should be determined to any external state at sending a packet and the external state is stamped at the packet. Besides, each member may change its state upon receiv- ing a packet from another node (chapter 5.1.1). 4.2. The Data Structures Every node maintains 4 different lists: the list of CH (CLUSTER HEAD), GW (Gateway (GW or DIST_GW) node), INITIAL (INITIAL node) and NEIGHBOR (ORDINARY node). Each list is updated whenever a node has received a packet from another node. 1. A list of CH Whenever a node has received a packet from CLUSTER HEAD, it updates or adds up information of that node to the list of CH. The entry contains: - NODE_ID: the node ID of the CH - LAST_RECV_TIME: the current time when this node has received a packet from the CH The global variable no_of_CH represents the number of valid ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries of the list of CH. 2. A list of GW This is a list of gateway nodes from which this node has heard. The entry contains: - NODE_ID: the node ID of the gateway node - LAST_RECV_TIME: the current time when this node has received this packet from the gateway node - STATE: the cluster state of the gateway node Yi, Kwon and Gerla Expires May 14, 2002 [Page 10]
I-D PC 14 November 2001 (DIST_GW or FULL_GW) - CH_ID_1: the node ID of first CH among the pair of CHs that the gateway node has announced - CH_ID_2: the node ID of second CH among the pair of CHs that the gateway node has announced The global variable no_of_GW represents the number of valid ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries of the list of GW. 3. A list of INITIAL Whenever a node has received a packet from an INITIAL node, it updates or adds up information of that node to the list of INI- TIAL. The entry contains: - NODE_ID: the node ID of the INITIAL node - LAST_RECV_TIME: the current time when this node has received a packet from the INITIAL node The global variable no_of_IN represents the number of valid ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries of the list of INITIAL. 4. A list of NEIGHBOR This is a list of ORDINARY nodes. The entry contains: - NODE_ID: the node ID of the ORDINARY node - LAST_RECV_TIME: the current time when this node has received a packet from the ORDINARY node - PRI_CH_ID: the node ID of primary CH. This field is optionally used (e.g., when an ORDINARY node sends "HELLO" messages, the scout message, etc.) The global variable no_of_ON represents the number of valid ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries of the list of NEIGHBOR. Note that PC uses the "implicit" timeout mechanism, where no explicit Yi, Kwon and Gerla Expires May 14, 2002 [Page 11]
I-D PC 14 November 2001 "timer" expires. Whenever a packet comes in, all out-of-date (current time - LAST_RECV_TIME > CLUSTER_TIME_OUT) entries must be removed from lists. 4.3. The Format of PC Header in IP Option Field PC uses the IP option field to piggyback the information of clusters. The basic format of IP option of PC is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | STA |G|H| RESERVED | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Node ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Options | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ STA The field is used to specify the state of each node. G CH give-up field. This field is used when a CH gives up its role and sends a "CH Give-Up Message" (chapter 5.5.1) to inform neighbors of the change. A node set this field as "TRUE" with "CH Give-Up Message. Otherwise, the default value is "FALSE". H If this message is a "HELLO" message, the sender set this field as "TRUE". Otherwise, the default value is "FALSE". RESERVED Reserved area. Must be set to "0"(zero). Yi, Kwon and Gerla Expires May 14, 2002 [Page 12]
I-D PC 14 November 2001 Node ID The IP address of the sender node. This may be different to the source address in the IP header. (based on IP V4) Options This field is used for a gateway node to announce two CHs. Also, when a node sends "HELLO" message, this option field may contain the node ID of primary CH of the sender node. If the sender belongs to only one cluster, let's say the node ID of CH of that cluster is "CH1", then the primary CH is CH1. Otherwise, the sender can choose randomly one primary CH among all CHs that are known to the sender. The format of options used by a "FULL_GW" or "DIST_GW" node is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CH_ID_1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CH_ID_2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ CH_ID_1 The IP address of first CLUSTER HEAD CH_ID_2 The IP address of second CLUSTER HEAD If this node is a FULL_GW node, then the order of "CH_ID_1" and "CH_ID_2" can be reversed. If this node is a DIST_GW node, then "CH_ID_1" should be the node ID of the primary CH of this node and "CH_ID_2" should be the node ID of remote CH to which this node relays messages from the primary CH. 5. The Detailed Algorithm This section describes the detail algorithm of PC. 5.1. Packet Processing Yi, Kwon and Gerla Expires May 14, 2002 [Page 13]
I-D PC 14 November 2001 All functions related to clustering are called only when a packet comes in or out. 5.1.1. Incoming packet Processing PC requires "promiscuous" packet reception. Upon receiving a packet, PC extracts IP option field that is used for PC protocol. If there is no IP option in the packet, then PC just bypass that packet to the proper application. A node with INITIAL_NODE state changes its state to CH_READY only when it has received a packet from the non-CH node. A cluster member decides the state following "Gateway Selection Heuristic" (chapter 5.4). A CH competes with the other CH when a packet has arrived from another CH based on "The Lowest ID Competition" rule (chapter 5.5). A state transition by incoming packet (RECV_MSG) is as follows: 1. If RECV_MSG.STA == CLUSTER_HEAD then If my state == CLUSTER_HEAD and my node ID > RECV_MSG.ID then send CH Give-Up Message to member nodes (chapter 5.5.1) Else If my state == CLUSTER_HEAD and my node ID < RECV_MSG.ID then RETURN // Do nothing Add ClusterHead (chapter 5.3.1) // Add this information to the list of CH and adjust its state //as a member of the cluster 2. Else If RECV_MSG.STA == FULL_GW or RECV_MSG.STA == DIST_GW then Add Gateway (chapter 5.3.2) // Add the information to the list of GW and adjust its state // if enough gateway nodes found, then this node can be an // ORDINARY node 3. Else If RECV_MSG.STA == INITIAL_NODE then Add Initial (chapter 5.3.3) Yi, Kwon and Gerla Expires May 14, 2002 [Page 14]
I-D PC 14 November 2001 // Add the information to the list of INITIAL // and adjust its state 4. Else If RECV_MSG.STA == ORDINARY_NODE then Add Neighbor (chapter 5.3.4) // Add the information to the list of NEIGHBOR // and adjust its state If my state == INITIAL_NODE and RECV_MSG.STA != CLUSTER_HEAD then change my state to CH_READY 5.1.2. Outgoing Packet Processing When a packet is sent from the "Network" layer to the "MAC" layer, PC changes all internal states (CH_READY or GW_READY) to external states and adds IP option before it enqueues a packet to the data queue. PC fills up IP option with the state of clusters (STA) and all other field in IP option of PC as follows: STA: my state (after changing the internal state to the external state) G: FALSE (TRUE when a node sends out "CH Give-Up Message") H: FALSE (TRUE when a node sends out "HELLO" messages) Node ID: my node ID If this node is a gateway node (FULL_GW or DIST_GW node) CH_ID_1: my_CH_ID_1 (the node ID of first CH for this node) CH_ID_2: my_CH_ID_2 (the node ID of second CH for this node) or my_REMOTE_CH (the node ID of remote CH for DIST_GW) 5.1.2.1. First Declaration Wins Rule How stable and quick the clustering mechanism converges is a very important feature that a clustering algorithm has to provide. "First Declaration Wins" rule improves, compared with other mechanisms, the clustering stability, speeds up converging time, and avoids the sta- tionary requirement for neighbor learning and clustering phase. The working mechanism of this rule is as follows: When a candidate CH (CH_READY node) has packets to send, it change its state to CLUSTER_HEAD and stamps cluster information to the out- going packets that claims the role of CH. After a successful transmission of that claim packet, every node in the sender's radio Yi, Kwon and Gerla Expires May 14, 2002 [Page 15]
I-D PC 14 November 2001 coverage can learn the presence of the CH through overhearing that packet. A declaration of the role as a gateway node follows the same rule, "First Declaration Wins", but there is no explicit role give-up mes- sage. 1. CLUSTER HEAD A node whose state is CH_READY should change its state to CLUS- TER_HEAD. 2. gateway (FULL_GW or DIST_GW) node A node whose state is GW_READY should change its state to FULL_GW, DIST_GW or ORDINARY_NODE (chapter 5.4.3.1). 5.2. Management Each node changes its state if necessary only when it has outgoing packets or incoming packets. 5.3. The Functions 5.3.1. Add ClusterHead Add information of CLUSTER HEAD to a list of CH and delete old entries from the list of CH (old entries: (current time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). A DIST_GW node changes its state to GW_READY if the no_of_CH is increased Check Gateway (chapter 5.3.6) // Check the number of gateway nodes and adjust state based on // gateway selection heuristic An INITIAL node changes its state to GW_READY or ORDINARY_NODE in "ReCalculate Member State" (chapter 5.4.3.2) called by Check Gate- way function Check Initial (chapter 5.3.7) // Check the number of INITIAL nodes Check Neighbor (chapter 5.3.8) Yi, Kwon and Gerla Expires May 14, 2002 [Page 16]
I-D PC 14 November 2001 // Check the number of ORDINARY nodes 5.3.2. Add Gateway Add FULL_GW or DIST_GW node's information to a list of GW and delete old entries from the list of GW. A FULL_GW node may change its state to GW_READY or ORDINARY_NODE, if new gateway has announced the same pair of CHs and the node ID of new gateway is less than own node ID. If this node found another pair of CHs that is not announced by another FULL_GW node, then it simply changes the pair of CHs (change my_CH_ID_1 && my_CH_ID_2 -- contains two node IDs of announced CH pair). Otherwise it changes its state to GW_READY. Check ClusterHead (chapter 5.3.5) // Check the number of CHs and adjust its state // if no neighbor CH (no_of_CH == 0) , then becomes INITIAL node. Check Initial (chapter 5.3.7) Check Neighbor (chapter 5.3.8) ReCalculate Member State (chapter 5.4.3.2) // Adjust its state based on Gateway Selection Heuristic // An ORINDARY node may change its state to GW_READY // An GW_READY node may change its state to ORINARY_NODE 5.3.3. Add Initial Add INITIAL node's information to a list of INITIAL node and delete old entries from the list of INITIAL. Check ClusterHead (chapter 5.3.5) Check Gateway (chapter 5.3.6) Check Neighbor (chapter 5.3.8) 5.3.4. Add Neighbor Add ORDINARY node's information to a list of NEIGHBOR and delete old entries from the list of NEIGHBOR. Check ClusterHead (chapter 5.3.5) Yi, Kwon and Gerla Expires May 14, 2002 [Page 17]
I-D PC 14 November 2001 Check Gateway (chapter 5.3.6) Check Initial (chapter 5.3.7) 5.3.5. Check ClusterHead Delete old entries (OLD_CH) from the list of CH (old entries: (cur- rent time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). Any member node changes its state to INITIAL_NODE if no_of_CH becomes "0" (zero) A gateway node changes its state to GW_READY if OLD_CH.NODE_ID equals to my_CH_ID_1 or my_CH_ID_2. 5.3.6. Check Gateway Delete old entries from the list of GW (old entries: (current time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). ReCalculate Member State (chapter 5.4.3.2) 5.3.7. Check Initial Delete old entries from the list of INITIAL (old entries: (current time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). 5.3.8. Check Neighbor Delete old entries from the list of NEIGHBOR (old entries: (current time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). 5.4. Gateway Selection Heuristic A gateway node is a bridge node between two clusters. A node that is reachable from two CHs may declare its role as a FULL_GW node only if this node has not heard from another FULL_GW node that had announced the same pair of CHs. A node is a member of only one cluster can declare as a DIST_GW node to improve the connectivity of the network. This scheme guarantees that one cluster always has at least two gateway nodes. Yi, Kwon and Gerla Expires May 14, 2002 [Page 18]
I-D PC 14 November 2001 The state of a node is re-calculated and updated whenever this node overhears an incoming packet. 5.4.1. One Gateway Node per Each Pair of CLUSTER HEADs (CHs) This scheme eventually allows only one FULL_GW node for each pair of CHs. If two nodes declare concurrently as FULL_GW nodes with announc- ing the same pair of CHs, then a node that has the higher ID may give up FULL_GW role or change its pair of CHs. A FULL_GW announces two IDs of CLUSTER HEAD when it has an outgoing packet. For example in Figure 2, (A) means that the node ID of that node is "A" and [B,C] means that the node ID of two CHs that a FULL_GW node has announced are "B" and "C". The connectivity matrix between two nodes is on the right of figure. GW: a FULL_GW node, NODE: a GW_READY node 1 2 3 4 5 6 7 GW (1)[4,7] CH (4) GW(3)[4,6] 1 1 1 0 1 1 0 1 NODE (5) 2 1 1 1 1 1 1 1 CH (7) NODE (2) CH (6) 3 0 1 1 1 1 1 0 4 1 1 1 1 1 0 0 5 1 1 1 1 1 1 1 6 0 1 1 0 1 1 0 7 1 1 0 0 1 0 1 Figure 2. An Example of FULL_GW Node In this case, when NODE (5) has an outgoing packet, NODE (5) can declare as FULL_GW for the pair of (CH (7), CH (6)) since there is no FULL_GW for ((CH (7), CH (6)). If NODE (2) and NODE (5) declare as FULL_GW nodes at the same time, then NODE (5) will give up the FULL_GW role and become an ORDINARY NODE after it has received a packet from NODE (2) because it has larger ID than NODE (2) and there is no remained pair that is not pronounced by another FULL_GW node. If there is no GW (1), then NODE (5) can change the pair of CHs to (CH (7), CH (4)) instead of (CH (7), CH (6)) when it has heard from NODE (2). A member node that has heard from CHs changes its state to ORDINARY_NODE when this node can hear from more than two CHs at the Yi, Kwon and Gerla Expires May 14, 2002 [Page 19]
I-D PC 14 November 2001 same time and there is no left pair of CHs that is not announced by other FULL_GW nodes. 5.4.2. The Distributed Gateway Selection Mechanism We employ a heuristic to provide the distributed selection mechanism. If a node has heard from only one CH and more than three gateway nodes, then this node can be an ORDINARY node. And if a node that is a member of only one cluster "C1" and it has overheard from more than two DIST_GW nodes that are also the member of the same cluster C1, then this node can be an ORDINARY node. Otherwise, this node changes its state to GW_READY to declare as the DIST_GW node. (=== : bi-directional link) CH 1 ===\\ // \\ GW 4 [1,5] === CH 5 // \\ // DIST_GW 2 === NODE 3 Figure 3. An Example of a DIST_GW Node Figure 3 shows an example of a DIST_GW node. The state of node "3" should be GW_READY since only two gateway nodes (GW 4 and DIST_GW 2) and one CH (CH 1) are known to this node. At sending a packet, node "3" will be a DIST_GW node. If a DIST_GW node has received a packet from another DIST_GW that has announced the same pair of primary CH and remote CH, then the node with lower ID wins. The node with higher ID changes its state to GW_READY. If an ORDINARY node receives a packet from DIST_GW node whose primary CH is unknown to this node, then this node may change its state to GW_READY (chapter 5.4.3.2). 5.4.3. The Procedure 5.4.3.1. The Processing of Outgoing Packets for a Member Node At sending a packet "MSG", a node "P" with the state GW_READY changes its state to ORDINARY_NODE, FULL_GW or DIST_GW as follows: (1) no_of_CH >= 2 Yi, Kwon and Gerla Expires May 14, 2002 [Page 20]
I-D PC 14 November 2001 If this node finds a pair of CHs that has not announced, then this node becomes a FULL_GW node. If there is no gateway node that con- nects one of clusters to which this node belongs to another cluster that a DIST_GW has announced, then this node becomes the DIST_GW node. Otherwise, it becomes the ORDINARY node. The pseudo code is as follows: For each pair of CHs known to P (ch1, ch2) For each FULL_GW node "G" known to P If G has announced the same pair of CH break; Else go to next FULL_GW node If no FOUND G then P changes its state to FULL_GW and MSG.CH_ID_1 = ch1 & MSG.CH_ID_2 = ch2 my_CH_ID_1 = ch1 & my_CH_ID_2 = ch2 RETURN Else go to next pair If all pairs are announced then For each DIST_GW node "DG" known to P If DG.CH_ID_1 is equal to one of CHs known to P then go to next DIST_GW node Else For each gateway node "G" except for DG If G.STATE == DIST_GW && G.CH_ID_2 == DG.CH_ID_2 then //there is a DIST_GW node that reaches remote CH break; Else If G.STATE == FULL_GW && G.CH_ID_1 (or 2) == DG.CH_ID_1 then break; Else go to next gateway node Yi, Kwon and Gerla Expires May 14, 2002 [Page 21]
I-D PC 14 November 2001 If no FOUND G then P changes its state to DIST_GW and MSG.CH_ID_1 = the node ID of primary CH MSG.CH_ID_2 = DG.CH_ID_1 my_CH_ID_1 = the node ID of primary CH my_REMOTE_CH = DG.CH_ID_1 RETURN Else go to next DIST_GW node If the state ID of P is GW_READY then P changes its state to ORDINARY_NODE (2) no_of_CH == 1 and the primary CH "CH1" (the cluster {CH1}) If there is no gateway node that connects CH1 to another CH (CH2) that a DIST_GW has announced, then this node becomes a DIST_GW node. If there is no known DIST_GW node in the same cluster {CH1}, then it becomes DIST_GW node. Otherwise, it becomes an ORDINARY node. The pseudo code is as follows: For each DIST_GW node "DG" If DG.CH_ID_1 == CH1 then go to next DIST_GW node Else For each gateway node "G" If G.STATE== DIST_GW && G.CH_ID_1 == CH1 && G.CH_ID_2 == DG.CH_ID_1 then go to next DIST_GW node Else If G.STATE== FULL_GW && the pair of CHs of G is the same pair to (CH1, DG.CH_ID_1) then go to next DIST_GW node If no FOUND gateway node then P changes its state to DIST_GW and MSG.CH_ID_1 = CH1 MSG.CH_ID_2 = DG.CH_ID_1 my_CH_ID_1 = CH1 my_REMOTE_CH = DG.CH_ID_1 RETURN If the state of P is GW_READY then Yi, Kwon and Gerla Expires May 14, 2002 [Page 22]
I-D PC 14 November 2001 For each DIST_GW node "DG" known to P If DG.CH_ID_1 == CH1 then P changes its state to ORDINARY_NODE RETURN Else go to next DIST_GW node If the state of P is GW_READY then P changes its state to DIST_GW and MSG.CH_ID_1 = CH1 MSG.CH_ID_2 = UNKNOWN my_CH_ID_1 = CH1 my_REMOTE_CH = UNKNOWN Note that an ORDINARY node changes its state to GW_READY when it receives a packet from another node and detects the shortage of gateway nodes (chapter 5.4.3.2). Therefore, a CH always has more than two relay nodes. 5.4.3.2. ReCalculate Member State An ORDINARY node may change its state to GW_READY if it detects the shortage of gateway nodes. A node with GW_READY state may change its state to ORDINARY_NODE if it detects the enough gateway nodes if there are more than two mem- bers. A member "P" changes its state as follows: If the state of P is neither FULL_GW nor DIST_GW then For each DIST_GW node "DG" For each gateway node "G" except for DG If G.STATE == DIST_GW && G.CH_ID_2 == DG.CH_ID_1 then //there is a DIST_GW node that reaches remote CH break; Else If G.STATE == FULL_GW && G.CH_ID_1 (or 2) == DG.CH_ID_1 then break; Else go to next gateway node If no FOUND G then Yi, Kwon and Gerla Expires May 14, 2002 [Page 23]
I-D PC 14 November 2001 P changes its state to GW_READY and RETURN If no_of_CH >= 2 For each pair of CHs known to P (ch1, ch2) For each FULL_GW node "G" known to P If G has announced the same pair of CH break; Else go to next FULL_GW node If no FOUND G then P changes its state to GW_READY and RETURN Else If no_of_CH == 1 ("CH1": the node ID of this CH) then If no_of_GW >= 3 then P changes its state to ORDINARY_NODE and RETURN Else if no_of_GW == 2 then For each gateway node "G" If G.STATE != DIST_GW || G.CH_ID_1 != CH1 then P changes its state to GW_READY and RETURN Else go to next gateway node P changes its state to ORDINARY_NODE and RETURN Else P changes its state to GW_READY and RETURN 5.5. The Lowest ID Competition The conflict of declarations of CLUSTER HEAD can happen due to the dynamic change of topology and packet delay. To resolve those con- flicts, a node that has the lowest ID among conflicted CHs kills other declaration. If a CLUSTER_HEAD has received a packet from the CH that has the lower ID than this node, then it gives up its role, changes its state following the Gateway Selection Heuristic (chapter 5.4), and sends out a "CH Give-Up Message". If two gateway nodes have announced the same pair of CHs, then the node with higher node ID should yield to the other. Yi, Kwon and Gerla Expires May 14, 2002 [Page 24]
I-D PC 14 November 2001 5.5.1. The CH Give-Up Message After one CH gives up the CLUSTER HEAD role and has no outgoing packet, then it send extra "CH Give-Up Message" which set "G" as "TRUE" in the IP option. 5.6. The Timeout Scheme Except "HELLO" message (chapter 5.7), there is no explicit timeout scheme. But every list is maintained by CLUSTER_TIME_OUT value. An entry that has not been updated for CLUSTER_TIME_OUT must be removed from a list. 5.7. The "HELLO" message Each node may optionally send "HELLO" message at each CLUS- TER_TIME_OUT interval. Because our algorithm constructs the clusters in a passive way, the outcome of clusters depends on the traffic pat- tern. Therefore, it does not guarantee fully connected clusters at some cases. Even though the probability to lose the partial connec- tivity is very low, the make-up mechanism to guarantee the full con- nectivity is necessary at certain points. The "HELLO" scheme could be optionally used to support full connectivity (chapter 8.2 (1)). 6. The Applicability PC can be used for an efficient flooding mechanism with allowing only non-ORDINARY nodes (CH, gateway nodes and INITIAL nodes) to be for- warding nodes. Since the ratio of ORDINARY nodes increases as the density of networks raises, PC works the more effectively as the net- work becomes denser. Many schemes such as routing protocols, service discovery or multi- cast can get benefits by employing PC because they use a flooding as the basic communication mechanism. This document, however, especially goes over the applicability to reactive routing protocols. 6.1. The Applicability to On-demand Routing Protocols On-demand routing protocols have two phases (the route request and route reply phase) to setup a path. The incremental flooding and uni- cast are used for the route query and route reply phase respectively. The cluster architecture by PC can support a platform of efficient in Yi, Kwon and Gerla Expires May 14, 2002 [Page 25]
I-D PC 14 November 2001 the route request phase. Only non-ORDINARY nodes participate in flooding of route request phase and, as a result, are intermediate nodes of any path. Note that, in the complete cluster architecture, two nodes can be reached each other through CHs and gateway nodes. For example in Figure 4, node "E", "F", "B" and "G" will stop for- warding route queries since they are ORDINARY nodes. Eventually, the route reply will go through only non-ORDINARY nodes. (E) (F) +-+ + +-+ <- : route reply src <-- |A| <-- /C\ <--|D| <--dest A, D : CHs +-+ +-+ +-+ C : gateway nodes (B) (G) B, E, F, G: ORDINARY nodes Figure 4. An Example of the Efficient Flooding 6.2. Protocol Characteristics * Does this protocol provide support for unidirectional links? (if so, how?) No. Bi-directional links are required. * Does the protocol require the use of tunneling? (if so, how?) No. * Does the protocol require using some form of source routing? (if so, how?) No. However, source routing could be used as a basic routing pro- tocol with passive clustering. * Does this protocol require the use of periodic messaging? (if so, how?) No. However, periodic HELLO messages could be used optionally to guarantee a fully-connected cluster architecture. * Does this protocol require the use of reliable or sequenced packet delivery? (if so, how?) No. However, the FIFO queue is required. Yi, Kwon and Gerla Expires May 14, 2002 [Page 26]
I-D PC 14 November 2001 * Does the protocol require link or neighbor sensing (if so, how?) No. However, neighbor sensing helps the clustering connectivity. * Does the protocol have dependence on a central entity? (if so, how?) No. All the functions are achieved in a distributed manner. * Does the protocol function reactively? (if so, how?) Yes. The formation of clusters is deferred until there is on-going data traffic. * Does the protocol function proactively? (if so, how?) No. * Does the protocol provide loop-free functions? (if so, how?) Yes. Passive clustering does not generate any packets that possi- bly occur a loop. * Does the protocol provide for sleep period operation? (if so, how?) No. In current version, no sleep mode is supported. * Does the protocol provide some form of security? (if so, how?) No. 7. Suggested Parameters CLUSTER_TIME_OUT 2 seconds 8. The Discussion and Implementation Consideration 8.1. Problems with a Critical Path Loss This section discusses some of the problems that we have encountered during the design of PC. In particular, they are related to the issue of the network connectivity. * The Connectivity Problem Yi, Kwon and Gerla Expires May 14, 2002 [Page 27]
I-D PC 14 November 2001 Because PC constructs the cluster architecture in a passive way, it is possible to lose some critical paths. Figure 5 shows an example. (=== : bi-directional link) DIST_GW 1 ====== CH 2 ======= DIST_GW 3 \\ // \\ || GW 7 == CH 8 // \\ || // DIST_GW 4 ===== ORDINARY 6 \\ \\ NODE 5 Figure 5. An Example of a Critical Path Loss In Figure 5, an ORDINARY node "6" has a critical path to node "5" and node "5" doesn't have outgoing packets. In this case, node "6" has no chance to get the knowledge from node "5", so node "6" will not forward flooding packets to node "5". As a result, node "5" can't hear a message from the cluster with CH "2". 8.2. The Possible Solutions There are several possible solutions as follows: (1) The "HELLO" messages The periodic "HELLO" messages solve this problem. If node "6" sends "HELLO" message, then node "5" changes its state to CH_READY and declares as a CH when node "5" sends out a "HELLO" message. Finally, node "6" becomes a FULL_GW node which connects CH "2" and "5". All ORDINARY nodes announce the node ID of primary CH. Node "6" announces CH "2" when this node sends out "HELLO" messages. Let's assume that NODE "5" is the ORDINARY node and the primary CH of node "5" is node "9". After exchanges of the "HELLO" messages, node "5" and "6" detect that there is no gateway node that connects CH "2" and "9" (chapter 5.4.3.2). Therefore, node "5" and "6" change their states to GW_READY to become DIST_GW nodes. The periodic "HELLO" message avoids the connectivity problem, but it occurs extra overhead for exchanging packets. Yi, Kwon and Gerla Expires May 14, 2002 [Page 28]
I-D PC 14 November 2001 (2) An ORDINARY node should send at least one outgoing packet with active declaration of CH. An ORDINARY node should send out at least one packet after being the ORDINARY node. When an ORDINARY node sends out a packet, it stamps the node ID of primary CH to the packet. And if an INITIAL node has heard from another ORDINARY node, then it claims as a CH in an active way (sends explicit packet to declare) instead of a passive way. In the Figure 5, if node "5" has heard from node "6", then node "5" will declare actively as a CH. Then, node "6" changes its state to FULL_GW after it has received a declaration packet from CH "5". Suppose, node "5" is an ORDINARY node and has heard from node "6", then node "5" becomes DIST_GW node since there is no gateway node to connect two clusters. This solution, however, has a problem with the node mobility and new incoming nodes. For example, if node "5" wakes up after node "6" finally becomes the ORDINARY node, then the critical path from node "5" to "6" is still lost. (3) The scout messages An ORDINARY node sets the BIRTH_TIME to the current time when it changes its state to the ORDINARY_NODE. And, it sends out a "scout" packet to catch un-covered neighbors after T seconds from the BIRTH_TIME. A node that has received the scout packet reacts the same way to (2). Still, this solution has the same problem to (2). But, ORDINARY nodes can send out "scout" messages periodically to prevent men- tioned problems. 8.3. Some Comments The problem of necessary gateway selection can be induced to the well-known set cover problem where a minimal set of gateway nodes that cover all two hops away neighbors. This problem is a NP complete problem with depending upon the quasi-stationary assumption to get the solution. Based on the quasi-stationary assumption, a set of necessary gateway nodes can be elected through the exchanges of neighbor lists or pre- known topology. However, the dynamic topology of the ad hoc networks challenges the Yi, Kwon and Gerla Expires May 14, 2002 [Page 29]
I-D PC 14 November 2001 basic assumption. In other words, without Oracle, the election algo- rithm to choose the set of necessary gateway nodes should be per- formed whenever the topology changes. This may cost huge overhead such as periodic exchanges of neighbor list, extra control packets to elect nodes, or extensive "HELLO" messages. Passive clustering, on the other hand, provides fully distributed, practical and very cheap in the sense of line overhead gateway selec- tion mechanism. In spite of possible cases (e.g., Figure 5) that lose critical paths, the extensive simulation studies show that the probability of such cases is extremely low in the fairly dense and loaded networks. Therefore, PC can be used as a practical clustering mechanism that provides well-partitioned groups regardless of the size, density, mobility, and the load status of the network. 9. Authors' Addresses Yunjung Yi UCLA 3771 Boelter Hall Los Angeles, CA 90095 EMail: yjyi@cs.ucla.edu Taek Jin Kwon Telcordia Technologies, Applied Research NVC3X-317 331 Newman Springs Rd. Red Bank, NJ 07701 EMail: tkwon@research.telcordia.com Mario Gerla UCLA Computer Science Department 3564 Boelter Hall Los Angeles, CA 90095 EMail: gerla@cs.ucla.edu Yi, Kwon and Gerla Expires May 14, 2002 [Page 30]
I-D PC 14 November 2001 References 1. T.J. Kwon and M. Gerla, Clustering with Power Control, Atlantic City, NJ (Nov. 1999). Proceedings of IEEE MILCOM'99. 2. C.R. Lin and M. Gerla, Adaptive Clustering for Mobile Wireless Net- works (Sep. 1997). IEEE Journal on Selected Areas in Communica- tions, Vol. 15, No. 7, pp. 1265-1275. 3. J.T. Tsai and M. Gerla, Multicluster, Mobile, Multimedia Radio Net- work (1995). ACM/Kluwer Journal of Wireless Networks, Vol.1, No.3, pp.255-65. 4. Amir Qayyum, Laurent Viennot, Anis Laouiti, "Multipoint relaying: An efficient technique for flooding in mobile wireless networks," INRIA report (March, 2000). 5. H.Lim and C. Kim,, "Flooding in wireless ad hoc networks," IEEE computer communications (2000). 6. Scott Bradner, "Key words for use in RFCs to indicate requirement levels," IETF RFC 2119 (March , 1997). 7. M. Gerla and J. Tsai, "Multicluster, mobile, multimedia radio net- works," ACM Baltzer Journal of Wireless Networks, Vol. 1. No. 3. (1995). Yi, Kwon and Gerla Expires May 14, 2002 [Page 31]