On Sun, 11 Apr 2004, sunder wrote:
The term is used because most or all trees in the region where the English language originated are shaped just like that: they have a single trunk which forks into branches which may themselves fork and so on. These branches do not connect back to one another.
I believe the real issue here is one of being able to stretch your mind into seeing things from different points of view. This is the reason I brought in the quasi-mystical quote about the sphere whose center is everywhere.
Someone comes to me and says: "the Internet is a tree". Then he points me at a graph of inter-AS (Autonomous System) connections to illustrate his point. That graph includes all of those seemingly redundant connections that make it _not_ a tree. These seemingly redundant connections are in fact a high proportion of all connections. That is to say, the graph is accurate and his statement wasn't. You can see the Internet in many ways. You can run a single traceroute and see it as a line. You can ping broadcast on your LAN and see it as a chorus line. If you understand what you are looking at, you can run traceroutes and see stable rings: hot potato routing at work, where the packets go out one way and come back another. Then again, I have spoken to hundreds? thousands? of people who think that the Internet _is_ the World Wide Web.
Let's explain why we have multiple connections and what types of these you can expect. There are two common types of multiple connections:
A) Two links to the same ISP: In terms of redundancy for the purposes of being fault tolerant, only one of the multiple links is ever used. With
You don't understand and you are quite wrong. If one AS has more than one link to another AS, there are often very good reasons for it, and both links are used. If network A peers with network B in both Paris and New York, both will generally dump traffic for the other network at the nearest connection. Why? Well, on the one hand, there is no reason to carry packets originating in Paris and destined for a host in Paris all the way to New York. On the other hand, many or most networks employ hot potato routing, meaning that if network A picks up a packet for network B in Paris, it dumps it on network B as soon as it can, to minimize costs, wherever the destination might be. Some networks, concerned with quality of service, adopt the opposite strategy, and carry packets as far as possible within their own network.
most ISP's, when you negotiate a contract for a backup connection, it's with the understanding that you'll only use it when the main one goes down.
I don't think that you have any evidence for this assertion about what characterizes 'most' backup agreements. I do know that most networks regard this sort of statistical information as highly confidential.
B) You have multiple connections to different ISP's (possibly with peering contracts, etc.) In this case when a node at your location tries to contact some other node on the internet, it's traffic doesn't go over ALL of your connections - it takes only a single path. [Ok, if your routers are correcting for an outage, then perhaps you'll see different paths being taken, but this is just the routing tables/routers settling or converging.]
The world is more complicated than this. Much more.
If both case A and case B, a single node in your location will see the entire internet as a tree with the root of that tree being the default gateway. (i.e. go back to doing traceroutes.) In the case of a multi-homed machine, or machine that participates in routing, it itself becomes the root of the tree.
There are tens of thousands of machines on the Internet that don't have a default gateway. Machines that participate in backbone routing have multiple connections and aren't the root of a tree in any normal sense of the word. There is no parent-child relationship between such routers: they are peers. These peers participate in a highly complex graph which dances continuously. The result is that routing has a large stochastic component: if you can understand what you are looking at, you often see traceroutes involving packets jumping sometimes one way, sometimes another. To make things even more difficult to understand, an increasing amount of traffic flows through MPLS tunnels, which are invisible to traceroutes.
Once you eliminate cycles, and you do so in real life, you go back to a tree. You only see the alternate paths used when failover or routing errors occur.
This just isn't true. Hot potato routing is the most easily understood example: traffic goes out one way and back another. It does this because the ASs involved have set their policy that way. Backbone routers have lots of knobs to configure traffic flow. Some of these allow you to throttle it, some allow you to split flows according to traffic type, some allow to to split flows statistically, some allow you to drop packets statistically. And some allow you to ignore pings and traceroutes ;-)
At the same time, I also disagree with you. If your POV is a single host, it sees the internet as a tree.
Sorry. I have spent too many long hours probing the Internet from single hosts to accept this. If you understand what you are looking at, you see something much more complicated than a tree.
In fact, one of the properties of trees is that you "pick up" any leaf node and designate it as the root.
There are different types of trees. Most discussions of 'trees' are about rooted trees, which are directed acyclic graphs with one and only one root. However, all trees are acyclic. The Internet isn't. Of course, most of this discussion revolves around one word: "is". If you said "the Internet _can be seen_ as a tree", few would disagree with you, especially if you allowed for the fact that that tree is continuously changing its shape. But "the Internet _is_ a tree"? That's simply an error. -- 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