[ndnSIM] Unusual behavior of Random Replacement Policy

[Saran Tarnoi]

Hi Alex,

Thank you so much for your response. That is really helpful.

However, I think the current implementation may be still incorrect in some
parts.
Please patiently go through the following explanation.

To my understanding, from the current codes, the items in policy_container
are sorted in ascending order based on their randomOrder values, and the
item pointed by policy_container::begin () will be erased. As a result, the
items with high randomOrder values are likely to stay in the cache for a
long time (if not forever). For a long simulation, the cache usually evicts
only the recently cached item since the others are likely to have higher
randomOrder values.

To fix the problem, I think we should assign new randomOrder values to all
of the items in the cache every time an item in inserted, so that the order
of items in the cache is shuffled.

I put the following codes after policy_container::insert (*item);:

for (typename policy_container::iterator it = policy_container::begin ();
it != policy_container::end (); it++)
      {
      // assign new random value to it
      get_order (&(*it)) = u_rand.GetValue ();
      }

It now seems to be a pseudo random replacement policy, the complexity is
not optimized though.

Hope this helps and please check the idea as well as merging it to the
master branch if it is usable.

Thanks so much,
Saran Tarnoi


2014-11-14 10:55 GMT+09:00 Alex Afanasyev <alexander.afanasyev at ucla.edu>:

> 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
> >
>
>


-- 
Regards,
Saran Tarnoi
Graduate Student
Department of Informatics
The Graduate University for Advanced Studies (Sokendai)
Tokyo, Japan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndnsim/attachments/20141114/9594ff4e/attachment.html>