On Fri, 9 Apr 2004, Eugen Leitl wrote:
Internet is mostly a tree (if you look at the connectivity maps).
Not at all. A tree has a root; the Internet doesn't have one. Instead you have several thousand autonomous systems interconnecting at a large number of peering points.
A modestly high dimensional grid of some billion nodes doesn't look like this: http://members.easynews.com/L4/opte/www.opte.org/maps/static/1069646562.LGL.... This is clearer: http://research.lumeta.com/ches/map/gallery/wired.gif
Yes. I know what a tree is, and I am quite familiar with structure of the Internet. These very pretty pictures certainly look like the Internet I am familiar with, but don't resemble trees.
For a long time, most traffic between European countries was routed through Virginia. This has improved only in the last few years. In the same way a lot of Pacific traffic still runs through California. In each case what matters is not geography but politics and quixotic regulations.
You're proving my point. The network started as a bureacratic, static, tiny, suboptimal configuration. As it grew bigger, and started participating in economy it started minimizing itself. This isn't just connectivity, but goes down to the protocol level. We know IPv6 isn't the answer, mostly because it is largely geography agnostic, can't handle nodes moving with orbital speeds (or even a speeding car), doesn't handle interplanetary latencies and isn't local-knowledge routed/switched in general. It also can't handle relativistic speed cut-through, which is the killer requirement.
Over the last 30 years or so, various people have hypothesized about what the "killer requirement" might be. To the best of my knowledge, all have been wrong. The Internet is quite obviously optimizing along certain lines. However, these lines don't follow any geographical geodesic, which was my point. And it is only obvious what the lines of optimization are in hindsight ;-)
Within most countries the same sort of illogic applies. In the UK, for example, most IP traffic flows through London, and within London most IP traffic flows through the Docklands area, a geographically small region of East London. It's fractal: even within Docklands, almost all traffic flows through a handful of buildings, and there is a strong tendency for most of that inter-building traffic to pass through a very small number of ducts.
You're correct, currently.
If you try to replace observations with theories, the most important thing is to verify that your theory corresponds with reality right now. If your theories aren't correct "currently", it is very unlikely that they will be a better fit tomorrow. It isn't a minor point that the Internet is fractal. This is in fact what is consistent everywhere and has been, to the best of my knowledge, throughout the history of the Internet. If you go back to your pretty pictures and look, you will see fractal structures.
Things will become better as network ages, and especially if we get cellular radio architectures in densely populated areas (there's about a GBit/s worth of wireless bandwidth within a small cell, when we ignore THz and optical wavelengths).
dictated by frozen chance, politics (peering arrangements). Automating peering arrangments and using agoric load levelling in the infrastructure will tend to erode that over time. Over time, physical lines will tend to be densest along densest traffic flow.
Very true -- but this has nothing to do with geodesics.
Human societies optimize. Geodesic is a shortest path on Earth surface. Look at Christaller and followup (Christaller and geodesics is good first start).
A geodesic is a minimal path in whatever geometry you are talking about. If you looked carefully at traffic between European countries around 1999, it turned out that the minimal cost path between say German and France was in fact through Virginia. Traffic was following a geodesic -- but not a geographic geodesic. As I recall, a 2 Mbps E1 between most major European cities and Virginia was about $30,000 a month, but an E1 across the English Channel was around $45,000 a month - 50% more to go 30 miles than to go 6,000. We had customers in Northern Ireland whose traffic to Dublin went first to London, then to our PoP in California, then to Virginia, and from there back to Ireland. This was our financial geodesic.
? City layouts that I am familiar with are either haphazard or built around rings or some mixture of the two. MFS built a US national ring, a ring in New York City, a ring in London, and rings elsewhere in Europe. Other carriers tended to follow the same pattern.
I'm not going to dive into city architecture, but compare these two adjacent cities: http://www.redtailcanyon.com/items/18393.aspx
I have spent time in both cities and am familiar with their layouts, but really can't see how this relates to how fiber is laid out in Europe and America.
connected with traffic ducts (rail, highway) which is typically loosely geodesic (but for obstacles in the landscape). Fiber typically follows railway or highway.
That's certainly true, but now you are talking about political decisions made ages ago. Many roads in England were built by the Romans. These
A road is a place channeling traffic from A to B. Roman roads which are still used (I use one quite frequently) were created between areas of major human activity, requiring traffic frequent enough to warrant an expediture (in terms of wealth fraction, roman roads were just as expensive as autobahns).
Indeed. But the point is that things tend _not_ to be optimized at the macro level; what happens is the opposite, micro-optimization around the results of previous decisions (some of which will have been just plain wrong). Roman engineers built roads a couple of thousand years ago, optimizing things according to then-current theories and strategies. We lay down rivers of fiber along those roads, reenforcing those ancient decisions, because the cost of reversing those ancient decisions, and all of the incalculable number of micro-decisions that followed, would be truly enormous. You can see the same pattern working itself out now. A group of Japanese banks invested in a building in Docklands, Telehouse, to act as a backup facility in case of a disaster in the City of London. This turned out to be a loser, in financial terms. The Japanese had misjudged the market demand for this kind of facility. Some telcos had put a few racks in the building. The first UK ISPs followed them there, because the facility was cheap. More ISPs followed. Some decided to build an exchange point there, the LINX, following somewhat misunderstood US models. Things mushroomed; the building, which had been quiet and empty, rapidly filled up with racks. The owners built another building across the street; investors built competing facilities a short distance away, to be close to the action. All of these were interconnected with more and more fiber. The end result is that most UK Internet traffic, and a large part of European traffic, passes through what used to be a more or less derelict area of East London, all because of a planning error on the part of some Tokyo-based banks.
roads lead to London. You see the same pattern on the Continent, of course, with the roads leading to the local capital (Paris, say) and then on to Rome. That is, fiber optic paths today reflect the strategic requirements of the Roman Empire, not geometry.
1) today, EU
today, elsewhere, looks different.
Not at all. Everywhere we see the same pattern of pearl-like growth: someone makes a decision, and those that follow build around the first decision, micro-optimizing as they go along, creating the odd fractal shapes that are all around us.
future, everywhere, looks even more different. We're at the beginning of the optimization process. You can't cheat physics in a relativistic universe, in an economic/evolutionary context.
This isn't physics. It's much more like biology. -- Jim Dixon jdd@dixons.org tel +44 117 982 0786 mobile +44 797 373 7881 http://jxcl.sourceforge.net Java unit test coverage http://xlattice.sourceforge.net p2p communications infrastructure