3 ms·
Giving everyone a guaranteed connection is a theoretical networking problem. The brute force solution as you've mentioned, is a crossbar switch, which is implem
by dragontamer 13y ago
Giving everyone a guaranteed connection is a theoretical networking problem. The brute force solution as you've mentioned, is a crossbar switch, which is implemented in O(n^2).
However, theoretical networking problems like this have been solved many years ago. The Clos Network can provide full duplex links at significantly better big-O
http://en.wikipedia.org/wiki/Clos_network http://en.wikipedia.org/wiki/Clos_network
I don't fully remember the details, but I believe you grow at approximately N*log(n). The problem is that the original Clos paper was published before big-O notation was invented... and that this was just "one other homework problem" that a professor gave to me about 5 years ago when I was in college.
So my memory is fuzzy, and the math is undocumented on the internet :-(
The internet is built on top of unreliable datagrams, which means the connectivity problem is even simpler. It satisfies the conditions of a Rearrangeably nonblocking Clos network. So the Big-O is even smaller than the above networking problem.
Clos wrote his paper specifically for phone connections. You cannot disconnect people for no reason while they're in the middle of a conversation. However, unreliable IP packets can be disconnected and rearranged, allowing you to use a cheaper form of the Clos network.
Either way, (like my professor from half a decade ago...), I'm going to leave the asymptotic complexity of "Strict Clos networks" and "Rearrangeably nonblocking CLOS networks" as an exercise up to the reader.
Mostly because I don't remember the solution... As a hint, replace the crossbar switches (in the wikipedia page) with a recursive Clos network and solve for the Recurrence relation. Use a 2x2 crossbar as the base case.
- waps 13y agoHave you thought about what such an architecture would mean bandwidth-wise on a WAN network ? I mean, dear God. This would actually require MORE links than full mesh. In other words, core network capacity (meaning total bandwidth in all links) if you have a clos scales even worse than n^2, with n the bandwidth you deliver to users. Even worse : you need as many long-haul links as you have subscribers (because your subscribers are connected to different locations). Is there question in your mind as to why ISPs don't do that ?