i LT i I Reliable Broadcast in Mobile Multihop Packet Networks Elena Pagani Gian Paolo Rossi Dipartimento di Informatica Universit degli Studi di Milan0 via Comelico 39 I 20135 Milano Italy pagae rossi dsi unimi it Abstract We describe a reliable broadcast protocol for mobile multihop packet radio networks The reliable broadcast service ensures that all the hosts in a group deliver the same set of messages to the upper layer It represents the building block to construct fault tolerant distributed applications whose demand is growing in a mobile environment too The protocol is intended for use in networks where the host mobility arbitrarily changes the network connectivity and where the rate of change is not so fast as to impose flooding as the only option In this context our protocol is a iirst attempt to show that a mechanism more flexible than spanning tree and more efficient than flooding is possible and a service such as the reliable broadcast can be obtained The protocol is constructed on top of a multi hop multicluster architecture It provides an exactly once message delivery semantics and tolerates communication failures and host mobility Temporaneous disconnections and network partitions are also tolerated under the assumption that they are eventually repaired Keywords mobile hosts multi hop radio networks clustered architecture reliable broadcast fault tolerance 1 Introduction We consider the reliable broadcast problem in multihop mobile packet radio networks The reliable broadcast service ensures that all the hosts in a group deliver the same set of messages to the upper layer This service is the building block to construct value added multicast services such as agreement and total ordering or it can be utilized to support the applications that involve groups of cooperating hosts use replication to achieve This work has been in part supported ment under contract MURST 1996 Pemi ion to make di Vhard by the Italian Govern copies of at1 or part oftbis material for Paonal or roomuse is granted without fee provided that the copies iire not made or distributed for profit or commercial advantage the copyfight notice the title of the publication and its date appear ad notice is given that copyright isby permission of the ACM Inc To copy otberwiq to republish to post on senws or to reditibute to lists require specific permission and or fee MOBICOM 97 Budapest Hungary yright 1997ACMO 89791 988 2 97 9 3 50 fault tolerance or share common resources Most of these applications include the hosts mobility as a primary requirement As a consequence a few proposal5 have been recently presented that address this problem in the frame of network configurations with fixed base stations connected through a wired infrastructure l 2 8 121 Th e resulting protocols benefit of the fixed part of the network In this paper we describe a reliable broadcast protocol that is intended for use in networks where the host mobility arbitrarily changes the network connectivity and where an infrastructure of base stations is not present This is the case of different applications such as vehicle traffic and fleets management or decision support in emergency relief and battlefield operations the groups are generally of small size and hosts are requested to interact according to a many to many scheme Without a global knowledge of the network topology the design of the broadcast and of fault tolerance is affected by the rate of topological change In the presence of high mobility the topology changes too fast to allow the construction of some logical routing structure and there is no alternative to flooding In the presence of very slow mobility the well known spanning tree algorithms such as those described in 4 can be utilized We consider mobile systems where the rate of topology change is difficult to predict and can range in between the two extreme bounds In this context our protocol is a first attempt to show that a mechanism more flexible than spanning tree and more efficient than flooding is possibIe and a service such as the reliable broadcast can be obtained When the rate of change becomes too high the protocol switches to flooding but since we expect that the mobility rate is not uniformily spread over all the hosts the protocol reacts by adapting the transmission according to the situations encountered in the different network zones To obtain these results the protocol assumes the existence of an underlying multi cluster multi hop packet network Following the clustering approach the hosts are grouped into clusters and a clustering algorithm such as described in lo 111 is supposed to identify the set of interconnected clusters that covers the whole population of hosts Unlike other network hosts that are stateless clusterheads maintain information necessary to ensure the message stabilization to provide recovery when failures occur and to maintain a local view of the clusterhead infrastructure This indicates that clusterheads are likely to become a potential hot spot of packet flow and a cluster bottleneck To avoid this event we are designing a simple and effective flow control mechanism to locally control the message traffic to prevent congestion and excessive packet dropping struct a clustered architecture covering the entire population of system hosts Most of existing clustered architectures are based on the notion of clusterhead and can be used for our purposes the clusterhead coordinates the transmissions within the cluster and represents the infrastructure to route inter cluster packets By followthe approaches described in lo 111 ing for instance the clustered architecture of figure 1 can be obtained Each node is a one hop neighbour of the clusterhead and at most two hops from the other members of the cluster Two clusterheads cannot be neighbours while The protocol provides an exactly once message delivery semantics and tolerates host mobility and communication failures it also tolerates temporaneous disconnections and network partitions under the assumption that they are eventually repaired and messages reach their group destinations When the clusterhead functions can be located at a well known site such as in the case of fixed base stations the protocol can be easily adapted to the new environment n clusterhead 0 The System Model The system we consider is composed of n mobile hosts with unique identifiers pl pn that communicate via a packet radio network We assume that all the mo bile hosts have