Subject: Re: [mobile-ip] Some Analysis

From: James Kempf <[email-masked]>
Date: Fri, 27 Apr 2001 10:09:33 -0700 (PDT)

Sami,

>
>When analysing the non-hierarchical case, you are summing all the
>delays to calculate the latency.  Wouldn't the binding updates
>(or registration requests) be sent in parallel to both HA, and all
>CNs?  Thus the latency would be a maximum of a set of numbers, not
>a sum ?
>

You're right, but the same can be said of the hierarchical case.
LMM(i) sends the BU to LMM-T independently of replying to MN,
so MN doesn't necessarily have to wait.

Also, I think MN would at least have to wait for the BU-ack to the HA 
before proceeding with sending the BU to the CN. So these would
be sequential.

In any case, I think this is a worst case analysis, there is potential
for optimization that could probably be developed. I basically
worked it out yesterday afternoon in a half hour, a little more time
with a white board could probably sharpen it up. If there is any
interest in the working group, I'm up for continuing, though I 
don't know how far one could get without having to resort to
simulation.

Thanx for your reply. It's such a relief to be able to do some
technical discussion around this issue.

		jak

---

From: Wolfgang Schönfeld <[email-masked]>
Date: Mon, 30 Apr 2001 19:32:17 +0200

Please see attached file...
-- 
Wolfgang Schoenfeld, GMD-IPSI, +49 6151 869 865

Many thanks again to Jak for triggering this discussion!!!
The many replies he received prove high interest.
Let me mention one more, I think, important point.
As Claude has shown in his INRIA report,
the mobile node's mobility has to be taken into account
when talking about performance of (non-)hierarchical mobility support.
Let me try to illustrate this by an example.

Assume you have a network with tree-like topology (like a cellular network)
where mobile nodes attach to the leaves (base stations).
Hierarchical mobility support means that each node is a mobility agent (HA, FA, or MAP).
When a mobile node MN moves from leaf A to leaf B,
exactly the mobility agents on the (unique!) path from A to B
are affected by the move, i.e. have to change the bindings for MN.
Let us call the length of that path the "distance" between A and B
(it is just the distance in the graph-theoretic sense)
and consider it as a measure for binding update performance
(obviously, more parameters come into play, see Jak's e-mail).

In order to arrive at some numbers :-) ,
consider as topology a complete binary tree of height n 
and, for a better understanding of the following,
draw it as a wheel of radius n where
- the root becomes the nave
- the branches become the (branching!) spokes
- the leaves are arranged on the felly
and MN moves on the felly.
(Had to use a German-English dictionary - hope the notions are correct.)
By accident, such a move may be very short
(of distance 2 in case of two base stations served by the same controller)
or very long (of distance 2n if the root/nave is traversed).
In order to have some better average cost analysis,
let us consider complete travels around the wheel,
i.e. permutations of the leaves/felly.

If MN proceeds from each leaf to its neighbour, say clock-wise, around the wheel,
then the average distance is (2^n-1)/(2^(n-2)) which approximates 4 .
(The number 2^n-1 is the sum of all distances since each part of a spoke
is traversed by some binding update excactly twice.
And 2^(n-2) is the number of leaves, i.e. of moves.
That the average length of a binding update is constant
is plausible since the very short distance of 2 happens in 50% of all cases.)
On the other hand, it is easy to imagine travels
where each move has distance 2n because it crosses the nave.
Altogether, binding updates in the hierarchical case 
have to traverse paths of lengths between 4 (constant) and 2n 
(linear in the diameter of the network).

Now let us only sketch non-hierarchical mobility support, i.e. Mobile IP.
Here, you fix a leaf (home agent) on the felly,
and all binding updates have to go to it.
But this means that at least 50% of them have to traverse the root/nave,
i.e. most cases are worst
and binding updates always have costs linear in the network diameter.

Let me finish by giving my peronal interpretation of these numbers
(and I would be very happy to receive critical replies):
Hierarchical mobility support is, in some cases, provably better
than the non-hierarchical counterpart.
But these cases do not occur very often.
Hence it is questionable to attempt an optimization -
it would have an effect only in rare cases.

Maybe, one should distinguish mobility
by feet, by car/train, and by plane
because they show different travel characteristics in the above model.
But, probably, this question is out of the scope of a theoretical analysis
and has, as Jak suggests, to be attacked by simulation.