<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hmm.. You’re right, the problem is still there.<div class=""><br class=""></div><div class=""><div class=""><br class=""></div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Nov 14, 2014, at 12:51 AM, Saran Tarnoi <<a href="mailto:sarantarnoi@gmail.com" class="">sarantarnoi@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hi Alex,<div class=""><br class=""></div><div class="">Thank you so much for your response. That is really helpful.</div><div class=""><br class=""></div><div class="">However, I think the current implementation may be still incorrect in some parts.</div><div class="">Please patiently go through the following explanation.</div><div class=""><br class=""></div><div class="">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.<br class=""><br class="">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.</div><div class=""><br class=""></div><div class="">I put the following codes after policy_container::insert (*item);:</div><div class=""><br class=""></div><div class=""><div class="">for (typename policy_container::iterator it = policy_container::begin (); it != policy_container::end (); it++)</div><div class=""> {</div><div class=""> <span class="" style="white-space:pre"> </span> // assign new random value to it</div><div class=""> <span class="" style="white-space:pre"> </span> get_order (&(*it)) = u_rand.GetValue ();</div><div class=""> }</div></div><div class=""><br class=""></div><div class="">It now seems to be a pseudo random replacement policy, the complexity is not optimized though.</div></div></div></blockquote><div><br class=""></div><div>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.</div><div><br class=""></div><div>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…</div><div><br class=""></div><div>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.</div><div><br class=""></div><div>—</div><div>Alex</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="">Hope this helps and please check the idea as well as merging it to the master branch if it is usable.</div><div class=""><br class=""></div><div class="">Thanks so much,</div><div class="">Saran Tarnoi</div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">2014-11-14 10:55 GMT+09:00 Alex Afanasyev <span dir="ltr" class=""><<a href="mailto:alexander.afanasyev@ucla.edu" target="_blank" class="">alexander.afanasyev@ucla.edu</a>></span>:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Saran,<br class="">
<span class=""><br class="">
> On Nov 3, 2014, at 1:23 AM, Saran Tarnoi <<a href="mailto:sarantarnoi@gmail.com" class="">sarantarnoi@gmail.com</a>> wrote:<br class="">
><br class="">
> Hello Alex and All,<br class="">
><br class="">
> I have experienced a few unusual things about the random replacement policy in ndnSIM.<br class="">
><br class="">
> 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.<br class="">
><br class="">
> 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?<br class="">
<br class="">
</span>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.<br class="">
<br class="">
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.<br class="">
<br class="">
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:<br class="">
<br class="">
if (u_rand2.GetValue() == 0)<br class="">
{<br class="">
// std::cout << "Cannot add. Signaling fail\n";<br class="">
// just return false. Indicating that insert "failed"<br class="">
return false;<br class="">
}<br class="">
else<br class="">
{<br class="">
// removing some random element<br class="">
base_.erase (&(*policy_container::begin ()));<br class="">
}<br class="">
<br class="">
—<br class="">
<span class="HOEnZb"><font color="#888888" class="">Alex<br class="">
</font></span><div class="HOEnZb"><div class="h5"><br class="">
> 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.<br class="">
><br class="">
> Please confirm the issue and give me some pieces of advice.<br class="">
> Thank you so much for your time.<br class="">
><br class="">
> --<br class="">
> Regards,<br class="">
> Saran Tarnoi<br class="">
><br class="">
<br class="">
</div></div></blockquote></div><br class=""><br clear="all" class=""><div class=""><br class=""></div>-- <br class=""><div class="gmail_signature"><div dir="ltr" class="">Regards,<div class="">Saran Tarnoi</div><div class="">Graduate Student</div><div class="">Department of Informatics</div><div class="">The Graduate University for Advanced Studies (Sokendai)</div><div class="">Tokyo, Japan</div></div></div>
</div>
_______________________________________________<br class="">ndnSIM mailing list<br class=""><a href="mailto:ndnSIM@lists.cs.ucla.edu" class="">ndnSIM@lists.cs.ucla.edu</a><br class="">http://www.lists.cs.ucla.edu/mailman/listinfo/ndnsim<br class=""></div></blockquote></div><br class=""></div></div></body></html>