How many DMF's a router needs *in the minimum possible configuration* depends
on whether or not it is a border router.
For routers which are not border routers, they need one DMF out to a border
router (i.e. up), and that's it. Traffic to other objects inside the area can
be handled by sending it to the border router, which will send it back to the
correct object. (Hey, it's not very optimal routing, but I'm talking about
the *minimal* set, right?)
Border routers require one DMF to each constituent object in their area, other
than ones which the border router is already a constituent of. If an object is
in itself an area (i.e. a sub-area of the area in question), with multiple
border routers, they only need one DMF to that object, to any one of the
border routers of the sub-area.
Obviously, routers which are border routers for a K level area are also either
border or interior routers in a K+1 level area; if interior, they will need
only the 1 DMF, but if they are border routers at that level as well they will
need DMF's for all objects in that K+1 level area which they are not
constituents of.
Let's talk about an area which has a total of B border routers, and I interior
objects. A percentage P of the objects are themselves sub-areas of A, so there
are (1-P)*I interior non-sub-area objects, and P*I sub-areas. For the
sub-areas, each has an average of S border routers. For the sake of
simplicity, let's assume that *none* of the border routers is part of any
sub-area. So, the resulting numbers are worst-case, since any border router
which *is* part of a sub-area removes the need for a DMF to that sub-area; the
packet is already in that sub-area.
Each of the B border routers has I DMF's associated with this area, for a
total of B*I. Each of the interior routers has single DMF. The non-area
routers contribute (1-P)*I, and border routers of sub-areas contribute P*I*S.
So, the total number of DMF's Ft associated with that area in the area is:
Ft = I * (B + (1-P) + P*S)
Exactly how fast this will grow as the area grows is thus somewhat tricky, and
can't be computed without some assumptions about the relationship between B
and I, etc. However, we can take a crack at it. We can pretty well assume the
P is a constant, and we can assume either i) that S is a constant, since the
area grows by creating more sub-areas, not making the existing sub-areas
larger, or ii) that S grows at the same rate as B (since they both represent
the count of border routers, just at different level). Let's take the worst
case, which is that O(B) = O(S). The growth rate of the total number of DMF's,
O(Ft) is:
O(Ft) = O(I) * O(c1 + (1 + P)*B)
or:
O(Ft) = O(I) * O((1 + P)*B)
or:
O(Ft) = O(I) * (1 + P) * O(B)
I don't know the exact formula for the number of border nodes on a graph with
a constant degree of connection between the nodes, but I'll hazard the guess
that the number of border nodes will grow as the square root of the number of
total nodes. (Handwave justification for this is that it's probably the same
as the ratio of the circumference of a circle to the area of a circle, since
you can model a graph with a fixed degree of connectivity among the nodes as a
geometrical figure where each node takes a fixed area, and thus the area is
proportional to the number of nodes.) So, that gives us that O(B) is
O(sqrt(I)). So, finally we get that:
O(Ft) = (1 + P) * O(I^1.5)
or just plain O(I^1.5) for short. Now, that's for one level. Note that if we
grow the system by adding more levels of area (a likely happening), rather
than increasing I, then I is a constant, so O(I) = 1, so there is no growth in
Ft at all!
Now, that was the total number of DMF's in the area. That's a relatively
uninteresting number, for reasons which should be intuitively obvious to
everyone. What's *important* are the number of DMF's which end in a router,
and the number of DMF's which go through (i.e. require state for storage)
interior routers.
Lets look at the number of DMF's which end in a router, Fe, first.
For interior routers, the count is the 1 outgoing DMF, plus incoming DMF's
from the border routers. There are two subcases: for routers which are not
border routers of sub-areas, all B border routers have a DMF to the router,
so there:
Fei = (1 + B)
For routers which are border routers of sub-areas, the incoming DMF's are
shared among the border routers of the sub-area; assuming the distribution
is even, this gives us:
Fes = (1 + B/S)
Note that in the worst case distribution, this is only as bad as the case
above, so we can ignore this case.
The border routers are a slightly harder case. There are I outgoing DMF's,
and the incoming DMF's from the interior routers are shared among all
the border routers. Again, assuming an even distribution, this gives us:
Feb = (I + ((1-P)*I + P*I*S)/B)
or:
Feb = I(1 + ((1-P) + P*S)/B)
Again, we can assume that P is a constant, and we can assume the worst case,
which is that O(B) = O(S). This gives us that:
O(Feb) = O(I) * O(1 + (c1 + P*B)/B)
or:
O(Feb) = O(I) * O(1 + P*B/B)
or:
O(Feb) = (1 + P) * O(I)
This makes intuitive sense, since we know that the DMF's from interior routers
which aren't border routers of sub-areas are shared among all border routers
of that area, whereas each border router has to maintain a DMF in to each of
those routers, so that term drops off in importance. On the other hand, since
the number of interior routers which are border routers of sub-areas are
growing as fast as the number of border nodes, that term will remain.
Since we know that O(B) = O(sqrt(I)), in the long run, as areas get large, the
particular Fe which will experience the highest growth rate is Feb, i.e. the
number of DMF's which end in a border router. This also makes good sense. That
growth rate is just plain old O(I) for short.
The analysis above only counts DMF's for this area. If a router is a border
router for a number of levels of area, it will have:
Febm = (1 + ((1-P) + P*S)/B) * sum(Ii), i=l...m
where Ii is the value of I for the area at level i, and l and m are the bounds
on the number of areas that router is a border router for. In the worst case,
l=0, and m=L, where L is the maximum number of levels in the system. So,
for that worst case:
Febm = (1 + ((1-P) + P*S)/B) * sum(Ii), i=0..L
If, for simplicity's sake, we assume that all Ii average I, then:
Febm = (1 + ((1-P) + P*S)/B) * I*L
and, using the same analysis as above:
O(Febm) = O(I) * O(L)
Exactly what O(I) and O(L) are remains to be seen, but we can grow the system
be holding I constant, and growing L. As a matter of fact, if N is the total
number of nodes in the system, and I is constant, then O(L) = logN. So, in
this worst case scenario:
O(Febm) = O(logN)
if we don't grow areas, but instead grow the number of levels.
To turn to the average number of DMF's through an router, Fa, we can calculate
that if we know the average path length for a DMF. The average number of DMF's
can be given by the formula:
total number of DMF's * average DMF length
Fa = -------------------------------------------
total number of routers
The average path length, A, for a graph of fixed degree (i.e. one in which
nodes have the same average number of arcs to neighbouring nodes, independant
of the size of the graph) is logN (where N is the number of nodes). [Chen 86]
This seems like a reasonable model to use, since physical routers have a
small, relatively constant average number of interfaces.
We can use the number of interior objects (I), plus the number of border
routers (B), as the number of nodes, in calculating the path length. So,
that gives us:
A = log(I + B).
However, if we assume that O(B) = O(sqrt(I)), as above in the calculation of
Ft above, then B tends to become irrelevant, and:
O(A) = O(logI)
We already deduced that the total number of flows, Ft, was:
Ft = I * (B + (1-P) + P*S)
and that:
O(Ft) = O(I^1.5)
What exactly to call the "total number of nodes" is a little tricky, and here's
where I have to do some even more energetic handwaving than usual. Strictly
speaking, we can't simply use the number of interior objects (I), plus the
number of border routers (B). The problem is that for the cases where a DMF
traverses a sub-area, it will traverse two border routers on that sub-area,
as well as some interior routers in that sub-area.
However, I will make the simplifying assumption that the "path length"
calculation above already made the assumption that each sub-area counted as
one "node", and errors above and below the division will cancel out. So,
that gives us that the total number of routers, R, is:
R = (I + B),
and again, assuming that B becomes irrelevant:
O(R) = O(I)
So, since:
O(Fa) = (O(Ft) * O(A)) / O(R)
substituting in for O(Ft), etc, gives us that:
O(Fa) = (O(I^1.5) * O(logI)) / O(I)
or:
O(Fa) = O(sqrt(I) * logI)
Again, of course, this only counts the flows from one level.
I could make some assumptions based on the idea that we will use an
"interstate" physical toplogy where long-distance connectivity is provided by
a physical mesh at the high levels, not by using the "local" meshes down an
abitratily large numebr of levels, but only a few levels down, but my head
started to hurt at that point; let's just do the simple thing for now.
If we assume that the worst case is that we have flows from all levels, L,
giving us a new count of DMF's, Fat, for the worst case we will make the above
quantity worse by a term of O(L), i.e.:
O(Fat) = O(sqrt(I) * logI) * O(L)
As stated above, exactly what O(I) and O(L) are remain to be seen, but again,
we can grow the system by holding I constant, and growing L. Again, I is
constant, and O(L) = logN, so, again in this worst case scenario:
O(Fat) = O(logN)
if we don't grow areas, but instead grow the number of levels.
I suppose I could sit and think about what the relationship between N, L and I
would be, if we decide to grow areas, and not the number of levels, but I
don't think it's worth it. However you slice it, these are *not* major growth
rates.