4

According to Internet Daemons, the notion of 'gateways' was introduced practically simultaneously with the TCP protocol. From what I have read, early NCP addresses were 8 bits: 2 to specify the host number, and 6 for the IMP number. (I am unsure which RFC officially codified this, as RFC 1 seems to only specify 5 bits for a destination.)

I am having trouble finding information on the topology connecting the IMPs at this early stage (pre '73) - certainly there is abundant theoretical work at this time detailing possibilities, but I am interested what the actual implementation was in ARPANET's youth. In particular, was every IMP connected to every other IMP? Or some other topology (potentially some early routing protocol)?

Improve this question
0

1 Answer 1

Reset to default
5

Early ARPANET logical maps (from 1970 onwards), as well as the geographic maps (note the UTAH spur in the 1969 map), show that it was not a full-mesh topology; there must therefore have been some kind of routing.

J. Noel Chiappa's website references a few early documents that talk about the specific implementation of routing at that time:

  • The interface message processor for the ARPA computer network (1970)

    • Quote from page 5:

      The routing algorithm directs each packet to its destination along a path for which the total estimated transit time is smallest. This path is not determined in advance. Instead, each IMP individually decides onto which of its output lines to transmit a packet addressed to another destination. This selection is made by a fast and simple table lookup procedure. For each possible destination, an entry in the table designates the appropriate next leg. These entries reflect line or IMP trouble, traffic congestion, and current subnet connectivity. This routing table is updated every halfsecond as follows:

      Each IMP estimates the delay it expects a packet to encounter in reaching every possible destination over each of its output lines. It selects the minimum delay estimate for each destination and periodically (about twice a second) passes these estimates to its immediate neighbors. Each IMP then constructs its own routing table by combining its neighbors' estimates with its own estimates of the delay to that neighbor. The estimated delay to each neighbor is based upon both queue lengths and the recent performance of the connecting communication circuit. For each destination, the table is then made to specify that selected output line for which the sum of the estimated delay to the neighbor plus the neighbor's delay to the destination is smallest.

      The routing table is consistently and dynamically updated to adjust for changing conditions in the network. The system is adaptive to the ups and downs of lines, IMPs, and congestion; it does not require the IMP to know the topology of the network. In particular, an IMP need not even know the identity of its immediate neighbors. Thus, the leased circuits could be reconfigured to a new topology without requiring any changes to the IMPs.

And you can also find what was the predecessor to that document – BBN Report No. 1783 from April 1969, only slightly later than the original proposal that was mentioned in Internet Daemons:

  • The Interface Message Processor for the ARPA Computer Network (1969)

    • Quote from page 6:

      We have designed, and are currently implementing, a routing algorithm. Each IMP regularly estimates the minimum delay path through the network to each destination and stores the information in an updatpd routing table. This algorithm and its implementation are discussed in Section 5.

Eventually the routing algorithm was replaced with a different one (from distance-vector to link-state) – which was still happening in the NCP era; no IP or gateways yet:

This topology lasted for a long time – even with TCP/IP in place, ARPANET still relied on IMP routing (with the original Host/IMP addresses becoming practically "layer 2" addresses underneath IP, so that the entire IMP-based ARPANET appeared as a single flat class-A IPv4 network, with 10.hh.hh.ii addresses being directly mapped to underlying Host/IMP addresses); IP gateways were only needed between the IMP-based ARPANET and other networks.

(I don't have any sources handy, but when I was reading about the 'HELLO' routing protocol used by NSFnet, it was mentioned that the resulting "flat L2 network" appearance of the ARPANET had caused difficulties for the development of IP-layer routing protocols, as the entire network appeared as a single link (interface) yet had varying costs to different destinations – and even these days, routing protocols such as OSPF can't represent that easily.)

More information (post-1973) can be found at:

Don't forget to read the IEN series of documents; they document a lot of the "early IP" evolution in-between RFCs (such as TCPv2 and TCPv3, before it was split up into TCP/IPv4).

Keep in mind that ARPANET was not the only network in existence, and the notion of "gateway" (in the sense of a router) existed in other networks as well, even if wasn't necessarily called that way. For example, Xerox's XNS – which IPv4 took some inspiration from – also had routers or gateways before ARPANET did (IP even took the RIP routing protocol from XNS).

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .