ARPAnet/IMP Software History	RECEIVED
		JAN 5   1978
		JOEL LEVIN

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

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)

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)