Transcript Globus Project Future Directions

The Internet:
Packet Switching and
Other Big Ideas
Ian Foster
2
The Internet
1969
4 nodes
2004
100s of millions
The Internet

Clearly a huge success in terms of not only
impact but also scalability



What were underlying big ideas? Let’s say:

Packet switching

End-to-end principle

Internet community & “standards” process
Also other important algorithms, e.g.


Some (not all) of the basic notions have
scaled over eight orders of magnitude
Routing, naming, multicast
Common thread: (fairly) robust emergent
behaviors from simple local strategies
3
4
Overview


Birth of the Internet

Packet switching

Process and governance
End-to-end principle


E.g., congestion avoidance and control
Decentralized, adaptive algorithms

Routing

Naming

Multicast
5
Simple Switching Network
6
Problem Statement



Many “stations” connected by point-to-point
“connections” (with some redundancy)
Enable any station to send “messages” to
any other station, despite diverse failure
modes
And further

Be efficient in use of network resources

Support stations of diverse capabilities

Support diverse applications & behaviors,
including many not yet known (!)
“Traditional” Approach:
Circuit Switching


A dedicated communication path between
the two stations
Communication involves:

Circuit Establishment



Point to Point from terminal node to network
Internal Switching and multiplexing among switching
nodes.

Data Transfer

Circuit Disconnect
E.g., the telephone network
7
8
Circuit Switching


Once connection is established:

Network is transparent

Nodes seems to be directly connected

Fixed data rate with “no delay”
However


Can be inefficient: resources are dedicated
to connection even if no data is sent
Delay prior to usage of connection
Public Switching Telecommunication Network
The generic component of the public switching telecommunication
network is divided into:

Subscribers

Local loop
(connects subscribers to the network)

Exchange
(switching centers)
(end office)

Trunks
(connection between exchanges)
(carry multiple voice channels using FDM or STDM)
9
History of the Internet:
Application Pull


Emergence of (timeshared) computers
supporting interactive use
J.C.R. Licklider of MIT, proposes a global
network of computers



L.C.R. Licklider & W. Clark, "On-Line Man
Computer Communication", August 1962.
A globally interconnected set of computers
through which everyone could quickly
access data and programs from any site
Moves to the Advanced Research Projects
Agency (ARPA) late in 1962

Lobbies to realize his vision
10
Licklider As Visionary:
Man-Computer Symbiosis (1960)…
… is an expected development in cooperative
interaction between men and electronic
computers. The main aims are
1. to let computers facilitate formulative thinking as
they now facilitate the solution of formulated
problems, and
2. to enable men and computers to cooperate in
making decisions and controlling complex
situations without inflexible dependence on
predetermined programs.
11
Technology Push

1962: Paul Baran



Invents packet switching ideas (but talks
about a “Distributed Adaptive Message
Block Network”)
1961-65: Leonard Kleinrock (MIT  UCLA)


Commissioned by the U.S. Air Force to
study how it could maintain command and
control over its missiles and bombers after
a nuclear attack
Develops the theory of packet switching
1965: Donald Davies in the UK

Independently invents packet switching, &
coins the term “packet”
12
13
Baran (1964)

There is an increasingly repeated statement made that one
day we will require more capacity for data transmission
than needed for analog voice transmission. If this
statement is correct, then it would appear prudent to broaden
our planning consideration to include new concepts for future
data network directions. Otherwise, we may stumble into being
boxed in with the uncomfortable restraints of communications
links and switches originally designed for high quality analog
transmission. New digital computer techniques using
redundancy make cheap unreliable links potentially
usable. A new switched network compatible with these links
appears appropriate to meet the upcoming demand for digital
service. This network is best designed for data transmission
and for survivability at the outset.
14
Baran (1964)

The requirements for a future all-digital-data distributed
network which provides common user service for a wide
range of users having different requirements is
considered. The use of a standard format message
block permits building relatively simple switching
mechanisms using an adaptive store-and-forward
routing policy to handle all forms of digital data
including "real-time" voice. This network rapidly
responds to changes in the network status. Recent
history of measured network traffic is used to modify
path selection. Simulation results are shown to indicate
that highly efficient routing can be performed by local
control without the necessity for any central--and
therefore vulnerable--control point.
Baran’s Proposal:
A Packet Switched Network
“Packet switching is the breaking down of
data into datagrams or packets that are
labeled to indicate the origin and the
destination of the information and the
forwarding of these packets from one
computer to another computer until the
information arrives at its final destination
computer. This was crucial to the
realization of a computer network. If
packets are lost at any given point, the
message can be resent by the originator.”
15
Packet Switching

Basic idea
Data to be transmitted is divided into small
packets of information and labeled to
identify the sender and recipient
 Sent over a network and then reassembled
at their destination
 If any packet did not arrive or was not
intact, original sender requested to resend
the packet


Note that this implies (relative to circuit
switching)
Less state at intermediate nodes
 More flexibility in end system behaviors
 More efficient use of networks
 More sophistication at end points

16
The Importance of
Technology Trends


Packet switching was
arguably a logical
consequence of
Moore’s law
Computers became
fast enough to enable
“smart terminals” able
to perform substantial
processing
17
Theoretical Underpinnings
“Packet switching was new and
radical in the 1960s. In order to plan
to spend millions of dollars and
stake my reputation, I needed to
understand that it would work.
Without Kleinrock’s work on
Networks and Queuing Theory, I
could never have taken such a radical
step. All the communications
community argued that it couldn’t
work. This book was critical to my
standing up to them and betting that
it would work.”
Larry Roberts
18
1969 Press Release:
“UCLA to be the First Station in
Nationwide Computer Network”
"As of now, computer
networks are still in their
infancy," says Dr. Kleinrock.
"But as they grow up and
become more sophisticated,
we will probably see the
spread of 'computer utilities'
which, like present electric
and telephone utilities, will
service individual homes and
offices across the country.”
19
History of the Internet

1968: ARPA awarded the ARPANET contract to BBN. BBN had
selected a Honeywell minicomputer as the base on which they
would build the switch. The physical network was constructed in
1969, linking four nodes: University of California at Los Angeles,
SRI (in Stanford), University of California at Santa Barbara, and
University of Utah. The network was wired together via 50 Kbps
circuits.


1972: First e-mail program created by Ray Tomlinson of BBN.
ARPANET used the Network Control Protocol or NCP to transfer
data. This allowed communications between hosts running on the
same network.


Backbones: 50Kbps ARPANET - Hosts: 4
Backbones: 50Kbps ARPANET - Hosts: 23
1973: Development began on the protocol to be called TCP/IP, by
a group headed by Vint Cerf from Stanford and Bob Kahn from
ARPA. This new protocol was to allow diverse computer networks
to interconnect and communicate with each other.

Backbones: 50Kbps ARPANET - Hosts: 23+
20
History of the Internet

1974: First Use of term Internet by Vint Cerf and Bob
Kahn in paper on Transmission Control Protocol.


Backbones: 50Kbps ARPANET - Hosts: 23+
1976: Dr. Robert M. Metcalfe develops Ethernet, which
allowed coaxial cable to move data extremely fast. This
was a crucial component to the development of LANs.
The packet satellite project went into practical use.
SATNET, Atlantic packet Satellite network, was born.
UUCP (Unix-to-Unix CoPy) developed at AT&T Bell Labs
and distributed with UNIX one year later.
DOD began to experiment with the TCP/IP protocol and
soon decided to require it for use on ARPANET

Backbones: 50Kbps ARPANET, plus satellite and radio
connections - Hosts: 111+
21
History of the Internet

1979: USENET (the decentralized news group network)
created: based on UUCP. BITNET introduced the "store and
forward" network, used for email and listservs.


1981: NSF created backbone called CSNET 56 Kbps network
for institutions without access to ARPANET.


Backbones: 50Kbps ARPANET, plus satellite and radio connections
- Hosts: 111+
Backbones: 50Kbps ARPANET, 56Kbps CSNET, plus satellite and
radio connections - Hosts: 213
1983: Internet Activities Board (IAB) created.
On January 1st, every machine connected to ARPANET had to
use TCP/IP. TCP/IP became the core Internet protocol and
replaced NCP entirely.
University of Wisconsin created Domain Name System (DNS),
which translated domain names into corresponding IP
numbers. No need to remember numbers!

Backbones: 50Kbps ARPANET, 56Kbps CSNET, plus satellite and
radio connections - Hosts: 562
22
23
Process and Governance

A key to the rapid growth of the Internet
has been the free and open access to the
basic documents, especially the
specifications of the protocols


“Request for Comments” (RFC) documents
“Rough Consensus and Running Code”

Frequent face-to-face meetings

Heavy use of email

Emphasis on implementation experiences
24
RFCs: For Example …
RFC: 791
INTERNET PROTOCOL
DARPA INTERNET PROGRAM
PROTOCOL SPECIFICATION
September 1981
This document specifies the DoD Standard Internet Protocol. This
document is based on six earlier editions of the ARPA Internet Protocol
Specification, and the present text draws heavily from them. There have
been many contributors to this work both in terms of concepts and in
terms of text. This edition revises aspects of addressing, error
handling, option codes, and the security, precedence, compartments, and
handling restriction features of the internet protocol.
Network Working Group
Request for Comments: 1149
D. Waitzman
And …
BBN STC
1 April 1990
A Standard for the Transmission of IP Datagrams on Avian Carriers
Status of this Memo
This memo describes an experimental method for the encapsulation of
IP datagrams in avian carriers. This specification is primarily
useful in Metropolitan Area Networks. This is an experimental, not
recommended standard. Distribution of this memo is unlimited.
Overview and Rationale
Avian carriers can provide high delay, low throughput, and low
altitude service. The connection topology is limited to a single
point-to-point path for each carrier, used with standard carriers,
but many carriers can be used without significant interference with
each other, outside of early spring. This is because of the 3D ether
space available to the carriers, in contrast to the 1D ether used by
IEEE802.3. The carriers have an intrinsic collision avoidance
system, which increases availability. Unlike some network
technologies, such as packet radio, communication is not limited to
line-of-sight distance. Connection oriented service is available in
some cities, usually based upon a central hub topology.
25
26
Overview


Birth of the Internet

Packet switching

Process and governance
End-to-end principle


E.g., congestion avoidance and control
Decentralized, adaptive algorithms

Routing

Naming

Multicast
Generalizing:
The End-to-End Principle




Reliable systems tend to require end-to-end
processing to operate correctly, in addition to
any processing in intermediate systems
End-to-end processing alone suffices to
make the system operate: intermediate
processing stages are largely redundant
Thus, intermediate processing can be made
simpler, relying on end-to-end processing to
make the system work
This leads to the model of a “dumb network”
with smart terminals, a completely different
model to the previous paradigm of the smart
network with “dumb terminals”
27
End-to-End Principle Applied:
End-to-End Transport

Dumb network: each node repeatedly




Receives a packet, with destination info
Forwards it towards destination, if it can,
with time to live decremented
Note: Must maintain routing information
Smart terminals are responsible for

Generating packets

Receiving packets

Detecting and dealing with out of order and
missing packets
28
Datagram Lifetime

Datagrams could loop indefinitely



Consumes resources
Transport protocol may need upper bound
on datagram life
Datagram marked with lifetime



Time To Live field in IP
Once lifetime expires, datagram discarded
(not forwarded)
Hop count


Decrement time to live on passing through each router
Time count

Need to know how long since last router
29
IP Fragmentation

IP re-assembles at destination only

Uses fields in header

Data Unit Identifier (ID)




Source and destination address

Protocol layer generating data (e.g., TCP)

Identification supplied by that layer
Data length


Identifies end system originated datagram
Length of user data in octets
Offset

Position of fragment of user data in original datagram

In multiples of 64 bits (8 octets)
More flag

Indicates that this is not the last fragment
30
31
IPv4 Header
32
Dealing with Failure

Re-assembly may fail if some fragments
get lost

Need to detect failure

Re-assembly time out



Assigned to first fragment to arrive
If timeout expires before all fragments
arrive, discard partial data
Use packet lifetime (time to live in IP)

If time to live runs out, kill partial data
33
Virtual Circuit vs. Datagram

Datagram:

Each packet is treated independently.

Each packet has a full address of the destination



Routing decision is taken for each packet at
each node
Different packets of one message may take
different routes
Virtual Circuit:

A connection is setup prior to data transfer

Each packet contains a VC identifier

Routing decision is made once for all packets

All packets follow the same route
34
Virtual Circuit vs. Datagram
Datagram:
Virtual Circuit:
+ Call setup time is avoided
+ Transmission order preserved
+ Fast adaptation to
congestion control
+ Error control is provided
+ Fast adaptation to node
failure
- Transmission order is not
preserved
- High load due to route
processing (decision per
packet)
- Receiver has no
preparation for incoming
transmissions
+ One routing decision per
connection
+ Receiver prepared for
transmission
- Delays in making a connection
- Poor adaptation to node failure
- Poor spreading of load
35
Why Packetize




For end-to-end route compromising of
many links, packetizing allows for parts of
message to be received, processed, and
forwarded while others are still being
prepared
Amount of retransmitted data due to errors
is reduced
Memory capacity of internal network nodes
can be reduced
Transmission time can be reduced
36
Effect of Packet Size on Transmission Time
Circuit Switching vs. Packet
Switching
37
Summary:
“Big Ideas” Underlying the Internet


Packet switching

Flexible, robust, efficient (in the network)

Enabled by “smart terminals”
End-to-end arguments in system design


E.g., reliable in-order delivery via TCP
Rough consensus and running code

As a means of creating and evolving a
complex artifact
38
39
Further Reading

Introduction to distributed communication network


A digital communications network for computers


http://portal.acm.org/citation.cfm?id=800001.811669
The Evolution of Packet Switching


http://www.rand.org/publications/RM/RM3420
http://www.packet.cc/files/ev-packet-sw.html
End-to-end arguments in system design

http://citeseer.nj.nec.com/saltzer84endtoend.html
Assignment
1)
Compare the delay in sending an x-bit message over a k-hop path in a
circuit-switched network and in a (lightly loaded) packet-switched
network. The circuit setup time is s sec, the propagation delay is d sec
per hop, the packet size is p bits, and the data rate is b bps. Under what
conditions does the packet network have a lower delay?
2)
Suppose that x bits of user data are to be transmitted over a k-hop path
in a packet-switched network as a series of packets, each containing p
data bits and h header bits, with x >> p+h. The bit rate of the lines is b
bps and the propagation delay is negligible. What value of p minimizes
the total delay?
3)
Calculate the total time required to transfer a 1.5-MB file in the following
cases, assuming a round trip time (RTT) of 80 ms, a packet size of 1 KB
and an initial 2 x RTT of "hand-shaking" before data is sent.
(a)
(b)
(c)
(d)
The bandwidth is 10 Mbps, and data packets can be sent continuously.
The bandwidth is 10 Mbps, but after we finish sending each data packet
we must wait one RTT before sending the next.
The link allows infinitely fast transmit, but limits bandwidth such that only
20 packets can be sent per RTT.
Zero transmit time as in (c), but during the first RTT we can send one
packet, during the second RTT we can send two packets, during the third
we can send four = 2^(3-1), and so on.
40