Transcript Systems Programming 8 (Connection

Systems Programming
Meeting 8:
Connection-Oriented
Communication
GWU CS 259 Brad Taylor Spring 2004
1
Objectives
• Connection-Oriented Communication
• Transmission Control Protocol / Internet
Protocol (TCP/IP)
• Client-Server Model
• Simple Client-Server Implementation: UICI
• UNIX Sockets
• Project Status Briefs (85% code review)
• Assignment 4: due in 2 weeks, finish project
testing this week!
GWU CS 259 Brad Taylor Spring 2004
2
Big difference between no bits of information and even a few
Power of Communication
• Communication very strange topic (all spent years on it)
– Sounds trite, but incredible force
– New ways to transmit/represent information = revolution
– Speedup = more transmission; does reception also increase? {D}
• Examples:
– Books enabled communication through time, across geography:
changed world
– Radio communication over air: changed planet
– Telephone escape geographic tyranny, talk to anyone in world:
try to find someone who hasn’t used it
– TV, Internet revolutionary implication: watch CSci 259 in bed
• Can view communication as transport
– Moving signal over geography
– New transport = revolution: Ships, Trains, Cars, Planes, Rockets
GWU CS 259 Brad Taylor Spring 2004
3
Power of Computer
Networks
• Computer networks:
– Send symbolic information (1’s and 0’s) between
“nodes”
01010111001
B
A
• Universal substrate, same plumbing supports
many revolutions:
–
–
–
–
email: talk to anyone in world in a different way
news: broadcast to bunch of different people
Web: now even grandma uses computer
Implications still playing out…
GWU CS 259 Brad Taylor Spring 2004
4
Computer Networks
Carry Symbols
Each time new transport, revolution
• Transportation history dominated by moving things
– Covered wagons, Trucks, Railways, Cars move people & goods
• Networks different, move bits
– The great invention: the packet: encapsulates information in
opaque sequence of 1s and 0s
Client view: tell A “Hello”
A
1010111... Network view
– Result: totally general, can carry any sequence of bits
• Information is weird
–
–
–
–
–
Most states, illegal to wrap a chicken in another
Recursive: wrap packet in another packet
Partitionable: split packet arbitrarily and then reassemble
Time independent: information can flow at different rates
Encoding independent: translate into another form and back
Generic: completely general error detection/correction
Aren’t allowed to split up people and then reassemble
GWU CS 259 Brad Taylor Spring 2004
5
Example Networks
• ARPAnet:
– First widely-used network, developed early 70s, still in use
– Connects large timesharing systems with leased phone lines
cross-country
– Provides mail, file transfer, remote login
• Usenet:
– Developed late 70s - early 80s
– Unix systems phone each other to send mail & transfer files
• Local area networks (LANs)
– Developed early 80s to connect workstations
– Ethernet most popular
• Internetworks:
– Mechanisms for tying existing networks together
GWU CS 259 Brad Taylor Spring 2004
6
Networking Big Win
• Allows decentralization (yet still share)
– Rather than one big thing, build pieces and connect
– Result: biggest things in the world are network-based
(“distributed systems”): Internet, telephone system …
• Decentralization gives:
– Robustness: one part breaks, who cares
– Piecemeal construction: rather than all at once (investment $)
– Modularity: end point internals don’t matter; just adhere to
protocol and can talk
– Massive concurrency: each node doing its own thing
• But how to connect heterogeneous, ever-changing,
massively complex network?
GWU CS 259 Brad Taylor Spring 2004
7
A Solution: Layers
• Consider networks as made of three main layers:
– Link level: physically encode bits on “wire” (line segment)
0101010
0101011
– Network layer: connecting segments, addressing (locating points
on graph) and routing (navigating graph)
a
b
– End-to-end layer: make networking simple and reliable
0101010
0 1 0 1 0 1 0 1 0
GWU CS 259 Brad Taylor Spring 2004
0101010
8
How Do Layers Work?
• Rules:
– Layers do not look inside packet
– If needing auxiliary information, attach header to
message on way down, strip on way up
Application
TCP
IP TCP
End-to-end (TCP)
Network level (IP)
TCP
IP TCP
eth IP TCP
eth IP TCP
Link level (eth)
– Protocol = Contract to talk to others at same level
GWU CS 259 Brad Taylor Spring 2004
9
Why layers?
• Major reason: independence
– Layers treat each other’s headers as opaque
– Change lower without
TCP
changing upper
AN2
– Change upper without
changing lower
TCP
• Placement
ETH
UDP
FDDI
ATM
BLAST
eth
– Technology evolve at different rates? Layer between
– Functionality needed by most clients? Move down
– Functionality needed by some clients? Move up
GWU CS 259 Brad Taylor Spring 2004
10
Networking Fundamentals
• Networking connects geographically separated things
• Implication 1: speed of light important
– 1ft/nanosecond
15 milliseconds
Boston
SF
– Can’t get better
• Implication 2: sharing (multiplexing)
– Laying pipe very expensive:
» ~10 Billion to replace wire with fiber in Britain;
» slice of radio spectrum cost 1.7 Billion at FCC auction
– Amortize cost by putting multiple machines on each link.
– Multiple users, one resource = need to multiplex
– We’ve had sharing before; what’s new? Blindness
GWU CS 259 Brad Taylor Spring 2004
11
Performance: Latency &
Bandwidth
• Latency: how long minimum communication takes
• Bandwidth: number of bits per time unit
bandwidth
link
latency
• Usual ways to minimize latency?
– Caching reduces latency when cache hits
– Prefetching hides latency
– Concurrency tolerates latency by doing something else
• Save bandwidth?
– Which latency trick(s) save bandwidth?
– How to trade CPU for bandwidth?
– Save both: change representation
GWU CS 259 Brad Taylor Spring 2004
12
Recursion Theme
• Construction:
– Base case: link
– Inductive step: connect links (or networks)
• Use: encapsulate packet in another, in another, …
– Universal transport: send message over any network
– Encapsulation: send message using another layer: wrap up,
handoff, unwrap
X
x
Y X
X
y
x
– Big use: send new protocols across old routers
• Presence: each layer in computer system has network
– CPU connected to disk by I/O bus, cache connected to memory
by memory bus, CPU to register by wire…
GWU CS 259 Brad Taylor Spring 2004
13
Recursion: It’s Networks
All the Way Down!
• Every layer in computer has three components
– Computation, Memory, Connection network
Internet
100ms
10M/100TB
LAN
500/50GB
1ms
1us
100MB RAM
CPU
1/100MB
3ns
Register
How fast?
How many?
• And up, too! Social mimics technical: Network standards
bodies mimic network itself
GWU CS 259 Brad Taylor Spring 2004
14
Connectivity Theme
Variations
• Point-to-point vs one-to-all (broadcast) connectivity
– Broadcast medium cheap; problem: contention
• Indirect connectivity:
– Rarely have point-to-point connection with destination
– Usually messages “hop” through multiple intermediaries
a
switch
b
– Router: connect one network to another (=> internetwork)
• No connectivity: must deal with failure constantly
– Networks tend to be big
– As n increases, # of dead things does also (link down)
– As n increases, # of overloaded things does also (msg lost)
GWU CS 259 Brad Taylor Spring 2004
15
Synthesized Reliability
Theme
Networks are unreliable
– Losses, corruptions, reorders and duplicate messages
– False premise: must make lower levels perfect
General approach: detect + retransmission
– General trick: something dead doesn’t respond: So wait
“reasonable amount of time”; no response, assume dead
– Lost messages reliability: Send message, wait for
acknowledgement, if timeout, re-send; repeat, as needed
– Corruption reliability: Use checksum to detect flipped bits;
discard if doesn’t match
– Duplication in time, rather than in space
GWU CS 259 Brad Taylor Spring 2004
16
The End-to-End Argument
• Low level functions either redundant or cheap
compared to cost of providing them where needed
– Low level incorporation: everyone must pay for it
• Useless security example:
– Safely send credit card #: encrypt on local machine, send it,
and end host decrypts
enc(m) = x
x
x
dec(x) = m
– LAN also encrypting useless (only 1 link)
• Harmful reliability example:
– Links try to synthesize reliability using retransmission
– Delay introduced (send; wait; retransmit; repeat)
– If delay sensitive (voice, video) this is exactly wrong thing to do!
Better to drop packets and continue
GWU CS 259 Brad Taylor Spring 2004
17
Memory & Wire Duality
• Every layer of computer made of three components
– Computation, Storage, Communication
• The latter two are the same thing:
– Storage: communicate through time (multiplexed in space)
– Wires: communicate through space (multiplexed in time)
• Recursively implemented in terms of each other
– Storage: use wire to get data from main memory into cache into
register into CPU
– Wires: use memory to hold message for sending, and to catch
message while receiving
• Connected in terms of each other
– Wires: Use a node to buffer and forward
– Memories: Use a wire to connect
GWU CS 259 Brad Taylor Spring 2004
18
Memory & Wire Duality
(con’t)
• Reliability: both use duplication
• Duplication in time:
– Wires = timeout + resend (using memory)
– Memory = checkpoint + restore from backup (using wire)
• Duplicate in space:
– Wires = send on multiple paths (duplicate wires)
– Memory = multiple copies (duplicate memory)
• General naming issues are the same:
– Name spaces, mapping names to addresses using table, using
address to find object
– “/foo/bar” to a disk block using directories and inodes
– www.seas.gwu.edu to ip address to ethernet address using
various name tables
GWU CS 259 Brad Taylor Spring 2004
19
Principles into Practice
• Network layer
– Gets bits from one network collection end to another
r2
r3
b
a
r1
f
e
c
– Uses globally unique names, routers, portable
message abstraction; example: internet protocol (IP)
• End-to-end layer
– Interface between applications & network some
successful end-to-end protocols
– Turning “best effort” into usable interface (such as
deriving TCP from first principles)
GWU CS 259 Brad Taylor Spring 2004
20
Success story #1: UDP
User Datagram Protocol: best-effort, process-to-process
– Lives on top of IP: adds corruption detection and “ports” so
packets can be addressed to a process on host
– Many header fields are hidden
UDP data cksum
src port
dst port
IP Hdr cksum
src IP addr
dst IP addr
GWU CS 259 Brad Taylor Spring 2004
Host: IP addr = 18.26.0.1
Port 1028
Port
Port 18
92
21
Success story #2: TCP
Transmission control protocol
– Reliable, in-order, process-to-process, two-way byte stream
Like UDP:
– Layered on top of IP; adds ports and data checksums
TCP
Unlike UDP:
IP
– Connection based
– Recovers from packet loss, duplication, corruption, reordering
– “how????” from first principles
GWU CS 259 Brad Taylor Spring 2004
22
Lost packets
sender
message
receiver
time
• Causes:
– Traffic burst causes router buffers to overflow
– Link corrupts packet (wireless up to 40% packet loss)
– How to fix?
GWU CS 259 Brad Taylor Spring 2004
23
Lost acks
sender
M
timout
ack
receiver
time
What will the result be?
GWU CS 259 Brad Taylor Spring 2004
24
Delayed acks =
Packet Duplication
sender
receiver
M
timout
ack
M
Possible causes:
– “congestion” in the network that delays packet
– a too-short timeout (how big should it be anyway?)
GWU CS 259 Brad Taylor Spring 2004
25
Connection Setup:
Three Way Handshake
sender
receiver
TCP is a two-way (duplex) pipe
– Different sequence number for each direction
– Asymetric open: server does a passive “listen,” client
does an active “open” (sends first message)
GWU CS 259 Brad Taylor Spring 2004
26
The two army problem
B
A
C
– C can beat either A or B, but not both.
– A and B want to agree on a time to simultaneously attack
– Also: The Byzantine Generals Problem
GWU CS 259 Brad Taylor Spring 2004
27
Protocol:
Naming, Setup & Guarantees
• Addressing: identifying receivers
– IP = host-to-host: every host has a unique IP address
– UDP & TCP = process-to-process: extend IP with a port
that is coupled to a process within a host
– Telephone: “host-to-host”: every connection point
associated with a unique phone number
• Connection model:
– IP, UDP, Ethernet: connectionless: Send packet
– Telephone, ATM, TCP: connection-based: Explicitly set
up connection before sending data; tear down
connection when done (richer service models easier)
• Data delivery model: once data entrusted to
protocol, what guarantees are made?
GWU CS 259 Brad Taylor Spring 2004
28
Two Connection Models
• Connectionless (or “datagram”):
– Packets contain enough information so routers can
decide how to get it to its final destination
b
b
B
A
C
• Connection-oriented (or “virtual circuit”)
– Connection between two nodes first set up
– Label it (called virtual circuit identifier: VCI)
– All packets carry label
1
1
1
B
A
GWU CS 259 Brad Taylor Spring 2004
C
29
Data Delivery Models
• Best-effort:
–
–
–
–
IP: packets can be lost, delayed & packet data corrupted
UDP: layers corruption detection on top of IP
Ethernet: may lose packets, detects corruption
ATM: can lose packets, detects corruption & makes reordering
less likely
• TCP: Reliable, in-order byte stream
– two-way byte stream; prevents: loss, duplication, corruption,
reorder
• Mostly reliable, quality-of-service: telephone
– two-way voice service with small end-to-end delays
– guarantees accepted calls will run to completion
– easier to build on ATM than non-connection based
GWU CS 259 Brad Taylor Spring 2004
30
Client-Server Model
• Many network communication types
use: mail, ftp, telnet, rlogin, http, and
nfs
• Server waits for requests
• Client requests service from server
• Communication endpoint specified
by host address and port number
• Port numbers differentiate
communication channels; standard
port numbers allow clients to request
services; for example:
mail: 25
ftp: 21
telnet: 23
rlogin 513
http: 80
nfs: 2049
GWU CS 259 Brad Taylor Spring 2004
31
Connection-Oriented
Communication
• Client sets up a connection using the Server's
well-known port number
• Then communicates over a private
communications channel
GWU CS 259 Brad Taylor Spring 2004
32
Connection-Oriented Protocol
• Server waits for client
request monitoring
communication
endpoint whose
address is known to
clients
• When client request
arrives, server creates
new communication
endpoint to handle
two-way symmetric
communication with
client
GWU CS 259 Brad Taylor Spring 2004
33
UICI: Simple Connection-Oriented
Client-Server Implementation
• Server:
–
–
–
–
Assign file descriptor (fd) to port for listening
Wait for connection request on that fd
Return communication file descriptor when request comes
Handles connection by reading or writing, using the
communication file descriptor
– Requests may be handled serially, or forking a child while the
parent is waiting for another request
• Client:
– Request connection from particular port on a particular host
– If successful, returns a file descriptor for communication
– Communicates by doing reads and writes on this file descriptor
GWU CS 259 Brad Taylor Spring 2004
34
UICI: Client-Server Interaction
GWU CS 259 Brad Taylor Spring 2004
35
Mapping UICI to Sockets
• UICI functions and UNIX Socket
functions:
– u_open => {socket, bind, listen}
– u_accept => {accept}
– u_connect => {socket, connect}
– u_read => {read}
– u_write => {write}
GWU CS 259 Brad Taylor Spring 2004
36
Socket Functions
• UICI functions and UNIX Socket
functions :
– socket creates a file descriptor
– bind associates a file descriptor with a port
and machine
– listen sets up buffers
– accept waits for a connection request
– connect requests a connection to a server
GWU CS 259 Brad Taylor Spring 2004
37
TCP/Socket Example:
Bare Minimum Client/Server
• Server:
– Creates a server socket bound to a fixed
port (12345)
– Receives a message from a client and
displays it
• Client:
– Creates a client socket
– Repeatedly sends the message "Hi" out of
this socket to the server
GWU CS 259 Brad Taylor Spring 2004
38
TCP Minimum:
tcpServer.c
#include "def"
main()
{
int sd, psd;
struct
sockaddr_in name;
char
buf[1024];
int
cc;
sd = socket
(AF_INET,SOCK_STREAM,0);
name.sin_family = AF_INET;
name.sin_addr.s_addr =
htonl(INADDR_ANY);
name.sin_port = htons(12345);
GWU CS 259 Brad Taylor Spring 2004
bind( sd, (SA *) &name,
sizeof(name) );
listen(sd,1);
psd = accept(sd, 0, 0);
close(sd);
for(;;) {
cc=recv(psd,buf,sizeof(buf
), 0) ;
if (cc == 0) exit (0);
buf[cc] = NULL;
printf("message received:
%s\n", buf);
}
}
39
TCP Minimum:
tcpClient.c
main(argc, argv )
int argc;
char *argv[];
hp = gethostbyname(argv[1]);
bcopy ( hp->h_addr,
&(server.sin_addr.s_addr), hp>h_length);
server.sin_port = htons(12345);
connect(sd, (SA *) &server,
sizeof(server));
for (;;) {
send(sd, "HI", 2, 0 );
printf("sent HI\n");
sleep(2);
}
{
int sd;
struct
sockaddr_in server;
struct hostent *hp,
*gethostbyname();
sd = socket
(AF_INET,SOCK_STREAM,0);
}
server.sin_family = AF_INET;
GWU CS 259 Brad Taylor Spring 2004
40
Project Status Report
Nate: GLIB Loop Example …
Group I: Dan, Ricardo & Kamal: “Wire Socket”
Group II: Clayton, Jason: “Named Pipes”
Group III: Brooke, Nush, Ram: “Shared Memory, Semaphores & Futexs”
Integration: Nate & Brad
Issues to discuss:
Code Review for Each Group
Error checking
Rough draft code submission for integration review
Further Guidance, Questions
GWU CS 259 Brad Taylor Spring 2004
41