Background
Introduction
Related work
Context
Method
Hormone-based delivery and replication
total
) for the requested unit. To create a hormone gradient P1 splits the available hormones and reserves a part for diffusion to neighbors (to_diffuse
). How much each neighbor gets from to_diffuse
depends on the quality of the link to it. Thus, P2 gets the highest rate and P4 the lowest rate. When the neighbors get the hormones, they forward again a part of it. The forwarding is repeated until a node is reached where the requested content is located (here, P7). The unit can now move hop-by-hop towards the highest hormone concentration, which is found at the requester.
Parameter settings
to_diffuse
in Figure 1). The evaporation value ϵ will be subtracted for reducing the hormones on alternative paths. These parameters need to be tuned dependent on each other. E.g., if η0 and η are low and the evaporation value ϵ is high, the movement of units is limited to a fewer number of hops. The greater the amount of hormones created, the further the hormones can travel and thus the search space increases. Further parameters regard the minimum hormone strength difference to move a unit m, which controls the mobility of units. If m is high, the units need a higher hormone concentration to move to a neighbor, leading to a longer waiting time for the requester. t is the minimum hormone strength, if a hormone value is below this threshold it is considered as insignificant and can be deleted. In general, the parameter settings are essential for the algorithm to work and their inter-dependencies and combinations make it hard to tweak them manually. We therefore optimize them using an evolutionary algorithm as described in (Elmenreich and Klingler 2007).ID | Explanation |
---|---|
η
0
| Hormone strength of a unit at new request |
η
| Increase of hormone after each time step by the requester |
α
| Percentage of hormones to be forwarded to the neighbors |
ϵ
| Hormone evaporation value |
t
| Significance threshold for hormones |
m
| Minimum hormone strength difference to move unit |
Replication mechanisms
Existing replication mechanisms
Owner replication
Path replication
Active replication
Local knowledge replication mechanisms
Simple hormone
Local popularity
Neighbor popularity ranking
Neighbor hormone ranking
Clean-up/Replacement strategies
Simulation setup
Network topology
Initial storage
Request generation
maxhops
(see Equation 1).Simulation parameters
η
0
| 3.95 |
η
| 4.39 |
α
| 0.45 |
ϵ
| 0.16 |
t
| 0.23 |
m
| 0.23 |
c
| 60% |
maxhops
| 10 |
Metrics
Results and discussion
-
hormone
replicates if for the given unit hormones exist on the neighbors -
hranking
ranks the hormones of neighbors to decide the need of replication -
owner
only replicates on the requesting node -
path
replicates always -
path_adapt
replicates with a given probability on the current node -
pop
replicates if the popularity of this unit is high enough on the current node -
pranking
ranks the unit’s popularity in the neighborhood to decide the need of replication
50 Nodes random network
owner
replication leads to the highest delay, followed by hormone
and pranking
, then path_adapt
and pop
. It can be seen that hranking
even outperforms the path
replication mechanism. The reason for this is that path
replication creates too many copies and therefore some nodes do not have any storage space left for transportc. The storage space balancing is not only a problem of path
replication, the other replication mechanisms also fill a number of nodes that cause the blocking of transport. In the following we compare the delay, the request failure rate and the utilization of the three introduced clean-up mechanisms hormone, LRU and LFU.
path
and hranking
, which switch their position. However, the clean-up has a negative impact on all replication mechanisms as their delay curves are located closer to 1s. In comparison to the base case, the most conspicuous example is the combination with local popularity replication (pop
), where a high delay jitter results in a gentle curve. The following hormone
delay curve shows a similar, although less extreme delay jitter increase.
path
replication is also affected, which results in a similar delay of path
, hranking
and path_adapt
. LRU further increases the delay jitter of path
as shown by a more gentle curve than hranking
. In this graph the delay of hormone
is even higher than owner
replication.
hormone
replication mechanism and owner
replication suffer from wrong decisions and result in gentle curves. path
replication results in doubled delay, which leads to a similar delay as pop
. hranking
results in a similar delay as path_adapt
, but with a lower delay jitter its curve is steeper.
path
replication). However, it has a very bad impact on pop
and hormone
replication and further results in the highest delay for owner
. LRU has the lowest impact on path_adapt
in comparison to the base case. Although the delay of the replication mechanisms increases it leads to steeper curves than hormone clean-up and LFU. LFU has the highest impact if considering the delay increase of the best combination (here, path_adapt
replication).hormone
replication seems to suffer from any clean-up. The reason is the low number of replicas created by this mechanism. Additionally, the placement is not ideal such that any removal is crucial. pranking
replication does not create enough replicas and therefore performs similar to hormone replication. The combination of pop
and hormone clean-up does not fit, because the replication mechanism considers long-term popularity (based on the history of the requests) and the clean-up mechanism considers short-term popularity. hranking replication creates many replicas on strategic positions and therefore the transport might be blocked.hormone
replication does not take advantage of any clean-up mechanism, because it already creates only a small amount of replicas. The utilization of path
and pop
replication lowers if clean-up is applied. path_adapt
and owner
lead in any combination to a stable utilization. The highest utilization improvement, in comparison to the base case, is shown by hranking
in combination with hormone
clean-up. Also LFU would make a good fit, but results in a higher delay.path
replication leads to the lowest utilization if combined with LRU. As already seen in the delay comparison, pop
replication with hormone clean-up do not fit. hranking
has the worst utilization if combined with LRU. The highest utilization is reached by owner
replication, because it creates the lowest number of replicas. However, has also the highest delay.hranking
and path
replication. The highest failed rate is reached by owner
replication. This indicates that replicas on the transport path improve the service quality. As already shown by the delay and the utilization, pop replication with hormone clean-up does not fit. The outliers marked by (*) can be explained by high failure rates at the beginning (within the first 100s) of the simulation. owner
and hormone
replication show the highest variance of failure rates.
owner
replication with LRU, path_adapt
with LRU and path
with hormone clean-up manage to lower the failure rate in comparison to the base case. This can be explained by a better balancing of the placement. LRU leads to the lowest increase of the failure rate with most of the approaches, except the combination of hranking
and path
with hormone clean-up. LFU leads to the highest increase of the failure rate.path
replication has the lowest delay it creates too many replicas and leads to the lowest utilization and therefore we do not further consider this approach. We further omit all cases with LFU clean-up, because it leads to the highest delay, the lowest utilization and the highest failure rates.hranking
and path_adapt
. hranking
has the lowest delay in combination with hormone clean-up. This combination leads to the best improvement of utilization in comparison to the base case and only results in a slight increase of the failure rate. The lowest impact on the delay has the combination of path_adapt
and LRU, which is further leading to a lower failure rate, however also a slightly lower utilization as the combination with hormone clean-up. We decide for combining path_adapt
with LRU because of higher chances to fulfill user requests.hranking
is based on neighborhood knowledge and path_adapt
represents an uninformed (traditional) approach.Impact of node failure
hranking
algorithm with hormone clean-up. One can see that it is capable of handling loss. Overall, the delay increases slightly, but interestingly the delay of 5, 10 and 20 removed nodes is very similar. This shows that the transport paths adapt fast to the new conditions.
path_adapt
replication with LRU leads to interesting results as shown in Figure 9. Here, the delay of the peer failure scenarios is lower than in the original case. This anomaly can be explained by referencing the clean-up failures of the original scenario. A clean-up fails if on the current node all units are currently in use or there is no copy of the current unit on a neighbor. A disadvantageous replica distribution might be that at every second hop a replica is placed, which means that a high number of replicas exist in the system, but because the nodes only see their neighbors, the units cannot be deleted. In the peer failure scenario, it is likely that a node that blocks the transport is removed and therefore opens the possibility of alternative paths. Hence, to reduce the delay of the original case, a clean-up mechanism would have to check the neighborhood with a larger hop-distance.
path_adapt
and hranking
are robust. However, if the number of failed nodes gets higher than 20, we expect a performance drop.
hranking
, but a more stable failure rate is reached by path_adapt
if nodes fail. hranking
places the units more efficiently, its utilization can be increased by a clean-up mechanism.1,000 nodes scale-free network
hranking
with hormone clean-up. In comparison to the small network scenario the delay is increased by around 500 ms and the curve is less steep. The paths in a scale-free network scenario are not as long as in a random network. The best performance is reached if the units are placed on high-degree nodes.
path_adapt
the problem with clean-up failures does not apply such as in the 50 nodes network. The reason is the network structure and its rather low diameter. Therefore, the delay of path_adapt
replication is only a bit higher to the delay of hranking
.
hranking
replication is more robust than path_adapt
.
Discussion
path
replication with hormone clean-up, although inefficient, performs best regarding delay. Alternatives could be path_adapt
replication with LRU and hranking
replication with hormone clean-up. The node failure scenarios showed that there are still nodes, which block the transport of units. To solve this issue the settings could be less strict regarding the deletion policy. Instead of deleting a unit only if there is a copy of it in the neighborhood, it could be weakened to delete a unit if another unit covering the same keyword is in the neighborhood.