1 Anirban Mondal (IIS, University of Tokyo, JAPAN) CLEAR: An Efficient Context and Location-based Dynamic Replication Scheme for Mobile-P2P Networks Anirban Mondal (IIS, University of Tokyo, JAPAN) Sanjay K. Madria (University of Missouri-Rolla, USA) Masaru Kitsuregawa (IIS, University of Tokyo, JAPAN) Contact address:
2 PRESENTATION OUTLINE INTRODUCTION PROBLEM CONTEXTREPLICA ALLOCATION ALGORITHM PERFORMANCE EVALUATION RELATED WORKS CONCLUSION AND FUTURE WORK
3 Ever-increasing popularity and proliferation of mobile technologyINTRODUCTION Ever-increasing popularity and proliferation of mobile technology
4 Ever-increasing popularity and proliferation of mobile technologyINTRODUCTION Ever-increasing popularity and proliferation of mobile technology Mobile user statistics for JAPAN Jan 31, 2006 (http://www.wirelesswatch.jp/) DoCoMo 50,496,200 KDDI/au 21,791,900 Vodafone 15,134,300 TU-KA 3,010,600 TOTAL 90,433,000
5 A maze of mobile devices
6 A maze of mobile devices Usually, these mobile devices interact via base stations But sometimes, base station infrastructure does not exist
7 A maze of mobile devices Usually, these mobile devices interact via base stations But sometimes, base station infrastructure does not exist M-P2P network: Mobile Hosts (MHs) interact in a P2P fashion
8 APPLICATION SCENARIOSA remote area which has no base station infrastructure
9 APPLICATION SCENARIOSA remote area which has no base station infrastructure A group of doctors in an earthquake-devastated region no. of injured people, no. of empty stretchers, no. of blood units Moving salespersons in the same locality sales profits, no. of units sold A group of zoologists looking for data on some micro-organism
10 APPLICATION SCENARIOSA remote area which has no base station infrastructure A group of doctors in an earthquake-devastated region no. of injured people, no. of empty stretchers, no. of blood units Moving salespersons in the same locality sales profits, no. of units sold A group of zoologists looking for data on some micro-organism Disaster control scenarios, collaborative sales and scientific studies
11 Problem with M-P2P networksUser movement Users switching ON or OFF their devices
12 Problem with M-P2P networksUser movement Users switching ON or OFF their devices Frequent Network Partitioning
13 Problem with M-P2P networksUser movement Users switching ON or OFF their devices Frequent Network Partitioning Reduced Data Availability in M-P2P networks
14 Problem with M-P2P networksUser movement Users switching ON or OFF their devices Frequent Network Partitioning Reduced Data Availability in M-P2P networks Dynamic replication is needed to improve data availability
15 Main contributions We envisage the M-P2P network as a cluster of MHs with a cluster head (CH) for data validation and replica allocation Proposal of CLEAR (Consistency and Load-based Efficient Allocation of Replicas) for improving M-P2P data availability CLEAR considers replica consistency and load as criteria CLEAR uses knowledge of moving users' schedules
16 PRESENTATION OUTLINE INTRODUCTION PROBLEM CONTEXTREPLICA ALLOCATION ALGORITHM PERFORMANCE EVALUATION RELATED WORKS CONCLUSION AND FUTURE WORK
17 Problem Context We envisage the M-P2P network as a cluster with a cluster head (CH) Data item sizes and bandwidth across MHs may vary A data item can be updated ONLY by its owner Each MH periodically sends to CH access statistics, update logs (including timestamps) and load, list of data items at itself LOAD of an MH Number of queries in the MH’s job queue Normalized w.r.t. bandwidth Hybrid architecture which preserves MH autonomy and deploys CH for facilitating data validation and replica allocation
18 Determination of future user access patternsThe objective of replica allocation is to replicate objects of an MH M's interest at MH(s) that would be near to M's future location at the time when M would access the objects Each MH moves according to some schedule Each MH sends its schedule to CH Schedule contains the MH’s location at different points of time and when the MH will access which objects
19 Replica Consistency Absolute replica consistency may not be criticalDesired replica consistency is application-dependent Ease of replica consistency maintenance should be measured by the percentage change in value of the updated attribute and not from the number of updates NQDC: Number of Queries (NQ) answered with Desired Consistency (DC) NQDC = NQ * C if C >= DC, otherwise 0 The value of C is looked up from a pre-existing table
20 PRESENTATION OUTLINE INTRODUCTION PROBLEM CONTEXTREPLICA ALLOCATION ALGORITHM PERFORMANCE EVALUATION RELATED WORKS CONCLUSION AND FUTURE WORK
21 CLEAR REPLICA ALLOCATION ALGORITHMThe algorithm considers User mobility patterns Load Replica consistency Available memory space Cost-benefit of replication
22 Query redirection to replicasSelect a set of underloaded MHs containing the replica Direct the query to the MH with best NQDC
23 PRESENTATION OUTLINE INTRODUCTION PROBLEM CONTEXTREPLICA ALLOCATION ALGORITHM PERFORMANCE EVALUATION RELATED WORKS CONCLUSION AND FUTURE WORK
24 Performance Study Parameters used for the performance studyPerformance metrics Average response time (ART) of a query Percentage Success Ratio (SR) (based on desired consistency Traffic (i.e., total hop-count) during replica allocation Reference approaches: E-DCG+ and NoRep
25 Performance of CLEAR CLEAR provides better ART than E-DCG+Consideration of MH mobility patterns Load-aware replica allocation CLEAR provides higher SR than E-DCG+ Consideration of consistency issues (NQDC) Quicker Updates due to load-aware replica allocation CLEAR avoids broadcast storm during replica allocation due to SP
26 Effect of variations in workload skewAs the workload skew increases, the effect of CLEAR’s load-based replica allocation becomes more pronounced.
27 Effect of variations in the replica allocation periodsTrade-off between freshness of data and communication cost
28 Effect of variations in write probabilityReplica consistency becomes difficult to maintain when there are more writes
29 Effect of variations in the no. of MHsMore MHs means more opportunities for replication
30 PRESENTATION OUTLINE INTRODUCTION PROBLEM CONTEXTREPLICA ALLOCATION ALGORITHM PERFORMANCE EVALUATION RELATED WORKS CONCLUSION AND FUTURE WORK
31 Related Works [Fife:03] discusses replication issues in MANETs.[Pitoura:96] discusses replication in distributed systems with partial, weak and variant connectivity Existing systems in this area ROAM Clique Rumor [Hara,Madria] discuss replica allocation in MANETs with periodic and aperiodic updates, and considers limited MH memory space access frequencies of data items network topology
32 Differences from existing worksTraditional replication techniques do not address frequent network partitioning issues limited resources of MHs Mobile Replication techniques mostly assume stationary networks P2P replication services are not `mobile-ready' as current P2P systems have mostly ignored data transformation, relationships and network characteristics. [Hara:02] considers frequent network partitioning w.r.t. replication in mobile ad-hoc networks (MANETs) Differences of our work from [Hara:02] We use load as a replication criterion We address different levels of replica consistency We consider unequal-sized data items.
33 Conclusion and future workWe have proposed the CLEAR scheme for dynamic replication to improve M-P2P data availability Exploits user mobility patterns Deploys a super-peer architecture that facilitates replica allocation, while maintaining P2P autonomy. Considers different levels of replica consistency and load as replica allocation criteria. Avoids broadcast storm during replica allocation and broadcast-based querying. Our experiments demonstrate that CLEAR improves M-P2P data availability Future work Economic replication in M-P2P networks (incentive schemes) Top-k query processing in M-P2P networks