[ndnSIM] Unusual behavior of Random Replacement Policy

[Alex Afanasyev]

Hmm..  You’re right, the problem is still there.



> On Nov 14, 2014, at 12:51 AM, Saran Tarnoi <sarantarnoi at gmail.com> wrote:
> 
> 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.

This probably would not help, as the policy_container wouldn’t be automatically re-sorted.  The only way to force re-sorting, is to re-add all items with new random values.

I was trying to think of a better way, but couldn’t quite figure out.  Ideally, we need to just pick a random element from the policy_container to evict (e.g., random based on number of items and evict item, whose number we selected at random).  Unfortunately, we cannot use std::vector in the implementation and the only efficient way is to use boost::intrusive::multiset, and assign sequence number to all inserted items.  Though this would require renumbering of items…

May be it would be easier to use just boost::intrusive::list and forget about efficiency.  Just every time element needs to be evicted, we will find it in O(n) complexity.

—
Alex


> 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 <mailto:alexander.afanasyev at ucla.edu>>:
> Hi Saran,
> 
> > On Nov 3, 2014, at 1:23 AM, Saran Tarnoi <sarantarnoi at gmail.com <mailto: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
> _______________________________________________
> ndnSIM mailing list
> ndnSIM at lists.cs.ucla.edu
> http://www.lists.cs.ucla.edu/mailman/listinfo/ndnsim

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndnsim/attachments/20141114/d0cf9b82/attachment.html>