| Not absolutely sure I understand the problem so first let me try to
describe it.
You have a network of N nodes, with n links (n will be even since they
are paired, back and forth, but I don't think that that matters).
Bytes are transmitted between the N nodes over the n links following
paths which minimize the number of links that the byte needs to be
transmitted over. You want to know the number of bytes transmitted
(where a byte transmitted from machine A through machine B to machine C
is counted once). What you have is the number of bytes transmitted
through each of the n links, which means that you overcount each link.
If that is a fair summary, here is a solution.
First of all you can assume that every message is sent to an adjacent
node. That means that there is *no* overcounting and this provides
a maximum number of messages consistent with your n link-counts. That
maximum is simply the sum of your n link-counts.
The minimum is less trivial but not too hard.
Imagine a path from one machine, A, to another, B, over some number of
links,p (p is the length of the path). The path is directional and is
the minimum path from A to B. The maximum amount of traffic along that
(directional) path is the minimum number of bytes transmitted over any
of its links. Any byte transmitted from A to B will be counted (in the
maximum count) p times in the maximum count. The maximum number of
counts for the path in the maximum count is therefore, the p times
the minimum number of bytes transmitted over any of its links.
To obtain the minimum possible traffic we want to see how much over-
counting could possibly have occured. Here is the procedure:
Start with a "minimum count", C, of 0. Have a list of all N(N-1) paths.
Let B[i] be the maximum number of bytes transmitted along path i (see
above), and p[i] be the length of path i. Find that path, j, which has
a maximum value for B[j]*p[j].
Add B[j] to C. Subtract B[j] from each of the links in path j. At
least one of those links (more if there were ties for minimum traffic
link) will go to zero. Drop every path which includes those links
(including path j) from the list (you don't actually have to do this
since their maximum traffic becomes zero, but its probably better to
get them out of the way -- a table indexing paths by links might come
in handy).
Repeat until you run out of (non-zero traffic) paths. C will be your
answer.
I think that that will produce an absolute minimum, but I haven't
absolutely convinced myself. In practice it shouldn't matter: it is
certainly conservative enough so it can be taken as a practical lower
limit unless some very bizzare things are taking place in the network.
Hope that helps.
Topher
|
| I think that to get a tighter result than Topher's bounds in .3 you will need
more information. Some information of a heuristic nature that might help would
be:
- Stick a network monitor on each link and sample sources and destinations of
messages, which will let you construct a profile of the actual distribution of
the number of hops per message on the links
- Make assumptions about the magnitude of the traffic between any pair of
sites and use those assumption to derive the path length distribution.
The kinds of assumptions that you might be able to reasonably defend are:
* Assume the traffic between any pair of sites is proportional to the product
of the number of Digital employees at the two sites
* Assume the traffic between any pair of sites is proportional to the product
of the number of nodes at the two sites
* Any better assumption than the above based on the business activity and
interrelations of the sites - f'rinstance, information tends to flow out of
Geneva more than it flows in :-)
If you do any of the above, you wind up with a function p(L,d,n) which is the
estimated probability that traffic on link L in direction d is part of an n-hop
path; then, if the traffic on each link is T(L,d), your "best guess" at the
total amount of traffic would be SUM(T(L,d)*p(L,d,n)/n) where the sum is over
all L, d, and n.
|
| .3> Find that path, j, which has a maximum value for B[j]*p[j].
I'll call this the B*p greedy algorithm. It doesn't quite work.
If something like it *will*, then I think the expression should
be B[j] * (p[j] - 1). I'll explain.
Whenever B bytes of traffic on two adjacent links are 'connected' (i.e.,
made part of a longer path) by the algorithm, the bytes 'transmitted'
decreases by B. When links form a path of length p, there are only p-1
'connections' between the links, and the bytes 'transmitted' is reduced
by B*(p-1). Thus, I think B*(p-1) should be better.
Also, the following is a counterexample to the B*p greedy algorithm (but
note that the B*(p-1) greedy algorithm minimizes the transmissions).
X ----- Y ----- Z
5 2
The B*p greedy algorithm takes:
5 bytes connecting X-Y, then
2 bytes connecting Y-Z,
for a total transmission of 5+2 = 7.
The B*(p-1) greedy algorithm takes:
2 bytes connecting X-Y-Z, then
3 bytes connecting Y-Z,
for a total transmission of 2+3 = 5.
|