Hierarchy, Force Monopoly, and Geodesic Societies

[Jim Dixon]

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 at 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