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.