[ndnSIM] Unusual behavior of Random Replacement Policy

[Alex Afanasyev]

Hi Saran,

> On Nov 3, 2014, at 1:23 AM, Saran Tarnoi <sarantarnoi at gmail.com> wrote:
> 
> Hello Alex and All,
> 
> I have experienced a few unusual things about the random replacement policy in ndnSIM.
> 
> First, the "insert" function in random-policy.h usually returns False. This is because the condition "MemberHookLess<Container>() (*item, *policy_container::begin ())" is usually False, which I really have no idea what is going on there. This issue effectively prevents the items in the cache from being replaced by coming ones for some reasons.
> 
> I fixed the issue by modifying the feasible value of u_rand. That is, "u_rand (0, std::numeric_limits<uint32_t>::max ())" is substituted with "u_rand (0, 1)". Then, the insert function no longer returns False. But I am not sure if this is a correct way to do. Does the approach break the rule of the random replacement policy?

I’m not sure that this is the correct approach.  u_rand now can return just two values, 0 and 1.  If cache is full, you will be (unconditionally) evicting all items with the stored value of 0, and them randomly items with value of 1.

The original intention to have policy container be ordered by random value is to ensure that items can be quickly removed in random order.  I think I made a mistake of using the same random number as a condition to cache / evict.

I would just add a new random variable ns3::UniformVariable u_rand2 (0, 1); and use this u_rand2 in the condition, keeping u_rand as it is:

    if (u_rand2.GetValue() == 0)
      {
        // std::cout << "Cannot add. Signaling fail\n";
        // just return false. Indicating that insert "failed"
        return false;
      }
    else
      {
        // removing some random element
        base_.erase (&(*policy_container::begin ()));
      }

—
Alex

> Second, using the approach, I experimented with two nodes, cache size is two while the item population is three. It appeared that the two nodes always replaced the same item. For example, if nodeA replaced item1, nodeB also replaced item1. Consequently, the two caches stored exactly the same set of cached items at the same time. This would not happen if the two nodes independently chose an item to be replaced. This made me think I might solve the issue incorrectly or do not understand something.
> 
> Please confirm the issue and give me some pieces of advice.
> Thank you so much for your time.
> 
> -- 
> Regards,
> Saran Tarnoi
>