[ndnSIM] Question on FIB matching
Alex Afanasyev
alexander.afanasyev at ucla.edu
Sun May 12 21:07:46 PDT 2013
Hi Hauchen,
I'm not sure that you can get any meaningful results using NS-3, since it was designed to simulate events, and not exactly suite for processing evaluation, unless this processing is defined as a sequence of events. You may want to check this info http://www.nsnam.org/docs/manual/html/realtime.html that describes how available schedules in NS-3 work. The key point is that "during event execution, simulation time is frozen". You can still use ndnSIM code and evaluate FIB performance, but you should not rely on any NS-3 time management elements.
Unfortunately, the implemented in ndnSIM FIB lookup process (actually, it is the same lookup for all other data structures, including Content Store and PIT) is not yet fully documented. The underlying data structure is a complex tree, where each node of the tree corresponds to a name component, and connection to child nodes is implemented as a hash array. If you want, you can check more details by looking into the source code in utils/trie/trie.h. I need to warn though, that this data structure is specific to ndnSIM, and different implementations may have different data structures with different properties.
Btw. What kind of problems are you getting when you're running the code that you mentioned?
---
Alex
On May 12, 2013, at 5:57 AM, Haochen Wang <haochenallen at gmail.com> wrote:
> Hi Alex,
> I want to know further about the FIB lookup algorithm. I'll also be grateful if there's any doxygen available to read.
> Meanwhile, I recently established a simulation exploring the relation between the quantity of FIB entries and the time of FIB lookup. Unfortunately, the result turns out irrelevant which upsets me. I assume that there must be a relation between the above two contents, could you please give me some hints about the problem?
> Also, I use the following sentences to input the FIB entires, and I guess there might be some mistakes leading to the problems.
> for(int i=0; i<1000; i++)
> {
> std::string str = "";
> std::stringstream intTostr;
> intTostr<<i;
> intTostr>>str;
> ndn::StackHelper::AddRoute ("c1", "/data1/data2/"+str, "n1", 1);
> ndn::StackHelper::AddRoute ("n1", "/data1/data2/"+str, "p1", 1);
>
> ndn::StackHelper::AddRoute ("c1", "/data1/", "n1", 1); // link to n1
> ndn::StackHelper::AddRoute ("n1", "/data1/", "p1", 1);
>
> }
> The perfix of interests is "/data1/", c1 for consumer, n1 for router and p1 for producer.
> I add contents with prefix "/data1/data2/" into FIB (1000 entries), which I think could have no influence on the results.
> I change the variable "i" to change numbers of entries written into FIB to implement the simulation.
>
> Warm Regards,
> Haochen
>
>
> 2013/5/11 Alex Afanasyev <alexander.afanasyev at ucla.edu>
> Hi Asit,
>
> I'm thinking to remove a requirement to have a valid FIB entry, in order to attempt to process interests (though I will still PIT creation procedure), but don't yet have a time frame for that.
>
> You can add default routes automatically using ndn::StackHelper::SetDefaultRoutes method http://ndnsim.net/doxygen/classns3_1_1ndn_1_1_stack_helper.html#a12b1c8f16bad953ac3b9bb4a6ab1fcab. If you don't want to have a dummy prefixes in FIB, you can try to remove lines 350-352 in model/pit/ndn-pit-impl.h, but you probably would need to check other parts of the code, since it was assumed that PIT entry has always a valid reference to PIT: A FIB entry is basically a place where information about past performance of Interest/Data exchanges within this prefix can be stored.
>
> ---
> Alex
>
> On May 8, 2013, at 5:08 PM, Asit Chakraborti <Asit.sc.Chakraborti at huawei.com> wrote:
>
>> Hi Alex,
>>
>> Thanks for the response, that makes sense. I needed to process the interests differently and was planning to create a new
>> Forwarding strategy, however, the interests got dropped and didn’t get delivered to the new strategy as there was no
>> FIB match. Either I have to modify the common code to allow PIT entries with no matching FIB (not sure how badly that
>> would violate the entire model), or may be I will try to have dummy “/” entries in the FIB…
>>
>> Thanks,
>> Asit.
>>
>> From: Alexander Afanasyev [mailto:cawka1 at gmail.com] On Behalf Of Alex Afanasyev
>> Sent: Wednesday, May 08, 2013 4:28 PM
>> To: Asit Chakraborti
>> Cc: ndnsim at lists.cs.ucla.edu
>> Subject: Re: [ndnSIM] Question on FIB matching
>>
>> Hi Asit,
>>
>> The currently implemented way always attempts to lookup FIB and create PIT entry for incoming interest, and if there is a CS match, such a PIT entry will be immediately satisfied.
>>
>> The main reason behind this implementation is to unify metric calculation: for every interest there will always be either new or existing PIT entry, and every satisfied interest can be tracked via PIT entry satisfaction. It is technically possible to change the implementation, but I'm not yet sure if this would get any major benefits.
>>
>> As for last question. Yes, it is assumed that there is always some FIB entry, at least a default entry for root prefix, that can match incoming interests. And if there is no such entry, then NDN router is not willing to do anything with such interests.
>>
>> Do you have a specific scenario where this assumption doesn't hold? It is relatively easy to create an alternative forwarding strategy with slightly different processing logic.
>>
>> ---
>> Alex
>>
>> On May 8, 2013, at 3:31 PM, Asit Chakraborti <Asit.sc.Chakraborti at huawei.com> wrote:
>>
>>
>> Hi Alex,
>>
>> My understanding of the code could be wrong, but it seems we require a FIB match on an incoming
>> Interest even before a CS match. Any historical reason behind this ? Or is it just the fact that with
>> the current model and APIs, a FIB entry usually exists if the content is in content store ?
>>
>> Thanks,
>> Asit.
>> _______________________________________________
>> ndnSIM mailing list
>> ndnSIM at lists.cs.ucla.edu
>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndnsim
>>
>> _______________________________________________
>> ndnSIM mailing list
>> ndnSIM at lists.cs.ucla.edu
>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndnsim
>
>
> _______________________________________________
> ndnSIM mailing list
> ndnSIM at lists.cs.ucla.edu
> http://www.lists.cs.ucla.edu/mailman/listinfo/ndnsim
>
>
>
>
> --
> *********************************************
> Beijing University of Posts and Telecommunications,
> No.10 Xi Tu Cheng Rd., Hai Dian Dis.,
> Beijing, CHINA, 100876
> School of Information and Communications,
> Cell Phone: 86-13581958046
> *********************************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndnsim/attachments/20130512/d648b8ea/attachment.html>
More information about the ndnSIM
mailing list