Implement pheromone evaporation about libara HOT 12 CLOSED

Have you given any thoughts where this is going to be implemented? As far as I know, the standard procedure is to use self messages which would require that whatever class is doing it, it has to be a OMNeT++ class. Possible candidates are:

• OMNeTARAClient

or a derived RoutingTable, e.g.

• OMNeTRoutingTable

Or. maybe something completely different?

from libara.

I think we want to implement a continuous pheromone evaporation as described in your tech report.

I propose to handle this via an Observer/Listener pattern.
Each time the routing table is updated via the RoutingTable::update(...) method it sends a message to all registered Listeners. One of those listeners should be the new PheromoneEvaporator class. It will calculate the appropriate evaporation factor depending on how long it has been since the last time the routing table has been updated. Please note that it can not be the routing table which stores the last time of access because this does heavily depend on the used time format (e.g simulation time vs real time) so this will be implemented by the evaporator class.

After the factor has been calculated, the evaporator should call the new method RoutingTable::evaporatePheromones(float evaporationFactor) which will apply the factor to all the entries in its table. Some of the routing table entries might be dropped if their pheromone value reaches some configurable minimum threshold.

One advantage of this approach is that we decouple the evaporation logic from everything to make it more reusable and testable. Another advantage is that this will scale much better in huge simulations because we do not need to generate a huge amount of self messages for each simulated node (as already mentioned in the original proposal of this technique by Prof Günes).

Let me know what you think :)

from libara.

The observer/listener pattern sounds reasonable to me. However, I'm wondering how to deal with the single entry in the routing table which pheromone value is not decreased but increased. Maybe, there is a better way besides passing information about the entry to the listener. But, maybe I'm missing the point?

I'm also puzzled how this actually decouples the evaporation logic from everything? The listener computes a factor which denotes at what date the routing table was accessed. Let's say it's a number p. This would mean that every entry for every destination would be updated the following way:

((1 - q) * phi_curr) ** p

I don't understand how to support different evaporation functions with the proposed approach.

from libara.

I'm not sure I get you question. I thought we will apply the same evaporation factor to all elements in the routing table at once. Why would we want to handle some of the table entries differently? But maybe I got the question wrong there.

For now I don't think it is necessary to pass any information to the listener besides that an update has happened (but not the specifics of that update). It does only need to known that an update has happened to trigger the evaporation.

Another point for clarification: I am assuming here that all calls to the update() method will increase the value (due to path reinforcement). The only time we decrease a value is in the evaporation phase via the proposed RoutingTable::evaporatePheromones(float evaporationFactor) method. But if this assumption does not hold I don't really see a problem either because then the evaporation should also take place anyway.

We can also talk about this problem later that day if you like to move the discussion to a chatroom :)

from libara.

You want to handle exactly one entry different. I'm 'interpreting' the update function the following way: If the routing table knows nothing about the destination a new entry is created, if it knows the destination an entry is updated - if such an entry exists, otherwise a new entry is created. In all three scenarios a pheromone value is set (which typically reinforces the pheromone value). However, you don't want to decrease the pheromone value of this entry in a next step (which would happen if you would call the listener afterwards). But maybe, we should discuss this in jabber.

from libara.

Ah yeah you are right, I did not think of the initial entry creation.

To fix the issue we simply give RoutingTableListener interface two methods instead of one: RoutingTableListener::routingTableEntryHasBeenUpdated() and ' RoutingTableListener::routingTableEntryHasBeenCreated()

We then always call the appropriate method from within the two execution branches in RoutingTable::update(...).

By the way: I would also like to change the semantics of RoutingTable::update(...) by splitting it up into two methods: update(...) and createEntry(...) The AbstractARAClient will could take care of choosing the right function to call so we could easily integrate a more modular design for the initial pheromone creation (already an issue in #13)

from libara.

Well, the problem also exists if you don't create an entry for the first time. Example:

The unordered map is defined as followed: 'destination' => [entry_1, entry_2, ....] whereas entry_X points to a tuple of next hop, pheromone value, etc.

So, let's assume the following content of our unordered map

"destination_1" => [entry_1a, entry_1b, entry_1c]
"destination_2" => [entry_2a, entry_2b]

Now, let's assume that the next hop in entry_2b was chosen which means that the pheromone value of this node needs to be increased, but all other entries (entry_1a, entry_1b, entry_1c, entry_2a) need to be decreased. The listener know computes the time the last time the routing table was accessed. However, the evaporatePheromones has to be aware of the entry which should not be updated (since it does not make sense to increase a pheromone value in the first step, but to decrease it directly afterwards). But still, maybe I'm missing the point?

from libara.

Oh and it seems like I've overlooked your questions in the second paragraph from before (how this would decouple anything).

This decouples the way the pheromones are evaporated from a specific AbstractARAClient implementation. Lets say you implement a exponential evaporation with some parameters that weight the time that has passed and the evaporation factor itself. So thats one implementation ExponentialEvaporator. We might also write a LinearEvaporator or some other specific function to selectively decrease the pheromone values depending on their current value.

In the ARAClient we only need to register some implementation of PheromoneEvaporator (e.g in the simulations via OMNeT++ parameter) and do not care about implementing the same functions over and over again in different ARAImplementations or simulation scenarios.

Edit
Damn, I overlooked the part where the pheromone values to the next hops are increased >.>. I thought we only strengthen the path to the source node when we are receiving something from that direction.

However can we really ignore an entry in the evaporation just because it has been strengthened lately?

What if the last update to the whole table has been some longer time ago. Now we receive a packet, so the table needs an update and we trigger the evaporation. This should decrease all values in the table by the same factor first before we decide on the next hop. If we ignore the chosen next hop it could get huge unfair advantage over the other possibilities.

But I see the problem that we first receive a packet which will update the table and trigger evaporation and then decide on a next hop which will also update the table but should not again trigger the evaporation. Maybe some other method should be used for that? Something like increasePheromone() which will not trigger the evaporation?

Its all getting a bit complex here so maybe the Listener Pattern isn't the best fit for the job.
We could forget about all of the listener stuff and just trigger the pheromone evaporation in the Abstract ARA client right before we call the update function. The ARAClient needs to keep track of the last time we called that method though..

from libara.

We should probably discuss this using a whiteboard. I still don't see how to support multiple evaporation functions while using the AbstractARAClient class. Regardings the update of pheromones - it doesn't make much sense for me to increase on pheromone value while decreasing it in the 'next step'.

from libara.

I think we should think with the Observer/Listener pattern. I've added a "interface" class EvaporationPolicy and a implemenation LinearEvaporationPolicy which represent a evaporation function for the ARA. I'm not really happy encapsulating a 'function' in an class in order to support multiple evaporation "functions", but right now this is the best way to go. Like the transmission probablitiy classes, the question remains if concrete implementations of the classes should also inherit from CSimpleModule in order to support the "par" mechnism (since evaporation functions have also parameters which should be settable via the ned file). But, maybe that's to specific right now.

EDIT: Okay, the Observer/Listener pattern doesn't make much sense. I think a timer would be nice which gets started the first time the update function is called and which is stopped and restarted the function is called the next time, the passed time since start and stop of the timer is used to compute a factor for the pheromone reduction.

from libara.

While we want to seperate between simulation and non-simulation code the question remains how to determine the last access time. In a non-simulation scenario this could be done by comparing (unix) timestamps, which is unfortunately not useful todo in a simulation scenario. Right now, an abstract 'time' class with two sub classes (one for simulations, one for non-simulations) comes up to my mind, but I'm not sure if that's the way to go. Anyway, it's quite late right now.

from libara.

This is now implemented, reviewed and refactored.
It will surely be be enhanced in the future but for now this feature is generally working.

from libara.