idnits 2.17.1 draft-ietf-manet-cbrp-spec-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-25) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 12 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 13 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 115 has weird spacing: '...cluster withi...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (August 1998) is 9385 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' == Outdated reference: A later version (-01) exists of draft-ietf-manet-term-00 -- Possible downref: Normative reference to a draft: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' ** Downref: Normative reference to an Historic RFC: RFC 1058 (ref. '6') -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' Summary: 11 errors (**), 0 flaws (~~), 5 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Mingliang Jiang 3 draft-ietf-manet-cbrp-spec-00.txt National University of S'pore 4 Jinyang Li 5 National University of S'pore 6 Yong Chiang Tay 7 National University of S'pore 8 August 1998 10 Cluster Based Routing Protocol(CBRP) Functional Specification 12 Status of this Memo 14 This document is an Internet-Draft. Internet-Drafts are working 15 documents of the Internet Engineering Task Force (IETF), its areas, 16 and its working groups. Note that other groups may also distribute 17 working documents as Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet- Drafts as reference 22 material or to cite them other than as "work in progress." 24 To view the entire list of current Internet-Drafts, please check the 25 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 26 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 27 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific 28 Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 30 Abstract 32 Cluster Based Routing Protocol (CBRP) is a routing protocol designed 33 for use in mobile ad hoc networks. The protocol divides the nodes of 34 the ad hoc network into a number of overlapping or disjoint clusters 35 in a distributed manner. A cluster head is elected for each cluster 36 to maintain cluster membership information. Inter-cluster routes are 37 discovered dynamically using the cluster membership information kept 38 at each cluster head. By clustering nodes into groups, the protocol 39 efficiently minimizes the flooding traffic during route discovery and 40 speeds up this process as well. Furthermore, the protocol takes into 41 consideration of the existence of uni-directional links and uses 42 these links for both intra-cluster and inter-cluster routing. 44 1 Introduction 46 There are several major difficulties for designing a routing protocol 47 for MANET. Firstly and most importantly, MANET has a dynamically 48 changing topology due to the movement of mobile nodes which favors 49 routing protocols that dynamically discover routes over conventional 50 distant vector routing protocols [6], e.g. Dynamic Source Routing[4], 51 TORA[3], ABR[5] etc. Secondly, the fact that MANET lacks any 52 structure makes IP subnetting impossible. However, routing protocols 53 that are flat, i.e. only one level of hierarchy, might suffer from 54 excessive overhead when scaled up. Thirdly, links in mobile networks 55 could be asymmetric at times. Routing protocols could make use of the 56 uni-directional links to improve its overall performance. 58 CBRP has the following features: 60 * fully distributed operation. 62 * less flooding traffic during the dynamic route discovery process. 64 * explicit exploitation of uni-directional links that would otherwise 65 be unused. 67 The idea of using clusters for routing in Ad hoc networks has 68 appeared in [7],[8]. In these protocols clusters are introduced to 69 minimize updating overhead during topology change. However, the 70 overhead for letting each and every node maintain up-to-date 71 information about the whole network's cluster membership and inter- 72 cluster routing information in order to route a packet is 73 considerable. In comparison, simpler and smaller clusters are found 74 in [9] and [10], however, the use of these clusters is mainly for the 75 task of channel assignment; how they can help in the routing process 76 is not discussed. 78 CBRP adopts the cluster formation algorithm as proposed in [9], but 79 unlike [9], CBRP mainly concentrates on the use of clusters in the 80 routing process. CBRP is different from previously proposed cluster- 81 based routing algorithms and it uses a dynamic route discovery 82 strategy. 84 2. CBRP terminology 86 This section defines terms used in CBRP that do not appear in [2]: 88 * Node ID 90 Node ID is a string that uniquely identifies a particular mobile 91 node. Node IDs must be totally ordered. In CBRP, we use a node's IP 92 address as its ID for purposes of routing and interoperability with 93 fixed networks. 95 * Cluster 97 A cluster consists of a group of nodes with one of them elected as a 98 cluster head. The election procedure is described in section 5.1 and 99 5.2. A cluster is identified by its Cluster Head ID. Clusters are 100 either overlapping or disjoint. Each node in the network knows its 101 corresponding Cluster Head(s) and therefore knows which cluster(s) it 102 belongs to. 104 * Host Cluster 106 A node regards itself as in cluster X if it has a bi-directional link 107 to the head of cluster X. In such a case, cluster X is a host 108 cluster for this node. 110 * Cluster Head 112 A cluster head is elected in the cluster formation process for each 113 cluster. Each cluster should have one and only one cluster head. A 114 cluster head has complete knowledge about group membership and link 115 state information in the cluster within a bounded time once the 116 topology within a cluster stabalizes. In CBRP, each node in the 117 cluster has a bi-directional link to the cluster head. 119 * Cluster Member 121 All nodes within a cluster EXCEPT the cluster head are called members 122 of this cluster. 124 * Gateway Node 126 A node is called a gateway node of a cluster if it KNOWS that it has 127 a bi-directional or uni-directional link to a node from another 128 cluster. As shown in Figure 1, node 3 and 4 are gateway nodes of 129 cluster 1, node 6 is a gateway node of cluster 8. 131 2 5 132 // \\ 133 // \\ 134 (1)===3==6====(8) 135 \\ // 136 \\ // 137 4<------7 139 Fig. 1 141 * Neighbor Table 143 The neighbor table is a conceptual data structure that we employ for 144 link status sensing and cluster formation. Each entry contains the ID 145 of a neighbor that it has connectivity with and the status of that 146 link and the role of the neighbor (a leader or a member). 148 3. Physical and Link Layer Assumptions 150 This section lists the assumptions we made about the underlying 151 physical and link layers when designing CBRP. Each node in MANET is 152 equipped with a transceiver. In general, CBRP works best with 153 omnidirectional antennas. Each packet that a node sends is broadcast 154 into the region of its radio coverage. 156 4. Link/Connection Status Sensing Mechanism 158 In CBRP, each node knows its bi-directional links to its neighbors as 159 well as unidirectional links from its neighbors to itself. For this 160 purpose, each node maintains a Neighbor Table as follows: 162 +------------+-------------------------------+---------------------+ 163 | NEIGHBOR_ID| LINK_STATUS | ROLE | 164 +------------+-------------------------------+---------------------+ 165 | neighbor 1 | bi/unidirectional link to me? | is 1 a cluster head?| 166 +------------+-------------------------------+---------------------+ 167 | neighbor 2 | bi/unidirectional link to me? | is 2 a cluster head?| 168 +------------+-------------------------------+---------------------+ 169 | ... 170 +------------+-------------------------------+---------------------+ 171 | neighbor N | bi/unidirectional link to me? | is N a cluster head?| 172 +------------+-------------------------------+---------------------+ 174 Each node broadcasts its Neighbor Table periodically in a HELLO 175 message as shown below every HELLO_INTERVAL. 177 +-----------+------------------------------------------------------+ 178 | MY_OWN_ID | MY_MEMBERSHIP_STATUS | 179 | | (CLUSTER_HEAD/CLUSTER_MEMBER/UNDECIDED) | 180 +-----------+------------------------------------------------------+ 181 | Neighbor Table | 182 +------------------------------------------------------------------+ 184 The first field specifies the ID of the sender. The second field 185 tells whether the sender is a cluster head, cluster member or 186 undecided. ("undecided" means a node is still in search of its host 187 cluster) 189 Upon receiving a HELLO message from its neighbor B, node A modifies 190 its own Neighbor Table as follows: 192 1. It checks if B is already in the Neighbor Table, if not, it 193 adds one entry for B. 194 2. If B's Neighbor Table contains A, A marks the link to B as 195 bi-directional in the relevant entry. 196 3. If B is cluster head, marks B as a cluster head in the entry. 198 Each entry in the Neighbor Table is associated with a timer. A table 199 entry will be removed if a HELLO message from the entry's node is not 200 received for a period of (HELLO_LOSS+1)*HELLO_INTERVAL, allowing 201 HELLO_LOSS consecutive HELLO messages to be lost from that node. 203 When a nodes' neighborhood topology stabilizes, each node will have 204 complete knowledge of all the nodes that it has a bi-directional link 205 to and all the nodes that have a uni-directional link to it within a 206 bounded time. However, a node would not know to whom it has a uni- 207 directional link. 209 Note that the 2nd and 3rd column of the neighbor table need not be 210 sent out for the purposes of link sensing, however, they are there 211 mainly for cluster formation and other functionality of the protocol. 213 5. Protocol Operation 215 The operations of CBRP are entirely distributed. According to the 216 functionality, CBRP could be viewed as a combination of the three 217 following sub-functions which will be discussed below. 219 5.1 Cluster Formation 221 The Cluster Formation algorithm is a simple "lowest ID" clustering 222 algorithm in which the node with a lowest ID is elected as the 223 Cluster Head [9]. 225 A node uses the information obtained from the HELLO message for 226 Cluster Formation. A node that has the lowest ID among all its bi- 227 directionally linked neighbors (a node that has given up the role as 228 a Cluster Head is not counted, i.e. a cluster member node ). The new 229 Cluster Head will change the first field in its subsequently 230 broadcast HELLO messages from "undecided" to "cluster head" 231 thereafter. 233 A cluster head regards all the nodes it has bi-directional links to 234 as its member nodes. A node regards itself as a member node for a 235 particular cluster if it has a bi-directional link to the 236 corresponding cluster head. Note that a member node may hear from 237 several cluster heads and therefore have several host clusters. 239 5.2 Cluster Maintenance 241 As clusters are identified by their respective cluster heads, we 242 would like to have the cluster heads change as infrequently as 243 possible. We use the following rules for changing cluster head, as 244 described in [10]. 246 1. A non-cluster head never challenges the status of an existing 247 cluster head, i.e. if X is a non-cluster head node with a 248 bi-directional link to cluster head Y, X does not become 249 a cluster head even if it has an ID lower than Y's. 250 2. Only when two cluster heads move next to each other (i.e. there 251 is a bi-directional link between them), one of them loses the 252 role of cluster head. 254 Therefore, our exact algorithm is not a strict "lowest ID" clustering 255 algorithm. The cluster maintenance procedure are discussed under 256 three subsections: 258 * Node Removal 260 A node X is removed from a host cluster either because it loses the 261 bi-directional links to the cluster head, or because of node 262 failures. In either case, the cluster head and node X will time out 263 the corresponding entries in their Neighbor Table so that the cluster 264 information will be updated. 266 * Node Addition 268 A member node is added to a new cluster when it discovers a bi- 269 directional link to the respective cluster head even if the cluster 270 head has a higher ID, which is consistent with rule 1. The node will 271 know its new host cluster and the new host cluster head will know its 272 new member through the updated Neighbor Table. 274 When a node is switched on, its MY_MEMBERSHIP_STATUS field in the 275 HELLO message is initially UNDECIDED for a period of UNDECIDED_PD. If 276 it discovers that it has a bi-directional link to a cluster head, it 277 modifies this field as CLUSTER_MEMBER. If there is no such bi- 278 directional links to any cluster head, it takes the role as a cluster 279 head and indicates this in the subsequent HELLO messages it sends. 281 * Cluster Head Contention 283 When two Cluster Heads move next to each other (till they have a bi- 284 directional link in-between), one of them must give up its role as 285 cluster Head. As a result, whenever a cluster head hears the HELLO 286 message from another cluster head indicating a bi-directional link in 287 between, it will compare its own ID with that of the other cluster 288 head's. The one with a smaller ID will continue to act as cluster 289 head. The one with a bigger ID gives up its role as cluster head and 290 changes from "cluster head" to "member" in its subsequent HELLO 291 messages. This might trigger the formation of other new clusters. 293 5.3 Routing Considerations 295 Routing in the CBRP is based on source routing, which is similar to 296 [4]. Therefore, it can be viewed as consisting of 3 phases: route 297 discovery, packets routing and stale route removal, of which packet 298 routing is trivial. 300 Cluster structure is exploited to minimize the flooding traffic 301 during route discovery phase. Furthermore, some uni-directional links 302 are discovered and used which increases network connectivity. This is 303 discussed in the Gateway Discovery section. 305 5.3.1 Gateway Discovery 307 Cluster X and cluster Y are said to be bi-directionally linked, if 308 any node in cluster X is bi-directionally linked to another node in 309 cluster Y, or if there is a pair of opposite uni-directional links 310 between any 2 nodes in cluster X and cluster Y respectively. 312 Cluster X is said to be uni-directionally linked to cluster Y if any 313 node in cluster X is uni-directionally linked to any other node in 314 cluster Y. Y is called X's upstream uni-directionally linked 315 neighboring cluster. 317 By Gateway Disvoery, a cluster head for cluster X will obtain the 318 information about cluster X's bi-directionally and upstream uni- 319 directionally linked neighboring clusters. 321 For this purpose, a Cluster Adjacency table is kept at each node 322 which is formatted as follows: 324 +------------------+-----------------------------------------------+ 325 |Adjacent Cluster1 | adjacent node|to/from/bi | 326 +------------------+-----------------------------------------------+ 327 |Adjacent Cluster2 | adjacent node|to/from/bi | 328 +------------------+-----------------------------------------------+ 329 |... | 330 +------------------------------------------------------------------+ 332 This table is updated by the periodic HELLO message a node hears. 333 Note that a node may have several links to nodes in a particular 334 cluster and only one of them is recorded in the Cluster Adjacency 335 Table. The selection rule is as follows: 337 1. A bi-directional link takes precedence over all uni-directional 338 links. 339 2. Of the links that have the same precedence, the one with the 340 lowest ID wins. 342 This table is periodically sent to the member node's host cluster 343 heads. (It could be piggybacked to the HELLO message if possible.) A 344 cluster head uses its members' Cluster Adjacency table to construct 345 its own cluster adjacency table. The construction rule is the same 346 as that of the member's. 348 Cluster head will flood its neighboring clusters with a message of 349 TTL 3 in search for the "to" link that corresponds to a "from" link 350 in its Cluster Adjacency Table. As a result, cluster heads will have 351 complete knowledge of all its bi-directionally linked neighboring 352 clusters even if there is no actual bi-directional links in between. 353 For example, in Fig 1, Cluster 1 knows that 2 can reach cluster 1 354 through 5, but 1 does not know that cluster 2 can be reached by node 355 3. In CBRP, cluster head 1 and 2 will discover this scenario and 356 disseminate the information to node 3 and 5 respectively. 358 3-->4 359 // \\ 1 and 2 are heads of their respective 360 // \\ clusters, 3,4,5,6 are members. 361 (1) (2) 362 \\ // 363 \\ // 364 6<--5 366 Fig. 2 368 5.3.2 Route Discovery 370 Route Discovery is the mechanism whereby a node S wishing to send a 371 packet to a destination D obtains a source route to D. Similar to 372 other MANET protocols [4] [1], the way S finds a route(or multiple 373 routes) to D is also done by flooding, however, because of the 374 clustering approach the number of nodes that are disturbed are much 375 less in general. 377 Essentially in Route Discovery, cluster heads are flooded in search 378 for a source route. To perform Route Discovery, the source node S 379 sends out a Route Request Packet (RREQ), with a recorded source route 380 listing only itself initially. Any node that forwards this packet 381 will append its own ID in this RREQ. Each node forwards a RREQ 382 packet only once and it never forwards it to a node that has already 383 appeared in the recorded route. In CBRP, the RREQ will always follow 384 a route with the following pattern to reach destination D: 385 S,CH1,G1,CH2,G2,G3,CH3 ..... D 387 A detailed description of how this is achieved is presented below. 388 Source always unicasts RREQ to its cluster head, say CH1. Each 389 cluster head will unicast RREQ to each of its bi-directionally linked 390 neighbors which have not yet appeared in the recorded route through 391 the corresponding gateway. This process continues until the target is 392 found or until another node that can supply a route to the target is 393 found. 395 When the target of the Request, node D, receives the RREQ, D may 396 choose to memorize the reversed source route to S. Node D then 397 copies the recorded source route into a Route Reply packet(RREP) 398 which it then sends back to the initiator of the Route Request (e.g., 399 node S) by reversing the recorded route and putting it in the IP 400 header of the Route Reply packet. The recorded route gives the 401 complete information about the SEQUENCE OF CLUSTERS source should 402 traverse in order to reach destination D. While forwarding the Route 403 Reply, intermediate cluster heads modifies the IP header of the 404 packets, substitute the inter-cluster incoming links to inter-cluster 405 outgoing links. Each intermediate cluster head also modifies the 406 recorded route in the Route Reply packet to optimize the recorded 407 route as much as possible using its knowledge of the cluster topology 408 and inter-cluster gateway information. An example of such 409 optimization is to connect two gateway nodes by an intra-cluster link 410 that does not go through the cluster head. 412 All source routes learned by a node are kept in a Route Cache, which 413 is used to further reduce the cost of Route Discovery. When a node 414 wishes to send a packet, it examines its own Route Cache and performs 415 Route Discovery only if no suitable source route is found in its 416 cache. 418 5.3.3 Route Removal 420 A source route is removed from S if the network topology has changed 421 such that S can no longer use the route to D because a hop along the 422 route no longer works. If S still wants to communicate with D, it can 423 invoke Route Discovery again to find a new route. 425 6. Discussions and Implementation Considerations 427 This section discusses some of the problems that we have encountered 428 during the design of CBRP. In particular, they are related to the use 429 of uni-directional links in routing. 431 6.1 ARP and Uni-directional links 433 In a MANET context, links between 2 nodes can be bi-directional and 434 uni-directional. However, when the link layer does MAC-layer 435 address based packet filtering, (which most current technologies do), 436 special care has to be taken for ARP for uni-directional links. For 437 example, when there is a uni-directional link from node A to node B 438 as shown in Figure 2, node A should not rely on the conventional ARP 439 protocol to resolve node B's MAC layer address, because node B's ARP 440 reply will never reach node A directly. 442 A---->B 444 Fig. 3 446 CBRP is able to use uni-directional links. For an intra-cluster uni- 447 directional link, the upstream node can be informed by its cluster 448 head of the MAC-layer address of the downstream node. For a inter- 449 cluster uni-directional link, as shown in Figure 1, node 3(5) will 450 know node 4(6)'s MAC-layer address by the process of gateway 451 discovery. 453 6.2 Rate of Stale Route Discovery and Uni-directional Links 455 In general (not pertaining to CBRP), when uni-directional links are 456 used, discovery of stale routes can be slow. As shown in Figure 3, 457 when the link between 1 and 2 breaks, node 1 will not be aware until 458 a message comes from 2 by way of 3,4,5,6. This observation justifies 459 CBRP's use of inter-cluster uni-directional links only between 2 460 clusters. 462 1--->2--->3--->4--->5 463 ^ | 464 | | 465 | | 466 | | 467 +-------- 6 <-------+ 469 Fig. 4 471 7. Future Directions 473 Cluster based routing protocols (CBRP) is the first step towards a 474 more scalable solution using clustering approach. It also suggests 475 how uni-directional links in Ad hoc networks can be used in routing 476 and the reveals problems resulting from such use. 478 Several questions remain to be answered in CBRP, 480 1. How collisions can be avoided or handled effectively. Shall we 481 have spatial reuse of the channels among different clusters? 482 2. Should clusters have native support for QoS as in [10]? 483 3. Should clusters be made bigger than two hops diameter? If so, 484 what criteria should be used to form a bigger cluster? Or, 485 should we use a hierarchy of clusters? Will the resulted more 486 complex cluster formation and maintenance procedure offset the 487 advantage of having a bigger size? 489 To give satisfactory answers to these interesting questions will be 490 our future directions in refining CBRP. 492 References 494 [1] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing", 495 MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3, 496 1997. 498 [2] Perkins, C.E., "Mobile Ad Hoc Networking Terminology", 499 draft-ietf-manet-term-00.txt, work in progress. 501 [3] Corson, M.S., and Ephremides, A., "A Distributed Routing 502 Algorithm for Mobile Wireless Networks", ACM/Baltzer Journal 503 on Wireless Networks, January 1995. 505 [4] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing in 506 Ad-Hoc Wireless Networks", Mobile Computing, T.Imielinski and 507 H.Korth, editors, Kluwer, 1996. 509 [5] Toh,C.K., "A Novel Distributed Routing Protocol To Support 510 Ad-Hoc Mobile Computing", International Phoenix Conference on 511 Computers and Communications (IPCCC'96), pg 480-486, March 1996. 513 [6] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1998. 515 [7] Das, B., Raghupathy, S, Vaduvur, B, "Routing in Ad Hoc Networks 516 Using a Spine", Proceedings of 6th International Conference on 517 Computer Communications and Networks, Las Vegas, USA, September, 518 1997. 520 [8] Krishna, P., Vaidya, N.H., Chatterjee, M., Pradhan, D.K., " A 521 Cluster-based Approach for Routing in Dynamic Networks", 522 Proceedings of the Second USENIX Symposium on Mobile and 523 Location-Independent Computing, 1995. 525 [9] Gerla, M., Tsai, T.C., "Multiculster, mobile, multimedia radio 526 network", ACM/Balzer Journal of Wireless Networks, 1995. 528 [10] Chiang, C.C., Wu, H.K., Liu, W., Gerla, M., "Routing in 529 Clustered Multihop, Mobile Wireless Networks with Fading 530 Channel", The Next Millennium, the IEEE SICON, 1997. 532 This work was supported in part by National University of Singapore 533 ARF grant RP960683. 535 Authors' Information 537 Jiang Mingliang 538 Mobile Computing Lab 539 School of Computing 540 National University of Singapore 541 Singapore 119260 542 Email: jiangmin@comp.nus.edu.sg 544 Li Jinyang 545 Mobile Computing Lab 546 School of Computing 547 National University of Singapore 548 Singapore 119260 549 Email: lijinyan@comp.nus.edu.sg 551 Tay Yong Chiang 552 Department of Mathematics 553 National University of Singapore 554 Singapore 11920 555 Email: mattyc@leonis.nus.edu.sg