marshallasch / saf Goto Github PK

1.0 3.0 0.0 111 KB

Hara's Static Access Frequency (SAF) data storage scheme for NS3

License: ISC License

C++ 74.79% Python 23.28% C 1.83% Shell 0.10%

ns3 manet masters mesh-networks ns-3 data-replication reproducibility

saf's Introduction

SAF Simulation

This modified version of the SAF simulator is designed to allow the SAF storage scheme to run as a module independently of the simulation runner logic.

The previous version of this implementation involved putting this repository into the scratch folder in NS-3, this is no longer the case. This module is designed to be placed in the contrib folder so it can be used as its own module and can be run independently of my simulation runner code.

This NS-3 scratch simulator code that attempts to implement the SAF data storage scheme and reproduce the performance evaluation as described in:

T. Hara, :Effective replica allocation in ad hoc networks for improving data accessibility" Proceedings IEEE INFOCOM 2001. Apr. 2001

Motivation

As part of my masters work as part of the Gillis Lab group¹ I am evaluating existing data storage schemes that does not have any available implementations to evaluate. A challenge that our lab group discovered is that there although there have been a number of works published that focus on developing new, better algorithms very little work has been done to evaluate the ones that exist, largely due to challenges around replicating the studies or reproducing the algorithms.

The goal of this implementation is to be able to have a baseline to compare other data storage schemes too (since there are none that are readily available and Hara's methods have been the defacto standard that others are compared to).

Note: Hara implemented their algorithm using a custom built simulator, we have chosen to implement it using the popular NS-3 network simulator instead.

Prereqs:

Not sure if there are others but on ubuntu:

sqlite3, libsqlite3-dev

If building netanim:

qt4-qmake
libqt4-dev

(additionally, on ubuntu 20.10, you need to add an additional repo because qt4 no longer ships with it)

https://launchpad.net/~gezakovacs/+archive/ubuntu/ppa

Building this project

Reproducibility is one of the key goals of simulator studies.

Download and build copy of the ns-3.32 all-in-one distribution.

wget https://www.nsnam.org/release/ns-allinone-3.32.tar.bz2
tar xjvf ns-allinone-3.32.tar.bz2
cd ns-allinone-3.32
python3 ./build.py --enable-examples

Change directories to the contrib/ folder of the ns-3.32 source distribution.
```
cd ns-3.32/contrib/
```

Clone this repository.

git clone [email protected]:marshallasch/saf.git saf

Change directory back to the ns-3.32 folder of the source distribution and re-configure ./waf so it can cache the new changes
```
cd ..
./waf configure --enable-examples --enable-tests
./waf build
```
Run the example simulation that is included within the module.
```
./waf --run 'saf-example'
```
Create your own simulations using the SAF module. This is done the same way you would run any other simulation using NS-3. Setup your nodes, add a mobility model, install the SAF application using the helper, then run the simulation.

One this to note is that the current implementation does not separate the SAF validation simulation from the base SAF implementation that can then be used in other applications, that is a work in progress.

Running the simulation

If you're familiar with ns-3, then you should know that the simulation is run via the waf build tool. Arguments to this program must be part of the same string that is passed to ./waf --run (that's just how it works 🤷).

Every parameter of the simulation is configurable. Run the following to see all the configurable parameters. The default values are as described in the SAF paper cited at the top of this document.

./waf --run 'saf-example --printHelp'  # <-- mind the quotes!

You can view an animation of the simulation using NetAnim, which is included with the ns-3 all-in-one distribution. To do so, run the following:

./waf --run 'saf-example --animation-xml=path/to/saf.xml'

This will generate an XML file at the specified path. You can then open this file with NetAnim to view what happens during the simulation run.

NOTE: currently the generation of the animation has been disabled to improve the run time

Code style

This project is formatted according to the .clang-format file included in this repository. It intentionally deviates from the code style used by the ns-3 library and simulator developers.

The code can be formatted using the included python script created by Guillaume Papin ([@Sarcasm]) and can be found Sarcasm/run-clang-format.

The following command can be run to automatically reformat the code in place according the included style guideline.

./run-clang-format.py -r -i --style file .

Special Thanks

I would like to acknowledge the amazing work that was done by Keefer Rourke (@keeferrourke) on the initial RHPMAN project that I used as a base for this implementation.

License

While ns-3 is itself licensed under the GNU General Public License v2, the code in this repository is made available under the Internet Systems Consortium (ISC) License.

A copy of this license is included in this repository, and embedded in the top of each source file.

saf's People

Contributors

Stargazers

Watchers

saf's Issues

Split SAF implementation

Currently the saf-application file is responsible for both the data storage and replication scheme as well as the data access simulation application. Both portions should be abstracted out from one another so that different applications and storage schemes can be properly evaluated.

Change the Message classes to use protobuf

I should have implemented the messages using protobuff, this would have solved the problems with byte offsets and all that fun stuff when parsing messages.

protobuf supports c++ so this should be a fairly trivial change.

Convert timeouts to use the request ID and not the data id

Currently when a data id is being requested its id gets put into a list to be able to handle timeout events. This causes problems in the case:

req 1

req 1 again
recv 1

recv 1 again

in this case there may be a timeout event happening when it did not actually timeout, there was just a timeout clash in the the list.

Run test simulations that Jason mentioned

Some extra test cases that should be run to confirm that the code is indeed correct:

confirm that the messages are only being sent to the correct number of nodes.
- Currently everything is sent via a UDP broadcast with a TTL=2, I believe this value is not correct and will result in the messages being sent to too many nodes
- check this by manually setting up the locations of nodes so that they are only have one node within range
show that there is congestion happening (other wise it is an ideal network which is less than realistic)
- this can be accomplished using #12
check behaviour when the data sizes are ridiculously large, this should also show congestion behaviour

Implement statistics collection

Need to collect some sort of stats so that something can be evaluated

Add code style checker

In order to maintain consitent code a style checker should be added. See the style guideline created by @keeferrourke's initial RHPMAN implementation to see if that would work for this project.

The --animation-xml parameter seems to do nothing

Was trying to create a netanim viz so I can see what was happening, but it doesn't seem to be creating the file. Tried a relative and absolute path. No feedback, or errors indicating a problem.

Runtimes note about debug vs optimized builds

After the algo has started working see commit <>.

debug build using the default parameters:

4:28.749 min

optimized using default parameters:

0:44.202 min

so Make sure that optimized builds are used for actual evaluations

make it configuratble from cli paramters

Currently the SAF algorithm has some paramters but the simulation runner does not have any.

Correct the stats collection for number of messages sent

Re conversation with Jason.
Count the number of messages being sent as if they were uni-cast messages as opposed to broadcast. (alternatively actually send them as uni-cast) this will allow the detection of dropped packets when a message is sent but all of the other nodes do not receive it. currently I have no way to know this.

given the current implementation mun sent != mun received because of the broadcasts

Since I am currently using a fixed range wifi model, I can get the nodes mobility model and find the number of nodes that are within the specified range. However this will not work for other communication models. A better approach will be to add a callback to the routing table and have the application maintain a list of all one hop nodes.

This has some other implications but it should work best.

Something is wrong that causes tests to crash

currently if you were to have this project included in your ns3 contrib folder and then run the ns3 test harness every single test will crash, not fail, crash. I do not yet know why, but it is something that I noticed earlier today when working on the rhpman implementation. The source of this needs to be fixed

refactor to use modular functions

As I learned when implementing the rhpman scheme, small functions make refactoring and fixing bugs waaaaaaay easier. this should be done here as well.

update cli flags to support SEM

Change the cli flag format to not use '-' use cammelCase to make the flags simpler to specify in scipts where the '-' might be miss-interpreted for a minus sign.

Calculate actual access frequencies

In the Hara paper there were several ways of setting the access frequencies for the different data items.
This should be implemented to replace the current hard coded value of 0.5

This should also be implemented as a cli parameter to select this.

replicate Hara evaluation

In order to validate this implementation the inital study by T. Hara should be replicated to check that the results are similar enough.

If not reevaluate the plan to use this as a base algorithm for the evaluations

Dependency Dashboard

This issue lists Renovate updates and detected dependencies. Read the Dependency Dashboard docs to learn more.

Edited/Blocked

These updates have been manually edited so Renovate will no longer make changes. To discard all commits and start over, click on a checkbox.

Update HorstBaerbel/action-clang-format action to v1.5

Open

These updates have all been created already. Click a checkbox below to force a retry/rebase of any.

Update actions/checkout action to v4

Detected dependencies

github-actions

.github/workflows/clang-format.yml

actions/checkout v3

HorstBaerbel/action-clang-format 1.4

.github/workflows/ns3-build.yml

actions/checkout v3

Check this box to trigger a request for Renovate to run again on this repository

Currently the application does not actually work when run on a mesh

While developing the implementation testing has been done using a wired network consisting of 4 nodes, this should be changed to a mesh of a number of devices to confirm it still works properly.

When I tested an earlier version using a mesh the code did not work for unknown reasons.