Subject: RE: [nemo] Re: BU storms when MR does RO on behalf of LFN's (was: Re: more comments on the RO Taxonomy draft)

From: "Pascal Thubert \(pthubert\)" <[email-masked]>
Date: Wed, 6 Oct 2004 11:44:39 +0200

Alex:

Let's take examples
-------------------

Case 1: MR joins a tree.

Say a MR with an LFN attaches into an existing tree at depth 3. so we
have:
Root-MR <- MR1 <- MR2 <- MR . Say LFN starts a connection with CN, and
say we want to optimize that.

With the assumptions in the quoted text, our MR has to bind its MNP to
the CN with its careof. But CN does not know how to reach that careof,
which is from MNP2 (MR2's MNP). So MR2 has to bind MNP2 with its careof
with CN. Recursively, MR1 and root-MR have to bind to CN as well.
So we need 4 bindings, which have to be synchronized while maintained
individually.

On the other hand, if you look at RRH, only the MR that moves sends a
binding. The BU traces the way out. That's a single BU, with a snapshot
of the tree at the time of the packet. No state in the intermediate
routers. No additional BUs that the CN has to correlate together. 

Case 2: Root-MR now changes its point of attachment.

With the assumptions in the quoted text, it has to send one BU to all
CNs of all the LFNs in the tree. This causes a burst on the network. If
there's no special code to support that in the MR, packets might even be
discarded inside the box because the output queue is saturated. Each BU
that gets dropped means a hung connection.

On the other hand, if the same amount of BUs was issued by the MRs to
which the LFNs are attached, they would arrive in a more dispersed
manner, which would help digesting them.

With RRH, MRs might delay the BU for a small amount of time in case
there's upstream traffic for that CN that would update the RRH cache in
the CN in-band, avoiding many of the BUs. 

Conclusion
----------

With the assumptions in the quoted text, for each (LFN, CN) that's ROed
binding, each MR above the LFN in the nested structure needs to send a
BU to all these CNs when it moves, so that a CN has the chain of BUs
that enables building a path down the tree. 

When a MR moves to a new place in the tree, it has to rebind for all CNs
down its tree, as we said. But then all MRs above it have to do it too.
And MRs up its previous location have to stop doing it, otherwise the CN
is very confused.

There no mechanism in NEMO for a MR to discover and maintain states
about MR-CN RO binding down its subtree. In the context of that chapter,
it means snooping. 

The text speak to the good sense and means, in short, how deep do you
want to go before you try something else?

> This is to say I do not think a BU storm is an inconvenient of having
MR
> send BU's on behalf of its MNN's, or LFN's.

The BU storm problem mentioned here is *not* that it would be wrong to
do RO from the first MR as opposed to LFN (where did you read that?).
It's about more then the minimum BUs being sent, and BUs being sent by
the wrong MRs.

Pascal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of Alexandru Petrescu
> Sent: mardi 5 octobre 2004 19:24
> To: Chan-Wah Ng
> Cc: IETF NEMO WG
> Subject: [nemo] Re: BU storms when MR does RO on behalf of LFN's (was:
Re: more comments on
> the RO Taxonomy draft)
> 
> draft:
> > An intermediate MR would keep track of all the pending
communications
> >  between hosts in its subtree of Mobile Networks and their CNs, and
a
> >  binding message to each CN each time it changes its point of
> > attachment.
> >
> > If this was done, then each CN, by receiving all the binding
messages
> >  and processing them recursively, could infer a partial topology of
> > the nested Mobile Network, sufficient to build a multi-hop routing
> > header for packets sent to nodes inside the nested Mobile Network.
> >
> > However, this extension has a cost:
> >
> > 1.  Binding Update storm
> >
> > when one MR changes its point of attachment, it needs to send a BU
to
> > all the CNs of each node behind him. When the Mobile Network is
> > nested, the number of nodes and relative CNs can be huge, leading to
> > congestions and drops.
> 
> related, not relative (minor).
> 
> What is more precisely the network on which numerous BU's will act as
a
> storm?  It is actually the segment between TLMR and the last common
> router on the path between the new AR and all CN's.  If you look
> closely, it is exactly the same common path that all packets (not only
> BU's to CN's) between all MNN's and their CN's will impose a stress.
> 
> Imagine a train with many people watching different videos over
Internet
> approaching the new AR.  That new AR's upstream connection is
relatively
> quiet (as preparing for a storm).  When that AR receives the train's
> TLMR suddenly all those BU/BAck's followed by application-level
packets
> will storm that common segment.  However, the number of BU/BAck's is
> much smaller than the number of video-streaming packets.  The "storm"
> has a small BU/BAck component.  Eliminate that component and it's
still
> "stormy".
> 
> This is to say I do not think a BU storm is an inconvenient of having
MR
> send BU's on behalf of its MNN's, or LFN's.
> 
> And, if a MR-RO-for-LFN's BU's were stormy in the sense like that of
> RS's of hosts powering up on a common subnet, would an exponential
> backoff algorithm limiting and randomizing the order of sent BU's
apply
> as a solution.
> Alex

---

From: Christophe Janneteau <[email-masked]>
Date: Wed, 06 Oct 2004 14:45:01 +0200

Salut Pascal,

Some comments on your email below.

> Let's take examples

Right. But note that the applications are still maintained even if the 
full path for RO is not known at CN (e.g. binding for MR2 missing), and 
the path would still be partially optimized.

That said, there may be some ways to speed up and "synchronize" the 
sending of the bindings of nested MRs to CN, so that CN gets all of them 
"at once".

> routers. No additional BUs that the CN has to correlate together. 

RRH may have advantages, but also has drawbacks (e.g. significant 
departure from Basic-NEMO BU semantic, determining optimun number of 
slot in RRH header, security, etc...). BTW, It may be too early  now to 
start comparing solutions, this may turn in an endless thread :)

When doing this exercise one should make sure that all the various 
criterias for comparison are taken into account. They also need to be 
defined first...

> CNs of all the LFNs in the tree. This causes a burst on the network.

But only Root-MR would sent BU, thus zero overhead is introduced inside 
the aggregation while this would not be true with RRH. If RRH is to be 
used only in BU messages, then lower MRs in the aggregation need to 
discover Root-MR movement in order to send BU...thus extra signalling. 
In addition all MRs behind Root-MR will then need to send BUs to update 
CNs with their optimized path, thus extra signalling.

If in-band RRH (i.e. in all data packets) is used then overhead of RRH 
header takes place for each packet?...

[...]

> the CN in-band, avoiding many of the BUs. 

Well, with MR-to-CN BU, only Root-MR would need to send the BU to the 
CNs, and of course could arrange not to send the simultaneously to avoid 
   overhead on the TLMR-RA link...

> Conclusion

No, I don't think CN will be confused if it still has bindings for the 
mobile routers up to MR's previous location. As soon as CN gets the new 
MR's binding, it knows that the MR has moved to a new location. This new 
location could match the prefix of a new upper mobile router. If CN has 
a binding for this new upper-MR is will use it, and route packet along 
new-upper-MR CoA and MR CoA. Entries for old-upper-MR is not used and 
does not arm at all....

Christophe.

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 06 Oct 2004 14:41:02 +0200

Pascal Thubert (pthubert) wrote:
>  have: Root-MR <- MR1 <- MR2 <- MR . Say LFN starts a connection with
>  CN, and say we want to optimize that.
> 
> With the assumptions in the quoted text, our MR has to bind its MNP 
> to the CN with its careof. But CN does not know how to reach that 
> careof, which is from MNP2 (MR2's MNP). So MR2 has to bind MNP2 with
>  its careof with CN. Recursively, MR1 and root-MR have to bind to CN
> 
What's "recursive" here?  I see "successively" but no "recursion". (????)

> as well. So we need 4 bindings, which have to be synchronized while 
> maintained individually.

I don't understand, what's the problem with being synchronized while
being maintained individually?

>  binding. The BU traces the way out. That's a single BU, with a 
> snapshot of the tree at the time of the packet. No state in the 
> intermediate routers. No additional BUs that the CN has to correlate
>  together.

Advertising for a solution has no place in problem discussion.  If you
want, we can discuss RRH separately, in a separate thread.

>  If there's no special code to support that in the MR, packets might
>  even be discarded inside the box because the output queue is 
> saturated. Each BU that gets dropped means a hung connection.
> 
> there's upstream traffic for that CN that would update the RRH cache
>  in the CN in-band, avoiding many of the BUs.
> 
> 
> Conclusion ----------
> 
> With the assumptions in the quoted text, for each (LFN, CN) that's 
> ROed binding, each MR above the LFN in the nested structure needs to
>  send a BU to all these CNs when it moves, so that a CN has the chain
>  of BUs that enables building a path down the tree.
> 
> When a MR moves to a new place in the tree, it has to rebind for all
>  CNs down its tree, as we said. But then all MRs above it have to do
>  it too. And MRs up its previous location have to stop doing it, 
> otherwise the CN is very confused.
> 
> about MR-CN RO binding down its subtree. In the context of that 
> chapter, it means snooping.
> 

I think the text speaks in a way that says RO is a problem and RRH is a
solution.

>> This is to say I do not think a BU storm is an inconvenient of 
>> having MR send BU's on behalf of its MNN's, or LFN's.
> 
> The BU storm problem mentioned here is *not* that it would be wrong 
> to do RO from the first MR as opposed to LFN (where did you read 
> that?). It's about more then the minimum BUs being sent, and BUs 
> being sent by the wrong MRs.

I read in the taxonomy draft that having an MR to send BU's on behalf of
the hosts in the subtree has a cost: BU storm (and 4 other costs too);
section 6.2.

(BTW, what do you call "processing BU's recursively" and "recursive
  fashion"?  What module/part/function calls upon itself?  I don't see
  any recursion in processing several incoming BU's and CN _iterating_
  through the BC to build a RH; anyways, be it iteration or recursion, I
  don't see the computation burden...)

Alex