[ndnSIM] How to modify LFU

[Alex Afanasyev]

Hi Shenglan,

I'm guessing you meant LFU.  Yes.  The ideally it should choose the least frequent one, but there it is not quite simple to determine/maintain which item is the least/most frequent.  Frequency can be defined in many ways (# hits / (total simulation time), # hits / last_second, # hits / last_hour, ...).  Right now, LFU policy uses first definition (#hist / (total simulation time)), which is not appropriate in some cases.

I understand your idea, I'm just a little bit confused how it can be implemented.  ContentStore knows only about content objects (and potentially their hits/misses).  How would you define downstream for a particular item?   The original interest that used to bring this content object is long time gone.  There could have been other interests that this content object has satisfied, which are also long time gone.

---
Alex

On May 2, 2013, at 7:52 PM, 陈胜蓝 <blindeafer at 163.com> wrote:

> I think it may be a replacement scheme. 
> The LRU policy is that when a content comes into a node and the node find out that there is no enough space to store the content.It will erase the least frequent content to make room for the new one.I am not sure if my understanding is correct.
> 
> My idea is that when there is no enough space to strore a new content,the node will push the most frequent one to downstream according to a record that record the corresponding interface the interest came in.So every intermedia node should record the interfaceID and the time when a interest of the content it stores come in.So we can get the interval a same interest access two times. The frequency=1/interval.
> 
> I am not sure if my representation is clear.Your reply will be really appreciated.
> 
> 
> 
> 
> 
> At 2013-05-03 10:11:33,"Alex Afanasyev" <alexander.afanasyev at ucla.edu> wrote:
> Hi Shenglan,
> 
> First, I would say that the current implementation of LFU is far from ideal.  May be Aaron can tell you more about the potential issues with the way LFU is implemented.
> 
> Do you have a specific design of how MFU should be implemented?  What is the data structure that can track frequencies?  How these frequencies can be updated, when (how often).  What is "frequency" in the first place (= what is your time period).  Another question that you may or may not have answer to is about how exactly you are planning to communicate to downstream nodes.  What do you mean by "pushing the most frequent content"?  Would it be part of the forwarding strategy or something else?
> 
> You can try to read the current code of lfu-policy.  What is basically happening is that each item in the content store is organized (in addition to normal name-based trie-like organization) as a multi-set (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L75) = the data structure that keeps order of items.  The order is maintained based on "frequency counter" value (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L71), which is assigned to 0 when item is added to the content store (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L103) and incremented every time an item is looked up (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L119).   The "missing" part is periodic "flushing" of this freshness counter, so the popular items in the past don't stay on the way of new items.
> 
> Btw. I'm not 100% convinced that "pushing" most frequent content downstream is actually content store task.  Could it be a specialized application/forwarding strategy module that periodically polls content store with normal LFU policy and do something with the most popular content?
> 
> ---
> Alex
> 
> On May 2, 2013, at 6:33 PM, 陈胜蓝 <blindeafer at 163.com> wrote:
> 
>> Hi Alex,
>> I want to implement a mfu-policy,and creat a new function to push the most frequently content to downstream node.
>> Would you like to give me some advice?
>> 
>> Best regards,
>> Shenglan
> 
> 
> 

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