[ARPAnet/IMP Software History] [Received Jan 5 1978 JOEL LEVIN] Bolt Beranek and Newman Inc. PRINCIPAL MILESTONES nodes 1969 4 Initial network -- 4 IMPs -- DDP 516 50 Kb circuits 1970 13 Distant hosts 230.4 KB circuits 1971 19 H316 IMP (lower cost) Directly connected terminals via TIP 1972 34 Magnetic tape handler for TIP Improved algorithms for flow control and storage allocation 1973 45 Satellite links to Hawaii and Europe Interconnection with foreign PTTs Reliability and Routing improvements Very distant hosts (via modems) 1974 51 Shift of emphasis to operational reliability TIP access control and accounting Logical subnetworks Selective memory checking and reloading 1975 58 Host access controls and "fairness" improvements High-reliability, high-throughput multiprocessor IMPs ARPANET operation to Defense Communications Agency Multi-access satellite network Private line interface (PLI) for data security Transmission of digital speech 1976 58 New terminal support protocol Expanded host and IMP address ranges Consolidation and emphasis on operational stability 1977 58 Distributed terminal control protocol (RCTE) Support of digital circuits (DDS) Routing study and consequent improvements Honeywell Level 6 processor support X.25 Link Access Protocol 1978 Major routing study underway Increased Host fan out (Level 6) Packet size as parameter (Level 6) X.25 Level 3 Bolt Beranek and Newman Inc. EVOLUTION OF THE ALGORITHMS 1969 Reliable communications subnetwork Delay of 1/2 second or less Independence of hosts and IMPs Hosts transmit messages (up to 8095 bits) IMPs segment messages into packets (up to 1008 bits) which are transmitted independently and in parallel to reduce delay Limit of one outstanding message per conversation between one pair of hosts to prevent congestion Specially designed asynchronous bit-serial host to IMP interface 24 bit hardware checksum Packets forwarded to next IMP and stored pending positive acknowledgement of receipt (up to 8 outstanding) Distributed adaptive routing algorithm - minimum delay based on estimates from neighbors and own knowledge of queuing delay and line condition - no need to know full topology - self-adjusting - efficient 1972 Regular exchange of line, host and IMP status Changes to improve performance under heavy loads (based on conclusions from experiments and simulations) Pre-allocation of buffers for multi-packet messages to ensure timely re-assembly at destination ACKs imbedded in normal messages 1973 "Hold down" logic added to damp response to new line or node data in order to prevent temporary looping Sensing of line speed and capacity and adjustment of routing information exchange frequency Event-driven routing calculation 1974 "Raw packets: -- sequencing and flow control logic bypassed Dynamic rather than static accounting for allocation and flow control data Allocation by Host pair (previously by IMP pair) Singly connected IMPs Inter-IMP message number re-synchronization 1975 Expanded number of outstanding messages per host pair More complete message state information at destination IMP 1976 Expanded formats for host and IMP addresses Consolidation of information about pending messages into uniform transaction blocks 1977 Provision for up to 16 outstanding packets on lines with long delay (e.g., satellite links) Improved calculation of re-assembly and store/forward storage limits Preliminary routing study and changes to contain and more rapidly correct congestion arising from bad lines or slow nodes Host and modem interfaces made equivalent (Level 6) Use of BSC for error detection and data transparency (Level 6) Use of HDLC for error recovery and acknowledgement (Level 6) 1978 Major routing study underway to incorporate most recent research and current experience Provision for 12 or more hosts per IMP (Level 6) Packet size made a parameter (Level 6) Bolt Beranek and Newman Inc. EVOLUTION OF MAINTENANCE AND CONTROL FUNCTIONS 1969 Performed by system programmers and hardware designers on a casual basis Remote controlled diagnostic loopback Power failure detection and recovery Watchdog timer and self-initiated reload from neighbor Packet tracing State snapshots Remote debugging package Performance statistics 1970 Centralized trouble reporting and diagnosis Exception-based problem reporting Distribution of new software via the network itself 1971 Introduction of host NCC processor to monitor network status and prepare reports Dedicated prime-shift NCC operator 1972 Loading of TIPs from NCC host Broadcast patching of IMPs from NCC host Full-time NCC operator coverage Responsibility for operations assigned to operators Fully remote software distribution Use of large host for some NCC functions 1973 Software-generated checksums for both data and software; self-initiated dump and re-load Addition of remote IMP hardware diagnostics Remote scanning for malfunctioning TIP terminal modems 1974 Selective reloading of IMP/TIP software On-line notification and status for host down-time 1975 Transfer of ARPANET to DCA administration as an operational utility Statistics and trace modules made selectively loadable 1976 Improved load and dump routines Auto-sensing of line and host configuration Emphasis on stability Consolidation 1977 Disk-based Network Monitoring Center Diskette-based Network Monitoring Center Error control on Host/IMP channel (Level 6)