Transcript ppt

NET0183 Networks and Communications
Lectures 3 and 4
ARPANET
DARPA / ARPA
Defense / Advanced Research Project Agency
(USA)
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
1
1967
• The initial plan for the ARPANET was published in October
1967 in the Proceedings of the first ACM symposium on
Operating System Principles.
• The reasons for establishing such a computer network were:
– Load Sharing
• data and program to be sent to a less busy, remote computer
– Message Service
• electronic mail
– Data Sharing
• remote access to databases
– Program Sharing
• data sent to remote computer which ran program
– Remote Service
• login to remote computer to access its data and programs
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
2
http://portal.acm.org/portal.cfm
1967
Another paper on the packet network concept.
The initial plan for the ARPANET.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
3
1967
• There was another paper at first ACM symposium on
Operating System Principles on the packet network
concept. This paper was by Davies and others from the
National Physical Laboratory in the UK.
• Work at MIT (1961-1967), RAND (1962-1965), and at NPL
(1964-1967) had proceeded in parallel without the
researchers knowing about each others´ work.
• The word “packet” was adopted from the work at NPL.
• The proposed line speed in ARPANET of 2.4 kbps was
upgraded to 50 kbps.
• Note that the ARPANET was not designed for the purposes
of having a network resistant to nuclear war. This was a
false rumor.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
4
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
A store and forward network.
• A copy of a packet is stored at a node until it has been
received at the following node.
– a store and forward network
• A store and forward network must deal with the routing of
packets, the queueing of packets, error control, etc.
• To shield host computers from these issues, ARPA chose to
use small processors as packet switches called Interface
Message Processors or IMPs.
• The work of creating the ARPA network divided into two
main parts: (i) the design and implementation of the IMP
subnet and (ii) the design and implementation of protocols
to allow host computers to make use of the network.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
5
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
6
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Host-subnet design principles
1. “The subnet should function as a
communications system whose essential task is
to transfer bits reliably from a source location to
a specified destination. Bit transmission should
be sufficiently reliable and error free to obviate
the need for special precautions (such as storage
for retransmission) on the part of the Hosts;”
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
7
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Host-subnet design principles
2. “The average transit time through the subnet
should be under a half second to provide for
convenient interactive use of remote
computers;”
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
8
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Host-subnet design principles
3. “The subnet operation should be completely
autonomous. Since the subnet must function as a store
and forward system, an IMP must not be dependent upon
its local Host.
The IMP must continue to operate whether the Host is
functioning properly or not and must not depend upon a
Host for buffer storage or other logical assistance such as
program reloading.
The Host computer must not in any way be able to change
the logical characteristics of the subnet; this restriction
avoids the mischievous or inadvertent modification of the
communication system by an individual Host user;”
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
9
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Host-subnet design principles
4. “Establishment of Host-to-Host protocol and the
enormous problem of planning to communicate
between different computers should be an issue
separated from the subnet design.”
Andy comments: From these design principles it is clear that at least two protocols are
required. One protocol governs the movement of packets over the IMP subnet. The other
protocol governs how host computers communicate with each other at a message level.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
10
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Message handling
• Hosts communicate via messages.
• An IMP takes a message from its Host computer and breaks
it down into packets which it then sends separately over
the network. This breaking down of messages into packets
during transmission is completely invisible to the Host
computers.
• “The transmitting Host attaches an identifying leader to the
beginning of each message. The IMP forms a header by
adding further information for network use and attaches
this header to each packet of the message.”
• The maximum size of a packet is about 1,000 bits. A
message from a Host to an IMP is about 8,000 bits.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
11
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
12
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Message handling
• “Each packet is individually routed from IMP-to-IMP
through the network toward the destination. At each IMP
along the way, the transmitting hardware generates initial
and terminal framing characters and parity check digits that
are shipped with the packet and are used for error
detection by the receiving hardware of the next IMP.”
• Packets of a message may arrive out of order. The
destination IMP reassembles the message in the right
order, stripping headers of each packet and identifying the
source Host in the leader.
Andy comments: Note how some of the subnet protocol is in hardware.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
13
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Message handling
• “Errors in transmission can affect a packet by
destroying the framing and/or by modifying the data
content. If the framing is disturbed in any way, the
packet either will not be recognized or will be rejected
by the receiver. In addition, the check digits provide
protection against errors that affect only the data.”
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
14
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Message handling
• Each IMP stores the packet until it receives a positive
acknowledgement from the succeeding IMP.
• An IMP can refuse a packet “by simply not returning a
positive acknowledgment”.
– The packet may be detected to have an error.
– IMP buffer storage may be temporarily full.
– Etc.
• If a packet is not acknowledged within a reasonable
time (e.g. 100 msec), the transmitting IMP can
retransmit, perhaps even along a different route.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
15
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Message handling
• “Acknowledgements themselves are not
acknowledged, although they are error checked
in the usual fashion.”
• Duplicate packets can arise as a result of a lost
acknowledgment. The destination IMP can detect
duplication using message and packet numbers in
the header.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
16
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Figure 4 – RFNMs and acknowledgements
An RFNM is also a packet and it is also acknowledged. Note that a later article
on ARAPNET design decisions suggests that acknowledgements were not sent
separately in order to reduce overheads.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
17
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
idle
idle
Figure 5 – Format of a packet on phone line
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
18
http://en.wikipedia.org/wiki/ASCII#ASCII_control_characters
Some ASCII control characters.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
19
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Doubling DLE characters
• IMP hardware doubles any DLE characters within
the actual data being sent so that the receiving
hardware can distinguish them from the DLEs
used to frame packets.
Andy comments: An alternative design solution could reserve certain characters
for control purposes. For example, characters such as DLE could not appear in the
data stream itself. Such a solution, however, could be too restrictive and place
severe limits on the data that could be sent over the network.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
20
Heart, F.E., Kahn, R.E., Omstein, S.M., Crowther, W.R., and Walden, D.C. The interface message processor for the
Arpa computer network, AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-567.
Routing algorithm
• Paths through the network are not determined in advance.
• Each IMP decides onto which of its output lines it should
transmit a packet.
• For every possible destination, an entry in a lookup table
specifies the appropriate output line.
• The system is adaptive. Routing tables are dynamically
updated to reflect changing conditions on the network.
– traffic congestion (what is the fastest route?)
– breaks in connectivity (what route is currently not available?)
• Neighbouring IMPs exchange minimum delay tables with
one another and use this information to construct routing
tables.
– Estimates of delays are based on queue lengths and recent
performances of connections.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
21
1968 and 1969
• In 1968 companies were asked to tender bids to build
the IMPs (Interface Message Processors).
– A request for quotation (RFQ).
– A request for proposal (RFP).
• In January 1969, a contract was awarded to Bolt,
Beranek and Newman Inc. (of Cambridge,
Massachussetts).
• In September 1969, BBN installed the first IMP at UCLA
and the first host computer was connected.
• In October 1969, Stanford Research Institute was
connected to the ARPANET and the first host-to-host
message was sent.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
22
http://www.nature.com/nature/journal/v461/n7268/full/4611202a.html
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
23
29OCT69
“talked to SRI Host to Host”
http://www.computerhistory.org/internet_history/
Kline began to type "LOG," to log in through telephone wires to the computer
more than 300 miles away at Stanford. But after the "L" and the "O," the
Stanford computer crashed.
LA Daily News 29 October 2009
http://www.dailynews.com/news/ci_13669715
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
24
http://som.csudh.edu/cis/lpress/history/arpamaps/
December, 1969
University of Utah
Stanford Research Institute
University of California, Santa Barbara
University of California, Los Angeles
8/25/2009
Four host computers were now connected
together forming the initial ARPANET.
NET0183 Networks and Communications
by Dr Andy Brooks
25
http://som.csudh.edu/cis/lpress/history/arpamaps/
June, 1970
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
26
from “The Arpanet and computer networks” by Larry Roberts
Proceedings of the ACM Conference on The history of personal workstations, 1986
April, 1971
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
27
1970/1971
• Terminals that could be connected directly to
the network through a PAD device were
designed and built during 1970 and 1971.
– PAD Packet Assembler and Disassembler
• The first Terminal Interface Processor (TIP)
was added to ARPANET in August, 1971.
– Users with no computer of their own could
connect to any computer on the ARPANET.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
28
1972/1973
• In October 1972, the ARPANET was demonstrated
publicly for the first time at the first International
Conference on Computer Communications (ICCC)
in Washington D.C.
– A reliable service was provided to thousands of
conference attendees, proving to all that packet
switching really does work.
• In 1972, network traffic rose from 100,000
packets a day to 1,000,000 packets a day.
• In September 1973, network traffic had risen to
2,900,000 packets a day.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
29
http://som.csudh.edu/cis/lpress/history/arpamaps/
June, 1974
Satellite links to Hawaii and Norway. Note that the Hawaii site is shown with a TIP and
not an IMP plus host computer.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
30
A Brief History of the Internet, Barry M Leiner et al, ACM SIGCOMM Computer Communication Review, Volume
39, Number 5, October 2009, pp 22-31.
The Network Control Protocol (NCP)
• In December 1970, the specification of the
initial ARPANET Host-to-Host protocol was
finished.
• During 1971-1972, ARPANET sites completed
the implementation of NCP and network users
could then start developing applications.
• In 1972, electronic mail was introduced. Email
was the largest network application for over a
decade.
Andy comments: other sources suggeststhat NCP really stood for Network Control Program.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
31
http://openmap.bbn.com/~tomlinso/ray/firstemailframe.html
The First Network Email
by Ray Tomlinson
“I used the at sign to indicate that the user was "at" some other host rather
than being local.
The first message was sent between two machines that were literally side by
side. The only physical connection they had (aside from the floor they sat on)
was through the ARPANET. I sent a number of test messages to myself from
one machine to the other. The test messages were entirely forgettable and I
have, therefore, forgotten them. Most likely the first message was
QWERTYUIOP or something similar. When I was satisfied that the program
seemed to work, I sent a message to the rest of my group explaining how to
send messages over the network. The first use of network email announced its
own existence.
These first messages were sent in late 1971.”
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
32
A Brief History of the Internet, Barry M Leiner et al, ACM SIGCOMM Computer Communication Review, Volume
39, Number 5, October 2009, pp 22-31.
The move from NCP to TCP/IP
• NCP could not address networks beyond a destination
IMP on the ARPANET.
• “... NCP had no end-end host error control, since the
ARPANET was to be the only network in existence and
it would be so reliable that no error control would be
required on the part of the hosts.”
• Robert Kahn decided to develop a new version of the
protocol which would provide an open-architecture
network environment. His work with others led to the
development of TCP/IP.
Transmission Control Protocol/Internet Protocol
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
33
A Brief History of the Internet, Barry M Leiner et al, ACM SIGCOMM Computer Communication Review, Volume
39, Number 5, October 2009, pp 22-31.
The move from NCP to TCP/IP
• The ARPANET host protocol moved from NCP
to TCP/IP on January 1, 1983.
8/25/2009
NET0183 Networks and Communications
by Dr Andy Brooks
34