des-testbed / libara Goto Github PK
View Code? Open in Web Editor NEWA framework for the implementation and evaluation of routing algorithms based on the Ant Colony Optimization (ACO) metaheuristic.
License: GNU General Public License v3.0
A framework for the implementation and evaluation of routing algorithms based on the Ant Colony Optimization (ACO) metaheuristic.
License: GNU General Public License v3.0
AbstractARAClient needs to have a pointer to some implementation of AbstractForwardingPolicy and use this in the getNextHop() function which no longer needs to be abstract.
To make an advanced analysis possible it will be necessary to save the pheromone values from the routing table of each network node and how they change over time.
It will be best tom serialize this data into a simple binary format because of the following estimates of the expected result size:
let n = 50 nodes
let simulationTime = 900 seconds
let phiSize = 4 Bytes (Single-precision floating-point format)
let avgNrOfTableEntries = 15 (wild estimate)
let sizeOfNextHopAddress = 4 Bytes (IPv4 Address)
let singleDataSize = (phiSize + sizeOfNextHopAddress) * avgNrOfTableEntries
= 120 Byte
let updatesPerSecond = 4 (very vague pessimistic guess for each (!) routing tabled entry)
let updatesInNodeLifeTime = updatesPerSecond * simulationTime
= 3600
let totalResultSizePerNode = singleDataSize * updatesInNodeLifeTime
= 422 kB
let totalresultSizePerReplication = totalResultSizePerNode * n
= 20,6 MB
let nrOfReplications = 30
let totalresultSize = totalresultSizePerReplication * nrOfReplications
= 618MB
This estimate is really vague and kind of worst case but I think it shows that we will never support an ASCII based serialization of this value.
If we receive a packet A from some node X it may happen that this node resends this packet A because its acknowledgment timer timed out.
In this case we do not want to answer with a DUPLICATE_WARNING packet but instead just reacknowledge this packet.
We need a protocol which allows to spread information about the current energy level of a node.
We need to implement the Route Failure handling as described in the original ARA paper
We have to implement that we do not start a new route discovery if we have already initiated a route discovery for the packets destination which has not yet completed.
We have to implement/integrate a energy model which allows us to study the behavior of battery powered (mobile) devices. It would be nice if the energy model can easily be replaced by a different (new) energy model. It is envisioned to use measured energy values of the testbed for simulation. While the "simple" integration of an existing energy model is crucial for EARA, the latter feature request would be a nice to have. It should also be possible to 'deactivate' the energy model, thus we can switch between ARA/EARA for our studies.
The evaporation in the current main branch does not work. Currentyl, all paths are reinforced instead of the chosen one. See also unit test "pathToDestinationEvaporates" in class "AbstractARAClienTest" in branch "evatest".
We should add a new forwarding policy which implements the transmission probablity as defined in EARA. Futhermore, we need to customize the classes RoutingTable and RoutingTableEntry in order to support energy values.
Every node needs to add all transmitted packets in a list of unacknowledged packets together with a timeout. This list must be checked regularly and packets need to be re-transmitted if they have not been acknowledged within the corresponding timeout.
If a packet is acknowledged it has to be deleted from the list of course.
A client receiving DATA packet must acknowledge the packet with an ACK packet. Piggybacking may be implemented later.
The client should also keep track of the number of retransmissions and abort packet delivery if the packet has been resend too many times. If this happens a ROUTE_FAILURE packet needs to be send to the node that has send this packet in the first place.
If a client receives a ROUTE_FAILURE packet it deletes the entry from the routing table and tries to deliver the packet on another route. If no other route is available a ROUTE_FAILURE is send pack to the source of the packet. If a source has no more routes to a host it must start a new route discovery.
Would be great if we could somehow test more of the parts that involve the OMNeT++ simulation behaviour
In inetmanet, the wireless range of the nodes is displayed by a circle around the nodes.
I would normally assume that this depicts the maximum transmission/reception range.
If this is the case, there is a bug with our simulations (visible in alternativeBasicEvaluation) because it seems like nodes can communicate with other nodes that are not within the depicted transmission range.
Maybe someone can confirm the bug and read the documentation (aka the fine code) or search the forums for this kind of behavior.
I cannot compile the package on my Mac. I get the following error:
Compiling .//core/AbstractARAClient.cpp
cc1plus: error: unrecognized command line option "-std=c++11"
make[1]: *** [../out/gcc-debug/libara/.//core/AbstractARAClient.o] Error 1
make: *** [arasource] Error 2
It seems that you require c++11 which is maybe not supported by all GCC versions?
We want to switch from g++ to clang.
Check branch 'linear' and see if the latest commit of the branch has been merged with the develop branch. If that's the case we should 'delete' the branch.
We need to implement the logic, that the initial creation of routing table entries is different from the normal table updates (pheromone reinforcement).
The currently implemented logic uses the hop count of each packet in a somewhat arbitrary formula and the reinforcement parameter Δφ:
void OMNeTARAClient::updateRoutingTable(const Packet* packet, NetworkInterface* interface) {
AddressPtr source = packet->getSource();
AddressPtr sender = packet->getSender();
float currentPheromoneValue = routingTable.getPheromoneValue(source, sender, interface);
float hopCountMalus = 1 / (float) packet->getHopCount();
float newPheromoneValue = currentPheromoneValue + deltaPhi * hopCountMalus;
routingTable.update(source, sender, interface, newPheromoneValue);
}
We need to change the logic to take into account that there might not be a current pheromone value (currentPheromoneValue == 0
) and then initialize it with some other formula.
Does the normal pheromone update of existing entries even take the hop count into account?
The current LinearEvaporationPolicy does not provide a linear evaporation but a exponential evaporation. Thus, it should be renamed from LinearEvaporationPolicy to ExponentialEvaporationPolicy.
If a user checks out the project and wants to build everything he usually invokes make all
or make test
. This will currently run into 2 errors that could be resolved automatically: At first the CppUTestFramework needs to be checked out and of course the make makefiles needs to be invoked if there is no src/Makefile.
Each *.cpp
file in the tests folder should have a dependency to a working CppUTest in stallation. A makefile dependency (check_if_cpputest_is_installed
) does also exist.
Apparently the following line does not work as expected because the target check_if_cpputest_is_installed
is never called:
.cpp.o: check_if_cpputest_is_installed
The current workaround is that this dependency is associated to the all target which does work but it would be nice if each cpp itself depends on the correct installation.
I think it would be more appropriate to rename the github repo to libARA.
What do you think?
There is a doxygen file in the repository which allows to generate a doxygen based documentation for the project. However, there is no make target for creating the documentation. While this can be done easily, it would be nice if the target would check if doxygen is installed instead of simply trying to execute the build. In addition, it would be nice if the doxygen documentation would use the doxygen style of the research group.
Needs a change now that this is no longer my private repository.
The test is currently ignored and fails if it is run.
It also seems unfinished.
I would finish it myself but I'm not completely sure how this EvaporationPolicy works.
Some documentation in CubicEvaporationPolicy.h would be awesome :)
We need to implement the pheromone evaporation (i.e. the constant decreasing of the pheromone values in the routing tables over time)
If a node receives a DUPLICATE_WARNING it means a data packet has been received over this node twice. The node must delete the corresponding entry from its routing table
The current packet delivery rate (PDR) is about 50% of all sent packets.
We need to find out if this is caused by a bug or if our choice of parameters is really bad.
We should improve our failure handling. Currently we just drop the packet if no alternative route exists after a link failure and inform the neighbors (as discussed earlier).
Nevertheless, the original paper states something about backtracking and relaying the packet via the neighbors. This is explained in some more detail by Alexander Bereskin in his diploma thesis "Optimierung von durch Ameisen inspiriertem Routing" section 3.5.
Here is a excerpt from the text:
"Falls keine Alternativen bekannt sind, wird im Paket der Flag f lag_rf
gesetzt, und dieses wird an alle direkten Nachbarn von vi gesendet.
Nach dem Empfang des markierten Paketes löschen die Nachbarknoten ebenfalls den feh-
lerhaften Zieleintrag aus ihrer Routingtabellen. Anschließend versuchen sie das Paket wei-
terzuleiten, sofern sie noch eine Route zum Empfänger kennen. Dabei ist die Anzahl der
Weiterleitungsversuche begrenzt, um die Last einzuschränken. Kommt das Paket auf die-
sem Weg beim Empfänger an, erkennt dieser am gesetzten Flag f lag_rf das während der
Weiterleitung aufgetretene Routingproblem und schickt per Broadcast einen BANT-Paket
an die anderen Knoten, um die Pheromonspur im Netzwerk zu aktualisieren. Ein Beispiel
der Fehlerbehandlung beim Routing ist auf der Abbildung 3.4 zu sehen.
Falls die direkten Nachbarn von vi nicht in der Lage sind, das Paket weiterzuleiten, lassen
sie f lag_rf gesetzt und leiten das Paket an ihre Nachbarn weiter. Bei diesen wiederholt
sich die Vorgehensweise - sie aktualisieren ihre Routingtabellen und versuchen, das Paket
weiterzuleiten. Damit wird die Fehlerbehandlung bis zum Sender propagiert, falls keine
Zustellung möglich ist. Der Sender broadcastet dann eine FANT und legt damit eine neue
Pheromonspur."
I think this sounds reasonable and may be the route failure handling that has been implemented in the DES-ARA version?!
This might be an issue caused by me. However, I'm not absolutely certain. If I run the simulation on the scenario branch, I receive the following error:
<!> Error in module (PingApp) ManetTest.node3.app (id=47) at event #481, t=0.625921: Model error: ASSERT: condition msg->getOriginatorId() == getId() false in function processPingResponse, applications/pingapp/PingApp.cc line 174.
Can you confirm that?
We need to agree on a file header. The current header is
/******************************************************************************
Copyright 2012, The DES-SERT Team, Freie Universität Berlin (FUB).
All rights reserved.
These sources were originally developed by Friedrich Große
at Freie Universität Berlin (http://www.fu-berlin.de/),
Computer Systems and Telematics / Distributed, Embedded Systems (DES) group
(http://cst.mi.fu-berlin.de/, http://www.des-testbed.net/)
------------------------------------------------------------------------------
This program is free software: you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any later
version.
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with
this program. If not, see http://www.gnu.org/licenses/ .
------------------------------------------------------------------------------
For further information and questions please use the web site
http://www.des-testbed.net/
*******************************************************************************/
We should add support for Periodic Ant Agents (PANTs) in our simulation. However, PANTs seem to be rather well undocumented (we should check the related master theses and the DES-ARA source code).
Upgrade the INETMANET Package from version 1.0 to 2.0. There is already a branch 'inetmanet2.0' which summarizes the required changes ...
We currently do not allow for more than one NIC in the OMNeT++ simulations because we have no possibility to determine which interface has been involved if a link failure has been reported from layer 2. In the future we need to remove this constraint but for now it does not impact "normal" simulations
Users which don't have push/pull rights to the repository
https://github.com/des-testbed/inetmanet-2.0
can't build ara-sim. The build process fails with a
"permission denied (publicKey)"
I assume that we are using the wrong URL for the git submodule, instead of
[email protected]:des-testbed/inetmanet-2.0.git
(as found in .gitmodules) we should use
git://github.com/des-testbed/inetmanet-2.0.git
The first one only works for people who can push changes to the repository (from my point of view). We should verify this and fix it.
We should provide a linear evaporation class which evaporates pheromones in a linear fashion.
We should provide the simulation scenarios from the original paper from 2002. This includes the following scenarios:
Issues:
Currently we only check if packets became deliverable if we receive a BANT.
It would be better to periodically check if any packet (destination) became deliverable and delete undeliverable packets if they stay to long in the packet trap.
In DES-ARA the packet trap counts for every packet how often it has been not deliverable in the periodic packet trap checks and disregards packets that exceed a specific limit. I propose we do the same
The current pheromone initialization function is
phi = initialPheromoneValue / hopCount
This has been chosen somewhat arbitrary by me and is not a good initialization function.
It would probably be better to implement a function based on the TTL
We want to provide a convient way of setting the forwarding policy via the omnetpp.ini configuration. Therefore, a (NED) interface ForwardingPolicy was introduced which every forwarding policy implements (like in NED). However, if we set the "OMNeTStochasticForwardingPolicy" in the omnetpp.ini file, the simulation environment complains that this policy does not implement the interface. If we set the forwarding policy "OMNeTEnergyAwareStochasticForwardingPolicy" everything works fine.
Forwarding policies are set via the forwardingPolicyModel Parameter, e.g.:
**.forwardingPolicyModel = "OMNeTEnergyAwareStochasticForwardingPolicy"
Please note that setting the forwarding policy is disabled in the basic ARANetworkLayer, e.g.
// FIXME
forwardingPolicy: OMNeTStochasticForwardingPolicy {
//forwardingPolicy: <forwardingPolicyModel> like ForwardingPolicy if
//forwardingPolicyModel != "" {
parameters:
@display("p=72,111");
}
Simulation terminates with a segfault when the simulation is finished
This issue has been outsourced from #32
The main task is to update the inetmanet simulation scenarios by other adhoc clients that solve the routing task via the AODV, DSDV and DSR algorithms
The final goal is to compare the results with the results from ARA.
We need more traffic generators
is the test wrong?
make test
!!............................................!...
.............................................!..
ERROR: Did not log expected message:
Forwarding DATA packet 123 from 192.168.0.1 to 192.168.0.10 via 192.168.0.3
Instead the following was logged:
Forwarding DATA packet 123 from 192.168.0.1 to 192.168.0.10 via 192.168.0.3 (phi=15.00)
./libara/core/AbstractARAClientLoggingTest.cpp:120: error: Failure in TEST(AbstractARAClientLoggerTest, sendsLogMessageIfDataPacketIsRelayed)
./libara/core/AbstractARAClientLoggingTest.cpp:60: error:
Did not log expected message
..
ERROR: Did not log expected message:
First BANT 123 came back from destination via destination. Waiting 5ms until delivering the trapped packets
Instead the following was logged:
First BANT 123 came back from destination via destination. Waiting 5ms until delivering the trapped packets
Could not stop route discovery timer (not found for destination destination)
./libara/core/AbstractARAClientLoggingTest.cpp:97: error: Failure in TEST(AbstractARAClientLoggerTest, sendsLogMessageIfBANTReachedItsDestination)
./libara/core/AbstractARAClientLoggingTest.cpp:60: error:
Did not log expected message
..................................................
...........................................
Errors (2 failures, 193 tests, 189 ran, 951 checks, 4 ignored, 0 filtered out, 100 ms)
make[1]: Leaving directory `/home/c/git/ara/Ara-Sim/tests'
I don't understand why the AbstractARAClient::handleAntPacketForThisNode method sends a BANT in case of a received FANT? Typically a destination node receives at some point a FANT where it destroys the FANT and creates a BANT and broadcasts it back. For most cases these might be the same nodes like the FANT has passed, but if someone thinks about asymmetric links this might not be the case.
We have to provide a descriptor class for the class OMNeTRoutingTable in order to read the routing table entries of ARA/EARA (including pheromone values, etc.).
We should use a TTL value inside the ARA packets instead of a hop count.
This will help us in calculating the initial pheromone value and help us prevent packages from going in infinite loops.
The description in the Readme does not work. It seems that the Git URL is not correct.
It would be totally awesome if we could use a continuous integration (CI) system for the project. One example for such a system would be Travis. However, the dependency management is somehow whacky, which makes it quite cumbersome to integrate our project in a hosted CI system.
For now we do not use the whole protocol stack like the other existing INET/MANET2.0 routing protocols. It could be beneficial to adapt the structure for manet routing as shown in the examples of inetmanet.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.