I have just finished reading (well, skimming some of) Christian Huitema’s “Routing in the Internet”. It is an historical account thru mid 1994. The author has many opinions with which I disagree but they are well demarcated and it is good to know what they are. The book is about the level that I need. It describes the algorithms, shows control packet formats but is far from a programming spec. I feel that I now have a good overview of the Internet design turmoil as of the mid 1994 and I did learn a couple of clever new network algorithms.

The book is from mainstream Internet culture in that it is nearly devoid of incentive ideas. At one point however he does suggest sticking your credit card into a machine to get better service. I found little notion of utility or other economics ideas to address network priority problems.

I gather from the book that the overall emerging Internet architecture is a collection of about 1000 ASs (Autonomous Systems) at the top under diverse administrative control. Protocol evolution between these units is sluggish. There are many unsolved routing policy questions at this level. Huitema suggests that BGP-3 and BGP-4 are the dominant protocols at this level. This is the only protocol that seems to be an “interface” protocol rather than a “network” protocol. By an interface protocol I mean that there is a semblance of a contract between the parties on the two sides of the interface, whereas in a network protocol there are merely packet formats, suggested router behaviors, and speculation on how conforming routers would cope.

BGP stands for “Border Gateway Protocol”. I keep thinking “Border Patrol”. When a routing advice packet crosses a gateway saying “5 hops to Inria via this interface” it is accompanied with a list of the ASs that that distance presumes. (ASs are globally identified by 16 bit numbers.) Loops can thus be avoided. Some routing policies can be implemented with this information. BGP has protocol for computing path attributes where not every AS needs to understand every attribute. BGP uses TCP which causes layering confusion. (I recall the electric generator in Brooklyn that couldn’t come up after a wide spread power failure because its lubricating pump had no power.)

Within an AS the OSPF protocol seems to be displacing RIP and earlier protocols. OSPF presumes that each router knows the whole topology of the AS. It is then in a position to route omnisciently. Topology information is spread by an incremental “flooding” scheme. The specs for OSPF are infamously complex.

There are several candidate multicast routing algorithms. One clever one, CBT, assigns a “core” router for a multicast session. Joiners of the session launch a “join” packet towards the core for the session. When the packet first reaches a router that belongs to that session, the connection is complete. This algorithm results in a “spanning tree” which does not send data where it is not needed.

Huitema collects together reports on several difficult emerging problems. Suggested solutions to some of the problems seem at odds with solutions to others. Huitema mentions these hard unsolved problems:

There are more or less credible solutions to each of these, but those solutions are in conflict. Huitema reports some of these such as RSVP producing reservations at one place while various routing protocols send your data elsewhere.

There is a set of OSI protocols that solve some of these problems but not others. Some small pieces of the network try to conform to these protocols simultaneously to the classic protocols. Huitema thinks that there are no advantages to this and no creditable direction in which to evolve from such a strategy.