Earlier quoted context omitted.
The netflix data itself points to a gradual lowering of bandwidth to their service. Now here's 2 scenarios : 1) Verizon decided to enter some router configurations that affect the packet forwarding to Netflix (well, most likely FROM netflix, as the internet is not actually symmetrical). What we should see as a result of this is a sudden change in bandwidth. 2) The load on the interfaces in between is changing, either…
> The basic problem is that a linear increase in bandwidth for the customer results in an exponential increase in costs for the ISP > N * (N - 1) =~ N^2 (assuming full duplex links, which would be generally correct for the internet) 1) N^2 is not exponential, it's polynomial. 2) Expanding capacity isn't even N^2, it's just linear. If you double each residential customer's bandwidth, you "only" have to double the capa…
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
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.