[Nfd-dev] Fwd: question about how to handle dangling state

[Lan Wang (lanwang)]

Junxiao,

I saw you created Bug #1966: Interest unsatisfied due to similar Interest suppression combined with loop detection.  This is basically the dangling state blocking similar Interest problem.  There was some discussion more than two years ago exploring possible solutions (e.g., return data if the duplicate Interest is blocking other Interests and how to differentiate a blocking dangling state from a non-blocking one).  I'm forwarding one of those emails.  

Lan

Begin forwarded message:

> From: Beichuan Zhang <bzhang at arizona.edu>
> Subject: Re: question about how to handle dangling state
> Date: March 23, 2011 5:31:45 PM CDT
> To: "Lan Wang (lanwang)" <lanwang at memphis.edu>
> Cc: Lixia Zhang <lixia at CS.UCLA.EDU>
> 
> 
> On Mar 23, 2011, at 2:01 PM, Lan Wang wrote:
> 
>> 
>> On Mar 22, 2011, at 3:05 PM, Beichuan Zhang wrote:
>> 
>>> Assuming all the problems in section 2 warrant interest return as a
>>> necessary feedback mechanism, I'd re-phrase the question regarding
>>> dangling state as: do we need a better solution (than interest  
>>> return)
>>> to solve the dangling state problem?
>>> 
>>> We can also ask the same question to every other problem listed in
>>> section 2. What I'm afraid of is that we may end up with many  
>>> specific
>>> mechanisms, each dealing with one specific problem, and altogether
>>> making the system more complicated than using a single interest  
>>> return
>>> mechanism.
>>> 
>>> I have some comments inline below.
>>> 
>>> On Mar 22, 2011, at 9:58 AM, Lan Wang wrote:
>>> 
>>>> Hi Beichuan and Lixia,
>>>> 
>>>> I have been thinking about the dangling state:
>>>> 
>>>> First, if a particular piece of dangling state doesn't block other
>>>> users from retrieving data (i.e. the state doesn't lead to the  
>>>> actual
>>>> data or there's no other users sharing the path), it only adds to  
>>>> the
>>>> memory consumption in routers.  Is it a problem?  I remember Van
>>>> doesn't think the memory overhead *alone* is a problem.  My answer
>>>> would be it depends on whether there is enough dangling state to
>>>> cause a memory problem in routers.  For this we need more
>>>> simulations.
>>> 
>>> The memory overhead depends on how aggressive each node explores the
>>> network and how long the interest lifetime is.
>> 
>> Now I realize that in the case of dangling state not blocking other
>> users, the memory overhead of dangling state is not the only problem
>> under the current CCN's router-based retry scheme.  When these
>> dangling states timeout, they lead to unnecessary path explorations,
>> even if data has been returned to the consumer over another path.
>> However, this wouldn't be a problem in our consumer-based retry
>> scheme, since the consumer will stop retrying when it gets the data.
>> This is true without using Interest returns to clear up the dangling
>> state (in other words,  we don't have to use Interest return to solve
>> the unnecessary path exploration problem in this case assuming memory
>> overhead is not a problem).
>> 
>> In the case of dangling state blocking other users, there may be
>> solutions other than sending data back to duplicate Interests or
>> returned Interests.  See below.
>>>> 
>>>> Second, what we care more about is when a dangling state does block
>>>> other users to get their data.  But the question is can we solve it
>>>> without using Interest returns?  One straight-forward solution to  
>>>> the
>>>> example we gave in the writeup is to let the producer send back
>>>> another copy of the data even if the Interest is a duplicate of a
>>>> previously satisfied Interest.   If we are dealing with dangling
>>>> state that does block other users,  sending the data is not a waste
>>>> of bandwidth as it actually helps the other users get their data
>>>> (actually faster than using Interest returns) and removes the
>>>> dangling state.
>>>> 
>>>> For the above solution, you may say that not only producers need to
>>>> do this, routers need to do the same (return data to duplicate
>>>> Interests).   Yes, the question is whether that would lead to a
>>>> problem.  One potential problem I can think of is that the duplicate
>>>> may indicate a looping Interest and, in that case, we shouldn't send
>>>> data back into the loop.  But not all the duplicate Interests are
>>>> caused by loops -- it could be caused by branching out the same
>>>> Interest along different paths and the Interests eventually meet  
>>>> at a
>>>> single point (as in our example).  I think what we need is to
>>>> distinguish the duplicate Interests caused by looping and that  
>>>> caused
>>>> by branching.  For the former case, we shouldn't return any data.
>>>> For the second case, we could return data.  How to distinguish the
>>>> two cases?  One possible solution is for each router to append a  
>>>> hash
>>>> value to an Interest using its own unique number and the nonce in  
>>>> the
>>>> Interest.  This way it can quickly recognize Interests that have
>>>> looped back to itself and discard the Interests.  There may be other
>>>> solutions.
>>> 
>>> Here's another case: Node A sends out an interest, and the interest
>>> loops back to A. However, along the path that the interest has
>>> traveled, it has suppressed some interests from other nodes. When A
>>> receives this interest, it has no idea whether other interests are
>>> being blocked or not. So if you're willing to live with the overhead
>>> (see below), you may just return data anyway and not to differentiate
>>> whether it's due to looping or branching.
>>> 
>> Agree.
>> 
>> Fundamentally, the problem of dangling state blocking other users has
>> several contributing factors: path exploration, state aggregation,
>> etc.  We can look at the state aggregation factor.  Basically, in
>> order to avoid sending data unnecessarily (as in the above approach),
>> we need to differentiate dangling state that is blocking other users
>> from dangling state that's not blocking other users.   So suppose in
>> the example in our writeup, D has already forwarded A's Interest
>> toward its upstream and then it receives the second Interest from J
>> for the same data, D can immediately send another Interest upstream
>> with a flag that says this Interest actually represents multiple
>> consumers' requests.  Therefore, whoever receives the Interest will
>> not simply drop it as a duplicate based on the nonce (which is
>> meaningless now).   Note that this only needs to happen once.  Even
>> if D receives other consumers' requests for the data, it doesn't need
>> to send another Interest upstream.   This scheme will not respond
>> with data if A's interest doesn't block J's interest.
>> 
>> Does sending the second Interest incur additional overhead compared
>> to the Interest return scheme?  No.  Because in the Interest return
>> scheme, we still need to forward J's interest after clearing up A's
>> Interest, so there's no more message overhead.  Moreover, the data
>> will come back faster than the Interest return scheme.
> 
> Instead of using a special flag, D can make up a new nonce and send  
> the interest. D only does this when the number of pending interests  
> (for the same name) increases from 1 to 2. This is compatible with  
> other parts of the current system and no other changes are needed.
> 
> However, this doesn't completely remove the overhead, because A will  
> receive the second copy of the data from D.
> 
> This doesn't fix the excessive path exploration (when there's no  
> blocked interests) as you pointed out above.
> 
>>> 
>>>> The only downside as I can see is that perhaps some data
>>>> will be sent along paths that have dangling state that doesn't
>>>> actually block other users.  The data may still be useful for future
>>>> users though.
>>> 
>>> This overhead is my main concern about returning data vs. returning
>>> interests. When there's no blocked interests, the overhead of  
>>> replying
>>> data  is extra bandwidth and cache space. So exploring paths becomes
>>> more expensive. A node needs to be frugal in sending interests out  
>>> via
>>> different faces.
>>> 
>>> Ideally whether a data stays in the cache should reflect the data's
>>> popularity, i.e., the number of consumers that want the data. Now if
>>> we return data to duplicate interests, then it will reflect how many
>>> interests a consumer sends out. So the more-aggressively sought
>>> data may
>>> take the cache space of the more popular data, which reduces the
>>> effectiveness of cache.
>> 
>> The new scheme described above addresses the data overhead problem.
>> The data is only returned when it is likely to reach consumers that
>> still want the data.
>> 
>>> 
>>>> 
>>>> So I think we need to reach a common understanding on whether  
>>>> returns
>>>> are absolutely necessary in removing the dangling state.
>>>> 
>>>> Another dimension is to prevent dangling state in the first place.
>>>> What are the possible mechanisms there?  If the prevention is good
>>>> enough, do we still need to worry about removing the dangling state?
>>> 
>>> by prevention, do you mean something like forwarding all interests
>>> without suppression? I cannot think of anything else right now.
>> 
>> By prevention, I mean limiting "unnecessary path exploration" (the
>> consumer already has the data, but there is state in the network that
>> causes unnecessary path exploration", and "aggressive path
>> exploration" (the consumer sends duplicate interests along too many
>> paths).   The first one can be limited by using consumer-based retry
>> instead of router-based retry.  The second one I think needs to be
>> limited somehow by the network.  This is like dealing with a denial-
>> of-service problem.
>> 
>> Lan
>> 
>