Opportunistic persistent data storage

of 46

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
46 pages
0 downs
12 views
Share
Description
1. Opportunistic Persistent Data Storage Author: Weerasooriya W.A.A.C.P. 11002192 SCS 4001 Individual Project Undergraduate Thesis Defense University of Colombo School of…
Transcript
  • 1. Opportunistic Persistent Data Storage Author: Weerasooriya W.A.A.C.P. 11002192 SCS 4001 Individual Project Undergraduate Thesis Defense University of Colombo School of Computing06th January 2016 Supervisor : Dr. Ranasinghe D.N. 1
  • 2. Overview| Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement •Motivation •Target & Assumptions •Background & Related work •Research Approach •Conclusion & Future work •Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 2
  • 3. Overview | Motivation| Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement • What are opportunistic networks? • Has new technology increased the importance of the opportunistic networks? • What is the main problem in opportunistic networks? 06th January 2016 WEERASOORIYA W.A.A.C.P. 3
  • 4. Overview | Motivation| Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 4 Kathiravelu, T. (2007). Towards Content Distribution in Opportunistic Networks.
  • 5. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 5 • Target: Establishing a persistent data storage on top of the opportunistic network using opportunistic properties of the network. Two research questions under this. Q1: What is the way to capture social network properties in opportunistic networks? Q2: What is the persistent storage mechanism for a network like ON? • Assumptions: o Processes/nodes do not crash. o Each node knows the size of the network. o Total number of members in the opportunistic network is fixed. o Security is not an issue when sharing data.
  • 6. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 6 • Human Social Network, Electronic Social Network & Virtual Social Network Conti, M., & National, I. (2010). Opportunities in Opportunistic Computing.
  • 7. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 7 • What is meant by opportunistic properties? • Why are they important? • How to represent the network topology in opportunistic networks? • How can we capture opportunistic properties ? A B Degree Centrality (Red node) =5
  • 8. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 8 Routing in opportunistic networks • All the nodes in the opportunistic network can be considered as routers. • Typical routing mechanisms can not be applied here. Why? • Due to the intermittent connection between nodes and frequent topology changes direct communications (both time and space coupled) are not possible. • Therefore asynchronous message passing has been introduced for content distributions. • Store-Carry-Forward- Mechanism • Several routing algorithms are there that can be used with opportunistic networks. • First Contact, Direct Delivery, Spray and Wait, DLifeComm • Flooding does work, but it reduces the network capacity. • A good network protocol should use the opportunistic properties to take forwarding decisions while minimizing flooding
  • 9. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 9 Mobility Modeling in Opportunistic Networks • Evaluate the system using real world traces is not very easy. • Why ? Human resources, expensive communication devices, coordinate large geographical are etc. • Using synthetic traces is the solutions. But can those synthetic traces mimic the real world human behavior? • What are the options available? • Human behavior is not random. They have certain patterns and those patterns might be repeated over the time. Ex: People go to office every weekdays • Random Way Point / Random Walk- weak human behavior modeling. • Working Day Movement model- this comprises of several sub models – Home, Office, Evening and Transport.
  • 10. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 10 ONE- Opportunistic Networking Environment Simulator • There are several simulators for MANET. Ex: NS3, Jist/SWAN etc. • But they are general simulators. • ONE- is designed specially to mimic the real world human behavior (Written in Java). • This is very flexible in many ways and easy to configure. • Can be used with various routing protocols as well as various mobility models. • Can generate different types of reports and flexible http://www.netlab.tkk.fi/tutkimus/dtn/theone/
  • 11. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 11 Inter-process communication • Nodes in the opportunistic networks can be considered as distributed processes. • So the concepts that are applied in distributed processes can also be applied for opportunistic networks. • As we said earlier due to the intermittent connections and frequent topology changes, asynchronous message passing is the options for opportunistic networks. • All the communication mechanisms described below are possible in opportunistic networks. Both Time and Space coupled Time uncoupled- Space coupled Time coupled- Space uncoupled Both Time and Space Uncoupled
  • 12. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 12 Both Time & Space Uncoupled- Shared Persistent Space • Due to the intermittent connections and frequent topology changes in opportunistic networks, both time & space uncoupled communication is more suitable. • This leads to a Distributed Shared Memory implementation on top of the opportunistic network.
  • 13. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 13 Read/Write Registers • Distributed Shared Memory is a good way of achieving time uncoupled communications. • Registers are simple and useful abstraction for such DSM . • Time uncoupled communications require a certain object, whose the state can be changed by one process and observed by another process . • These objects can be considered as Registers. • We are considering here a single register and it stores a single integer • Two operations are there , • Write(x)- write the integer x on the register and return OK • Read()- Return the value stored in the register.
  • 14. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 14 Properties of Read/Write Registers • Liveness- Every operations eventually completes. • Safety- Read returns the last value written- This will be satisfied when there are no overlapping read() write(x) operations. • With the presence of the concurrent operations the its strength is reduced using following three different conditions A. Safe Safety:
  • 15. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 15 Properties of Read/Write Registers Cont. B. Regular Safety: C. Atomic Safety
  • 16. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 16 Design of the proposed solution • Our solution will be applied as the middleware of the system. It provides read(), write(x) operations to the user application. So user application will see a single shared storage. • All the message passing and complexities are hidden from the application programmer
  • 17. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 17 Experimental Settings • Used a 64bit dual core (2.4 GHz) machine to run the simulator • Total number of nodes: 1028 • Communication Technology: Bluetooth for all the nodes • Transmission speed: 2Mbps for all the nodes • Transmission range: 10m • Simulation time: It varies depending on the experiments. Usually 604800 S=7 days or 950400 S=11 days for experiments which require longer times. • Warm up time: Warm up times are needed for the routing and mobility model. So we have set it for 86400 S=1 day and some cases it is 172800 S=2 days. • Routing mechanism: Depending on the experiment purpose we can use different routing mechanisms (DLifeComm, DD, FC, SNW). Except in the second experiment we will only use DLifeComm. • Mobility model: We use WDM model. But in the 1st experiment for the comparison purpose we use RWP also.
  • 18. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 18 Human behavior modeling using WDM- ONE simulator • All our results depend on the human behavior modeling ability of the simulator. • First of all we have to check whether our simulator is capable of modeling real world human behavior more accurately or not. • Two features will be important- Inter Contact Time & Contact Duration
  • 19. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 19 Human behavior modeling using WDM- ONE simulator Cont. • Taking all the ICT and CD times between all the node contacts in a given simulation time we can create ICT and CD distributions. • We created ICT and CD distributions for WDM model and RWP model respectively using our simulator’s results of ICT and CD times. Results suggested that WDM, ICT and CD distributions are more closely to the real world ICT and CD distributions.
  • 20. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 20 Human behavior modeling using WDM- ONE simulator Cont. • ICT distribution ICT distribution of a real world trace
  • 21. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 21 Human behavior modeling using WDM- ONE simulator Cont. • CD distribution CD distribution of a real world trace
  • 22. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 22 Best Dissemination policy using opportunistic properties • The nature of the data dissemination depends on the mobility nature of the sender. Ex: Sender is a bus driver or a taxi driver, sender is a person who rarely travels. • So when we are doing experiments we have to consider several mobility natures. • Here we are considering three mobility natures (1) Sender has the “bus movement” (2) Sender can be an “office worker” (3) Sender travels every where- achieved by SPMB
  • 23. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 23 Best Dissemination policy using opportunistic properties Cont. • Three different simulations were required for the previously given three types of senders. At the same time for each sender separate five different simulations (altogether 15) were done using different routing strategies. • X axis- the simulation time- for every 10800 S data were captured. • Y axis- (the ratio of the nodes which have the latest copy)/ total number of messages in the system
  • 24. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 24 Best Dissemination policy using opportunistic properties Cont. • Sender is in a bus Sender is an office worker
  • 25. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 25 Best Dissemination policy using opportunistic properties Cont. • Sender travels everywhere- SPMB
  • 26. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 26 Communities captured by DlifeComm routing mechanism
  • 27. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 27 (1,N) Register, Write Globally, Read Locally- NO ACK
  • 28. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 28 (1,N) Register, Write Globally, Read Locally- Cont.
  • 29. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 29 (1,1) Register, Write Globally, Read Globally –Quorum mechanism • Majority Quorum mechanism
  • 30. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 30 (1,1) Register, Write Globally, Read Globally –Quorum mechanism Cont. Write(x) Read()
  • 31. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 31 (1,1) Register, Write Globally, Read Globally –Quorum mechanism Cont.
  • 32. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 32 Optimized Quorum mechanism • Majority is not the necessity to achieve the consistency between two quorums. Intersection is the necessity. • How to have considerable number of common nodes across quorums ? • Solutions: Write to some prominent actors in the network and this will give secure number of intersections even though the quorum size is reduced. • Use the Centrality metric to find the prominent actors (Here we use the degree of the node as the centrality metric) • Applied the methodology given in “Moreira, W., Mendes, P., Ferreira, R., & Cerqueira, E. (2012). Opportunistic Routing based on Users Daily Life Routine” To calculate the value. • A table is maintained in each node to store others’ centrality values. At regular intervals (this frequency can be changed) each node share their table values with their neighbors. • So when an operation is sent it is sent only to the selected top nodes in the centrality table (which have the higher centrality values).
  • 33. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 33 Optimized Quorum mechanism Cont. A B
  • 34. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 34 Optimized Quorum mechanism Cont. • Experiments are done considering four possible writer and reader combinations. (only the top 200 nodes were sent the messages and waiting ACK only from 50). • Writer- Office worker/ Reader- SPMB • Writer- Bus/ Reader- SPMB • Writer- SPMB/ Reader-Bus • Writer- SPMB/ Reader-Office worker
  • 35. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 35 Optimized Quorum mechanism Cont. • Writer- Office worker/ Reader- SPMB
  • 36. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 36 Optimized Quorum mechanism Cont. • Writer- Bus/ Reader- SPMB
  • 37. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 37 Optimized Quorum mechanism Cont. • Writer- SPMB/ Reader- Office worker
  • 38. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 38 Optimized Quorum mechanism Cont. • Writer- SPMB/ Reader- BUS
  • 39. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 39 (1,1) Register with Optimized Quorum system- Time comparison Quorum -515 Quorum- 50
  • 40. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 40 (1,N) Register with Optimized Quorum system • Problem of the previous (1,1) Register solution with the presence of the multiple readers.
  • 41. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 41 (1,N) Register with Optimized Quorum system cont. • Solution: Each reader enforces the value they read to the quorum before returning the value they read- This introduces the additional write operation to the readers.
  • 42. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledgement 06th January 2016 WEERASOORIYA W.A.A.C.P. 42 (N,N) Register with Optimized Quorum system • Solution: The only problem here is maintaining a global sequence number for write operations. This can be done maintaining a distributed shared sequence number.
  • 43. Overview | Motivation | Target & Assumptions | Background & Related work | Research Approach | Conclusion & Future work | Acknowledg
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks