CSE 222A: Computer Communication Networks
George Porter
Lecture 2:?
Layering & End-to-End
Thanks: Alex C. Snoeren, Mike Freedman & Amin Vahdat
Lecture 2 Overview
●? Short Internet history lesson
??
Growth & change
●? Layering
??
Application interface
??
Transport services
●? Discussion of End-to-End principle
CSE 222A – Lecture 2: Layering & End-to-End
2
In-class exercise
●? Break into about 10 groups (~8-10 ppl. per group)
●? Think of a recent, “modern” distributed application
??
Examples include Snapchat, Twitter, Instagram, Facebook,
Slack, Skype, [fill in something else here]
●? Will return to this topic later in class
CSE 222A – Lecture 2: Layering & End-to-End
3
Background
●? 1957: USSR launches Sputnik, first artificial earth
satellite
??
U.S. responds by forming ARPA
●? 1962: Licklider’s
Galactic Network
●? 1966: Roberts (MIT)
Towards a Cooperative Network
of Time-Shared Computers
??
Also, Star Trek debuts…
●? 1967: ACM SOSP
Multiple Computer Networks and
Intercomputer Communication
●? 2008: Amazon EC2 (the “cloud”)
●? 2009: Android phones hit the market at volume
CSE 222A – Lecture 2: Layering & End-to-End
4
Vannevar Bush
●?
Vannevar Bush established the U.S. military /
university research partnership that later
developed the
ARPANET.
“Consider a future device for individual use, which is a sort of
mechanized private file and library. It needs a name, and to
coin one at random, "memex" will do. A memex is a device in
which an individual stores all his books, records, and
communications, and which is mechanized so that it may be
consulted with exceeding speed and flexibility. It is an
enlarged intimate supplement to his memory.
“It consists of a desk, and while it can presumably be
operated from a distance, it is primarily the piece of furniture
at which he works. On the top are slanting translucent
screens, on which material can be projected for convenient
reading. There is a keyboard, and sets of buttons and levers.
Otherwise it looks like an ordinary desk.
Vannevar Bush,
As We May Think; Atlantic Monthly, July 1945.
CSE 222A – Lecture 2: Layering & End-to-End
5
Source: Livinginternet.com
J.C.R. Licklider
●?
Joseph Carl Robnett "Lick" Licklider developed
the idea of a universal network, spread his vision
throughout the
IPTO, and inspired his
successors to realize his dream by creation of
the
ARPANET.
“It seems reasonable to envision, for a time 10 or 15 years
hence, a 'thinking center' that will incorporate the functions of
present-day libraries together with anticipated advances in
information storage and retrieval.”
“The picture readily enlarges itself into a network of such
centers, connected to one another by wide-band
communication lines and to individual users by leased-wire
services. In such a system, the speed of the computers would
be balanced, and the cost of the gigantic memories and the
sophisticated programs would be divided by the number of
users.”
J.C.R. Licklider,
Man-Computer Symbiosis, 1960.
CSE 222A – Lecture 2: Layering & End-to-End
6
Source: Livinginternet.com
1969 Internet Map
CSE 222A – Lecture 2: Layering & End-to-End
7
Chicago Data Center (2008)
CSE 222A – Lecture 2: Layering & End-to-End
9
Dublin Data Center (2009)
CSE 222A – Lecture 2: Layering & End-to-End
10
Back to the Future: Cloud
Computing
Google’s Worldwide Data Centers
http://www.google.com/about/datacenters/inside/locations/
Racks and racks and racks…
CSE 222A – Lecture 2: Layering & End-to-End
12
Internet Timeline
●? 1971: Tomlinson develops email program, big hit
●? 1972: Telnet
●? 1973: FTP
●? 1974: TCP
●? 1978: TCP split into TCP and IP
●? 1979: USENET established using UUCP between
Duke and UNC by Tom Truscott, Jim Ellis, and Steve
Bellovin
●? 1984: 1000 hosts, DNS introduced
●? 1988: Internet worm brings down 10% of Internet
●? 1991: WAIS, Gopher, WWW released
CSE 222A – Lecture 2: Layering & End-to-End
13
Internet Growth Trends
●?
1977: 111 hosts on Internet
●?
1981: 213 hosts
●?
1983: 562 hosts
●?
1984: 1,000 hosts
●?
1986: 5,000 hosts
●?
1987: 10,000 hosts
●?
1989: 100,000 hosts
●?
1992: 1,000,000 hosts
●?
2001: 150 – 175 million hosts
●?
2002: over 200 million hosts
●?
2011: over 2
billion users
??
Over 1
billion of them are on mobile devices (per KPCB)
●?
2014: ~1B hosts (~3B users)
CSE 222A – Lecture 2: Layering & End-to-End
14
End hosts are changing!
CSE 222A – Lecture 2: Layering & End-to-End
15
Internet History
●? Goal: effective multiplexed use of existing networks
??
Minimal support from underlying networks
e.g., no support for multicast, real-time, fast failover, congestion
control, etc.
??
Packet switching (fine-grained resource sharing)
AT&T said it could not be built
??
Routers connecting networks
●? Recommended reading:
??
“Where Wizards Stay Up Late”
by Hafner & Lyon
CSE 222A – Lecture 2: Layering & End-to-End
16
Internet History: Other Goals
●? Survive hardware failure
●? Support multiple types of applications
●? Run on wide variety of networks
●? Distributed management of resources
●? Cost-effective
●? Low cost host attachment
●? Accounting
CSE 222A – Lecture 2: Layering & End-to-End
17
Survivability
●? Internet approach
??
Cheap, commodity components
??
Stateless routers + self-healing
??
Keep routing simple (non-adaptive)
??
End to end recovery
●? Telephone approach
??
Ultra reliable switches
??
Make the network very smart
CSE 222A – Lecture 2: Layering & End-to-End
18
OSI Model
Presentation
Application
Session
Transport
Network
Data link
Physical
Ultimate data
destination
Format
conversion
Reliable, ordered
delivery
Routing/
Internetworking
Data framing
over links
Bits on
the wire
Interaction across
presentation
Presentation
Application
Session
Transport
Network
Data link
Physical
Web browser
ASCII/XDR
Restartable file
transfer
TCP
IP
Ethernet, ATM
SONET, 100BT
Example
Function
CSE 222A – Lecture 2: Layering & End-to-End
19
OSI Model
Presentation
Application
Session
Transport
Network
Data link
Physical
Ultimate data
destination
Format
conversion
Reliable, ordered
delivery
Routing/
Internetworking
Data framing
over links
Bits on
the wire
Interaction across
presentation
Function
Where does security go?
What about reliability?
CSE 222A – Lecture 2: Layering & End-to-End
20
OSI Model Discussion
●? OSI standardized before implemented
??
IETF philosophy: “We reject kings, presidents and voting. We
believe in rough consensus and working code”
??
IETF requires two working/interoperable versions before
considering a standard
●? Modular design, but some boundaries are arbitrary
??
Why seven layers?
??
What exactly is the session layer?
??
Much basic network functionality at multiple layers
Reliability, flow control, security
CSE 222A – Lecture 2: Layering & End-to-End
21
Internet Architecture
●? IP Hourglass:
NFS
HTTP
email
rlogin
RPC
Telecollaboration
TCP
RSVP
IP
Ethernet
ATM
packet radio
UDP
SONET
PPP
air
modem
100BT
n? Layering not strict
?? Can define new abstractions on any existing protocol
CSE 222A – Lecture 2: Layering & End-to-End
22
Layering in Applications
●? Bottlenecks
??
Boundary crossings
??
Copies
??
Context switches
●? Layering nice way to
logically consider protocols
??
May not lead to fastest
implementation
??
But! Processors are getting
faster… people are getting
more expensive
app
socket
TCP
IP
ether
user
kernel
copy
copy
Packet
arrives
TCP
revc
hw intr
sw intr
task context
CSE 222A – Lecture 2: Layering & End-to-End
23
Socket Abstraction
●? Best-effort packet delivery is a clumsy abstraction
??
Applications typically want higher-level abstractions
??
Messages, uncorrupted data, reliable in-order delivery
●? Applications communicate using “sockets”
??
Stream socket: reliable stream of bytes (like a file)
??
Message socket: unreliable message delivery
socket
socket
User process
User process
Operating
System
Operating
System
CSE 222A – Lecture 2: Layering & End-to-End
24
Two Basic Transport Features
●?
Demultiplexing: port numbers
●?
Error detection: checksums
Web server
(port 80)
Client host
Server host 128.2.194.242
Echo server
(port 7)
Service request for
128.2.194.242:80
(i.e., the Web server)
OS
Client
IP
payload
detect corruption
CSE 222A – Lecture 2: Layering & End-to-End
25
Two Main Transport Layers
●? User Datagram Protocol (UDP)
??
Just provides demultiplexing and error detection
??
Header fields: port numbers, checksum, and length
??
Low overhead, good for query/response and multimedia
●? Transmission Control Protocol (TCP)
??
Adds support for a “stream of bytes” abstraction
??
Retransmitting lost or corrupted data
??
Putting out-of-order data back in order
??
Preventing overflow of the receiver buffer
??
Adapting the sending rate to alleviate congestion
??
Higher overhead, good for most stateful applications
CSE 222A – Lecture 2: Layering & End-to-End
26
Sharing the ‘Net
●? Best-effort network easily becomes overloaded
??
No mechanism to “block” excess calls
??
Instead excess packets are simply dropped
●? Examples
??
Shared Ethernet medium: frame collisions
??
Ethernet switches and IP routers: full packet buffers
●? Quickly leads to congestion collapse
Load
Goodput
“
congestion
collapse”
Increase in load that
results in a decrease in
useful work done.
27
Adjusting to Congestion
●? End hosts adapt their sending rates
??
In response to network conditions
●? Learning that the network is congested
??
Shared Ethernet: carrier sense multiple access
?? Seeing your own frame collide with others
??
IP network: observing your end-to-end performance
?? Packet delay or loss over the end-to-end path
●? Adapting to congestion
??
Slowing down the sending rate, for the greater good
??
But, host doesn’t know how bad things might be…
CSE 222A – Lecture 2: Layering & End-to-End
28
Ethernet Back-off Mechanism
●? Carrier sense: wait for link to be idle
??
If idle, start sending; if not, wait until idle
●? Collision detection: listen while transmitting
??
If collision: abort transmission, and send jam signal
●? Exponential back-off: wait before retransmitting
??
Wait random time, exponentially larger on each retry
CSE 222A – Lecture 2: Layering & End-to-End
29
TCP Congestion Control
●? Additive increase, multiplicative decrease
??
On packet loss, divide congestion window in half
??
On success for last window, increase window linearly
t
Window
halved
Loss
CSE 222A – Lecture 2: Layering & End-to-End
30
End-To-End Argument
Application
TCP
IP
Router
Where to
Place
Functionality?
Link Layer
CSE 222A – Lecture 2: Layering & End-to-End
31
End-to-End Argument
●? Functionality should be implemented at a lower layer if
and only if it can be correctly and completely
implemented there
??
Should not be implemented at lower level if redundant with
higher level
??
Performance optimizations are not a violation
●? Early example
??
ARPANet provided reliable link transfers between switches
??
Packets could still get corrupted on host-to-switch link, or
inside switches
??
Want to know if host
acted on the request not whether it
received it
CSE 222A – Lecture 2: Layering & End-to-End
32
Example: Reliable File Transfer
●?
From disk on file (web) server over network to client
??
Disk can introduce bit errors
??
Host I/O buses can introduce bit errors
??
Packets can get garbled, dropped, misordered at any node
●?
Solution: integrity check on file, not per packet or per hop
2
4
3
1
CSE 222A – Lecture 2: Layering & End-to-End
33
Hop by Hop for Performance
●? Does not violate end to end argument to provide
reliability at link layer, even if not required for correct
operation
●? For file transfer application, consider varying
conditions:
??
Prob(corrupted/lost packet per link) = p
??
Prob(packet lost end to end), avg. 15 hops across Internet
p = 0.0001% => Prob(loss) = 0.0015%
p = 1% => Prob(loss) = 14%
●? Chance of file corruption grows with size of file
??
Potentially retransmit entire file for one lost packet?
CSE 222A – Lecture 2: Layering & End-to-End
34
Application-Specific Semantics
●? Example: move reliability into the network
communication protocol (such as TCP)
??
Certain computational and bandwidth overheads to
implementing reliable, in-order delivery in the network
??
Not all applications want to pay this overhead
●? Real-time voice/audio
??
Better to drop a packet, rather than hold up later packets
??
On-time delivery more important than
reliability
●? Applications should be able to pick and choose the
semantics they require from underlying system
??
Active Networks, overlay networks
CSE 222A – Lecture 2: Layering & End-to-End
35
Other Examples
●? Distributed transactions
??
Exactly once vs. at most once vs. at least once
●? Security
??
Security only as strong as weakest assumption/link
●? Suppressing duplicate messages
??
Duplicate effort between network and application layer
●? Mis-ordered messages
CSE 222A – Lecture 2: Layering & End-to-End
36
Discussion
●? When should the network support a function?
??
E.g., link-layer retransmission in wireless networks?
●? Who’s interests are served by the e2e argument?
●? How does a network operator influence the network
without violating the e2e argument?
●? Does the design of IP and TCP make it
hard to violate
the e2e argument?
??
E.g., middlebox functionality like NATs, firewalls, proxies
●? Should the e2e argument apply to routing?
CSE 222A – Lecture 2: Layering & End-to-End
37
For Next Class…
●? Read P&D Chapter 3
●? Read and review Cerf & Kahn `74
●? Keep thinking about term project ideas/groups
??
Suggestions available by the end of this week
CSE 222A – Lecture 2: Layering & End-to-End
38
