How to calculate backplane throughput given an arbitrary list of network links?

Question

Given a device (router lets say) that can take an arbitrary number of network connections how much backplane throughput should be allocated to a given set of network connections.

(we assume all of these are symmetrical, and further to simplify the discussion we assume we're only counting each interface once, instead of once for TX and a second time for RX)

Also we assume traffic is always TRANSITING the router, never destined to it directly. So any packets that come in one interface must leave another. There is no "loopback" function here.

examples:

a single 1G link. It can't send any traffic to anywhere so backplane allocation is ZERO.

two 1G links. one can perfectly saturate the other, so total backplane allocation should be 1000mbps.

a single 1G link and a single 50M link. total allocation is 50mbps since the most traffic the 1G link would ever be able to send is 50mbps.

My intuitive assumption is there must be a "simple" formula to get this, something easily suitable for an excel spreadsheet or the like, but I haven't been able to come up with anything.

The mental algorithm I use to come up with the "right" answer is essentially picking the biggest link, stack the others against it until it's "saturated", then repeating with the next largest remaining link, etc. any throughput left over from the last interface at the end is discarded.

Here's the test cases I've come up with, my official answer, and the various results I get from the various strategies I've tried.

case	My answer	sum	sum / 2	'sum the minimums of the sorted pairs'	sum - max
4x50m	100	200	100	100	150
1x100,3x50	100	250	125	100	150
2x125, 2x50	175	350	175	175	225
1x1000,2x200,1x50	450	1450	725	250	450

Answer 1

Revision: Thanks to help from JvdV and EDS in this connected question, I have added a way to accept the text inputs shown in the Cases from your examples.

To get the correct backplane bandwidth, you need to find the right combination of connections that will total to half of the aggregate bandwidth. For example, if you had connections of 1,2, ... ,6, you are looking for any combination that adds to 21/2=10. e.g., 6,4 gets you there.

i.e., the correct answer will approach the half of the sum of all bandwidth. While sum/2 would provide a quick & dirty approximation, it can be wildly off if the number of connections is small and their make-up is asymmetrical. e.g. the case that you presented as 1x1000,2x200,1x50 has a backplane bandwidth of 450 - far from 725.

To get to the correct answer in all cases, requires some form of iteration, which is not supported in Excel functions. You can create real iteration through LAMBDA recursion (not yet released) or VBA. But there is also another way: iteration can be emulated through functions that contain iterations.

You can imagine this as a method of 'folding'. What we are trying to do is to put the connections on either side of a piece of paper and fold the paper where the left and right side numbers cancel each other. The sum of the numbers that get canceled are the backplane bandwidth. The residual is waste. For example: connections of speeds 1,2,3,4,5, and 6, would have 4 & 6 on the left side and 2, 3, & 5 on the right. The 1 has no match and becomes residual, like this:

There are obviously 2^6-2=62 possible arrangements on the paper and we have to find the one that best balances them. I came up with two approaches which I will call:

• Brute-force Folding : create every possible fold and search for the one that gets half the summation on a single side.
• Adaptive Folding : sort the connections, make an initial fold and use it to determine the next fold, rinse, repeat.

Brute-force is achievable as a LET formula without iteration. Adaptive works, but requires iteration or possibly recursion, so it would only be possible with a LAMBDA or VBA UDF tmk.

Forming the Input

Connection Array

In all cases we need to normalize the input into an array of connection speeds. e.g.:

That's probably not the best user interface for the formula because it would be tedious and take up a lot of cells to write all those out. So there are two possible alternatives:

Connection Table

Connections	of Speed
1	1050
2	400
1	200
1	100
1	50

Comma Delimited Strings -as you showed in your example

1x1050,2x400,1x200,1x100,1x50

So, the front part of the formula will simply form the input into a Connection Array.

The rest focuses on the calculation mechanics.

Brute-Force Folding

Using a Connection Table as input, you can do:

=LET( connectionTable, A2:B6,
       connections, INDEX(connectionTable,,1), speeds, INDEX(connectionTable,,2),
       elements, SUM( connections ),  eSeq, SEQUENCE( elements,,0 ),
       bySeq, SEQUENCE( ROWS( connections ) ),
       byPos, MMULT( --(bySeq >= TRANSPOSE( bySeq )), connections ),
       conx, INDEX( speeds, IFERROR(MATCH( eSeq, byPos, 1 )+1,1)  ),
       bpBW, LET( array, conx,
                  r, ROWS( array ), c, 2^(r-1)-1, s, SUM(array),
                  cSeq, SEQUENCE(1,c,1),
                  idx, MOD(SEQUENCE(r,c,0),c)+1, e, 2^SEQUENCE(r,,r-1,-1), foldArray, MOD(INT(idx/e),2),
                  p, MMULT( SIGN( SEQUENCE( 1, ROWS( foldArray ) ) ), array*foldArray ), n, s - p,
                  c2z, MATCH( MIN( ABS( p-n ) ), ABS( p-n ), 0 ),
                  result, MIN( INDEX( CHOOSE( {1;2}, p, n ), , c2z ) ),
                   result  ),
       bpBW )

Where connectionTable is a table containing the number of connections of each speed as described above. Here is an illustration of 1x1050,2x400,1x100,1x50 which will yield a backplane bandwidth of 1100 with no residual. It effectively puts 1050 and 50 on one page and the rest on the other.

Notes

I nested the LETs and broke out their results of result and bpBW to make it easier to inspect each part. This can be consolidate further, but that would make it harder to optimize and understand. The calculations can also be simplified a little bit by using s/2 instead of creating an n array, but that makes it harder to explain and to break out and examine, so I did left this formula in its most readable and understandable format even if it is quite long.

How it works

The first LET starts by reshaping the Connection Table input into a Connection Array which is an expanded list of connection speeds.

The second LET is the takes the array from the first LET and calculates the bpBW (backplane bandwidth) as result.

It does this by generating an array of binary representations of each possible fold called the foldArray. It then multiplies this times array to create a matrix of values and that matrix is summed column-wise to create a single-row array called p or the positive side of the fold. It also calculated n, the negative side of the fold by taking s (the sum of all connections) - p. (This can be simplified and eliminated by using s/2 as a reference, but I kept n in place for inspection to understand how the approach actually works.)

Now that we have both sides of the fold, the residuals can be calculated as ABS( p - n ). We are looking for the column with lowest residual or "closest to zero" c2z. At that column, we need to take the smaller of the p and n values. That min is the backplane bandwidth.

Putting it All Together

This diagram shows how it works. The blue sections are showing how the inputs can be shaped into a Connection Array and the green section shows how the computations are rendered.

Variations on Inputs

The version above accepts a Connection Table as input. Here are different versions of the formula for each possible way that you might want to accept the input:

Connection Array

=LET( array, A2:A7,
         r, ROWS( array ), c, 2^(r-1)-1, s, SUM(array),
         cSeq, SEQUENCE(1,c,1),
         idx, MOD(SEQUENCE(r,c,0),c)+1, e, 2^SEQUENCE(r,,r-1,-1), foldArray, MOD(INT(idx/e),2),
         p, MMULT( SIGN( SEQUENCE( 1, ROWS( foldArray ) ) ), array*foldArray ),
         c2z, MATCH( MIN( ABS( s/2-p ) ), ABS( s/2-p ), 0 ),
         bpBW, MIN( INDEX( CHOOSE( {1;2}, p, s-p ), , c2z ) ),
       bpBW )

Comma Delimited e.g. "1x100,2x500,3x200"

=LET( case, A11,
       x, FILTERXML("<t><s>"&SUBSTITUTE(SUBSTITUTE(A11,",","x"),"x","</s><s>")&"</s></t>","//s"),
       connectionTable, INDEX(x,SEQUENCE(COUNT(x)/2,2)),
       connections, INDEX(connectionTable,,1), speeds, INDEX(connectionTable,,2),
       elements, SUM( connections ),  eSeq, SEQUENCE( elements,,0 ),
       bySeq, SEQUENCE( ROWS( connections ) ),
       byPos, MMULT( --(bySeq >= TRANSPOSE( bySeq )), connections ),
       conx, INDEX( speeds, IFERROR(MATCH( eSeq, byPos, 1 )+1,1)  ),
       bpBW, LET( array, conx,
                   r, ROWS( array ), c, 2^(r-1)-1, s, SUM(array),
                   cSeq, SEQUENCE(1,c,1),
                   idx, MOD(SEQUENCE(r,c,0),c)+1, e, 2^SEQUENCE(r,,r-1,-1), foldArray, MOD(INT(idx/e),2),
                   p, MMULT( SIGN( SEQUENCE( 1, ROWS( foldArray ) ) ), array*foldArray ),
                   c2z, MATCH( MIN( ABS( s/2-p ) ), ABS( s/2-p ), 0 ),
                   result, MIN( INDEX( CHOOSE( {1;2}, p, s-p ), , c2z ) ),
                    result  ),
       bpBW )

And here are the results applied to an extended version of your cases:

case	Brute-force
4x50	100
1x100,3x50	100
2x125, 2x50	175
1x1000,2x200,1x50	450
1x1050,2x400,1x200,1x100,1x50	1100
1x1050,2x400,1x150,1x100,1x50	1050
2x1000,2x200,1x50,1x100	1250
1x200,3x125,4x400,3x1000,2x2000	4575
1x130,1x270,1x410,1x390,1x300,1x120	810
1x170,2x270,1x210	440
1x130,1x270,1x180,1x220	400

Adaptive Folding

It would be a lot of work to fully describe adaptive folding or build it in VBA and I think the above answers your question already, so I will keep this brief.

The problem with the Brute Force approach is that it computes all possible arrangements. A 16 port device would have a 524,272 cell array. 24 ports is 201 million, 32 is 68 billion, and 48 port would be 6.8 quadrillion. When you reach such levels SUM/2 is probably already a good enough approximation, but if you really had to have a correct answer, Brute-Forcing it would break your machine.

So an alternative is to search for the best-fit combination of connections that form SUM/2 of aggregate bandwidth without 'boiling the ocean'. The method is:

1. Sort the Connection Array - descending.
2. Start subtracting elements 2... to X from element 1 until the sum is <= 0. Then set a variable B to equal the sum of the bandwidth of elements 2... X - Residual (if there is any).
3. Go to element X+1 and add the Residual and then repeat Step 2 above by adding the new B to the old B. Keep repeating 2 and 3 until all connections have been reviewed. B is the answer.

This reduces a 48 port connection from a 6.8 quadrillion array to at-most a 48^2 array and 47 iterations. In all likelihood, the algorithm will end in less than 10 iterations on such a large device.