What is the difference between a banyan network and a folded banyan network?

Question

What is the difference between a folded banyan and a regular banyan network. Teradata replication is apparently based on a folded banyan design, but many of the google top ranked results to explain folded banyan contain incorrect or contradictory information (hopefully they're not Bing-bait).

Answer 1

I notice your question was a long time ago, but hope this is helpful for the curious...

In the early days of telephones, each household had a line which ran to the telephone exchange. The human operator could patch your line to somebody else's line with a patch chord, direct from socket to socket. Obviously, for say, 100 lines, the operator needed 100 sockets, but only a handful of patch chords - corresponding to the maximum number of simultaneous calls that might be needed.

But, when mechanised with electro-mechanical switches, it was not possible to make a switch that could switch between too many possible connections, and the switching system needed to be modular and extensible. So, each individual switch could route a call to one of ten destinations. Each of those destinations could be another 10-way switch, and so on.

Each incoming line went to a 10-way switch. The first digit you dialled set that first switch, connecting the line to the next switch. The second digit you dialled, set that switch, connecting to the next. And so on, in turn. (See "stepping switch" or uniselector on Wikipedia.)

If you had (say) 1,000,000 lines, you'd need 6-digit phone numbers. Ostensibly, you'd need 1,000,000 x log(1,000,000) = 6,000,000 switches in the exchange, to connect any pairs. But notice, there might be fewer than 1,000 calls going on at any one time, so a great majority of the switches would be idle - making the exchange way more expensive than necessary.

So, a more clever scheme was needed - the Banyan network, named after the tree. It works pretty much the same as before, but now the first three digits route the million input lines, through the old 10-way switch network, in three stages, down to one of just 1000 intermediate points. The last three digits route the 1000 intermediate points back out through another expanding network of 10-way switches to the million lines. Like the human operator in the original exchanges, it can't cope with more than 1,000 simultaneous calls, and only then if the numbers called are fortuitous, with the first three digits all different!

But now notice... that the network of switches is symmetrical: 1,000,000 to 100,000 to 10,000 to 1,000 to 10,000 to 100,000 back to 1,000,000. With analogue telephony, switches are switches - they don't care which direction electricity is flowing through them, just so long as they are switched to the correct position. So the cunning step is to "fold" the network: 1,000,000 to 100,000 to 10,000 to 1,000 and back out on the same array of switches, on a different route (provided you can hook up the intermediate points appropriately). And hey - you have a folded Banyan network. It uses half the resources of a Banyan network, with only a bit of extra complication routing the calls.

Lastly, the biggest expense in such switching networks was the first layer of switches (1,000,000 of them in our example, one per line). On larger exchanges, they were replaced with "linefinders" - when you lift the telephone handset, the exchange connected you to the first free switch in a much smaller bank of switches. Since only 1,000 calls can be active at one time, only 1,000 switches are really needed in this first bank. (So you knew you had been allocated one, you got a "dial tone" when one was available.) Of course, many other optimisations and reductions were employed, that was just the start!

Nowadays, everything is digital of course, but ATM networks can and do use "folded banyan" topology, at least in broad shape. Many input points, multiplexed down to fewer and fewer intermediate nodes, then back out to many output points - using the same hardware, but with a different route to the appropriate output point. And the biggest users of ATM networks? Telephone companies!

Hope that helps.

Mi5ke

Answer 2

Banyan Network

The Banyan network is a type of multistage interconnection networks (MINs) frequently implemented as a basic building block in ATM switching fabric architectures. It is named so for its complex connecting patterns that resembles the Banyan tree's aerial root system.

As a variety of the Banyan network, the folded Banyan network is a buffered multistage burst cross-connect network that uses dual-redundant, bi-directional switch elements. A folded Banyan network has self-routing capability, modularity, linear scalibility, and enhanced fault-tolerance.

BYNET

The description found in the IT Toolbox article is supported by the Teradata Online Manual, Introduction to Teradata Warehouse, where it describes the BYNET as possessing high-speed logic providing bi-directional broadcast, multicast, and point-point communication with merge functions. It goes on to state there are multiple BYNETs to create a fault-tolerant environment and enhance interprocessor communication.

Hope this helps.